42 ~ Theory ofComputer Science
EXAMPLE 2.5
We can define an equivalence relation R on any set S by defining aRb if
a =b. (Obviously, a =a for every a. So, R is reflexive. If a =b then b =a.
So R is symmetric. Also, if a = band b =c, then a =c. So R is transitive.)
EXAMPLE 2.6
Define a relation R on the set of all persons in New Delhi by aRb if the persons
a and b have the same date of birth. Then R is an equivalence relation.
Let us study this example more carefully. Corresponding to any day of the
year (say, 4th February), we can associate the set of all persons born on that
day. In this way the ~et of all persons in New Delhi can be partitioned into 366
subsets. In each of the 366 subsets, any two elements are related. This leads to
one more property of equivalence relations.
DefInition 2.4 Let R be an equivalence relation on a set S. Let a E S. Then
C G is defined as
{b E S IaRb}
The C a is called an equivalence class containing a. In general, th6C a ' s are
called equivalence classes.
EXAMPLE 2.7
For the congruence modulo 3 relation on {I, 2, ..., 7},
C 2 = {2, 5}, C j = {l, 4, 7}, C 3 = {3, 6}
For the equivalence relation 'having the same birth day' (discussed in Example
2.6), the set of persons born on 4th February is an equivalence class, and the
number of equivalence classes is 366. Also, we may note that the union of all
the 366 equivalence classes is the set of all persons in Delhi. This is true for
any equivalence relation because of the following theorem.
Theorem 2.1 Any equivalence relation R on a set S partitions S into disjoint
equivalence classes.
Proof Let U C a denote the union of distinct equivalence classes. We have to
prove that: aES
(i) S = U CO'
aES
(ii) C" Ii C h = 0 if C" and C h are different, i.e. C" ;f. C/ r
Let 5 E S. Then 5 E C, (since sRs, R being reflexive). But C\ \;;; U C(/'
aES
So S \;;; U Ca' By definition of C", C a \;;; S for every a in S. So U C a \;;; S.
"ES
aES
Thus we have proved (i).
Before proving (ii), we may note the following:
if aRb
(2.1)