Main Page | See live article | Alphabetical index

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

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 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).

## 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
22 * 316 * 51 * 718 * 116 * 1312 * 1716 * 197
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.