Every proof on this site is built out of the same handful of logical moves: "for all," "there exists," "if... then," and "not." The first half of this page makes those moves precise, especially the two that trip people up most: changing the order of quantifiers, and negating a statement. The second half puts them to work on relations, which are how mathematicians say two different things are "the same in the way we care about." That idea (equivalence classes) is how abstract algebra glues things together: remainders, cosets, and quotient groups are all equivalence classes.
You've been reading these symbols since the Sets page. Here they are officially, starting with the two quantifiers.
$\forall$ means "for all" or "for every" (universal quantifier).
A "for all" statement makes a big claim: no exceptions anywhere. Its partner claims much less: one example is enough.
$\exists$ means "there exists" (existential quantifier).
Next, the ways to connect two statements $X$ and $Y$.
$X \implies Y$ means "if $X$ then $Y$" or "$X$ implies that $Y$" (conditional statement).
A conditional only makes a promise about what happens when $X$ is true. When $X$ is false, the promise can't be broken, so $X \implies Y$ counts as true. That surprises almost everyone the first time, so here it is with actual numbers.
Which of these are true? (a) "If $2 + 2 = 4$, then $3$ is odd." (b) "If $2 + 2 = 4$, then $3$ is even." (c) "If $2 + 2 = 5$, then $3$ is even." (d) "If $2 + 2 = 5$, then $3$ is odd."
Only (b) is false: its "if" part is true and its "then" part is false. In (a) both parts are true. In (c) and (d) the "if" part is false, so the promise was never tested, and both are true. A statement that is true because there's nothing to check is called vacuously true.
All four cases at once, with T for true and F for false:
$$\begin{array}{cc|c} X & Y & X \implies Y \\ \hline \text{T} & \text{T} & \text{T} \\ \text{T} & \text{F} & \text{F} \\ \text{F} & \text{T} & \text{T} \\ \text{F} & \text{F} & \text{T} \end{array}$$
Sort the four ways a day can go, and see which ones break the promise.
Drag each day into a bin, then check.
Going both ways gets its own symbol.
"iff" is not a typo. It's "if and only if" with the boring parts cut out. Spell-check will fight you on this forever.
$X \iff Y$ means "$X$ if and only if $Y$" (iff), that is, $X \implies Y$ and $Y \implies X$ (biconditional statement).
A biconditional is two promises at once, so it breaks in two rows of the table instead of one. Predict each row before you reveal it.
Tap each ? to predict T or F, then reveal.
And finally, the one that flips everything.
$\neg$ looks like a tiny hockey stick. Negation is the hockey stick that checks your statement into the boards.
$\neg X$ means "not $X$" (negation).
This one has more costumes than any other symbol, so expect to see it written other ways.
Other books write "not X" as ~X or with a bar over the X. This site always uses $\neg$, and saves the squiggle $\sim$ for relations, which show up in the second half of this page.
Here's all of that at work in a definition you already know.
On the Sets page, $\emptyset \subseteq A$ for every set $A$. In this language: "$\forall a \in \emptyset$, $a \in A$." There's no $a \in \emptyset$ to check, so the statement can't fail.
"Every unicorn in this room is purple" is a true statement. There are no unicorns in this room, so there's nothing to check. Mathematicians call this vacuously true. Everyone else calls it cheating.
Write the definitions of $A \subseteq B$ and $A \not\subseteq B$ using quantifiers.
Compare the two lines: "$\forall$" became "$\exists$", and "$\in B$" became "$\notin B$." The second line is the negation of the first, and that pattern is a rule we'll meet shortly.
Statements with two quantifiers are where it gets interesting, because the order you read them in matters.
Consider the following statement: $\forall n \in \mathbb{Z}, \exists x \in \mathbb{Q}$ such that $x - n = 1$. What does it mean, and is it true?
It means "for every integer $n$, there exists a rational number $x$ such that $x - n = 1$."
This is a true statement, since, for $n \in \mathbb{Z}$, we may take $x = n + 1$. Then $x \in \mathbb{Q}$ and $x - n = 1$.
Now swap the two quantifiers and change nothing else.
Reversing the order of the quantifiers in the previous example gives: $\exists x \in \mathbb{Q}$ such that $\forall n \in \mathbb{Z}, x - n = 1$. What does it mean, and is it true?
This means "there exists a rational number $x$ such that, for every integer $n$, we have $x - n = 1$."
This is a false statement. To see why, note that for $x \in \mathbb{Q}$, if we take $n$ to be the smallest integer which is greater than or equal to $x$, then $x - n \le 0$, so $x - n \neq 1$.
Same symbols, opposite answers. In the first statement, $x$ is chosen after $n$, so it can depend on $n$: the answer $x = n + 1$ changes every time $n$ does. In the swapped one, $x$ is chosen first, once, and then it has to work for every $n$ at the same time. A good way to feel the difference is to play it as a game against an opponent.
You play $\exists x$, the opponent plays $\forall n$. You win a round when $x - n = 1$. Whoever's quantifier comes first has to move first.
The game is a reliable way to read any quantified statement: $\forall$ is your opponent's move, $\exists$ is yours, and you take turns from left to right.
Anything chosen after an "$\exists$" may depend on everything to its left, but nothing to its right. In "$\forall n\ \exists x$," $x$ may depend on $n$. In "$\exists x\ \forall n$," $x$ is fixed before anyone has said what $n$ is. When you prove an $\exists$ statement, check that your choice only uses variables that were already chosen.
When both variables come from a small set, you can see all four orders at once. Light up the pairs where a condition holds: "for every $x$ there is a $y$" asks every row for a lit cell, while "there is one $y$ for every $x$" needs a whole column.
Pick a rule or tap cells to make your own. Tap a statement to see why it's true or false.
Now try calling a few before the game is played.
Swapping the quantifiers doesn't always change the answer, though. Try one where both orders come out the same way.
Prove or disprove: $\exists x \in \mathbb{Z}$ such that $\forall n \in \mathbb{Z}$, $xn = n$. Then decide whether the swapped statement, $\forall n \in \mathbb{Z}, \exists x \in \mathbb{Z}$ such that $xn = n$, is true.
True. Let $x = 1$. Then $\forall n \in \mathbb{Z}$, $xn = 1 \cdot n = n$. $\blacksquare$
The swapped statement is also true: for each $n$, the same $x = 1$ works. In general, "$\exists x\ \forall n$" implies "$\forall n\ \exists x$": an $x$ that works for every $n$ certainly works for each one. The other direction can fail, as the two examples before the duel showed.
Here's one of the most useful tricks for proving an if-then statement: prove a different-looking statement that means exactly the same thing.
The contrapositive of the statement $X \implies Y$ is the statement $\neg Y \implies \neg X$.
"Different-looking but the same" is the whole point.
The statement $X \implies Y$ is equivalent to the statement $\neg Y \implies \neg X$. (contrapositive)
Why? If $X \implies Y$ holds and $Y$ fails, then $X$ can't have been true, or $Y$ would have been true too. Read it in plain English: "every $X$ is a $Y$" says the same thing as "anything that isn't a $Y$ isn't an $X$."
On the Properties of Integers page, the proof of the well-ordering principle starts with "Consider the contrapositive." Proving "$A \neq \emptyset \implies A$ has a smallest element" head-on is awkward, but its contrapositive is a clean induction.
Write each statement as a conditional, then write its contrapositive.
Both statements quietly begin with "for all": "for every $n$, if $n \in \mathbb{N}$ then $n \in \mathbb{Q}$." That's what makes the second pair false: it fails for some $x$. Take $x = \sqrt{2}$, which is in $\mathbb{R}$ but not in $\mathbb{Q}$.
A statement and its contrapositive are always true together or false together. There's a look-alike that doesn't have that property.
The converse of the statement $X \implies Y$ is the statement $Y \implies X$.
It's easy to mix the two up, because both of them flip the sides.
Don't flip without negating. The converse is a different statement. "If $n \in \mathbb{N}$ then $n \in \mathbb{Q}$" is true, but its converse "if $n \in \mathbb{Q}$ then $n \in \mathbb{N}$" is false ($n = \frac{1}{2}$). Flip and negate: same statement. Flip only: different statement.
A picture makes the difference obvious. If every $X$ is a $Y$, the circle for $X$ sits inside the circle for $Y$. Drag $n$ around and see which statements it can break.
The two statements that broke together, the converse $Y \implies X$ and the inverse $\neg X \implies \neg Y$, are contrapositives of each other. Build all four versions yourself, one flip or negation at a time.
The contrapositive shines when the conclusion is easier to work with than the hypothesis.
Let $n \in \mathbb{Z}$. Write the contrapositive of "if $n^2$ is even then $n$ is even," and use it to prove the statement.
Contrapositive: "if $n$ is odd then $n^2$ is odd."
Proof. Suppose $n$ is odd, so $n = 2k + 1$ for some $k \in \mathbb{Z}$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. Since the contrapositive is true, so is the original statement. $\blacksquare$
(Proving it directly is much harder: knowing $n^2 = 2m$ doesn't hand you anything about $n$.)
To prove a statement is false, you prove its negation is true. So you need to be able to negate anything, mechanically, without having to think hard about it. Two rules do all the work.
Negation of a universally quantified statement: $\neg (\forall x \in A, X)$ (the negation of "for all $x \in A$, statement $X$ holds") is equivalent to $\exists x \in A$ such that $\neg X$ (there exists an $x \in A$ such that statement $X$ does not hold).
That's the counterexample rule: to break a "for all," one bad $x$ is enough. The other rule is its mirror image.
Negation of an existentially quantified statement: $\neg (\exists x \in A \text{ such that } X)$ (the negation of "there exists an $x \in A$ such that statement $X$ holds") is equivalent to $\forall x \in A, \neg X$ (for every $x \in A$, statement $X$ does not hold).
Put together: the $\neg$ walks through the statement from left to right. Every quantifier it passes flips ($\forall \leftrightarrow \exists$), and when it reaches the end, it negates the condition. Here's the swapped statement from before.
Negate the false statement $\exists x \in \mathbb{Q}$ such that $(\forall n \in \mathbb{Z}, x - n = 1)$.
Negation: $\forall x \in \mathbb{Q}, \neg(\forall n \in \mathbb{Z}, x - n = 1)$.
Equivalently: $\forall x \in \mathbb{Q}, \exists n \in \mathbb{Z}$ such that $x - n \neq 1$. (true)
That's exactly what the opponent was doing in the duel: whatever $x$ you picked, they found an $n$ with $x - n \neq 1$.
Watch the $\neg$ move through a statement one step at a time.
Pick a statement, then press STEP to push the $\neg$ one tile to the right. Watch what happens to each tile it passes.
Now build one yourself. The tray has a few tiles that look almost right.
Now the full process, including the part that comes before any writing: figuring out whether the statement is even true.
Prove or disprove: $\forall t \in \mathbb{R}, (\exists n \in \mathbb{Z} \text{ such that } nt > t)$.
Scratch work / thought process: First try some examples and decide whether you think the statement is going to be true for every $t \in \mathbb{R}$:
Negation: $\exists t \in \mathbb{R}$ such that $\neg(\exists n \in \mathbb{Z} \text{ such that } nt > t)$.
Equivalently: $\exists t \in \mathbb{R}$ such that $\forall n \in \mathbb{Z}, \neg (nt > t)$.
$\exists t \in \mathbb{R}$ such that $\forall n \in \mathbb{Z}, nt \le t$. (true)
Proof that this is true: Let $t = 0$. Then $\forall n \in \mathbb{Z}$, $nt = 0 = t$, so $nt \le t$. $\checkmark$
Since the negation of the original statement is true, the original statement itself is false.
The scratch work is the real lesson in that example.
The cases $t > 0$ and $t < 0$ both work, and they tempt you to start writing a proof. The one case that breaks the statement, $t = 0$, is the one everybody forgets. Before you try to prove a "for all," always test the edge cases: $0$, negatives, $1$, and the empty set.
Practice the hunt. Some of these claims hold for a long time before they break, and one of them never breaks at all.
Your turn to negate one.
Negate the statement $\forall x \in \mathbb{R}, \exists y \in \mathbb{R}$ such that $y^2 = x$. Which one is true, the statement or its negation? Prove it.
Negation: $\exists x \in \mathbb{R}$ such that $\forall y \in \mathbb{R}$, $y^2 \neq x$.
The negation is true. Proof. Let $x = -1$. For every $y \in \mathbb{R}$, $y^2 \ge 0 > -1$, so $y^2 \neq -1$. $\blacksquare$
So the original statement is false. (Over $[0, \infty)$ instead of $\mathbb{R}$, the original would be true: take $y = \sqrt{x}$.)
Time to use all that logic on a new object. A relation is a rule that says which elements of a set are "related" to which others.
The Functions page promised relations as subsets of $A \times B$. Here we only need the case $A = B = S$, a relation on one set $S$.
A relation $R$ (or $\sim$) on a set $S$ is a subset $R \subseteq S \times S$.
Notation: If $(a, b) \in R$ then we write $aRb$ ($a$ is related to $b$).
That's the whole definition: a relation is just a list of which ordered pairs are related. It can be any list at all, which is why there are so many examples.
Six relations, numbered (1) to (6), which we'll keep coming back to.
On a finite set you can draw a relation as a grid: row $x$, column $y$, and the cell is filled when $(x, y)$ is in the relation. Here are $R_1$ to $R_4$:
Notice the variety: finite lists you can write out completely, relations built from functions, a geometric relation, an inequality, and divisibility. They behave very differently, and three properties sort them out.
Here are some properties that a relation $R$ on $S$ may satisfy. First: is every element related to itself?
$R$ is reflexive $\iff \forall x \in S, (x, x) \in R$.
Second: do relationships always go both ways?
$R$ is symmetric $\iff \forall x, y \in S$, if $(x, y) \in R$ then $(y, x) \in R$.
Third: do relationships chain together?
$R$ is transitive $\iff \forall x, y, z \in S$, if $(x, y) \in R$ and $(y, z) \in R$ then $(x, z) \in R$.
These are exactly the three things any reasonable notion of "is the same as" should satisfy: everything is the same as itself, sameness goes both ways, and two things that are the same as a third are the same as each other. So the relations with all three get a name.
If $R$ is reflexive, symmetric, and transitive, then we say that it is an equivalence relation.
On the grid, reflexive means the whole diagonal is filled, and symmetric means the grid matches its own mirror image across the diagonal. Transitive is harder to spot by eye, which is why the grid below hunts for broken chains for you.
Tap a cell to add or remove the pair $(x, y)$. The panel checks all three properties live. Load the examples' $R_1$ to $R_4$, or try the missions.
There's a second picture of the same thing: draw an arrow from $x$ to $y$ for every pair. Then the diagonal turns into loops, and mirror cells turn into arrows that go both ways.
Tap a grid cell, or tap a dot and then the dot its arrow points to.
Here are the examples from before, checked one property at a time. First, the four small ones.
Relation (1) $S = \{1, 2, 3\}$. Which of $R_1, R_2, R_3, R_4$ are equivalence relations?
$R_3$ is the sneaky one. It does everything right except for the element $2$, which isn't related to anything at all, not even itself.
Symmetric and transitive are "if... then" properties, so they're automatically satisfied when the "if" never happens. That's why $R_2$ passes transitivity without any interesting chains: the only chains are things like $(1,1), (1,1)$. Reflexive is different. It's a "for all" with no "if," so it demands that every single element show up on the diagonal. Forgetting one element (like $2$ in $R_3$) breaks it.
When a relation is missing a property, you can usually repair it by adding pairs. The smallest repair is always the same set of pairs, and finding it is a good test of whether you really see each property.
The two examples built from functions behave very differently from each other.
Relation (2) $f\colon X \to X$, $R = \{(x, f(x)) : x \in X\}$. Relation (3) $f\colon X \to Y$, $R = \{(x, x') : f(x) = f(x')\}$ (the fibers of $f$). Are they equivalence relations?
(2) $R$ is reflexive exactly when $f(x) = x$ for every $x \in X$, and then $R = \{(x, x) : x \in X\}$ is "equals," an equivalence relation. Otherwise it may or may not be symmetric, and may or may not be transitive. On $X = \{1, 2, 3\}$:
(3) (equivalence relation)
Relation (3) is worth remembering as a template: "same output under $f$" is always an equivalence relation, because "$=$" is one. Relation (4) works for the same kind of reason. Every triangle is similar to itself, similarity goes both ways, and two triangles similar to a third are similar to each other, so it's an equivalence relation. The last two are about numbers.
Relation (5) $S = \mathbb{R}, xRy \iff x \le y$. Relation (6) $n \in \mathbb{N}$, $a \sim b \iff n \mid (a - b)$. Are they equivalence relations?
(5) (not an equivalence relation)
(6) (equivalence relation)
Relation (6) is important enough to get its own notation.
$\equiv$ has three lines, but it's weaker than $=$: $7 \equiv 2 \pmod 5$, and $7 \neq 2$. More lines, less equal.
Notation: For $a, b \in \mathbb{Z}$, $$a \equiv b \pmod n \iff n \mid (a - b).$$ ($a$ equals $b$ modulo $n$.)
Two to try. The first one looks like it should be an equivalence relation, and isn't.
Define $\sim$ on $\mathbb{R}$ by $x \sim y \iff |x - y| \le 1$. Which of the three properties does $\sim$ have?
Reflexive $\checkmark$: $|x - x| = 0 \le 1$.
Symmetric $\checkmark$: $|y - x| = |x - y|$, so $|x - y| \le 1 \implies |y - x| \le 1$.
Not transitive: $0 \sim 1$ and $1 \sim 2$, but $|0 - 2| = 2 > 1$, so $0 \not\sim 2$.
"Close to" is a classic non-example. Small differences add up, so being close isn't transitive.
Play with the tolerance yourself. However small you make it, the chain still breaks, until the very end.
$x \sim y \iff |x - y| \le \varepsilon$. Drag $a$, $b$, $c$ and the $\varepsilon$ slider.
Define $\sim$ on $\mathbb{Z}$ by $a \sim b \iff a + b$ is even. Prove that $\sim$ is an equivalence relation.
Proof. Reflexive: $a + a = 2a$ is even, so $a \sim a$.
Symmetric: If $a + b$ is even then $b + a = a + b$ is even.
Transitive: Suppose $a + b = 2k$ and $b + c = 2l$. Then $a + c = (a + b) + (b + c) - 2b = 2(k + l - b)$, which is even. $\blacksquare$
(In fact $a + b$ is even exactly when $a - b = (a + b) - 2b$ is even, so this is the same relation as $a \equiv b \pmod 2$ in disguise.)
An equivalence relation sorts a set into groups of elements that are "the same." Each one gets a name.
If $\sim$ is an equivalence relation on $S$ then, $\forall x \in S$, the equivalence class of $x$ is the subset of $S$ defined by $$[x] = \{y \in S : x \sim y\}.$$
In words, $[x]$ is everything that's "the same as" $x$. The brackets aren't the only way to write it.
Other books write the class of x as x̄, or [x]∼ when two relations are in play. On this site the bar is saved for one special case: the classes of integers modulo $n$ later on this page, as on the Modular Arithmetic page.
A class can have lots of names: any element in it can be used to label it.
Every element of the equivalence class $[x]$ is a representative for the class.
Three facts make equivalence classes behave well. Each one uses exactly the properties you'd expect.
Fact 2. Proof. Suppose $y \in [x]$, so $x \sim y$, and by symmetry $y \sim x$. If $z \in [x]$, then $x \sim z$, and since $y \sim x$ and $x \sim z$, transitivity gives $y \sim z$, so $z \in [y]$. Therefore $[x] \subseteq [y]$.
Since $y \sim x$, we have $x \in [y]$, so reversing the roles of $x$ and $y$ in the argument above gives $[y] \subseteq [x]$.
Conclusion: $[x] = [y]$. $\blacksquare$
Fact 3. Proof. If $y \in [x_1] \cap [x_2]$, then, by Fact 2, $[y] = [x_1]$ and $[y] = [x_2]$, so $[x_1] = [x_2]$. $\blacksquare$
Fact 2 is the reason "any element can be the representative" is safe: whichever element of the class you pick, you get the same class. Fact 3 says two classes either don't overlap at all or are exactly the same.
Now find the classes for the equivalence relations we've met, starting with the two extremes.
Relation (1) $S = \{1, 2, 3\}$. Find the equivalence classes of $R_2 = \{(1, 1), (2, 2), (3, 3)\}$ and of $R_4 = S \times S$.
$R_2$: $[1] = \{1\}, [2] = \{2\}, [3] = \{3\}$.
$R_4$: $\forall x \in S, [x] = \{y \in S : (x, y) \in R_4\} = S$ (only one equivalence class).
$R_2$ is "equal to," which splits everything up as finely as possible. $R_4$ is "everything is related to everything," which lumps it all together. Every other equivalence relation lands somewhere in between. The fibers of a function give a nice middle case.
$f^{-1}(\{y\})$ below does not use the inverse function from the Functions page. It's the set of everything that $f$ sends to $y$, and it makes sense for any $f$, bijective or not.
Relation (3) $f\colon X \to Y, R = \{(x, x') : f(x) = f(x')\}$ (equivalence relation). Describe its equivalence classes.
$\forall y \in f(X), \exists x \in X$ such that $f(x) = y$. Write $f^{-1}(\{y\}) = \{x' \in X : f(x') = y\}$, the preimage of $\{y\}$, or the fiber over $y$. (Note: $f$ may not be bijective.)
Then $f^{-1}(\{y\}) = [x]$, since $x' \in f^{-1}(\{y\}) \iff f(x') = y = f(x) \iff x \sim x'$. So the equivalence classes are exactly the fibers. Then:
One warning about how the fiber gets written in other places.
Many books shorten f−1({y}) to f−1(y). It's handy, but it looks exactly like the inverse function applied to $y$, which only exists when $f$ is a bijection. On this site, $f^{-1}(y)$ always means the inverse function, and the fiber keeps its braces.
Change a function's arrows and watch its classes regroup. Inputs with the same color share an output, so they share a class.
Drag the head of any arrow to a different output.
Relation (4) has classes too, and they're easy to picture: the class of a triangle $T$ is every triangle with the same three angles, whatever its size, position, or turn.
And the most important example of all: divisibility by $n$. Its classes have their own name.
The equivalence classes of $\equiv \pmod n$ on $\mathbb{Z}$ are called the residue classes modulo $n$.
There are exactly $n$ of them, one for each possible remainder. For these classes we write a bar instead of brackets: $\overline{r}$ means $[r]$ for the relation $\equiv \pmod n$.
Relation (6) $n \in \mathbb{N}, a \sim b \iff n \mid (a - b)$ (equivalence relation) ($a \equiv b \pmod n$). Find the equivalence classes.
Equivalence classes (residue classes modulo $n$):
$$\begin{align*} \overline{0} &= \{\dots, -2n, -n, 0, n, 2n, \dots\} \\ \overline{1} &= \{\dots, -2n+1, -n+1, 1, n+1, 2n+1, \dots\} \\ \overline{2} &= \{\dots, -2n+2, -n+2, 2, n+2, 2n+2, \dots\} \\ &\vdots \\ \overline{n-1} &= \{\dots, -n-1, -1, n-1, 2n-1, 3n-1, \dots\} \end{align*}$$
$\mathbb{Z} = \bigcup_{r=0}^{n-1} \overline{r}$. Proof: By the division algorithm, $\forall b \in \mathbb{Z}, \exists q, r \in \mathbb{Z}$ such that $b = qn + r$, $0 \le r \le n-1$. Then $b - r = qn$, so $b \equiv r \pmod n$ and $b \in \overline{r}$.
The residue classes $\overline{0}, \overline{1}, \dots, \overline{n-1}$ are disjoint. Proof: Let $0 \le r \le r' \le n-1$. Suppose that $b \in \mathbb{Z}$, and that $b \in \overline{r} \cap \overline{r'}$. Then, by Fact 3, $\overline{r} = \overline{r'}$. Then $r \in \overline{r'}$, so $n \mid (r' - r)$. But $0 \le r' - r \le n-1$, so $r' = r$.
That first proof runs on the division algorithm from Properties of Integers. Its condition on the remainder (here $0 \le r < n$) is exactly what picks out one representative $r$ from each class.
If you write the integers in rows of length $n$, wrapping around like text on a page, the columns are the residue classes. The widget below turns that sideways so each row is one line of the list above.
Change $n$, then tap any integer. Its whole residue class lights up, along with how the division algorithm put it there.
Another way to see why there are exactly $n$ classes: wind the number line around a circle that is $n$ units around.
Negative integers are where people slip: the class of $-17$ modulo $5$ is not $\overline{2}$. Call a few before you check.
Next, we'll learn to add and multiply residue classes themselves: $\overline{3} + \overline{4} = \overline{2}$ modulo $5$. The $n$ classes, with that arithmetic, form $\mathbb{Z}/n\mathbb{Z}$, one of the most important examples in the whole course.
Both of the last two examples ended the same way: the classes cover everything, and they don't overlap. That shape has a name.
Let $S$ be a set and, for every $i \in I$ (an indexing set), let $A_i \subseteq S$. We say that $\{A_i\}_{i \in I}$ is a partition of $S$ if:
In words: chop $S$ into non-empty pieces, with every element in exactly one piece. Each of the three conditions can fail on its own.
Let $S = \{1, 2, 3, 4, 5, 6\}$. Which of these are partitions of $S$? (a) $\{\{1, 2\}, \{3, 4, 5\}, \{6\}\}$ (b) $\{\{1, 2, 3\}, \{3, 4, 5, 6\}\}$ (c) $\{\{1, 2\}, \{4, 5, 6\}\}$ (d) $\{\{1, 2, 3, 4, 5, 6\}, \emptyset\}$
Break each condition on purpose, one at a time, and then put things right.
Tap a cell to put an element in a part, or take it out.
The big result of this page is that partitions and equivalence relations are the same thing, described two different ways. One direction at a time.
Every partition determines an equivalence relation. Suppose $\{A_i\}_{i \in I}$ is a partition of $S$. Define $\sim$ on $S$ by $$x \sim y \iff \exists i \in I \text{ such that } x, y \in A_i.$$ Then $\sim$ is an equivalence relation.
Notice which property of a partition each check used: ii) for reflexive and iii) for transitive. Now the other direction.
Every equivalence relation determines a partition. Suppose $\sim$ is an equivalence relation on $S$, and let $\{A_i\}_{i \in I}$ be the collection of distinct equivalence classes of $\sim$. Then $\{A_i\}_{i \in I}$ is a partition of $S$.
Therefore, $\{A_i\}_{i \in I}$ is a partition of $S$. $\blacksquare$
So you can hand someone either one, and they can rebuild the other. Here are both directions on the integers.
Which equivalence relation does the partition of $\mathbb{Z}$ into the even integers $E$ and the odd integers $O$ determine? And which partition does $\equiv \pmod 3$ determine?
$\{E, O\}$ is a partition of $\mathbb{Z}$: both parts are non-empty, every integer is even or odd, and none is both. Its relation is $a \sim b \iff a$ and $b$ have the same parity $\iff a - b$ is even $\iff a \equiv b \pmod 2$. Its classes are $[0] = E$ and $[1] = O$.
Going the other way, $\equiv \pmod 3$ determines the partition $\{\overline{0}, \overline{1}, \overline{2}\}$: the multiples of $3$, the integers one more than a multiple of $3$, and the integers two more.
Sort some elements into bins and watch the relation build itself. Turn on SORT GRID to see each bin become a solid square on the diagonal.
Drag each element of $S = \{1, 2, 3, 4, 5, 6\}$ into a bin. The grid shows the relation "is in the same bin as."
Since partitions and equivalence relations match up one to one, counting one counts the other. A four-element set has exactly fifteen of each.
When we meet subgroups, the cosets of a subgroup $H$ will be the equivalence classes of a relation on a group $G$, so they partition $G$. Lagrange's theorem is what you get by counting that partition.
Go from a partition to its relation by hand once.
Let $S = \{1, 2, 3, 4, 5, 6\}$ with the partition $\{\{1, 4\}, \{2\}, \{3, 5, 6\}\}$. List the pairs in the equivalence relation it determines. How many are there? Can you count them without listing them?
$\{(1,1), (1,4), (4,1), (4,4),\ (2,2),\ (3,3), (3,5), (3,6), (5,3), (5,5), (5,6), (6,3), (6,5), (6,6)\}$
There are $14$ pairs. A part with $k$ elements contributes every ordered pair from that part, which is $k^2$ pairs, so the count is $2^2 + 1^2 + 3^2 = 4 + 1 + 9 = 14$.
Every question below makes a new version each time you press the button, in the same order as the lesson. Every wrong choice is a real mistake, and choosing one tells you which.
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
$R_3$ was symmetric and transitive but not reflexive. Here's a "proof" that this can't happen. Your job is to find out what's wrong with it.
"Claim." Every symmetric, transitive relation $R$ on a set $S$ is reflexive.
"Proof." Let $x \in S$, and choose $y$ with $(x, y) \in R$. By symmetry, $(y, x) \in R$. By transitivity, $(x, y), (y, x) \in R \implies (x, x) \in R$. So $R$ is reflexive. $\blacksquare$
(a) Find the mistake. (b) Add one hypothesis to the claim to make it true, and prove the corrected version.
(a) "Choose $y$ with $(x, y) \in R$" assumes such a $y$ exists. Nothing in "symmetric" or "transitive" promises that: both are "if... then" statements, and they say nothing about an element that isn't related to anything. That's exactly $2$ in $R_3$: no pair in $R_3$ involves $2$, so there's no $y$ to choose.
(b) Claim. If $R$ is symmetric and transitive, and $\forall x \in S, \exists y \in S$ such that $(x, y) \in R$, then $R$ is reflexive.
Proof. Let $x \in S$. By the new hypothesis, there is some $y \in S$ with $(x, y) \in R$. By symmetry, $(y, x) \in R$. By transitivity applied to $(x, y)$ and $(y, x)$, $(x, x) \in R$. Since $x$ was arbitrary, $R$ is reflexive. $\blacksquare$