Theorem of incomplétude of Gödel

The theorems of incomplétude of Gödel are two famous theorems of Logique mathematics, shown by Kurt Gödel in 1931 in its article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme ( On the proposals formally indécidables of the Principia Mathematica and of the related systems ).

Introduction

Coarsely, the first theorem states that a sufficient theory to make the arithmetic one is necessarily incomplete, with the direction where there exist inevitably statements which are not demonstrable and whose negation is not either demonstrable: i.e. there exist statements on which it is known that one will be able nothing to never say within the framework of this theory. Under the same kind of assumptions on the theories considered, the second theorem affirms that there exists a statement expressing the coherence theory - the fact that it does not make it possible to show all and thus anything - and that this statement cannot be shown in the theory itself. Because of the assumptions of the theorems, any theory which claims to formalize the whole of mathematics, like the Set theory, is concerned. Does one need for as much giving up so that a mathematical speech has a value of universal truth? On what to be based to know if it is coherent, since it seems that one cannot arrive there by purely internal means at mathematics? The theorems of Gödel do not give an answer but make it possible to draw aside those which are too simple. It should already be noted that these two limitations (stated whose truth is inaccessible, coherence of the speech) are only relative, as the continuation of the article will indicate it.

These theorems, and especially their effects on the design of their discipline which the mathematicians of the time had, in particular David Hilbert and his pupils, were very unexpected. Few mathematicians first of all included/understood these theorems and what they implied. It is necessary to count among those John von Neumann, which after having assisted with first exposed of Gödel in 1930 on the first theorem of incomplétude, sent a letter to him mentioning a corollary which was the second theorem (that Gödel knew already). Paul Bernays also, close collaborator of David Hilbert, very quickly included/understood the consequences of these theorems on the designs of this last, and gave the first detailed demonstration of the second theorem in the work Grundlagen der Mathematik, (Co-signed with Hilbert). Lastly, Gödel went several times to the United States in the years 1930. Its work had a great audience near Alonzo Church and of its pupils, Stephen Cole Kleene and John Barkley Rosser, and played a big role in the birth of the Théorie of the calculability.

The second of famous the list of problems that Hilbert presented in 1900 in Paris was that of the demonstration of the coherence of the arithmetic one. All the question, which is not eluded by Hilbert, is of knowing which means one is given for such a proof. The second theorem of incomplétude watch which is needed a theory which must be “stronger” (in a direction that it would be necessary to specify) that arithmetic itself. It is generally considered that the answer brought to the second problem of Hilbert is negative. Gerhard Gentzen gave however in 1936 a proof of coherence of arithmetic, in a compatible way well-sure with the second theorem of Gödel. The proof is extremely interesting, but its significance as a proof of coherence remains debatable (see the articles on Gentzen and the Programme of Hilbert).

For better including/understanding the historical context which led Gödel to show its theorems and the impact of those at the time, to consult the article on the Programme of Hilbert.

The continuation of the article does not seek to follow exactly the contents of the article of Gödel. Some points were specified since. One starts with a presentation still a little abstract. Drafts of the evidence of the theorems, as well as precise details on their statements, are given at the end of the article.

Statements of the two theorems

The first theorem of incomplétude can be stated in a following way still a little approximate (the technical terms are explained in the following paragraph).

In any theory recursively axiomatisable, coherent and able “to formalize the arithmetic one”, one can build an arithmetic statement which can be neither proven nor refuted in this theory.

Such statements are known as indécidables in this theory. One also says independent of the theory.

Always in the article of 1931, Gödel from of deduced the second theorem from incomplétude:

If T is a coherent theory which satisfies similar assumptions, the coherence of T , which can be expressed in the theory T , is not demonstrable in T .

These two theorems were proven for the Arithmétique of Peano and thus for the theories stronger than this one, in particular the theories intended to found mathematics, such as the set theory, or the Principia Mathematica…

Conditions for application of the theorems

To fix the ideas, one considers henceforth that the theories in question are, as those which one has just mentioned (arithmetic of Peano, set theory), of the first order theories of the traditional Logique, even if the theorems of incomplétude remain valid, under the same conditions, for example in Logique intuitionalist or passing to the higher order.

  • By theory recursively axiomatisable, one hears that the theory can be axiomatized so that it is possible to recognize in a purely mechanical way the axioms among the statements of the language of the theory. It is the case obviously theories used to formalize whole or part of usual mathematics.
  • A theory is coherent if no contradiction can be proven starting from its axioms. It is also said that it is consistent or not-contradictory. For the first theorem of incomplétude, Gödel made an assumption of coherence a little stronger. The simple assumption of coherence is enough in any event for the second theorem, which states only the not-demonstrability statement of coherence. J.B. Rosser gave in 1936 a demonstration of the first theorem of incomplétude under the simple assumption of coherence. Strictly speaking, the statement of the first theorem of incomplétude given to the beginning of this article is thus not exactly that of Gödel. It is often named theorem of Gödel-Rosser.
  • A theory makes it possible to formalize the arithmetic one if, on the one hand it is possible to define (in a direction which would have to be specified) the entireties (given by zero and the function successor), with the usual operations, at least addition and multiplication, and if on the other hand a certain number of statements on the entireties are provable in the theory. The Arithmétique of Peano is such a theory, and satisfies the assumptions of the two theorems of incomplétude. In fact an arithmetic theory much weaker is enough for the first (the recurrence is primarily not useful). For the second, one needs a minimum of recurrence.
    It is remarkable that to formalize the arithmetic one, the addition and the multiplication are enough (in addition to zero and the successor). It is the very first step towards the solution of the tenth problem of Hilbert (see theorem of Matiyasevich). The addition alone is not enough: the Arithmétique of Presburger, which is the theory obtained by restricting the Arithmétique of Peano to the language of the addition (in addition to zero and the successor), is complete.

