Godel's Proofs

Here are Godel's two main results: (1) no consistent axiom system for arithmetic can be complete, and (2) no axiom system for arithmetic can be proven consistent by any argument in that system.

Godel did this by constructing a statement, in the language of arithmetic, that says of itself that it cannot be proven. Such a statement must be true because if it were false, it would be both false and provable (an impossible combination if the axioms are consistent). Thus, the statement must be true and so unprovable.

We first define a function from the symbols, expressions, and proofs of A, the language of A, to the subset of the natural numbers (a subset we call Godel's numbers).

The next step is showing that certain meta-truths about the symbols, expressions, and proofs of arithmetic correspond to truths about their Godel numbers.

Godel showed that whenever some string of statements is a proof in A, the string's Godel number (call this number x) stands in a particular numerical relation (call this relation H) to the Godel number of the statement being proven (call this number y).

We will now define a function g of three variables.

From the Godel number of a particular expression, the Godel number of a particular symbol, and an arbitrary number to a particular Godel number--namely, the Godel number of the result of inserting the number for the symbol in the expression.

Using the predicate H and the function g, we can now construct a statement in the language of arithmetic that says of itself that it has no proof. To construct this statement, we begin with this statement function: (x)~Hxg(y; 13; y). This statement function asserts that no number stands in the relation H to the number g(y;13;y).

This statement function, like any expression, can be assigned a Godel number in the usual way: However, rather than working out the entire number, it will be easier and more convenient just to call it bign. Now form this statement: (x)~Hxg(bign;13;bign)--this statement is exactly like the statement function from which it comes except that the number we are calling 'bign' appears in place of the variable 'y'. We call this statement G.

G asserts that no number stands in the numerical relation H to g(bign;13;bign), and this means (on the meta level) that the expression with g(bign;13;bign) as its Godel number has no proof in A.

But, g(bign;13;bign) is G's own Godel number, that is, G asserts of itself that it cannot be proven in A.

But G must be true because, if it were false, that is, if G could be proven, it would be false and provable--impossible assuming that one's axiom system for arithmetic is consistent. Thus, G must be true. But since G asserts that G cannot be proven in A, it follows that G cannot be proven in A. Thus, G is true but unprovable.

Suppose ~G, that is, suppose ~(x)~Hxg(bign;13;bign). By QN, we have (Ex)Hxg(bign;13;bign). This means that G, the statement with Godel number g(bign;13;bign), is provable in A. But if A is consistent, if G is provable, G must be true. Thus, if A is consistent, if we assume ~G (that is, if G is provable), G must be true. Thus, if A is consistent, if ~G, we can prove G.

But, from Godel's first result, we know G cannot be proven in A. Thus, in A we can never prove that A is consistent.

Carter, Phil 305