Gödel numbering

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 (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, he 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 this can be done. 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:

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.

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. (Gödel 1931)

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

each formula may serve just as the very numeral of its own Gödel number.

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.

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