GATE CS 2001 Q1.2 — Sets, Relations and Functions

To determine which relations are equivalence relations, we test each for reflexivity, symmetry, and transitivity.

1. Relation $R_1$: $a + b$ is even over $\mathbb{Z}$
   • Reflexive: For any $a \in \mathbb{Z}$, $a + a = 2a$, which is always even. Thus, $(a, a) \in R_1$.
   • Symmetric: If $a + b$ is even, then $b + a = a + b$ is also even. Thus, if $(a, b) \in R_1$, then $(b, a) \in R_1$.
   • Transitive: If $a + b$ is even and $b + c$ is even, then $a$ and $b$ have the same parity (both even or both odd), and $b$ and $c$ have the same parity. Consequently, $a$ and $c$ must have the same parity, making $a + c$ even. Thus, $(a, c) \in R_1$.
   Since $R_1$ satisfies all three properties, $R_1$ is an equivalence relation.


2. Relation $R_2$: $a + b$ is odd over $\mathbb{Z}$
   • Reflexive: For any $a \in \mathbb{Z}$, $a + a = 2a$, which is always even (never odd). Thus, $(a, a) \notin R_2$.
   Since it is not reflexive, $R_2$ is not an equivalence relation.


3. Relation $R_3$: $a \cdot b > 0$ over non-zero rationals $\mathbb{Q}^*$
   • Reflexive: For any $a \in \mathbb{Q}^*$, $a \cdot a = a^2 > 0$ (since $a \neq 0$). Thus, $(a, a) \in R_3$.
   • Symmetric: If $a \cdot b > 0$, then $b \cdot a = a \cdot b > 0$. Thus, $(b, a) \in R_3$.
   • Transitive: If $a \cdot b > 0$ and $b \cdot c > 0$, then $a$ and $b$ have the same sign, and $b$ and $c$ have the same sign. Therefore, $a$ and $c$ must have the same sign, which implies $a \cdot c > 0$. Thus, $(a, c) \in R_3$.
   Since $R_3$ satisfies all three properties, $R_3$ is an equivalence relation.


4. Relation $R_4$: $|a - b| \le 2$ over $\mathbb{N}$
   • Transitive: Consider $a = 1$, $b = 3$, and $c = 5$ in $\mathbb{N}$:
     • $|1 - 3| = 2 \le 2 \implies (1, 3) \in R_4$
     • $|3 - 5| = 2 \le 2 \implies (3, 5) \in R_4$
     • But $|1 - 5| = 4 > 2 \implies (1, 5) \notin R_4$
   Since transitivity fails, $R_4$ is not an equivalence relation.

Thus, $R_1$ and $R_3$ are equivalence relations, while $R_2$ and $R_4$ are not.