Godel number (thing)

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.

Elements

A system P is made up of two main types of elements:

Primitive signs

• "0" (zero)
• "succ" (successor)
• "¬" (logical not)
• "⊦" (logical or)
• "∀" (for all)
• "(" (left parenthesis)
• ")" (right parenthesis)

These represent all the operations 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 browsers, so I'll explain in words after each usage.)

Variables

These are classed as:

• Variables of type one - natural numbers (members of the set of natural numbers)
• Variables of type two - sets of variables of type one (subsets of the set of natural numbers)
• Variables of type three - sets of sets of variables of type one (sets of subsets of the natural numbers)
• Variables of type four, five, etc are defined analogously.

Numbering elements

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 pⁿ 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.

Numbering sequences

Finally, given the sequence (n₁, n₂, ... n_k), 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 (n₁, n₂, ... n_k) to 2ⁿ¹.3ⁿ² ... p_k^nk, where p_k 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.

Example

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 2¹.3¹⁷ = 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.

Reference

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.