Suppose R is an equivalence relation on a set S. For each a in S, let [a] denote the set of elements of S to which a is related under R, that is,
We call [a] the equivalence class of a in S under R. The collection of all such equivalence classes is denoted by S/R, that is, . It is called the quotient set of S by R.
The fundamental property of an equivalence relation and its quotient set is contained in the following theorem:
Let R be an equivalence relation on a set S. Then, the quotient set S/R is a partition of S. Specifically,
(i) For each , we have .
(ii) if and only if .
(iii) If , then [a] and [b] are disjoint.
Proof of (i):
Since R is reflexive, for every and therefore .
Proof of (ii):
we want to show that . That is, we got to prove, (i) and (ii) .
Let ; then, . But, by hypothesis and so, by transitivity, . Accordingly, . Thus, .
To prove that , we observe that implies, by symmetry, that . Then, by a similar argument, we obtain . Consequently, .
Now, assume .
Then by part (i) of this proof that for each , we have . So, also, here ; hence, .
Proof of (iii):
Here, we prove the equivalent contrapositive of the statement (iii), that is:
If then .
if then there exists an element with . Hence, and . By symmetry, , and, by transitivity, . Consequently, by proof (ii), .
The converse of the above theorem is also true. That is,
Suppose is a partition of set S. Then, there is an equivalence relation on S such that the set of equivalence classes is the same as the partition .
Specifically, for , the equivalence in Theorem I is defined by if a and b belong to the same cell in P.
Thus, we see that there is a one-one correspondence between the equivalence relations on a set S and the partitions of S.
Proof of Theorem II:
Let , define if a and b belong to the same cell in P. We need to show that is reflexive, symmetric and transitive.
(i) Let . Since P is a partition there exists some in P such that . Hence, . Thus, is reflexive.
(ii) Symmetry follows from the fact that if , then .
(iii) Suppose and . Then, and . Therefore, . Since P is a partition, . Thus, and so . Thus, is transitive.
Accordingly, is an equivalence relation on S.
Thus, the equivalence classes under are the same as the cells in the partition P.