I'm trying to understand predicate logic and models. I have an old exam question where we are supposed to find a model that shows that the formula does not hold:

$$ \exists x(P(x) \land \neg M(x)), \ \exists y(M(y) \land \neg S(y)) \vdash \exists z (P(z) \land \neg S(z)) $$

Solution: Consider the model $\mathcal{M}$ with universe $A = \{0,1\}$ and $P^\mathcal{M} = S^\mathcal{M} = \{0\}$ and $M^\mathcal{M}=\{1\}$ and $l$ mapping all variables to $0$. ......more text

I know that $P^\mathcal{M} \subseteq A$. Same with the other predicates. And I suppose $l$ is a lookup-function, but why is it mapping all variables to zero? What is the meaning of that? When we set $P^\mathcal{M} = \{0\}$, does this mean that $P^\mathcal{M}$ is only true when $x = 0$?


When we wet $P^\mathcal{M} = \{0\}$, we mean that, according to the model $\mathcal{M}$, $0$ is the only element of the universe that satisfies the predicate $P$. And similarly for the other predicates.

Your exercise asks to show that the formula $\exists z (P(z) \land \lnot S(z))$ is not a consequence of $\exists x (P(x) \land \lnot M(x))$ and $\exists y (M(y) \land \lnot S(y))$. This amounts to show that there is a model $\mathcal{M}$ such that $\mathcal{M} \models \exists x (P(x) \land \lnot M(x))$ and $\mathcal{M} \models \exists y (M(y) \land \lnot S(y))$ but $\mathcal{M} \not\models \exists z (P(z) \land \lnot S(z))$, i.e., in $\mathcal{M}$, the formulas $\exists x (P(x) \land \lnot M(x))$ and $\exists y (P(y) \land \lnot S(y))$ are true but $\exists z (P(z) \land \lnot S(z))$ is false.

The model $\mathcal{M}$ you described is exactly what you are looking for, because $\mathcal{M} \models P(0) \land \lnot M(0)$ and $\mathcal{M} \models M(1) \land \lnot S(1)$, but $\mathcal{M} \not\models \exists z (P(z) \land \lnot S(z))$ since according to $\mathcal{M}$ all the elements of the universe that satisfy $P$ satisfy $S$ as well.

Note that the function $l$ mapping all variables to $0$ does not play any role in the exercise, since all the formulas involved in it are closed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.