This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(April 2021) (Learn how and when to remove this message)

This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Gödel numbering" – news ·newspapers ·books ·scholar ·JSTOR(May 2025) (Learn how and when to remove this message)

Inmathematical logic, aGödel numbering is afunction that assigns to each symbol andwell-formed formula of someformal language a uniquenatural number, called itsGödel number.Kurt Gödel developed the concept for the proof of hisincompleteness theorems.^{[1]: 173–198}

A Gödel numbering can be interpreted as anencoding in which a number is assigned to eachsymbol of amathematical notation, after which a sequence ofnatural 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 Gödel's paper in 1931, the term "Gödel numbering" or "Gödel code" has been used to refer to more general assignments of natural numbers to mathematical objects.

Gödel noted that each statement within a system can be represented by a natural number (itsGödel number). The significance of this was that properties of a statement—such as its truth or falsehood—would be equivalent to determining whether its Gödel 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, 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 usingASCII. 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 wordfoxy is represented by102111120121.
• The logical formulax=y => y=x is represented by120061121032061062032121061120.

Gödel used a system based onprime 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, Gödel used the following system. Given a sequence${\displaystyle (x_1,x_2,x_3,...,x_n)}$ of positive integers, the Gödel encoding of the sequence is the product of the firstn primes raised to their corresponding values in the sequence:

${\displaystyle \mathrm{e}\mathrm{n}\mathrm{c}(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 thefundamental theorem of arithmetic, any number (and, in particular, a number obtained in this way) can be uniquely factored intoprime factors, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded).

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

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

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

Infinitely many different Gödel numberings are possible. For example, supposing there areK basic symbols, an alternative Gödel numbering could be constructed by invertibly mapping this set of symbols (through, say, aninvertible functionh) to the set of digits of abijective base-K numeral system. A formula consisting of a string ofn 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.}$

If K is chosen to be a power of 10, this scheme makes it fairly easy for a human to convert between a string of symbols and its Gödel number, since the Gödel number represented in base 10 is just the concatenation of the${\displaystyle n}$ decimal numbers${\displaystyle h(s_i)}$.

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

One may use Gödel numbering to show how functions defined bycourse-of-values recursion are in factprimitive recursive functions.

Once a Gödel numbering for a formal theory is established, eachinference rule of the theory can be expressed as a function on the natural numbers. Iff is the Gödel mapping andr is an inference rule, then there should be somearithmetical functiong_r of natural numbers such that if formulaC is derived from formulasA andB through an inference ruler, i.e.

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

then

${\displaystyle g_r(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 asPeano arithmetic in which one can make statements about numbers and their arithmetical relationships to each other, one can use a Gödel numbering to indirectly make statements about the theory itself. This technique allowed Gödel to prove results about the consistency and completeness properties offormal systems.

Incomputability 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 aformal language to natural numbers in such a way that the numbers can be manipulated by analgorithm 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 countablegroup, to natural numbers to allow algorithmic manipulation of the mathematical object.^{[citation needed]}

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 asTuring machines that manipulate strings rather than numbers.^{[citation needed]}

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 ahereditarily 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 ininfinitary languages.

• Church encoding
• Description number
• Gödel numbering for sequences
• Gödel's incompleteness theorems
• Chaitin's incompleteness theorem

• Nagel, Ernest;Newman, James R. (1959).Gödel's Proof.

• Hofstadter, Douglas (1979).Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books.ISBN 978-0-465-02656-2. Defines and uses an alternative Gödel numbering.
• Hofstadter, Douglas (2007).I Am a Strange Loop. Basic Books.ISBN 978-0-465-03078-1. Includes the history of Gödel'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 fromthe original(PDF) on September 27, 2016. Uses Gödel numbering to encode programs.

• Mathematical logic
• Theory of computation
• Works by Kurt Gödel

• 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