Subsection 5.4.2 Equivalence Relations
We look at some properties of relations. In particular, we define the reflexive, symmetric, and transitive properties. We will look at how to prove whether a relation is reflexive, symmetric, and/or transitive. We then use these properties to define equivalence relations.
Definition 5.4.6.
Let \(R\) be a relation on \(A\text{.}\) Then
\(R\) is reflexive if for all \(x\in A\text{,}\) \(x R x\text{.}\) In ordered pair notation, \((x, x)\in R\text{.}\)
\(R\) is symmetric if for all \(x, y\in A\text{,}\) if \(x R y\) then \(y R x\text{.}\) In ordered pair notation, if \((x, y)\in R\) then \((y, x)\in R\text{.}\)
\(R\) is transitive if for all \(x, y, z\in A\text{,}\) if \(x R y\) and \(y R z\) then \(x R z\text{.}\) In ordered pair notation, if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
Example 5.4.7. Reflexive, Symmetric, Transitive.
Let \(A=\{1, 2, 3\}\text{,}\) define the relation on \(A\) by
\begin{equation*}
R=\{(1, 1), (2, 2), (3, 3)\}.
\end{equation*}
\(R\) is reflexive since \((x, x)\in R\) for each \(x\in A\text{.}\)
\(R\) is symmetric since if \((x, y)\in R\) then \((y, x)\in R\text{.}\) Note, this property does not mean \((x, y)\in R\text{,}\) just that if a pair is in \(R\text{,}\) then the reverse is as well.
\(R\) is transitive since if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\) Note, this property can be tedious to check by hand. In this example, though, the only pairs that fit the hypothesis are pairs like \((x, y)=(1, 1), (y, z)=(1, 1)\text{,}\) so \((x, z)=(1, 1)\text{,}\) which is in \(R\text{.}\)
Example 5.4.8. Another Look at the Properties.
Let \(A=\{1, 2, 3\}\text{,}\) define the relation on \(A\) by
\begin{equation*}
R=\{(1, 2), (1, 3), (2, 3)\}.
\end{equation*}
\(R\) is not reflexive since \((1, 1)\notin R\text{.}\)
\(R\) is not symmetric since \((1, 2)\in R\text{,}\) but not \((2, 1)\text{.}\)
\(R\) is transitive since if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
Check: \((x, y)=(1, 2), (y, z)=(2, 3)\text{,}\) so \((x, z)=(1, 3)\text{,}\) which is in \(R\text{.}\) This is the only set of ordered pairs where the second coordinate matches the first.
Activity 5.4.4. Pratice with the Properties on a Finite Relation.
Let \(A=\{1, 2, 3\}\text{.}\) Let \(R=\{(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)\}\text{.}\)
(a)
Determine if \(R\) is reflexive.
(b)
Determine if \(R\) is symmetric.
(c)
Determine if \(R\) is transitive.
Activity 5.4.5. More Practice with a Finite Relation.
Let \(A=\{1, 2, 3, 4\}\text{.}\) Let \(R=\{(1, 1), (1, 3), (2, 2), (3, 2), (3, 3)\}\text{.}\)
(a)
Determine if \(R\) is reflexive.
(b)
Determine if \(R\) is symmetric.
(c)
Determine if \(R\) is transitive.
Checking that a relation is reflexive, symmetric, or transitive on a small finite set can be done by checking that the property holds for all the elements of \(R\text{.}\) But if \(A\) is infinite we need to prove the properties more generally.
Proving Reflexive, Symmetric, and Transitive Properties.
To prove

Reflexive.
Let \(x\in A\text{.}\) Show \((x, x)\in R\text{.}\)

Symmetric.
Assume \((x, y)\in R\text{.}\) Show \((y, x)\in R\text{.}\)

Transitive.
Assume \((x, y), (y, z)\in R\text{.}\) Show \((x, z)\in R\text{.}\)
To disprove a property, find a specific counterexample.

Reflexive.
Find \((x, x)\notin R\) for some \(x\in A\text{.}\)

Symmetric.
Find \((x, y)\in R\) with \((y, x)\notin R\text{.}\)

