Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 9.3 Equivalence relations and equivalence classes

An important class of relations are those that are similar to “=”. We know that “is equal to” is reflexive, symmetric and transitive. Any relation that has these properties acts something like equality does — we call these relations equivalence relations.

Definition 9.3.1.

Let \(R\) be a relation on a set \(A\text{.}\) If \(R\) is reflexive, symmetric and transitive then \(R\) is an equivalence relation.
From our work in the previous section we know that the following relations are equivalence relations
  • “is equal to”
  • “has same parity as”
  • “is congruent to”
Notice that these other two relations are weaker than equality — the underlying objects do not have to be the same in order to be equivalent.

Example 9.3.2.

Let \(A\) be the set of students at a particular university. Show that the relation “has the same birthday as” is an equivalence relation.
We need to prove that the relation is reflexive, symmetric and transitive; we prove each in turn.
  • Reflexive — Since any person has the same birthday as themselves, the relation is reflexive.
  • Symmetric — Let \(a\) have the same birthday as \(b\text{.}\) Then \(b\) has the same birthday as \(a\text{.}\) Hence the relation is symmetric.
  • Transitive — Let \(a\) have the same birthday as \(b\) and \(b\) have the same birthday as \(c\text{.}\) Then it follows that \(a\) and \(c\) must be born on the same day of the year. Hence \(a\) has the same birthday as \(c\text{.}\)
Consider now the set \(A = \set{0,1,2,3,\dots,10}\) and consider congruence modulo 4. As we have done a few times, we’ll draw a picture of the relation on this set. Not, there could, potentially be a lot of arrows in this figure. To save some space, we can take advantage of the fact that congruence is reflexive, and so we know that if there is an arrow from \(a\) to \(b\text{,}\) there must be one back from \(b\) to \(a\text{.}\) So, instead of drawing two arrows between \(a\) and \(b\text{,}\) we’ll just draw a single arc.
We can do exactly the same thing, but now with the relation “has the same parity as”
In each case we should notice that the set of nodes in the pictures fall into a small number of subsets, in which each node is connected to every other node. These connected subsets are examples of equivalence classes.

Definition 9.3.3.

Given an equivalence relation \(R\) defined on a set \(A\text{,}\) we define the equivalence class of \(x \in A\) (with respect to \(R\)) to be the set of elements related to \(x\text{:}\)
\begin{align*} [x] &= \set{ y \in A \;:\; y \rel x } \end{align*}
This is sometimes also written as “\(E_x\)”.
So in our “congruent modulo 4” example above, the equivalence classes are
\begin{align*} [0] &= \set{0,4,8} & [1]&= \set{1,5,9} & [2] &= \set{2,6,10} & [3] = \set{3,7}\\ [4] &= \set{0,4,8} & [5]&= \set{1,5,9} & [6] &= \set{2,6,10} & [7] = \set{3,7}\\ [8] &= \set{0,4,8} & [9]&= \set{1,5,9} & [10] &= \set{2,6,10} \end{align*}
while in our “has the same parity as” example we get
\begin{align*} [0] &= \set{0,2,4,6,8,10} & [1]&= \set{1,3,5,7,9}\\ [2] &= \set{0,2,4,6,8,10} & [3]&= \set{1,3,5,7,9}\\ [4] &= \set{0,2,4,6,8,10} & [5]&= \set{1,3,5,7,9}\\ [6] &= \set{0,2,4,6,8,10} & [7]&= \set{1,3,5,7,9}\\ [8] &= \set{0,2,4,6,8,10} & [9]&= \set{1,3,5,7,9}\\ [10] &= \set{0,2,4,6,8,10} \end{align*}
First notice that there are no empty equivalence classes. This follows from the fact that equivalence relations are reflexive:
Let \(x \in A\text{.}\) We know that \(R\) is reflexive, so \(x \rel x\text{.}\) Since we define
\begin{align*} [x] &= \set{a \in A \;:\; a \rel x} \end{align*}
we must have that \(x \in [x]\text{.}\)
Also notice that there is a lot of repetition in our lists of equivalence classes. Indeed, we could have been listed them as:
\begin{align*} [0]=[4]=[8] &= \set{0,4,8} & [1]=[5]=[9] &= \set{1,5,9}\\ [2]=[6]=[10] &= \set{2,6,10} & [3]=[7] = \set{3,7} \end{align*}
In fact it looks exactly like
\begin{gather*} [x]=[y] \iff x \rel y \end{gather*}
This is an important (and true!) result, so let’s call it a theorem and prove it.
We prove each implication in turn.
  • (\(\Leftarrow\)) Assume \([x] = [y]\text{.}\) From our lemma above, we know \(x \in [x]\text{.}\) Hence \(x \in [y]\text{.}\) But we define \([y]= \set{a \in A \;:\; a \rel y}\text{,}\) and since \(x\) is in this set we know that \(x \rel y\) as required.
  • (\(\Rightarrow\)) Assume \(x \rel y\text{.}\) In order to prove that \([x] = [y]\text{,}\) we prove that each is a subset of the other.
    • Let \(a \in [x]\text{,}\) and so \(a \rel x\text{.}\) Now since \(x \rel y\) and \(R\) is transitive, we know that \(a \rel y\text{.}\) Consequently \(a \in [y]\text{,}\) and thus \([x] \subseteq [y]\text{.}\)
    • Now let \(b \in [y]\text{,}\) so \(b \rel y\text{.}\) Since \(R\) is symmetric, we know that \(y \rel x\text{,}\) and because of transitivity, this implies that \(b \rel x\text{.}\) Hence \(b \in [x]\) and so \([y] \subseteq [x]\)
    Thus \([x] = [y]\text{.}\)

