GATE CS 2016 Set 2 Q26 — Sets, Relations and Functions

Let the binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ be defined as:

$$(a, b) R (c, d) \iff a \leq c \text{ or } b \leq d$$

1. Checking Proposition $P$ (Reflexivity)

For $R$ to be reflexive, every element $(a, b) \in \mathbb{N} \times \mathbb{N}$ must be related to itself, i.e., $(a, b) R (a, b)$ must hold.

$$(a, b) R (a, b) \iff a \leq a \text{ or } b \leq b$$

Since $a \leq a$ is always true for any $a \in \mathbb{N}$, the disjunction is always true. Thus, $R$ is reflexive. Proposition $P$ is true.

2. Checking Proposition $Q$ (Transitivity)

For $R$ to be transitive, if $(a, b) R (c, d)$ and $(c, d) R (e, f)$, then $(a, b) R (e, f)$ must hold.

Let us test this with a counterexample. Let:

• $(a, b) = (2, 2)$
• $(c, d) = (3, 1)$
• $(e, f) = (1, 1)$

Now we check the relations:

1. Does $(2, 2) R (3, 1)$ hold?
   Yes, because $2 \leq 3$ (the first condition is satisfied).
2. Does $(3, 1) R (1, 1)$ hold?
   Yes, because $1 \leq 1$ (the second condition is satisfied).
3. Does $(2, 2) R (1, 1)$ hold?
   No, because neither $2 \leq 1$ nor $2 \leq 1$ is true.

Since $(2, 2) R (3, 1)$ and $(3, 1) R (1, 1)$ but $(2, 2) \not R (1, 1)$, the relation $R$ is not transitive. Proposition $Q$ is false.

Thus, $P$ is true and $Q$ is false.