The
proof 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 R
x (x is an
element of A) is
equal to A:
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 R
x.
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.