Immediate consequences of the first theorem of incomplétude

One can reformulate the first theorem of incomplétude by saying that if a theory T satisfies the useful assumptions, there exists a statement such as each of the two theories obtained one by adding to T this statement like axiom, the other by adding the negation of this statement, are coherent. Let us give in the demonstration.

Being given a statement G , let us note not G its negation. It is shown easily that a statement G is not demonstrable in T if and only if the theory T + not G (the theory T to which one adds the axiom not G ) is coherent. Indeed, if G is demonstrable in T , T + not G is obviously contradictory. Reciprocally, let us suppose T + not G contradictory. That means that, in the theory T , one can deduct from not G a contradiction. One deduced that G is consequence of T (it is a reasoning by the absurdity).

It is thus equivalent to say that a statement G is indécidable in a coherent theory T , and to say that the two theories T + not G and T + G are coherent. The statement G not being obviously indécidable in each one of these two theories, one sees that the concept of statement indécidable is by nature relative to a given theory.

Thus, if G is the statement indécidable given for T by the first theorem of incomplétude, one will have, by again applying this theorem, a new statement indécidable in the theory T + G (and thus besides indécidable also in the theory T ).

In fact, when the theorem of incomplétude applies to a theory T , it applies to all the coherent extensions of this theory, as long as they remain recursively axiomatisables: there is no average manpower to supplement such a theory.

It also should be noted that, whatever the theory concerned, Gödel showed that the statement obtained is arithmetic, i.e. one can express it in the language of the arithmetic one. It is even about a statement of arithmetic which, although tiresome to write explicitly, is logically rather simple (in a direction which will be specified at the end of the article). For example, one will obtain by the theorem of Gödel applied to the set theory of Zermelo-Fraenkel an arithmetic statement but which will be indécidable in this one.

Immediate consequences of the second theorem of incomplétude

It can be useful to include/understand the statement of the second theorem of incomplétude, to reformulate it by contraposée:

If T is a theory recursively axiomatisable which makes it possible to formalize “sufficient arithmetic”, and if T proves an expressing statement which it is coherent, then T is contradictory.

On the other hand, a theory which shows an expressing statement which it is not coherent, can not be contradictory very well, like one deduces it from the second theorem of incomplétude itself!

Let us give in a proof. Let us call cohT a statement which expresses the coherence of T in the theory T . In the same way that in the preceding paragraph for the first theorem, one reformulates the second theorem of incomplétude by saying that, under the useful assumptions on T , if the theory T is coherent, the theory T'=T + not cohT is still coherent. Let us recall that " T is not coherent " , means that there exists a proof of a contradiction in T . A proof in T is also a proof in You , which has just an additional axiom. It is thus simple to show in a theory such as T , which satisfies the assumptions of the theorem of Gödel, that not cohT has as a consequence not cohT' (let us not forget however that cohT and cohT is statements expressed in the language of these theories, it would be necessary, so that the proof is really complete, to return in detail of this representation to show this implication). One thus deduced from the second theorem of complétude, and the existence of a coherent theory T which satisfies the assumptions of this theorem -- let us take for example the arithmetic one of Peano -- the existence of a coherent theory You which shows not cohT' , namely an expressing statement which it is not coherent. Such theories are extremely fortunately pathological: one in met forever among the usual mathematical theories. This result can shock the intuition, but it should well be seen that one can reformulate the second theorem of incomplétude by saying that any coherent theory which satisfies the useful assumptions has an extension which shows the negation of its coherence.

A contrario an incoherent theory, in which all the statements are provable, will show obviously an expressing statement that it is coherent.

One sees by these various remarks that the second theorem of incomplétude does not say anything in discredit coherence of one theory to which it applies, for example the coherence of arithmetic of Peano. All that he says of the latter, it is that it can be proven only in one theory logically stronger.

Another example of simple application, but enough surprising, of the second theorem of incomplétude is the Théorème of Löb, which affirms that, in a theory T which satisfies the useful assumptions, to prove in T a statement under the assumption that this statement is provable in the theory, amounts proving the statement. In other words this assumption is useless.

Truth and demonstrability

One will introduce the concept of truth , sometimes ignored apart from mathematical, but useful logic to include/understand the theorems of Gödel. One will see that the truth is a mathematical concept, rather intuitive, but who does not formalize oneself in theories as simple as those in which demonstrability is formalized: one needs a minimum of set theory, whereas demonstrability is satisfied with the arithmetic one. The concept of truth which one will use defines mathematically (but in a stronger theory than that studied). The vocabulary used corresponds to the intuition, the concept is very convenient. But it is not need to allot an excessive value to this concept to use it. For example, Gödel builds indeed a statement which one shows that it is true in NR, which one can interpret by “one can prove it in a theory stronger than that of departure”.

The theorems of Gödel relate to theories being able to formalize the arithmetic one sufficient; to simplify, one limits oneself in addition in this paragraph to the arithmetic theories, i.e. with the theories which speak only about the entireties.

