Gödel's incompleteness theorems

The Gödel incompleteness theorem is one of the key phrases of modern logic. He deals with the derivability of statements in formal systems. The set shows the limits of formal systems from a certain performance. He proves that there must be sufficiently strong in systems, such as the arithmetic statements that can neither prove nor disprove formally. The theorem thus proves the impossibility of the Hilbert program, which was founded by David Hilbert, among other things, to prove the consistency of mathematics. The set was published in 1931 by the Austrian mathematician Kurt Gödel.

Specifically, two incompleteness theorems are distinguished. The first incompleteness theorem states that there is always unprovable statements in sufficiently strong non-contradictory systems. The second incompleteness theorem states that a sufficiently strong consistent systems have their own consistency can not prove it.

Through these propositions of mathematics is set a fundamental limit: Not every mathematical proposition can be (for example, arithmetic, geometry and algebra ) formally derived or disproved from the axioms of a mathematical sub-region.

In science theory and in other areas of philosophy, the set is one of the meistrezipierten mathematics. The book Gödel, Escher, Bach and the works of John Randolph Lucas are often highlighted as examples.

• 3.1 First Incompleteness
• 3.2 Second Incompleteness 3.2.1 Meaning of the Hilbert program

• 9.1 Original Publications
• 9.2 Popular introductions
• 9.3 Mathematical introductions
• 9.4 The meaning of the sentences

Basic concepts

Statements are sequences of characters that must satisfy similar to a program of a programming language of a certain syntax. For such statements can be defined in an obvious way, the concept of validity or truth in structures ( see model theory). The truth of a statement may well depend on the considered structure: A statement with the intended meaning "There is an element that is strictly greater than 0 and strictly less than 1 " For example in the structure of the real numbers, but not in the structure of the natural numbers.

A formal system is a system in which can prove mathematical statements. Each formal system consists of a language that specifies the set of well-formed formulas and statements, a set of axioms and a set of inference rules with which new statements can be derived from already proven statements. A formal system determines a theory, the set of all derivable in the system statements. What is important is that the correctness of the proof can be verified in the formal system in a mechanical manner. For example, calculi with infinitely large evidence no formal systems in this sense. In the sense of computability theory this corresponds to the formal requirement that the theory must be enumerable recursively.

A system T is called consistent or consistent if there is no statement A, so it follows from T both A and the negation (negation ) of A. This condition is, as one can easily show with ex falso quodlibet the principle, equivalent to the fact that not every statement follows from T.

A system T is called complete if for all propositions A of T the statement A or its negation follows.

Gödel sentences

First incompleteness theorem

Statement

The first incompleteness theorem states that one can not prove or disprove any statements in formal recursively enumerable systems of arithmetic:

A sufficient condition that a system is " sufficiently powerful ", is that it describes natural numbers with addition and multiplication, and let that be expressed and proved some basic properties of natural numbers therein, including, for example, that under no natural number zero and that there can be statements like, etc. or formulate.

Sketch of proof

Godel showed the sentence originally under a slightly stronger condition than the consistency, namely the ω - consistency, which is also assumed in this diagram for simplicity.

His argument uses an enumeration of all sentences within the considered formal system. Here, each set is assigned ( its Godel number ) has a unique number. Gödel then constructed a formula of the form

And shows by means of a diagonalization that n is a setting for x such that the set with the number n is equivalent to the statement

Is. He receives a set with the intuitive meaning "I'm not derivable ", the so-called Gödel sentence. This construction motivated Godel himself with the Liar paradox.

Now consider the sentence "The sentence with the number n is derivable ". Based on a proof by contradiction shows that this rate and thus the system is just as its negation derivable incomplete: Suppose that the set could be derived. Then results from the ω - consistency and strength of the system that the record with the number n can be derived. This is precisely equivalent to the negation of the sentence " The sentence with the number n is derivable ". This leads to a contradiction in the system. As this was but assumed to be consistent, the sentence can not be derived.

Suppose now that the negation of the sentence, so the sentence "The sentence with the number n is not derivable " is derived, and thus the equivalent thereto record with the number n Because the system is assumed to be sufficiently powerful to this " trace " evidence within the system, now follows that the sentence "The sentence with the number n is derivable " is derived. For this, it would have to turn the system may be contradictory. So the sentence "The sentence with the number n is not derivable " not derivable. The metalinguistic sentence, that the sentence with the number n in the system is not derivable, however, proved.

Second incompleteness

The second incompleteness theorem says that any sufficiently powerful consistent system can not prove its own consistency:

