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.
|#||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
* 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.