Discrete Mathematics previous year-GATE 2025 Equivalence relation Let R and S be any two equivalence

Discrete Mathematics previous year-GATE 2025 Equivalence relation Let R and S be any two equivalence

In the context of GATE (Graduate Aptitude Test in Engineering) examinations, understanding the properties of equivalence relations is crucial. An equivalence relation on a set $A$ is a relation that is reflexive, symmetric, and transitive.

Key Properties of Equivalence Relations:

1. Reflexivity: Every element is related to itself. For all $a\in A$, $(a,a)\in R$.

2. Symmetry: If an element $a$ is related to an element $b$, then $b$ is also related to $a$. For all $a,b\in A$, if $(a,b)\in R$, then $(b,a)\in R$.

3. Transitivity: If an element $a$ is related to $b$, and $b$ is related to $c$, then $a$ is related to $c$. For all $a,b,c\in A$, if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Intersection of Equivalence Relations:

When considering two equivalence relations $R$ and $S$ on a set $A$, their intersection $R\cap S$ is also an equivalence relation. This is because the intersection of two reflexive, symmetric, and transitive relations retains these properties.

Union of Equivalence Relations:

However, the union $R\cup S$ of two equivalence relations is not necessarily an equivalence relation. While the union of two reflexive and symmetric relations remains reflexive and symmetric, it may fail to be transitive.

Example Illustrating Non-Transitivity:

Consider a set $A=\{1,2,3\}$ with two equivalence relations $R$ and $S$:

• $R=\{(1,2),(2,1)\}$

• $S=\{(2,3),(3,2)\}$

Their union is:

$R\cup S=\{(1,2),(2,1),(2,3),(3,2)\}$

In this union, we have $(1,2)\in R\cup S$ and $(2,3)\in R\cup S$, but $(1,3)\notin R\cup S$. This lack of transitivity means $R\cup S$ is not an equivalence relation.

GATE Examination Insight:

A relevant GATE question from 2005 asked:

*”Let $R$ and $S$ be any two equivalence relations on a non-empty set $A$. Which one of the following statements is TRUE?

A. $R\cup S$ and $R\cap S$ are both equivalence relations.

B. $R\cup S$ is an equivalence relation.

C. $R\cap S$ is an equivalence relation.

D. Neither $R\cup S$ nor $R\cap S$ is an equivalence relation.”*

The correct answer is C: $R\cap S$ is an equivalence relation.

Conclusion:

Understanding the behavior of unions and intersections of equivalence relations is essential for discrete mathematics and examinations like GATE. While intersections of equivalence relations remain equivalence relations, unions do not necessarily preserve the transitivity property required for equivalence relations.

Discrete Mathematics previous year-GATE 2025 Equivalence relation Let R and S be any two equivalence