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, 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.
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 102111120121. The logical formula x=y => y=x is represented by 120061121032061062032121061120.
Gödel's encoding
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 ( x 1 , x 2 , x 3 , . . . , x n ) {\displaystyle (x_{1},x_{2},x_{3},...,x_{n})} 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:
e n c ( x 1 , x 2 , x 3 , … , x n ) = 2 x 1 ⋅ 3 x 2 ⋅ 5 x 3 ⋯ p n x n . {\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 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 s 1 s 2 s 3 … s n {\displaystyle s_{1}s_{2}s_{3}\dots s_{n}} would then be mapped to the number
… excerpt ends here. Continue reading the full article.
