D1 is simply a restatement of the requirement from the proof of the first theorem that provability is weakly representable. Roughly put, D2 requires that the whole demonstration of D1 , for the candidate provability predicate ProvF, can itself be formalized inside F. Finally, D3 requires that the provability predicate is closed under Modus Ponens. If the arithmetized provability predicate indeed satisfies these conditions, the second theorem can be proved. This immediately yields the unprovability of Cons F , given the first incompleteness theorem.
|Published (Last):||23 May 2006|
|PDF File Size:||3.80 Mb|
|ePub File Size:||15.5 Mb|
|Price:||Free* [*Free Regsitration Required]|
D1 is simply a restatement of the requirement from the proof of the first theorem that provability is weakly representable. Roughly put, D2 requires that the whole demonstration of D1 , for the candidate provability predicate ProvF, can itself be formalized inside F. Finally, D3 requires that the provability predicate is closed under Modus Ponens.
If the arithmetized provability predicate indeed satisfies these conditions, the second theorem can be proved. This immediately yields the unprovability of Cons F , given the first incompleteness theorem. Furthermore, Jeroslow demonstrated, with an ingenious trick, that it is in fact possible to establish the second theorem without D3.
However, in some other cases e. However, in practise one has to establish whether a proposed arithmetized provability predicate really satisfies the conditions case by case, and typically this is long and tedious. This drawback, among other things see Feferman , led Solomon Feferman in the late s to look for an alternative line of attack to the second theorem see Feferman Feferman approaches the issue in two steps: First, he isolates the formulas ProvFOL x which arithmetize some standard notion of derivability in first-order logic in order to allow us to fix one chosen formula for provability in logic.
How the set of non-logical axioms of the system at issue are presented is left open at this stage. Secondly, Feferman looks for a suitable constraint for presenting the axioms.
Among the formulas of the language of arithmetic, he isolates what he calls PR- and RE-formulas; the former correspond to the canonical primitive recursive PR definitions in arithmetic, and the latter to existential generalizations of the former.
These two classes are easy to discriminate purely by their syntactical form. In fact, by the MRDP Theorem see below , one could—instead of RE-formulas—focus on even simpler class of existentially quantified Diophantine equations. We have above noted the important fact that in all arithmetical theories F containing Q, a set is strongly representable in F if and only if it is recursive, and a set is recursively enumerable if and only if it is weakly representable.
Furthermore, one can always take the formula weakly or strongly representing the set to be a RE-formula i. It is then natural to require that the set of non-logical axioms of the system at issue is represented by such a formula. For theories which are axiomatizable with finitely many axioms, there is a unique representation of the axioms in the form of a list, and consequently, a unique consistency statement relative to ProvFOL x. Then Cons F is not provable in F.
For still different approaches to the second incompleteness theorem, see Feferman , a; Visser Tarski clearly distinguished the object language, i. What the undefinability theorem shows is that the object language and the metalanguage cannot coincide, but must be distinct. A theory is called decidable if the set of its theorems sentences derivable in it is decidable, that is by the Church-Turing thesis recursive. Otherwise, the theory is undecidable.
Informally, being decidable means that there is a mechanical procedure which enables one to decide whether an arbitrary given sentence of the language of the theory is a theorem or not. The converse, though, does not always hold: there are incomplete theories which are decidable. Nevertheless, incompleteness at least opens the possibility of undecidability.
Moreover, all theories which contain Robinson arithmetic Q either directly, or Q can be interpreted in them are both incomplete and undecidable. Thus, for a very wide class of theories, incompleteness and undecidability go hand in hand.
One elegant and simple way of demonstrating the undecidability of extensions of Q goes, roughly, as follows: Let F be any consistent theory that contains Q. Assume then that the set of its theorems is decidable, that is by the Church-Turing thesis , recursive. Therefore, F must be undecidable. A theory F is called essentially undecidable if every consistent extension of it in the language of F is undecidable.
The above proof sketch in fact establishes that Q is essentially undecidable. There are some very weak theories that are undecidable but not essentially undecidable. Recall that Q has only finitely many axioms and let AQ stand for the single sentence consisting of the conjunction of the axioms of Q.
But then a decision procedure for first-order logic would provide a decision method for Q. The latter, however, is impossible, as it has already been shown. This undecidability result was first established by Church a, b; the method of deriving it via the undecidability of Q is due to Tarski, Mostowski and Robinson Subsequently, a number of theories and problems from different areas of mathematics have been shown to be undedicable see, e.
Georg Kreisel soon pointed out that this depends vitally on how provability is expressed; with different choices, one gets opposite answers Kreisel Above, the focus has been on expressing, inside a formal system, that the system is consistent, i.
But naturally the theory should not merely be consistent but also sound, i. How should the soundness of a system, i. If one wants to express this in the language of the system itself, it cannot be done by a single statement saying this, because there is, by the undefinability of truth, no suitable truth predicate available in the language.
The scheme can also be restricted. Exactly which instances of the reflection scheme are actually provable in the system? Hence, the instances of soundness reflection principle provable in a system are exactly the ones which concern sentences which are themselves provable in the system. However, in number theory, typically a solution is sought consisting only of integers. That makes a great difference. The former of the above equations has infinitely many solutions among real numbers, but only four among integers.
As a result of their collaboration, the first important result in this direction was achieved. Davis, Putnam, and Robinson , showed that the problem of solvability of exponential Diophantine equations is undecidable.
In , Yuri Matiyasevich added the final missing piece, and demonstrated that the problem of the solvability of Diophantine equations is undecidable. The essential technical achievement was that all semi-decidable recursively enumerable sets can be given a Diophantine representation, i. As there are semi-decidable recursively enumerable sets which are not decidable recursive , the general conclusion follows immediately: MRDP Theorem There is no general method for deciding whether or not a given Diophantine equation has a solution.
This also provides an elegant variant of the incompleteness theorems dealing with Diophantine equations: Corollary For any 1-consistent axiomatizable formal system F there are Diophantine equations which have no solutions but cannot be proved in F to have no solutions.
The question of avoiding the requirement of 1-consistency here is tricky; see Dyson, Jones and Shepherson The question then arises whether there are any simple and natural mathematical statements which are likewise undecidable in chosen basic theories, e.
There are now various specific statements with clear mathematical content which are known to be undecidable in some standard theories though, just how natural even these are has been disputed; see Feferman b. Some well known, natural examples are listed below, beginning with some quite natural mathematical statements which are independent of PA, and proceeding to more and more powerful theories.
It is often stated that before the celebrated Paris-Harrington theorem see below , no such natural independent mathematical statements were known. This is not, however, strictly speaking, correct. Already much earlier, around , Gerhard Gentzen see the entry on the development of proof theory had provided such a statement.
It is very natural to generalize the idea of induction from the domain of natural numbers to the domain of ordinal numbers. In set theory, such generalizations are called principles of transfinite induction. Though some constructivists may be sceptical about the legitimacy of full set theory, there are limited and more concrete cases of transfinite induction only dealing with some well-defined classes of countable ordinals that are perfectly acceptable even from the constructivist or intuitionist viewpoint.
Gentzen showed that the consistency of PA can be proved if this transfinite induction principle is assumed. Therefore, because of the second incompleteness theorem, the principle itself cannot be provable in PA Gentzen This provides a quite natural statement of finite combinatorics which is independent of PA.
The theorem states that every Goodstein sequence eventually terminates at 0. This is a theorem which concerns certain orderings of finite trees Kruskal Harvey Friedman showed that this theorem is unprovable even in subsystems of second-order arithmetic much stronger than PA see Simpson There are some concrete examples of mathematical statements undecided even in stronger theories which come from the so-called descriptive set theory.
This field of mathematics is related to topology and was initiated by the French semi-intuitionists Lebesgue, Baire, Borel; see the section on descriptive set theory, etc. It studies sets which possess relatively simple definitions in contradistinction to the ideas of arbitrary sets and various higher power-sets, which the semi-intuitionists rejected as meaningless called projective or analytic sets. Classically these were defined as the sets that can be built up from a countable intersection of open sets by taking continuous images and complements finitely many times; they coincide with the sets which are definable in the language of PA2.
A Borel function is defined analogously see, e. Harvey Friedman has established the following theorem: roughly, if S is a Borel set, then there exists a Borel function f such that the graph of f is either included in or disjoint from S. Friedman showed that this simple-sounding theorem is not provable even in full second-order arithmetic PA2, but proving it necessarily requires the full power of ZFC see Simpson Further, it was a traditional question of descriptive set theory a question which can be formulated in the language of second order arithmetic whether all projective sets see above are Lebesque measurable.
This remained an open problem for many decades, and for a good reason: it turned out that the statement is independent even of the full ZFC set theory see Solovay However, this case is very different. In all the above independence results the relevant statements are still theorems of mathematics, taken as shown to be true the last case, which requires large cardinal axioms that go beyond ZFC, is more controversial; still, at least many set-theoreticians find such axioms plausible.
And with the first incompleteness theorem itself, the truth of the unprovable statement easily follows, given that the assumption of the consistency of the system is indeed correct. Hilbert , on the other hand, had assumed that Peano Arithmetic and other standard theories were complete.
In his attempted proof, he needed the notion of truth. Murawski This also easily yields a weak version of the incompleteness result: the set of sentences provable in arithmetic can be defined in the language of arithmetic, but the set of true arithmetical sentences cannot; therefore the two cannot coincide. Moreover, under the assumption that all provable sentences are true, it follows that there must be true sentences which are not provable.
This approach, though, does not exhibit any particular such sentence. In particular, even the notion of truth was considered as suspicious or even nonsensical at the time, at least by some logical positivists e.
This led to the incompleteness theorems in the form that they are now known. Some important figures in the field of logic and the foundations of mathematics quite quickly assimilated the results and understood their relevance, but there was also quite a lot of misunderstanding and resistance for detailed accounts of the reception, see Dawson ; Mancosu The word quickly started to spread of these results which apparently had great importance for the foundations of mathematics—though views on what really was the moral varied.
Paul Bernays, perhaps the most important collaborator of Hilbert, showed great interest in the results, though he first had difficulties in understanding them properly. He also suggested that his methods would be applicable to standard systems of set theory however, it was only after the satisfactory characterization of decidability and the Church-Turing thesis a few years later that it was possible to give a fully general formulation of the incompleteness theorems see above ; this was first done in Kleene Zermelo seems to have had serious difficulties in understanding the relevant concepts and results.
Proof sketch for Gödel's first incompleteness theorem
Assumptions[ edit ] We work with first-order predicate calculus. Our languages allow constant, function and relation symbols. Structures consist of non-empty domains and interpretations of the relevant symbols as constant members, functions or relations over that domain. We assume classical logic as opposed to intuitionistic logic for example.
Gödel’s Incompleteness Theorems
The proof of the second incompleteness theorem is obtained by formalizing the proof of the first incompleteness theorem within the system F itself. Expressing consistency[ edit ] There is a technical subtlety in the second incompleteness theorem regarding the method of expressing the consistency of F as a formula in the language of F. There are many ways to express the consistency of a system, and not all of them lead to the same result. The formula Cons F from the second incompleteness theorem is a particular expression of consistency. Other formalizations of the claim that F is consistent may be inequivalent in F, and some may even be provable.