An Abstract Form of Gödel’s Theorem – Part 3

Earlier we define P to be the set of sentences of L called the provable sentence of L.  In this post P will be the set of Gödel numbers of all the provable sentences of L instead of the set of expressions themselves.  Not only that, given any number set A, àwill stand for the compliment of A relative to the natural numbers.  So, à is the set of all natural numbers not in A.  So, if P is the set of Gödel numbers of all the provable sentences of L, then  is the set of Gödel numbers of all the non-provable sentences of L.

Theorem (GT) – After Gödel with Shades of Tarski¹

Prove:  There is a true sentence of L not provable in L.

Given: (1) The set * is expressible in L and (2) L is correct.

To begin, let’s examine our givens.  First off, when we say that * is expressible in L, we mean that there is some predicate of L that expresses *.  Let’s call this predicate H.  So, by the definition of expressibility that was given in an earlier post…

(1) *

where T is the set of all true sentences of L.   Secondly, when we say L is correct, then we are saying that no provable sentences in L can be false.

With those two ideas in place, the proof follows quickly.  Let h be the Gödel number of the predicate H.  Since (1) is true for all n, and in particular for n=h, then…

(2) *

In the previous post we called the Gödel number for the expression H(n) to be d(n).  Also, in the earlier post the set A* was defined as the set of all natural numbers such that d(n)∈A. If we let A be the set , then we get the following equivalence…

(3) 

Once again, this equivalence holds for all n, and in particular for n=h, which in turn gives us…

(4)

Since the sets  and  are compliments of one another, then it follows that…

(5)

Once again, this holds are all n, and in particular it will hold for the Gödel number for the expression H(n), which is d(h) giving us…

(6)

Substituting (6) into (4) gives us…

(7)

And substituting (7) into (2) gives us…

(8)

Since d(h) is the Gödel number for the expression H(h) then by definition of the set P…   is provable in L and is not provable in L.  Now, if H(h) is provable, then .  However, from (8) above, this means that H(h) is not in T! So, we would have a provable sentence that is not in T making it false.  But this contradicts our given that L is correct – namely, no provable sentences are false.  Now, if H(h) is not provable, then and from (8) above we get that H(h) is in T.  In other words, H(h) is a true sentence not provable in L.  Q.E.D.

For me, I am not quite completely clear on what took place above.  I can follow the symbol manipulation and understand the final argument, but what is exactly happening is still fuzzy for me.  In the next couple of posts I will try to look further at the nature of the sets P, P*, and * and the role they play in this proof.

---

1. Smullyan – GIT, Pg. 7.

Advertisement