2.3: Equivalence Relations
- Page ID
- 99058
Let \(X\) be a set and \(R\) a relation on \(X\). We say \(R\) is an equivalence relation if
(1) \(R\) is reflexive
(2) \(R\) is symmetric
(3) \(R\) is transitive.
Define a relation \(R\) on \(\mathbb{R}\) by \(x R y\) if and only if \(x^{2}=\) \(y^{2}\). Then \(R\) is an equivalence relation.
Let \(R\) be a relation defined on \(\mathbb{Z} \times \mathbb{Z}\) as follows. If \(a, b, c, d \in \mathbb{Z}\), \[(a, b) R(c, d) \text { if and only if } a+d=b+c \text {. }\] Then \(R\) is an equivalence relation. Indeed, let us check the three properties.
Reflexive: By (2.14), we have \((a, b) R(a, b)\) if \(a+b=a+b\), which clearly holds. Symmetric: Suppose \((a, b) R(c, d)\), so \(a+d=b+c\). To see if \((c, d) R(a, b)\), we must check whether \(c+b=d+a\); but this holds by the commutativity of addition.
Transitive: Suppose \((a, b) R(c, d)\) and \((c, d) R(e, f)\). We must check that \((a, b) R(e, f)\), in other words that \[a+f=b+e .\] We have \(a+d=b+c\) and \(c+f=d+e\), and adding these two equations we get \[a+d+c+f=b+c+d+e .\] Cancelling \(c+d\) from each side of (2.16), we get (2.15) as desired.
Let \(R\) be a relation on \(X=\mathbb{Z} \times \mathbb{N}^{+}\)defined by \[(a, b) R(c, d) \text { if and only if } a d=b c \text {. }\] Then \(R\) is an equivalence relation on \(X\). (Prove this; Exercise 2.4).
Let \(f: X \rightarrow Y\). Define a relation \(R_{f}\) on \(X\) by \[x R_{f} y \text { if and only if } f(x)=f(y) .\] Then \(R_{f}\) is an equivalence relation. We check the conditions for an equivalence relation:
\(R_{f}\) is clearly reflexive, since, for any \(x \in X\), \[f(x)=f(x) .\] \(R_{f}\) is symmetric since, for any \(x \in X\) and \(y \in X\), \[f(x)=f(y) \text { if and only if } f(y)=f(x) .\] To show \(R_{f}\) is transitive, let \(x, y, z \in X\). If \(f(x)=f(y)\) and \(f(y)=\) \(f(z)\) then \(f(x)=f(z)\).
Equivalence relations have three of the key properties of identity. They allow us to relate objects in a set that we wish to consider as "the same" in a given context. This allows us to focus on which differences between mathematical objects are relevant to the discussion at hand, and which are not. For this reason, a common symbol for an equivalence relation is \(\sim\).
Let \(R\) be an equivalence relation on a set \(X\). If \(x \in X\) then the equivalence class of \(x\) modulo \(R\), denoted by \([x]_{R}\), is \[[x]_{R}=\{y \in X \mid x R y\} .\] If \(y \in[x]_{R}\) we call \(y\) a representative element of \([x]_{R}\). The set of all equivalence classes \(\left\{[x]_{R} \mid x \in X\right\}\) is written \(X / R\). It is called the quotient space of \(X\) by \(R\).
We may use \([x]\) for the equivalence class of \(x\), provided that the equivalence relation is clear.
Notation. Equivalence mod \(R, \equiv_{R}, \sim\) Let \(R\) be an equivalence relation on a set \(X\). We may express that \(x R y\) by writing \[x \equiv y \bmod R\] or \[x \equiv_{R} y\] or \[x \sim y .\] Proposition 2.19. Suppose that \(\sim\) is an equivalence relation on \(X\). Let \(x, y \in X\). If \(x \sim y\), then \[[x]=[y] .\] If \(x\) is not equivalent to \(y(x \nsim y)\), then \[[x] \cap[y]=\emptyset .\] Proof. (i) Assume \(x \sim y\). Let us show that \([x] \subseteq[y]\). Let \(z \in[x]\). This means that \(x \sim z\). Since \(\sim\) is symmetric, and \(x \sim y\), we have \(y \sim x\). As \(y \sim x\) and \(x \sim z\), by transitivity of \(\sim\) we get that \(y \sim z\). Therefore \(z \in[y]\). Since \(z\) is an arbitrary element of \([x]\), we have shown that \([x] \subseteq[y]\). As \(y \sim x\), the same argument with \(x\) and \(y\) swapped gives \([y] \subseteq[x]\), and therefore \([x]=[y]\).
(ii) Now assume that \(x\) and \(y\) are not equivalent. We must show that there is no \(z\) such that \(z \in[x]\) and \(z \in[y]\). We will argue by contradiction. Suppose there were such a \(z\). Then we would have \[x \sim z \quad \text { and } \quad y \sim z .\] By symmetry, we have also that \(z \sim y\), and by transitivity, we then have that \(x \sim y\). This contradicts the assumption that \(x\) is not equivalent to \(y\). So if \(x\) and \(y\) are not equivalent, no \(z\) can exist that is simultaneously in both \([x]\) and \([y]\). Therefore \([x]\) and \([y]\) are disjoint sets, as required.
So what have we shown? We have not shown that any particular relation is an equivalence relation. Rather we have shown that any equivalence relation on a set partitions the set into disjoint equivalence classes.
As we shall see throughout this book, and you will see throughout your mathematical studies, this is a surprisingly powerful tool.
Definition. Pairwise disjoint Let \(\left\{X_{\alpha} \mid \alpha \in A\right\}\) be a family of sets. The family is pairwise disjoint if for any \(\alpha, \beta \in A, \alpha \neq \beta\), \[X_{\alpha} \cap X_{\beta}=\emptyset .\] DEFINITION. Partition Let \(Y\) be a set and \(\mathcal{F}=\left\{X_{\alpha} \mid \alpha \in A\right\}\) be a family of non-empty sets. The collection \(\mathcal{F}\) is a partition of \(Y\) if \(\mathcal{F}\) is pairwise disjoint and \[Y=\bigcup_{\alpha \in A} X_{\alpha} .\] Given an equivalence relation \(\sim\) on a set \(X\), the equivalence classes with respect to \(\sim\) give a partition of \(X\). Conversely, partitions give rise to equivalence relations.
(i) Let \(X\) be a set, and \(\sim\) an equivalence relation on \(X\). Then \(X / \sim\) is a partition of \(X\). (ii) Conversely, let \(\left\{X_{\alpha} \mid \alpha \in A\right\}\) be a partition of \(X\). Let \(\sim\) be the relation on \(X\) defined by \(x \sim y\) whenever \(x\) and \(y\) are members of the same set in the partition. Then \(\sim\) is an equivalence relation.
PROOF. Part (i) of the theorem is Proposition \(2.19\) restated, and we gave the proof above. To prove the converse, we must show that the relation \(\sim\) defined as in part (ii) of the theorem is an equivalence.
Reflexivity: Let \(x \in X\). Then \(x\) is in some \(X_{\alpha_{0}}\), as the union of all these sets is all of \(X\). Therefore \(x \sim x\).
Symmetry: Suppose \(x \sim y\). Then there is some \(X_{\alpha_{0}}\) such that \(x \in X_{\alpha_{0}}\) and \(y \in X_{\alpha_{0}}\). This implies that \(y \sim x\).
Transitivity: Suppose \(x \sim y\) and \(y \sim z\). Then there are sets \(X_{\alpha_{0}}\) and \(X_{\alpha_{1}}\) such that both \(x\) and \(y\) are in \(X_{\alpha_{0}}\), and both \(y\) and \(z\) are in \(X_{\alpha_{1}}\). But since the sets \(X_{\alpha}\) form a partition, and \(y\) is in both \(X_{\alpha_{0}}\) and \(X_{\alpha_{1}}\), we must have that \(X_{\alpha_{0}}=X_{\alpha_{1}}\). This implies that \(x\) and \(z\) are in the same member of the partition, and so \(x \sim z\).