1.2 Equivalence Relations
Definition 1.2.1. Given any set \(X\), a subset \(\mathcal {R}\) of \(X\times X=\{(x,y):x,y\in X\}\) is called a relation on \(X\). If \((x,y)\in \mathcal {R}\) we write \(x\mathcal {R}y\) and say that \(x\) is related to \(y\).
Example 1.2.2. If \(X=\{1,2,3\}\), then \(X\times X=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}\) and \(\mathcal {R}=\{(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)\}\) is a relation on \(X\).
If \(x,y\in X\), then \(x\mathcal {R}y\) if and only if \((x,y)\in \mathcal {R}\).
Other commonly used notations for relations are \(\thicksim \) and \(\equiv \) \[x\thicksim y\iff x\mathcal {R}y\iff x\equiv y\]
Definition 1.2.3. A relation \(\mathcal {R}\) on a set \(X\) is called an equivalence relation if it satisfies the following conditions for all \(x,y,z\in X\),
- i.
- \(x\mathcal {R}x\) \((\mathcal {R}\) is reflexive)
- ii.
- \(x\mathcal {R}y\) implies \(y\mathcal {R}x\) \((\mathcal {R}\) is symmetric \()\)
- iii.
- \(x\mathcal {R}y\) and \(y\mathcal {R}z\) imply \(x\mathcal {R}z\) \((\mathcal {R}\) is transitive \()\)
Example 1.2.4. On the set \(\mathbb {R}-\{0\}\), define the relation \(\mathcal {R}\) by \(x\mathcal {R}y\) if and only if \(xy>0\). Then \(\mathcal {R}\) is an equivalence relation on \(\mathbb {R}-\{0\}\). All three conditions have to be checked:
- i.
- Reflexive. For \(x\neq 0\) we have \(x\cdot x=x^2>0\), so \(x\mathcal {R}x\).
- ii.
- Symmetric. If \(xy>0\) then \(yx=xy>0\), so \(x\mathcal {R}y\) implies \(y\mathcal {R}x\).
- iii.
- Transitive. Suppose \(xy>0\) and \(yz>0\). Multiplying these two positive numbers gives \(xy^2z>0\), and since \(y^2>0\) we may divide by it to get \(xz>0\). So \(x\mathcal {R}z\).
Two non-zero reals are related exactly when they have the same sign, so this relation has precisely two equivalence classes: the positive reals and the negative reals.
Definition 1.2.5. A collection \(\{X_i:i\in I\}\) of non-empty subsets of a set \(X\) is called a partition of \(X\) if
- 1.
- \(X_i\cap X_j=\emptyset \) whenever \(i\neq j\), and
- 2.
- \(\bigcup _{i\in I}X_i=X\).
The two conditions say that the pieces do not overlap and that between them they use up all of \(X\): every element of \(X\) lies in exactly one piece.
Example 1.2.6. \(S=\Big \{\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}, \{9,10\}\Big \}\) is a partition of the set \(X=\{1,2,3,4,5,6,7,8,9,10\}\): the five pieces are pairwise disjoint and their union is \(X\).
By contrast \(\Big \{\{1,2\},\{2,3\},\{4,5,6,7,8,9,10\}\Big \}\) is not a partition of \(X\), because the first two pieces share the element \(2\); and \(\Big \{\{1,2\},\{3,4\}\Big \}\) is not a partition of \(X\) either, because their union is not all of \(X\).
Definition 1.2.7. Let \(\mathcal {R}\) be an equivalence relation on a set \(X\) and let \(x\in X\). The equivalence class of \(x\) is the set \[[x]=\{y\in X: x\mathcal {R}y\},\] that is, the set of all elements related to \(x\).
We have the following fundamental result about equivalence classes.
Theorem 1.2.8. The equivalence classes of an equivalence relation on a set \(X\) constitute a partition of \(X\).
Proof. Let \(\mathcal {R}\) be an equivalence relation on \(X\). Two things must be shown: that the classes cover \(X\), and that two of them are either identical or disjoint.
The classes cover \(X\)
Let \(x\in X\). By reflexivity \(x\mathcal {R}x\), so \(x\in [x]\). Hence every element of \(X\) lies in at least one class, no class is empty, and \(\bigcup _{x\in X}[x]=X\).
Two classes that meet are equal
Suppose \([x]\cap [y]\neq \emptyset \), and pick \(z\in [x]\cap [y]\). Then \(x\mathcal {R}z\) and \(y\mathcal {R}z\).
Let \(a\in [x]\), so \(x\mathcal {R}a\). From \(z\mathcal {R}x\) (symmetry applied to \(x\mathcal {R}z\)) and \(x\mathcal {R}a\), transitivity gives \(z\mathcal {R}a\). From \(y\mathcal {R}z\) and \(z\mathcal {R}a\), transitivity gives \(y\mathcal {R}a\), so \(a\in [y]\). This shows \([x]\subseteq [y]\), and exchanging the roles of \(x\) and \(y\) shows \([y]\subseteq [x]\). Hence \([x]=[y]\).
So any two classes are either disjoint or the same set. Together with the first part, the distinct classes are non-empty, pairwise disjoint, and have union \(X\) — which is exactly what it means to be a partition of \(X\). □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.