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 |
2 Step 2 3 Step 3 4 An informal account of the proof |
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:
Step 1
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 |
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
Finally, sequences of arithmetical statements are assigned further Gödel numbers, such that the sequenceStep 2
prime 1 character 1 * prime 2 character 2 * prime 3 character 3
and so on.
For example the statement
x, P(x) becomes
22 * 316 * 512 * 76 * 1116 * 137, 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
Statement 1 (GN1)
Statement 2 (GN2)
Statement 3 (GN3)
gets the Gödel number 2GN1*3GN2*5GN3, 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).