GATE CS 2005 Q42 — Sets, Relations and Functions

An equivalence relation must satisfy three properties: reflexivity, symmetry, and transitivity.

Let $R$ and $S$ be two equivalence relations on a non-empty set $A$. Let us analyze the properties of their intersection and union.

1. Intersection ($R \cap S$) is always an equivalence relation:

• Reflexivity: For any $a \in A$, since $R$ and $S$ are reflexive, $(a, a) \in R$ and $(a, a) \in S$. Therefore, $(a, a) \in R \cap S$.
• Symmetry: If $(a, b) \in R \cap S$, then $(a, b) \in R$ and $(a, b) \in S$. Since $R$ and $S$ are symmetric, $(b, a) \in R$ and $(b, a) \in S$. Thus, $(b, a) \in R \cap S$.
• Transitivity: If $(a, b) \in R \cap S$ and $(b, c) \in R \cap S$, then:
  • $(a, b) \in R$ and $(b, c) \in R \implies (a, c) \in R$ (since $R$ is transitive)
  • $(a, b) \in S$ and $(b, c) \in S \implies (a, c) \in S$ (since $S$ is transitive)
  Therefore, $(a, c) \in R \cap S$.

Since $R \cap S$ is reflexive, symmetric, and transitive, it is always an equivalence relation.

2. Union ($R \cup S$) is not necessarily an equivalence relation:

While $R \cup S$ is always reflexive and symmetric, it often fails to be transitive. Consider the following counterexample:

• Let $A = \{1, 2, 3\}$.
• Let $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ (equivalence classes: $\{1, 2\}, \{3\}$).
• Let $S = \{(1,1), (2,2), (3,3), (2,3), (3,2)\}$ (equivalence classes: $\{1\}, \{2, 3\}$).
• The union is $R \cup S = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$.

Here, $(1, 2) \in R \cup S$ and $(2, 3) \in R \cup S$, but $(1, 3) \notin R \cup S$. Thus, transitivity is violated, meaning $R \cup S$ is not an equivalence relation.

Therefore, only $R \cap S$ is guaranteed to be an equivalence relation.