Which of the relations on {0, 1, 2, 3} is an equivalence relation ?
2018
Which of the relations on {0, 1, 2, 3} is an equivalence relation ?
- A.
{ (0, 0) (0, 2) (2, 0) (2, 2) (2, 3) (3, 2) (3, 3) }
- B.
{ (0, 0) (1, 1) (2, 2) (3, 3) }
- C.
{ (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) }
- D.
{ (0, 0) (0, 2) (2, 3) (1, 1) (2, 2) }
Attempted by 262 students.
Show answer & explanation
Correct answer: B
Answer: The relation { (0, 0) (1, 1) (2, 2) (3, 3) } is an equivalence relation on {0,1,2,3}.
Reflexive: The relation contains (x,x) for every x in {0,1,2,3}, so it is reflexive.
Symmetric: If (a,b) is in the relation then a=b, hence (b,a)=(a,a) is also in the relation. Therefore it is symmetric.
Transitive: If (a,b) and (b,c) are in the relation then a=b and b=c, so a=c and (a,c)=(a,a) is in the relation. Thus it is transitive.
Why the other given relations are not equivalence relations:
{ (0, 0) (0, 2) (2, 0) (2, 2) (2, 3) (3, 2) (3, 3) }: Not reflexive because (1,1) is missing.
{ (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) }: Not reflexive (missing (2,2) and (3,3)) and not symmetric because (1,2) appears but (2,1) does not.
{ (0, 0) (0, 2) (2, 3) (1, 1) (2, 2) }: Not reflexive because (3,3) is missing; not symmetric because (0,2) is present but (2,0) is not; and not transitive because (0,2) and (2,3) are present but (0,3) is not.
A video solution is available for this question — log in and enroll to watch it.