- Gödel number
In
mathematical logic , a Gödel numbering is a function that assigns to each symbol andwell-formed formula of someformal language a uniquenatural number called its Gödel number. The concept was first used byKurt Gödel for the proof of his incompleteness theorem.A Gödel numbering can be interpreted as an encoding in which a number is assigned to each
symbol of amathematical notation , after which a sequence ofnatural number s can then represent a sequence of strings. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic.In the time since Gödel's paper was published in 1931, the term Gödel numbering has come to be used for a variety of more general assignments of mathematical objects to natural numbers.
Gödel's encoding
Gödel used a system of Gödel numbering based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic he was dealing with.
In order 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 obtained this way can be uniquely factored into prime factors, so it is possible to effectively 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 (but more concise) ways to construct a
Gödel numbering for sequences .Lack of uniqueness
A Gödel numbering is not unique, in that for any proof using Gödel numbers, there are many ways in which these numbers could be defined.
Suppose there are "K" basic symbols. An alternative Gödel numbering could be constructed by mapping each of the basic symbols (through, say, a mapping "h") to a digit of a bijective base-"K" numeral system, so a formula consisting of a string of "n" symbols would be mapped to the number
:
Application to formal arithmetic
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 if formula "C" can be derived from formulas "A" and "B" through an inference rule "r", i.e.:then there should be some arithmetical function "gr" of natural numbers such that: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 offormal system s.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 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.
#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 machine s that manipulate strings rather than numbers.See also
*
Church numeral
*Description number
*Gödel's incompleteness theorems
* Chaitin's incompleteness theoremReferences
* Gödel, Kurt, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatsheft für Math. und Physik 38, 1931, S.173-198.
Further reading
* "", by
Douglas Hofstadter . This book defines and uses an alternative Gödel numbering.
*"Gödel's Proof " byErnest Nagel andJames R. Newman . This book provides a good introduction and summary of the proof, with a large section dedicated to Gödel's numbering.
*"I Am a Strange Loop " byDouglas Hofstadter . This is a newer book by Hofstadter that includes the history of Gödel's numbering.
Wikimedia Foundation. 2010.