The statement follows from the first set. Let T be a consistent formal system which is so strong that in the first incompleteness theorem can be formalized and proved. Then T proves the statement. " Not provable in T" "If T is consistent, then the sentence is " I am not provable To create a contradiction, suppose T proves the statement " T is consistent". Combining the two statements, obtained by Modus Ponens in T a proof of the statement " The sentence" I am not provable " is not provable in T. " This statement, however, is equivalent to the statement "I am not provable ", are thus there is also a proof of this statement. This is a contradiction to the first incompleteness theorem. Thus T is either inconsistent, or it can not prove its own consistency.

Importance

First incompleteness theorem

Gödel's first incompleteness theorem shows that every consistent formal system containing enough statements about natural numbers is incomplete: there are true statements expressible in its language, but which are not provable. Thus, no formal system (which the assumptions of the theorem satisfied) characterize the natural numbers clearly, as more and unprovable number-theoretic statements remain.

The existence of an incomplete formal system is initially not surprising. A system can therefore simply be incomplete because not all the necessary axioms have been discovered. For example, Euclidean geometry is incomplete without the axiom of parallels; this can not be proven with the other axioms nor disproved.

Gödel's theorem shows that in theories which contain a small amount of number theory, a complete and consistent finite list of axioms can not in principle exist, and that a corresponding infinite list from a computer program can not be enumerated. According to the Church - Turing thesis can not be created by another intuitively computable algorithm such a list also. Every time a new record is added as an axiom, there are other true statements that still can not be proven with the new axiom. If an axiom is added, which makes the system completely, the system will simultaneously contradictory.

Nevertheless, there is complete and consistent quantities axiom for arithmetic, which can not be listed by an algorithm, however. For example, the set of true statements about natural numbers, a complete and consistent axiomatization of arithmetic. The difficulty here is that there is no mechanical method to prove that a statement is in this set. A similar problem arises with infinite calculi such as the Arithmetic with ω - rule, an infinite final rule that can be proven true arithmetic statements exactly. Since derivatives are infinite with the ω - rule, there is no mechanical method to verify such evidence.

The incompleteness theorem only says something for formal systems which fulfill the necessary conditions. Not all mathematically interesting axiomatic systems fulfill these requirements, even if they have models that contain the natural numbers. For example, there are complete axiomatization of Euclidean geometry, the theory of algebraically closed field of characteristic p, the dense linear orders without maximum and minimum element and the natural numbers without multiplication ( Presburger arithmetic). It is crucial that these theories are not expressive enough to represent certain essential properties over natural numbers.

Second incompleteness

Gödel's second incompleteness theorem also implies that a sufficiently strong theory T1 can not prove the consistency of a theory T2 if this proves the consistency of T1. For such a theory T1 can prove that if T2 is consistent and this proves the consistency of T1, T1 must also be consistent. Because the consistency of T1 can be formalized as " no number n is Gödel number of a proof by contradiction in T1". If T1 would be inconsistent, then T2 would prove for some n, that n is the Gödel number of a proof by contradiction in T1. But if T2 also proves the consistency of T1, it also proves that there is no such n, would be inconsistent.

This corollary of the second incompleteness theorem shows that it is not possible, such as to formalize the consistency of Peano arithmetic with finite resources, which can be formalized in a weaker theory whose consistency can prove the Peano arithmetic. For example, can the consistency of primitive recursive arithmetic ( PRA), which is often viewed as a formalization of the finite core of mathematics, prove in Peano arithmetic. Thus PRA can not prove the consistency of Peano arithmetic. The fact is often seen as proof that Hilbert's program, which would justify the mathematics of finite consistency proofs, at least not in the narrow sense of " finite " is executable.

The second incompleteness theorem makes consistency evidence is not completely impossible, only consistency proofs that can be formalized in the concerned theory itself. In particular, often are consistency proofs possible in stronger systems. Thus, the Peano arithmetic proves the consistency of weaker forms of arithmetic, Zermelo -Fraenkel set theory, the consistency of Peano arithmetic, and extensions of Zermelo -Fraenkel set theory with large cardinals prove the consistency of set theory. But such a theory is not always stronger. Thus, for Gentzen's consistency proof for Peano arithmetic in a theory formalize, which consists of the primitive recursive arithmetic and weak an axiom for the well- foundedness of the ordinal ε0. Neither of these theories proves all the statements of others, the strengths of the two theories are therefore not directly comparable.

The second incompleteness theorem is proved only for formal systems that are strong enough to formalize the proof of the first incompleteness theorem. There are consistent theories can express and prove the consistency, in particular subsystems of arithmetic, where multiplication a total function is not provable. These systems are capable of formalizing the Beweisbarkeitsbegriff, but not necessary for the first incompleteness theorem diagonalization.

