Gödel noted that statements within a system can be represented by natural numbers. The significance of this was that properties of statements - such as their truth and falsehood - would be equivalent to determining whether their Gödel numbers had certain properties. The numbers involved might be very long indeed, but this is not a barrier; all that matters is that we can show such numbers can be constructed. In simple terms, we devise a method by which every formula or statement that can be formulated in our system gets a unique number, in such a way that we can mechanically convert back and forth between formulas and Gödel numbers. Clearly there are many ways this can be done. Given any statement, the number it is converted to is known as its Gödel number. A simple example is the way in which English is stored as a sequence of numbers in computers using ASCII or Unicode:
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 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: According to the fundamental theorem of arithmetic, any number can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Gödel number. 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. There are more sophisticated 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 to the set of digits of a bijective base-K numeral system. A formula consisting of a string of n symbols would then be mapped to the number In other words, by placing the set of K basic symbols in some fixed order, such that the ith symbol corresponds uniquely to the ith 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=10000.
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 functiongr of natural numbers such that if formula C is derived from formulas A and B through an inference rule r, i.e. then 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:
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.
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.
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.
