7.2: Definition and Basic Properties of Equivalence Relations

People often need to sort through a collection of objects, putting similar objects together in a group.

Example \(7.2.1\).

When making an inventory of the animals in a zoo, we may wish to count the number of antelopes, the number of baboons, the number of cheetahs, and so forth. In this case, all of the animals of the same species might be grouped together.

Solution

Mathematically speaking, we would define a binary relation \(S\) on the set of animals in the zoo by \[x S y \quad \text { iff } \quad x \text { and } y \text { are in the same species. }\]

When \(x\) and \(y\) are placed in the same group (that is, when \(x S y\) in the above example), we may say that \(x\) is “equivalent” to \(y\). This means that \(x\) and \(y\) are the same in all respects that are of interest to us. (In the above example, we are interested only in the species of an animal, not its weight, or its age, or anything else.) We call the corresponding binary relation an “equivalence relation.” Thus, the binary relation \(S\) in the above example is an equivalence relation.

Example \(7.2.2\).

Here are additional examples:

1. If we are interested only in first names, we could define an equivalence relation \(N\) on the set of all people by \[x N y \text { iff } x \text { has the same first name as } y \text {. }\]
2. Suppose a candy store has bins for different kinds of candy that they sell. To an employee restocking the bins, all pieces of candy that go into the same bin are the same, so he or she is dealing with an equivalence relation on the set of candy.
3. In geometry, one is often interested only in the shape of a triangle, not its location (or its colour, or anything else). Therefore, mathematicians define an equivalence relation \(\cong\) on the set of all triangles by \[T_{1} \cong T_{2} \text { iff } T_{1} \text { is congruent to } T_{2} .\]

Remark \(7.2.3\).

Suppose \(\sim\) is an equivalence relation. (That is, we have \(x \sim y\) iff \(x\) and \(y\) are the same in all respects that are of interest to us.) Then we would expect:

1. \(\sim\) is reflexive (\(x\) is the same as \(x\)),
2. \(\sim\) is symmetric (if \(x\) is the same as \(y\), then \(y\) is the same as \(x\)), and
3. \(\sim\) is transitive (if \(x\) is the same as \(y\), and \(y\) is the same as \(z\), then \(x\) is the same as \(z\)).

This motivates the following definition:

Definition \(7.2.4\).

An equivalence relation on a set \(A\) is a binary relation on A that is reflexive, symmetric, and transitive.

Remark \(7.2.5\).

Instead of representing an equivalence relation by a letter, it is traditional to use the symbol \(\sim\) (or sometimes \(\equiv\) or \(\cong\)).

Example \(7.2.6\).

For any \(n \in \mathbb{Z}\), we know that congruence modulo \(n\) is reflexive, symmetric, and transitive (see Exercise \(5.1.18\)). Therefore, congruence modulo \(n\) is an equivalence relation.

Example \(7.2.7\).

Define a binary relation \(\sim\) on \(\mathbb{R}\) by \(x \sim y\) iff \(x^{2} = y^{2}\). Then \(\sim\) is an equivalence relation.

Solution

We wish to show that \(\sim\) is reflexive, symmetric, and transitive.

(reflexive) Given \(x \in \mathbb{R}\), we have \(x^{2} = x^{2}\), so \(x \sim x\).
(symmetric) Given \(x, y \in \mathbb{R}\), such that \(x \sim y\), we have \(x^{2} = y^{2}\). Since equality is symmetric, this implies \(y^{2} = x^{2}\), so \(y \sim x\).
(transitive) Given \(x, y, z \in \mathbb{R}\), such that \(x \sim y\) and \(y \sim z\), we have \(x^{2} = y^{2}\) and \(y^{2} = z^{2}\). Therefore \(x^{2} = y^{2} = z^{2}\), so \(x^{2} = z^{2}\). Hence \(x \sim z\).

Example \(7.2.8\).

Define a binary relation \(\sim\) on \(\mathbb{N} \times \mathbb{N}\) by \((a_{1}, b_{1}\)) \sim (a_{2}, b_{2})\) iff \(a_{1}+b_{2} = a_{2}+b_{1}\). Then \(\sim\) is an equivalence relation.

Solution

