Proof sketch for Gödel's first incompleteness theorem

This article outlines proofs of Gödel 's incompleteness between. Here are two mathematical theorems, which are among the key findings of logic and which were proved by Kurt Gödel in 1930.

The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an algorithm that can prove all true statements about natural numbers with addition and multiplication. The second incompleteness theorem states that such a system 's own consistency can not prove it.

• 3.1 Halting Problem
• 3.2 Berry - paradox
• 3.3 Grelling -Nelson's antinomy

First incompleteness theorem

The first incompleteness theorem can be summarized as follows generally:

Here is the Robinson arithmetic (including Q ) is a weak form of arithmetic in first order predicate logic. This has the constant " zero ", the successor function, which adds intuitive to a given number one, and the functions for addition and for multiplication. It has the following axioms, the fundamental properties of natural numbers and the arithmetic operations formalize:

• Zero has no predecessor:
• 1 When x = y 1, x = y:
• Each number is zero or has a predecessor:
• Axiomatic definition of addition and multiplication:

The points on the expressions indicate here and in the rest of this paper that these terms belong to the considered language. Thus (see below ) is a formula of the considered formal system, while evidence (n, m) is a relation between natural numbers. The "numeral " a natural number N, the natural number representation of the system is denoted by, the numeral 4 is such B.The term.

In the following, it is assumed that T is the Robinson arithmetic itself. The proof can be carried out for any other system where the arithmetic can be interpreted so that all functions can be from the Robinson arithmetic as defined by expressions of the new system, just that all theorems of Robinson Arithmetic in theorems of the other system proceed. In particular, it is assumed that the axiom system is decidable. Gödel proved the sentence originally for much stronger system of Principia Mathematica. Also can be the proof of the Zermelo -Fraenkel set theory perform, the only non logical character has the element relation in which numbers can be interpreted as sets but so that all theorems of Robinson arithmetic can be interpreted as theorems of set theory. The proof can also be adapted for a merely enumerable axiom system.

The proof is divided into four parts:

Arithmetization the syntax

The main problem with the above-described embodiment, the proof initially seems to lie in that when constructing a message P, which is equivalent to " p unverifiable " p must contain a reference to p. Gödel's solution is to show that statements in such a way numbers can be assigned to the evidence of a statement can be replaced by the fact that it is checked whether the statement number assigned has a certain arithmetic property. This allows the construction of a self-referential formula avoids the infinite regress.

The first step of the proof is therefore to map formulas and finite sequences of formulas ( injective ) to natural numbers. These numbers are called Gödel numbers of formulas. Initially each symbol of the language of the arithmetic is assigned a number, similar to the ASCII code, which assigns a unique number to each character. There are several ways to do this, here is a series of numbers is directly associated with each character.

The Gödel number of a formula is obtained by concatenation of the Gödel numbers for each symbol of the formula. Each formula can be uniquely reconstructed from its Gödel number. The Gödel number of a formula F is denoted by G (F).

This Gödel numbering obtained, for example, the sentence expressing the commutative property of addition, the number of:

( the spaces are used only for readability. ) Not all numbers represent formulas, for example, is

For " " which is not a correct formula.

In the system, each natural number n is represented by her Numeral. Conversely, each numeral has a Gödel number, so is the Gödel number for the same:

The assignment of Gödel numbers can be extended to finite sequences of formulas. To obtain the number of a finite sequence of Godel formulas, the numbers of the formulas are successively written, and each separated by a zero. Since the Gödel number of a single formula never contains a zero, every formula of the sequence can be uniquely reconstructed.

It is important that the formal arithmetic can prove some simple facts. In particular, they must be able to prove that every number has a Gödel number. Likewise, they must prove that it is the Gödel number of a formula F ( x), which has a free variable, and a number m is the Gödel number of a formula F ( m), in which all occurrences are replaced x by the Gödel number of m, are, and that you can get these Godel number from the first by an effective procedure.

The Beweisbarkeitsrelation

The formal system has axioms and rules of inference, from which the formulas of the system can be proved. A formal proof is in the system is thus a chain of formulas in which each is either an axiom or can be obtained by a rule of inference from previous formulas.

Since the formal system is decidable, one can effectively decide whether a given number is Gödel number of an axiom. In the case of finite axiomatized system Q is even sufficient to check whether the number of Godel number one of the seven axioms is the same.

Rules of inference can be represented as binary relations between Godel numbers of sequences of formulas. For example, there is a rule of inference D1 through which one, S2, the formula obtained from the formulas S1. Then stating the relation R1 to this derivation rule that n if in relation to m is ( n R1m applies ) when n is the Gödel number of a list of formulas that contains S1 ​​and S2, and m is the Gödel number of a list of formulas, consisting of the formulas in the encoded list of N and further contains. Since each derivation rule is a simple formal rule, it is possible to effectively decide whether two numbers n and m are related R1.

