1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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.) $\endgroup$ Jan 21, 2022 at 0:01
  • $\begingroup$ 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 $\endgroup$
    – Haus
    Jan 21, 2022 at 0:06
  • 1
    $\begingroup$ Is $\Sigma$ a consistent and complete set of propositions? Otherwise Point 1. does not hold. $\endgroup$ Jan 21, 2022 at 0:14
  • $\begingroup$ @Taroccoesbrocco Only consistent, you know some counterexample? $\endgroup$
    – Haus
    Jan 21, 2022 at 0:15
  • $\begingroup$ Moreover, are you in propositional logic or in first-order logic? $\endgroup$ Jan 21, 2022 at 0:23

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$
    – Haus
    Jan 21, 2022 at 0:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .