edited by
9,040 views
26 votes
26 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
edited by

4 Answers

Best answer
27 votes
27 votes
$R\cup S$ 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 \cup S$ will contain, $(a, b)$ and $(b, c)$ but not $(a, c)$ and hence, not transitive.

Correct Answer: $C$.
edited by
28 votes
28 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.

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

edited by
1 votes
1 votes

 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

–2 votes
–2 votes
R={(1,1)}
S={(2,2)}

R ∩ S= phi (irreflexive)

so how is intersection equivalence?

it should be none of these?
Answer:

Related questions

36 votes
36 votes
6 answers
1
Kathleen asked Sep 22, 2014
24,492 views
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be:$O(n)$$O(n \log n)$$O \left( n^{\frac{3}{2}} \right)...
24 votes
24 votes
3 answers
4
gatecse asked Sep 21, 2014
7,065 views
The set \(\{1, 2, 4, 7, 8, 11, 13, 14\}\) is a group under multiplication modulo $15$. The inverses of $4$ and $7$ are respectively:$3$ and $13$$2$ and $11$$4$ and $13$$8...