The collection of all equivalence classes of elements of S under an
equivalence relation R is denoted by S
R , i.e.,
S
R
a a S
=
∈
{[ ] :
}.
It is known as “quotient” set of S by R.
Ì Exam ple 0.1.11: Given a relation R is ‘circular’ if ( , )
a b R
∈ and
( , )
( , )
b c R
c a R
∈ ⇒
∈ . Show that a relation is reflexive and circular if and
only if it is reflexive, symmetric, and transitive.
Solu tion
Let the relation R be reflexive and circular. We shall prove that R is reflexive,
symmetric and transitive.
( , )
, ( , )
( , )
a b R b c R
c a R
∈
∈ ⇒
∈ , since R is cir cu lar and
( , )
a a R
∈ since R is reflex ive.
We have ( , )
, , )
( , )
c a R a a R
a c R
∈ (
∈ ⇒
∈ , since R is circular.
Thus shows ( , )
a c R
∈ and ( , )
c a R
∈ . Hence R is symmetric
( , )
, ( , )
( , )
,
a b R b c R
c a R
R
a c R
∈
∈ ⇒
∈
⇒
∈
since is circular
( , )
, since is symmetric
is transitive
R
R
⇒
It is given that R is reflexive.
Conversely, if R is reflexive, symmetric, and transitive then we show that
R is reflexive and circular.
( , )
, ( , )
( , )
,
a b R b c R
a c R
R
R
∈
∈ ⇒
∈
⇒
∈
since is transitive
( )
c,a
, since is symmetric
is circular
R
R
⇒
( , )
, ( , )
( , )
,
a c R c a R
a a R
R
R
∈
∈ ⇒
∈
⇒
since is transitive
is reflexive
Ì Exam ple 0.1.12: Show that the relation “congruence modulo m” over
the set of positive integers is an equivalence relation.
Solu tion
Assume that N = Set of all positive integers
and m = given positive integer.
For x y N x y
,
,
∈
≡ (mod m) if and only if x – y is divisible by m, i.e.
x y km
k z
− =
∈
,
.
for
10
Theory of Automata, Formal Languages and Computation