2.2k views

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

edited | 2.2k views
0

For getting quick answer solve it using binary relation on set {a,b,c}.
0
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.

$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
+3
Lets say R= {a b } and S = { c d }

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

+1
yes @ muthu i have same doubt also
+4
@muthu @Ramij   In question R and S itself are equivalence relation but in your example, neither R is equivalence nor S.

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
+3

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

http://www.cse.iitd.ernet.in/~mittal/gate/gate_math_2005.html

0
Thanks for providing a clear solution
0
Equivalence?
+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)
Ans: C
by Loyal (7.3k points)
+1
please write answers only if you have something different to share from other's, otherwise it is irrelevant!!
0
yeah...!! good catch :p ;)
R={(1,1)}
S={(2,2)}

R ∩ S= phi (irreflexive)

so how is intersection equivalence?

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

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