The second step is to show that these Gödel numbering can be used to express the notion of provability. A proof of a formula S is a chain of formulas in which each one is either an axiom, or arises from previous statements by a derivation rule, and in the last statement S is. This makes it possible to define the Gödel number of a proof using the method for coding of finite sequences of formulas given above. In addition, a formula Proof ( x, y) can be defined, for two numbers x and y will be true ( and provable ), when x is the Gödel number of a proof of S, and y = G ( S).

Proof ( x, y ) is an arithmetic relationship, as well as as " x y = 6", but much more complicated. N For all the specific numbers and m is either the formula proof (m, n) or its negation proof (m, n) verifiable ( but not both). This is because the relation between the numbers can be " checked " in a simple way. The construction of the formula proof depends crucially on the assumption that the system of axioms is decidable; without this assumption the formula would not be constructed.

This can now define a formula that is " F provable " the metalinguistic statement represents: F is provable if x is a number that encodes a proof of F:

Here is " " as well as " " just an abbreviation for a certain very long arithmetic formula; the symbols " " and "" itself does not belong to the language of the system.

An important feature of the formula is that is provable if p is provable. For if p is provable, then there exists a proof with Gödel number n then is true and, as stated above, to prove. This is certainly the weaker existential proposition provable.

Formalized the results can be summarized in this section using the Ableitbarkeitssymbols:

Diagonalization

The next step is to construct a statement that asserts its own unprovable. For this purpose, can apply the Diagonallemma. This states that it comes with free variable x is a statement p in the arithmetic and stronger formal systems for every formula F ( x), so that the system equivalence

Proves. A formula that is obtained with the intuitive meaning "I have the property F (x). " For F Substituting the negation of provable (x ), we obtain the proposition p, meaning " My Godel number is the Gödel number of an unprovable formula " so ," I am unprovable ".

The formula p is not directly equal to; rather states p that, if one performs some calculation, given the number of unprovable statement. If one performs this calculation, however, shows that the resulting number is the Gödel number of p itself. This construction is similar to the following natural language statement:

This phrase does not refer directly to himself, but you get the original statement, if one carries out the specified transformation, and thus maintains the set its own unprovable. The proof of the Diagonallemmas uses a similar method.

Proof of the independence of the Gödel sentence

Assume now that the formal system ω - consistent, and therefore consistent, is. Let p be the statement, which was constructed in the preceding section.

If p were provable, then it would prove. But p is equivalent to the negation of. Thus, the system would be inconsistent because it would prove a statement and its negation. So p can not be proved, since the theory is consistent by assumption.

If the negation of p would be provable, then it would prove. But not a natural number n, the Gödel number of a proof of his p, since p is not provable. Thus, the system proves on the one hand the existence of a number with a certain characteristics, but proves on the other hand for each digit that it does not have this property. This is impossible in an ω - consistent system. Thus, the negation of p is not provable.

Thus, the statement p is undecidable: it can not be proved or disproved in the selected system. Thus, the system is ω - inconsistent or incomplete. This argument can be applied to any formal system that meets the conditions apply. This means that all formal systems that meet the requirements, ω - inconsistent or incomplete.

It should be noted that p is not proved even if the system is consistent and ω - inconsistent. The assumption of ω - consistency is only necessary to show, that the negation of p is not provable.

If you try to eliminate the incompleteness, by adding one of the unprovable formulas p or not p as an axiom, one obtains a new formal system. In this can be applied and we obtain again a statement of the form "I am not provable in the new system. " And the new system is again ω - inconsistent or incomplete the same process.

As shown in the previous section, the construction of the Gödel sentence initially allows only the proof of the incompleteness of ω - consistent systems. John Barkley Rosser showed in 1936 that the incompleteness can be shown also in consistent but ω - inconsistent systems using the same technique.

By Diagonallemma a sentence can be constructed that has the metalinguistic meaning " If there is a proof for me, then there is a shorter proof of my negation. ". This set is also known as replacement Ross R:

Suppose the system is consistent and R is provable, where there is a proof with Gödel number n. Then the system and thus proves the equivalent. As for all insertions is decidable, and the system is consistent following the adoption of this statement is also true in. Thus there exists a number m

Now, suppose that the system is consistent and the Ross replacement is refutable, there being a proof of the negation with Gödel number n. Since the system is consistent, R is not provable. Then is provable:

But this can be proved by contraposition and Modus Ponens:

Which corresponds to the replacement R Ross. This is a contradiction, since R by assumption can not be proven. So the Ross replacement is not refutable in a coherent system.