Remark 9.3.6. Representing classes — be kind.

This result tells us that given any two related elements \(x \rel y\text{,}\) their equivalence classes are the same. This can help us choose how we might represent an equivalence class to our reader; since \([x]=[y]\text{,}\) we might as well choose to write it using which ever of \(x\) and \(y\) is simpler for the reader. That is, we’ll write the class using its simplest representative.
In the above example we saw that \([0]=[4]=[8]\text{,}\) \([1]=[5]=[9]\) and so forth, so when discussing these classes we should pick to represent them as
\begin{equation*} [0] \qquad [1] \qquad [2] \qquad \text{and} \qquad [3]. \end{equation*}
In general it is a good idea to be kind to your reader (and yourself) by representing your equivalence classes using simple members of those equivalence classes.
We can push the above theorem further to show that any two equivalence classes are disjoint or equal. Equivalence classes cannot overlap “just a little” — it is all or nothing. We’ll call this result a corollary.
Let \(R\) be an equivalence relation on \(A\) and let \(x,y \in A\text{.}\) Now form the set \(B = [x] \cap [y]\text{.}\) Either this set is empty or not.
  • If \(B = \es\) then there is nothing left to prove.
  • On the other hand, if \(B\) is non-empty, then there must be some element \(b \in B\text{.}\) Hence \(b \in [x]\text{,}\) so \(b \rel x\) and by symmetry of \(R\) we know \(x \rel b\text{.}\) Now, since \(b\in [y]\text{,}\) we have \(b \rel y\text{.}\) By transitivity of \(R\text{,}\) \(x \rel y\text{.}\) The previous theorem then ensures that \([x] = [y]\) as required.
Before we go on, let us look at some more examples of equivalence classes.

Example 9.3.8.

Let \(R\) be congruence modulo \(5\) on the set of integers. We know from Theorem Theorem 9.2.6 above, that this is an equivalence relation. Now, using Euclidean division Fact 3.0.3, and dividing by \(5\text{,}\) we see that any integer \(n\) can be written as
\begin{equation*} n=5q+r \qquad \text{ where } r \in \set{0,1,2,3,4} \end{equation*}
Hence \(n-r = 5q\text{.}\) So \(n\) must be congruent to one of \(0,1,2,3,4\) modulo 5. Thus our equivalence classes are exactly
\begin{equation*} [0] \qquad [1] \qquad [2] \qquad [3] \qquad [4]. \end{equation*}

