UNILOG 2022 – Gödel’s Incompleteness Theorem revisited, par Yu Li

Texte de l’article qu’a présenté samedi ma collègue Yu Li de l’Université de Picardie, au congrès Unilog 2022 qui se tenait à Chania en Crète.

Gödel’s Incompleteness Theorem revisited

– What is the undecidable problem?

 I would rather have questions that can’t be answered than answers that can’t be questioned. – Richard P. Feynman

Yu Li * * Laboratoire MIS, Université de Picardie Jules Verne, 33 rue Saint-Leu, 80090 Amiens, France 

  1. Introduction

In a famous article written in 1931 : «  On Formally Undecidable Propositions of Principia Mathematica and Related Systems I »  [1], Kurt Gödel claimed to have proved the incompleteness of the system reported in Principia Mathematica (i.e. Peano arithmetic), and by that answered negatively the Entscheidungsproblem (the « decision problem »), a challenge put forward by David Hilbert and Wilhelm Ackermann in 1928. 

The Entscheidungsproblem was originally expressed as « Determination of the solvability of a diophantine equation », i.e., the 10th of the 23 problems proposed by Hilbert in his lecture at the International Congress of Mathematicians in Paris in 1900 [2].  Church formulated the Entscheidungsproblem as : « By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system » [3] (Copeland 2004: 45).  If it is not possible to find such a method, some propositions would be regarded as « undecidable ». Such a realisation would then establish the incompleteness of Principia Mathematica (PM).

Gödel claimed that the PM system is incomplete, as it is possible to show at least one such undecidable proposition. As a proof, Gödel gave a paradox similar in nature to the Liars paradox: a proposition Q asserting about itself that it is unprovable.It is nowadays a commonly accepted view that Gödel proved the incompleteness of the PA system, thus revealing that truth is simply bigger than proof [4].

However, Gödel’s proof of the incompleteness theorem has been continuously challenged since its publication. Let us note that as early as 1936 the logician Chaïm Perelman had drawn the attention to the fact that there wasn’t anything more to Gödel’s demonstration than the generation of a paradox [5]; and the logician Wittgenstein held a similar view [6]. Paul Jorion, a former pupil of Perelman, has claimed in a different context [7] that Gödel’s proof is marred by several other errors, due to his disdain towards the tight or lax persuasive quality of the various steps in his demonstration. Ernst Zermelo stated in a letter to Gödel in 1931 that Gödel’s proof of the existence of undecidable propositions exhibits an « essential gap » [8]. Alan Turing alluded to the errors made by Gödel without mentioning his name and ventured to fix them in his article in 1936, entitled « On Computable Numbers, with an Application to the Entscheidungsproblem » [9].

Gödel’s thesis consists of three chapters: Chapter 1 outlines the main idea of the proof; Chapters 2 and 3 formalise the idea of Chapter 1. In this paper, I focus on Chapter 1, where I examine Gödel’s proof from the perspective of a dynamic process by considering the generation of hypotheses and the reasoning from hypotheses to conclusion as an organic whole, and analyze how Gödel constructed the paradoxical proposition Q. 

I try to point out that by confusing the proof of formula with the formula, Gödel’s proof becomes an infinite regress that would have made it impossible to construct any meaningful proposition. Unfortunately, Gödel did not realize this, but introduced improper presuppositions which allow to construct the paradoxical proposition Q. Moreover, he considered Q as an undecidable proposition that exists in PM.

II. The crux of Gödel’s proof

Gödel’s proof is framed by a proof by contradiction [1] (p. 17-19), which assumes that PM is complete, according to him it means that all formulas in PM or their negations are provable; in addition, all formulas in PM can be divided into classes offormulas (class sign) and be enumerated. Gödel then resorts to Cantor’s diagonal argument to construct a paradox similar in nature to the Liar’s paradox: a proposition Q asserting about itself that it is unprovable.

Gödel enumerates accordingly all classes of formulas in PM :

R(1) : [R(1), 1] [R(1), 2] [R(1), 3]… [R(1), n] …

R(2) : [R(2), 1] [R(2), 2] [R(2), 3]… [R(2), n] …

R(3) : [R(3), 1] [R(3), 2] [R(3), 3]… [R(3), n] …

R(4) : [R(4), 1] [R(4), 2] [R(4), 3]… [R(4), n] …

R(q) : [R(q), 1] [R(q), 2] [R(q), 3]… [R(q), q] … [R(q), n] …

R(n) denotes a class of formulas and [R(n), j] denotes the jth formula of R(n). Gödel takes the formulas on the diagonal: [R(1), 1] [R(2), 2] [R(3), 3] [R(4), 4]… [R(n), n], … derives the negations of them, and defines the formula class K, K = {n|Bew¬[R(n); n]}, while Bew x means that the formula x is provable. K is actually the set of the negations of [R(n), n], K = {¬[R(1), 1],¬[R(2), 2],¬[R(3), 3],¬[R(4), 4]… ¬[R(q), q],… }.

Gödel considers that the formula class K falls within the sequence of enumerated formula classes, say corresponding to R(q). Thus, on the one hand, [R(q); q] is the formula A on the diagonal, and on the other hand, it is the formula ¬Q in K. There is a paradox: Q = ¬Q, that is, the proposition Q says about itself that it is unprovable!

The gist of our argument below, is that there exist improper presuppositions inGödel’s proof.

III. An analysis of the proof of Gödel’s Incompleteness Theorem

At the beginning of the proof, Gödel unconsciously took proof of formula as formula, which led to an infinite regress; unfortunately, Gödel was not aware of this and introduced an improper presupposition, provable formulas, which led to the paradoxial proposition Q.

  1. Proof of a formula and formula: confusion of meta-language with object language

We consider a familiar instance :

Illustration 1. Proposition P: √2 is a rational number; its negation ¬P: √2 is not a rational number.

«  √2 is not a rational number »  (¬P) cannot be proved directly, but there exists the familiar proof by contradiction to prove that «  √2 is a rational number »  (P), thus ¬P is proved to be true indirectly.

Proof :

Assume that «  √2 is a rational number » , then √2 = p/q, where p and q are both positive integers and mutually prime;

p = √2 × q, 

p^2 = 2 × q^2,

p^2 is thus even and so is p, since only the even square of an even number is even.

Since p is even, we can regard p as being the double of s : p = 2 x s

Let’s substitute 2s to p in p^2 = 2 × q^2,

(2 x s)^2 =  2 × q^2

4 x s^2 = 2 × q^2

2 x s^2 = q^2

q^2 is thus even and so is q

p and q are even numbers, thus not mutually prime, contradicting the assumption that p and q are mutually prime;

Therefore, the assumption «  √2 is a rational number » is invalid, and «  √2 is not a rational number » has been proven.

P and ¬P are the formulas about the numbers themselves; while the proof by contradiction is about the provability of P and ¬P.

The relation between the formula  and the proof of formula is generally expressed as the relation between the object language and the meta-language. What is about mathematical objects and what is about the provability of formulas are two concepts completely different in nature but intrinsically related.

However, Gödel made such a claim with surprising imprudence: « Similarly, proofs, from a formal point of view, are nothing but finite sequences of formulae (with certain specifiable properties)». In this way, the formula and the proof of formula are confused.

2. A provable formula : infinite regress and improper presumption

As Gödel shows in the end of chapter 1, the provable formula is the key concept in his proof :

« The method of proof just explained can clearly be applied to any formal system that, first, when interpreted as representing a system of notions and propositions, has at its disposal sufficient means of expression to define the notions occurring in the argument above (in particular, the notion ‘provable formula’) and in which, second, every demonstrable formula is true in the interpretation considered. » [1] (p. 19).

What is the meaning of a « provable formula » in PM? 

From common sense, a provable formula means that there exists a valid proof of this formula, that is, the provable formula concerns the existence of the proof.

In illustration 1, the proposition « √2 is not a rational number » is a provable formula since there is a valid proof by contradiction for proving that √2 is not a rational number.

Since Gödel treats the proof of formula as the formula, the provable formula in PM means that the proof is provable in PM, that is, the validity of proof can be verified in PM, which leads to an infinite regress. Lewis Carroll’s fable « What the Tortoise Said to Achilles » provides an illustration of infinite regress [10].

Suppose that « P0 is provable », that implies that there exists  P1, the proof of P0, and since P1 is treated as a formula, « P1 is provable ». Similarly, « P1 is provable »  implies that there exists P2, the proof of formula P1, and «  P2 is provable », … and so on, resulting in an infinite regress (Figure 1). 

A proof of infinite regress cannot establish any conclusion, so the verification of the validity of proof in PM becomes problematic, then the existence of proof in PM becomes problematic, and the existence of provable formulas in PM becomes also problematic.

Consequently, Gödel cannot talk about the enumeration of classes of formulas, nor about the use of diagonal method to construct the paradoxical proposition Q in PM. In other words, the paradoxical proposition Q cannot be constructed in Gödel’s proof.

But Gödel constructed the paradoxical proposition Q after all, because he presupposed the verification of the validity of proof in PM, which made the provable formula an improper presupposition.

Russell gave a simple example of an improper presupposition in « On Denoting » : « the present king of France is bald. » [11] Whether this proposition is judged to be true or false, it presupposes the existence of the present King of France, who, however, does not exist.

IV. Conclusion

The brief analysis in this paper shows that there are improper presuppositions in Gödel’s proof that enable Gödel to construct the paradoxical proposition Q as evidence for the existence of undecidability problems of PM, and thus to conclude that PM is incomplete.

Therefore, taken as a whole, the actual formulation of Gödel’s incompleteness theorem is :

PM is incomplete, because there are undecidable problems similar to the liar’s paradox in PM.

Let’s remember what Bertrand Russell once wrote in a letter to Leon Henkin: « I realised, of course, that Gödel’s work is of fundamental importance, but I was puzzled by it. […] If a given set of axioms leads to a contradiction, it is clear that at least one of the axioms must be false » [1] (p. 90)

I hope to initiate a debate :

  1. Is the paradoxical proposition Q similar to the liar’s paradox an undecidable proposition in PM? 
  2. Is Gödel’s proof valid? If not, what is a valid proof for the incompleteness of PM?
  3. By revisiting Gödel’s incompleteness theorem today, what would be the insights for us from the perspective of epistemology? What would be the insights for solving the « P vs NP » problem, as well as some underlying theoretical problems of artificial intelligence, from the perspective of algorithm theory?

Reference :

[1] S.G. Shanker (ed.), Gödel’s Theorem in Focus, Croom Helm 1988, https://pdfslide.net/documents/godels-theorem-in-focus-philosophers-in-focus.html

[2] David Hilbert, Mathematical Problems, http://aleph0.clarku.edu/~djoyce/hilbert/problems.html

[3] Brian Jack Copeland, The EssentialTuring, http://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf

[4] Casti, John L. & Werner DePauli, Gödel. A Life of Logic, Cambridge (Mass.) Perseus: 2000

[5] Jean Ladrière, Les limitations internes des formalismes. Etude sur la signification du théorème de Gödel et des théorèmes apparentés dans la théorie des fondements des mathématiques, ed. Nauwelaerts-Gauthier-Villars, Leuven-Paris, 1957, pages 140 à 142

 [6] Kreisel, G. (1958). « Wittgenstein’s Remarks on the Foundations of Mathematics ». The British Journal for the Philosophy of Science. IX (34): 135–58. doi:10.1093/bjps/IX.34.135

[7] Paul Jorion, Comment la vérité et la réalité furent inventées (Gallimard 2009)

[8] NOTE Completing the Godel-Zermelo Correspondence, https://www.sciencedirect.com/science/article/pii/0315086085900709

[9] Turing, A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2 (published 1937), 42

[10] https://en.wikisource.org/wiki/What_the_Tortoise_Said_to_Achilles

[11] https://en.wikipedia.org/wiki/On_Denoting

Partager :

