How would you show if a formula is valid in first order logic?

Question

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.

Answer 1

$$\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.}