7.2: Equivalence Relations

As we have seen in the previous section, the notions of reflexive, symmetric, and transitive are independent of each other. That is, a relation may have some combination of these properties, possibly none of them and possibly all of them. However, we have a special name for when a relation satisfies all three properties.

Definition 7.35. Let $\sim$ be a relation on a set $A$. Then $\sim$ is called an equivalence relation on $A$ if $\sim$ is reflexive, symmetric, and transitive.

The symbol “$\sim$" is usually pronounced as “twiddle" or “tilde" and the phrase “$a\sim b$" could be read as “$a$ is related to $b$" or “$a$ twiddles $b$".

Problem 7.36. Let $A=\{1,2,3,4,5,6\}$ and define $$R=\{(1,1),(1,6),(2,2),(2,3),(2,4),(3,3),(3,2),(3,4),(4,4),(4,2),(4,3),(5,5),(6,6),(6,1)\}.$$ Using $R$, complete each of the following.

1. Draw the digraph for $R$.
2. Determine whether $R$ is an equivalence relation on $A$.
3. Find $Rel(R)$ by determining $rel(x)$ for each $x\in A$.

Problem 7.37. Let $A=\{a,b,c,d,e\}$.

1. Make up an equivalence relation $\sim$ on $A$ by drawing a digraph such that $a$ is not related to $b$ and $c$ is not related to $b$.
2. Using your digraph, find $Rel(\sim)$ by determining $rel(x)$ for each $x\in A$.

Problem 7.38. Given a finite set $A$ and an equivalence relation $\sim$ on $A$, describe what the corresponding digraph would have to look like.

Problem 7.39. Determine which relations given in Problem 7.34 are equivalence relations.

Problem 7.40. Let $\mathcal{T}$ be the set of all triangles and define $\sim$ on $\mathcal{T}$ via $T_1\sim T_2$ if $T_1$ is similar to $T_2$. Determine whether $\sim$ is an equivalence relation on $\mathcal{T}$.

Problem 7.41. If possible, construct an equivalence relation on the empty set. If this is not possible, explain why.

Theorem 7.42. Suppose $\sim$ is an equivalence relation on a set $A$ and let $a,b\in A$. Then $rel(a)=rel(b)$ if and only if $a\sim b$.

Theorem 7.43. Suppose $\sim$ is an equivalence relation on a set $A$. Then

1. $\displaystyle \bigcup_{a\in A}\ rel(a)=A$, and
2. [thm:equiv yields partition b] For all $a,b\in A$, either $rel(a)=rel(b)$ or $rel(a)\cap rel(b)=\emptyset$.

In light of Theorem 7.43, we have the following definition.

Definition 7.44. If $\sim$ is an equivalence relation on a set $A$, then for each $a\in A$, we refer to $rel(a)$ as the equivalence class of $a$.

When $\sim$ is an equivalence relation on a set $A$, it is common to write each equivalence class $rel(a)$ as $[a]$ (or sometimes $\overline{a}$). The element $a$ inside the square brackets is called the representative of the equivalence class $[a]$. Theorem 7.42 implies that an equivalence class can be represented by any element of the equivalence class. For example, in Problem 7.36, we have $[1]=[6]$ since 1 and 6 are in the same equivalence class. The collection of equivalence classes $Rel(\sim)$ is often denoted by $A/\mathord\sim$, which is read as “$A$ modulo $\sim$" or “$A$ mod $\sim$". The collection $A/\mathord\sim$ is sometimes referred to as the quotient of $A$ by $\sim$.

Example 7.45. Let $P$ denote the residents of a particular town and define $\sim$ on $P$ via $a\sim b$ if $a$ and $b$ have the same last name. It is easily seen that this relation is reflexive, symmetric, and transitive, and hence $\sim$ is an equivalence relation on $P$. The equivalence classes correspond to collections of individuals with the same last name. For example, Maria Garcia, Anthony Garcia, and Ariana Garcia all belong to the same equivalence class. Any Garcia can be used as a representative for the corresponding equivalence class, so we can denote it as $[\text{Maria Garcia}]$, for example. The collection $P/\mathord\sim$ consists of the various sets of people with the same last name. In particular, $[\text{Maria Garcia}]\in P/\mathord\sim$.

Example 7.46. The five distinct sets of relatives that you identified in Problem 7.22 are the equivalence classes for $\equiv_5$ on $\mathbb{Z}$. These equivalence classes are often called the congruence classes modulo 5.

The upshot of Theorem 7.43 is that given an equivalence relation, every element lives in exactly one equivalence class. In the next section, we will see that we can run this in reverse. That is, if we separate out the elements of a set so that every element is an element of exactly one subset, then this determines an equivalence relation.

Problem 7.47. If $\sim$ is an equivalence relation on a finite set $A$, describe $A/\mathord\sim$ in terms of the digraph corresponding to $\sim$.

Problem 7.48. For each of the equivalence relations you identified in Problem 7.39, succinctly describe the corresponding equivalence classes.

Problem 7.49. Suppose $R$ and $S$ are both equivalence relations on a set $A$. Is $R\cap S$ an equivalence relation on $A$? If so, prove it. Otherwise, provide a counterexample.

Problem 7.50. Suppose $R$ and $S$ are both equivalence relations on a set $A$. Is $R\cup S$ an equivalence relation on $A$? If so, prove it. Otherwise, provide a counterexample.