Truth in the standard model of the arithmetic one

Whereas demonstrability is defined compared to a theory, a system of axioms, the truth is defined relative with a model, a mathematical structure: a unit provided with laws and relations. So in a theory a statement can be indécidable, in a model a statement is true or false, not other alternative. We will interest we in the continuation in the truth in the standard model of arithmetic, the entireties that “everyone knows”, that one notes NR . It is a so intuitive structure which these precise details can appear superfluous. But precisely the theorem of incomplétude of Gödel shows the existence of mathematical structures which resemble curiously the entireties, for example they check all the axioms of arithmetic of Peano including the recurrence, but which are not the usual entireties, since they check a false statement in NR . Indeed, if G is a formula indécidable in T , let us take the arithmetic one of Peano for T , we saw with the preceding section that the theories T + G and T + not G are coherent. That means, according to the Théorème of complétude of same Gödel, that these theories have each one a model. These two models do not satisfy the same statements: they cannot be identical. One of them at least is thus not the standard model. When one shows the theorem of Gödel, one knows besides which of the two statements is true in the standard model (knowing that the theory T is coherent). The fact that one knows that a statement is true in the model NR , without knowing to show it in the arithmetic theory of Peano, means simply that one can show it in a stronger arithmetic theory, that one inevitably did not seek to clarify.

At the time where Gödel its theorem shows, the concept of truth is not really formalized, even if it is known of this last, puiqu' it showed in 1929 the Théorème of complétude. The definition used currently is due to Alfred Tarski, one finds it in an article published in 1956. Let us define the truth in NR . The language has for only symbol of constant 0 , for only symbols of function S (the function successor, which adds 1), + and ×, for only symbol of relation in addition to the equality, the symbol of inequality ≤.

The standard model is defined simply: the only elements of the basic whole of the model are the usual entireties, all described by the terms of the language of the form S… S 0 (where S is the sign for the function successor, " to add 1"), i.e. the well-known unary notation which corresponds to the primitive idea of entirety. The terms of the language are primarily Polynôme S with several variables and positive whole coefficients, the atomic formulas, which are the elementary statements, without logical symbol, of the polynomial equalities or inequalities. To define the model it remains to describe the closed , i.e. without variable , true and false atomic formulas .

One easily defines the truth in NR of the equalities and polynomial inequalities on the entireties (not of variable!) noted this way, and one can even make it mechanically, i.e. the truth of the atomic statements (closed equalities and polynomial inequalities) is décidable with the algorithmic direction. The algorithms concerned are primarily those of the addition and of the multiplication bases some 1, conceptually simpler than those which one teaches at the elementary school for base 10 (although probably more tiresome to use).

From there, one defined the model, and thus one with the definition by induction of the truth of an unspecified formula in this model. Without returning in the formal definition, let us observe some particular cases. First of all the truth of the formulas closed without quantifiers remains décidable: one can bring back oneself to conjunctions and disjunctions of equalities and inequalities (≠ and ≤) polynomial. Let us pass to the quantifiers, a statement of the kind ∃x (P (X) =Q (X)) where P and Q is polynomials with only one variable, is true when one can find an entirety N such as P (N) =Q (N) . Notice that if there exists such an entirety, a machine will be able to find it, by testing the entireties the ones after the others by ascending order. But the machine will not stop if there does not exist such an entirety. There is not obviously that the checking of such formulas is algorithmiquement décidable (and it is not to it).

The situation is " pire" for the universal quantifier: a statement of the kind ∀ X (P (X) =Q (X)) is true so for each entirety N , the equality P (N) =Q (N) is true: it is well defined, but, if the definition is followed, that asks for an infinity of checks! One sees well the difference between truth and demonstrability. A proof is necessarily finished, and moreover one must be able to recognize an formal evidence mechanically. To show a universal statement such as this one, usually a recurrence is made. Summarily, a proof by recurrence is a way finished representing an infinity of checks. The recurrence can " déplier" in order to build an infinity of evidence, for each entirety. However the recurrence introduces a certain uniformity into this evidence. There is no obviousness that thus one can capture the truth in NR of all the universal statements, and the theorem of Gödel precisely shows that it is not the case. The statement of Gödel, which is true in NR and nondemonstrable is precisely a universal statement, let us call the ∀ X H (X) . Let us take the case of arithmetic of Peano. When the statement precisely is defined, it is shown that for each entirety N , H (N) is provable in the arithmetic one of Peano. But one cannot show ∀ X H (X) .

Let us notice that, when one has average a mechanics to decide the truth in NR certain classes of statements, for example the statements without quantifiers, one has in particular a proof of these statements, or their negations, with the nonformal direction of this concept, without inevitably paying attention to the theory in which derives this proof. In the cases approached above, this evidence is derived indeed in the theories for which one can show the theorems of Gödel.

Truth and incomplétude

Let us recall that if one shows a statement starting from true statements in a model, the statement obtained is true in this model, and that, in a model, a statement (a closed formula) is either true or false. Consequently the theory of the true statements in NR is closed by deduction and complete. One immediately deduces from the first theorem of incomplétude that

the theory of the true statements in is not recursively axiomatisable.

and thus, the truth being closed by deduction

If T is a theory recursively axiomatisable which makes it possible to formalize " sufficient arithmétique" , and all the axioms are true in NR , there exists a statement G true in NR which is not demonstrable in T .

