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 ∈ S$ satisfying $x≤y$, where $→$ stands for logical implication. Which of the following statements CANNOT be true?
- $P(x) = $True for all $x ∈ S$ such that $x ≠ b$
- $P(x) = $False for all $x ∈ S$ such that $x ≠ a$ and $x ≠ c$
- $P(x) = $False for all $x ∈ S$ such that $b ≤ x$ and $x ≠ c$
- $P(x) = $False for all $x ∈ S$ such that $a ≤ x$ and $b ≤ x$
My attempt :
- This can be true, because making all elements true trivially satisfy formula $P(x) ⇒ P(y)$.
- This can also be true, if all elements are connected from $b$, then , they can be anything, in particular, they all can be false.
- This can also be true, infact, it is exactly the case we saw in option $(2)$
- This can't be true, because if an element has an edge from both $a$ and $b$, then it has to true.
Can you explain more formally , please?
Let $G$ be the partial order consisting only of the elements $a,b$ and $c$ thus $a\leq c$ and $b\leq c$ but $a$ and $b$ are unrelated. As $P(a)$ hold and $a\leq c$ necessarily $P(c)$ has to hold. Thus we know that $$P(a)=true\>\>\>\> P(b)=false \>\>\>\> P(c)=true$$
is true, since each element $x\in G$ such that $x\neq b$ then $x = a$ or $x=c$ but then $P(x)=true$.
is also true, since if $x\neq a$ and $x\neq c$ then $x=b$ thus $P(x)=false$
is also true since each $x$ such that $x\geq b$ and $x\neq c$, the only option avalible for $x$ is $x=b$ and thus we know that $P(x)=false$.
On the other hand 4. can be true if we do not have any elements which is greater than both $a$ and $b$, something which is not necessary in a partial order. So for instance choose the order consisting of three disjoint elements which are unrelated to eachother. If we however assume that $c$ is a greatest element, then indeed it can not be true.