Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: December 2015

Let S={1, 2, 3, 4, 5} and A=S×S. Define the following relation R on A: (a,b) R(c,d) if and only if ad=bc show that R is an equivalence relation and compute A/R.

Lets S={1,2,3,4,5}, A=SxS

R=(a,b)R(c,d) if ad=bc

Let (a,b) R (a,b) ∴ ab=ba

This expression is true, hence (a,b) R (a,b)

∴ Given relation Is reflexive. It (a, b) R (c, d) ∴ ad =bc ...(i)

Then check for (c, d) R (a, b) ∴ cb=da

Above two expression are similar

∴ If (a, b) R (c, d) then (c, d) R (a, b)

∴ The given relation is symmetric

Let (a, b) R (c, d) and (c, d) R (e, f)

(a, b) R (c, d) ∴ ad =bc

(c, d) R (e, f) ∴ cf=ed

Check for (a, b) R (e, f)

∴ (a, b) R (e, f)

Hence R is Transitive. Thus R is an equivalence relation.

⇒ A / R

[1]= {1, 2} = [2] [3]={3, 4}=[4].

Hence, A/R= {[1], [3]}.