It is a theorem of incomplétude, weaker however than the first theorem of incomplétude of Gödel, because it applies to less of theories, the assumptions being definitely stronger. In addition one cannot formalize it directly in the arithmetic one, to deduce the second theorem from it from incomplétude. Such as it is he results besides from the Théorème of Tarski (1933), which is easier to show than that of Gödel. As the statement G nondemonstrable is true in and that the theory shows only true statements in NR , the negation of this statement is not either demonstrable. In addition as the theory T has a model, it is coherent.

It is possible however to give an assertion in this form which is really equivalent to that shown by Gödel. One can indeed specify in the statement of the theorem the logical complexity of the statement G above. Then, rather than to suppose that all the axioms of the theory, and thus finally all its theorems, are true in NR , one can be satisfied with an assumption on the axioms of the theory which has as a consequence that all the theorems of the logical complexity of the negation of G are true in NR . It is precisely the case of the assumption of coherence that made Gödel (clarified in a footnote later). Such an assertion is given at the end of the paragraph diagonalisation in the continuation of the article.

Examples of incomplete systems and statements indécidables

The existence of incomplete theories is banal. Many theories, like the theory of the groups, the rings, of the bodies, are not complete: for example one can say to the first order which a group or a body has 2 elements, or 3 elements. It is different for the arithmetic one, one would have wished to capture by axiomatic all properties of the natural entireties. For the theories intended to found mathematics, Principia Mathematica or axiomatic Set theory, one can expect not to have still discovered all the axioms. But the theorem of Gödel affirms that there will remain always statements indécidables (as long as the theory remains recursively axiomatisable).

There exist also interesting complete theories, like the Arithmétique of Presburger already evoked, the theory of the Corps algebraically closed of a given characteristic, the theory of the body real fields, and the elementary geometry which is associated for him.

Statements indécidables in the arithmetic one of Peano

Applied to arithmetic, the theorems of Gödel provide statements whose significance is completely interesting, since it is about the coherence of the theory. However these statements depend on selected coding. They are painful to write explicitly.

Paris and Harrington showed in 1977 qu ' a reinforcement of the theorem of finished Ramsey, true in NR , is not demonstrable in the arithmetic one of Peano. It is about the first example of statement indécidable in the arithmetic one which does not use coding of the language. Since, one discovered others of them. The Théorème of Goodstein is such a statement; its proof is particularly simple (when the ordinal ones are known), but uses an induction until ordinal countable the ε0. Kirby and Paris showed into 1982 that one cannot prove this theorem in the arithmetic one of Peano.

The statements of this kind which were discovered are results of combinative. Their proof is not necessarily very complicated, and there makes some is not no reason to think that there is a bond between technical complexity of a proof and possibility of formalizing this one in the arithmetic one of Peano.

Statements indécidables in set theory

In set theory, there are other statements indécidables that those provided by the theorem of Gödel which can be of different nature. Thus, according to work of Gödel, then of Paul Cohen, the Axiom of the choice and the Hypothèse of continuous the are statements indécidables in ZF the set theory of Zermelo and Fraenkel, the second being besides indécidable in ZFC (ZF plus the axiom of the choice). But on the one hand, they are not arithmetic statements. In addition, the theory obtained by adding to ZF the axiom of the choice or its negation is équi-coherent with ZF: the coherence of the one involves the coherence of the other and reciprocally. In the same way for the assumption of the continuous one. It is not the case for a statement expressing the coherence of ZF, according to precisely the second theorem of incomplétude. In the same way for one of the two statements obtained by the usual evidence of the first theorem of incomplétude (it is equivalent to a statement of coherence).

As soon as one can show in a set theory T+A , that a unit (an object of the theory) is model set theory T , i.e. the coherence of T , one deduces by the second theorem from incomplétude that, if T is coherent, has is not demonstrable in T . One shows thus that some axioms which affirm the existence of " grands" cardinals, are not demonstrable in ZFC.

Theorems of incomplétude and calculability

The concept of Calculabilité speaks for various reasons on the theorems of incomplétude. Was used it to define the assumptions of them. It intervenes in the proof of the first theorem of incomplétude (Gödel uses the primitive recursive functions). Finally incomplétude and indecidability of arithmetic are dependant.

Algorithmic Indecidability

There is a close link between algorithmic decidability of a theory, the existence of a mechanical method to test if a statement is or not a theorem, and complétude of this theory. A theory recursively axiomatisable and supplements is décidable. One can thus prove the first theorem of incomplétude by showing that a theory which satisfies the useful assumptions is indécidable. This result, the algorithmic indecidability of the theories which satisfy the assumptions of the first theorem of incomplétude, was shown independently by Turing and Church in 1936 (see Problème of the decision), by using the methods developed by Gödel for its first theorem of incomplétude. For a result of indecidability, which is a negative result, it is necessary to have formalized the Calculabilité, and to be convinced that this formalization is correct, conviction which cannot rest only on mathematical bases. In 1931, Gödel knows a model of calculation which one would say now Turing-complete, general recursive functions, described in a letter that Jacques Herbrand addressed to him, and that it specified itself and exposed in 1934. However it is not at the time convinced to have described all the calculable functions thus. Following work of Kleene, Church, and Turing, these two last stated independently in 1936 the Thèse of Church: the calculable functions are the general recursive functions.

