GATE CS 2021 Set 1 Q43 — Sets, Relations and Functions

A relation $S$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.

We are given that a relation $S$ is circular if:

Analyzing Option C: Reflexive and Circular $\implies$ Equivalence

Let $S$ be a relation that is both reflexive and circular.

1. Symmetry:

   We need to show that if $aSb$, then $bSa$.

   • Assume $aSb$.
   • Since $S$ is reflexive, we know $bSb$ holds.
   • Applying the circular property to $aSb$ and $bSb$, we get $bSa$.

   Thus, $S$ is symmetric.

2. Transitivity:

   We need to show that if $aSb$ and $bSc$, then $aSc$.

   • Assume $aSb$ and $bSc$.
   • Applying the circular property, we get $cSa$.
   • Since we already proved $S$ is symmetric, $cSa \implies aSc$.

   Thus, $S$ is transitive.

Since $S$ is reflexive, symmetric, and transitive, it is an equivalence relation. Therefore, Option C is correct.

Eliminating Other Options

• Option A: A reflexive and symmetric relation is not necessarily transitive.
  Counterexample: On $A = \{1, 2, 3\}$, let $S = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$. $S$ is reflexive and symmetric, but not transitive because $(1,2) \in S$ and $(2,3) \in S$ but $(1,3) \notin S$.
• Option B & D: For any non-empty set $A$, the empty relation $S = \emptyset$ is vacuously symmetric, transitive, and circular. However, it is not reflexive, so it cannot be an equivalence relation.