Example 9.3.9.

Let \(S\) be the set of all students at University of British Columbia. We define a relation on \(S\) by
\begin{equation*} a \rel b \qquad \iff \qquad \text{$a$ has the same age as $b$}. \end{equation*}
Now this definition is still a little sloppy around the edges. To make it more precise:
  • \(S\) is the set of all students enrolled on the 1st of October 2019.
  • By “age” we mean the age in years rounded down to the nearest integer.
Show that this defines an equivalence relation and determine the equivalence classes.
Solution.
We’ll first show that this is reflexive, symmetric and transitive and then look at the equivalence classes.
  • Reflexive — Let \(a\) be a student. Then since \(a\) has the same age as \(a\text{,}\) it follows that \(a \rel a\) as required.
  • Symmetric — Let \(a,b\) be students so that \(a\) has the same age as \(b\text{.}\) This means that \(b\) has the same age as \(a\) and hence \(b \rel a\) as required.
  • Transitive — Let \(a,b,c\) be students so that \(a\) has the same age as \(b\) and \(b\) has the same age as \(c\text{.}\) Then \(a\) has the same age as \(c\) and so \(a \rel c\text{.}\) Hence the relation is transitive.
The equivalence classes are just sets of students with the same age (in years rounded to nearest integer). So there will be an equivalence class full of 18 year-olds, another of 19 year-olds, and so on. We should be a little careful, there may 108  be a very small number of 15 year-olds, 16 year-olds and on up to 75 year old students.

Example 9.3.10.

Let \(R\) be a relation defined on \(\mathbb{R}^2\) by
\begin{equation*} (a,b) \rel (c,d) \iff a+d=c+b \end{equation*}
Show that is an equivalence relation and determine its equivalence classes.
Solution.
We first show that it is an equivalence relation and then we’ll look at its equivalence classes.
  • Reflexive — Let \((a,b) \in \mathbb{R}^2\text{,}\) then since \(a+b=a+b\text{,}\) it follows that \((a,b) \rel (a,b)\text{.}\) Hence the relation is reflexive.
  • Symmetric — Let \((a,b), (c,d) \in \mathbb{R}^2\) and assume that \((a,b) \rel (c,d)\text{.}\) This implies that \(a+d=c+b\text{.}\) Since equality is symmetric, we know that \(c+b=a+d\) and so \((c,d) \rel (a,b)\text{.}\)
  • Transitive — Let \((a,b), (c,d), (e,f) \in \mathbb{R}^2\) and assume that
    \begin{equation*} (a,b) \rel (c,d) \qquad \text{ and } \qquad (c,d) \rel (a,b). \end{equation*}
    Hence we know that
    \begin{equation*} a+d=c+b \qquad \text{ and } c+f = e+d. \end{equation*}
    Rearrange the second of these to give \(c = e+d-f\text{.}\) Substitute this into the first to get
    \begin{align*} a+d \amp=c+b \\ \amp=\underbrace{e+d-f}_{=c}+b \amp \text{ and so}\\ a+f\amp=e+b. \end{align*}
    Hence \((a,b)\rel (e,f)\) as required.
So what do the equivalence classes look like? Theorem Theorem 9.3.5 tells us that two elements are in the same equivalence class if and only if they satisfy the relation. So let \((a,b) \in \mathbb{R}^2\) and let us examine its equivalence class. The pair \((x,y) \in [(a,b)]\) if and only if \((a,b) \rel (x,y)\) . That is we must have \(a+y=x+b\)
\begin{equation*} y=x+(b-a). \end{equation*}
Hence the equivalence class of \((a,b)\) is the set of points lying on the line with gradient 1 that passes through \((a,b)\text{.}\)
Our results above tell us that an equivalence relation cuts a set up into non-empty disjoint pieces, such as is depicted below.
Here we have coloured the different equivalence classes and you can think of the dots in the different subsets as being some elements in those equivalence classes. Notice there is no overlap between the subsets, and the entire set is covered by the subsets — no piece is missing. This separation 109  of a set into disjoint pieces is called a set partition.

