Page 14 - DMTH403_ABSTRACT_ALGEBRA

Unit 1: Generating Sets

Note that Notes

(i) [1] and [6] are not disjoint. In fact, [1] = [6]. Similarly, [2] = [7], and so on.
(ii) N = [I] U [2] U [3] U [4] U [5], and the sets on the right hand side arc mutually disjoint.
We will prove these observations in general in the following theorem.
Theorem 1: Let R be an equivalence relation on a set S. For a  S, let [a] denote the equivalence
class of a. Then
(a) a [a],
(b) b  [a]  [a] = [b],

(c) S =  [a]
a S
(d) if a, b  S, then [a]  [b] =  or [a] = [b].

Proof: (a) Since R is an equivalence relation, it is reflexive.
 aRa V a  S.  a  [a].
(b) Firstly, assume that b " [a]. We will show that [a]  [b] and [b]  [a]. For this, let x  [a].
Then xRa.
We also know that aRb. Thus, by transitivity of R, we have xRb, i.e., x  [b].  [a]  [b]. We can
similarly show that [b]  [a].
 [a] = [b].

Conversely, assume that [a] = [b]. Then b  [b] = [a].  b  [a].

(c) Since [a]  S V a  S,  [a]  S .
a S
Conversely, let x  S. Then x  [x] by (a) above. [x] is one of the sets in the collection whose union

is  [a] .
a S

Hence, x   [a] . So, S   [a] .
a S a S
Thus, S   [a] and  [a]  S , proving (c).
a S a S
(d) Suppose [a]  [b]  . Let x  [a]  [b].
Then x  [a] and x  [b]

 [x] = [a] and [x] = [b], by (b) above.
 [a] = [b].
Note that, in Theorem 1, distinct sets on the right hand side of (c) are mutually disjoint because
of (d). Therefore, (c) expresses S as a union of mutually disjoint subsets of S; that is, we have a
partition of S into equivalence classes.

Let us look at some more examples of partitioning a set into equivalence classes.

LOVELY PROFESSIONAL UNIVERSITY 7