Equivalence Relations and partitions
Partitions
Definition: A partition of a set \(A\) is a set of non-empty subsets of \(A\) such that the union of all of the subsets is \(A\) and the intersection of any two of the subsets is the empty set.
Intuitively: a partition is a division of \(A\) into disjoint subsets.
Partitions (Examples)
Integers divided into even and odd integers.
Integers divided into congruence classes modulo \(3\).
Books with one author divided up into classes by author.
People grouped by their county of residence.
Partitions and Equivalence Relations
Theorem (11.2): Let \(R\) be an equivalence relation on a set \(A\). Then the equivalence classes \(\{[a]:a\in A\}\) form a partition of \(A\).
Converse to Theorem 11.2
Proposition: Suppose \(P\) is a partition of a set \(A\). Define a relation \(R\) on \(A\) by setting \(aRb\) if and only if \(a\) and \(b\) belong to the same element of the partition. Then \(R\) is an equivalence relation.
As a result, partitions of a set are “the same” as equivalence relations on a set.