Answer to Question #171798 in Discrete Mathematics for AMIT RAWAT

Question

Let A = {1, 2, 3, 4, 5, 6, 7} and

R = {(x, y) | x –y is divisible by 3}

Show that R is an equivalence relation. Draw the graph of R.

Answer 1

Solution:

4-1=3 is divisible by 3.

5-2=3 is divisible by 3.

6-3=3 is divisible by 3.

7-4=3 is divisible by 3.

And vice versa.

Also, 1-1=0 is divisible by 3.

2-2=0 is divisible by 3.

and so on

$R=\{(4,1),(5,2),(6,3),(7,4),(1,4),(2,5),(3,6),(4,7), \\ (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)\}$

Reflexive:

Clearly, $\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)\}$

So, $\{(a,a)\in R, \forall a\in A\}$

Hence, it is reflexive.

Symmetric:

Clearly, $\{(1,4),(4,1),(2,5),(5,2),(3,6),(6,3),(4,7),(7,4)\}$

So, $\{(a,b)\in R \Rightarrow (b,a)\in R, \forall a\in A\}$

Hence, it is symmetric.

Transitive:

Clearly,

$\{(1,4),(4,1),(1,1),(2,5),(5,2),(2,2),(3,6),(6,3),(3,3),(4,7),(7,4),(4,4)\}$

So, $\{(a,b)\in R, (b,c)\in R\Rightarrow (a,c)\in R,\forall a\in A\}$

Hence, it is transitive.

Thus, the given relation is an equivalence relation.

Graph of R: