8.4 Equivalence Relations

We can bring these properties together to define a particular type of relation.

Definition 8.30 (Equivalence Relation).

Let $X$ be a set. Let $\sim$ be a relation on $X$ . If $\sim$ is reflexive, symmetric and transitive, then we call $\sim$ an equivalence relation.

Equivalence relations are important as they give us a notion of ’equivalence’ or ’sameness’ between mathematical objects.

We’ve already seen in Example 8.23 that $=$ on $\mathbb{R}$ is an equivalence relation. Let us look at some other examples.

Theorem 8.31.

Let $m\in\mathbb{N}$ . Congruence modulo $m$ on the set $\mathbb{Z}$ is an equivalence relation.

Proof.

To show that congruence modulo $m$ is an equivalence relation, we need to show it is reflexive, symmetric and transitive.

First we show that $a=b\mod m$ is reflexive. Take any integer $x\in\mathbb{Z}$ , and observe that $m|0$ , so $m|(x-x)$ for any $m$ . By definition of congruence modulo $m$ , we have $x=x\mod m$ . This shows $x=x\mod m$ for every $x\in\mathbb{Z}$ , so $a=b\mod m$ is reflexive.

Next, we will show that $a=b\mod m$ is symmetric. For this, we must show that for all $x,y\in\mathbb{Z}$ , the condition $x=y\mod m$ implies that $y=x\mod m$ . We use a direct proof. Suppose $x=y\mod m$ . Thus $m|(x-y)$ by definition of congruence modulo $m$ . Then $x-y=ma$ for some $a\in\mathbb{Z}$ by definition of divisibility. Multiplying both sides by $-1$ gives $y-x=m(-a)$ . Therefore $m|(y-x)$ , and this means $y=x\mod m$ . We’ve shown that $x=y\mod m$ implies that $y=x\mod m$ , and this means $a=b\mod m$ is symmetric.

Finally we will show that $a=b\mod m$ is transitive. For this we must show that if $x=y\mod m$ and $y=z\mod m$ , then $x=z\mod m$ . Again, we use direct proof. Suppose $x=y\mod m$ and $y=z\mod m$ . This means $m|(x-y)$ and $m|(y-z)$ . Therefore there are integers $a$ and $b$ for which $x-y=ma$ and $y-z=mb$ . Therefore, we obtain $(x-y)+(y-z)=x-z=ma+mb$ . Consequently, $x-z=m(a+b)$ with $a+b\in\mathbb{Z}$ , and so $m|(x-z)$ . Hence $x=z\mod m$ . This completes the proof that congruence modulo $m$ is transitive.

We have shown that congruence modulo $m$ is reflexive, symmetric and transitive, and hence an equivalence relation.

We can also look at equivalence relations between functions:

Theorem 8.32.

Let $X$ be the set of all sets and $\sim$ be a relation on $X$ such that $A\sim B$ if there exists a bijective function $f:A\to B$ where $A,B\in X$ . Then $\sim$ is an equivalence relation.

Proof.

Recall that a bijective function is both surjective and injective.

•

To show $\sim$ is reflexive, consider the identity function $id_{A}:A\to A$ where $id_{A}(a)=a$ for all $a\in A$ . This is a bijective function. Indeed, $id_{A}(a)=id_{A}(b)$ implies $a=b$ for all $a,b\in A$ immediately from the definition of $id_{A}$ so this function is injective. It is also surjective since $y=id_{A}(y)$ for all $y\in A$ .
•

For $\sim$ to be symmetric, recall that bijective functions are invertible. Therefore, if $A\sim B$ , then there exists a bijection $f:A\to B$ . As this is a bijection, there exists $f^{-1}:B\to A$ which is also a bijection meaning $B\sim A$ so $\sim$ is symmetric.
•

For transitivity, recall that the composition of bijective functions is a bijection by Proposition 6.47 so if $A\sim B$ and $B\sim C$ , then there exist bijections $f:A\to B$ and $g:B\to C$ . Consider $g\circ f:A\to C$ . As both $f$ and $g$ are bijections, then $g\circ f$ is also a bijection so $A\sim C$ .

