GATE CS 2004 Q24 — Sets, Relations and Functions

Let the domain set be $A = \{0, 1, 2\}$.

The given relation is defined as:
$S = \{(x, y) \mid y = x + 1 \text{ and } x, y \in A\}$

Listing the elements of $S$ explicitly:
$S = \{(0, 1), (1, 2)\}$

To find the reflexive transitive closure of $S$ (denoted as $S^*$), we perform two steps:

1. Transitive Closure ($S^+$):
   Since $(0, 1) \in S$ and $(1, 2) \in S$, by transitivity, $(0, 2)$ must be in $S^+$.
   $S^+ = \{(0, 1), (1, 2), (0, 2)\}$
2. Reflexive Transitive Closure ($S^*$):
   We add the reflexive pairs $(x, x)$ for all $x \in A$ to the transitive closure:
   $S^* = S^+ \cup \{(0, 0), (1, 1), (2, 2)\}$
   $S^* = \{(0, 0), (1, 1), (2, 2), (0, 1), (1, 2), (0, 2)\}$

Now, let's evaluate the given options for $x, y \in \{0, 1, 2\}$:

• Option A: $\{ (x, y) \mid y > x \} = \{(0, 1), (0, 2), (1, 2)\}$ (This is only the transitive closure $S^+$).
• Option B: $\{ (x, y) \mid y \geq x \} = \{(0, 0), (1, 1), (2, 2), (0, 1), (0, 2), (1, 2)\}$ (This matches $S^*$ exactly).
• Option C: $\{ (x, y) \mid y < x \} = \{(1, 0), (2, 0), (2, 1)\}$.
• Option D: $\{ (x, y) \mid y \leq x \} = \{(0, 0), (1, 1), (2, 2), (1, 0), (2, 0), (2, 1)\}$.

Thus, the reflexive transitive closure of $S$ is represented by the relation $y \geq x$.