Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE? A. R union S and R intersect S are both equivalence relations B. R union S is an equivalence relation C. R intersect S is an equivalence relation D. Neither R union S nor R intersect S are equivalence relations
GATE 2005 · Discrete Mathematics · Relations · medium
Answer: C. R intersect S is an equivalence relation
- Verify R intersect S is an equivalence relation: Reflexive: since aRa and aSa both hold, a(R inter S)a. Symmetric: if a(R inter S)b then aRb and aSb, so bRa and bSa (by symmetry of R,S), hence b(R inter S)a. Transitive: if a(R inter S)b and b(R inter S)c then aRb,bRc and aSb,bSc, so aRc and aSc (transitivity of R,S), hence a(R inter S)c.
- Show R union S can fail transitivity: Counterexample: A = {1,2,3}, R = {(1,1),(2,2),(3,3),(1,2),(2,1)}, S = {(1,1),(2,2),(3,3),(2,3),(3,2)}. Then (1,2) in R union S and (2,3) in R union S, but (1,3) is in neither R nor S, so R union S is not transitive.