Second incompleteness

The second incompleteness theorem states:

A sufficient condition for this is "sufficiently powerful " that the proof of the first incompleteness theorem can be formalized in the system. There must be a formula Bew ( x) possess that expresses the provability in this system. In addition, this formula must satisfy the so-called Bernays - Lob - axioms. These require that the following conditions hold for all formulas F and H:

While this is in the system Q, for the first incompleteness theorem can already show, not yet fulfilled, but already in the primitive recursive arithmetic ( PRA), and even in stronger theories such as Peano arithmetic, and set theory.

By using these properties can now be formalized as follows, the first incompleteness theorem. Let F be the constructed in the proof of the first sentence statement with the meaning ". I am not provable " Then the following three statements can be derived:

• ( according to axiom 3)
• ( according to the definition of R )
• ( from the tautology by Axiom 1 and 2)

By contraposition obtained from these three sentences following sentence, corresponding to the first incompleteness theorem:

To create a contradiction, assume now that T proves its consistency, ie. This applies, ie. According to Axiom 1 then applies. But then T would be inconsistent because it is both proves. So, T, if it is consistent, the own consistency not prove.

Alternatively, the second incompleteness theorem also by the set of Loeb prove. After this is true for a system T that satisfies the Bernays - Lob - axioms, the statement only if applies. Now, if T proves its own consistency, service and setting. After the set of Loeb therefore, applies so T is inconsistent.

Alternative evidence

There are several other proofs of the incompleteness theorem known that do not require self-referential formula as opposed to Gödel's proof. Direct evidence of the first incompleteness theorem for special powerful systems such as Peano arithmetic or Zermelo - Fraenkel set the theory obtained by different Unbeweisbarkeitsresultate for mathematical statements. In addition, there are also different proofs that show how Godel's Proof by formalization of paradoxes, the incompleteness of all sufficiently powerful formal systems.

Halting problem

Alan Turing showed in 1937 that the first incompleteness theorem can be by means of computability theory show.

The halting problem is the set of Gödel numbers of pairs of Turing machines and words, so stops on input after finitely many steps. Analogously, define also for other models of computability the halting problem. Turing showed that the halting problem is not decidable. It can be shown that the halting problem is arithmetically representable, ie there is an arithmetic formula so that iff is true if keeps on typing. Suppose that the considered theory is complete and only proves true arithmetic formulas. Let be a Turing machine and given a word. Then you can browse all the evidence of the theory systematically until you find a proof for or. Since the theory is complete, one of the two formulas is exactly actually provable. Logically, therefore, could decide the halting problem, a contradiction. So there are Turing machines and words, so that is neither provable nor refutable.

Berry paradox

George Boolos showed in 1989 that the first incompleteness theorem can be proved by a formalization of the Berry paradox. This consists of the following natural language expression:

Since every non-empty set of natural numbers has a least element and because only finitely many numbers with fewer than fourteen words can be defined, defines this term a number. The paradox consists in the fact that the concrete number supposedly can not be named in less than fourteen words, but the expression has only thirteen words.

This paradox is formalized by Boolos as follows. A formula F ( x) designates the number n, if the system under consideration T proves that n is the only number with property F ( x) is:

Well there are a arithmetically definable predicate C (x, z), which is only true if an arithmetic formula with length z is the number x is calling. This can then be define the following predicates:

Now let k be the length of the formula. Then, consider the formula "x is the smallest number that can not be define k symbols with less than 10 ×. " There are only finitely many numbers with less than 10 × k symbols are defined, there must be a number n, so true, and since there is exactly one smallest number that is also true. If this formula is provable, then the number n would call. However, the formula has much less character than 10 · k, so that the formula can not be proved.

Gregory Chaitin showed in 1974 by a similar formalization of the Berry paradox that there is a number n for any formal system that proves false arithmetic statements, so can prove the system for not a number that its Kolmogorov complexity greater than n.

Grelling -Nelson's antinomy

Another proof can be obtained from the Grelling -Nelson's antinomy. A formula F ( x ) with free variable hot autologically if F ( G ( F ( x ))) is provable. Now there is an arithmetic formula GG ( x ) ( for " Godel Grelling formula" ) with the meaning ". X is the Gödel number of a car- logical formula " Now consider the formula GG ( G (GG (x ))) with meaning " the formula GG ( x ) is not autologically. " Suppose the formula is provable. But then by definition autologically GG ( x) and the system is inconsistent. So the formula GG ( G (GG (x ))) is unprovable, but as it maintains this very unprovability, also true. If the formula refutable, then the system would be similar to ω - inconsistent as in Gödel's proof, would therefore prove a false statement.