GATE CSE 1998 | Question: 1.7

Question

Let $R_1$ and $R_2$ be two equivalence relations on a set. Consider the following assertions:

1. $R_1 \cup R_2$ is an equivalence relation
2. $R_1 \cap R_2$ is an equivalence relation

Which of the following is correct?

• A. Both assertions are true
• B. Assertions (i) is true but assertions (ii) is not true
• C. Assertions (ii) is true but assertions (i) is not true
• D. Neither (i) nor (ii) is true

Comments

Question : 

Let R1 and R2 be two equivalence relations on a set. Consider the following assertions:
i. R 1 ∪ R 2 is an equivalence relation
ii. R 1 ∩ R 2 is an equivalence relation

 It means they can’t be null because in the worst case it is satisfying reflexive.

E.g; If R contains {a,b,c} then R1 and R2 both contains at least {(a,a),(b,b),(c,c)}.  So it is symmetric and transitive too, consequently an equivalence relation.

---

R1 U R2 is reflexive and symmetric but may not be transitive. We can prove it-- suppose (a,b)∈R1 U R2

then (a,b)∈R1 or (a,b)∈R2.

Similarly suppose (b,c)∈R1 U R2

then (b,c)∈R1 or (b,c)∈R2.

So it is possible that (a,b)∈R1 and (b,c)∈R2.

So a and c are not related and (a,c) does not belongs to R1 U R2 . So it is not transitive.

Similarly we can prove that R1∩R2 is an equivalence relation

---

Similar Ques https://gateoverflow.in/80583/gate-cse-1987-question-2d

Answer 1

Answer: $C$

$R_1$ intersection $R_2$ is equivalence relation..
$R_1$ union $R_2$ is not equivalence relation because transitivity needn't hold. For example, $(a, b)$ can be in $R_1$ and $(b, c)$ be in $R_2$ and $(a, c)$ not in either $R_1$ or $R_2.$

Comments

But empty set does not satisfy reflexive property only satisfy transitive and symmetric

---

by default we dont consider the base set as empty unles mentioned by author lor examinor

---

@yankur9 That case can't happen. For two equivalence relations on the same set, the intersection is never empty. Both R₁ and R₂ are reflexive, so both contain (a,a) for every element a.

Answer 2

$R1$ and $R2$ both are equivalence relation so $R1∩R2$ is also an equivalence relation because $\cap$ include only those pairs which are in both $R1$ and $ R2$.
Assertions (ii) is true 

$R1∪R2$ is NOT an equivalence relation 
see counter example over $(a,b)$ : 
$R1=\{(a,a),(b,b),(a,b),(b,a)\}$ is equivalence relation
$R2=\{(a,a),(b,b),(c,b),(b,c)\}$ is equivalence relation
$R1∪R2=\{(a,a),(b,b),(a,b),(b,a),(c,b),(b,c)\}$ is NOT equivalence relation because transitive pair $(a,c)$ isn't include in it .
assertions (i) is not true

Ans is C
 

Comments

when R2 is defined over (a,b) how have you taken c ?

---

Let relation is defined on set s={a,b,c}

Let R1={(a,a),(b,b),(c,c),(a,b),(b,a)}

And let. R2={(a,a),(b,b),(c,c),(b,c),(c,b)}

Here both are equivalence relation

But R1UR2={(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,a)}

Now here it can be seen that (a,c) is not pre sent in R1UR2 as it should be to make it transitive since (a,b) and (b,c) is present.

---

R2 must have (c,c) to be equivalence relation

Answer 3

learn this property and solve with in second

SHORT TRICK

Comments

thanks where did you learned these ? the go classes discrete maths course did not cover these parts.

---

Bhai Go Classes has covered this thing very well, i already studied above diagram from them.

Answer 4

It say that two equivalence R1 and R2 relation on a same set.

Let relation is defined on set S={1,2,3}

Counter Eaxmple for Assertion i

 R1={(1,1),(2,2),(3,3),(1,2),(2,1)}

 R2={(1,1),(2,2),(3,3),(2,3),(3,2)}

Here both are equivalence relation

 R1 U R2={(1,1),(2,2),(3,3),(2,3),(3,2),(1,2),(2,1),(3,1)}

(3,1) come for transitivity.but there (1,3) is not present.Therefore ,we can say that it violated Symmetric property so it is not Equivalence Relation.
But in every case the Assertion ii is satisfied equivalence relation.

Then answer is Option (C).

Answer 5

I felt like adding a little more rigour by proving the property that the intersection of two equivalence relations is an equivalence relation. Assume $R_1\bigcap R_2$ is not an equivalence relation for contradiction's sake. In that case there exists an x such that x$R_1$x exists or x$R_2$x exists but not x( $R_1\bigcap R_2$ )x. But we know that $R_1$ and $R_2$ are equivalence relations on the same set. So there should be a reflexive pair of x in both the relations we have been presented with.

Thus the contradiction is our initial assumption.

Answer 6

We can also solve it as:

If two binary equivalence relation are intersected then we get common pairs that thenselves follow equivalence properties. Like say from A and B if something is common then definitely it will follow equivalent properties for both A and B as they are common to both.

But if there happens a union then there are chances of having pairs that don't follow transitivity. Because there are pairs being added, we only know they follow properties from "their" sets but not from opposite sets.