One can be more precise by giving a restricted class of statements for which the prouvability is indécidable. If one takes again the arguments developed in the paragraph Vérité and demonstrability above, one sees for example that the class of the statements without quantifiers (and variables) is, it, décidable.

By using the arguments developed by Gödel, one shows that the prouvability of the Σ1 statements is indécidable. Without entering in detail of the definition of the Σ1 formulas (made below), that does not seem so far from a negative solution with the tenth problem of Hilbert: the existence of an algorithm of decision for the resolution of the equations diophantiennes. But one needed several tens of years and successive efforts several mathematicians of which Martin Davis, Hilary Putnam, Julia Robinson and finally Youri Matiiassevitch to arrive there in 1970 (see theorem of Matiiassevitch).

One can completely deduce the first theorem from Gödel of the theorem of Matiiassevitch. That can appear artificial, puiqu' a result of indecidability much easier to show is enough. But one can deduce some from the statements indécidables of a particularly simple form. Indeed, the theorem of Matiiassevitch is equivalent saying that the truth of the statements (closed formulas) which is written like polynomial equalities quantified existentiellement, is not Décidable. However:

  • one can mechanically recognize such statements, and thus their negations;

  • the whole as of the such true statements is Récursivement énumérable, and thus, according to the theorem of Matiiassevitch, the whole as of the such false statements is not Récursivement énumérable;

  • the whole of the theorems of a theory recursively axiomatisable is recursively énumérable (see Théorie recursively axiomatisable), and thus the whole of the theorems which are written like the negation of a polynomial equality quantified existentiellement also;

  • the assumption of coherence which Gödel for its first theorem of incomplétude makes has as a direct consequence that equalities quantified existentiellement and false cannot be demonstrable.

One from of deduced that there exist nondemonstrable true statements, which are written like the negation of a polynomial equality quantified existentiellement, or more simply like a universally quantified polynomial inequality.

A proof partial of the first theorem of incomplétude

The proof by Gödel of its first theorem of incomplétude uses primarily two ingredients:

  • coding by integers of the language and functions which make it possible to handle it, which one calls the arithmetisation of syntax ;

  • a diagonal Argument which, by using the arithmetisation of syntax, reveals a statement similar to the Paradoxe of the liar: the stated of Gödel is equivalent, via coding, with a statement affirming its clean not prouvability in the theory considered.

But the statement of Gödel is not paradoxical. It is true in NR , because if it were false, it would be provable. However this statement is of sufficiently simple logical complexity so that its prouvability in a coherent theory able to code the arithmetic one involves its truth in NR (one does not need to suppose that NR is model theory). It is thus true in NR . It is thus not provable, by definition of the statement.

To show that the negation of the statement of Gödel is not either provable, one needs an assumption of stronger coherence, as that which Gödel made. Rosser astutely modified the statement to be able to use coherence simply. With regard to the proof of Gödel the argument is the following: the statement being true, its negation is false. If it were supposed that NR is model theory, that would be enough so that it is not demonstrable. But Gödel built a statement of a sufficiently low logical complexity so that an assumption much less strong is enough: it is primarily a question of saying that such false statements cannot be demonstrable, and he can express it in a syntactic way.

The proof outlined above is taken again in a more precise way in the paragraph " diagonalisation".

Arithmétisation of syntax

At the time current, whoever knows a little data processing does not have any evil to imagine that one can represent the statements of a theory by numbers. However it is also necessary to handle these codings in the theory. The difficulty lies in the restrictions of the language: a first order theory with primarily the addition and the multiplication like symbols of function. It is the difficulty which Gödel solves to show that the prouvability can be represented by a formula in the theory.

The continuation is a little technical. In first reading, one can simplify the argumentation by supposing that NR is model of T , in which case one does not need to be attentive with the logical complexity of the statement. The part on the function β and the representation of the recurrence remains useful. One also specifies concepts, and results which were evoked or written in an approximate way above.

Codes

It can be amusing to write to oneself even codings, it is to it certainly much less lira those of the others. One thus finds much variety in the literature. The choice of coding does not have great importance, in oneself. Possibly some " manieront" more easily in the theory. As the formulas and the demonstrations can be seen like continuations finished of characters, letters, space, punctuation, and those of finished number, one can code them by a number, that being written in a base of size the number of characters necessary, or by any other means which makes it possible to code finished continuations of entireties (Gödel uses the exhibitors of the décompostion of a number in factors first). One can also use a coding of the couples (see below) to represent, finished continuations, the useful trees, and thus syntactic structures…

Σ0 formulas

A more important problem is to have functions to handle these structures, the equivalent of the programs in data processing: it is about clear that one cannot be satisfied with compositions of constant functions, additions and multiplications, i.e. of polynomials with positive whole coefficients. One will represent the useful functions by formulas. Let us see an example, in addition extremely useful for codings. The bijection of Cantor between NR × NR and NR is well-known and completely calculable: one enumerates the couples of entireties diagonal by diagonal (constant sum), for example while making grow the second component:

=… + (x+y) +y= ½ (x+y) (x+y+1) +y

This function is not represented already any more by a term of the language, because of division by 2, but it is represented by the formula (one uses " ≡" for the relation of equivalence):

z= ≡ 2z= (x+y) (x+y+1) +2y

Let us pass now to the functions of decoding, i.e. with a couple of functions opposite. One will need quantifiers:

x=π1 (Z) ≡ ∃y≤z 2z= (x+y) (x+y+1) +2y   ;         y=π2 (Z) ≡ ∃x≤z 2z= (x+y) (x+y+1) +2y