Transitive.
Find \((x, y), (y, z)\in R\) with \((x, z)\notin R\text{.}\)
Example 5.4.9. Proving Refexive, Symmetric, Transitive.
Let \(R\) be the relation on \(\mathbb{Z}\) given by \((m, n)\in R\Leftrightarrow 3\mid(mn)\text{.}\)
Reflexive: Show \((m, m)\in R\text{.}\) Now \(mm=0\text{,}\) and \(3\mid 0\text{.}\) So we get that \(3\mid mm\text{.}\) Thus \((m, m)\in R\) for all \(m\in \mathbb{Z}\text{.}\)
Symmetric: Assume \((x, y)\in R\text{.}\) Then \(3\mid (xy)\text{.}\) This implies \(xy=3k\) for some \(k\in\mathbb{Z}\text{.}\) But then \(yx=3k=3(k)\text{,}\) where \(k\in \mathbb{Z}\text{.}\) Thus, \(3\mid (yx)\text{.}\) Hence, \((y, x)\in R\text{.}\)
Transitive: Assume \((x, y), (y, z)\in R\text{.}\) Then \(3\mid (xy)\) and \(3\mid (yz)\text{.}\) This implies \(xy=3k\) for some \(k\in\mathbb{Z}\) and \(yz=3j\) for some \(j\in\mathbb{Z}\text{.}\) But then \(xz=xy+yz=3k+3j=3(j+k)\text{,}\) where \(k+j\in \mathbb{Z}\text{.}\) Thus, \(3\mid (xz)\text{.}\) Hence, \((x, z)\in R\text{.}\)
Activity 5.4.6. The Equals Relation.
Define the relation on \(\mathbb{R}\) by \(xRy \iff x=y\text{.}\)
(a)
Prove or disprove \(R\) is reflexive.
(b)
Prove or disprove \(R\) is symmetric.
(c)
Prove or disprove \(R\) is transitive.
Activity 5.4.7. The Less Than Relation.
Define the relation on \(\mathbb{R}\) by \(xRy \iff x < y\text{.}\)
(a)
Prove or disprove \(R\) is reflexive.
(b)
Prove or disprove \(R\) is symmetric.
(c)
Prove or disprove \(R\) is transitive.
Definition 5.4.10.
A relation that is reflexive, symmetric and transitive is an equivalence relation.
In
Example 5.4.9 we proved that the relation given by
\((m, n)\in R \Leftrightarrow 3\mid (mn)\) is an equivalence relation since we proved it is reflexive, symmetric, and transitive.
In fact, the proof can easily be adapted to show \((m, n)\in R \Leftrightarrow d\mid (mn)\) is an equivalence relation for \(d\neq 0, d\in \mathbb{Z}\text{.}\)
This is an important enough relation that it has its own notation.
\begin{equation*}
m\equiv n \mod d.
\end{equation*}
Definition 5.4.11.
Let \(m, n, d\in \mathbb{Z}, d>0\text{.}\) Then \(m\) and \(n\) are congruent modulo \(d\) if \(d\mid (mn)\text{.}\) We denote congruence mod \(d\) by \(m\equiv n \mod d\).
We often just say \(m\) is congruent to \(n\) mod \(d\text{.}\)
Example 5.4.12. Congruence mod \(d\).
True or false: \(7\equiv 1 \mod 3\text{.}\)
Answer 1.Since \(3\mid (71)\text{,}\) true.
True or false: \(7\equiv 2 \mod 3\text{.}\)
Answer 2.Since \(3\mid (7+2)\text{,}\) true.
True or false: \(7\equiv 7 \mod 3\text{.}\)
Answer 3.Since \(3\nmid (7+7)\text{,}\) false.
True or false: \(7\equiv 2 \mod 3\text{.}\)
Answer 4.Since \(3\nmid (72)\text{,}\) false.
Let \(R\) be an equivalence relation on \(A\text{.}\) Let \(a\in A\text{.}\) The set
\begin{equation*}
[a]=\{b\in A : b R a\}
\end{equation*}
is the equivalence class of \(a\text{.}\)
Given a specific \(a\in A\text{,}\) we find the equivalence class of \(a\) by finding all the elements that are related to \(a\text{.}\) Keep in mind the equivalence class is a set, denoted \([a]\text{.}\)
Example 5.4.13. Equivalence Classes.
Consider the equivalence relation \(m\equiv n \mod 3\text{,}\) on \(\mathbb{Z}\text{.}\)