We have shown that $\sim$ is reflexive, symmetric and transitive meaning it is an equivalence relation.

8.4.1 Cyclic Relations

Definition 8.33.

Let $\sim$ be a relation on a set $X$ . We call $\sim$ cyclic if, for every $a,b,c\in X$ such that $a\sim b$ and $b\sim c$ , we have $c\sim a$ .

Notice that this differs from the definition of a transitive relation since the conclusion is $c\sim a$ instead of $a\sim c$ .

If we know our relation is cyclic, we only need to check that it is also reflexive to confirm that it is an equivalence relation.

Proposition 8.34.

Let $\sim$ be a relation over a set $X$ .

$\sim$ is an equivalence relation if and only if $\sim$ is reflexive and cyclic.

Proof.

Let $\sim$ be a relation over a set $X$ .

We first assume that $\sim$ is an equivalence relation and aim to show that it is reflexive and cyclic.

Since $\sim$ is an equivalence relation, we know that $\sim$ is reflexive, symmetric, and transitive. Consequently, $\sim$ is reflexive, so we just need to show that $\sim$ is cyclic.

To prove that $\sim$ is cyclic, let $a,b,c\in X$ where $a\sim b$ and $b\sim c$ . We need to show that $c\sim a$ . As $a\sim b$ and $b\sim c$ and since $\sim$ is transitive, $a\sim c$ . Then, since $\sim$ is symmetric, we see that $c\sim a$ , which is what we needed to prove.

Hence, if $\sim$ is an equivalence relation, it is reflexive and cyclic.

On the other hand, assuming $\sim$ is reflexive and cyclic, we can prove that $\sim$ is an equivalence relation. We need to show that $\sim$ is reflexive, symmetric, and transitive. Since we already know by assumption that $\sim$ is reflexive, we just need to show that $\sim$ is symmetric and transitive.

First, we prove that $\sim$ is symmetric. To do so, consider any arbitrary $a,b\in X$ where $a\sim b$ holds. Since $\sim$ is reflexive, we know that $a\sim a$ . Therefore, by cyclicity, since $a\sim a$ and $a\sim b$ , we learn that $b\sim a$ meaning $\sim$ is symmetric.

Finally, we prove that $\sim$ is transitive. Let $a,b$ , and $c$ be any elements of $X$ where $a\sim b$ and $b\sim c$ . We need to prove that $a\sim c$ . Since $\sim$ is cyclic, from $a\sim b$ and $b\sim c$ we see that $c\sim a$ . We’ve already proven $\sim$ is symmetric so we also have $a\sim c$ and so $\sim$ is transitive.

Overall, we have shown that $\sim$ is cyclic and reflexive if and only if it is an equivalence relation.

8.4.2 Equivalence Classes

As we’ve already seen, it can be very helpful in a proof to reduce the number of cases that need considering. Equivalence relations are often a very useful way to do this as they can tell us which objects are “the same". Instead of working with each individual object, we can therefore work with sets consisting of the ’same’ object.

Definition 8.35.

Let $\sim$ be an equivalence relation on a set $X$ , and let $x\in X$ . The equivalence class of $x$ is

[x]=\{y\in X:x\sim y\}.

The set of equivalence classes is the set $X/{\sim}=\left\{[x]:x\in X\right\}$ .

Example 8.36.

We are already very familiar with equivalence classes in relation to rational numbers. Consider the set

F=\left\{(p,q):p,q\in\mathbb{Z},q\neq 0\right\}.

Let $\sim$ be the equivalence relation on $F$ such that $(a,b)\sim(c,d)$ if $ad=bc$ . Since $ad=bc\iff\frac{a}{b}=\frac{c}{d}$ as $b,d\neq 0$ , the equivalence class $[(a,b)]$ is the set of all pairs $(c,d)$ whose corresponding fraction $\frac{c}{d}$ is equal to $\frac{a}{b}$ . So, for example,

\left[(1,2)\right]=\left\{(2,4),(3,6),(4,8),\cdots\right\},

since

\frac{1}{2}=\frac{2}{4}=\frac{3}{6}=\frac{4}{8}=\cdots

