2
$\begingroup$

I'm trying to understand how I can solve two particular tasks.

I need to show if the following formulas are valid:

  1. $Pa \lor Pb \rightarrow \exists xPx$

    and this one

  2. $\forall xPx \rightarrow Pa \land Pb$

The book I'm reading from tells me that

a closed formula $\varphi$ is valid if it is true in all models $M$, otherwise it is falsifiable

But, still I didn't understand that so well.

I would appreciate if someone could show me how I can solve the two formulas above so they are valid.

Thank you.

$\endgroup$
  • $\begingroup$ Type \$\varphi\$ to get $\varphi$. $\endgroup$ – Git Gud Nov 4 '13 at 0:23
  • $\begingroup$ @GitGud Thanks! Edited now. $\endgroup$ – Dabbish Nov 4 '13 at 0:24
  • 1
    $\begingroup$ Try negating each expression and see if you get a contradiction. If you do, they're tautologous, and tautologies are true in every model. $\endgroup$ – Malice Vidrine Nov 4 '13 at 0:25
  • $\begingroup$ (Or, if you're supposed to use model theoretic methods, think about the model with underlying set $\{a,b\}$ and about the definitions of truth for $\varphi\wedge\psi$, $\exists\alpha\varphi$, etc.) $\endgroup$ – Malice Vidrine Nov 4 '13 at 0:34
3
$\begingroup$

$$\fbox{Syntactically}~^{\dagger}$$

For (1), assume $Pa \lor Pb$. Suppose $Pa$, then $\exists xPx$ (by $\exists$-introduction). Similarly for $Pb$. Since $\exists xPx$ follows from both cases, conclude $\exists xPx$ (by $\lor$-elimination based on the first assumption and the two cases). This shows that $Pa \lor Pb \vdash \exists x Px$.

For (2), assume $\forall x Px$. Then, in particular you have $Pa$ (by $\forall$-elimination). Similarly for $Pb$. Conjoin $Pa$ and $Pb$ to get the desired conclusion. This shows that $\forall x Px \vdash Pa \land Pb$.

Assuming the proof system is sound, these will imply $Pa \lor Pb \models \exists x Px$ and $\forall x Px \models Pa \land Pb$.

$$\fbox{Semantically}~^{\dagger}$$

For (1), assume some model satisfies $Pa \lor Pb$. This means that either the object denoted by 'a' is in the interpretation of the predicate 'P' or the object denoted by 'b' is. In either case, we know that the interpretation of 'P' is non-empty, therefore the model also satisfies $\exists xPx$.

For (2), assume some model satisfies $\forall x Px \equiv \lnot \exists x \lnot Px$. Suppose, for contradiction, that this model also satisfies $\lnot Pa \lor \lnot Pb$. Suppose it satisfies $\lnot Pa$, then it satisfies $\exists x \lnot Px$, but this contradicts the first assumption. Supposing that it satisfies $\lnot Pb$ similarly leads to a contradiction. Since both cases of the hypothesis lead to a contradiction, it follows that the model actually satisfies $\lnot(\lnot Pa \lor \lnot Pb)$, which is equivalent to $Pa \land Pb$.

$\dagger$ Meaning proof-theoretically and model-theoretically, respectively.

$\endgroup$
  • $\begingroup$ thanks alot for a great answer! I would appreciate if you also could give an helping on on my previous question which i posted here.math.stackexchange.com/questions/550239/… Thanks again! $\endgroup$ – Dabbish Nov 4 '13 at 2:39
  • $\begingroup$ I'm glad you found it helpful! I have answered your other question, so let me know there if you're having trouble following it or finding the relations. $\endgroup$ – Hunan Rostomyan Nov 4 '13 at 4:30

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.