175 réflexions sur « UNILOG 2022 – Gödel’s Incompleteness Theorem revisited, par Yu Li »

  1. J’ai pratiquement fini la lecture du chapitre 2 de l’article de Godel.

    Je suis surprise de voir que dans l’article de Godel ainsi que presque tous les articles qui parlent de la preuve du théorème d’incomplétude de Godel, aucun exemple n’est donné pour l’expliquer, et je ne le trouve pas normal, …

  2. Bonjour Yu Li. J’ai essayé de relire votre article un peu plus attentivement.

    1. Dans la lettre de Zermelo à Gödel que vous mentionnez, j’ai retenu :

    « In reality, the situation is quite different, and only after this prejudice has been overcome (a task I have made my particular duty) will a reasonable “metamathematics” be possible »,

    que j’interprète -peut-être abusivement- comme : il y a une imprécision dans votre preuve car vous utilisez un argument méta-mathématique. Par mon travail, je gomme cette imprécision en remplaçant « méta-mathématique » par « raisonnablement méta-mathématique ». Peut-être Zermelo veut-il dire ainsi que l’argument devient exclusivement mathématique dans le cadre de la théorie des ensembles de Zermelo et Fraenkel (ZF)? C’est en tout cas ce que je dis à PJ dans mon commentaire du 01/04 13h21.

    2. Dans la correspondance de Russell à Henkin que vous citez, le problème est pour moi de savoir si « pour chaque entier n, P(n) est vraie » équivaut ou non à « pour tout entier n, P(n) est vrai ». Je discute cette subtilité en mon commentaire du 01/04 8h46 (partie 4&5). (La formule G de Gödel vraie et non démontrable dans PA1 est de la forme ∀nH(n), H(n) étant vrai pour tout entier standard n.)

    Pour faire voir cette subtilité (la différence entre « pour chaque » (en puissance) et « pour tout » (en acte)) je propose l’exemple suivant : -dans un bureau de vote les votants votent sous le regard d’une caméra espion qui constate que chaque votant vote oui. Dans l’urne chaque enveloppe scellée contient donc « oui », mais un « oui » seulement en puissance, car, avant le dépouillement personne -autre que la caméra-espion- ne sait qu’il y a « oui » dans chaque enveloppe. C’est seulement après dépouillement que l’on sait que tous les votants ont dit « oui », ce « oui » étant alors acté par ceux habilités à rédiger ces actes (huissiers, notaires, officiers ministériels).

    Peut-être ce point est-il important pour valider ou invalider le théorème d’incomplétude? (Je n’ai pas de réponse.)
    .
    3. Si en 2 on interprète P(n) par « à l’étape n, Achille n’a pas rattrapé la tortue », alors j’ai bien peur que ce qui précède ne permette pas de résoudre le paradoxe de la course d’Achille, coursier « par récurrence ». René Thom, mathématicien, épistémologue à ses heures, ironise :

    « (…) peut-être faudra-t-il renverser l’interprétation traditionnelle des paradoxes des Eléates. Ce n’est pas le continu qui fait problème, mais bien le continu dans sa réalisation d’infini actuel, qui justifie l’infini
    dénombrable : car, n’est-ce pas, Achille finit par dépasser la tortue… ».

    4. À propos de la descente infinie. La preuve de l’irrationalité de racine carrée de 2 que vous proposez (due à Euclide?) n’est pas obtenue en supposant la rationalité vers une contradiction produite par une suite infinie « descendante », car la contradiction apparaît dès la deuxième étape. Voir (1) pour une preuve par descente infinie. Une autre preuve par descente infinie est due à Aristote (2); mais est-ce bien une preuve?

    « L’assertion d’Aristote est beaucoup plus forte, puisqu’il conclut que, sous l’hypothèse par l’absurde, les nombres impairs deviendraient pairs. Autrement dit il n’y aurait plus de nombres impairs. Et en conséquence, mais seulement dans un deuxième temps, plus de nombres du tout. ».

    1: https://fr.wikipedia.org/wiki/M%C3%A9thode_de_descente_infinie

    2: https://journals.openedition.org/philosant/2120#tocto2n2

    Bien à vous,
    BR

  3. @ Yu Li.

    À la fin de mon commentaire du 01/05 9h41 j’écrivais : « Ma question demeure. Peut-être Yu Li, très au fait du sujet, aura-t-elle l’amabilité de me répondre? ».

    Cette question se référait à mon commentaire du 30/04 11h39 :

    « Ma position actuelle -compte tenu du commentaire de PJ -est qu’il y a une peut-être une petite erreur dans le théorème de Gödel (très facile à confirmer ou infirmer), mais que cette erreur n’est pas dans la démonstration mais dans l’énoncé qui commence par quelque chose comme : « Si la théorie PA1 [P pour Peano, A pour Arithmétique, 1 pour premier ordre] est cohérente alors … » et qui doit être remplacé par l’énoncé « Si la théorie PA1 a un modèle alors… ». (Il suffit donc préciser ce qu’on entend par théorie cohérente. »

    1. J’ai pratiquement fini la lecture du deuxième chapitre du texte original de Gödel, et je suis presque certaine que la proposition « vraie mais indémontrable » construite par Gödel est au fond encore un paradoxe du menteur. Si ma lecture est correcte, alors cela suggère qu’il y a une grande erreur dans la preuve de Gödel plutôt que une petite erreur.

      Le chapitre 2 du texte original de Gödel semble difficile à lire, mais en fait, il n’est pas si difficile. Nous avons déjà beaucoup parlé de l’extérieur du théorème d’incomplétude de Gödel, nous devons maintenant nous pencher sur l’intérieur. Voulez-vous que nous (@Druuh et toutes les personnes intéressées) lisions ensemble le chapitre 2 ?

      1. @ Yu Li

        Je ne peux pas m’intéresser au chapitre 2 sans avoir lu le chapitre 1 et sans connaître l’énoncé original du théorème de Gödel par Gödel lui-même (en admettant qu’il ait été rédigé en anglais -car je ne lis pas l’allemand-). Or depuis que je suis en retraite je n’ai plus accès aux bibliothèques universitaires. Dans mon commentaire du 03/04 21h59 je vous demande seulement comment Gödel parle de la cohérence des théories auxquelles s’appliquent son théorème: cohérence syntaxique (non contradiction interne), cohérence sémantique (existence d’un modèle externe), cohérence sans autre précision.

        Ce que je fais là, je le fais pour vous aider. J’ai déjà écrit ici, à vous ou à PJ, que je n’étais plus intéressé depuis longtemps par la logique formelle en général, et donc par le théorème d’incomplétude en particulier. Ceci dit la philosophie analytique a toujours eu pour but d’éliminer les ambiguïtés du langage naturel et des principes à partir desquels on peut décider de la véracité d’une assertion formulée dans ce langage. Et cette philosophie a toujours de l’intérêt pour essayer de comprendre en quoi nous pouvons faire confiance à notre propre langage naturel (le chinois pour vous, le français pour moi)., langages qui contiennent des paradoxes : blanc-cheval-qui-n’est-pas-cheval, etc.

        Pour moi la réponse la plus profonde à cette question est celle donnée par Zermelo à Gödel (1): le théorème d’incomplétude appliqué à PA1 est correct dans ZF car, supposant ZF sémantiquement contradictoire (existence d’un modèle externe de ZF -où?-), alors on a l’existence d’un modèle standard de PA1 interne à ce modèle de ZF et l’énoncé de Gödel (restreint à PA1) est un théorème de ZF, théorie plus puissante que PA1.

        1: Voir votre note [8].

        Bien à vous,
        BR.

        1. Pour moi « presque » tout rentre dans ZF, le métalangage naturel devenant le langage de ZF et la méta-mathématique exprimée en langage naturel devient la méta-mathématique exprimée en langage de ZF, c’est-à-dire la mathématique pour les mathématiciens qui acceptent l’axiome de ZF postulant l’existence d’un ensemble infini. Ce que n’accepte peut-être pas PJ au vu de la réaction qu’il a vis-à-vis des oracles en théorie P vs NP…

          Le problème continue si on veut appliquer le théorème d’incomplétude à ZF (et non plus à PA1). Il faut, selon moi, nécessairement partir d’une théorie plus puissante que ZF dans laquelle on peut construire en interne un modèle de ZF : toute la théorie des grands cardinaux est motivée par le théorème d’incomplétude de Gödel. Et Patrick Dehornoy en était, selon moi, l’un des maîtres mondiaux;

        2. Merci pour tout !

          – Je ne peux pas m’intéresser au chapitre 2 sans avoir lu le chapitre 1 et sans connaître l’énoncé original du théorème de Gödel par Gödel lui-même.

          Je suis tout à fait d’accord ! Le chapitre 1 de l’article de Gödel est une présentation non formelle de son idée de la preuve, et le chapitre 2 est une formalisation de son idée de la preuve, donc le premier chapitre est très important à lire !

          La critique de Gödel par Zermelo est très poussée ! Dans sa lettre, Zermelo interroge explicitement sur l’existence du « problème indécidable » (vrai mais indémontrable) construit par Gödel dans le « système » de Gödel.

          La lettre de Zermelo n’est pas longue, et je la cite ici :

          ****
          Dear Mr. Godel,

          I am sending you, enclosed, a proof-sheet of my Fundumenta paper, and I would be pleased if I might count you among the few who have at least tried to take up the ideas and methods developed there and make them fruitful for their own research. While I was engaged in preparing a short abstract of my Elster lecture, in the course of which I had also to refer to yours, I came subsequently to the clear realization that your proof of the existence of undecidable propositions exhibits an essential gap. In order to produce an “undecidable” proposition, you define on page 178 a “class sign” (a propositional function of one free variable) S = R(q), and then you show that neither [R(q);q] = A nor its negation ¬A would be “provable.” But does

          S = Bew¬[R(n);n]

          really belong to your “system,” and are you justified in identifying this function with R(q), just because it is a “class sign “? I know that later on there follows a detailed theory of “class signs,” but for a critique the following consideration suffices here: in your formula (1), let the sign combination “Bew” be omitted and write instead

          n in K* = ¬[R(n);n] = S*

          If you then once more set S*=R(q*), it follows that the proposition

          A* = R(q*; q*)

          can be neither « true » nor « false »; that is, your assumption leads to a contradiction analogous to Russell’s antinomy. Just as in the Richard and Skolem paradoxes, the mistake rests on the (erroneous) assumption that every mathematically definable notion is expressible by a “finite combination of signs” (according to a fixed system!)-what I call the “finitistic prejudice.” In reality, the situation is quite different, and only after this prejudice has been overcome (a task I have made my particular duty) will a reasonable “metamathematics” be possible. Correctly interpreted, precisely your line of proof would contribute a great deal to this and could thereby render a substantial service to the cause of truth. But as your “proof” now stands, I cannot acknowledge it as binding. I wanted to impart this to you early on, to give you time to check it over.

          With best regards

          E. Zermelo

          ****
          Je pense que la question de Zermelo rejoint ce que je souhaite à éclaircir le sen de « vrai » dans notre discussion (Yu LI 25 AVRIL 2022):

          À mon avis, le terme « vrai » a deux significations :
          1, au sens existentiel : réel (vrai) et imaginaire
          2, au sens de la valeur de vérité : vrai et faux

          P.S.:
          1. La traduction en anglais de l’article de Gödel:https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf
          2. La lettre de Zermelo:https://www.sciencedirect.com › science › article › pii › pdf

          1. J’ai donné ma position -la même que celle de Zermelo je crois- dans mon commentaire de 04/04 5h41:

            « Pour moi la réponse la plus profonde à cette question est celle donnée par Zermelo à Gödel (1): le théorème d’incomplétude appliqué à PA1 est correct dans ZF car, supposant ZF sémantiquement contradictoire (existence d’un modèle externe de ZF -où?-), alors on a l’existence d’un modèle standard de PA1 interne à ce modèle de ZF et l’énoncé de Gödel (restreint à PA1) est un théorème de ZF, théorie plus puissante que PA1. ».

            Aussi je réitère ma question posée dans mon commentaire du à laquelle vous devez avoir une réponse immédiate puisque vous avez en permanence sous les yeux l’énoncé original par Gödel du théorème d’incomplétude. La question est: Gödel parle-t-il de cohérence syntaxique (cohérence interne), de cohérence sémantique (cohérence externe -où?- ou de cohérence sans préciser. Pour moi il doit s’agir de cohérence sémantique, et le modèle « standard » de PA1 doit être celui construit dans ZF, et le théorème de Gödel est alors (pour PA1 uniquement) un théorème de ZF. J’imagine que Gödel est très conscient de ça parce qu’il connaît bien le modèle « standard » de ZF, à savoir le sous-modèle des ensemble constructibles.

            Bien à vous,
            BR.

            1. Je ne pense pas que Zermelo conteste l’affirmation de Gödel concernant l’incomplétude de PA ou ZF, parce qu’il y a effectivement des « problèmes indécidables » dans PA ou ZF, comme le théorème de Goodstein qui est indécidable dans PA, et la conjecture de Collatz (qui jusqu’à présent peut être considérée comme un « problème potentiellement indécidable » dans PA ou ZF).

              La critique de Zermelo porte plutôt sur la validité de la preuve de Gödel, arguant qu’il existe un « essential gap » dans la preuve de Gödel. Si le défi de Zermelo est valable, alors ça signifie que « l’incomplétude du système formel » n’a pas été prouvée par Gödel, …

              1. @Yu Li. Dans ZF l’hypothèse du continu est indécidable (Gödel 1938 et Cohen 1963).

                Mais pourquoi ne répondez-vous pas à ma question (que je vous pose -ainsi qu’à PJ- pour la deux ou troisième fois)? La question est: dans l’énoncé original de son théorème d’incomplétude que vous avez sûrement sous les yeux, Gödel parle-t-il -à propos de PA1 ou de ZF pour fixer les idées- de cohérence syntaxique (cohérence interne), de cohérence sémantique (cohérence externe c’est-à-dire existence d’un modèle -où?-) ou de cohérence sans préciser.
                Pour moi, s’il s’agit de cohérence syntaxique, alors il y a peut-être là un « essential gap »: c’est, je crois, le point de vue que défend PJ, lorsqu’il martèle qu’il doit y avoir deux niveaux de langage, l’un « méta » par rapport à l’autre.

                PS: Bien que je sois pas du tout intéressé par l’arithmétique, je sais qu’il y a une quantité des conjectures d’arithmétique du type de celles de Polya (conjecture résolue, je l’apprends ici) ou de Collatz. Je pense qu’ici -sur ce blog- il faut se concentrer sur le théorème d’incomplétude de Gödel et sur ce qui peut intéresser les épistémologues (professionnels -ou amateurs comme PJ-). Je trouve que vous mélangez un peu tout.

                Bien à vous,
                BR

                1. Gödel a formulé « Théorème d’Incomplétude de Gödel » comme Proposition VI au Chapitre 2 de son article. (https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf)

                  Concernant sa preuve, je donne ici juste une brève description de l’idée de la preuve « magique » par Gödel, basée sur ce que j’ai compris jusqu’à présent, et j’ai besoin encore plus de temps pour la comprendre davantage.

                  D’abord, Gödel définit l’énoncé mathématique Q(x, y) :
                  Q(x, y) ≡ ¬{x Bc[Sb(y  19⁄Z(y) )]} 

                  Q(x, y) exprime : « x ne peut pas prouver y(y) ».

                  Ensuite, par la technique de substitution basée sur le codage de Gödel et des propriétés des fonctions récursives établies par Gödel, Gödel transforme « x ne peut pas prouver y(y) » en « Q ne peut pas prouver Q(Q) ».

                  Enfin, par la définition de la ω-consistance de Gödel, Gödel montre que Q est une « proposition indécidable » : Q et ¬Q sont toutes deux indémontrables. Ainsi, Gödel transforme le « paradoxe du menteur » en « théorème », …

                  Vous demandez : dans l’énoncé original de son théorème d’incomplétude que vous avez sûrement sous les yeux, Gödel parle-t-il -à propos de PA1 ou de ZF pour fixer les idées- de cohérence syntaxique (cohérence interne), de cohérence sémantique (cohérence externe c’est-à-dire existence d’un modèle -où?-) ou de cohérence sans préciser.

                  Je cite l’énoncé de Proposition VI et une explication de Gödel à la fin de Chapitre 2.

                  1. Proposition VI (p.57)

                  The general result as to the existence of undecidable propositions reads:

                  Proposition VI: For every ω-consistent recursive class c of formulae there correspond recursive class-signs r, such that neither v Gen r nor Neg (v Gen r) belongs to Flg(c) (where v is the free variable of r).

                  2. Une explication de Gödel à la fin de Chapitre 2 (p.62)

                  In the proof of Proposition VI the only properties of the system P employed were the following:

                  1. The class of axioms and the rules of inference (i.e. the relation “immediate consequence of ”) are recursively definable (as soon as the basic symbols are replaced in any fashion by natural numbers).
                  2.Every recursive relation is definable in the system P (in the sense of Proposition V).

                  Hence in every formal system that satisfies assumptions 1 and 2 and is ω-consistent, undecidable propositions exist of the form x∀ F(x), where F is a recursively defined property of natural numbers, and so too in every extension of such a system made by adding a recursively definable ω-consistent class of axioms. As can be easily confirmed, the systems that satisfy assumptions 1 and 2 include the Zermelo-Fraenkel and the v. Neumann axiom systems of set theory, and also the axiom system of number theory which consists of the Peano axioms, the operation of recursive definition [according to schema (2)] and the logical rules. Assumption 1 is in general satisfied by every system whose rules of inference are the usual ones and whose axioms (like those of P) are derived by substitution from a finite number of schemata.

                  1. Je cite encore le premier paragraphe du Chapitre 2 pour clarifier le contexte de la preuve de Godel :

                    – We proceed now to the rigorous development of the proof sketched above, and begin by giving an exact description of the formal system P for which we seek to demonstrate the existence of undecidable propositions. P is essentially the system obtained by superimposing on the Peano axioms the logic of PM (numbers as individuals, relation of successor as undefined basic concept).

                2. J’ai des questions :
                  1. cohérence = consistance ?
                  2. Pouvez-vous expliquer avec un exemple : qu’est-ce que la cohérence syntaxique (cohérence interne), la cohérence sémantique (cohérence externe) ?

                    1. Votre question sur la cohérence est très importante ! Gödel utilise la « ω-consistance » dans sa preuve, qui est l’une des clés de sa preuve.

                      Dans sa preuve de la proposition 6, Gödel explique la ω-consistance comme suit :

                      ******
                      Let c be any class of formulae. We denote by Flg(c) (set of – consequences of c) the smallest set of formulas which contains all the formulae of c and all axioms, and which is closed with respect to the relation “immediate consequence of ”. c is termed ω-consistent, if there is no class-sign a such that:

                      (n)[Sb(a  v⁄Z(n) ) ∈ Flg(c)] & [Neg(v Gen a)] ∈ Flg©

                      where v is the free variable of the class-sign a.

                      Every ω-consistent system is naturally also consistent. The converse, however, is not the case, as will be shown later.

                      ******
                      Ma compréhension préliminaire de la formule ci-dessus est que :
                      Tout a(n) peut être prouvé dans c, alors que pour tout n, a(n) ne peut être prouvé dans c. Lorsque cela se produit, Gödel dit que le système n’est pas « ω-consistant ».

                      Ma question est :
                      – selon la distinction entre la cohérence syntaxique et la cohérence sémantique,  » ω-consistant  » est plutôt une cohérence sémantique ?

                    2. Bonjour Yu Li,

                      J’ai commencé à parcourir l’article de Gödel dont vous m’avez envoyé le lien. J’essaye de lire la traduction anglaise de son article -je pratique mal l’anglais et, surtout, je suis incapable de penser en anglais (j’ai déjà du mal en français…)-. Je défriche l’article !avec l’idée que Gödel voulait montrer la supériorité de la démontrabilité sur la vérité (idée que l’on retrouve jusqu’à la fin de sa vie où il a cherché à démontrer l’existence de Dieu), et je remarque dans ce sens que, en fin d’introduction, le traducteur en anglais du texte allemand répertorie les symboles que Gödel utilise pour représenter les concepts méta-mathématiques qu’il utilise et que les concepts de vérité et de vrai n’y figurent pas.

                      Je suis d’accord avec votre 09/05 11h20 : la notion de ω-cohérence est importante. Dans (1) il est écrit (en français…):

                      « D’un point de vue sémantique, dans la définition ci-dessus le n fait référence à un entier standard, qui renvoie à un entier « ordinaire » (un entier du méta-langage dans lequel on raisonne sur la théorie) ».

                      Un adage français dit: « Chassez le naturel il revient au galop! ». Une variante pour Gödel -variante qui ne déplaira peut-être pas à PJ-: « Chassez le méta-langage, il revient au galop? ».

                      Bien à vous,
                      BR.

                      1: https://fr.wikipedia.org/wiki/Th%C3%A9orie_om%C3%A9ga-coh%C3%A9rente

  4. Je voudrais présenter la conjecture de Polya en rapport avec le code de Gödel, qui nous permet de méditer plus profondément sur des concepts tels que la vérité, la réalité et la démontrabilité etc.

    Conjecture de Pólya

    La conjecture de Pólya a été proposée par le mathématicien hongrois George Pólya (1887 – 1985) en 1919.

    Pendant longtemps, on a cru que la conjecture de Polya était correcte. Ce n’est qu’en 1958 que Haselgrove a prouvé théoriquement l’existence d’un nombre infini de contre-exemples.

    En 1960 Lehman a trouvé un contre-exemple concret : 906 180 359, réfutant ainsi la conjecture de Polya.

    La conjecture de Pólya énonce que pour tout entier n supérieur à 2, si l’on divise les entiers naturels inférieurs ou égaux à n (en ne comptant pas 0) entre ceux qui ont un nombre impair de facteurs premiers et ceux qui en ont un nombre pair, alors le premier ensemble a plus (ou autant) d’éléments que le second.

    Il faut noter que les facteurs premiers sont comptés autant de fois qu’ils sont répétés. Ainsi, 18 = 21 × 32 a 1 + 2 = 3 facteurs premiers, alors que 17 = 17^1 a 1 facteur premier.

    Par exemple :

    18 = 2^1 × 3^2 : 3 prime factors i.e. an odd number
    17 = 17^1 : 1
    16 = 2^4 : 4
    15 = 3 x 5 : 2
    14 = 2 x 7: 2
    13 = 13 : 1
    12 = 2^2 x 3 : 3
    11 = 11 : 1
    10 = 2 x 5 : 2
    9 = 3^2 : 2
    8= 2^3 : 3
    7 = 7 : 1
    6 = 2 x 3 : 2
    5 = 5 : 1
    4 = 2^2 : 2
    3 = 3 : 1
    2 = 2 : 1

    L’ensemble des entiers naturels qui ont un nombre impair de facteurs premiers :
    18, 17, 13, 12, 11, 8, 7, 5, 3, 2 : 10
    L’ensemble des entiers naturels qui ont un nombre pair de facteurs premiers :
    16, 15, 14, 10 9, 6, 4, 1 : 8

    Référence :
    https://en.wikipedia.org/wiki/Pólya_conjecture

  5. @Yu Li. Si vous êtes plus intéressée par l’épistémologie et la philosophie des sciences que par la technique (ce que je crois), alors il faudra que vous alliez regarder du côté de la théorie des ensembles (ZFC), et en particulier du coté de la théorie des grands cardinaux (en rapport quasi-direct avec le théorème d’incomplétude)

    En philosophie occidentale, il y a la célèbre injonction de Socrate: « Connais-toi toi-même ». Dans ZFC cette introspection est impossible: il n’y a pas d’injection élémentaire stricte d’un modèle de ZFC dans lui-même. Mais en rajoutant l’hypothèse de cardinaux de plus en plus grands (les cardinaux de Laver sont actuellement les plus grands(?)), c’est-à-dire en complétant ZFC de plus en plus, on approche de plus en plus cette introspection.

    Patrick Dehornoy était l’un des spécialistes du sujet : https://www.lmno.cnrs.fr/archives/dehornoy/Books/Ensembles/chapLV.pdf (les repères chronologiques et le résumé du chapitre sont à la fin).

  6. @BasicRabbit Un adage français dit: « Chassez le naturel il revient au galop! ».

    Il existe un adage similaire en chinois: « 江山易改,本性难移 »(Il est facile de changer les rivières et les montagnes, mais difficile de changer le naturel).

    Le théorème d’incomplétude de Gödel, résultat si important, existe depuis de nombreuses années, mais il est difficile de voir Gödel engager un dialogue direct avec les gens au sujet de sa thèse de son vivant. Il est remarquable que Zermelo ait lancé un dialogue constructif avec Gödel en 1931, qui s’est malheureusement terminé peu après par Gödel, comme le commente le wiki (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Criticisms):

    – In September 1931, Ernst Zermelo wrote to Gödel to announce what he described as an « essential gap » in Gödel’s argument. In October, Gödel replied with a 10-page letter, where he pointed out that Zermelo mistakenly assumed that the notion of truth in a system is definable in that system (which is not true in general by Tarski’s undefinability theorem). But Zermelo did not relent and published his criticisms in print with « a rather scathing paragraph on his young competitor » (Grattan-Guinness, pp. 513). Gödel decided that to pursue the matter further was pointless, and Carnap agreed (Dawson, p. 77). Much of Zermelo’s subsequent work was related to logics stronger than first-order logic, with which he hoped to show both the consistency and categoricity of mathematical theories.

    Je pense que la preuve de Gödel comporte trois ingrédients importants : le méta-langage, les fonctions récursives et la ω-cohérence. On ne peut éviter des discussions de ces concepts : Chassez le naturel il revient au galop, …

    1. @Yu Li. Pour moi on voit bien où et comment intervient la ω-consistance dans la remarque de la fin de la page 300 de (1):

      « Dans la démonstration ci-dessus |4.4.4 (et 4.4.5 dans le cas particulier où T=PA1)], la dissymétrie entre ∆ et ¬∆ provient de l’impossibilité de passer directement de T ⊢ Prouvable T ( ‘Φ’ ) à T ⊢ Φ, forçant à utiliser l’hypothèse, a priori plus forte, que T est ω-consistante. En effet, la relation T ⊢ PreuveT(S’Φ’0,Sp0) pour un entier (standard) p implique T ⊢ Φ, mais la relation T ⊢ ∃ y (PreuveT(S’Φ’0,y)), elle, ne garantit pas l’existence d’un tel entier : ».

      (Pour moi utiliser le théorème de complétude permet de voir apparaître sémantiquement (une « vraie » preuve nécessite que ‘Φ’ soit un entier standard) des difficultés très difficiles à voir syntaxiquement.)

      Pour moi on voit dans cette démonstration la différence de niveau de langage qui permet de transformer un paradoxe (celui du menteur) en un théorème (explication ci-dessus complétée par la fin de la remarque p.301), levant (à mon avis…) l’objection majeure de PJ.

      1: https://www.lmno.cnrs.fr/archives/dehornoy/Books/Ensembles/chapLI.pdf

  7. @BasicRabbit

    “Je défriche l’article avec l’idée que Gödel voulait montrer la supériorité de la démontrabilité sur la vérité (idée que l’on retrouve jusqu’à la fin de sa vie où il a cherché à démontrer l’existence de Dieu)”

    Mais dans le livre de Casti & DePauli, il a dit « What Gödel discovered is that even if there exist true relations among pure numbers, the methods of deductive logic are just too weak for us to be able to prove all such facts. In other words, truth is simply bigger than proof » (voir l’article de Paul dans ce blog).

    Qu’a dit Godel ? Que pense-t-on qu’il ait dit ?

    Il me semble que la meilleure façon de savoir ce que Godel a dit réellement est de lire son texte original.

    « J’ai commencé à parcourir l’article de Gödel dont vous m’avez envoyé le lien. » Bravo!

    1. Yu Li: « Il me semble que la meilleure façon de savoir ce que Gödel a dit réellement est de lire son texte original ».

      C’est votre problème (et celui de PJ) de savoir si l’énoncé et la démonstration « historique » de Gödel sont corrects. Ce qui m’intéresse à la rigueur c’est de savoir si les théorèmes d’incomplétude actuels -dans lesquels les hypothèses ont été beaucoup affaiblies et les démonstrations beaucoup simplifiées et clarifiées- sont corrects. J’ai tendance à croire que la réponse à cette question est oui, et que les différences entre démontrabilité et vérité, et entre langage et méta-langage, sont maintenant bien comprises en logique formelle.

  8. @ Druuh. J’ai dit à Yu Li tout ce que je pouvais dire sur le sujet (et je vois que je commence à radoter). À vous de prendre le relais :

     » 30 avril 2022 à 14 h 32 min
    Chers tous,
    je vais prendre le temps nécessaire pour lire tout ceci. Mes activités professionnelles m’engloutissent en ce moment, je mettrai donc peut être quelques jours. Je pense en effet que le dialogue de sourds qui s’est instauré entre moi et vous Mr Jorion est en partie dû au fait que je n’ai pas suffisamment essayé de comprendre votre point de vue, ce que je vais m’efforcer de faire mieux maintenant. » .

    @PJ. À vous aussi de prendre le relais quand vous serez remis sur pied(s?):

     » 1 mai 2022 à 19 h 33 min
    N’interprétez pas mon silence relatif dans les jours qui viennent pour du désintérêt ».

    1. « Chassez le naturel il revient au galop!  »

      Je trouve que cet adage exprime parfaitement une esprit selon lequel il ne faut pas essayer de changer les idées des gens.

      Ainsi, lorsque nous échangeons des idées, il ne s’agit pas de changer les idées de l’autre, mais de prendre conscience de ce que nous ne voyons pas et de nous compléter.

      Nous avons eu des dialogues tellement riches jusqu’à présent, et je le trouve génial ! N’hésitez pas à faire une retraite.

      1. Yu Li : « N’hésitez pas à faire une retraite. ».

        Notre Napoléon, empereur des français -autoproclamé et autocouronné- a fait une piteuse retraite de Russie. Après un séjour à l’île d’Elbe il a fait un retour (« Les Cent jours ») qui s’est achevé à Waterloo où la coalition européenne l’a contraint de se retirer définitivement à l’île de Sainte Hélène.

        En français retour et retraite n’ont pas le même sens…

        1. Par « retraite », j’entends une retraite spirituelle, c’est-à-dire une retraite réguliere et suffisante de notre vie quotidienne afin de nous recentrer et de répondre aux besoins profonds de notre esprit.

          1
          1. Ce « retour » n’était pas forcément celui qu’attendait Basic Rabbit dans sa retraite …

            Mais on ne va pas chinoisé .

            1. @ Juannessy. Bonjour (ça fait une paille).

              1. Exact: je n’avais pas pensé à ce genre de retraite.

              2. En français, quand deux verbes se suivent, on met -en général- le second à l’infinitif. N’oublions pas que nous sommes lus par une chinoise.

              1. Vous avez raison , et à ma courte honte , j’ai perdu la face devant Yu Li .

                Je fais une retraite de 8 jours pour la retrouver .

                    1. Et il en manque une sur « re traite » , que j’ai suggérée en parlant d e reblochon , de « re blocher », soit traire une seconde fois les vaches , cette astuce qu’avaient trouvé les paysans savoyards pour se faire un petit complément de ressource qui échappait aux calculs du seigneur .

                      @Yu Li : Bonjour et pardon pour les petites facéties échangées avec Alice Basic Rabbit , mais je suis émerveillé que vous ayez pu « sentir » et « comprendre  » la moitié de nos jeux de mots , ce que l’on appelle  » co naître  » ( Zhidào ?)

                      Je n’ai plus ( et n’ai jamais vraiment eu dans mes vies antérieures ) la capacité de suivre vos riches et fructueux échanges avec BasicRabbit et Paul Jorion . C’est la faute à un professeur de physique de mathématiques spéciales qui au début des années 1960 avait pour coutume de donner un premier devoir ( costaud ) qu’il annonçait noter comme ça le valait vraiment , le seul de l’année où la note serait juste , à l’aune de la rigueur que les sciences exigent .

                      Je me souviens que le problème portait sur la fameuse relation d’Einstein E = € MC2 (  » euro pour epsilon …) , et les équations aux dimensions , ainsi que sur le choix des unités importantes des grandeurs physiques . Je m’étais passionné pour le sujet , et j’avais passé le samedi et le dimanche sur mon devoir en rendant presque une quinzaine de pages grand format .

                      Nous étions 33 élèves en classe .Lors de la restitution des devoirs les notes s’échelonnaient entre  » 5 /20 « et  » – 35/20″.
                      Pour ma part j’avais la cinquième meilleure note avec 0,5/ 20 , et une appréciation dont je me souviens encore :  » peut être doué pour la métaphysique , mais pas pour la physique « . Il m’a bien fallu deux semaines pour m’en remettre , sans me décourager de poursuivre mes études .Aujourd’hui , les parents d’élèves demanderaient la révocation du professeur, mais on avait la peau plus dure et la formation plus spartiate , à cette époque .

                      C’est ce qui m’a permis de me cantonner aux mathématiques appliquées plus qu’aux mathématiques pures , et me permet de saluer le bonheur de votre heureuse présence sur le blog .

        2. @Basic Rabbit:

          ça m’avait aussi paru bizarre .

          Signé: un retraité de retour , mais qui , bien que savoyard d’adoption , n’aime pas le  » reblochon » .

          ( mais ça doit encore être dans la relation entre métalangage et langage objet )

  9. Pour la route…

    « Le vrai, le faux, l’insignifiant » par Alain Chenciner (1). À parcourir, en particulier le paragraphe 5 intitulé « Du faux lorsqu’il se révèle fécond. »

    Paragraphe applicable à Gödel ?

    Wikipédia : « Ainsi, cette recherche de démonstrations de cohérence, apparemment rendue vaine par les théorèmes d’incomplétude, fut au contraire extrêmement fructueuse en posant les bases de la théorie de la démonstration moderne. » (2) ;

    Gaspard des montagnes : « … de mon point de vue il n’y a que 2 types de problème : ceux que l’on a déjà résolus et ceux que l’on devra résoudre dans le futur, évitons de mettre des verrous sur des portes que l’on a pas encore vu, pu ou su ouvrir. Et comme disait Mark Twain « Ils ne savaient pas que c’était impossible, alors ils l’ont fait. » (3) .

    1: https://perso.imcce.fr/alain-chenciner/Vrai_faux_insignifiant.pdf

    2: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del#G%C3%A9n%C3%A9ralisations_et_conjectures

    3: https://www.pauljorion.com/blog/2022/05/07/video-p-vs-np-problemes-solubles-et-insolubles/

  10. Comme nous avons discuté, la « ω-consistance » est l’une des clés de la preuve de Godel.

    Je voudrais parler de mon questionnement préliminaire sur ce concept : la ω-inconsistance existe-t-elle en logique mathématique ?

    1, « ω-consistance » de Godel (https://fr.wikipedia.org/wiki/Th%C3%A9orie_om%C3%A9ga-coh%C3%A9rente, voir aussi BasicRabbit 10 MAI 2022 )

    En logique mathématique une théorie arithmétique est appelée théorie ω-cohérente quand, pour toute propriété P des nombres entiers que l’on peut exprimer dans le langage de la théorie,

    si pour chaque entier n, P(n) est démontrable dans la théorie (∀x P(n)), alors ¬∀x P(x) n’est pas démontrable dans la théorie (∃x ¬P(n)).

    2. ω-consistance et logique mathématique

    Il est bien connu qu’en logique mathématique, lorsqu’une proposition est prouvée vraie, cela implique que sa négation est prouvée fausse ; inversement, lorsqu’une proposition est prouvée fausse, cela implique que sa négation est prouvée vraie. C’est-à-dire qu’en ce qui concerne l’existence d’une preuve d’une proposition, la démontrabilité de P et ¬P est cohérente.

    J’utilise deux exemples pour illustrer mon propos.

    Exemple 1 (voir mon article dans ce blog)

    P: √2 is a rational number.
    ¬P: √2 is not a rational number.

    « √2 is not a rational number » (¬P) cannot be proved directly, but there exists the familiar proof by contradiction to prove that « √2 is a rational number » (P), thus ¬P is proved to be true indirectly.

    Cela montre que la démontrabilité de P et ¬P est cohérente.

    Exemple 2:La conjecture de Pólya (voir https://en.wikipedia.org/wiki/Pólya_conjecture)

    De façon équivalente, la conjecture peut être formulée avec la fonction de Liouville de la façon suivante :

    L(n) = ∑ (k=1, n) λ(k)^≤ 0, pour tout n > 1.

    Ici, λ(k) = (−1)Ω(k) vaut 1 si le nombre de facteurs premiers de l’entier k est pair, et -1 s’il est impair. La fonction Ω compte le nombre total de facteurs premiers d’un entier.

    Par exemple, L(18) = 8-10 = -2 (voir Yu LI 7 MAI )

    La conjecture de Pólya (∀n L(n))a été prouvé fausse (réfutée) par C. Brian Haselgrove en 1958: ¬∀n L(n); autrement dit, il existe des contre-exemples, par exemple, pour n = 906 150 257, L(n) est faux: ∃x ¬L(n).

    Pour chaque entier n, L(n) est démontrable (comme faux) dans PA1, alors ¬∀x L(n) (∃x ¬L(n)) est aussi démontrable (comme true) dans PA1.

    Cela montre aussi que la démontrabilité de ∀x L(n) et ¬∀x L(n) est cohérente.

    Puisque, la démontrabilité de P et ¬P en logique mathématique est naturellement cohérente, cela a-t-il un sens de proposer la ω-consistance ? En d’autres termes, la ω-inconsistance existe-t-elle en logique mathématique ?

    1. @ Yu Li.

      1. Vous écrivez: « Il est bien connu qu’en logique mathématique, lorsqu’une proposition est prouvée vraie, cela implique que sa négation est prouvée fausse. ». Je présume qu’une proposition -disons P- prouvée vraie est pour vous synonyme de P est un théorème (d’une théorie, disons PA1 pour fixer les idées) et que non P prouvée fausse est pour vous synonyme de non P n’est pas un théorème.

      Pour moi ce que vous écrivez n’est pas bien connu en logique mathématique; car c’est l’une des définitions possibles de la cohérence d’une théorie: il n’existe pas d’énoncé P tels que P et non P soient toutes les deux des théorèmes.

      2 Vous écrivez : « En logique mathématique une théorie arithmétique est appelée théorie ω-cohérente quand, pour toute propriété P des nombres entiers que l’on peut exprimer dans le langage de la théorie, si pour chaque entier n, P(n) est démontrable dans la théorie (∀x P(n)), alors ¬∀x P(x) n’est pas démontrable dans la théorie (∃x ¬P(n)). ».

      Attention! Le fait que P(n) soit démontrable (disons dans PA1) pour tout entier standard n n’implique pas nécessairement (si on accepte comme correct le théorème d’incomplétude…) que l’énoncé ∀x P(x) soit lui aussi démontrable dans PA1: l’énoncé G de Gödel non démontrable dans PA1 est de la forme ∀x P(x) alors que les énoncés P(n) sont démontrables dans PA1 pour tout entier standard n.

      (Relire le paragraphe « Existence de théories cohérentes mais ω-incohérentes » de https://fr.wikipedia.org/wiki/Th%C3%A9orie_om%C3%A9ga-coh%C3%A9rente .)

      Bien à vous,
      BR.

      1. @ Yu Li.

        Nous n’avons pas la même idée de ce qu’est la cohérence d’une théorie. Vous écrivez :

        « Exemple 1 (voir mon article dans ce blog)

        P: √2 is a rational number.
        ¬P: √2 is not a rational number.

        « √2 is not a rational number » (¬P) cannot be proved directly, but there exists the familiar proof by contradiction to prove that « √2 is a rational number » (P), thus ¬P is proved to be true indirectly. » ,

        et vous concluez :

        « Cela montre que la démontrabilité de P et ¬P est cohérente. » .

        En fait, dans votre article, vous refaites l’une des preuves classiques de ¬P. Mais vous ne dites rien sur P dont, peut-être un jour à venir, on trouvera une démonstration … qui impliquera que PA1 est incohérente.

        Vous me direz que PA1 est cohérente parce que, par le théorème de complétude de Gödel, celle-ci a un modèle. Mais ce modèle est construit dans le cadre -plus large- d’un modèle de PM ou de ZF, théories également supposées cohérentes mais dont, peut-être un jour à venir, on prouvera l’incohérence. L’existence de ce modèle exige de postuler l’existence d’un ensemble infini « en acte » (en pas seulement « en puissance ») (2).

        Dans l’article que vous m’avez fourni (1) l’hypothèse de ω-cohérence est pour Gödel suffisante pour prouver sa proposition VI (et donc son théorème). En fait on sait maintenant que l’hypothèse de cohérence simple est suffisante (et évidemment nécessaire).

        1: https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf

        2: René Thom : « En plaquant ainsi sur le monde l’infini mathématique, l’homme ne fait-il pas preuve de la même présomption inconsciente que le magicien primitif qui commandait aux Dieux… ? ».

        1. Vous dites :
          – En fait, dans votre article, vous refaites l’une des preuves classiques de P (la démonstration par absurde). Mais vous ne dites rien sur ¬P dont, peut-être un jour à venir, on trouvera une démonstration … qui impliquera que PA1 est incohérente.

          Par exemple, un jour à venir, on trouvera une démonstration (¬P: « √2 is irrational ») (voir https://gowers.wordpress.com/2010/03/28/when-is-proof-by-contradiction-necessary/) :
          – We begin by calculating the continued-fraction expansion of √2. We find that √2=1+(√2-1)=1+1/(√2+1). The denominator of the fraction is (√2+1) = 2+(√2-1)=2+1/(√2+1), so we see that the continued-fraction expansion repeats itself, and, in one reasonably standard notation, is [1;2,2,2,…]. In particular, it is infinite. Therefore,  is irrational.

          Cette démonstration prouve toujours que « √2 is irrational » (¬P), qui n’impliquera pas que PA1 est incohérente comme dit Godel, mais au contraire, PA1 est toujours cohérente, …

          1. Je pense que les fameux commentaires de Wittgenstein sur le théorème d’incomplétude de Gödel concernent aussi ce sujet (https://en.wikipedia.org/wiki/Remarks_on_the_Foundations_of_Mathematics) :
            – If one assumes that P is provable in PM, then one should give up “¬P is not provable in PM”.

            Just as we can ask, “ ‘Provable’ in what system?,” so we must also ask, “ ‘True’ in what system?” “True in Russell’s system” means, as was said, proved in Russell’s system, and “false” in Russell’s system means the opposite has been proved in Russell’s system.—Now, what does your “suppose it is false” mean? In the Russell sense it means, “suppose the opposite is been proved in Russell’s system”; if that is your assumption you will now presumably give up the interpretation that it is unprovable. And by “this interpretation” I understand the translation into this English sentence.—If you assume that the proposition is provable in Russell’s system, that means it is true in the Russell sense, and the interpretation “P is not provable” again has to be given up.

          2. @Yu Li. vous écrivez :

            « Cette démonstration prouve toujours que « √2 is irrational » (¬P), qui n’impliquera pas que PA1 est incohérente comme dit Gödel, mais au contraire, PA1 est toujours cohérente, … ».

            Pour moi ce n’est certainement pas une preuve de l’irrationalité de √2 dans PA1 qui dira quoi que ce soit sur la cohérence ou l’incohérence de PA1. Par contre si quelqu’un arrive à prouver la rationalité de √2 dans PA1, alors là oui, jointe à une preuve de l’irrationalité de √2 dans PA1on aura prouvé l’incohérence de PA1. (Mais c’est plutôt dans l’autre sens que ça risque -très hypothétiquement!- de se passer: ce sera une preuve de l’incohérence de PA1 qui -par principe d’explosion- impliquera la rationalité -et d’ailleurs aussi l’irrationalité- de √2.

            (J’en profite pour vous redire que, pour moi, la preuve la plus simple de l’irrationalité de √2 est donnée dans (1). (j’aurais aimé voir écrit que cette preuve est une preuve dans PA1…).

            1: https://fr.wikipedia.org/wiki/M%C3%A9thode_de_descente_infinie

            1. Oui, ce n’est pas une preuve rigoureuse. Je l’ai utilisé juste pour m’interroger sur la conséquence de la définition de la ω-cohérence :
              – si pour chaque entier n, P(n) est démontrable dans la théorie,
              alors ¬∀x P(x) n’est pas démontrable dans la théorie (¬ pour la négation, ∀ pour la quantification universelle, « pour tout »).

              Cette définition pourrait impliquer une compréhension trompeuse de la relation entre la « démontrabilité » et la « valeur de vérité » d’une proposition, qui est le sujet central du théorème d’incomplétude, …

  11. En écho à la citation de Thom ci-dessus: à quoi sert l’infini en mathématiques ? Patrick Dehornoy en parle dans une conférence d’une heure. Il y a deux parties : l’infini est-il nécessaire (de 0′ à 40′) et l’infini est-il utile (de 40′ à 1h) ?

    (Il parle du théorème de Fermat-Wiles à 43′. « La preuve du théorème n’est toujours pas écrite dans le cadre du système ZF »; « Est-ce qu’on peut la faire dans l’arithmétique de Péano? Je ne sais pas. Pour le théorème des nombres premiers il a fallu 50 ans [pour se passer de l’infini]; peut⁻être qu’il faudra tout aussi longtemps. ».)

    https://webtv.univ-rouen.fr/videos/a-quoi-sert-linfini-conference-de-patrick-dehornoy/

    1. À noter dans l’exposé de Dehornoy (15’30): « Il s’agit de trouver des exemples d’énoncés d’arithmétique qui soient vrais mais non démontrables dans Peano (…) Des énoncés vrais, mais s’ils ne sont pas démontrables, qu’est-ce que ça veut dire? Ça veut dire vrais parce que démontrables en utilisant de l’infini. ». Pour moi ce que dit Dehornoy rejoint ce que dit Zermelo dans sa critique , critique que j’ai interprétée plus haut (05/05 22 h 10) ainsi : « vrai et non démontrable dans Peano » = « démontrable dans une théorie plus forte que Peano en utilisant l’infini (typiquement des théories des ensembles comme PM ou ZF) ».

  12. @BasicRabbit Merci beaucoup! Je vais prendre du temps à lire ces documents.

    A vrai dire, je ne sais pas comment exprimer la profonde perplexité et le grand choc que m’a provoqué le déchiffrage de la preuve du théorème d’incomplétude de Gödel, …

    J’explique plus en détail ma question concernant la ω-cohérente :
    – En logique mathématique une théorie arithmétique est appelée théorie ω-cohérente (oméga-cohérente) quand, pour toute propriété P des nombres entiers que l’on peut exprimer dans le langage de la théorie,
    – si pour chaque entier n, P(n) est démontrable dans la théorie,
    alors ¬∀x P(x) n’est pas démontrable dans la théorie (¬ pour la négation, ∀ pour la quantification universelle, « pour tout »).

    Cette définition de ω-cohérent implique que Gödel a assimilé la « démontrabilité » de P(x) à la « valeur de vérité » de P(x) :
    – si pour chaque entier n, P(n) est démontrable dans la théorie (ça signifie que ∀x P(x) est vrai, donc ¬∀x P(x) est faux), alors ¬∀x P(x) n’est pas démontrable dans la théorie (ça signifie que la preuve utilisée pour prouver ∀x P(x) ne peut pas être utilisée pour prouver ¬∀x P(x)).

    Mais en réalité, la « démontrabilité » de P(x) et « valeur de vérité » de P(x) se situent aux niveaux différents :
    – Du point de vue de la valeur de vérité, ∀x P(x) est vrai et ¬∀x P(x) est faux;
    – Mais du point de vue de la démontrabilité, la preuve pour prouver que ∀x P(x) est vraie est aussi la preuve pour prouver que ¬∀x P(x) est fausse.

    On reprend la conjecture de Pólya comme exemple :
    La conjecture de Pólya (∀n L(n))a été prouvé fausse par C. Brian Haselgrove en 1958,alors la preuve pour prouver que ∀n L(n) est faux est aussi la preuve pour prouver que ∃x ¬L(n) est true.

    1. @Yu Li.

      Pour bien comprendre la définition de la ω-cohérence il faut d’abord voir ce qui se passe quand l’énoncé P de dépend pas de n. Ce qui se passe est écrit dans l’introduction de (1) : on a alors une définition de la cohérence simple (2).

      « Quand on prend pour P un énoncé clos (qui ne dépend pas de x -ni de n) on retrouve la définition de la cohérence, appelée parfois dans ce contexte cohérence simple, qui est donc conséquence de l’ω-cohérence. ».

      Votre « Cette définition de ω-cohérent implique que Gödel a assimilé la « démontrabilité » de P(x) à la « valeur de vérité » de P(x) »

      devient dans ce cas particulier :

      « Cette définition de cohérent implique que Gödel a assimilé la « démontrabilité » de P à la « valeur de vérité » de P ». On est donc confronté au rapport « philosophique » entre « valeur de vérité » et démontrabilité.

      Dans ce cas particulier votre « Mais en réalité, la « démontrabilité » de P(x) et « valeur de vérité » de P(x) se situent aux niveaux différents :
      – Du point de vue de la valeur de vérité, ∀x P(x) est vrai et ¬∀x P(x) est faux;
      – Mais du point de vue de la démontrabilité, la preuve pour prouver que ∀x P(x) est vraie est aussi la preuve pour prouver que ¬∀x P(x) est fausse. »

      devient

      « Mais en réalité, la « démontrabilité » de P et « valeur de vérité » de P se situent aux niveaux différents :
      – Du point de vue de la valeur de vérité, P est vrai et ¬P est faux;
      – Mais du point de vue de la démontrabilité, la preuve pour prouver que P est vraie est aussi la preuve pour prouver que ¬P est fausse. ».

      Pour moi votre dernière phrase est ambiguë car il me semble que vous mélangez « valeur de vérité » et démontrabilité.

      Pour moi le rapport entre vérité et démontrabilité est au cœur des rapports entre philosophie et mathématique. Les matheux qui s’intéressent aux fondements de leur discipline ont -je crois…- la position exprimée en 13/05 17h02 : la vérité n’est pour eux que la démontrabilité dans le cadre plus large d’une théorie plus puissante (comme l’est la théorie des ensembles par rapport à PA1). Mais leur position ne fait que reculer le problème: ils font l’hypothèse que cette théorie plus puissante est cohérente (sinon tout -et la négation de tout- est démontrable (3).

      La définition de la satisfaisabilité/valeur de vérité par Tarski est une définition qui vaut dans le cadre d’un modèle de la théorie des ensembles (modèle supposé exister car la théorie des ensembles est supposée non-contradictoire…). Pour espérer bien comprendre le théorème d’incomplétude de Gödel on ne peut pas faire l’impasse -j’en suis convaincu, et, je crois, Druuh aussi- sur le théorème de complétude de Gödel (4).

      Je pense que c’est typiquement avec PJ qu’il vous faut discuter de ce point fondamental (5).

      Nota Bene: Je pense que vos deux arguments-exemples sont bien proches d’être des tautologies (6).

      1: https://fr.wikipedia.org/wiki/Th%C3%A9orie_om%C3%A9ga-coh%C3%A9rente

      2: https://fr.wikipedia.org/wiki/Coh%C3%A9rence_(logique)

      3: https://fr.wikipedia.org/wiki/Principe_d%27explosion

      4: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_compl%C3%A9tude_de_G%C3%B6del

      5: Impasse que semble avoir faite PJ: « En 1930 Kurt Gödel démontra un premier théorème mettant en évidence que « la logique des prédicats du premier ordre est complète, je n’en dirai pas d’avantage. » (« Comment la vérité… », p.286.

      6: https://fr.wikipedia.org/wiki/Tautologie

      1. @ Yu Li.

        Je lis dans (1) que l’ω-cohérence n’est nécessaire dans la preuve originale de Gödel que pour prouver que la négation ¬G de son énoncé (formule close) que je note G (G pour Gödel…) n’est pas démontrable dans T: en fait une forme très affaiblie suffit : le théorème vaut pour toute théorie T qui est une théorie récursivement axiomatisable, cohérente, et qui démontre toutes les formules Σ0 vraies dans N.

        J’en déduis que seule la cohérence simple de T (syntaxique ou sémantique?) est nécessaire pour prouver que G n’est pas démontrable dans T.

        Cependant, puisque vous semblez focalisée sur l’ω-cohérence, je vous re-signale (déjà signalé en 12/05 23h40) que le fait que P(n) soit démontrable pour tout entier naturel n n’entraîne pas que ∀x P(x) soit démontrable (disons dans PA1), ne serait-ce que parce que l’énoncé ∀x P(x) n’a pas de sens dans PA1.

        Par exemple en prenant pour P(n) l’énoncé du « grand » problème de Fermat à l’ordre n, Wiles a démontré le théorème pour tout entier naturel n>2. Mais l’énoncé ∀x>2 P(x) a-t-il un sens? P(n) a un sens pour tout entier naturel n parce que c’est une formule du langage de PA1: 2 n’est pas un terme du langage mais c’en devient un lorsque le remplace par ss0, 0 et s (successeur) étant des symboles du langage. Je ne suis pas du tout convaincu que ∀x P(x) ait un sens; or ce sont, pour moi ,des considérations qu’il faut avoir à l’esprit quand on travaille sur le théorème d’incomplétude.

        1. Complément:

          1: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del

          Chaque fois qu’on lit P(n) (où n est sous-entendu être un entier naturel et P(x) une formule du langage à une variable libre -disons x-)il faut lire P(ss..s0) où le nombre de s est n, formule close (donc énoncé) du langage (de, disons, PA1). C’est, selon moi, indispensable pour comprendre la phrase suivante de (1) -section « Diagonalisation »-:

          « On remarque que la formule G en question est équivalente à une formule universelle ∀x H(x), où H est Σ0. Cette formule étant vraie, pour chaque entier n (représenté par s…s 0) H(n) est vraie, donc démontrable étant Σ0. On a donc bien, comme annoncé dans le paragraphe « vérité et démontrabilité », un énoncé universel ∀x H(x) qui n’est pas démontrable dans T, alors que pour chaque entier n, H(n) est démontrable dans T.

  13. Je pense que nous avons fait de grands progrès dans notre échange : nous avons commencé à reconnaître que la différence essentielle entre la ω-cohérence de Gödel et la cohérence de la logique mathématique, qui est une des clés pour comprendre la preuve de Gödel !

    La preuve de Gödel n’implique pas de concepts complexes, et elle peut être comprise par toute personne ayant un niveau moyen de connaissances ; le problème est qu’il faut mobiliser notre bon sens :

    « Le bon sens est la chose du monde la mieux partagée : car chacun pense en être si bien pourvu que ceux même qui sont les plus difficiles à contenter en toute autre chose n’ont point coutume d’en désirer plus qu’ils en ont. »

    Et je pense que l’utilisation d’exemples représentatifs est un excellent moyen de stimuler notre bon sens !

    Malheureusement, aucun exemple représentatif n’est donné tout au long de l’article de Gödel, ainsi que dans les nombreux articles interprétant le travail de Gödel, laissant le texte original de Gödel entouré de mystère depuis 90 ans, …

    1. @ Yu Li.

      – Quand vous écrivez : « La preuve de Gödel n’implique pas de concepts complexes, et elle peut être comprise par toute personne ayant un niveau moyen de connaissances ; « , vous me semblez plus optimiste que Paul Jorion qui, lui, est, je crois, toujours convaincu que la preuve par Gödel de son théorème d’incomplétude est incorrecte! (Personnellement je suis moins optimiste que vous.)

      – Je suis d’accord avec vous « que l’utilisation d’exemples représentatifs est un excellent moyen de stimuler notre bon sens ! ». À ce sujet il me semble à peu près clair que l’irrationalité de √2 se démontre, par récurrence absurde, dans PA1 (1). Se démontre-t-elle dans RA1 (R pour Robinson (2) -l’axiome de récurrence est-il indispensable?- ?.

      1: https://fr.wikipedia.org/wiki/M%C3%A9thode_de_descente_infinie

      2: « L’arithmétique de Robinson suffit pour le théorème d’incomplétude de Gödel-Rosser et pour le théorème de Church (indécidabilité du problème de la décision), au sens où l’arithmétique de Robinson, et même toute théorie axiomatique dans le langage de l’arithmétique qui est récursive et cohérente et qui a pour conséquence les axiomes de l’arithmétique de Robinson, est nécessairement incomplète et indécidable. » ( https://fr.wikipedia.org/wiki/Arithm%C3%A9tique_de_Robinson )

      1. « La preuve de Gödel n’implique pas de concepts complexes, et elle peut être comprise par toute personne ayant un niveau moyen de connaissances », je voulais dire qu’il y a des complications artificielles dans l’article de Godel, et je n’ai pas dit que je pense que la preuve de Godel est correcte, au contraire il y a quelques choses très graves dans la preuve de Godel, … je ne sais pas si vous avez ressenti cela dans notre discussion sur la ω-cohérence ?

        1. @Yu Li. Vous écrivez : « La preuve de Gödel n’implique pas de concepts complexes, et elle peut être comprise par toute personne ayant un niveau moyen de connaissances ». Je suis d’accord avec vous sur la première partie de la phrase (« La preuve de Gödel n’implique pas de concepts complexes »), mais pas sur la seconde « elle peut être comprise par toute personne ayant un niveau moyen de connaissances », car je pense que le théorème d’incomplétude ne peut être compris que par les rares à la fois suffisamment mathématiciens pour dominer la logique mathématique et suffisamment philosophes pour dominer la logique philosophique. Et je ne suis pas sûr que la philosophie analytique ait réussi à atteindre cet objectif (pour moi sûrement pas Russell et Whitehead (1)).

          Pour moi qui découvre ce théorème en même temps que vous -et en quelque sorte pour vous, pour que vous ayez éventuellement un autre son de cloches que celui d’un PJ lorsqu’il se coiffe d’une casquette d’épistémologue- je ne peux m’empêcher de le comparer à d’autres « grands » théorèmes, dont les premières démonstrations étaient fausses, mais qui ont fini par trouver des démonstrations correctes (c’est-à-dire acceptées par la collectivité mathématique de leur temps), théorèmes qualifiés de « grands » parce qu’ils ouvrent de nouvelles perspectives -parfois grandioses- à ladite collectivité (éventuellement étendue aux philosophes).

          C’est dans cette classe que je range la « preuve » d l’irrationalité de √2 par Aristote -preuve qui, pour moi, n’en est pas une (2)- mais « preuve » qui « ouvre » la théorie de la démonstration (et le théorème d’incomplétude de Gödel l’ « ouvre » encore plus, même si la démonstration originale est incorrecte -ce n’est pas mon problème, mais c’est celui de PJ et le vôtre-). C’est pour ça que je vous ai proposé de parcourir « Le vrai, le faux et l’insignifiant » d’Alain Chenciner, autour de cette citation thomienne que je trouve superbe de profondeur : « C’est seulement parce qu’on accepte le risque de l’erreur qu’on peut récolter de nouvelles découvertes ».

          1: Le mathématicien David Bessis vient d’écrire « Mathemtica » (visiblement, pour moi, un clin d’œil à « Principia Mathématica ») avec pour objectif de réhabiliter l’intuition en mathématiques (actuellement complètement étouffée par l’impératif de la démonstration « coûte que coûte » à la Russel et Whitehead). Dans le dernier chapitre il oppose l’arithméticien anglais Godfrey Hardy et l’indien Srinivasa Ramanujan, ce dernier auteur de centaines de conjectures -dont la plupart ont fini par trouver une preuve, et peu se sont avérées fausses-. Bessis -qui a quitté les mathématiques universitaires pour une start-up en intelligence artificielle- écrit p.341 : « Face à Principia Mathematica, ce conseil devient un impératif de santé mentale: « Il ne faut jamais lire les livres de maths ». J’ai envie d’ajouter : il ne faut jamais se lancer dans la preuve d’un théorème si l’on ne s’est pas convaincu au préalable qu’il est « vrai » (Aristote donne l’opposition conjecture/théorème comme un exemple d’opposition puissance/acte). Ramanujan : « « Une équation pour moi n’a aucune signification, à moins qu’elle ne représente une pensée de Dieu.». (Cependant, Hardy tenait à ce qu’on ne considère pas Ramanujan comme un mystique dont les inspirations mathématiques proviendraient « d’une mystérieuse et immémoriale sagesse orientale » ( https://fr.wikipedia.org/wiki/Srinivasa_Ramanujan ).)

          2: La plus simple que je connais est celle qui figure dans https://fr.wikipedia.org/wiki/M%C3%A9thode_de_descente_infinie

        2. Il y a une inertie scientifique au moins aussi importante que l’inertie sociale ou l’inertie politique : car l’immense majorité des gens ne pensent pas par eux-mêmes, se contentant de colporter les idées de ceux, très rares, qui pensent par eux-mêmes (1). Aristote fait pour moi incontestablement partie de ceux-là, bien que je n’aie lu que quelques lignes de lui (elles sont dans mon précédent commentaire!). mais tout ce qu’il a écrit ne doit pas être pour autant pris pour argent comptant. Aristote a sans doute en effet lui aussi colporté la doxa de son temps. Ainsi il a écrit :

          « Il est admis qu’il n’existe que trois figures planes qui peuvent remplir le plan : le triangle, le quadrilatère, et l’hexagone, et seulement deux solides, la pyramide et le cube. ».

          L’erreur est passée inaperçue pendant près de 1800 ans, jusqu’à ce qu’un allemand, Johannes Müller (1436-1476), connu sous le nom de Regiomontanus, et l’un des pères de la trigonométrie, la révéla (2).

          PJ a étudié la question de l’irrationalité de √2 par Aristote (cf. son commentaire -ici- du 19/04 11h33) : « la preuve par Aristote de l’irrationalité de racine carrée de 2 se faisait par un argument de régression à l’infini aboutissant à une absurdité. ». Qu’en pense-t-il : « démonstration » ou démonstration? (Voir éventuellement https://journals.openedition.org/philosant/2120).

          1: C’est mon cas. je me contente de faire du prosélytisme pour l’œuvre de René Thom (dont il suffit de lire quelques lignes pour se rendre compte que, lui, pense par lui-même!) (https://www.maths.ed.ac.uk/~v1ranick/papers/thom/data/citations.pdf).

          2: https://images.math.cnrs.fr/Empiler-des-tetraedres.html

  14. En parlant d’utiliser des exemples représentatifs pour stimuler le bon sens, j’ai été frappée par l’histoire de la règle des signes de Stendhal, auteur de Le Rouge et le Noir en 1830, m’a marqué (http://www.mathkang.org/pdf/reglesigne.pdf) :

    Stendhal raconte ses démélés avec le calcul dans La Vie de Henry Brulard dont voici un extrait :

    Mon enthousiasme pour les mathématiques avait peut-être eu pour base principale mon horreur pour l’hypocrisie, l’hypocrisie à mes yeux c’était ma tante Séraphie, Mme Vignon et leurs prêtres.

    Suivant moi l’hypocrisie était impossible en mathématiques et, dans ma simplicité juvénile, je pensais qu’il en était ainsi dans toutes les sciences où j’avais ouï dire qu’elles s’appliquaient. que devins-je quand je m’aperçus que personne ne pouvait m’expliquer comment il se faisait que : moins par moins donne plus ?

    (C’est une des bases fondamentales de la science qu’on appelle algèbre).

    On faisait bien pis que ne pas m’expliquer cette difficulté (qui sans doute est explicable car elle conduit à la vérité), on me l’expliquait par des raisons évidemment peu claires pour ceux qui me les présentaient. 

    M. Chabert pressé par moi s’embarrassait, répétait sa leçon, celle pré­cisément contre laquelle je faisais des objections, et finissait par avoir l’air de me dire:
« Mais c’est l’usage, tout le monde admet cette explication. Euler et Lagrange, qui apparemment valaient autant que vous, l’ont bien admise… ».

    A la fin, Stendhal a dit, avec frustration :

    Je fus longtemps à me convaincre que mon objec­tion sur – X – = + ne pourrait pas absolument entrer dans la tête de M. Chabert, que M. Dupuy n’y répondrait jamais que par un sourire de hau­teur, et que les forts auxquels je faisais des ques­tions se moqueraient toujours de moi.
 J’en fus réduit à ce que je me dis encore aujourd’hui: il faut bien que – par – donne + soit vrai, puisque évidemment, en employant à chaque instant cette règle dans le calcul, on arrive à des résultats vrais et indubitables. 

    1. Un de mes petits fils potasse actuellement  » le rouge et le noir » pour l’oral du bac ( fin de première ) . Il m’a regardé avec des yeux de chien battu quand je lui ai cité votre commentaire !

    2. Aristote : « Abstraire n’est pas mentir ». Thomas d’Aquin: « Quand il abstrait le mathématicien ne ment pas ».

      Thom (mon gourou) ; « Il n’arriverait plus aux modernes de traiter de « menteur » [tiens, tiens…], celui qui, par jeu ou par conviction, confère un sens à une expression linguistique usuellement considérée comme dépourvue de sens [je mens…]. À ce compte, les poètes, les philosophes, et même les mathématiciens n’échapperaient guère à l’opprobre du mensonge. Ces derniers, par exemple, ont utilisé l’expression (absurde) √-1 pendant deux siècles avant d’en avoir une interprétation plausible. En grande partie la « philosophie » est une affaire d’affirmation (ou de rejet) d’expressions formées à partir de mécanismes formels reconnus, dans un contexte sémantique surprenant [le théorème d’incomplétude…]. Dans les bons cas, c’est la pratique (l’empirie) qui décide; à défaut les « préjugés » du philosophe. Sur le fond, évidemment, reste l’opposition Platon-Aristote. En dépit de mon admiration pour ce dernier, je reste platonicien en ce que je crois à l’existence séparée (« autonome ») des entités mathématiques, étant entendu qu’il s’agit là d’une région ontologique différente de la « réalité usuelle » (matérielle) du monde perçu; (C’est le rôle du continu -de l’étendue- que d’assurer la transition entre les deux régions. » (Esquisse d’une sémiophysique, pp.244 et 245).

      (Les crochets -[ ]- sont « évidemment » de moi. Et cette citation montre tout-à-fait clairement -selon moi- ce qui sépare Thom (et ce qui me sépare) du matérialiste-empiriste PJ -c’est ainsi que je le perçois-.)

  15. @BasicRabbit Aristote : « Abstraire n’est pas mentir ». Thomas d’Aquin: « Quand il abstrait le mathématicien ne ment pas ».

    Vous avez abordé une question fondamentale : lorsqu’on est confronté à un raisonnement, comment savoir s’il est valable ou s’il s’agit d’un raisonnement fallacieux ?

    Si l’on se penche sur l’histoire de la logique, on peut constater que la logique a été fondée comme une discipline par les philosophes grecs pour dénoncer des raisonnement fallacieux (les sophismes)

    Cependant,« Il n’arriverait plus aux modernes de traiter de « menteur » [tiens, tiens…], celui qui, par jeu ou par conviction, confère un sens à une expression linguistique usuellement considérée comme dépourvue de sens [je mens…]. À ce compte, les poètes, les philosophes, et même les mathématiciens n’échapperaient guère à l’opprobre du mensonge. (Thom)

    C’est exactement la situation à laquelle nous sommes confrontés avec la preuve du théorème d’incomplétude de Gödel : comment savoir si la preuve de Gödel est valide ou fallacieuse ?

    C’est pourquoi je pense que Paul soulève une question qui donne à réfléchir:
    – What makes a demonstration worthy of the name?

    1. @Yu Li. Votre « What makes a demonstration worthy of the name? » m’incite à commenter ici alors qu’il aurait été plus naturel de commenter l’article éponyme de PJ (1), car c’est en commentaires de cet article que je me suis demandé non seulement si la démonstration par Gödel du théorème d’incomplétude était correcte, mais aussi si la démonstration de PJ, dans -essentiellement- le chapitre IV Comment la vérité… », était ou non convaincante. Gödel, Jorion, Aristote.

      Le chapitre IV de « Comment la vérité… », chapitre intitulé « La revanche de Pythagore » commence par : « C’est Aristote qui fixe la norme en matière de démonstration ». La première chose à faire, à mon avis, est de critiquer la propre démonstration d’Aristote de l’irrationalité de √2 (1) à l’aune de ses propres critères, avant de s’attaquer à la critique de la preuve par Gödel du théorème d’incomplétude à l’aune de ces mêmes critères. Critiquer la preuve par Aristote de l’irrationalité de √2 c’est, selon moi, critiquer l’une des premières preuves où les mathématiques sont confrontées à l’infini dans une démonstration (pour moi cette preuve « ouvre » la théorie de la démonstration non finitiste en mathématiques).

      Pour moi cette démonstration d’Aristote est incorrecte. Qu’en pensez-vous? Et qu’en pense éventuellement PJ? Ces questions sont pour moi importantes car c’est, à mon avis, la question de l’infini qui est au cœur de la démonstration du théorème d’incomplétude (l’audio-vision de la conférence de Patrick Dehornoy « À quoi sert l’infini en mathématiques? »(3) a clarifié mes idées à ce sujet).

      1: https://www.pauljorion.com/blog/2022/04/09/what-makes-a-demonstration-worthy-of-the-name-by-paul-jorion-yu-li/

      2: https://journals.openedition.org/philosant/2120).

      3: https://webtv.univ-rouen.fr/videos/a-quoi-sert-linfini-conference-de-patrick-dehornoy/

  16. @Druuh Vous dites que la formule dont parle Godel est une formule du calcul des predicats (25 AVRIL 2022 ):
    – De meme, la fameuse formule de Godel est vraie dans N, mais pas dans d’autres modeles de Peano (et c’est precisement pour cela qu’elle n’est pas demontrable dans Peano).

    Quand vous êtes disponible, pouvez-vous expliquer ce que la fameuse formule de Godel est vraie dans N? et pourquoi ?

  17. Aujourd’hui est le jour où Gautama le Bouddha a réalisé qu’il n’y a pas de chemin vers la Vérité : si vous voulez être illuminée, c’est dans le moment présent.

    Je voudrais partager l’étymologie de Bouddha (Buddhi) :
    « Bu » signifie Buddhi ou l’intellect. Celui qui transcende son intellect et ne s’identifie plus à ses pensées, est un Bouddha.

    1. @Yu Li:  » « Bu » signifie Buddhi ou l’intellect. Celui qui transcende son intellect et ne s’identifie plus à ses pensées, est un Bouddha. »;

      Thom (mon gourou) : »En permettant la construction de structures mentales qui simulent de plus en plus exactement les structures et les forces du monde extérieur -ainsi que la structure même de l’esprit-, l’activité mathématique se place dans le droit fil de l’évolution. C’est le jeu signifiant par excellence, par lequel l’homme se délivre des servitudes biologiques qui pèsent sur son langage et sa pensée et s’assure les meilleures chances de survie pour l’humanité. » (Stabilité structurelle et morphogenèse, 2ème ed. pp.320 et 321).

      Les vrais matheux (1): des Bouddhas ?

      1: Je m’empresse de dire que je n’en suis pas un (et de très loin).

    2. @Yu Li (Suite). Thom encore:

      « … en écrivant ces lignes j’ai acquis une conviction: au cœur même du patrimoine génétique de notre espèce, au fond insaisissable du logos héraclitéen de notre âme, des structures simulatrices de toutes les forces naturelles extérieures agissent, ou en attente, sont prêtes à se déployer quand ce deviendra nécessaire. La vieille image de l’Homme microcosme reflet du macrocosme garde toute sa valeur: qui connaît l’Homme connaîtra l’univers. Dans cet essai d’une théorie générales des modèles [le sous-titre de Stabilité Structurelle et Morphogenèse], qu’ai-je fait d’autre sinon de dégager et d’offrir à la conscience les prémisses d’une méthode que la vie semble avoir pratiquée dès son origine? » (Fin de l’épilogue de SSM).

      Pourquoi cette citation, en partie redondante avec la précédente? parce qu’apparaît implicitement le « Connais-toi toi-même » de Socrate, qui, pour moi, renvoie directement à l’étude de l’ultra-infini en théorie des ensembles et aux plongements élémentaires -plongements introspectifs- d’un univers de ZF dans lui-même (1).

      1: Cf. mon commentaire du 09/05 17h30, https://www.lmno.cnrs.fr/archives/dehornoy/Books/Ensembles/chapLV.pdf p.517 et suivantes

  18. @BasicRabbit Je vais prendre du temps à lire et réfléchir ce que vous avez proposé!

    Nous avons discuté de la «  cohérence » , et une autre clé de la preuve de Gödel est la « récursivité » : la proposition G de Gödel est exprimée sous la forme d’une « fonction récursive », et pouvons nous discuter un peu de ce sujet ? (votre commentaire 14 MAI 2022 )

    1. @Yu Li. La seule chose que je crois avoir compris au sujet de fonctions récursives c’est qu’elles sont au langage mathématisé des logiciens formels ce que les fonctions effectivement calculables sont au méta-langage « naturel » (pour moi le français), la thèse de Church étant que c’est la même chose. À part ça je n’y connais techniquement strictement rien, mais je suis conscient qu’une connaissance approfondie des fonctions récursives, des définitions récursives et des preuves récursives, est essentielle pour la compréhension de la preuve du théorème d’incomplétude de Gödel (avoir parcouru (1) m’en a convaincu).

      1: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del

    2. @Yu Li. J’en profite pour donner ma position actuelle (qui a évolué et qui peut évoluer…). Je considère que le problème de l’irrationalité de √2 est actuellement bien compris et qu’on dispose de plusieurs preuves de l’irrationalité admises par les collectivités mathématiques et épistémologiques contemporaines. Je considère qu’on dispose actuellement de preuves du théorème d’incomplétude de Gödel admises par la collectivité des logiciens formels. Pour moi la preuve originale par Gödel de son théorème d’incomplétude est encore mise en cause par des épistémologues exactement dans le même rapport (eudoxo-aristotélicien) que la preuve de l’irrationalité de √2 par Aristote l’a, elle aussi, longtemps été -et l’est encore? (1)-. Aristote est pour moi un pionnier qui a « ouvert » la méthode de démonstration par descente infinie, et, toujours selon moi, Gödel a « ouvert » une nouvelle page de la théorie de la démonstration.

      Il est bien connu que nombre de « grands » théorèmes ont d’abord eu des preuves incorrectes, et même que des conjectures assorties d’une « preuve » se sont avérées fausses, l’exemple récent le plus connu étant l’erreur de Poincaré, erreur qui « ouvrira » la théorie du chaos. Pour Thom le faux est au vrai ce que l’idéal est au réel (encore une proportion eudoxo-aristotélicienne):

      « Il ne faut pas s’étonner du caractère exceptionnel de la réalisation de l’idéal. Situation bien connue en Science, où fréquemment une situation théorique joue un rôle essentiel dans l’organisation des phénomènes, bien que, en un sens strict, cette situation ne se réalise jamais. En Science, le vrai est souvent secondaire par rapport à un faux qui engendre et canalise la totalité du vrai… Ainsi en va-t-il de même de l’idéal… ».

      1: https://journals.openedition.org/philosant/2120

    3. @Yu Li. À propos de la récursivité. Vous écrivez dans votre article:

      I try to point out that by confusing the proof of formula with the formula, Gödel’s proof becomes an infinite regress that would have made it impossible to construct any meaningful proposition. »

      J’ai jadis entendu dire que les démonstrations les plus subtiles que l’on peut faire par méthode de descente infinie dans le cadre de PA1 sont liées aux ordinaux récursifs (1) (ou, plus généralement, aux relations -récursives- bien fondées (2)): plus la démonstration est subtile, plus l’ordinal récursif est grand (ou plus la relation bien fondée est compliquée). Il me semble que, dans sa conférence sur l’infini (3, 42’55), Dehornoy suggère que la preuve par Wiles du grand théorème de Fermat utilise des méthodes de descente sur des ordinaux « inaccessibles » -et donc très loin d’être récursifs ou même dénombrables- (Dehornoy parle de super-infini).

      1: https://fr.wikipedia.org/wiki/Grand_ordinal_d%C3%A9nombrable

      2: https://fr.wikipedia.org/wiki/Relation_bien_fond%C3%A9e#R%C3%A9currence_noeth%C3%A9rienne_ou_bien_fond%C3%A9e

      3: https://webtv.univ-rouen.fr/videos/a-quoi-sert-linfini-conference-de-patrick-dehornoy/

      1. @Yu Li. À propos de votre « une autre clé de la preuve de Gödel est la « récursivité ».

        Vous avez posé le 15/05 23h23 la question suivante à Druuh: « pouvez-vous expliquer ce que la fameuse formule de Gödel est vraie dans N? et pourquoi ? ». Sans répondre à vos questions précises, je vous signale l’existence d’une conséquence du théorème de non-définissabilité de la vérité de Tarski:

        Proposition (premier théorème d’incomplétude de Gödel, forme faible) : Pour toute théorie récursive T incluse dans Th 1 (N, 0, S, +, ·, #), il existe une formule vraie dans (N, 0, S, +, ·, #) non prouvable à partir de T.

        C’est dans (1), p.298 (PA1 est une telle théorie récursive, et Th 1 (N, 0, S, +, ·, #) est la théorie -complète- dont toutes les formules closes vraies sont prises pour axiomes).

        Le théorème de Tarski est plus simple à prouver que le théorème d’incomplétude de Gödel parce qu’il n’y est question ni de démontrabilité, ni de ω-cohérence. Mais tous les autres ingrédients y sont: représentabilité du méta-langage par le langage formel codé et argument diagonal de Cantor.

        Dehornoy note p.279 :

        « Le résultat de représentabilité que l’on va établir ici montre que ces fonctions sont également simples du point de vue de la prouvabilité. Ce résultat est essentiel pour l’obtention des résultats d’impossibilité de la section 4, et, en un sens, il constitue le noyau dur de leur démonstration. ».

        Vous avez donc tout-à-fait raison de vous concentrer sur les questions de récursivité, c’est-à-dire sur les trois premiers chapitres ! (Bon courage…). Pour moi ce problème de la représentabilité est aussi le noyau dur de la critique de PJ (et donc de la vôtre?).

        1: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del

    4. @Yu Li. Je découvre le jeu de l’hydre de Kirby et Paris (ce sont eux qui ont démontré que le théorème de Goodstein n’était pas démontrable dans PA1). C’est un exemple, plus « concret » que celui de Goodstein, de théorème d’arithmétique démontrable dans ZF mais pas dans PA1(1):

      « Mais ce que Kirby et Paris ont prouvé dans leur article est en réalité bien plus génial : pour prouver que Hercule est toujours plus fort que l’hydre, on ne peut pas faire autrement que d’utiliser les ordinaux. La démonstration du théorème de l’hydre est en fait absolument impossible à réaliser avec les outils de l’arithmétique que l’on connaît, comme les opérations sur les nombres entiers ou la démonstration par récurrence.

      Le théorème de l’hydre est en fait ce que l’on appelle en logique un théorème indécidable pour l’arithmétique : un théorème qui est vrai mais qui ne peut pas être démontré au sein de cette théorie.
      La notion d’énoncé « vrai » est un peu plus précise que cela en mathématiques. Pour dire qu’un énoncé est vrai dans une théorie donné des mathématiques (comme celle de l’arithmétique de Peano), il faut qu’elle soit vraie dans tous les modèles de cette théorie (le modèle le plus simple de l’arithmétique de Peano est celui de la séquence de nombres 0-1-2-3-… que l’on trouve dans la théorie des ensembles ZF). En fait, le théorème de Kirby & Paris montre que l’énoncé est vrai dans la théorie des ensembles (et donc, dans le modèle classique de l’arithmétique), mais ne dit rien de sa véracité de façon générale. Il a donc été un peu précipité pour moi d’affirmer que l’énoncé est vrai sans plus de précisions.

      C’est d’ailleurs ce qu’énonce le théorème de Gödel : la plupart des théories mathématiques contiennent des énoncés qui sont vrais mais qui ne peuvent pas y être démontrés. Mais ça, c’est une autre histoire… »

      1: http://eljjdx.canalblog.com/archives/2016/02/12/33360210.html

    5. @Yu Li.

      1. Erreur dans mon précédent commentaire : la référence (1) à Dehornoy est : https://www.lmno.cnrs.fr/archives/dehornoy/Books/Ensembles/chapLI.pdf

      2. À propos de l’hypothèse de ω-cohérence dans le théorème d’incomplétude.

      Lorsqu’on se place dans un modèle de ZF, on a un modèle standard de PA1 dont les éléments sont les ordinaux finis, l’ensemble des éléments étant noté N ou ω (plus petit ordinal infini). Dans ce cas on peut se passer de l’hypothèse de ω-cohérence -et même de l’hypothèse de cohérence tout court puisque PA1, ayant un modèle (le modèle standard) est cohérente. Voir la fin du commentaire du théorème d’incomplétude de (1), p.301.

  19. @BasicRabbit Merci beaucoup pour votre générosité et votre enthousiasme ! Je répondrai à vos commentaires au fur et à mesure.

    Vous dites (16 MAI 2022) : « Il est bien connu que nombre de « grands » théorèmes ont d’abord eu des preuves incorrectes, et même que des conjectures assorties d’une « preuve » se sont avérées fausses, l’exemple récent le plus connu étant l’erreur de Poincaré, erreur qui « ouvrira » la théorie du chaos. Pour Thom le faux est au vrai ce que l’idéal est au réel (encore une proportion eudoxo-aristotélicienne): »
    « En Science, le vrai est souvent secondaire par rapport à un faux qui engendre et canalise la totalité du vrai… Ainsi en va-t-il de même de l’idéal… ».

    Exactement, la faille du « grand » théorème de Gödel a « ouvert » le grand travail de Turing (un sujet dont nous aurons l’occasion de parler) !

    Il n’est donc pas étonnant qu’il puisse y avoir des erreurs dans la preuve de Gödel, mais si nous considérons le « faux » comme le « vrai » et n’en sommes pas conscients, alors, au lieu de engendrer et canaliser la totalité du vrai, le faux pourrait emmêler nos perceptions, causant des souffrances mentales indicible et consumant nos vies, …

    Dans le livre de Rebecca Goldstein, « Incompleteness : The Proof and Paradox of Kurt Gödel », il y a des discussions fascinantes sur ce sujet (https://www.rebeccagoldstein.com/publications/incompleteness-proof-and-paradox-kurt-gödel).

    Paul et moi, nous avons des ressentis à ce sujet et remettons donc en question la preuve de Gödel dans l’espoir de pouvoir réfléchir et faire le tri entre ce qui est vrai et ce qui ne l’est pas, …

  20. @ Yu Li. Vous écrivez: « Paul et moi, nous avons des ressentis à ce sujet et remettons donc en question la preuve de Gödel dans l’espoir de pouvoir réfléchir et faire le tri entre ce qui est vrai et ce qui ne l’est pas, … ».

    C’est un chose de remettre en cause la preuve et c’en est une autre de remettre en cause l’énoncé. Ma position est que, après 90 ans de clarifications, de simplifications et d’améliorations, les énoncés et les démonstrations « modernes » sont corrects (je fais confiance à des gens comme Dehornoy, Laver, Kirby, Paris, Harrington (1), etc.). mais peut-être allez-vous trouver avec PJ la faille qui va tout écrouler et « ouvrir » autre chose (2). C’est ce qui est arrivé à Lusin et Souslin lorsqu’ils ont trouvé une erreur dans une preuve de Lebesgue qui affirmait à tort que la projection sur la droite d’un borélien du plan était un borélien de la droite, « ouvrant » ainsi la riche théorie descriptive des ensembles (3), théorie qui génère et étudie une hiérarchie analytique (4) analogue à la hiérarchie arithmétique (5) cruciale dans la preuve du théorème d’incomplétude.

    NB: En ce qui me concerne je n’irai pas jusqu’à parler d’enthousiasme (qui vient du grec ancien ἐνθουσιασμός (« possession divine »)!

    1: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Paris-Harrington

    2: Je pense qu’il vous faut « rentrer dans le sujet » beaucoup plus profondément que ne le montrent vos deux articles, ne serait-ce que pour pouvoir établir des correspondances preuve-programme (à la Curry-Howard) entre démontrabilité et calculabilité, correspondances qui me semblent intéressantes pour l’étude du problème P vs NP (je pense -au flair car je n’y connais rien- que les correspondances que donne J.L Krivine (mon directeur de thèse) (6,7) sont intéressantes à considérer de ce point de vue). Je pense qu’il vous faut trouver un « vrai spécialiste » de ces sujets côté logiciens formels (tous ceux que j’ai connus sont en retraite depuis longtemps…), afin de pouvoir échanger avec lui.

    3: https://fr.wikipedia.org/wiki/Th%C3%A9orie_descriptive_des_ensembles

    4: https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_analytique

    5: https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_arithm%C3%A9tique

    6: https://fr.wikipedia.org/wiki/Correspondance_de_Curry-Howard

    7: http://www.pps.jussieu.fr/~krivine/articles/completude.pdf

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.