Project ForgeDiscrete Mathematics
Set Theory & Abstract Algebra
GATE 2016
Hard
A binary relation R on ℕ×ℕ 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?
- ABoth P and Q are true
- P is true and Q is false
- CP is false and Q is true
- DBoth P and Q are false
Explanation
Reflexive: (a,b)R(a,b) needs a≤a or b≤b — always true, so P holds. Transitive: consider (5,5)R(1,100) [via 5≤100] and (1,100)R(1,1) [via 1≤1], but (5,5)R(1,1) would need 5≤1 or 5≤1 — both false. So transitivity fails: Q is false.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.