2.5  Equivalence Relations and Partitions

Section 2.4 sorted relations by four properties: reflexive, symmetric, antisymmetric and transitive (Definition 2.4.1). This section studies the relations that have the first, second and fourth. They are the relations that say two things are “the same” in some respect, and each of them cuts its set into disjoint pieces of mutually “same” elements. We prove that the pieces always form a partition, and that every partition arises from exactly one such relation. Then we build the integers modulo $n$, and meet the check that every definition on pieces needs: that it does not depend on which element names the piece. Section 1.4 promised that check for functions defined on classes; here it is.

2.5.1. Arithmetic on a clock

On a twelve-hour clock, five hours after nine o’clock it is two o’clock. People say “$9+5=2$ on a clock”, and nobody is confused. Read as a statement about integers, it is false: $9+5=14$. So what is it a statement about?

The clock does not distinguish $2$ from $14$, or from $26$ or $-10$: all of them put the hand in the same place. Two integers name the same hour when they differ by a multiple of $12$. The sentence “$9+5=2$” is then about hours, and an hour is not one integer but a whole collection of them, $\{\dots ,-10,2,14,26,\dots \}$. The addition adds collections: take any integer from the first, any from the second, add them, and see which collection the sum lands in.

Two things have to be checked before this is mathematics. First, “differ by a multiple of $12$” must behave like “is the same as”: it must cut the integers into separate collections, and no integer may land in two of them. Second, the answer must not depend on the choice: if we take $21$ for “nine” and $-7$ for “five”, the sum $14$ must still name two o’clock. It does, since $21+(-7)=14$. The first check is the theory of equivalence relations and partitions. The second is called well-definedness, and it comes at the end of the section.

2.5.2. Equivalence relations

Equality has three properties that every argument with “$=$” uses silently: $x=x$; if $x=y$, then $y=x$; and if $x=y$ and $y=z$, then $x=z$ (Logic and Proof, Proposition 5.7.1). They are exactly what lets us replace a thing by an equal thing, as often as we like, in either direction. “Same hour on the clock”, “same remainder on division by $3$” and “same absolute value” all have the same three properties, although none of them is equality. They deserve a common name.

An equivalence relation declares things the same in a way that behaves like equality.

In words: (Eq1) says everything is the same as itself. (Eq2) says “the same” has no direction: if $x$ counts as the same as $y$, then $y$ counts as the same as $x$. (Eq3) says sameness passes along a chain: two things that are each the same as a third are linked through it. In symbols, (Eq1)–(Eq3) are $$\mathrm{\forall }x\in Xx\sim x,\mathrm{\forall }x,y\in X(x\sim y\to y\sim x),$$ $$\mathrm{\forall }x,y,z\in X((x\sim y\wedge y\sim z)\to x\sim z).$$ The symbol $\sim$ is a letter for a relation, like $R$ in Section 2.4; it is written between its arguments because it is read like $=$. Nothing needs checking for well-definedness: the definition names a property of a set of pairs.

Part (d) is the degenerate case, and it is worth keeping: it says that the definition makes no demand on an empty set, so the theorems below hold for $X=\mathrm{\varnothing }$ without a separate case. On a non-empty set the empty relation is not an equivalence relation: (Eq1) fails at any element $x$, since $(x,x)\notin \mathrm{\varnothing }$. The same set of pairs passes on one set and fails on another, because (Eq1) speaks about every element of $X$.

Part (c) is an instance of a pattern that returns later in this section, with the fibers of a function: “$x\sim y$ when some quantity attached to $x$ equals the same quantity attached to $y$”. Any such relation inherits (Eq1)–(Eq3) from equality.

