6.2 Equivalence relations

In this section we shall introduce a tool which is very useful in mathematics because it provides a way of reducing a complicated situation to a simpler one.

Thus we have already seen two examples of equivalence relations:

1. (i)

   ‘‘congruence modulo $5$’’ on the set of integers;

2. (ii)

   ‘‘being in the same college’’ on the set of MATH111 students.

Let us take the first of these. Given any $a\in\mathbb{Z}$, we may consider the subset of $\mathbb{Z}$ consisting of numbers which are congruent to $a$ modulo $5$. For example, if $a=2$ we obtain the subset $\{\dots,-8,-3,2,7,12,\dots\}$, while if instead $a=9$ we obtain the subset $\{\dots,-6,-1,4,9,14,\dots\}$. This prompts the following definition.

Thus for the relation of congruence modulo $5$ on the set $\mathbb{Z}$, we have

We note several things about each of these equivalence classes:

1. (i)

   $a$ is an element of the equivalence class of $a$ (e.g., $2\in\widehat{2}$);

2. (ii)

   if $b$ is any element of the equivalence class of $a$, then the equivalence classes of $a$ and $b$ are the same (e.g., $7\in\widehat{2}$, and $\widehat{7}=\{\dots,-8,-3,2,7,12,\dots\}=\widehat{2}$);

3. (iii)

   if $b$ is any element of $S$ not in the equivalence class of $a$, then the equivalence classes of $a$ and $b$ are disjoint (e.g., $9\;\not\in\widehat{2}$, and

   $$\widehat{2}\cap\widehat{9}=\{\dots,-8,-3,2,7,12,\dots\}\cap\{\dots,-6,-1,4,9,14,\dots\}=\emptyset).$$

These also hold for the ‘‘college’’ relation on the set $S$ of MATH111 students, as is easy to see; in fact we shall prove that they are true for equivalence classes in general.

Proof. (i) Since $\sim$ is reflexive, $a\sim a$ and so $a\in\widehat{a}.$

(ii) Suppose that $b\in\widehat{a}$, so that $b\sim a$; as $\sim$ is symmetric, we also have $a\sim b.$

If we take $c\in\widehat{b}$, then $c\sim b$; as $\sim$ is transitive, from $b\sim a$ we deduce $c\sim a$ and so $c\in\widehat{a}$ — thus $\widehat{b}\subseteq\widehat{a}$.

On the other hand if we take $c\in\widehat{a}$, then $c\sim a;$ as $\sim$ is transitive, from $a\sim b$ we deduce $c\sim b$ and so $c\in\widehat{b}$ — thus $\widehat{a}\subseteq\widehat{b}.$ Therefore $\widehat{b}=\widehat{a}$ as required.

(iii) We prove this by contraposition. Suppose that $\widehat{b}\cap\widehat{a}\neq\emptyset$, and take $c\in\widehat{b}\cap\widehat{a}.$ We then have $c\sim b$ and $c\sim a$; from the former we have $b\sim c$ because $\sim$ is symmetric, and then using the latter as well we have $b\sim a$ since $\sim$ is transitive. Hence $b\in\widehat{a}$, and the result is proved. $\Box$

Proof. Let $a\in S$. Then $a\in\widehat{a}$, so $a$ lies in at least one equivalence class. Now suppose that $\widehat{b}$ is any other equivalence class containing $a$. Then $\widehat{b}=\widehat{a}$ by Proposition 6.2.3(ii), and thus $\widehat{a}$ is the unique equivalence class containing $a$. $\Box$

Motivated by the above results, we make the following definition.

We may think of a partition of $S$ as a way of dividing $S$ up into pieces. We have shown that the equivalence classes corresponding to any equivalence relation on $S$ form a partition of $S$; the pieces into which $S$ is divided are the equivalence classes. In fact given any partition of a non-empty set $S$ we may define a relation $\sim$ on $S$ by stipulating that $a\sim b$ if $a$ and $b$ lie in the same subset of $S$ (as in the ‘‘college’’ example, above). An easy check shows that $\sim$ is an equivalence relation, whose equivalence classes are exactly the subsets making up the partition. Thus the concepts of ‘‘equivalence relation’’ and ‘‘partition’’ are very closely linked; each gives rise to the other in a natural way.

Another consequence of our results is that we can make the following definition.

From Proposition 6.2.3(i), we see that $a$ is a representative of $\widehat{a}$; from (ii) and (iii) we see that $b$ is a representative of $\widehat{a}$ if and only if $\widehat{b}=\widehat{a}$.

Thus if we have an equivalence relation on a set $S$, we may consider the set of equivalence classes; often this is ‘‘simpler’’ than $S$ itself, because it has fewer elements (each equivalence class may contain many elements of $S$). We shall see later that sometimes the equivalence classes provide enough detail for the task at hand, allowing us to ignore much that is irrelevant and concentrate on what is essential.

We conclude this section by mentioning two equivalence relations which exist on any non-empty set $S$. The first is the relation defined by $a\sim b$ for all $a,b\in S$, in which any two elements of $S$ are related; here there is a single equivalence class consisting of the whole of $S$. The second is the relation of equality, defined by $a\sim b$ if $a=b$; this time each equivalence class consists of a single element of $S$. These two relations are not very useful, as the first oversimplifies the structure of $S$ to a single class while the second does not simplify $S$ at all; interesting equivalence relations lie between these two extremes.