Gödel numbers are constructed as follows. First we identify the elements we are to represent, and then we assign a natural number to each one. Finally, we assign a natural number to each possible sequence of the elements; these last numbers are our Gödel numbers.
A system P is made up of two main types of elements:
These represent all the operation
s that we can perform in the system; more complex operations can be constructed from them, as from the Peano postulates
. (Not all these symbols show up in all browser
s, so I'll explain in words after each usage.)
These are classed as:
To number the primitive signs, they are assigned the first 7 odd numbers:
- "0" (zero) = 1
- "succ" (successor) = 3
- "¬" (not) = 5
- "⊦" (logical or) = 7
- "∀" (for all) = 9
- "(" (left parenthesis) = 11
- ")" (right parenthesis) = 13
Each variable of type n is uniquely assigned a number of the form pn where p is a prime greater than 13; each variable of a given type will have a different value of p.
This allows us to represent every sequence of basic signs as a sequence of natural numbers.
Finally, given the sequence (n1, n2, ... nk), which can be mapped to a given sequence of signs, we seek to represent this sequence as a single number. We do this by mapping (n1, n2, ... nk) to 2n1.3n2 ... pknk, where pk is the kth prime. This product of powers of primes is the Gödel number of the expression.
To obtain the components from a given Gödel number, we need simply to represent it as a product of prime factors and decode in the opposite sequence to the above; there is only one possible prime factorization for any natural number, and hence each Gödel number represents a unique expression.
The expression "succ(n)", where n is a variable of type 1, can be expressed by the sequence (1,17), where "succ" is represented by 1, and "n" is represented by 17 to the power of 1. We convert this to a single number by calculating 21.317 = 258280326. This rather large number 258280326 is the Gödel number of "succ(n)"; however it is not usually necessary to calculate a Gödel number, but just to know that one can be calculated.
Kurt Gödel. "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". [www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf]. 1931. Section 2.2.