Equivalence relations
The datum of an equivalence relation is a partition
What is the information that is contained by an equivalence relation on a set?
The datum of an equivalence relation on a set \( S \) turns out to be a partition of \( S \). Compare to the case of the product of two sets, which has a set of ordered pairs as its datum.
Partition. Definition.
Let \( S \) be a set. A partiton \( \mathcal{P} \) of \( S \) is a family of disjoint non-empty subsets of \( S \) that union to \( S \).
For example, \( \{\{1,3,5\}, \{2,4,6\}, \{0\}, \{7\}, \{8, 9\} \} \) is a partition of the set \( \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \).
From equivalence relations to partitions, and back
There is a 1-1 correspondence between partitions and equivalence relations, and in this sense they represent the same notion.
Here is the process of obtaining a partition from an equivalence relation. Let \( \sim \) be an equivalence relation on a set \( S \). For every \( a \in S \) the equivalence class of \( a \) is the subset of \( S \) defined by
The set of all equivalence classes is a partition of \( S \), denoted \( \mathcal{P}_{\sim} \).
Conversely, given a partition \( \mathcal{P} \), we can form an equivalence relation \( \sim \) where \( a \sim b \) is true if \( a \) and \( b \) are in the same element of \( \mathcal{P} \).
Quotients
The quotient of a set \( S \) with respect to an equivalence relation \( \sim \) is preciely the partition \( \mathcal{P}_{\sim} \) (the set of equivalence classes formed by \( \sim \) with respect to \( S \)). We write the quotient as \( S \):
Quotients and equivalence relations, a perspective
The equivalence relation becomes equality in the quotient. Taking a quotient turns an equivalence relation into an equality.
Example
Let \( \sim \) be the relation defined for \( \mathbb{Z} \) like so:
Then the quotient is the set containing two equivalence classes, \( \mathbb{Z}/ \mathord{\sim} = \{ [0]_{\sim}, [1]_{\sim} \} \).