Let (5, ≤) be a partial order with two minimal elements a and b, and a maximum…
2003
Let (5, ≤) 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 ∈ S satisfying x ≤ y,
where ⇒ stands for logical implication.Which of the following statements CANNOT be true ?
- A.
P(x) = True for all x ∈ S such that x ≠ b
- B.
P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
- C.
P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
- D.
P(x) = False for all x ∈ S such that a ≤ x and b ≤ x
Attempted by 32 students.
Show answer & explanation
Correct answer: D
Key facts: a and b are minimal, c is the maximum, P(a)=True, P(b)=False, and whenever x ≤ y, P(x) implies P(y).
From monotonicity and P(a)=True, any y with a ≤ y must satisfy P(y)=True. In particular, since c is maximum and a ≤ c, we must have P(c)=True.
The requirement that elements above both a and b are all False would force P(c)=False because c is above both a and b. That contradicts the deduction P(c)=True above. Hence that requirement cannot hold.
By contrast, other proposed assignments are possible in suitable posets. Examples:
• Making every element except b True is consistent (e.g., S = {a, b, c} with P(a)=True, P(c)=True, P(b)=False).
• Making only a and c True and all others False is consistent if there are no elements strictly between a and c (again S = {a, b, c} is an example).
• Assigning False to all elements above b except c is consistent because P(b)=False does not force truth upward; c is still True because of a.
Conclusion: The only statement that cannot be true is the one asserting that every element above both a and b is False, because the maximum element c is above both and must be True.