« Speculations on Gödel's Incompleteness Theorems, the Halting Problem, and The Simulation Argument | Main | Upcoming Singularity and Artificial Intelligence Events of Interest »

July 31, 2008

Gödel's First Incompleteness Theorem and Gödel Numbering

My last post talked about Kurt Gödel's incompleteness theorems. Gödel used a technique called Gödel numbering to prove his first incompleteness theorem. This numbering system allows mathematical statements to talk about other mathematical statements - in other words, it is a meta-mathematical system. Essentially, Gödel numbering can be thought of as a function that assigns a unique integer to every mathematical statement in a formal language.

For example, consider the arbitrary symbol mapping below. Note that symbol mappings do not have to be unique. In fact, an infinite number of these mappings can be created which still give unique Gödel numbers to all possible correctly formed formulas.

Symbol Mapping
+ 1
0 2
x0 3
^ 4
1 5
x1 6
* 7
2 8
x2 9
= 10
3 11
x3 12
) 13
4 14
x4 15
( 16
... ...

In general,

# 3 * # - 2
x# 3 * (# + 1)
3 * # + 1

Note that multiple, infinite sequences of symbols can be mapped by interleaving them within the sequence.

For example, the formula

   (x0 + 1) = x02 + 2x0 + 1

maps to the following sequence of integers:

   16, 3, 1, 5, 13, 10, 3, 4, 8, 1, 8, 7, 3, 1, 5

In order to encode this sequence, and therefore the original statement, as a unique Gödel number, the following function can be used

   GödelNumber(y0,y1,y2,...) = 2y0 * 3y1 * 5y2 * 7y3 * 11y4 * ... * primenxn

with subsequent terms following the sequence of prime numbers. The fundamental theorem of arithmetic guarantees that any natural number greater than 1 can be written as a unique product of prime numbers. Therefore, the original sequence of integers can be recovered uniquely through factorization. Our example statement can be mapped to the number



Note that the number is broken into two parts for presentation only - it is in reality a single 95 digit number. Mathematical proofs can, in a similar manner, be represented by sequences of Gödel numbers called Gödel sentences. Now assume that all the Gödel sentences which represent proofs that are true can be listed in a sequence:

  a, b, c, d, ...

Encode the statement "this mathematical proof does not appear in the list of Gödel sentences" as a Gödel sentence. Can it be found in the list? Assume that it can. If so, it must be false, because it states that it is not in the list. Therefore, it must in fact never appear in the list. This means that it is fact a true proof, and since it does not appear in the list, our list of "all true mathematical proofs" is necessarily incomplete.

Related Posts

Speculations on Gödel's Incompleteness Theorems, the Halting Problem, and The Simulation Argument
Past, Present and Future

Chris K. Haley, NestedUniverse.net. Subscribe Get free RSS or email updates here.