Natural deduction via completeness theorem

first-order-logiclogicnatural-deduction

I have some question about how to use completeness theorem, I need to show the follow:

Let $\Sigma$ be a consistent set of propositions and $\phi, \psi$ formulas. Show that

  1. If $\Sigma\not\vdash \phi$ then $\Sigma\vdash\neg \phi$
  2. If $\Sigma\not\vdash \phi$ then $\Sigma\not\vdash[\phi\lor (\psi\land \phi)]$

I think that by completeness theorem this is equivalent to the following:

Let $\Sigma$ be a satisfiable set of propositions and $\phi, \psi$ formulas. Show that

  1. If $\Sigma\not\models \phi$ then $\Sigma\models\neg \phi$
  2. If $\Sigma\not\models \phi$ then $\Sigma\not\models[\phi\lor (\psi\land \phi)]$.

My attempt: The latter is easy to prove,

  1. If $\Sigma\not\models \phi$, then there exists a model $\mathcal{A}$ such that $\mathcal{A}\models \Sigma$ but $\mathcal{A}\not\models \phi$, then $\mathcal{A}\models \neg \phi$, then $\Sigma\models \neg \phi.$

  2. If $\Sigma \not\models\phi$ then there exists a models $\mathcal{A}$ such that $\mathcal{A}\models\Sigma$ but $\mathcal{A}\not\models \phi$ then $\mathcal{A\not\models \phi\land\psi}$, then $\mathcal{A}\not\models \phi\lor (\phi\land\psi)$ and then $\Sigma\not\models [\phi\lor (\psi\land \phi)]$

I appreciate if you tell me if I have any errors, or if I'm right, any help is welcome.

Best Answer

It is true that, thanks to completeness (and soundness) theorem, proving Points 1 and 2 is equivalent to prove Points 3 and 4. And your proof of Point 4 is correct. But your proof of Point 3 is not correct, and actually Point 3 (and hence Point 1) does not hold!

Where is the error in your attempt to prove Point 3? From the fact that $\mathcal{A} \models \lnot \phi$ it does not follow that $\Sigma \models \lnot \phi$. Indeed, $\Sigma \models \lnot \phi$ means that for every model $\mathcal{A}'$, if $\mathcal{A}' \models \Sigma$ then $\mathcal{A}' \models \lnot \phi$. But in your attempt to prove Point 3, you have just shown that there exists a model $\mathcal{A}$ such that $\mathcal{A} \models \Sigma$ and $\mathcal{A} \models \lnot \phi$. A priori, it is still possible that there is another model $\mathcal{B}\models \Sigma$ such that $\mathcal{B} \models \phi$, your argument does not exclude this possibility. And actually this is what actually happens!

Why Point 3 does not hold? Suppose that $\Sigma$ is the set of axioms defining a group (it can be easily expressed in first-order logic, see here), and that $\phi$ is the formula expressing that the group is abelian. Clearly, $\Sigma \not\models \phi$ because not all groups are abelian, but from that it does not follow that $\Sigma \models \lnot \phi$ because it is not true that all groups are non-abelian.

Related Question