Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. Kurt Gödel developed the concept for the proof of his incompleteness theorems.

A Gödel numbering can be interpreted as an encoding in which a number is assigned to each symbol of a mathematical notation, so that a sequence of symbols is represented by a sequence of natural numbers. Such a sequence can in turn be coded as a single natural number, which allows formulas, and properties of formulas, to be handled within formal theories of arithmetic. The technique is also known as the arithmetization of syntax.

Since the publication of Gödel's paper in 1931, the terms "Gödel numbering" and "Gödel code" have also been used more generally for effective assignments of natural numbers to mathematical objects.

Simplified overview

Gödel noted that each statement within a system can be represented by a natural number (its Gödel number). The significance of this was that syntactic properties of a statement—such as being a well-formed formula, being an axiom, or being provable—correspond to arithmetical properties of its Gödel number, so that questions about the system become questions about numbers. The numbers involved might be very large indeed, but this is not a barrier; all that matters is that such numbers can be constructed.

In simple terms, Gödel devised a method by which every formula or statement that can be formulated in the system gets a unique number, in such a way that formulas and Gödel numbers can be mechanically converted back and forth. There are many ways to do this. A simple example is the way in which English is stored as a sequence of numbers in computers using ASCII. Since ASCII codes are in the range 0 to 127, it is sufficient to pad them to 3 decimal digits and then to concatenate them; the text is recovered by splitting the digits into groups of three, starting from the right:

Gödel's encoding

number variables property variables ...
Symbol 0 s ¬ ∨ ∀ ( ) x1 x2 x3 ... P1 P2 P3 ...
Number 1 3 5 7 9 11 13 17 19 23 ... 289 361 529 ...
Gödel's original encoding

Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol of his formal system P, a type-theoretic system obtained from that of Principia Mathematica by adding the Peano axioms.

To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence (x1,x2,x3,...,xn) of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:

enc(x1,x2,x3,…,xn)=2x1⋅3x2⋅5x3⋯pnxn.

By the fundamental theorem of arithmetic, every natural number greater than 1 factors uniquely into prime factors, so the original sequence can be recovered from its Gödel number. Because every exponent xi is positive, the primes occurring in the factorization are exactly the first n primes, so the length n of the sequence is recovered as well.

Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof.

There are more sophisticated (and more concise) ways to construct a Gödel numbering for sequences.

Example

In the Gödel numbering used by Nagel and Newman, the symbol "0" has Gödel number 6 and the symbol "=" has Gödel number 5. The Gödel number of the formula "0 = 0" is therefore 26 × 35 × 56 = 243,000,000. Conversely, factoring 243,000,000 gives the exponents 6, 5 and 6, which spell out "0 = 0".

Under a different numbering, in which "0" has number 1 and "=" has number 5, the same formula receives the Gödel number 21 × 35 × 51 = 2,430.

Lack of uniqueness

Infinitely many different Gödel numberings are possible. For example, supposing there are K basic symbols, an alternative Gödel numbering could be constructed by invertibly mapping this set of symbols (through, say, an invertible function h) to the set of digits of a bijective base-K numeral system. A formula consisting of a string of n symbols s1s2s3…sn would then be mapped to the number

h(s1)×Kn−1+h(s2)×Kn−2+⋯+h(sn−1)×K1+h(sn)×K0.

The scheme works equally well with any base larger than the number of symbols. If the base is a power of 10, say 10m, and every code h(si) has at most m decimal digits, then the Gödel number written in base 10 is just the concatenation of the codes, each padded with leading zeros to m digits, which makes conversion by hand easy. With base 10 and three symbols coded 1, 2 and 3, for example, the string s1s2s3 receives the number 123. The ASCII encoding in the overview above and the numbering used in the proof sketch for Gödel's first incompleteness theorem both use base 1000.

Application to formal arithmetic

Recursion

One may use Gödel numbering to show how functions defined by course-of-values recursion are in fact primitive recursive functions.

Expressing statements and proofs by numbers

Once a Gödel numbering for a formal theory is established, each inference rule of the theory can be expressed as a function on the natural numbers. If f is the Gödel mapping and r is an inference rule, then there should be some arithmetical function gr of natural numbers (for Gödel's numbering, a primitive recursive one) such that if formula C is derived from formulas A and B through an inference rule r, i.e.

A,B⊢rC,

then

gr(f(A),f(B))=f(C).

This is true for the numbering Gödel used, and for any other numbering where the encoded formula can be arithmetically recovered from its Gödel number.

Thus, in a formal theory such as Peano arithmetic, which can express statements about numbers and their arithmetical relationships, a Gödel numbering makes it possible to indirectly make statements about the theory itself, such as that a given formula is provable. Using a diagonal construction (later generalized as the diagonal lemma), Gödel obtained a sentence that in effect asserts its own unprovability, and thereby proved his results about the completeness and consistency of formal systems.

Generalizations

In computability theory, the term "Gödel numbering" is used in settings more general than the one described above. It can refer to:

  1. Any assignment of the elements of a formal language to natural numbers in such a way that the numbers can be manipulated by an algorithm to simulate manipulation of elements of the formal language. Turing machines, for example, can be described by finite strings of symbols, listed in a fixed order and thereby numbered, so that a universal Turing machine can run any machine given its number.
  2. More generally, an assignment of elements from a countable mathematical object, such as a countable group, to natural numbers to allow algorithmic manipulation of the mathematical object; Rabin, in founding computable algebra, calls such an assignment an "indexing".

Also, the term Gödel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as Turing machines that manipulate strings rather than numbers.

Gödel sets

Gödel sets are sometimes used in set theory to encode formulas, and are similar to Gödel numbers, except that one uses sets rather than numbers to do the encoding. In simple cases when one uses a hereditarily finite set to encode formulas this is essentially equivalent to the use of Gödel numbers, but somewhat easier to define because the tree structure of formulas can be modeled by the tree structure of sets. Gödel sets can also be used to encode formulas in infinitary languages.

See also