The Gateway to Computer Science Excellence
+16 votes

Let $R$ and $S$ be any two equivalence relations on a non-empty set $A$. Which one of the following statements is TRUE?

  1. $R$ $∪$ $S$, $R$ $∩$ $S$ are both equivalence relations
  2. $R$ $∪$ $S$ is an equivalence relation
  3. $R$ $∩$ $S$ is an equivalence relation
  4. Neither $R$ $∪$ $S$ nor $R$ $∩$ $S$ are equivalence relations
in Set Theory & Algebra by Boss (17.5k points)
edited by | 2.2k views
Just additional information -->

For getting quick answer solve it using binary relation on set {a,b,c}.
To prove $R \cap S$ is always an equivalence relation, start with assuming it is not and arrive at a contradiction.

That is, show that if $R$ and $S$ are reflexive, symmetric, and transitive; then $R \cap S$  must be reflexive, symmetric and transitive as well.

5 Answers

+18 votes
Best answer
$RUS$ might not be transitive. Say $(a,b)$ be present in $R$ and $(b,c)$ be present in $S$ and $(a, c)$ not present in either, $R U S$ will contain, $(a, b)$ and $(b, c)$ but not $(a, c)$ and hence not transitive.

option c.
by Active (3.3k points)
edited by
Lets say R= {a b } and S = { c d }

then, RnS = { } and empty set is not reflexive .. so, how RnS be equivalence..

Please clear my doubts...
yes @ muthu i have same doubt also
@muthu @Ramij   In question R and S itself are equivalence relation but in your example, neither R is equivalence nor S.
+21 votes

R ∩ S is an equivalence relation, because in R ∩ S, we have all pairs of type (a,a) definitely, so R ∩ S is reflexive.

Moreover, if there is any pair (a,b) in R ∩ S, then that must have been present in both R and S, and thus (b,a) must have also been present in both R and S, and so in R ∩ S, so R ∩ S is also symmetric.

We can argue similarly for transitivity. If there are pairs (a,b) and (b,c) in R ∩ S, then they both must have been present in R as well as S, and so (a,c) would have also been present in both R and S, and so (a,c) must also be present in R ∩ S, hence R ∩ S is transitive also.

Now let us see R ∪ S. It is actually need not be equivalence. The intuition is we may violate the transitivity property because if some (a,b) comes from R, and some (b,c) comes from S, then we will not have (a,c) in R ∪ S (assuming we don't have (a,c) in R or S.

So let us construct a counter example for R∪S to be equivalence statement. Let A = {1,2,3}

Now let R = {(1,1),(2,2),(3,3),(1,2),(2,1)}, and let S = {(1,1),(2,2),(3,3),(2,3),(3,2)}. Now R ∪ S = {(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)}. This violates transitivity as we have (1,2) and (2,3), but not (1,3). 
So option (C) is correct.

by Active (1.9k points)
edited by

Copy paste is not supposed to be an impressive task at that level richa.

Thanks for providing a clear solution
+1 vote

 If R and S are equivalence relation then R ∩ S is always an equivalence relation.

But R ∪ S may or may not be an equivalence relation because it might not be transitive always.

So, the correct answer is (C) R ∩ S is an equivalence relation

by Loyal (8k points)
0 votes
Ans: C
by Loyal (7.3k points)
please write answers only if you have something different to share from other's, otherwise it is irrelevant!!
yeah...!! good catch :p ;)
–2 votes

R ∩ S= phi (irreflexive)

so how is intersection equivalence?

it should be none of these?
by Active (3.2k points)
Here it is said that R and S are both equivalence relations.But in your example none of them is an equivalence relation.
In ur examples, neither R nor S is an equivalence Relation..

according to you all elements of A should be added to it?
yes, R & S both should be reflexive first to be equivalence relations.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,395 answers
105,446 users