Two ways to prove the completeness theorem from corollary

232 Views Asked by At

I'm trying to prove the Completeness Theorem for propositional logic from the following corollary.

If $\Sigma \models τ $, then there is a finite subset $Σ_0⊆Σ$ such that $\Sigma_0 ⊨τ $.

It seems to me that there are two legitimate ways to go about it, direct proof and proof by contradiction.

Direct proof would show that the finite satisfiablity of $\Sigma$ ensures there is a truth assignment function $v$ satisfying $\Sigma_0$ and that, by the assumption in the corollary, this $v$ must also satisfy every member of $\Sigma$.

Proof by contradiction would assume that $\Sigma$ is not satisfiable but is finitely satisfiable, and show that $\Sigma$ contains some logical contradiction which a finite $\Sigma_0$ must then imply (so that $\Sigma_0$ cannot be satisfiable).

Are these proofs equally rigorous?

1

There are 1 best solutions below

0
On

In your attempt of direct proof there is a point that is not clear at all. The fact that there is a truth assignment $v$ satisfying $\Sigma_0$ (some finite subset of $\Sigma$), does not imply that $v$ must also satisfy every member of $\Sigma$ (in general, this is false).

Analogously, in your attempt of proof by contradiction, you suppose correctly that $\Sigma$ is finitely satisfiable and not satisfiable, but then you do not show how this assumption leads to a contradiction.


Let us see how to proceed properly. We want to derive the theorem

$(\circ) \ $ If a set of well-formed formulas is finitely satisfiable, then it is satisfiable

from the statement

$(*) \ $ Given a set $\Sigma$ of well-formed formulas and a well-formed formula $\tau$, if $\Sigma \models τ$ then there is a finite subset $\Sigma_0 \subseteq \Sigma$ such that $\Sigma_0 \models \tau $.

We can first observe that $(*)$ is equivalent (by contraposition) to

$(**) \ $ Given a set $\Sigma$ of well-formed formulas and a well-formed formula $\tau$, if for every finite subset $\Sigma_0 \subseteq \Sigma$ we have $\Sigma_0 \not\models \tau $, then $\Sigma \not\models τ$.

Let us now prove the theorem $(\circ)$.

Direct proof: Let $\Sigma$ be a finitely satisfiable set of well-formed formulas. This means that for every finite subset $\Sigma_0$ of $\Sigma$ there is a truth assignment $v_0$ satisfying $\Sigma_0$; moreover, such a $v_0$ does not satisfy the formula $p \land \lnot p$ (since it is a contradiction). So, we have shown that $\Sigma_0 \not\models p \land \lnot p$ for every finite subset $\Sigma_0$ of $\Sigma$. By $(**)$, this implies that $\Sigma \not \models p \land \lnot p$, i.e. there is a truth assignment that satisfies $\Sigma$ but not $p \land \lnot p$. In particular, $\Sigma$ is satisfiable. QED.