GATE CS 2015 Set 2 Q16 — Sets, Relations and Functions

Let the relation $R$ be defined on the set of positive integers $\mathbb{Z}^+$ as:

We analyze the properties of $R$ as follows:

1. Reflexivity: For any $a \in \mathbb{Z}^+$, the condition $a \neq a$ is always false. Thus, $aRa$ does not hold for any element.
   Therefore, $R$ is not reflexive.
2. Symmetry: Suppose $aRb$ holds. This means $a \neq b$ and $\gcd(a, b) > 1$. Since inequality and greatest common divisor are symmetric operations: $$b \neq a \quad \text{and} \quad \gcd(b, a) = \gcd(a, b) > 1$$ This implies $bRa$ holds.
   Therefore, $R$ is symmetric.
3. Transitivity: Suppose $aRb$ and $bRc$ hold. For $R$ to be transitive, $aRc$ must also hold. Let us test this with a counterexample:
   • Let $a = 2$, $b = 6$, and $c = 3$.
   • $2R6$ is true because $2 \neq 6$ and $\gcd(2, 6) = 2 > 1$.
   • $6R3$ is true because $6 \neq 3$ and $\gcd(6, 3) = 3 > 1$.
   • However, $2R3$ is false because $\gcd(2, 3) = 1$.
   Therefore, $R$ is not transitive.

Hence, $R$ is symmetric but not reflexive and not transitive, which corresponds to Option D.