Question: Discrete Structures: Equivalence Relation
1

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.

 modified 2.2 years ago  • written 2.3 years ago by Krrish • 190

 written 2.3 years ago by Krrish • 190
2

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

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, 2} =  ={3, 4}=.

Hence, A/R= {, }.

 written 2.2 years ago by Krrish • 190