Godel number

In 1931, Kurt Godel released a paper titled "On Formally Undecidable Propositions of Principia Mathematica and Related Systems" (well the title was originally in German). The paper contains a proof of what is commonly referred to as Godel's Theorem. This theorem is in two parts.

In a nutshell, the first part states that any consistent axiomatic mathematical system which is capable of talking about number theory will be incomplete. That is to say there will be statements in the system which we cannot prove true and cannot prove false (within the system). The second part states that for any such system the statement "This system is consistent" is unprovable (within the system). That is we cannot prove that it is impossible to derive a contradiction in the system.

One tool used by Godel in proving his theorem is Godel numbering. He came up with a procedure to assign a postive whole number (called the Godel number) to each symbol, formula and proof in the system. No two symbols etc. could have the same Godel number, so there was a direct correspondence between statements in the system and a subset of the positive whole numbers. The reason this is important is : statements referring to statements within the system can now be thought of as statements referring to positive whole numbers. More accurately (though more technically) : meta-mathematical statements became statements in number theory.

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.