A binary relation R on N x N is defined as follows: (a,b) R (c,d) if a <= c or b <= d. Consider the following propositions: P: R is reflexive. Q: R is transitive. Which one of the following statements is TRUE? A. Both P and Q are true. B. P is true and Q is false. C. P is false and Q is true. D. Both P and Q are false.

GATE 2016 · Discrete Mathematics · Relations · medium

Answer: P (reflexive) is TRUE, Q (transitive) is FALSE. Answer: B. P is true and Q is false.

1. Verify reflexivity (P): For any (a,b) in N x N: a <= a is always true (by reflexivity of <=). So the condition 'a <= a OR b <= b' is always satisfied. P is TRUE: R is reflexive.
2. Find counterexample to transitivity (Q): Take (a,b)=(3,2), (c,d)=(1,3), (e,f)=(2,1). Check (3,2)R(1,3): 3<=1? No. 2<=3? Yes. So (3,2)R(1,3). Check (1,3)R(2,1): 1<=2? Yes. So (1,3)R(2,1). Check (3,2)R(2,1): 3<=2? No. 2<=1? No. NOT related! Transitivity FAILS. Q is FALSE.