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:
Theorem I:
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):
Assume: .
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,
Theorem II:
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.
Furthermore,
.
Thus, the equivalence classes under are the same as the cells in the partition P.
More later,
Nalin Pithwa.