Appendix
2. A Proof of SelfProof
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 somethingfornothing, but in fact it is more like
nothingfornothing.
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 selfreference 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.
Selfproving 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.
Selfproof is true because it is empty. It proves itself
and nothing else.
No comments:
Post a Comment