In particular, this means we can view $\mathbb{Q}$ as the set of all equivalence classes of $F$ , since no fraction is repeated in this set.

We do have to take care with notation here as $[x]$ does not tell us which equivalence relation we are defining equivalence classes with respect to. So we must always make sure that the context in which we are using this notation is clear.

Exercise 8.37.

Prove that $\sim$ in Example 8.36 is an equivalence relation.

Solution (please try for yourself before looking)

Proof.

We first show that $\sim$ is reflexive i.e. $x\sim x$ for every $x\in F$ . So suppose $x\in F$ . Then there exist $a,b\in\mathbb{Z}$ with $b\neq 0$ such that $x=(a,b)$ . Then $ab=ab$ since $a,b\in\mathbb{Z}$ . So $x\sim x$ and thus, $\sim$ is reflexive.

Next we show that $\sim$ is symmetric. So we need to prove that $x\sim y\implies y\sim x$ for every $x,y\in F$ . So suppose $x,y\in F$ such that $x\sim y$ . Then there exist $a,b,c,d\in\mathbb{Z}$ where $b,d\neq 0$ such that $x=(a,b)$ and $y=(c,d)$ . Since $x\sim y$ , we have $(a,b)\sim(c,d)$ and thus $ad=bc$ . This means that $cb=da$ . Therefore $(c,d)\sim(a,b)$ and thus $y\sim x$ , which proves that $\sim$ is symmetric.

Finally, to show that $\sim$ is transitive, we need to prove that $x\sim y$ and $y\sim z$ implies that $x\sim z$ for all $x,y,z\in F$ . So suppose that $x,y,z\in F$ such that $x\sim y$ and $y\sim z$ . Then there exist $a,b,c,d,e,f\in\mathbb{Z}$ where $b,d,f\neq 0$ such that $x=(a,b)$ , $y=(c,d)$ and $z=(e,f)$ . Since $x\sim y$ and $y\sim z$ , we have $(a,b)\sim(c,d)$ and $(c,d)\sim(e,f)$ . This means that $ad=bc$ and $cf=de$ . Thus, $c=\frac{de}{f}$ , since $f\neq 0$ . Hence,

{ad=b\left(\frac{de}{f}\right)\iff adf=bde\iff af=be,}

since $d\neq 0$ . Thus, $(a,b)\sim(e,f)$ which means that $x\sim z$ . Hence, $\sim$ is transitive.

Having shown that $\sim$ is reflexive, symmetric and transitive, we’ve therefore shown $\sim$ is an equivalence relation on $F$ .

Example 8.38.

We saw in Theorem 8.31 that congruence modulo $m$ is an equivalence relation. The equivalence classes for this relation are:

	$\displaystyle[0]$	$\displaystyle=\{n\in\mathbb{Z}:n=0\mod m\}=\{0,m,2m,\cdots\}$
	$\displaystyle[1]$	$\displaystyle=\{n\in\mathbb{Z}:n=1\mod m\}=\{1,m+1,2m+1,\cdots\}$
	$\displaystyle\vdots$	$\displaystyle\hskip 56.9055pt\vdots$
	$\displaystyle[m-1]$	$\displaystyle=\{n\in\mathbb{Z}:n=m-1\mod m\}=\{m-1,2m-1,3m-1,\cdots\}.$

For congruence modulo $m$ , we can prove that there are finitely many equivalence classes. This is not always the case.

Theorem 8.39.

Let $m\in\mathbb{N}$ . Congruence modulo $m$ on the set $\mathbb{Z}$ has exactly $m$ equivalence classes.

Proof.

We saw in Corollary 8.5 that every integer $k$ is congruent to exactly one of $0,1,\cdots,m-1\mod m$ . Setting $r\in\{0,1,\cdots,m-1\}$ such that $k=r\mod m$ , then $[k]=\{n\in\mathbb{Z}:n=k\mod m\}=\{n\in\mathbb{Z}:n=r\mod m\}=[r].$ This means that we have at most $m$ equivalence classes.

Moreover, for $r_{1},r_{2}\in\{0,1,\cdots,m-1\}$ , Theorem 8.4 says that $r_{1}\equiv r_{2}\mod m$ if and only if $r_{1}=r_{2}$ which means that there are at least $m$ equivalence classes.

