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.

### Mathematics Hothouse shares:

### Like this:

Like Loading...