A non-example by minimal change. On $\mathbb{R}$, let $x\sim y$ mean $x-y\in \mathbb{Z}$, and let $xRy$ mean $x-y\in \mathbb{N}$. The first is an equivalence relation, as an example later in this section checks. The second changes one letter. It is still reflexive, since $x-x=0\in \mathbb{N}$ by (( )0), and still transitive: if $x-y\in \mathbb{N}$ and $y-z\in \mathbb{N}$, then $x-z=(x-y)+(y-z)\in \mathbb{N}$ by Lemma 2.1.1 (b). But it is not symmetric: $1R0$, since $1-0=1\in \mathbb{N}$, while $0-1=-1$, and $-1\notin \mathbb{N}$ because every natural number is $\ge 0$ (Lemma 2.1.1 (a)). The clause that fails is (Eq2). The relation $R$ is the order $y\le x$ restricted to pairs at integer distance; it has a direction, and sameness has none.

Why these three clauses. Each clause has a job, and each failure has a witness.

• Drop (Eq1), and an element may be the same as nothing at all. On $\{1\}$, the empty relation is symmetric and transitive (Section 2.4’s warning), and $1$ is related to nothing; it would sit in no piece of the cutting.
• Drop (Eq2), and the pieces overlap. The relation $\le$ on $\{1,2\}$ is reflexive and transitive; the set of elements below $2$ is $\{1,2\}$, the set below $1$ is $\{1\}$, and the two share $1$ without being equal.
• Drop (Eq3), and sameness leaks. “$|x-y|\le 1$” on $\mathbb{R}$ is reflexive and symmetric, and $0$ is related to $1$, $1$ to $2$, $2$ to $3$, and so on, while $0$ is not related to $2$. Every integer is linked to every other through a chain of steps of length $1$, though few are related directly.

The name comes from “equal value”: equivalent elements are equal in whatever respect the relation measures.

The payoff is the object the clock was after: the collection of everything that counts as the same as a given element.

2.5.3. Equivalence classes

An equivalence class is everything that counts as the same as one element.

The class is a subset of $X$, by specification (Definition 1.1.3). Its definition fixes the order of the letters as $x\sim a$; by (Eq2) the order does not matter, and $x\in [a]$ holds exactly when $a\sim x$.

For the four relations of Example (Four equivalence relations): under equality, $[a]=\{a\}$; under $X\times X$, $[a]=X$ for every $a\in X$; under “same absolute value”, $[3]=\{-3,3\}$ and $[0]=\{0\}$; and on the empty set there are no elements and so no classes.

The quick check shows the features the theorem below proves in general: every class is non-empty, no number is in two classes, and every number is in one. A family of subsets with these three features has a name.

Here $\bigcup \mathcal{P}$ is the union of the set of sets $\mathcal{P}$ (Definition 1.2.4): the set of points lying in some block. Since every block is a subset of $X$, the union is always a subset of $X$, and (P3) says that every $x\in X$ lies in some block. With (P2), it lies in exactly one: if $x\in P$ and $x\in Q$, then $P\cap Q\ne \mathrm{\varnothing }$, so $P=Q$.

Examples: $\{\{1,2\},\{3\}\}$ is a partition of $\{1,2,3\}$. For a non-empty $X$, $\{X\}$ is a partition with one block, and $\{\{x\}:x\in X\}$ is one with a block for each point. The even and the odd integers form a partition of $\mathbb{Z}$ with two blocks, because every integer is even or odd and not both (Theorem 2.2.3 with $n=2$). For $X=\mathrm{\varnothing }$, the empty set of blocks $\mathcal{P}=\mathrm{\varnothing }$ is a partition: (P1) and (P2) are vacuous, and $\bigcup \mathrm{\varnothing }=\mathrm{\varnothing }$.

Non-examples by minimal change. $\{\{1,2\},\{2,3\}\}$ covers $\{1,2,3\}$ and its sets are non-empty, but $2$ lies in both, so (P2) fails. $\{\{1,2\},\{3\},\mathrm{\varnothing }\}$ satisfies (P2) and (P3), and fails (P1). Without (P1), “the block containing $x$” would still be unique, but a partition could carry useless empty blocks, and the correspondence with equivalence relations below would break, since no class is empty.

A partition is a set of subsets of $X$. So is the set of all classes of an equivalence relation, and it gets its own name.

