GATE CS 2003 Q31 — Sets, Relations and Functions

We are given a partial order $(S, \leq)$ with a maximum element $c$, and minimal elements $a$ and $b$. The predicate $P$ satisfies:

• $P(a) = \mathbf{True}$
• $P(b) = \mathbf{False}$
• $x \leq y \implies (P(x) \implies P(y))$

Let us analyze the condition in Option D: $a \leq x$ and $b \leq x$.

Since $a \leq x$, the implication rule requires that $P(a) \implies P(x)$ must hold. Since $P(a) = \mathbf{True}$, we must have:

For this implication to be true, $P(x)$ must be $\mathbf{True}$ for all $x$ such that $a \leq x$.

Therefore, it is impossible for $P(x) = \mathbf{False}$ for any $x$ satisfying $a \leq x$ (which includes any $x$ satisfying both $a \leq x$ and $b \leq x$, such as the maximum element $c$). Thus, the statement in Option D cannot be true.