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** R_{x}. Therefore, y belongs to some R_{z}, so y R z, and thus y is an element of A, because R only relates elements of A. We then have that **U** R_{x} 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 R_{u}, so u is an element of **U** R_{x}. So we have that A is a subset of **U** R_{x}.

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 R_{x} and R_{y} 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 R_{x}. Then z R x and thus z R y by transitivity. Therefore z is an element of R_{y}. So R_{x} is a subset of R_{y}. Similarly, it can be proven that R_{y} is a subset of R_{x}, by considering an element w of R_{y}. Therefore R_{x} = R_{y}. Therefore, if the intersection of R_{x} and R_{y} 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** R_{x} is the union of all R_{x}, and x R y means that x is related to y under R.