GATE CS 2000 Q2.5 — Sets, Relations and Functions

To determine the nature of the relation $R$ defined on the set of integers $\mathbb{Z}$ by $xRy \iff (x + y) \text{ is even}$, we check the three properties of an equivalence relation:

1. Reflexivity: For any $x \in \mathbb{Z}$, $x + x = 2x$, which is always even. Thus, $xRx$ is true for all $x \in \mathbb{Z}$.
2. Symmetry: If $xRy$, then $x + y$ is even. Since $x + y = y + x$, it follows that $y + x$ is also even, meaning $yRx$.
3. Transitivity: If $xRy$ and $yRz$, then both $x + y$ and $y + z$ are even.
   Since the sum of two even numbers is even: $$(x + y) + (y + z) = x + 2y + z \quad \text{is even}$$ Since $2y$ is always even, subtracting it from the even sum $(x + 2y + z)$ leaves an even number: $$x + z = (x + 2y + z) - 2y \quad \text{is even}$$ Thus, $xRz$.

Since $R$ is reflexive, symmetric, and transitive, it is an equivalence relation.

Equivalence Classes:

The equivalence class of an element $a \in \mathbb{Z}$ is defined as $[a] = \{x \in \mathbb{Z} \mid xRa\}$.

• If $a$ is even, then $x + a$ is even if and only if $x$ is also even. This gives the class of all even integers: $$[0] = \{\dots, -4, -2, 0, 2, 4, \dots\}$$
• If $a$ is odd, then $x + a$ is even if and only if $x$ is also odd. This gives the class of all odd integers: $$[1] = \{\dots, -3, -1, 1, 3, 5, \dots\}$$

These two disjoint classes partition the set of all integers $\mathbb{Z}$. Therefore, there are exactly $2$ equivalence classes (one for even integers and one for odd integers).