One thus represented a function, more exactly his graph (the underlined formula) by a formula of the language of the arithmetic one. The formulas above are quite particular: the first is a polynomial equality, if one replaces the three free variables by closed terms of the language, representative of the entireties ( S… s0 ), it becomes décidable. The two following ones use a quantifier limited : " ∃x≤z A" mean " there exists X smaller or equal to Z such as A". There still if one replaces the two free variables by entireties this formula becomes décidable: to check a limited existential quantification , it is enough to seek to the terminal, either one found, and the statement is checked, or one did not find and it is not it. It is not any more the case (for the second part of the assertion) if the existential quantification is not limited. One will be able to preserve this property of decidability by adding limited universal quantifications , noted " ∀ x≤ p A" (" for any X smaller or equal to p, A"). The formulas built starting from the polynomial equalities by using the usual Boolean connectors, and of the only limited quantifications are called formulas Σ0 . Notice that the negation of a Σ0 formula is Σ0.

One is easily convinced, of the arguments are given just above and to the paragraph truth and demonstrability , that the truth in NR of the closed formulas Σ0 is décidable: there is average a mechanics to know if they are true or false. To show the first theorem of incomplétude of Gödel (it is necessary a little more for Gödel-Rosser, of the recurrence for the second), the minimal condition on the theory, in addition to being recursively axiomatisable and of an assumption of coherence, is to show all the true Σ0 formulas in NR , and thus, by stability by negation of Σ0 and coherence, to show any false. It is what one understood by " to formalize sufficient arithmétique". Notice that it is an assumption on the axioms of the theory. For example the whole of the true Σ0 formulas in NR being décidable, one can choose it as system of axioms for a theory which will be well recursively axiomatisable (one can obviously simplify it). In particular one can show:

In the arithmetic one of Peano, the closed formulas Σ0 are true in NR if and only if they are demonstrable.

Result which is shown besides without truly using the axioms of recurrence of arithmetic of Peano (what is natural since there is no truly universal quantification in these statements).

Σ1 formulas

It would be quite convenient to be satisfied to handle representable functions by Σ0 formulas: truth and demonstrability are confused, these formulas are décidables, therefore the functions represented by Σ0 formulas are calculable. But the " language of programmation" induced is not rich enough. One must introduce the formulas Σ1 , which are the formulas obtained while placing an existential quantifier at the head of a Σ0 formula. In general the negation of a Σ1 formula is not equivalent to a Σ1 formula. One with the following property:

In a theory which proves all the true Σ0 formulas in NR , the true Σ1 formulas in NR are provable.

Indeed a formula Σ1 " ∃ X has x" is true in NR means that for certain entirety, that one can write " S… s0" , the formula " With S… s0" is true, but this formula is Σ0.

There exist coherent arithmetic theories, which show closed formulas Σ1 false, contrary to what occurs for Σ0. It should be specified that such arithmetic theories are rather pathological, as those which show a statement expressing their own contradiction (see beginning of the article). The assumption of additional coherence useful for the first theorem of incomplétude, which one will call Σ-coherence , it is precisely to suppose that the theory does not show any closed formula Σ1 false. One supposes that certain formulas are not demonstrable, therefore contradiction is not it: it is well an assumption of coherence at least as strong as simple coherence. It is really stronger: one can express the negation of the coherence of a theory by a Σ1 formula.

Definable functions, representable functions

A subset E of NR , or more generally of NR p is definable in arithmetic the if there exists a formula F of arithmetic with p free variables such as:

(n1,…, np) ∈ E if and only if F (n1,…, np) is true in NR

A subset E of NR p is representable in a theory T if there exists a formula if there exists a formula F of arithmetic with p free variables such as:

(n1,…, np) ∈ E if and only if F (n1,…, np) is demonstrable in T .

A function F with several variables on NR is definable in NR if its graph is defined in NR , representable in a theory You if its graph is representable in T . A unit, or a function is definable by a Σ1 formula if and only if it, or it, is representable by this formula in a Σ-coherent theory where all the Σ0 statements are demonstrable.

There exist other stronger concepts of representability, for the whole as for the functions. For that introduced here one often says slightly representable .

One will note y=f (X) a Σ1 formula defining or representing F . For the theorem of Gödel it is the concept of function or overall representable which is useful, but the concept of function or overall definable is simpler to handle, and as one is interested in the cases where they are equivalent, one goes in the continuation speech of definissability by a Σ1 formula.

One can notice that the conjunction, the disjunction of two formulas Σ1, the existential quantification of a formula Σ1, the limited universal quantification of a Σ1 formula, are equivalent in NR (one notes ≡ NR ) to a Σ1 formula:

∃x has ∨ ∃x B ≡ ∃x (has ∨ B)   ;     ∃x ∃y has (X, there) ≡ NR ∃z ∃x≤z ∃y≤z has (X, there)   ;     ∃x has ∧ ∃y B ≡ ∃x ∃y (has ∧ B)  ;     ∀x≤z ∃y has (X, there) ≡ NR ∃ U ∀x≤z ∃y≤u has (X, there).

The whole of functions at our disposal is thus stable by composition (one gives the example for a variable, one generalizes without sorrow with functions of several variables):

z=f O G (X) ≡ ∃ there ∧ y = G (X)

In a natural way is also defined:

