GATE CS 1998 Q1.7 — Sets, Relations and Functions

To determine the validity of the assertions, let us analyze the properties of the intersection and union of two equivalence relations $R_1$ and $R_2$ defined on a set $A$.

Assertion (ii): $R_1 \cap R_2$ is an equivalence relation

An equivalence relation must be reflexive, symmetric, and transitive. Let us check these properties for $R_1 \cap R_2$:

• Reflexivity: Since $R_1$ and $R_2$ are equivalence relations, they are both reflexive. For any $a \in A$, $(a, a) \in R_1$ and $(a, a) \in R_2$. Therefore, $(a, a) \in R_1 \cap R_2$. Thus, $R_1 \cap R_2$ is reflexive.
• Symmetry: Let $(a, b) \in R_1 \cap R_2$. This means $(a, b) \in R_1$ and $(a, b) \in R_2$. Since both $R_1$ and $R_2$ are symmetric, we have $(b, a) \in R_1$ and $(b, a) \in R_2$. Thus, $(b, a) \in R_1 \cap R_2$. Thus, $R_1 \cap R_2$ is symmetric.
• Transitivity: Let $(a, b) \in R_1 \cap R_2$ and $(b, c) \in R_1 \cap R_2$.
  • From $(a, b), (b, c) \in R_1$, we get $(a, c) \in R_1$ (since $R_1$ is transitive).
  • From $(a, b), (b, c) \in R_2$, we get $(a, c) \in R_2$ (since $R_2$ is transitive).
  Therefore, $(a, c) \in R_1 \cap R_2$. Thus, $R_1 \cap R_2$ is transitive.

Since $R_1 \cap R_2$ satisfies all three properties, Assertion (ii) is always true.

Assertion (i): $R_1 \cup R_2$ is an equivalence relation

The union of two equivalence relations is not necessarily transitive. We can show this with a counterexample:

Let $A = \{1, 2, 3\}$.

• Let $R_1 = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ (equivalence relation with partition $\{\{1, 2\}, \{3\}\}$)
• Let $R_2 = \{(1,1), (2,2), (3,3), (2,3), (3,2)\}$ (equivalence relation with partition $\{\{1\}, \{2, 3\}\}$)

Now, their union is: $$R_1 \cup R_2 = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$$

In $R_1 \cup R_2$, we have $(1, 2) \in R_1 \cup R_2$ and $(2, 3) \in R_1 \cup R_2$, but $(1, 3) \notin R_1 \cup R_2$. Hence, transitivity fails, and $R_1 \cup R_2$ is not an equivalence relation. Thus, Assertion (i) is not true.

Therefore, Assertion (ii) is true but Assertion (i) is not true.