Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: Dec 2013

Let a, b € I where I be the set of Integers.

1. R is reflexive:

   Since a-a=0=0.m, Ɏ a € I, aRa.

   Hence, R is reflexive.

2. R is symmetric:

   Suppose aRb

   a-b is divisible by m.

   a-b = k.m for some integer k,

   b-a = (-k).m for some integer –k.

   bRa

   Hence R is symmetric.

3. R is transitive:

   Suppose aRb and bRc

   $a-b=k_1m$ and $b-c=k_2m$ for some integers $k_1$ and $k_2$.

   $(a-b)+(b-c)=( k_1+k_2)m$

   $a-c=(k_1+k_2)m$ for the integer $k_1 + k_2$.

   aRc

   Hence R is transitive.

   This proves that R is an equivalence relation on I.