5
$\begingroup$

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more concise answer. Here is where I got stuck in finding the proof using this method:

  • Since the proof states that if $\Gamma \vdash$ formula(A) is a tautology then $\Gamma$ $\vdash$ A, its contra-positive is the that if $\Gamma$ proves A is not provable then $\Gamma$ does not prove A is a tautology. This is assuming $\Gamma$ is the set of all the given hypotheses.

  • Base case is when length of proof is 1:
    I know that if A $ \in \Gamma$ then $\Gamma$ $\vdash$ A. But I don't know what could disprove A in a proof of length 1. I can list the cases in which $\neg$A is proved and therefore A is disproved but I am not very confident in this method.

If I have all the base cases I am confident that I can finish the rest of the proof but I'm still stuck at the beginning.

Thanks for the help.

$\endgroup$
4
  • $\begingroup$ You can see Wiki's entry on Propositional calculus : Sketch of completeness proof. $\endgroup$ Jul 18, 2014 at 21:39
  • $\begingroup$ It is not clear t me the role of induction; if we want to prove that : it $\Gamma \vDash A$, then $\Gamma \vdash A$, the induction is on what ? $\endgroup$ Jul 21, 2014 at 19:16
  • $\begingroup$ induction on the length of the proof. $\endgroup$
    – Jecht Tyre
    Jul 21, 2014 at 19:41
  • $\begingroup$ But induction on the lenght of the proof works to prove that : if $\Gamma \vdash A$, then $\Gamma \vDash A$. Fo the other way, we have not yet the proof of $A$ ... $\endgroup$ Jul 21, 2014 at 19:43

1 Answer 1

6
$\begingroup$

See George Tourlakis, Mathematical Logic (2008), page 93 :

3.2.1 Metatheorem (Post's Tautology Theorem) : If $\Gamma \vDash_{TAUT} A$, then $\Gamma \vdash A$.

Proof. It is most convenient to prove the contrapositive, namely, if $\Gamma \nvdash A$, , then $\Gamma \nvDash_{TAUT} A$

Some facts are needed :

Claim One. There is an enumeration $G_0,G_1, \ldots$ of all formulae of propositional logic.

See page 95 :

Assume the hypothesis side, $\Gamma \nvdash A$.

We next construct a set of formulae, $\Delta$, which is as large as possible with the properties that it includes $\Gamma$, but also

$\Delta \nvdash A$.

We build $\Delta$ by stages, $\Delta_0, \Delta_1, \ldots$ by an inductive definition, adding no more than one formula at each step.

The $\Delta_n$ sequence is:

$\Delta_0 = \Gamma$

For $n \ge 0$ :

$\Delta_{n+1} = \Delta_n \cup \{ G_n \}$, if $\Delta_n \cup \{ G_n \} \nvdash A$

$\Delta_{n+1} = \Delta_n \cup \{ \lnot G_n \}$, if $\Delta_n \cup \{ \lnot G_n \} \nvdash A$

$\Delta_n$, else.

Thus, at each stage we add to the set that we are constructing at most one formula, which is a member or a negation of a member of the sequence $\{ G_n \}$.

We define $\Delta = \bigcup_{n \ge 0} \Delta_n$, forming $\Delta$ as the set of all the members found in all the $\Delta_n$.

Several facts follow :

Claim Two. $\Gamma \subseteq \Delta$.

Claim Three. For $n \ge 0, \Delta_n \nvdash A$. This follows by induction on $n$.

Claim Five. $\Delta \nvdash A$.

Claim Six. For every formula $B$, either $B \in \Delta$, or $\lnot B \in \Delta$, but not both.

Claim Seven. $\Delta$ is deductively closed, that is, if $\Delta \vdash B$, then $B \in \Delta$.

Now we can define a valuation $v$ that verifies $\Gamma \nvDash A$.

Define a valuation $v$ by setting, for each variable $p$, $v(p) = t$ iff $p \in \Delta$.

Main Claim. For all formulae $B, v(B) = t$ iff $B \in \Delta$.

The proof is by induction on the complexity of $B$. We have the following cases:

(i) $B$ is a variable : by definition of $v$.

Then, check all cases according to the inductive definition of formula.

After that, we can easily conclude the proof as follows: By the Main Claim, every formula $B \in \Delta$ — and hence every formula $B \in \Gamma$ since $\Gamma \subseteq \Delta$ — satisfies $v(B) = t$.

On the other hand, as $\Delta \nvdash A$ it must be $A \notin \Delta$; thus, again via the Main Claim, $v(A) = f$. Therefore $\Gamma \nvDash_{TAUT} A$.

See page 99 :

3.2.2 Corollary. If $\vDash B$, then $\vdash B$.

Proof. Case of $\Gamma = \emptyset$.


Note

A different kind of proof of the Completeness Theorem for propositional logic (due to Kalmar, 1935) can be found in Elliott Mendelson, Introduction to mathematical logic (4ed - 1997), page 42; also in this case it is required the proof of a lemma by induction on the complexity of the formula.

$\endgroup$
1
  • $\begingroup$ I have the textbook and this lengthy proof is exactly what I wanted to avoid. However, I did find the proof I was looking for on the wiki page you gave earlier. You can prove the base with a truth table and then carry out an induction on the complexity of the A. I think that was the answer I was looking for. $\endgroup$
    – Jecht Tyre
    Jul 28, 2014 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.