Let R be a reflexive and transitive relation on a set A. Define a new relation E on A as: E = {(a, b) | (a, b) in R and (b, a) in R}. a. Prove that E is an equivalence relation on A. b. Define a relation <= on the equivalence classes of E as [a] <= [b] if (a, b) in R. Prove that <= is a partial order on the equivalence classes.

GATE 1997 · Discrete Mathematics · Relations · medium

Answer: E is an equivalence relation on A; the induced <= on the equivalence classes A/E is a partial order.

1. Prove E is an equivalence relation: Reflexive: R is reflexive, so (a,a) in R and (a,a) in R, hence (a,a) in E. Symmetric: if (a,b) in E then (a,b) in R and (b,a) in R; swapping gives (b,a) in R and (a,b) in R, so (b,a) in E. Transitive: if (a,b) in E and (b,c) in E, then aRb, bRa, bRc, cRb. By transitivity of R: aRb and bRc gives aRc; cRb and bRa gives cRa. So (a,c) in E.
2. Prove <= on A/E is a partial order: Well-defined: if [a]=[a'] and [b]=[b'], then (a,a') in E so aRa', a'Ra; (b,b') in E so bRb', b'Rb. If aRb then a'Ra, aRb, bRb' gives a'Rb' by transitivity of R. So the definition is independent of representative. Reflexive: (a,a) in R so [a] <= [a]. Antisymmetric: [a] <= [b] and [b] <= [a] means aRb and bRa, so (a,b) in E, meaning [a]=[b]. Transitive: [a]<=[b] and [b]<=[c] means aRb and bRc, so aRc by transitivity of R, giving [a]<=[c].