We wish to show that \(\sim\) is reflexive, symmetric, and transitive.

(reflexive) Given \((a, b) \in \mathbb{N} \times \mathbb{N}\), we have \(a + b = a + b\), so \((a, b) \sim (a, b)\).
(symmetric) Given \((a_{1}, b_{1}),(a_{2}, b_{2}) \in \mathbb{N} \times \mathbb{N}\), such that \((a_{1}, b_{1}) \sim (a_{2}, b_{2})\), the definition of \(\sim\) tells us that \(a_{1} + b_{2} = a_{2} + b_{1}\). Since equality is symmetric, this implies \(a_{2} + b_{1} = a_{1} + b_{2}\), so \((a_{2}, b_{2}) \sim (a_{1}, b_{1})\).
(transitive) Given \((a_{1}, b_{1}),(a_{2}, b_{2}),(a_{3}, b_{3}) \in \mathbb{N} \times \mathbb{N}\), such that \[(a_{1}, b_{1}) \sim (a_{2}, b_{2}) \text { and } (a_{2}, b_{2}) \sim (a_{3}, b_{3}) ,\]

we have \[a_{1}+b_{2}=a_{2}+b_{1} \text { and } a_{2}+b_{3}=a_{3}+b_{2} .\]
Therefore \[\begin{aligned}
\left(a_{1}+b_{3}\right)+\left(a_{2}+b_{2}\right) &=\left(a_{1}+b_{2}\right)+\left(a_{2}+b_{3}\right) \\
&=\left(a_{2}+b_{1}\right)+\left(a_{3}+b_{2}\right) \\
&=\left(a_{3}+b_{1}\right)+\left(a_{2}+b_{2}\right)
\end{aligned}\]
Subtracting \(a_{2} + b_{2}\) from both sides of the equation, we conclude that \(a_{1} + b_{3} = a_{3} + b_{1}\), so \((a_{1}, b_{1}) \sim (a_{3}, b_{3})\).

Exercise \(7.2.10\).

Show that each of these binary relations is an equivalence relation.

1. A binary relation \(\sim\) on \(\mathbb{R}\) is defined by \(x \sim y \text { iff } x^{2}-3 x=y^{2}-3 y\)
2. A binary relation \(\sim\) on \(\mathbb{R}\) is defined by \(x \sim y \text { iff } x-y \in \mathbb{Z} \text {. }\)
   [Hint: You may assume (without proof) that the negative of any integer is an integer, and that the sum of any two integers is an integer. For transitivity, notice that \(x-z=(x-y)+(y-z)\).]
3. A binary relation \(\sim\) on \(\mathbb{N}^{+} \times \mathbb{N}^{+}\) is defined by \(\left(a_{1}, b_{1}\right) \sim\left(a_{2}, b_{2}\right) \text { iff } a_{1} b_{2}=a_{2} b_{1}\).
   [Hint: Similar to the proof in Example \(7.2.8\), but with multiplication in place of addition.]

Any time we have a function, we can use it to make an equivalence relation on the domain of the function:

Example \(7.2.11\).

1. Every animal has only one species, so \(\text { Species }\) is a function that is defined on the set of all animals. The equivalence relation \(S\) of Example \(7.2.1\) can be characterized by \[x S y \quad \text { iff } \quad \text { Species }(x)=\operatorname{Species}(y) .\]
2. If we assume that every person has a first name, then \(\text { FirstName }\) is a function on the set of all people. The equivalence relation \(N\) of Example \(7.2.2(1)\) can be characterized by \[x N y \quad \text { iff } \quad \text { FirstName }(x)=\text { FirstName }(y) .\]

The following result generalizes this idea to all functions.

Exercise \(7.2.12\).

Suppose \(f : A \rightarrow B\). If we define a binary relation \(\sim\) on \(A\) by \[a_{1} \sim a_{2} \quad \text { iff } \quad f\left(a_{1}\right)=f\left(a_{2}\right) ,\]

then \(\sim\) is an equivalence relation.

Exercise \(7.2.13\).

Show that if \(\sim\) is an equivalence relation on \(\mathbb{R}\), then there exist \(a, b \in \mathbb{R}\), such that \(a \sim b\) and \(a + b = 6\).