Let (S, <=) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S -> {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) => P(y) for all x <= y, where => stands for logical implication. Which of the following statements CANNOT be true? A. P(x) = True for all x in S such that x >= b B. P(x) = False for all x in S such that b >= x and x >= c C. P(x) = False for all x in S such that not(x >= b) and not(b >= x) D. P(x) = False for all x in S such that a <= x and b <= x

GATE 2003 · Discrete Mathematics · Partial Order · medium

Answer: D. P(x) = False for all x in S such that a <= x and b <= x — this CANNOT be true because a <= x forces P(x) = True by monotonicity.

1. Establish forced truth values: P(a) = True. Since a is minimal but can have elements above it, for any x with a <= x, P(x) must be True. P(b) = False. For any y with y <= b, we cannot derive P(y) = True from this alone. But P(c) must be True because a <= c.
2. Analyze option D: If a <= x, monotonicity gives P(a) => P(x), i.e., True => P(x), so P(x) = True. If additionally b <= x, that does not change P(x) = True. So no element that is above a can have P(x) = False. Option D requires P(x) = False for all elements above both a and b — but a <= x already forces P(x) = True. Contradiction.