The quotient set is a set by specification inside $\mathcal{P}\left(X\right)$ (Definition 1.1.3, Definition 1.2.2), and it is often written $\{[a]:a\in X\}$. The quotient map is a function by Definition 1.4.1: each $a\in X$ has the value $[a]$, which lies in $X/\sim$, and only that value. It is surjective: an element of $X/\sim$ is $[a]$ for some $a\in X$, and then it is $q(a)$ (Definition 1.4.4). The quotient map forgets everything about $a$ except which class it lies in, and that is the point of it. Read “$X/\sim$” as “$X$ with equivalent elements identified”.

2.5.4. The classes form a partition

Here is the theorem the clock needs. It also says exactly when two names give the same class.

Part (b) is the rule we will use most. It turns a statement about classes, $[a]=[b]$, into a statement about elements, $a\sim b$, and back. On the clock: $[14]=[2]$ because $14-2=12$ is a multiple of $12$. By (b), the quotient map $q$ of Definition 2.5.4 has $q(a)=q(b)$ exactly when $a\sim b$. So $q$ is injective only when every class has a single element: two different elements $x,y$ of one class $[c]$ have $[x]=[c]=[y]$ by (b), so $q(x)=q(y)$. Part (c) says that two classes are either equal or disjoint; there is no third possibility. That is what the relations of “Why these three clauses” lacked: for $\le$, the sets $[2]=\{1,2\}$ and $[1]=\{1\}$ given by the formula of Definition 2.5.2 overlap and differ, and with $a=2$, $b=1$, $c=1$ the line of (c) that fails is the one that uses (Eq2) (Exercise A1(c)).

2.5.5. Every partition comes from one equivalence relation

The theorem turns an equivalence relation into a partition. The reverse is just as natural: given the blocks, call two points “the same” when they lie in a common block.

So the two passages undo each other. Going from $\sim$ to $X/\sim$ and back gives $\sim$ again, by (b); going from $\mathcal{P}$ to ${\sim }_{\mathcal{P}}$ and back gives $\mathcal{P}$ again, by (a). An equivalence relation and a partition are two descriptions of one structure: the relation says which pairs are the same, and the partition lists the piles. This is the move classes from a relation, a relation from classes, and we choose whichever description makes the next step easier.

The transitivity step in (a) is where (P2) does its real work (the classes part uses it again, the same way), and it is the step that a hasty proof skips. If the blocks were allowed to overlap, as in the cover $\{\{1,2\},\{2,3\}\}$ of $\{1,2,3\}$, then “lie in a common set” would relate $1$ to $2$ and $2$ to $3$ but not $1$ to $3$.

2.5.6. Congruence modulo n

Back to the clock, with any number of hours. The divisibility notation $d\mid m$, “there is $k\in \mathbb{Z}$ with $m=kd$”, is Definition 2.2.1.

So $14\equiv 2(\mathrm{mod}12)$, since $14-2=1\cdot 12$; $-10\equiv 2(\mathrm{mod}12)$, since $-10-2=(-1)\cdot 12$; and $7\not\equiv 2(\mathrm{mod}12)$, since $5$ is not a multiple of $12$ (the multiples $12k$ are $0$ for $k=0$, at least $12$ for $k\ge 1$ and at most $-12$ for $k\le -1$, by discreteness, Proposition 2.1.2 (c)). The symbol $\equiv$ here always carries its modulus, so it does not clash with the semantic equivalence $\phi \equiv \psi$ of Logic and Proof, Chapter 4.

The quotient set is written $\mathbb{Z}/n$, “the integers modulo $n$”. Its elements are the residue classes $[a]=\{x\in \mathbb{Z}:x\equiv a(\mathrm{mod}n)\}=\{a+kn:k\in \mathbb{Z}\}$; the second form holds because $x\equiv a$ means $x-a=kn$, that is, $x=a+kn$. When two moduli are in play we write $[a{]}_n$ for the class of $a$ in $\mathbb{Z}/n$. For example, $[2{]}_{12}=\{\dots ,-22,-10,2,14,26,\dots \}$, the integers that name two o’clock.

How many classes are there? The clock has twelve positions, and the division algorithm says why: each integer has exactly one remainder among $0,1,\dots ,11$.