Importance for the Hilbert program

Gödel replied with his incompleteness theorem to the so-called Hilbert program a serious blow. This was proposed by David Hilbert in 1921 and had a decisive influence on the research in the logic in the 1920s. It aimed to formalize the whole of mathematics through a system of axioms in first-order logic and prove the consistency of the axioms. This should concern about nonconstructive inferential in mathematics that have been expressed mainly by intuitionists, to be resolved. Hilbert suggested to prove the consistency of complex systems by that simpler systems. The motivation for this is that a proof for the consistency of a system which is given in this system itself, can not be trusted. Because of a contradiction out, everything can prove ( ex falso quodlibet ), so could be a contradiction in the system and the consistency of the system prove. Therefore, the consistency should be proved in a simpler system, so that ultimately the consistency of all of mathematics can be traced back to simple, obvious non-contradictory axioms.

After the second incompleteness theorem, it is impossible to prove the consistency of a system in itself, and therefore a fortiori, they demonstrate in a simpler system.

Philosophical interpretations

Although Gödel was repeated to detect in the course of his life as a Platonist, his incompleteness theorem has been repeatedly interpreted in a subjectivist sense. Also Gödel's participation seemed at Vienna Circle one close to the incompleteness of logical positivism to suggest the opposite Platonism in many ways. Gödel's restrained, conflict -averse nature helped to preserve these interpretations alive.

However, Gödel himself understood his sentence in particular as a blow against the propagated by Hilbert formalism in mathematics, which should ultimately make all of mathematics to a purely formal structure without reference to the " real world." However, the mathematical objects were quite "real " for Gödel as a Platonist. Although they were not to be confirmed by sensory perceptions (as it demanded the positivists ), but they were of the knowledge available. The incompleteness theorem showed for Godel, that you could not be subdued by purely formal means of this reality.

Although Gödel in his attitude towards the then significant logical positivism not very different from Ludwig Wittgenstein difference, of a reality beyond the possible importance recognized by sets ( and even more important thought as the speakable ), held Wittgenstein and Gödel her life not much from each other. In Wittgenstein's work of incompleteness is treated rather dismissively. For Wittgenstein, the rate was good for only for " logical feats ". Gödel, however, had any influence in later interviews Wittgenstein on his own thinking away from him.

Common Fallacies

The Gödel's incompleteness theorems are cited outside of mathematical logic, even outside of mathematics. It is however easy to overlook that the terminology used in the sets does not always have the importance, the terms in other contexts. In some experiments, making the results to a wider audience, this problem is not too strongly emphasized. Consequently many misconceptions about the meaning of sentences come about.

Therefore, here are some warnings against false conclusions:

• Confusion can arise from the fact that Gödel has not only proved the incompleteness theorems, but also the Gödel's completeness theorem. Here it should be noted that the notion of completeness is used in two different senses: The completeness theorem proves the semantic completeness of the first -order predicate logic, that treats a relationship between models and evidence.
• The incompleteness, however, proves that certain amounts of expressions are not completely in the sense of a theory: there are cases where neither a sentence nor its negation belong to the theory.

Examples of unprovability concrete sentences

While the unprovable statement that is constructed in the proof of the first incompleteness theorem, is rather artificial, and natural mathematical statements are known which are unprovable in natural mathematical axiom systems.

Application

To show the unprovability some statements of set theory, can sometimes directly, the second incompleteness use: If follows from a statement in a set theory that there is a model of set theory and therefore is consistent, then this statement can - consistency of the respective not be derivable - assumed set theory. Examples are the unprovability of the replacement axiom in Zermelo set theory, because it can construct the model, or the unprovable axiom of the Universe, which directly calls for the existence of certain models of ZFC.

Others

Gödel called his essay On formally undecidable propositions of Principia Mathematica and related systems I, because he was planning to write a second essay in which he wanted to explain the evidence in more detail. However, the first tower was already so great recognition that the need for a second accounted for, which was therefore never written.

Specifically, referring Gödel's essay on the Principia Mathematica, a large formal system which Bertrand Russell and Alfred North Whitehead published 1910-1913. However, Gödel showed that every system is just as susceptible to the same thickness as the Principia Mathematica.

Furthermore, Gerhard Gentzen showed that a constructive mathematics and logic is quite consistent. Here is a basic dispute of mathematics. The philosopher Paul Lorenzen has a consistent logic and mathematics developed ( Methodological constructivism), and his book metamathematics (1962 ) specially written to show that Gödel 's incompleteness is not an objection to a consistent construction of mathematics.