Godel numbering

In mathematical logic, a Godel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Godel number. Kurt Godel developed the concept for the proof of his incompleteness theorems.^{[1]: 173-198}

A Godel numbering can be interpreted as an encoding in which a number is assigned to each symbol of a mathematical notation, after which a sequence of natural numbers can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic.

Since the publishing of Godel's paper in 1931, the term "Godel numbering" or "Godel code" has been used to refer to more general assignments of natural numbers to mathematical objects.

Godel noted that each statement within a system can be represented by a natural number (its Godel number). The significance of this was that properties of a statement--such as its truth or falsehood--would be equivalent to determining whether its Godel number had certain properties. 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, Godel 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 Godel 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 word foxy is represented by 102111120121.
• The logical formula x=y => y=x is represented by 120061121032061062032121061120.

Godel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing.

To encode an entire formula, which is a sequence of symbols, Godel used the following system. Given a sequence ${\displaystyle (x_{1},x_{2},x_{3},...,x_{n})}$ of positive integers, the Godel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:

${\displaystyle \mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.}$

According to the fundamental theorem of arithmetic, any number (and, in particular, a number obtained in this way) can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Godel number (for any given number n of symbols to be encoded).

Godel 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 proof's key observation (Godel 1931).

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

In the specific Godel numbering used by Nagel and Newman, the Godel number for the symbol "0" is 6 and the Godel number for the symbol "=" is 5. Thus, in their system, the Godel number of the formula "0 = 0" is 2⁶ x 3⁵ x 5⁶ = 243,000,000.

Infinitely many different Godel numberings are possible. For example, supposing there are K basic symbols, an alternative Godel 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 ${\displaystyle s_{1}s_{2}s_{3}\dots s_{n}}$ would then be mapped to the number

${\displaystyle h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.}$

In other words, by placing the set of K basic symbols in some fixed order, such that the ${\displaystyle i}$-th symbol corresponds uniquely to the ${\displaystyle i}$-th digit of a bijective base-K numeral system, each formula may serve just as the very numeral of its own Godel number.

For example, the numbering described here has K=1000.^[ii]

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

Once a Godel 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 Godel mapping and r is an inference rule, then there should be some arithmetical function g_r of natural numbers such that if formula C is derived from formulas A and B through an inference rule r, i.e.

${\displaystyle A,B\vdash _{r}C,}$

then

${\displaystyle g_{r}(f(A),f(B))=f(C).}$

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

Thus, in a formal theory such as Peano arithmetic in which one can make statements about numbers and their arithmetical relationships to each other, one can use a Godel numbering to indirectly make statements about the theory itself. This technique allowed Godel to prove results about the consistency and completeness properties of formal systems.

In computability theory, the term "Godel 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.^{[citation needed]}
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.^{[citation needed]}

Also, the term Godel 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.^{[citation needed]}

Godel sets are sometimes used in set theory to encode formulas, and are similar to Godel 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 Godel numbers, but somewhat easier to define because the tree structure of formulas can be modeled by the tree structure of sets. Godel sets can also be used to encode formulas in infinitary languages.

• Church encoding
• Description number
• Godel numbering for sequences
• Godel's incompleteness theorems
• Chaitin's incompleteness theorem

• Nagel, Ernest; Newman, James R. (1959). Godel's Proof.

• Hofstadter, Douglas (1979). Godel, Escher, Bach: an Eternal Golden Braid. Basic Books. ISBN 978-0-465-02656-2. Defines and uses an alternative Godel numbering.
• Hofstadter, Douglas (2007). I Am a Strange Loop. Basic Books. ISBN 978-0-465-03078-1. Includes the history of Godel's numbering.
• Hemann, Jason; Holk, Eric (June 15, 2013). "Visualizing the Turing Tarpit" (PDF). FARM '13: Proceedings of the First ACM SIGPLAN Workshop on Functional Art, Music, Modeling & Design: 71-76. doi:10.1145/2505341.2505348. ISBN 978-1-4503-2386-4. Archived from the original (PDF) on September 27, 2016. Uses Godel numbering to encode programs.

• Mathematical logic
• Theory of computation
• Works by Kurt Godel

• CS1 German-language sources (de)
• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from April 2021
• All articles lacking in-text citations
• Articles needing additional references from May 2025
• All articles needing additional references
• All articles with unsourced statements
• Articles with unsourced statements from February 2020