GATE 2016 CS (CS2) – Question 36

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 2 marks · Multiple choice

On $\mathbb N\times\mathbb N$, (a,b)R(c,d) iff a ≤ c or b ≤ d. P: R is reflexive. Q: R is transitive. Which is true?

Both P and Q
P true, Q false
P false, Q true
Both false

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) P true, Q false

Explanation

Reflexivity holds since a≤a. For transitivity choose x=(2,2), y=(3,1), z=(1,1). Then xRy via 2≤3 and yRz via 1≤1, but xRz fails because both 2≤1 comparisons fail. Thus P is true and Q false, B.

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

GATE 2017 CS (CS2) Q31 – X=a,b,c,d,e has partial order R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e…
GATE 2010 CS (CS1) Q13 – How many reflexive relations exist on a five-element set?
GATE 2015 CS (CS2) Q12 – Find the cardinality of the power set of 0,1,2,…,10.
GATE 2015 CS (CS2) Q13 – On positive integers, aRb iff a≠b and a,b have a common divisor greater than one. Which…
GATE 2015 CS (CS3) Q12 – U is the power set of S=1,2,3,4,5,6. T is cardinality, T′ complement in S, and T∖R set…
GATE 2015 CS (CS3) Q60 – On ordered pairs of positive integers, ((p,q),(r,s))∈R iff p−s=q−r. Which describes R?

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →