A Proof of Self-Proof; 15 of 15

          Appendix 2. A Proof of Self-Proof

          Let A = the axioms of arithmetic, and “A prvs x” be the arithmetic sentence encoding the statement that there is a proof of x from the axioms A.

          Let h = the Henkin sentence “This sentence is provable”; then h = A prvs h .

Löb says that h = true; it is both true and provable. All proofs of  Löb’s theorem involve Gödel’s second incompleteness theorem:

For all B:      B not prvs contradiction

                    implies

B not prvs (B not prvs contradiction)

-        That is, consistent systems do not prove that they are consistent.

Here is a proof of Löb’s theorem:

Say h = A prvs h;  then

(not h)  =  A not prvs h   =  A not prvs (not (not h))

So if (not h)  =  C  then     C   =  A not prvs (not C)

Therefore  (A+C) prvs ( A not prvs (not C))

Therefore  (A+C) prvs ( (A+C) not prvs (not C))

Therefore  (A+C) prvs ( (A+C) not prvs (C and not C))

Therefore  (A+C) prvs ( (A+C) not prvs (contradiction))

So by Gödel’s Second Incompleteness Theorem

          (A+C)  prvs (contradiction)

So      A prvs (not C)

So      A prvs h

So by definition of h,   h =  true.

QED.

          This proof is valid, but I left out a few steps; in particular, proof of Gödel’s second incompleteness theorem. A more detailed proof of Löb’s theorem would explain why this proof is possible. It seems like something-for-nothing, but in fact it is more like nothing-for-nothing.

Another proof of Löb’s theorem requires this assumption:

If A prvs X, then A prvs ( X and (A prvs X))

That is, any proof can be proved to be a proof. This assumption about provability can itself be proved from the nature of Gödel coding of provability. Any valid proof can be checked at every step, and that way proven to be a proof.

The following lemma says that Henkin sentences tell us nothing new; everything they help prove can be proven without their help.

Lemma 1. “The Vanity of Faith”

If h = A prvs h,  then for all sentences X

(A+h) prvs X          implies         A prvs X

Proof of lemma:

Say h = A prvs h,   and    (A+h) prvs X:

Then                      (A + not X) prvs (not h)

so                 (A + not X) prvs (A not prvs  h)

so                 (A + not X) prvs (A not prvs contradiction)

so                 (not X) prvs (A prvs (A not prvs contradiction))

Now for a Gödel statement. Let G be the sentence

          G       =        A not prvs G

Such a G exists by various self-reference theorems. Therefore

          not G           implies         A prvs G

          not G           implies         A prvs (G and A prvs G)

          not G           implies         A prvs (G and not G)

          not G           implies         A prvs contradiction

          A not prvs contradiction            implies         G

This, along with the statement bolded above, proves

          (not X)         prvs   (A prvs G)

So therefore

          (not X)         prvs   (A prvs (G and (A prvs G)))

          (not X)         prvs   (A prvs (G and not G))

          (not X)         prvs   (A prvs contradiction)

So therefore           (A + not X)            prvs             contradiction

And therefore        A       prvs             X

QED.

Self-proving sentences prove nothing new. They add no information. Call a sentence ‘deductively empty’ if it proves nothing new; then lemma 1 says that faith is empty. The next lemma proves that deductively empty statements must be true.

Lemma 2. “The Law of Levity”

If, for all sentences y,      (A+X) prvs y          implies         A prvs y

Then                                A prvs X

Proof of lemma:  Assume that for all sentences y

          (A+X)  prvs  y       implies         A prvs y

Let y equal X:        (A+X)  prvs  X      implies         A prvs X

But (A+X) prvs X is obviously true:

therefore A prvs X.

QED.

Informally:

“Emptiness implies inevitability.”

“Vanities are necessities.”

“Bubbles rise.”

Now for  Löb’s Theorem:

 If   h  =  A prvs h    then   h  is true;   A does prove h.

Proof of theorem:

Combine the Vanity of Faith with the Law of Levity:

          h  =  A prvs h

          implies

          h is deductively empty

          implies

          h is provably true.

QED.

Self-proof is true because it is empty. It proves itself and nothing else.