Taken together, there are exactly $m$ equivalence classes congruence modulo $m$ on $\mathbb{Z}$ .

We also have examples where there are an infinite number of equivalence classes. This was true for our relation defined on the set $F$ in Example 8.36. Here’s another example.

Example 8.40.

Consider the set $\mathbb{R}\times\mathbb{R}$ with the relation $(a,b)\sim(c,d)$ if and only if $a^{2}+b^{2}=c^{2}+d^{2}$ .

Let us consider the equivalence class of $(a,b)$ . Let $A=a^{2}+b^{2}$ . Then a general point $(x,y)\in\mathbb{R}^{2}$ is related to $(a,b)$ if $x^{2}+y^{2}=A$ . This is the equation of a circle centred at the origin with radius $\sqrt{A}$ so the equivalence classes consist of concentric circles. Note that the equivalence class $[(0,0)]$ is a circle of radius $0$ and consists of a single point $(0.0)$ .

Examples of these equivalence classes are shown in Figure 8.9.

Figure 8.9: Diagram showing the equivalence classes

[(0,0)]

in black,

[(2,0)]

in red,

[(3,4)]

in blue and

[(0,8)]

in orange under the equivalence relation defined in Example 8.40.

Exercise 8.41.

Prove that the relation given in Example 8.40 is an equivalence relation.

Solution (please try for yourself before looking)

Proof.

Consider the set $\mathbb{R}\times\mathbb{R}$ with the relation $(a,b)\sim(c,d)$ if and only if $a^{2}+b^{2}=c^{2}+d^{2}$ . We need to show reflexivity, symmetry and transitivity.

•

To show $\sim$ is reflexive, we note that $a^{2}+b^{2}=a^{2}+b^{2}$ so $(a,b)\sim(a,b)$ .
•

For $\sim$ to be symmetric, we assume $(a,b)\sim(c,d)$ so $a^{2}+b^{2}=c^{2}+d^{2}.$ This is equivalent to $c^{2}+d^{2}=a^{2}+b^{2}$ so $(c,d)\sim(a,b)$ and $\sim$ is symmetric.
•

For transitivity, if $(a,b)\sim(c,d)$ and $(c,d)\sim(e,f)$ , then $a^{2}+b^{2}=c^{2}+d^{2}$ and $c^{2}+d^{2}=e^{2}+f^{2}$ but this means $a^{2}+b^{2}=e^{2}+f^{2}$ and $(a,b)\sim(e,f)$ which gives transitivity.

We have shown that $\sim$ is reflexive, symmetric and transitive meaning it is an equivalence relation.

8.4.3 Equivalence Classes and Partitions

We now consider some properties of equivalence classes.

Theorem 8.42.

Let $X$ be a non-empty set and let $\sim$ be an equivalence relation on the set $X$ . Then, for all $x,y\in X$ :

a)

$x\in[x]$ .
b)

$x\sim y$ if and only if $[x]=[y]$ .
c)

Either $[x]=[y]$ or $[x]\cap[y]=\emptyset$ .

Proof.

a)

Let $x\in X$ . As $\sim$ is an equivalence relation on $X$ , then by reflexivity, we necessarily have that $x\sim x$ . Therefore $x\in[x]$ by Definition 8.35.
b)

We first show that if $x\sim y$ , then $[x]=[y]$ . We are therefore showing that two sets are equal so we need to show that $[x]\subseteq[y]$ and vice versa.

Let $a\in[x]$ . Then $x\sim a$ by Definition 8.35. By assumption $x\sim y$ and, by the transitivity and symmetry of $\sim$ , we therefore have $y\sim a$ so $a\in[y]$ . Therefore $[x]\subseteq[y]$ .

Similarly, if $b\in[y]$ , then $y\sim b$ and, by transitivity with $x\sim y$ , $x\sim b$ so $b\in[x]$ and $[y]\subseteq[x]$ .

We have then shown that if $x\sim y$ , then $[x]=[y]$ . On the other hand, we assume $[x]=[y]$ and show that $x\sim y$ .