Here $n-1\in \mathbb{N}$ by Lemma 2.1.1 (c), since $n\ne 0$, so $\{0,\dots ,n-1\}$ is the set of Section 2.1.

So $\mathbb{Z}/12$ has exactly the twelve classes $[0],\dots ,[11]$, one for each position of the hand. (The clock face writes $12$ where we write $[0]$, and $[12]=[0]$.) The uniqueness also gives a test that is often quicker than the definition: $a\equiv b(\mathrm{mod}n)$ if and only if $a$ and $b$ leave the same remainder on division by $n$. Indeed, if $a\equiv b$, then $[a]=[b]$, and the one $r$ with $[a]=[r]$ is also the one with $[b]=[r]$; conversely, if both leave the remainder $r$, then $[a]=[r]=[b]$. With $n=2$, the two classes of $\mathbb{Z}/2$ are the even integers $[0]$ and the odd integers $[1]$: the partition of $\mathbb{Z}$ into evens and odds is the quotient set of congruence modulo $2$.

2.5.7. Two more sources of equivalence relations

Congruence is one way to manufacture an equivalence relation. Here is the most general way, and a second example on the real line that later chapters return to.

Two instances. For $f(x)=\left|x\right|$ on $\mathbb{R}$, ${\sim }_f$ is “same absolute value”, and the fiber over $3$ is the class $\{-3,3\}$. For the map $\mathbb{Z}\to \{0,1,2\}$ sending each integer to its remainder on division by $3$ (a function by the uniqueness in Theorem 2.2.3), ${\sim }_f$ is congruence modulo $3$, by the remainder test above. The example says that “the same in some respect” always means “equal value of some function”: an equivalence relation is the same thing as a function, up to the names of its values.

Picture each class as one point of a circle of circumference $1$: the real line is wound around it, and two numbers land on the same point when they differ by an integer. Each class has exactly one representative in $[0,1)$: the class of $\sqrt{2}$ meets $[0,1)$ in $\sqrt{2}-1$, for instance. Proving this for every class needs the integer part of a real number, which Analysis on the Real Line, Chapter 1 constructs; we do not use it here. With $\mathbb{Q}$ in place of $\mathbb{Z}$, the relation “$x-y\in \mathbb{Q}$” is again an equivalence relation on $\mathbb{R}$, and choosing one point from each of its classes is how Measure and Integration, Chapter 1 builds a set of real numbers that has no length.

2.5.8. Operations on classes

Now the second check of the clock. To add hours we want to define $$[a]+[b]:=[a+b]\text{in }\mathbb{Z}/n.$$ The right-hand side is computed from the representatives $a$ and $b$. If another pair of representatives of the same two classes gave a different class, the “definition” would assign two answers to one input, and Definition 1.4.1 forbids that: a function gives each input exactly one value. So the definition is legitimate only if the answer does not depend on the representatives. That property is called well-definedness, and it was met in Section 1.4, where “write a rational number as $p/q$, then send it to its numerator $p$” failed to be a function (Example (Relations that are not functions)).

In the language of Definition 1.4.1: the addition of $\mathbb{Z}/n$ is the function $\mathbb{Z}/n\times \mathbb{Z}/n\to \mathbb{Z}/n$ whose graph is the set of all pairs $(([a],[b]),[a+b])$ with $a,b\in \mathbb{Z}$. Clause (Fn1) holds because every element of $\mathbb{Z}/n$ is a class $[a]$; clause (Fn2) is the proposition. The clock sentence of the opening is now a true statement: in $\mathbb{Z}/12$, $$[9]+[5]=[14]=[2],$$ the first equality by the definition of $+$, the second because $14-2=12$. And $[21]+[-7]=[14]=[2]$ as well, as the proposition guarantees.

Well-definedness can fail, and the next example shows a failure next to a success, with the minimal change between them.

The general lesson: a rule “$[a]\mapsto$ something computed from $a$” defines a function on the classes exactly when equivalent representatives give the same output. The check always has the same shape: take $a\sim a^{\prime }$, and show that the outputs agree.

2.5.9. Exercises

A. Check your understanding

B. Practice