Equivalence Relations

We now turn our attention to equivalence relations.

Definition of Equivalence Relations

Definition 1 A binary relation \((R,A,A)\) is symmetric if \(x\mathrel{R}y\) implies \(y\mathrel{R}x\). If

\[(x\mathrel{R}y)\wedge(y\mathrel{R}z)\implies x\mathrel{R}z\]

holds, then it is called transitive. Finally, if \(x\mathrel{R}x\) for all \(x\), then \(R\) is reflexive on \(A\). A relation \(R\) that is reflexive, symmetric, and transitive is called an equivalence relation.

Hereafter, when \(R\) is an equivalence relation, we will use \(x\sim_{\tiny R}y\). When there is no risk of confusion, we may also write \(x\sim y\) or \(x\equiv y\).

Example 2 On a given set \(A\), the relation $x=y$ is an equivalence relation on \(A\), and in this case \(R\) is the same as the set \(\Delta_A\). On the other hand, the relation $x\in A$ and $y\in A$ can easily be verified to also be an equivalence relation on \(A\). The set representing this relation is exactly \(A\times A\).

Consider any equivalence relation \(R\) on a set \(A\). Since \(R\) is reflexive, \(\Delta_A\subseteq R\), and the inclusion \(R\subseteq A\times A\) is clear. Thus the first of the two examples above is the smallest equivalence relation that can be defined on \(A\), and the second is the largest.

This can be summarized as follows.

Proposition 3 A binary relation \((R,A,A)\) is an equivalence relation if and only if the following three conditions hold:

\[\pr_1R=A,\qquad R=R^{-1},\qquad R\circ R=R\]

Proof

First, assume \(R\) is an equivalence relation.

• Since \((x,x)\in R\) for all \(x\in A\), \(\pr_1R=A\) holds.

• Also, since \(R\) is symmetric, \(x\sim_\tiny{R} y\iff y\sim_\tiny{R}x\) holds, and thus from

  \[(x,y)\in R\iff (y,x)\in R\iff (x,y)\in R^{-1}\tag{1}\]

  we obtain \(R=R^{-1}\).

• Finally, we need to show \(R\circ R=R\). First, let \((x,y)\in R\) be arbitrary. Since \(R\) is reflexive, \((x,x)\in R\), and from \((x,x)\in R\) and \((x,y)\in R\), we see that \((x,y)\in R\circ R\). Conversely, let \((x,y)\in R\circ R\) be arbitrary. Then there exists \(z\in A\) such that \((x,z)\in R\) and \((z,y)\in R\). By transitivity of \(R\), \((x,y)\in R\) holds.

Now suppose a binary relation \(R\) satisfying the three given conditions is provided.

• From \(R=R^{-1}\), by reversing the logic in equation (1), we see that \(R\) is symmetric.
• Assume \(x\mathrel{R}y\) and \(y\mathrel{R}z\) hold. Then \((x,z)\in R\circ R=R\), so \(R\) is transitive.
• Finally, from \(\pr_1R=A\), we know there exists \(y\in A\) such that \((x,y)\in R\). Now since \(R\) is symmetric, \(y\mathrel{R}x\) also holds, and by transitivity, \((x\mathrel{R}y)\wedge(y\mathrel{R}x)\implies x\mathrel{R}x\) holds. That is, \(R\) is reflexive.

In this post, we will explore the fundamental properties of equivalence relations, and in the next post, we will examine equivalence relations that appear in various contexts.

Equivalence Relations and Partitions

Definition 4 Consider an equivalence relation \((R,A,A)\). For any \(x\in A\), the section \(R(x)\) at \(x\) is called the equivalence class of \(x\) under \(R\). The collection of such equivalence classes is called the quotient set of \(R\), denoted by \(A/R\).

By definition, \(R(x)\) is the collection of elements that are considered equivalent to \(x\) under the equivalence relation \(R\). In many cases, the equivalence class containing \(x\) is written as \([x]_R\). When there is no risk of confusion, their set \(A/R\) may also be denoted as \(A/\mathord{\sim}\).

Set $$A$$ (left), equivalence relation $$R$$ defined on it (center), and quotient set $$A/R$$ (right). Each element of $$A/R$$ is an equivalence class $$[x]_R$$ from the middle figure.

Example 5 We have already seen that $x=y$ on a set \(A\) is an equivalence relation. In this relation, the equivalence class of \(x\) is the set \(\{x\}\). On the other hand, in the same example, $x\in A$ and $y\in A$ was also an equivalence relation, in which case the equivalence class of \(x\) is the entire set \(A\).

In Example 2, we said \(\Delta_A\) is the smallest and \(A\times A\) is the largest, but rather than comparing set inclusions, it is more common to say that \(\Delta_A\) is the finest equivalence relation and \(A\times A\) is the coarsest equivalence relation, following this perspective. (§Sum of Sets, ⁋Definition 1)

Lemma 6 For an equivalence relation \((R,A,A)\), define \(p:A\rightarrow A/R\) by \(x\mapsto [x]_R\). Then \(p\) is a function, and \(x\sim_{\tiny R} y\) is equivalent to \(p(x)=p(y)\).

Proof

It is not difficult to show that \(p\) as defined above is indeed a function. Here we only prove the equivalence.

First, assume \(x\sim_{\tiny R} y\). From \(y\in [x]_R=R(x)\), we have \(\{y\}\subseteq R(x)\), and thus by §Operations on Binary Relations, ⁋Proposition 6 and Proposition 3,

\[R(y)\subseteq R(R(x))=(R\circ R)(x)=R(x)\]

holds. Since \(R\) is an equivalence relation, we can swap the roles of \(x\) and \(y\), and thus \(R(x)=R(y)\) holds.

Conversely, if \([x]_R=[y]_R\), then from \(x\in [x]_R=[y]_R\), we obtain \(y\sim_{\tiny R} x\), and thus the lemma holds.

The function \(p\) above is called the canonical projection. Since the subset \([x]_R\subseteq A\) is the preimage under \(p\) of the element \([x]_R\in A/R\), we see that equivalence classes are pairwise disjoint. In other words, an equivalence relation \((R,A,A)\) induces a partition of \(A\).

The following proposition shows that the converse also holds.

Proposition 7 Let \((A_i)_{i\in I}\) be a partition of \(A\). Then the relation

there exists some \(i\) such that \(x,y\in A_i\)

is an equivalence relation on \(x\) and \(y\).

Proof

Let us denote the above relation by \(R\).

• It is clear that \(R\) is reflexive on \(A\).
• If \(x\) and \(y\) belong to the same set, then \(y\) and \(x\) also belong to the same set, so \(x\mathrel{R}y\) implies \(y\mathrel{R}x\). Thus \(R\) is symmetric.
• Finally, if \(x\mathrel{R}y\) and \(y\mathrel{R}z\), then \(x,y\in A_i\) and \(y,z\in A_j\). Since \(y\in A_i\cap A_j\) and \((A_i)_{i\in I}\) is a partition, \(i=j\). Thus \(x,z\in A_i\), and the proposition holds.

---

References

[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

---