f (X) =g (there) ≡ ∃ Z ∧ z = G (there)

However, to be able to have a sufficiently expressive language to define the useful functions on syntax, it misses a very useful concept: the definition by recurrence. The idea to obtain it is to use a coding of the finished continuations (lists of data processing). Let us suppose that we have such a coding, note l= '' the entirety which codes the finished continuation n0,…, np. It is necessary to be able to decode: let us note β (L, I) =ni the element places from there I of the continuation coded by L (the value does not have importance if I is too large). Let us suppose that we have a function G of NR in NR (an infinite succession of entireties) defined by:

G (0) =a  ;     G (n+1) =f (G (N))

and that F is definable in NR . Then one will be able to define the function G by:

y=g (X) ≡ ∃ L ∧ ∀ I < X β (L, i+1) =f (β (L, I)) ∧ y = β (L, X)

formulate which is equivalent in NR to a Σ1 formula as soon as the graph of β is Σ1. This spreads with the diagram of recurrence used for the primitive recursive functions. It is thus enough to find a Σ1 formula which defines a function β: it is the main difficulty solving for the coding of syntax.

The function β

The name of function β is taken again original article of Gödel. To define it, it had the idea to use the Théorème of the Chinese remainders: to code n1,…, np one will give p entireties first between them two to two, generated starting from one only whole D, and an entirety has whose remainders of divisions by each one of these entireties are n1,…, np. The continuation n1,…, np will thus be coded by the two entireties has and D, the entirety if one wants only one of them. Several (an infinity!) entireties will code the same continuation, which is not awkward if one thinks of the objective (to code the definitions by recurrence). The main thing is that one ensures that any finished continuation has at least a code.

Being given the entireties n1,…, np, one selected an entirety S, such as S ≥ p and for all ni, s≥ni. The entireties

d0=1+s! , d1=1+2s! ,…, dn=1+ (n+1) S!
between them two to two are then first. Moreover ni < di. By the Chinese theorem one deduces the existence from an entirety has such as for each entirety ni of the finished continuation, the remainder of the division of has by di is ni. One thus has, by posing D = S! :

β (D, has, I) =r (has, 1+ (i+1) d)  ;     z=r (has, b) ≡ z

There is well a function β defined by a Σ0 formula.

One from of deduced that:

if a function is defined by primitive recurrence starting from definable functions by Σ1 formulas, it is definable by a Σ1 formula.

One can make much things with the primitive recursive functions. Once this result obtained, the remainder is nothing any more but business of care. One can use more or less astute methods to manage the problems of connection of variables. One recursively shows that the function which codes the substitution of a term for a variable in a formula is recursive primitive, that the whole of (codes of) the evidence of a theory T axiomatisable is recursive primitive, and finally that the function which extracts from a proof the conclusion of this one is recursive primitive. To say that a formula is provable in T , it is to say that there exists a proof of this formula in T , which, coded in the theory, remains Σ1, although the predicate " to be démontrable" is not him recursive primitive, nor even recursive.

In conclusion, for a theory recursively axiomatisable T , one has two formulas Σ1, DemT (X) and z=sub (X, there) , such as:

  • DemT (⌈F⌉) is true in NR if and only if F is provable in T   ;

  • for any formula F (X) , ⌈F (n) ⌉ = sub (⌈F⌉, N), and the function sub is defined by the formula z=sub (X, there) .

One noted ⌈F⌉ the entirety which codes the formula F .

Owing to the fact that the formulas are Σ1, one can replace " vrai" by " demonstrable in T " under the sufficient assumptions.

Diagonalisation

The construction of the statement of Gödel rests on a diagonal Argument. One first of all builds the formula with a free variable Δ (X):
Δ (X) ≡ ∀z X) ⇒ DemT (Z)
who can be interpreted in NR by the formula of code X applied to his own code is not demonstrable in T , and one applies this formula to the entirety ⌈Δ⌉. One obtains G=Δ (⌈Δ⌉), a formula which says well it even as it is not demonstrable in T . One begins again by specifying it the argumentation already given to the top. It is supposed that T is recursively axiomatisable, shows all the true Σ0 formulas in NR , therefore all the true Σ1 formulas in NR , and that it is Σ-coherent.

  • Δ (⌈Δ⌉) is a closed formula, equivalent to the negation of a Σ1 formula;

  • if the formula G were demonstrable, the negation of G being Σ1 could not be true because then it would be demonstrable, and thus that would contradict the coherence of T . The formula G would be thus true in NR , which would like to say, by construction of G, which the formula G would not be demonstrable, contradiction. Thus G is not demonstrable.

  • if the negation of the formula G were demonstrable in T , by Σ-coherence it would be true, but it is false according to what precedes. Thus the negation of G is not demonstrable.

It is thus seen well, the last argument being rather tautological, as the true contents of the theorem are in the not-demonstrability of G. the first theorem of incomplétude of Gödel is thus stated as well by:

If T is a theory recursively axiomatisable, coherent, and who shows all the true Σ0 formulas in , then there exists a formula G, negation of a Σ1 formula, which is true in NR , but nondemonstrable in T .

Notice that the formula G in question is equivalent to a universal formula ∀x H (X) , where H is Σ0. This formula being true, for each entirety N (represented by S… S 0) H (N) is true, therefore demonstrable being Σ0. One thus, like announced well in the paragraph “truth and demonstrability”, a universal statement ∀x H (X) which is not demonstrable in T , whereas for each entirety N , H (N) is demonstrable in T .

