Gödel number

Gödel numbers (abbrev. GN) are a form of encoded logical statement, essential to the proof of Gödel's incompleteness theorem. An analogy is to the numbers used to represent menu items in foreign language restaurants, where for example "133" might mean "I wish to eat the steak chow mein with stir-fried radish". The main requirement is that each statement has a Gödel number that is unique. One might feel unhappy about a restaurant where "133" meant either "chow mein" or "blinis" or both together. Similarly, Gödel numbers ensure that each syntactically correct logical statement has a unique coded identifier.

Table of contents

1 Step 1 2 Step 2 3 Step 3 4 An informal account of the proof

Step 1

Gödel numbers are constructed with reference to symbols of the propositional calculus and formal arithmetic. Each symbol is first assigned a natural number, thus:

Logical symbols	Numbers 1:12
¬ ( ) S 0 = . +	1 ("not") 2 ("for all") 3 ("if,then") 4 ("or") 5 ("and") 6 7 8 ("is the successor of") 9 10 11 12
Propositional symbols	Numbers greater than 10 but divisible by 3
P Q R S	12 15 18 21
Individual variables	numbers greater than 10 with remainder 1 when divided by 3
v x y	13 16 19
Predicate symbols	numbers greater than 10 with remainder 2 when divided by 3
E F G	14 17 20

And so on and so forth (NB the syntax of the propositional calculus ensures that there is no ambiguity between "P" and "+", even though both are assigned the number 12).

Step 2

Arithmetical statements are assigned unique Gödel numbers referenced to the series of prime numbers. This is based on a simple code which essentially reads
prime 1 ^{character 1} * prime 2 ^{character 2} * prime 3 ^{character 3}
and so on. For example the statement
x, P(x) becomes
2² * 3¹⁶ * 5¹² * 7⁶ * 11¹⁶ * 13⁷, because
{2, 3, 5, 7, 11, ...} is the prime series, and 2, 16, 12, 6, 16, 7 are the relevant character codes. This is a large but perfectly determinate number (on the order of 10^46).

Step 3

Finally, sequences of arithmetical statements are assigned further Gödel numbers, such that the sequence
Statement 1 (GN1)
Statement 2 (GN2)
Statement 3 (GN3)
gets the Gödel number 2^GN1*3^GN2*5^GN3, which we will call GN4. The proof of Gödel's incompleteness theorem depends on the demonstration that, in formal arithmetic, some sets of statements logically entail or prove other statements. For example it might be shown that GN1, GN2, and GN3 together, i.e. GN4, prove GN5. Because this is a demonstrable relationship between numbers it is entitled to its own symbol, for example R. R(v,x) would then mean "x proves v". In the case where x and v are Gödel numbers GN5 and GN4 we would say
R(GN5,GN4).

An informal account of the proof

The core of Gödel's argument is that we can write the statement
x, ¬R(v,x)
which means
no proposition of type v can be proved.
The Gödel number for this statement would be
2² * 3¹⁶ * 5¹ * 7¹⁸ * 11⁶ * 13¹² * 17¹⁶ * 19⁷
but we will call it GN6. Now if we consider the statement
x, ¬R(GN6,x),
we will realise that it says
no proposition that says 'no proposition of type v can be proved' can be proved.
This collapses into the statement
this proposition cannot be proved,
which is inconsistent, because if it is provable then it is not provable, and vice versa.