Find \([0]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 0.
Answer.\([0]=\{0, 3, 3, 6, 6, \ldots\}=\{3k : k\in \mathbb{Z}\}\)

Find \([1]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 1.
Answer.\([1]=\{1, 4, 2, 5, 7, 10, \ldots\}=\{3k+1: k\in \mathbb{Z}\}\)

Find \([2]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 2.
Answer.\([2]=\{2, 5, 1, 4, 7, \ldots\}=\{3k+2: k\in \mathbb{Z}\}\)

Find \([3]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 3.
Answer.\([3]=\{0, 3, 3, 6, 6, \ldots\}=\{3k : k\in \mathbb{Z}\}\)

Find \([1]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 1.
Answer.\([1]=\{2, 5, 1, 4, 7, \ldots\}=\{3k+2: k\in \mathbb{Z}\}\)
We can notice a few things from this last example. We can see that some of our equivalence classes are the same. In particular, \([0]=[3]\) and \([2]=[1]\text{.}\) In fact, there are only three distinct equivalence classes, \([0], [1], [2]\text{,}\) any other equivalence class will equal one of these.
A few other things to notice, distinct equivalence classes are disjointthey have no elements in common. Also, \([a]\) contains \(a\text{.}\) Furthermore, the equivalence classes \([0], [1], [2]\) partition the integers.
Definition 5.4.14.
A set of subsets of a set \(B\text{,}\) \(\{A_1, A_2, \ldots, A_n\}\text{,}\) is a partition of \(B\) if
\(\bigcup_{i=1}^nA_i=B\text{,}\)
\(A_i\cap A_j=\emptyset\) whenever \(i\neq j\text{.}\)
What this really says is that a set of subsets will be a partition of \(B\) if the union of the subsets is all of \(B\text{,}\) and the subsets are pairwise disjoint.
Example 5.4.15. Partition.
Let \(B=\{1, 2, 3, 4, 5, 6\}\text{.}\) Then let \(A_1=\{1\}, A_2=\{2, 4, 6\}, A_3=\{3, 5\}\text{.}\) We can see that \(\{A_1, A_2, A_3\}\) is a partition of \(B\) since \(A_1\cup A_2\cup A_3=B\) and the subsets have no elements in common, hence they are disjoint.
Now if we let \(A_1=\{1, 2, 3, 4\}, A_2=\{2, 3, 4, 5, 6\}\text{.}\) We can see that \(\{A_1, A_2\}\) is not a partition of \(B\) since \(A_1\cap A_2=\{2, 3, 4\}\neq\emptyset\text{.}\)
Example 5.4.16. More Equivalence Classes.
Let \(N(A)\) be the number of elements in \(A\text{.}\)
Consider the equivalence relation \(A R B \Leftrightarrow N(a)=N(B)\text{,}\) on \(\mathcal{P}(\{1, 2, 3\})\text{.}\)
This is the relation where two subsets of \(\{1, 2, 3\}\) are related if they have the same number of elements. You can check that this is an equivalence relation.

Find \([\emptyset]\text{,}\) the set of elements in \(\mathcal{P}(\{1, 2, 3\})\) equivalent to \(\emptyset\text{.}\)
Answer.
\([\emptyset]=\{\emptyset\}\text{,}\) since this is the only subset with 0 elements.

Find \([\{1\}]\text{.}\)
Answer.
\([\{1\}]=\{\{1\}, \{2\}, \{3\}\}\text{,}\) since these all have 1 element.

Find \([\{1, 2\}]\text{.}\)
Answer.\([\{1, 2\}]=\{\{1, 2\}, \{2, 3\}, \{1, 3\}\}\)

Find \([\{1, 2, 3\}]\text{.}\)
Answer.\([\{1, 2, 3\}]=\{\{1, 2, 3\}\}\)
Once again, the distinct equivalence classes are disjointthey have no elements in common. Furthermore, the equivalence classes \([\emptyset], [\{1\}], [\{1, 2\}], [\{1, 2, 3\}]\) partition the power set by size of the subset.
Activity 5.4.8. An Absolute Value Relation.
Define the relation on \(\mathbb{R}\) by \(xRy \iff x=y\text{.}\)
(a)
Prove \(R\) is an equivalence relation.
(b)
Find \([0]\) and \([5]\text{.}\)
Activity 5.4.9. Equivalence Mod 5.
Recall that \(n \equiv m\ \text{mod}\ 5\iff 5\mid (mn)\text{.}\)
(a)
Prove the relation \(nRm \iff n \equiv m\ \text{mod}\ 5\) is an equivalence relation on \(\mathbb{Z}\text{.}\)
(b)
Find \([0]\) and \([2]\text{.}\)
Activity 5.4.10. A Partition Relation.
Let \(S=\{1, 2, 3, 4, 5, 6\}\text{.}\) Let \(A_1=\{1, 2, 3\}, A_2=\{4\}, A_3=\{5, 6\}\text{.}\)
(a)
Check the conditions in
Definition 5.4.14 to show
\(\{A_i\}\) is a partition of
\(S\text{.}\)
(b)
Define the relation on \(S\text{,}\) \(xRy \iff\) \(x\) and \(y\) are in the same subset of the partition. Is \(1 R 3\text{?}\) Is \(2 R 4?\) Is \(5 R 5?\)
(c)
Show \(R\) is reflexive, symmetric and transitive.
(d)
Find \([1]\text{,}\) the equivalence class of 1.
(e)
Do you think this particular partition matters? Could we define this relation on any partition of any set and still have it be reflexive, symmetric and transitive?
There is an important connection between equivalence classes and partitions, as we see in the next two theorems.
Theorem 5.4.17.
Let \(A\) be a set and \(R\) an equivalence relation. The equivalence classes of \(R\) form a partition of \(A\)
.Conversely, as we saw in
Activity 5.4.10, if we have a partition
\(\{A_1, A_2, \ldots, A_n, \ldots\}\) of
\(A\) and define the relation
\((a, b)\in R \Leftrightarrow a\) and
\(b\) are in the same subset
\(A_i\text{,}\) then
\(R\) is an equivalence relation. We call this the equivalence relation
induced by the partition.
Theorem 5.4.18.
Let \(A\) be a set and \(\{A_1, A_2, \ldots, A_n, \ldots\}\) be a partition of \(A\text{.}\) Let \(R\) be the relation induced by the partition. Then \(R\) is an equivalence relation.
The proof of
Theorem 5.4.17 follows directly from the next two Lemmas.
Lemma 5.4.19.
Let \(R\) be an equivalence relation on \(A\) and \(a, b\in A\text{.}\) If \(a R b\) then \([a]=[b]\text{.}\)
Proof.
Since we want to show the sets are equal, we will show \([a], [b]\) are subsets of each other.
Show \([a]\subseteq [b]\text{.}\) Let \(x\in [a]\text{.}\) Then by defintion of equivalence class, \(x R a\text{.}\) We assumed \(a R b\text{.}\) By the transitive property, \(x R b\text{.}\) Thus, \(x\in [b]\text{.}\)
Show \([b]\subseteq [a]\text{.}\) Let \(x\in [b]\text{.}\) Then by defintion of equivalence class, \(x R b\text{.}\) We assumed \(a R b\text{.}\) By the symmetric property, \(b R a\text{.}\) By the transitive property, \(x R a\text{.}\) Thus, \(x\in [a]\text{.}\)
Lemma 5.4.19 really says that if two elements are related in an equivalence relation, they the must have the same equivalence class. You can check this with the above examples. Note, we needed the symmetric and transitive properties to prove this lemma.
Lemma 5.4.20.
Let \(R\) be an equivalence relation on \(A\) and \(a, b\in A\text{.}\) Either \([a]\cap[b]=\emptyset\) or \([a]=[b]\text{.}\)
Before proving the lemma, note that we are trying to prove an “or” statement. A common technique is to assume one part is false and show the other part is true. This technique comes from the logical equivalence \(p\vee q\equiv \neg p\rightarrow q\text{.}\)
Proof.
Assume
\([a]\cap[b]\neq \emptyset\text{.}\) We want to show
\([a]=[b]\text{.}\) Since
\([a]\cap[b]\neq \emptyset\text{,}\) there exists
\(x\in [a]\cap[b]\text{.}\) This means
\(x R a\) and
\(x R b\text{.}\) By the symmetric property,
\(a R x\text{.}\) By the transitive property, since
\(a R x\) and
\(x R b\text{,}\) we have
\(a R b\text{.}\) By
Lemma 5.4.19,
\([a]=[b]\text{.}\)
Lemma 5.4.20 really say that two equivalence classes are either disjoint or exactly the same.
Theorem 5.4.17 follows since, by the reflexive property,
\(x R x, \forall x\in A\) means every element is in an equivalence class. Thus, the union of the equivalence classes is all of
\(A\text{.}\) By
Lemma 5.4.20 distinct equivalence classes are disjoint. Thus, we have a partition of
\(A\text{.}\)
Exercises Exercises
1.
Define the congruence modulo 3 relation, \(T\text{,}\) on \(\mathbb{Z}\) by
\begin{equation*}
m\ T\ n \iff 3\mid (mn).
\end{equation*}
Is \(10\ T\ 1\text{?}\) Is \(1\ T\ 10\text{?}\) Is \((2, 2)\in T\text{?}\) Is \((8, 1)\in T\text{?}\)
List five integers \(n\) such that \(n\ T\ 0\text{.}\)
List five integers \(n\) such that \(n\ T\ 1\text{.}\)
List five integers \(n\) such that \(n\ T\ 2\text{.}\)
2.
Define the relation, \(S\text{,}\) on \(\mathbb{Z}\) by
\begin{equation*}
m\ S\ n \iff 5\mid (m^2n^2).
\end{equation*}
Is \(1\ S\ (9)\text{?}\)
Is \(2\ S\ 13\text{?}\)
Is \(2\ S\ (8)\text{?}\)
Is \((8)\ S\ 2\text{?}\)
3.
Let \(A=\{3, 4, 5\}\) and \(B=\{4, 5, 6\}\) and let \(S\) be the “divides” relation. That is, for all \((x, y)\in A\times B\text{,}\)
\begin{equation*}
x\ S\ y \iff x\mid y.
\end{equation*}
Find the set of ordered pairs in \(S\text{.}\)
4.
Let \(G\) be the relation on \(\mathbb{R}\) defined by
\begin{equation*}
x\ G\ y\iff xy\geq 0.
\end{equation*}
Determine if \(G\) is reflexive. Justify your answer.
Determine if \(G\) is symmetric. Justify your answer.
Determine if \(G\) is transitive. Justify your answer.
5.
Let \(D\) be the relation on \(\mathbb{Z}^+\) defined by
\begin{equation*}
m\ D\ n\iff m\mid n.
\end{equation*}
Determine if \(D\) is reflexive. Justify your answer.
Determine if \(D\) is symmetric. Justify your answer.
Determine if \(D\) is transitive. Justify your answer.
6.
Let \(F\) be the relation on \(\mathbb{R}\times \mathbb{R}\) defined by
\begin{equation*}
(x_1, y_1)\ F\ (x_2, y_2)\iff x_1=x_2.
\end{equation*}
Determine if \(F\) is reflexive. Justify your answer.
Determine if \(F\) is symmetric. Justify your answer.
Determine if \(F\) is transitive. Justify your answer.
7.
Define the relation \(R\) on \(\mathbb{Z}\) by
\begin{equation*}
m\ R\ n \iff 5\mid(mn).
\end{equation*}
Prove or disprove \(R\) is reflexive.
Prove or disprove \(R\) is symmetric.
Prove or disprove \(R\) is transitive.
8.
Let \(X=\{a, b, c\}\) and \({\cal P}(X)\) be the power set of \(X\text{.}\) Define the relation \(L\) on \({\cal P}(X)\) by
\begin{equation*}
A\ L\ B \iff \text{ the number of elements in $A$ is less than the number of elements in $B$.}
\end{equation*}
Prove or disprove \(L\) is reflexive.
Prove or disprove \(L\) is symmetric.
Prove or disprove \(L\) is transitive.
9.
Let \(X\) be a nonempty set and \({\cal P}(X)\) be the power set of \(X\text{.}\) Define the “subset” relation \(S\) on \({\cal P}(X)\) by
\begin{equation*}
A\ S\ B \iff A\subseteq B.
\end{equation*}
Prove or disprove \(S\) is reflexive.
Prove or disprove \(S\) is symmetric.
Prove or disprove \(S\) is transitive.