The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
1.3k 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
asked in Set Theory & Algebra by Boss (18.1k points)
edited by | 1.3k views
0
Just additional information -->

For getting quick answer solve it using binary relation on set {a,b,c}.

5 Answers

+14 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.
answered by Active (3.3k points)
edited by
+1
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...
0
yes @ muthu i have same doubt also
+16 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.

answered by Active (2.1k points)
edited by
+1

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

+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

answered by Loyal (6.5k points)
–1 vote
Ans: C
answered by Loyal (7.2k 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 ;)
–2 votes
R={(1,1)}
S={(2,2)}

R ∩ S= phi (irreflexive)

so how is intersection equivalence?

it should be none of these?
answered 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.


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

38,174 questions
45,676 answers
132,605 comments
49,562 users