# Natural deduction via completeness theorem

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.

• Your proof of 1 is wrong, but that’s good because it is not true. (Your translation, as well as proof of 2, look fine.) Jan 21, 2022 at 0:01
• Could you tell me where is my error in 1, please? I think that is when I say then if the model $\mathcal{A}\not\models \phi$ then $\mathcal{A}\models \neg \phi$, but I don't know other way for prove this. And I can't think of a counterexample
– Haus
Jan 21, 2022 at 0:06
• Is $\Sigma$ a consistent and complete set of propositions? Otherwise Point 1. does not hold. Jan 21, 2022 at 0:14
• @Taroccoesbrocco Only consistent, you know some counterexample?
– Haus
Jan 21, 2022 at 0:15
• Moreover, are you in propositional logic or in first-order logic? Jan 21, 2022 at 0:23

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.