|
In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). The concept was first used by Kurt Gödel for the proof of his incompleteness theorem. A numbering of the set of computable functions is sometimes called Gödel numbering or effective numbering. A Gödel numbering can be interpreted as a programming language with the Gödel numbers assigned to each computable function as the programs which calculate the values for the function in that programming language. Rogers' equivalence theorem characterizes the numberings of the set of computable functions that are Gödel numberings.
Definition Given a countable set S, a Gödel numbering is a function with both f and the inverse of f a computable function. Base notation and strings One of the simplest Gödel numbering schemes is used every day: The correspondence between integers and their representations as strings of symbols. For example, the sequence 2 3 is understood, by a particular set of rules, to correspond to the number twenty-three. Similarly, strings of symbols from some alphabet of N symbols can be encoded by identifying each symbol with a number from 1 to N and reading the string as the base N+1 representation of an integer. Gödels encoding The numbering system used in Gödel's incompleteness theorem encodes arbitrary sequences of any positive integers, which allowed Gödel to encode not just strings of symbols, but sequences of strings as well. Given a sequence of positive integers, the Gödel encoding is obtained by calculating the first n primes (), then calculating the product of these primes raised to their corresponding values in the sequence: According to the fundamental theorem of arithmetic, any code obtained this way can be uniquely factored into prime factors, so it is possible to recover the original sequence. 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. Discussion The Gödel numbering is not unique. The general idea is to map formulas onto natural numbers. An alternative Gödel numbering could be to consider each of the symbols of Step 1 to be mapped (through, say, a mapping h) to a digit of a base-22 numeral system, so a formula consisting of a string of n symbols would be mapped to the number 22^0. Also, Gödel numbering implies that each inference rule of the formal system can be expressed as a function of 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 Then, since the formal system is a formal arithmetic, which can make statements about numbers and their arithmetical relationships to each other, it follows that the system can also, by means of Gödel coding, indirectly make statements about itself: that is, a proposition of the formal system can make assertions which, when viewed through the perspective of the Gödel mapping, translate into assertions about other propositions of the same formal system, or even about itself. Thus, by this means a formal arithmetic can make assertions about itself, becoming self-referential, almost like a second-order logic. This provided Gödel (and other logicians) with a means of exploring and discovering proofs about consistency and completeness properties of formal systems. See also Further reading | ||||||||
|
| |||||||||
 |
|
| |