Question

Let (A, ≤) be a partial order with two minimal elements a, b and a maximum element c. Let P:A –>  {True, False} be a predicate defined on A. Suppose that P(a) = True, P(b) = False and P(a) ⇒ P(b) for all satisfying a ≤ b, 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 b ≤ x and x ≠ c

(c) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c

(d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

The question was asked in an online interview.

I would like to ask this question from Relations topic in division Relations of Discrete Mathematics

Answer 1

The correct choice is (d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

To explain I would say: Here, maximum element is c and so c is of a higher order than any other element in A. Minimal elements are a and b: No other element in A is of lower order than either a or b.

We are given P(a) = True. So, for all x such that a≤x, P(x) must be True. We do have at least one such x, which is c as it is the maximum element. So, P(x) = False for all x ∈ S such that a ≤ x and b ≤ x -> cannot be true. P(x) = True for all x  S such that x ≠ b -> can be True as all elements mapped to TRUE doesn’t violate the given implication. P(x) = False for all x ∈ S such that x ≠ a and x ≠ c -> can be True if a is related only to c. P(x) = False for all x ∈ S such that b ≤ x and x ≠ c -> can be True as b≤x ensures x≠a and for all other elements P(x) can be False without violating the given implication.