By a), we have that $x\in[x]$ so, as $[x]=[y]$ , we have that $x\in[y]$ . By definition, this means $y\sim x$ so by the symmetry of $\sim$ $x\sim y$ .

This completes the proof for b).
c)

Consider the set $[x]\cap[y]$ .

Case 1: $[x]\cap[y]$ is non-empty.

This means there is an element $a\in[x]$ and $a\in[y]$ . As $a\in[x]$ , then $x\sim a$ so, by b), $[x]=[a]$ . Similarly, $[y]=[a]$ . Hence, $[x]=[y]$ .

Case 2: $[x]\cap[y]$ is empty.

As the intersection must be either empty or non-empty, we have covered all possible cases and hence, we must have either $[x]=[y]$ or $[x]\cap[y]=\emptyset$ .

Exercise 8.43.

In b), why did we have to use both transitivity and symmetry when showing $[x]\subseteq[y]$ but only needed transitivity when showing $[y]\subseteq[x]$ ?

Solution (please try for yourself before looking)

Transitivity is sufficient for showing $[y]\subseteq[x]$ because we already know that $x\sim y$ and $y\sim b$ (no swapping of order is necessary), which immediately gives us $x\sim b$ .

This theorem means we can sort the elements of a set $X$ into distinct equivalence classes. Note that all the equivalence classes we found in the previous section are disjoint.

The map $p:X\to X/\sim$ which maps elements to their equivalence classes is often called the canonical projection and will continue to appear in your later studies³³ 3 In particular, your algebra courses. If you are interested, you may want to read about quotient spaces.. By Theorem 8.42, $p(x)$ is a surjective map which can be used to decompose any function into the composition of a surjective and injective function.

Proposition 8.44.

Let $f:A\to B$ be a function and consider the equivalence relation $\sim$ on $A$ where $a\sim b$ if and only if $f(a)=f(b)$ for $a,b\in A$ .

Define the function $i:A/\sim\to B$ where $i([a])=f(a)$ . Then $i$ is injective and $f=i\circ p$ where $p:A\to A/\sim$ is the canonical projection.

Proof.

We first show that the function $i:A/\sim\to B$ where $i([a])=f(a)$ is injective.

Assume $[a],[b]\in A/\sim$ such that $i([a])=i([b])$ . To prove injectivity, we want to show $[a]=[b]$ .

By definition of $i$ , if $i([a])=i([b])$ , then $f(a)=f(b)$ so, by definition of the equivalence relation $\sim$ , we necessarily have $a\sim b$ . However, by Theorem 8.42, this means $[a]=[b]$ . Hence, we have shown $i$ is an injective function.

Finally, we consider $i\circ p:A\to B$ . Then, for $a\in A$ , $(i\circ p)(a)=i([a])=f(a)$ so $i\circ p=f$ and any function can be decomposed into the composition of a surjective and injective function.

Theorem 8.42 is not the first time we’ve seen a set being discomposed into disjoint subsets. Recall from Block 2, Definition 4.9:

Definition 8.45.

Let $\mathcal{P}$ be a (possibly infinite) set of subsets $A_{1},A_{2},\cdots$ of the set $A$ such that

1.

$A=\bigcup_{k=1}^{\infty}A_{k}$ and
2.

$A_{i}\cap A_{j}=\emptyset$ for every $i\neq j$ .

Then we call the collection $\mathcal{P}$ a partition of the set $A$ .

Theorem 8.46.

Let $X$ be a non-empty set. If $\sim$ is an equivalence relation on $X$ , then $X/\sim$ , the set of equivalence classes, is a partition of $X$ .

Proof.

Let $\sim$ be an equivalence relation on the set $X$ with equivalence classes $[x_{1}],[x_{2}],\cdots$ . We need to show that $\cup_{i}[x_{i}]=X$ and the equivalence classes are pairwise disjoint.

We first show that $\cup_{i}[x_{i}]\subseteq X$ . Let $x\in\cup_{i}[x_{i}]$ . Then $x$ is an element of at least one equivalence class. By Definition 8.35, this means $x\in X$ so $\cup_{i}[x_{i}]\subseteq X$ .

