How to prove Post's Theorem by induction?

Question

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.

Answer 1

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.