Definition 9.3.11.

A partition of a set \(A\) is a collection \(\mathcal{P}\) of non-empty subsets of \(A\text{,}\) so that
  • if \(x \in A\) then there exists \(X \in \mathcal{P}\) so that \(x \in X\text{,}\) and
  • if \(X,Y \in \mathcal{P}\text{,}\) then either \(X \cap Y = \es\) or \(X = Y\)
The elements of \(\mathcal{P}\) are then called blocks, parts or pieces of the partition.
An equivalent definition is that a partition of a set \(A\) is a collection \(\mathcal{P}\) of non-empty subsets of \(A\text{,}\) so that
  • \(\ds \bigcup_{X \in \mathcal{P}} X = A\text{,}\) and
  • if \(X,Y \in \mathcal{P}\text{,}\) then either \(X \cap Y = \es\) or \(X = Y\)
Where the union \(\ds \bigcup_{X \in \mathcal{P}} X\) is the union of all the sets in the partition \(\mathcal{P}\text{.}\)
Consider our equivalence class examples above, and notice that in each case the equivalence classes form partitions of the underlying set. Rather than just “notice” let us do one (new) example more explicitly.
Given an equivalence relation we can prove that its equivalence classes form a set partition.
Let \(\mathcal{P} = \set{[x] \so x\in A}\) be the set of equivalence classes.
  • Let \(x \in A\text{.}\) Then by Lemma Lemma 9.3.4 above we know that \(x \in [x]\text{,}\) and by definition \([x] \in \mathcal{P}\text{.}\) Hence for any \(x \in A, x \in X\) for some \(X \in \mathcal{P}\text{.}\)
  • Let \(X,Y \in \mathcal{P}\text{.}\) Then by Corollary Corollary 9.3.7, we know that either \(X=Y\) or \(X \cap Y= \es\text{.}\)
Hence the set of equivalence classes forms a set partition.
So an equivalence relation gives equivalence classes that define a set partition. We can also go backwards. A set partition can be used to define equivalence classes that in turn define an equivalence relation. To be more precise, take a set partition \(\mathcal{P}\) of a set \(A\text{.}\) For any two elements \(x,y \in A\) we can define
\begin{gather*} x \rel y \iff x,y \text{ are elements of the same part of the partition }\mathcal{P} \end{gather*}
It is not too hard to prove that this relation is an equivalence relation.
We need to show that \(R\) is reflexive, symmetric and transitive.
  • Reflexive — Let \(x \in A\text{.}\) Since \(\mathcal{P}\) is a set partition, we know that \(x\) is an element of some piece of the partition. Hence \(x \) is in the same piece of the partition as itself, and so \(x \rel x\) as required.
  • Symmetric — Let \(x \rel y\text{,}\) so we know that \(x, y\) lie in the same piece of the partition. Hence we must also have \(y \rel x\text{.}\)
  • Transitive — Let \(x \rel y\) and \(y \rel z\text{.}\) Then there must be \(X,Y \in \mathcal{P}\) so that \(x,y \in X\) and \(y,z \in Y\text{.}\) Hence \(X \cap Y \neq \es\) (since it contains \(y\)). Since \(\mathcal{P}\) is a partition, we know that \(X \cap Y = \es\) or \(X=Y\text{.}\) Hence \(X=Y\) and so \(x,z \in X\text{.}\) Thus \(x \rel z\) as required.
See here.
Alternatively, we might say that such a partitioning of a set is called a set partition. However that sentence is a bit self-referential. At any rate, the term set partition is another on point naming by mathematicians.
<Prev^TopNext>