Argument of the proof of the second theorem of incomplétude

The second theorem of incomplétude is proven primarily by formalizing the proof of the first theorem of incomplétude for a theory T in this same theory T . Indeed, it was shown above that, if the theory were coherent the formula G of Gödel (which depends on T ), is not provable. But the formula of Gödel is equivalent to its nonprouvability. It was thus shown that the coherence of the theory T involves G : if T is sufficient to formalize this proof, one then showed in the theory T that the coherence of the theory T involves G , formula which is not provable in T , therefore is not provable in T .

One uses simply the not-demonstrability of G , therefore the simple assumption of coherence is enough. On the other hand the theory T must inevitably be more expressive than for the first theorem of incomplétude. In particular one needs recurrence.

The conditions which must check the theory T to show the second theorem of incomplétude were specified first of all by Paul Bernays in the Grundlagen der Mathematik (1939) Co-writing with David Hilbert, then by Martin Löb, for the demonstration of sound theorem, an alternative of the second theorem of incomplétude. The conditions of demonstrability of Löb relate to the predicate of prouvability in the theory T , which one names like above DemT :

  • D1. If F is demonstrable in T , then DemT (⌈F⌉) is demonstrable in T .

  • D2. DemT (⌈F⌉) ⇒ DemT ( DemT (⌈F⌉)) is demonstrable in T .

  • D3. DemT (⌈F ⇒ G⌉) ⇒ ( DemT (⌈F⌉) ⇒ DemT (⌈G⌉)) is demonstrable in T .

The condition D1 appeared implicitly to show the first theorem of incomplétude. The second condition D2 is a formalization in the theory of D1 . Finally the last, D3 , are a formalization of the primitive logical rule known as of Modus Ponens . Let us note cohT the formula which expresses the coherence of T , i.e. the absurdity, that one notes ⊥, is not demonstrable (the negation is now noted ¬):

cohT ≡ ¬ DemT (⌈⊥⌉)

Like the negation of a formula F , ¬F , is equivalent to F involves the absurdity, F⇒⊥ , one deduces from the condition D3 that

  • Of 3 DemT (⌈¬F⌉) ⇒ ( DemT (⌈F⌉) ⇒ ¬cohT.

To deduce the second theorem from incomplétude of the three conditions of Löb, it is enough to take again the reasoning already made above. That is to say G the formula of Gödel, which, under simple assumption of coherence, involves ¬ DemT (⌈G⌉). According to D1 and the coherence of the theory T , G is not demonstrable in T (first theorem). One formalizes now this reasoning in T . Let us suppose that in T , DemT (⌈G⌉). As in addition one shows in T that DemT (⌈G ⇒ ¬ DemT (⌈G⌉) ⌉), one deduces by D3 in T , DemT (⌈¬ DemT (⌈G⌉) ⌉). Finally by Of 3 one showed ¬cohT in T . Let us recapitulate: one showed in T that DemT (⌈G⌉) ⇒ ¬cohT, i.e. by definition of G , ¬ G ⇒ ¬ cohT , and by contraposée cohT ⇒ G . However one saw that G is not demonstrable in T , therefore cohT is not demonstrable in T .

The proof of D1 was already outlined in connection with the first theorem of incomplétude: it is a question of formalizing demonstrability properly, and one uses that the closed formulas Σ1 true are demonstrable.

The condition D3 formalizes the rule of modus ponens , a rule which one may find it very beneficial to have in the formal systems for the demonstrations that one chose. It would be necessary to return in detail of coding to give the proof of D3 , but it will not be quite difficult. It is necessary to pay attention to formalizing well the result indicated in the selected theory: the variables concerned (for example there exists a X which is the code of a proof of F ) are the variables of the theory. One will need some results on the order, knowledge to show some elementary results on the evidence in the theory.

It is the condition D2 which proves to be most delicate has to show. It is a particular case of the property

  • For any closed formula F Σ1, F ⇒ DemT (⌈F⌉) is demonstrable in T

who formalizes (in T ) that any formula closed Σ1 true is demonstrable in T . One gave above no detail on the proof of this last result, T being for example the arithmetic one of Peano. If one gave some, one would realize that one does not have need for the axiom of recurrence of the theory, but that, on the other hand, one reasons by recurrence over the length of the terms, the complexity of the formulas… As it is now necessary to formalize this proof in the theory, one needs recurrence. To summarize the situation: when one seriously showed the first theorem of incomplétude for the arithmetic one of Peano, one made this proof, which is a little long, but does not present a difficulty. For the second theorem, the only thing to be made now consists in showing that this proof formalizes in the arithmetic one of Peano itself, which is intuitively relatively clear (when the proof was made), but very painful to clarify completely.

One can in makes show the second theorem of incomplétude for a theory weaker than the arithmetic one of Peano, the arithmetic primitive recursive . One extends the language in order to have symbols of function for all the recursive primitive functions, and one adds to the theory the axioms which define these functions. One restricts the recurrence with the formulas without quantifiers, with the result that those are " immédiates". The arithmetic recursive primitive is often regarded as the formalization of mathematics finitaires, with which Hilbert hoped to be able to prove the coherence of the mathematical theories.

Random links:Círdan | Park of Trenton Junction | Kouzma Petrov-Vodkine | James Nelson | Lemma of Neyman-Pearson