Alternatively, let $y\in X$ . By Theorem 8.42 part a), $y\in[y]$ . As $[y]$ is an equivalence class of $X$ , there exists some $[x_{i}]$ such that $[x_{i}]=[y]$ . Therefore, $y\in\cup_{i}[x_{i}]$ and, overall, we have $\cup_{i}[x_{i}]=X$ .

Finally, let $[x_{i}]$ and $[x_{j}]$ be two equivalence classes. Then, by Theorem 8.42 part c), either $[x_{i}]=[x_{j}]$ or $[x_{i}]\cap[x_{j}]=\emptyset$ so the equivalence classes are pairwise disjoint.

Example 8.47.

Consider congruence modulo 2. The equivalence classes here are

	$\displaystyle[0]$	$\displaystyle=\{n\in\mathbb{Z}:n=0\mod 2\}=\{0,2,4,\cdots\}$
	$\displaystyle[1]$	$\displaystyle=\{n\in\mathbb{Z}:n=1\mod 2\}=\{1,3,5,\cdots\}.$

Alternatively, we can say congruences modulo 2 partitions the integers into odd and even numbers.

Sometimes, it’s more useful to start with a partition on a set $X$ and it turns out, we can define a relation on the set $X$ from a partition.

Definition 8.48.

Let $\mathcal{P}$ be a partition on the non-empty set $X$ with sets $A_{1},A_{2},\cdots$ . Let $\sim$ be a relation on $X$ with $x\sim y$ if there exists some $A_{i}\in\mathcal{P}$ such that $x\in A_{i}$ and $y\in A_{i}$ . We call this the relation induced by the partition $\mathcal{P}$ .

Example 8.49.

Consider the set $\{1,2,3,4,5,6\}$ with the partition $\{\{1,4\},\{3\},\{2,5,6\}\}$ , then the corresponding equivalence relation is given by the graph in Figure 8.10.

Figure 8.10: The relation induced by the partition given in Example 8.49.

Looking at the properties of this induced relation, we get the following fundamental theorem.

Theorem 8.50.

Let $X$ be a non-empty set with a partition $\mathcal{P}$ . The relation $\sim$ induced by the partition $\mathcal{P}$ is an equivalence relation.

Proof.

We have to show that the relation $\sim$ induced by a partition $\mathcal{P}$ on a non-empty set $X$ is reflexive, symmetric and transitive.

Reflexivity: Let $x\in X$ . Then, as $\mathcal{P}$ is a partition of $X$ , there exists some (unique) subset $X_{i}\in\mathcal{P}$ such that $x\in X_{i}$ . Therefore $x\sim y$ for all $y\in X_{i}$ by Definition 8.48 but $x\in X_{i}$ so $x\sim x$ as required.
Symmetry: Suppose $x,y\in X$ such that $x\sim y$ . This means there is a set $X_{i}\in\mathcal{P}$ such that $x\in X_{i}$ and $y\in X_{i}$ . However, if both $y\in X_{i}$ and $x\in X_{i}$ , then $y\sim x$ by Definition 8.48.
Transitivity: Let $x,y,z\in X$ such that $x\sim y$ and $y\sim z$ . Therefore there are some sets $X_{i},X_{j}\in\mathcal{P}$ such that $x,y\in X_{i}$ and $y,z\in X_{j}$ .

By definition of a partition, $X_{i}\cap X_{j}$ is empty if $i\neq j$ . However, $y\in X_{i}$ and $y\in X_{j}$ by assumption so we must have $X_{i}=X_{j}$ . But this means $x\in X_{i}$ and $z\in X_{i}$ so $x\sim z$ and $\sim$ is transitive.

Therefore $\sim$ induced by $\mathcal{P}$ is an equivalence relation.

Together, we’ve therefore seen that partitions define equivalence relations and equivalence relations define partitions: there is a bijective correspondence between them. They are therefore really just two different ways of looking at the same thing!

We can now also address the question posed at the beginning of this section: what is equality?

Definition 8.51 (Equality).

Given a non-empty set $X$ , equality on $X$ is the equivalence relation on $X$ whose equivalence classes all contain a single element.