Let R and S be any two equivalence relations on a non-empty set A. Which one…

Correct statement: R ∩ S is an equivalence relation.

Proof:

• Reflexive: For every a in A, (a,a) belongs to both R and S because both relations are reflexive; hence (a,a) is in R ∩ S.

• Symmetric: If (a,b) is in R ∩ S, then (a,b) is in both R and S. Since both are symmetric, (b,a) is in both R and S, so (b,a) is in R ∩ S.

• Transitive: If (a,b) and (b,c) are in R ∩ S, then they are in both R and S. Transitivity of R and of S gives (a,c) in both, so (a,c) is in R ∩ S.

Thus R ∩ S is reflexive, symmetric, and transitive, so it is an equivalence relation.

Counterexample showing R ∪ S need not be an equivalence relation:

• Let A = {1,2,3}. Define R with equivalence classes {1,2} and {3}. Then R contains (1,2) and (2,1) and all diagonal pairs.

• Define S with equivalence classes {2,3} and {1}. Then S contains (2,3) and (3,2) and all diagonal pairs.

• Then R ∪ S contains (1,2) and (2,3) but does not contain (1,3), so transitivity fails and R ∪ S is not an equivalence relation.

Conclusion: R ∩ S is always an equivalence relation; R ∪ S need not be. Therefore the true statement is that R ∩ S is an equivalence relation.