NationMaster - Encyclopedia: Gödel number

In Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers and contains many open problems that are easily understood even by non-mathematicians. ...formal number theory a Gödel numbering is a In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ...function which assigns to each symbol and formula of some In mathematics, logic and computer science, a formal language is a set of finite_length words (i. ...formal language a unique Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non_negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...natural number called a Gödel number (GN). The concept was first used by Kurt Gödel [ kurt gøːdl], ( April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. ...Kurt Gödel for the proof of his In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...incompleteness theorem.

Contents

1 Definition

2 Example

2.1 Step 1
2.2 Step 2
2.3 Step 3
2.4 An informal account of the proof

3 Discussion

4 Further reading

Definition

Given a In mathematics the term countable set is used to describe the size of a set, e. ...countable set S, a Gödel numbering is a function

with both f and the In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ...inverse of f a In computability theory computable functions or Turing computable functions are the basic objects of study. ...computable function.

Example

Step 1

Gödel numbers are constructed with reference to symbols of the A propositional calculus is a formal, deduction system, or proof theory for reasoning with propositional formulas as symbolic logic. ...propositional calculus and formal arithmetic. Each symbol is first assigned a Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non_negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...natural number, thus:

Logical symbols	Numbers 1:12
¬ ( ) S 0 = . +	1 ("not") 2 ("for all") 3 ("if,then") 4 ("or") 5 ("and") 6 7 8 ("is the successor of") 9 10 11 12
Propositional symbols	Numbers greater than 10 but divisible by 3
P Q R S	12 15 18 21
Individual variables	numbers greater than 10 with remainder 1 when divided by 3
v x y	13 16 19
Predicate symbols	numbers greater than 10 with remainder 2 when divided by 3
E F G	14 17 20

And so on and so forth (NB the syntax of the propositional calculus ensures that there is no ambiguity between "P" and "+", even though both are assigned the number 12).

Step 2

Arithmetical statements are assigned unique Gödel numbers referenced to the series of In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ...prime numbers. This is based on a simple code which essentially reads
prime 1 ^{character 1} * prime 2 ^{character 2} * prime 3 ^{character 3}
and so on. For example the statement
x, P(x) becomes
2² * 3¹⁶ * 5¹² * 7⁶ * 11¹⁶ * 13⁷, because
{2, 3, 5, 7, 11, ...} is the prime series, and 2, 16, 12, 6, 16, 7 are the relevant character codes. This is a large but perfectly determinate number (namely 14259844433335185664666562849653536301757812500).

Step 3

Finally, sequences of arithmetical statements are assigned further Gödel numbers, such that the sequence
Statement 1 (GN1)
Statement 2 (GN2)
Statement 3 (GN3)
gets the Gödel number 2^GN1*3^GN2*5^GN3, which we will call GN4. The proof of In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...Gödel's incompleteness theorem depends on the demonstration that, in formal arithmetic, some sets of statements logically entail or In mathematics, a proof is a demonstration that, given certain axioms, some statement of interest is necessarily true. ...prove other statements. For example it might be shown that GN1, GN2, and GN3 together, i.e. GN4, prove GN5. Because this is a demonstrable relationship between numbers it is entitled to its own symbol, for example R. Then we could write R(v,x) to express "x proves v". In the case where x and v are Gödel numbers GN4 and GN5 we would say R(GN5,GN4).

An informal account of the proof

The core of Gödel's argument is that we can write the statement

x, ¬R(v,x)

which means

no proposition of type v can be proved.

The Gödel number for this statement would be

2² * 3¹⁶ * 5¹ * 7¹⁸ * 11⁶ * 13¹² * 17¹⁶ * 19⁷

but we will call it GN6. Now if we consider the statement

x, ¬R(GN6,x),

we will realise that it says

no proposition that says 'no proposition of type v can be proved' can be proved.

This collapses into the statement

this proposition cannot be proved.

If the statement can actually be proved, then its formal system is inconsistent because it proves something which states that it itself cannot be proven (a contradiction). If the statement cannot be proved within its formal system, then what the statement asserts is actually true, so the statement is consistent, but since the formal system contains a statement which is semantically true but which cannot be proven (syntactically), then the system is incomplete. Therefore, assuming that the formal system is consistent, it has to be incomplete.

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 $s 1 s 2 s 3 ... s n$ would be mapped to the number

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 g_r 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 A self_reference occurs when an object refers to itself. ...self_referential, almost like a In mathematical logic, second_order logic is an extension of either propositional logic or first_order logic which contains variables in predicate positions (rather than only in term positions, as in first_order logic), and quantifiers binding them. ...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: A Church integer is a representation of natural numbers as functions, invented by Alonzo Church as part of his lambda calculus. ...Church number.