0
$\begingroup$

I have been reading my text book for a bit now and am still puzzled on how to show something like in the following example problems:

For arbitrary formulas $\phi$, $\psi$, and $\chi$ show that:

  1. $(\phi \lor \psi) \models \chi$ iff $\phi \models \chi$ and $\psi \models \chi$

  2. $\emptyset \models (\phi \to \psi)$ iff $\phi \models \psi$

Thank you for helping me understand in advance.

$\endgroup$
1
$\begingroup$

The notion $\models$ is saying that every model which satisfies the formula on the left side satisfies the formulas on the right side.

  1. Assume that $\phi\lor\psi\models \chi$. If $M\models \phi$, then $M\models \phi\vee \psi$ and thus $\phi\lor\psi\models \chi$ implies that $M\models \chi$, thus any arbitrary model which satisfies $\phi$ also satisfy $\chi$ i.e. $\phi\models \chi$. If we now assume $N\models\psi$ then we may in the same way show $N\models \chi$ and thus $\psi\models \chi$.

For the second direction assume that $\phi \models \chi$ and $\psi\models \chi$. If $M\models \phi\vee\psi$, then by the definition of $\vee$, we know that $M\models \phi$ or $M\models \psi$. If $M\models \phi$ then $\phi \models \chi$ implies that $M\models \chi$ on the other hand if $M\models\psi$ then $\psi \models \chi$ implies that $M\models \chi$. Thus we conclude that $M\models \chi$ and thus $\phi\lor\psi\models \chi$ hold.

  1. Assume $\emptyset\models (\phi\rightarrow \psi)$. Thus each structure satisfies $\phi\rightarrow\psi$. Assume that $M\models \phi$. Since each structure satisfy $\phi\rightarrow\psi$ we know that $M\models \phi\rightarrow\psi$. Thus we may especially draw the conclusion that $M\models \psi$, hence $phi\models \psi$.

For the second direction assume $\phi\models \psi$ and let $M$ be any structure. If $M\not\models \phi$ then $M\models \phi\rightarrow \psi$ since the first part of the implication is false. On the other hand if $M\models \phi$ then $\phi\models \psi$ implies that $M\models \psi$, thus $M\models \phi\rightarrow \psi$ hold, as both parts of the implication are true. Hence any model satisfies $(\phi\rightarrow \psi)$, which make us able to conclude that $\emptyset\models (\phi\rightarrow \psi)$.

$\endgroup$

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.