Gödel numbering

Short description: Function in mathematical logic

For numberings of the set of computable functions, see Numbering (computability theory).

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (April 2021) (Learn how and when to remove this template message)

|

This article needs additional citations for verification. Please help improve this article by adding 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 template message)

|

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.[1]: 173–198

A Gödel 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 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.

## Contents

* 1 Simplified overview
* 2 Gödel's encoding
* 2.1 Example
* 3 Lack of uniqueness
* 4 Application to formal arithmetic
* 4.1 Recursion
* 4.2 Expressing statements and proofs by numbers
* 5 Generalizations
* 6 Gödel sets
* 7 See also
* 8 Notes
* 9 References
* 10 Further reading

## 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 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 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 Template:Value.
* The logical formula `x=y => y=x` is represented by Template:Value.

## 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[1]: 179 [lower-roman 1]

Gödel 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, 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.

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 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 a Gödel numbering for sequences.

### Example

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 26 × 35 × 56 = 243,000,000.

## 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)×K(n−1)+h(s2)×K(n−2)+⋯+h(sn−1)×K1+h(sn)×K0.

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

For example, the numbering described here has K=1000.[lower-roman 2]

## Application to formal arithmetic

### Recursion

Main article: Course-of-values 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

Main article: Proof sketch for Gödel's first incompleteness theorem

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 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 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 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:

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

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

## Notes

1. ↑ Gödel's notation[1]: 176 has been adapted to modern notation.
2. ↑ For another, perhaps-more-intuitive example, suppose you have three symbols to encode, and choose bijective base-10 for familiarity (so enumeration starts at 1, 10 is represented by a symbol e.g. A, and place-value carries at 11 rather than 10: decimal 19 will still be 19, and so with 21; but decimal 20 will be 1A). Using h(sn)=n and the formula above:

(1×10(3−1)+2×10(3−2)+3×10(3−3))=(1×102+2×101+3×100)=(100+20+3)[lower-roman 3]

...we arrive at 123 as our numbering—a neat feature.

3. ↑ (or, in bijective base-10 form: 9A+1A+3)

## References

1. ↑ 1.0 1.1 1.2 Gödel, Kurt (1931). "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (in de). Monatshefte für Mathematik und Physik 38. doi:10.1007/BF01700692. http://www.w-k-essler.de/pdfs/goedel.pdf. Retrieved 2013-12-07.

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

## Further reading

* 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". FARM '13: Proceedings of the first ACM SIGPLAN workshop on Functional art, music, modeling & design: 71–76. doi:10.1145/2505341.2505348. Archived from the original on September 27, 2016. https://web.archive.org/web/20160927114325/https://blog.theincredibleholk.org/TarpitGazer/jot-visualization.pdf. Uses Gödel numbering to encode programs.

* v
* t
* e

Mathematical logic

General|

* Formal language
* Formation rule
* Formal proof
* Formal semantics
* Well-formed formula
* Set
* Element
* Class
* Classical logic
* Axiom
* Rule of inference
* Relation
* Theorem
* Logical consequence
* Type theory
* Symbol
* Syntax
* Theory

Systems|

* Formal system
* Deductive system
* Axiomatic system
* Hilbert style systems
* Natural deduction
* Sequent calculus

Traditional logic|

* Proposition
* Inference
* Argument
* Validity
* Cogency
* Syllogism
* Square of opposition
* Venn diagram

Propositional calculus
and Boolean logic

* Boolean functions
* Propositional calculus
* Propositional formula
* Logical connectives
* Truth tables
* Many-valued logic

Predicate logic|

* First-order
* Quantifiers
* Predicate
* Second-order
* Monadic predicate calculus

Naive set theory|

* Set
* Empty set
* Element
* Enumeration
* Extensionality
* Finite set
* Infinite set
* Subset
* Power set
* Countable set
* Uncountable set
* Recursive set
* Domain
* Codomain
* Image
* Map
* Function
* Relation
* Ordered pair

Set theory|

* Foundations of mathematics
* Zermelo–Fraenkel set theory
* Axiom of choice
* General set theory
* Kripke–Platek set theory
* Von Neumann–Bernays–Gödel set theory
* Morse–Kelley set theory
* Tarski–Grothendieck set theory

Model theory|

* Model
* Interpretation
* Non-standard model
* Finite model theory
* Truth value
* Validity

Proof theory|

* Formal proof
* Deductive system
* Formal system
* Theorem
* Logical consequence
* Rule of inference
* Syntax

Computability
theory|

* Recursion
* Recursive set
* Recursively enumerable set
* Decision problem
* Church–Turing thesis
* Computable function
* Primitive recursive function

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Gödel numbering. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Gödel_numbering&oldid=3986232"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template