that the equivalence classes
of any equivalence relation
R on a set
A form a partition
of A is as follows (assuming the axiom of choice
so that representatives can be chosen from each of the equivalence classes):
First, show that U
(x is an element
of A) is equal
Let y be an element of U Rx. Therefore, y belongs to some Rz, so y R z, and thus y is an element of A, because R only relates elements of A. We then have that U Rx is a subset of A. Similarly, if u is an element of A, by the reflexivity property of R, u R u, so u is an element of Ru, so u is an element of U Rx. So we have that A is a subset of U Rx.
We can then conclude that A = U
Next, show that the equivalence classes are pairwise disjoint
I will prove this with an indirect argument. If the intersection of Rx and Ry is not the empty set, then there is an element u of A such that u R x and u R y. By the symmetry and transitivity properties of R, this implies that x R y. Let z be an element of Rx. Then z R x and thus z R y by transitivity. Therefore z is an element of Ry. So Rx is a subset of Ry. Similarly, it can be proven that Ry is a subset of Rx, by considering an element w of Ry. Therefore Rx = Ry. Therefore, if the intersection of Rx and Ry is not the empty set, then the two sets are equal.
We can then conclude that the equivalence classes are pairwise disjoint.
It can then be concluded that the equivalence classes under R form a partition of A.
A note on notation: U Rx is the union of all Rx, and x R y means that x is related to y under R.