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 :

348 réponses à “UNILOG 2022 – Gödel’s Incompleteness Theorem revisited, par Yu Li”

  1. Avatar de BasicRabbit
    BasicRabbit

    Je me lance…

    La question qui m’intéresse est la suivante: pourquoi revisiter maintenant un théorème datant de 80 ans? Une réponse a été suggérée par Paul Jorion dans la toute fin de « Comment la vérité… »:

    « Turing a-t-il vacillé (…) devant des faits incontestables mais qui disqualifiaient les travaux qu’il avait entrepris dans la première partie de son œuvre? Je n’en sais rien. Tout ce que je sais, c’est que les rapports significatifs qu’entretiennent les nombres l’ont ébranlé et que le mur de brique qu’il rencontra dans la récurrence des nombres de Fibonacci au sein du vivant lui évoqua les clés d’encodage d’un système crypté. Si tel fut son doute, il n’aura pu s’empêcher de penser que le « test de Turing » de l’intelligence artificielle est sans portée: si la voie illuministe possède un quelconque mérite, il existe un codeur, et l’intelligence artificielle existe depuis plusieurs dizaines de milliers d’années, car c’est la nôtre. ».

    Pour moi c’est ça qui est important et qui motive, au fond, une révision des théorèmes d’incomplétude de Gödel : que disent ces théorèmes sur les rapports entre l’intelligence humaine (IH) -voire l’intelligence naturelle (IN)- et l’intelligence artificielle (IA) ?

    Étymologiquement un théorème est l’objet d’une vision. Je pense que cette définition renvoie plutôt à l’école platonicienne (Tout est géométrie) qu’à l’école pythagoricienne (Tout est nombre), école pour laquelle un théorème serait plutôt l’objet d’une diction. (À ce propos PJ note p.291 que c’est Euclide, un géomètre, qui a introduit en mathématiques le style « axiomatique », c’est-à-dire, le passage du « voir » au « dire »(1)).

    Le philosophe-géomètre platonicien René Thom a écrit dans « Infini opératoire et réalité physique  » (article que je n’ai pas lu!): « Selon de nombreuses philosophies Dieu est géomètre; il serait peut-être plus logique de dire que le géomètre est Dieu ». Peut-être le philosophe-algébriste pythagoricien Alexandre Grothendieck, auteur de « La clef des songes », sous-titré « Dialogue avec le bon Dieu ») aurait accepté : « Selon certaines philosophies Dieu est arithméticien; il serait peut-être plus logique de dire que l’arithméticien est Dieu » ? (Pour moi, le Dieu en question est l’être donné des philosophes, dont PJ parle à plusieurs reprises dans « Comment la vérité… ».)

    Bien que j’aie baigné « professionnellement » dans les problèmes d’incomplétude (il y a maintenant plus de 50 ans…) je ne suis d’aucune utilité pour répondre à vos trois questions (je m’adresse à ma consœur Yu Li). La raison est que les problèmes d’incomplétude auxquels je me suis intéressé l’ont été dans le cadre de la théorie des ensembles et non de l’arithmétique, et que dans ce cadre on a un moyen « sémantique » de résoudre de tels problèmes (en construisant de nouveaux modèles de la théorie des ensembles grâce à la méthode du forcing de P. Cohen). Je vous signale néanmoins à ce propos que mon directeur de thèse Jean-Louis Krivine a proposé une preuve sémantique du théorème d’incomplétude de Gödel (de mémoire on la trouve à la fin de son « Théorie axiomatique des ensembles, PUF).

    Pour moi la question « philosophique » posée par les théorèmes d’incomplétude de Gôdel est de savoir si on peut tirer une connaissance objective (un théorème) d’une connaissance subjective liée à l’auto-référence (« je me mens »). On est là, à mon avis, dans ce que je considère comme le top de la métaphysique (l’étude de l’être en tant qu’être, selon Aristote). Je n’ai pas de réponse…

    En bibliographie vous signalez l’un des paradoxes de Zénon. Si on consulte Wikipédia le paradoxe a été résolu par l’invention/découverte du calcul infinitésimal. PJ nous conseille la prudence (p.274): « Soyons parcimonieux dans notre recours aux infinitésimaux pour éviter les pièges que nous tendent les paradoxes de Zénon ». Pour René Thom, mon actuel gourou (et pour moi à sa suite…) le paradoxe ne peut être résolu que par un penseur du continu (Thom considère qu’il est peut-être le premier tel penseur depuis Aristote).

    Peut-être en sera-t-il de même pour le paradoxe du menteur? Peut-être faudra-t-il que le mathématicien change sa vision des mathématiques? De Pythagore à Platon?

    (1) Le problème du passage du « voir » au « dire », à savoir du morphologique au logique a été abordé « philosophico-mathématiquement » par Jean Petitot dans  » “Le hiatus entre le logique et le morphologique: prédication et perception » ((http://jeanpetitot.com/ArticlesPDF/Petitot_Thom_Urbino.pdf)

  2. Avatar de BasicRabbit
    BasicRabbit

    En ce qui concerne le deuxième partie du point 2 (« If not, what is a valid proof for the incompleteness of PM? ») j’ai retrouvé une version récente (et unifiée) des preuves des « théorèmes de limitation » de Church, Tarski et Gödel (1). C’est de Patrick Dehornoy (beaucoup, beaucoup plus fort que moi…) que j’ai connu à l’époque. Ces théorèmes de limitation sont énoncés et prouvés dans la partie 4. Tout est motivé et expliqué et, il me semble, les points délicats (de son point de vue…) ne sont pas éludés mais au contraire systématiquement mis en avant. Je pense que vous pourrez peut-être confronter là votre propre point de vue au sien sur les points litigieux qui vous tiennent à cœur. (Pour le débat, c’est trop tard: Patrick est décédé en 2019…).

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

    1. Avatar de Paul Jorion

      Je vais très certainement regarder. Merci !

  3. Avatar de BasicRabbit
    BasicRabbit

    À propos de votre question 2: « If not, what is a valid proof for the incompleteness of PM? ».

    Ce que vous et PJ (1) appelez le théorème d’incomplétude de Gödel n’en est qu’un cas particulier. Cas particulier intéressant en soi, mais très nettement en deça du véritable théorème: cf. (2) et ce qui suit. Une question qui se pose déjà est donc: peut-on démontrer ce cas particulier sans faire appel ni au paradoxe du menteur, ni à l’argument diagonal. Le théorème de Goodstein (joint au théorème de Kirby et Paris répond à la question: voir une esquisse de la preuve en (3), preuve qui (me) donne un peu le vertige et qui (me) laisse penser qu’il y a peu d’espoir d’obtenir une preuve dans l’arithmétique de Peano (il n’y en a en fait aucun, la non-prouvabilité du théorème de Goodstein à partir de l’arithmétique de Peano ayant été établie par L. Kirby et J. Paris en 1982 (4)).

    Une fois ce cas particulier du théorème d’incomplétude résolu, il est naturel de considérer l’arithmétique de Peano à laquelle on a rajouté le théorème de Goodstein comme axiome. C’est alors une conséquence du (véritable) théorème d’incomplétude de Gödel que cette nouvelle théorie -dans laquelle le théorème de Goodstein est un théorème puisque c’en est un axiome- est elle aussi incomplète.

    1: Cf. « Comment la vérité… », p.286.

    2: https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del#%C3%89nonc%C3%A9s_des_deux_th%C3%A9or%C3%A8mes

    3: https://www.lmno.cnrs.fr/archives/dehornoy/Talks/DycShort.pdf

    4: https://www.lmno.cnrs.fr/archives/dehornoy/Books/Ensembles/chapLI.pdf , p.310.

  4. Avatar de BasicRabbit
    BasicRabbit

    À propos de la régression à l’infini (« infinite regress ») dont il est question dans l’article.

    Il me semble avoir lu (sous la plume de PJ?) que les anciens grecs ne connaissaient pas (et donc n’acceptaient pas) le principe de démonstration par récurrence, et que 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é.

    L’axiome de récurrence de Peano porte sur les entiers naturels (ceux de tout le monde, dès le CP) et dit qu’une régression infinie sur les entiers (régression exprimable dans le langage de l’arithmétique) est impossible. Si la preuve du théorème de Goodstein utilise un argument de ce type, alors il s’agit très vraisemblablement d’une régression portant sur des ordinaux éventuellement infinis (je crois que c’est ça qui se passe, mais il faut consulter plus spécialiste que moi pour confirmation). À ce propos j’ai lu sous une plume que je considère comme autorisée -celle de Patrick Dehornoy- que l’actuelle preuve (par Wiles) du théorème de Fermat-Wiles utilise une récurrence transfinie et qu’on ne sait pas encore (à l’époque où il a dit ça) si ce célèbre théorème d’arithmétique se démontre dans l’arithmétique de Peano…

    1. Avatar de Paul Jorion

      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é.

      En effet :

      Comment la vérité et la réalité furent inventées (2009) :

      La question de l’incommensurabilité entre des longueurs aussi co-présentes que le côté et la diagonale, obligèrent à définir une nouvelle famille de nombres : les irrationnels. Autre défaite des mathématiques de la même nature : le rapport entre la circonférence d’un cercle et son diamètre, et le rapport entre son aire et le carré de la moitié de son diamètre, qui produisent eux aussi un irrationnel : π, dont la valeur est 3,141592…

      Les irrationnels durent être distingués à leur tour en « irrationnels algébriques » qui sont les racines d’une équation algébrique au nombre de termes finis et dont les coefficients sont rationnels (Legendre cité par Remmert 1991 : 151), et les autres : les « irrationnels transcendantaux » qui « omnem rationem transcendunt » (Remmert 1991 : 151). Au quatrième siècle av. J.-C., Eudoxe avait découvert une manière de contourner la difficulté que créaient les irrationnels : la méthode de l’exhaustion où deux irrationnels sont soustraits l’un de l’autre jusqu’à ce que leur reste devienne négligeable (van der Waerden 1983 : 89-91 ; Szabo [1969] 1977 : deuxième partie ; Fowler 1990 : deuxième chapitre).

  5. Avatar de BasicRabbit
    BasicRabbit

    À propos du théorème de complétude de Gödel.

    PJ (1): « En 1930, Kurt Gödel démontra un premier théorème mettant en évidence que « la logique des prédicats de premier ordre est complète; je n’en dirai pas davantage ».

    Dans la mesure où Gödel cherche à faire une démonstration syntaxique de son théorème d’incomplétude, il n’y a effectivement pas de raison d’en dire davantage. En ce qui me concerne je ne peux me passer de ce théorème de complétude qui lie démontrabilité et vérité selon l’équation: démontrable dans une théorie = vrai dans tous les modèles de la théorie, théorème qui précise ce qu’écrit Ladrière: « Les énoncés vrais sont les axiomes et les théorèmes » (2). Ce théorème me permet -je parle pour moi, chacun voyant midi à sa porte- de donner un sens sémantique (sic!) au théorème d’incomplétude : il existe toujours un énoncé clos du langage de la théorie respectant les hypothèses (disons celle de Peano pour fixer les idées) qui est vrai dans un modèle de cette théorie et faux dans un autre. Cela mérite, selon moi, explication.

    Dans la théorie des groupes (par exemple) on voit bien comment ce théorème de complétude fonctionne: pour démontrer que l’ « axiome » de commutativité est indépendant des axiomes de la théorie, il suffit d’exhiber un groupe commutatif et un groupe non commutatif, ce qui n’est pas difficile. La question qui s’est posée à moi pour l’arithmétique (disons de Peano) c’est une question qui, je crois, se pose à tout un chacun qui aborde ces questions de complétude et d’incomplétude: naïvement, pour qui débarque dans ces problèmes, il n’y a « évidemment » qu’un seul modèle de l’arithmétique de Peano, et ce modèle est le modèle standard N, celui que tout le monde connaît de puis le CP (ce qui renvoie à l’affirmation de Ladrière évoquée plus haut). Mais quand on pénètre un peu plus dans le sujet, on apprend que les théories comme celle de Peano n’ont jamais un seul modèle (en jargon de logicien on parle alors de théories catégoriques), elles en ont toujours beaucoup (et même une infinité): ça a été pour moi assez difficile à digérer, mais je suis convaincu qu’il faut en passer par là pour espérer rentrer vraiment dans le sujet des théorèmes d’incomplétude.
    .

    1: « Comment la vérité… », p.286.

    2: id., p.291.

  6. Avatar de BasicRabbit
    BasicRabbit

    Yu Li : « I hope to initiate a debate ».

    Je pense que pour initier un débat entre épistémologues et spécialistes du sujet, il est nécessaire de s’accorder sur les points que j’ai évoqués. Restera alors à trouver un spécialiste qui acceptera de débattre (je suis loin, très loin, d’en être un). Peut-être Druuh? (1) Je lirai ses échanges avec PJ et Yu Li avec intérêt.

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

  7. Avatar de BasicRabbit
    BasicRabbit

    Complément à mon commentaire du 16/04 12h33.

    En reparcourant (1) je me remets en mémoire des raffinements du « théorème » de Ladrière: « Les énoncés vrais sont les axiomes et les théorèmes. ». Il y a effectivement toute une classe de formules closes pour lesquels le « théorème » est correct : « Dans une théorie qui a pour conséquences toutes les formules Σ0 vraies dans N, les formules Σ1 vraies dans N sont prouvables. ».

    Cet argument semble important pour la preuve du premier théorème d’incomplétude: cf. (2) où on y trouve la sacro-sainte phrase « On obtient G=Δ(⌈Δ⌉), une formule qui dit bien d’elle-même qu’elle n’est pas démontrable dans T », phrase que PJ et Druuh ne manqueront sans doute pas de débattre…

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

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

  8. Avatar de Yu LI
    Yu LI

    Joyeuses Pâques !

    Je vous remercie pour vos discussions riches et intéressantes. Je voudrais d’abord clarifier ma proposition de relecture du premier chapitre de la thèse de Gödel, puis je répondrai à vos commentaires.

    Puisque nous discutons du théorème d’incomplétude de Gödel, il est d’abord nécessaire de parvenir à un consensus sur ce que dit Gödel ; ce que dit Paul, et ce que je dis, n’est pas une priorité dans la discussion actuelle.

    Et ce que Gödel dit est juste là, dans sa thèse de 1931. La thèse de Gödel se compose de trois chapitres : le premier expose les idées principales de la preuve, et les deuxième et troisième formalisent les idées du premier. Le premier chapitre est très court (2 pages) et ne contient pas d’exposé purement formel (https://pdfslide.net/documents/godels-theorem-in-focus-philosophers-in-focus.html, p.17-19). Je pense que la lecture de ces deux pages est inspirant pour déchiffrer le théorème d’incomplétude de Gödel.

    Le théorème d’incomplétude de Gödel est constitué de la conclusion et de la preuve. Comme conclusion Gödel affirme qu’il existe des « propositions indécidables » dans PM (Principia Mathematica), donc PM est incomplet (ainsi que les systèmes concernés, par exemple Peano Arithmetics); et comme preuve de l’existence d’une telle proposition indécidable dans PM, Gödel construit une proposition Q affirmant sa propre non probabilité dans PM, ce qui est similaire au Paradoxe du Menteur.

    C’est pourquoi j’ai proposé de discuter les 3 questions mentionnées dans mon article :
    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?

    1. Avatar de BasicRabbit
      BasicRabbit

      Joyeuses Pâques à vous également.

      Je n’ai pas le niveau (et de très loin) pour répondre aux questions que vous vous posez. Mais je suivrai avec intérêt le débat que vous appelez de vos vœux, s’il a lieu sur ce blog (avec le commentateur Druup?).

      Bien à vous,
      BR.

      1. Avatar de Yu LI
        Yu LI

        Ruiz, merci de ta correction : ce n’est pas « probabilité », je voulais dire « prouvabilité (en anglais, provability) ».

  9. Avatar de Druuh
    Druuh

    Reprenons les choses une par une si vous le voulez bien.

    Quelques commentaires préliminaires :

    1) BasicRabbit, vos nombreux commentaires sur ce billet et le précédent « what makes a demonstartion worthy of the name » (Goodstein, transduction sur ordinaux infinis, perspectives historiques, etc..) sont très intéressant certes, mais appréciable à leur juste valeur uniquement par des mathématiciens professionnels en logique mathématique, ce qui n’est pas le cas de tout le monde ici. Je propose donc d’être plus terre à terre autant que possible.

    2) Mr Jorion, le simple fait de m’avoir demandé dans le billet précédent des références à propos de « démontrable équivalent à vrai dans tous les modèles » montre votre méconnaissance totale de la logique mathématique, car ce résultat de base est bien connu de tous les étudiants du domaine en 2ème ou 3ème année d’université. Maintenant que vous savez cela, avez vous toujours un problème avec l’existence d’une formule « vraie dans N sans pour autant être démontrable dans Peano » ? Yu Li, quelle est votre position à ce propos ?

    Ceci étant dit, je souhaite faire préciser quelque chose pour qu’il n’y ai pas de malentendu et partir du bon pied : ce sur quoi vous émettez des critiques, est ce le théorème d’incomplétude en tant que tel, ou plutôt sa démonstration par Gödel ? J’avoue ne jamais avoir lu cette démonstration originale, mais une version légèrement différente lorsque j’étais étudiant.

    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)». –> Pourquoi est ce surprenant à vos yeux ? Cela vient juste de la théorie formelle de la démonstration..

    Toute la subtilité dans la (les) preuve(s) du théorème d’incomplétude réside dans un point capital de nature purement technique : la théorie de la récursivité. L’idée géniale de Gödel consiste à expliciter des codages astucieux des formules du langage dans les entiers qui permettent, par exemple, d’obtenir que l’ensemble A des couples d’entiers naturels (a,b) tels que a est le code d’une formule et b le code d’une preuve de a dans T, est un ensemble récursif. Et un autre résultat montre qu’il existe une formule DEM(x,y) du langage qui « représente » cet ensemble de couples d’entiers, i.e. telle que les couples d’entiers de A sont exactement ceux qui vérifient la formule DEM(x,y).

    https://zupimages.net/up/22/15/fbcd.png

    https://zupimages.net/up/22/15/qfsl.png

    Si on n’a pas compris tous les détails et les finesses de la récursivité, ainsi que l’astuce des codages des formules, on ne peut pas comprendre la preuve du théorème.

    1. Avatar de Paul Jorion

      Cher Druuh, voici ce qui caractérise le débat que j’ai ici depuis des années avec des mathématiciens, dont BasicRabbit, Marc Peltier, et plusieurs autres : ils considèrent que je suis à même de comprendre ce qu’ils disent, et je considère réciproquement qu’ils sont capables de comprendre ce que je leur réponds.

      La différence entre mes conversations avec eux et le débat entre vous et moi, c’est que vous considérez que ce que je dis « montre ma méconnaissance totale de la logique mathématique », que je ne comprends pas « tous les détails et les finesses de la récursivité », autrement dit que je n’ai pas le niveau nécessaire pour un débat fructueux avec vous, alors que je vous vois moi vous perdre en cours de route aussitôt que je vous demande la différence que vous établissez entre « vrai » et « démontrable », ce qui me convainc de mon côté, et de manière symétrique, que vous ne possédez pas les bases nécessaires pour participer à un débat sur les fondements des mathématiques. Évitons donc de vous faire perdre davantage de votre temps précieux à tenter de me faire comprendre les notions élémentaires de la logique et des mathématiques, cela me permettra de mon côté de continuer à concentrer mes efforts sur P vs. NP.

      P.S. Je continue de croire que vous pourriez découvrir des choses que vous ignorez en lisant le chapitre 4 de « Comment la vérité et la réalité furent inventées » où j’explique l’évolution de la notion de vérité en mathématiques, de l’invention du calcul infinitésimal par Newton et Leibniz à la démonstration par Gödel de son théorème d’incomplétude de l’arithmétique.

      1. Avatar de BasicRabbit
        BasicRabbit

        @ PJ (« Cher Druuh, voici ce qui caractérise le débat que j’ai ici depuis des années avec des mathématiciens, dont BasicRabbit, Marc Peltier, et plusieurs autres ». )

        Il n’y a jamais eu de débats entre vous et moi, ni sur votre blog ni ailleurs. C’est à la suite de l’un de nos rares et brefs échanges (où, seul, Marc Peltier est intervenu en ma faveur) que j’ai quitté votre blog (pour y revenir très rarement sur des sujets qui m’intéressent -PSI, « Comment la vérité… »-, comme actuellement).

        Je cesse immédiatement et définitivement de commenter sur votre blog pour la raison ci-dessus et aussi pour la façon dont vous rompu tout débat avec Druuh sur les rapports entre vérité et démontrabilité alors que vous vous y étiez engagé (cf. les commentaires d’un autre article récent -de vous cette fois- sur le sujet), en bottant ici en touche pour lui retourner qu’il n’a pas, lui, « les bases nécessaires pour participer à un débat sur les fondements des mathématiques », ce qui n’est pas du tout le sujet.

        @ YuLi. Désolé pour vous: je considère que PJ n’a pas à commenter ainsi sur votre article (qu’il règle éventuellement « ça » sur le sien).

        BR.

        1. Avatar de Paul Jorion

          En effet, il n’y a jamais eu de débat entre vous et moi sur ce blog. Un exemple, parmi des dizaines, de cette absence de débat entre nous, sous votre plume, le 6 janvier 2021 :

          Peut-être PJ a-t-il changé sa position par rapport à Thom ? Moi je suis resté -c’est à dire que je suis parti…- sur cet échange : « BasicRabbit, la différence entre nous, c’est que pour moi René Thom est un mathématicien dont les travaux m’ont toujours fort intéressé et inspiré, mais ce n’est pas un oracle dont la moindre des paroles doit être lue comme du marc de café. (…) Votre révérence à Thom n’est pas d’ordre scientifique mais mystique, c’est cela qui fait que nous ne serons jamais d’accord.  »

          PJ est nominaliste (« la physique est une magie contrôlée par les mots ») alors que Thom ne l’est pas (« la physique est une magie contrôlée par la géométrie ») : cf. p.192 de « Comment la vérité… » -de mémoire-. PJ pense, je crois, comme Aristote pour qui la mathématique est une connaissance des substances abstraites de la matière. Pour moi c’est aussi une connaissance des substances séparées de la matière, c’est-à-dire une théologie au sens d’Aristote. C’est, à mon avis, en substance ce qui sépare (c’est le cas de le dire) Aristote de son maître Platon… et PJ de moi…

          1. Avatar de BasicRabbit
            BasicRabbit

            Ce n’est pas un débat, c’est au contraire le constat qu’il n’y en a pas. J’ai quitté le blog -blog que j’ai toujours considéré comme un divan psychanalytique- peu après l’échange suivant, pour moi d’anthologie, où l’on vous voit vous comporter vis-à-vis de Thom -que vous refusez de voir en philosophe- à peu près de la façon dont je considère que vous vous comportez vis-à-vis de Gödel :

            « PJ: « Non, il n’y a pas de « René Thom de la théorie du chaos ». Il y en a un « de la théorie des catastrophes (élémentaires) » en topologie. »

            BR: Il vaut mieux laisser s’exprimer Thom sur la façon dont il considère sa théorie:
            « Qu’est-ce que la théorie des catastrophes? C’est avant tout une méthode et un langage. Comme tout langage, la théorie des catastrophes sert à décrire la réalité. » (Le statut épistémologique de la théorie des catastrophes)

            PJ: Il vaut peut-être mieux NE PAS le laisser s’exprimer : « méthode et langage » est beaucoup trop vague, alors que dire que c’est une branche de la topologie est très précis.

            BR: « Il vaut peut-être mieux NE PAS le laisser s’exprimer »
            J’espère que vos doigts ont couru sur le clavier sous l’effet d’une pulsion inconsciente. Effet Libet?

            PJ : « BasicRabbit vous êtes un troll au profil particulier : vous ne faites de mal à personne mais quel que soit le sujet abordé, vous poursuivez imperturbablement votre apologie de l’œuvre de René Thom, ce qui ne serait finalement pas trop gênant si vous la représentiez comme celle du mathématicien qu’il fut. Au lieu de cela, vous le présentez comme un oracle dont les phrases citées au hasard pourraient nous éclairer. Cela fait des années que vous faites cela sans bénéfice évaluable. Vous souligniez hier que vous le faites inlassablement, ce qui est incontestable. Je vous ai répondu que nous de notre côté commencions à être lassés, ce que vous n’avez pas voulu relever en dépit du renfort qui me fut rapidement apporté. »

            https://www.pauljorion.com/blog/2014/11/06/la-question-du-soliton-est-devenue-indecomposable/comment-page-1/#comments

  10. Avatar de Druuh
    Druuh

    De deux choses l’une : soit il y a un facheux malentendu entre nous quand nous nous exprimons sur ce sujet, soit vous êtes d’une mauvaise foi confondante. Je préfère envisager la première hypothèse, et je suis prêt à en débattre pour lever tout éventuel malentendu résiduel. A propos de « vrai » et « démontrable », il me semble vous avoir détaillé en long, en large et en travers ce que les mathématiciens logiciens (pas Aristote) entendent précisément par ces deux vocables. Et, comme je l’ai dit de nombreuses fois, Gödel était un mathématicien, pas un philosophe, il se référait donc à des définitions mathématiques dans sa preuve. Où considérez vous donc qu’il reste un point à débattre à ce sujet ?
    Je comprends qu’il y a d’autres points litigieux à vos yeux à propos de cette démonstration, mais allons pas à pas. Commençons par se mettre éventuellement d’accord sur celui ci.

    1. Avatar de Paul Jorion

      Je vous ai dit poliment que je partageais votre sentiment que l’un d’entre nous n’a pas le niveau nécessaire pour poursuivre ce débat. Restons-en là.

  11. Avatar de Druuh
    Druuh

    Dire que quelqu’un qui a fait de la recherche universitaire dans ce domaine n’a pas le niveau n’a aucun sens.

    1. Avatar de Paul Jorion

      Vous ne devez pas fréquenter l’université depuis un certain temps.

  12. Avatar de Yu LI
    Yu LI

    Je pense que c’est une occasion très précieuse pour nous de nous rencontrer et de discuter du théorème d’incomplétude de Gödel, car peu de gens sont prêts à consacrer du temps et de l’énergie à un sujet aussi difficile, délicat, mais fondamental aux différents domains.

    Tout d’abord, permettez-moi de répondre à la de BasicRabbit : pourquoi revisiter maintenant un théorème datant de 80 ans?

    Ma revisite du théorème d’incomplétude de Gödel a lié avec ma recherche sur le problème P vs NP qui est bien connu comme un problème fondamental de la théorie de la complexité (informatique théorique).

    J’ai eu l’occasion d’enseigner ce contenu (partielle) à plusieurs reprises dans l’Université de Picardie Jules Verne, mais c’était une expérience « étrange » sans précédent pour moi, car peu après chaque fois de cet enseignement, je ne ressentais rien d’autre que quelques définitions curantes : P, NP, NP-complétude, sans parler des sentiments des étudiants.

    J’ai rencontré par hasard le philosophe chinois Zhou Jianming lorsque j’ai lu son article sur la comparaison des cultures chinoise et occidentale et j’ai parlé de mon expérience « étrange » d’enseignement sur la matière « théorie de la complexité », et il m’a dit que mon sentiment avait du mérite, car il y avait un emmêlement de forme et de contenu.

    Nous avons donc commencé une collaboration de plus 10 ans sur le problème P vs NP : nous avons décortiqué l’article original de Cook qui posait le problème P vs NP, et découvert la dissonance cognitive causée par l’introduction de l’Oracle dans la preuve de Cook ; nous avons inspiré d’une célèbre proposition de la logique traditionnelle chinoise, «  Cheval blanc n’est pas cheval », pour dissiper la confusion entre la hiérarchie des P et NP dans les définitions courantes. Mais à la fin, j’ai quand-même senti d’avoir atteint un « goulot d’étranglement » : nous savions que NP était étroitement lié au « problème décidable » (Entscheidungsproblem), qui est le sujet étudié par Turing dans son fameux article de 1936, mais qui a été remplacé par une version populaire, « problème d’arrêt ». Le problème est que le « problème d’arrêt » n’a pas été en mesure d’apporter une compréhension éclairante au « problème décidable » qui est étroitement lié au « problème NP » à notre point de vue.

    J’ai fait la connaissance de Paul après avoir lu son billet de blog sur « Cheval blanc n’est pas cheval », et j’ai appris qu’il a remis en question le théorème d’incomplétude de Gödel, ce qui m’a fait penser que le « problème décidable » devrait être poursuivi jusqu’à Gödel, donc nous collaborons pour revisiter ce théorème vieux de 80 ans : je le revisite principalement d’un point de vue algorithmique et logique, tandis que Paul le déchiffre principalement d’un point de vue épistémologique en poursuivant son travail dans « Comment la vérité et la réaliste furent inventés ».

    Comme je l’ai suggéré, afin de rendre notre discussion constructive, concentrons-nous d’abord sur ce que Gödel a dit dans son article, ce que Paul dit et ce que je dis, n’est pas une priorité pour l’instant, sinon nous risquons de tomber dans une dispute sans issue, …

  13. Avatar de un lecteur
    un lecteur

    En lisant Druuh, j’ai un sentiment qui tangente la certitude que le langage mathématique existe de toute éternité. Il n’a pas d’histoire, il attend, impassible, d’être découvert.
    Amour, poésie, sentiment, beauté, physique, technologie, des artéfacts de notre finitude, pauvre de nous sur le point de nous éteindre sans avoir touché le graal.

    1. Avatar de Paul Jorion

      En effet. Les textes mathématiques sont-ils des articles de catéchisme dont toute discussion est blasphématoire ? Ou sont-ils des productions humaines dont la genèse, la personnalité des intervenants, leurs motivations, leurs intérêts, sont pertinents et méritent examen ?

      C’est un vieux débat, dans lequel les partisans du premier point de vue campent sur leur position que les partisans du second sont au mieux des ignorants, au pire des hérétiques. Les seconds se lassent et finissent par ignorer les premiers. Je n’ai pas de dispositions moi à considérer que Gödel soit une seconde manifestation de Moïse et René Thom, la réincarnation de Dieu-le-Père : je lis leurs œuvres comme des productions humaines dont les auteurs sont faillibles, je signale leurs faiblesses et je dénonce leurs erreurs.

      1. Avatar de CloClo
        CloClo

        Strike ! Civilement dit mais dur ! 🤣

        Je vais me mettre à la civilité en fait c’est plus drôle à lire.

      2. Avatar de Druuh
        Druuh

        En vous lisant je confirme qu’il y a un grand malentendu car je n’ai jamais pensé tout cela bien bien que vous soyez persuadé que ça soit le cas.

      3. Avatar de BasicRabbit
        BasicRabbit

        Je pense que la véritable coupure galiléenne -où il n’est pas seulement question de géocentrisme et d’héliocentrisme- a actualisé le divorce entre science et philosophie et qu’il faut tout mettre en œuvre pour refermer cette parenthèse -selon moi dramatique- qui mène l’humanité à la catastrophe. Je pense comme Thom et à sa suite que: « Il faut être philosophe en science et scientifique en philosophie ». Aussi je pense que le commentaire fielleux ci-dessus de PJ est exactement la chose à ne pas écrire (mais je sais que je n’ai aucune chance d’être entendu de lui et, sans doute, de beaucoup de lecteurs de ce blog). Lorsque PJ écrit que « les seconds se lassent et finissent par ignorer les premiers », il est pour moi clair que les mathématiciens portent une lourde responsabilité dont Alain Badiou -un des très rares philosophes contemporains à essayer de s’intéresser à ce qu’ils font- s’est plaint (1).

        Remarque : Il n’est pas besoin de traiter Thom de réincarnation de Dieu-le-Père. Il suffit de le citer: « Selon de nombreuses philosophies Dieu est géomètre; il serait peut-être plus logique de dire que le géomètre est Dieu. » (« Infini opératoire et réalité physique », 1989).

        PJ est matérialiste-nominaliste/conventionaliste-constructiviste et n’est pas platonicien (ce qu’est Thom). PJ fait cependant -à mon avis- un bon bout de route avec Thom dans « Principes des systèmes intelligents : dynamique d’affect et dynamique de gradient. Mais il y a ensuite nette bifurcation, PJ choisissant la voie de l’organon aristotélicien -le miracle grec selon lui…- alors que Thom choisit une autre voie, aristotélicienne mâtinée de platonicienne. Citations thomiennes:

        1- « Il me semble qu’il y a au cœur de l’aristotélisme un conflit latent (et permanent) entre un Aristote logicien, rhéteur (voire même sophiste quand il critique Platon et les Anciens) et un Aristote intuitif, phénoménologue, et topologue quasiment malgré lui. C’est avec ce dernier que je travaille, et j’ai tendance à oublier le premier [avec lequel PJ travaille] ». Cette citation (Esquisse d’une Sémiophysique, p.245) revoie à la note de fin d’annexe suivante: « J’ai découvert depuis la rédaction de ce texte le livre de Daniel W. Graham, Aristotle’s two systems (Clarendon Press, Oxford, 1987), qui expose de manière systématique cette opposition selon lui incompatibles; »;

        2- « En dépit de mon admiration pour ce dernier [Aristote] je reste platonicien en ce que … » (p.244);

        3- Voir aussi le début du chapitre 7 de ES dont voici un extrait : « mon espoir est ici d’apporter quelques éléments mettant en jeu des aspects peut-être difficilement appréciés des spécialistes à qui le problème des rapports entre mathématique et réalité ne s’est jamais posé (…), et non comme le problème essentiel qu’il est effectivement. »;

        4- « Enfin, last but not least, Aristote évoque la présence, par analogie, de l’idée abstraite d’architecture dans la construction et la programmation des organogénèses. On voit ici ce qu’il y a de contradictoire avec la philosophie fondamentalement matérialiste d’Aristote: les Idées platoniciennes n’existent pas mais il faut bien quelque chose comme une Idée pour diriger tout cet ensemble. Voici le modèle que je proposerai pour combler cette lacune (…). (ES, p.167).

        Remarque: dans un commentaire datant de 2012 PJ m’écrivait :

        « Si je ne commente pas personnellement vos présentations de la pensée de Thom, c’est que le plus souvent, je ne reconnais pas Thom dans ce que vous écrivez. Sinon, j’ai beaucoup de respect pour ses manières très aventureuses de s’efforcer de voir les choses autrement. Seule critique : Thom s’affirme constamment « aristotélicien » mais j’ai souvent beaucoup de mal à reconnaître dans l’Aristote dont il parle, celui qui m’est à moi familier. Dit de manière un peu plus directe : je n’ai pas le sentiment qu’il ait consacré beaucoup de temps à la lecture d’Aristote. ».

        PJ s’avance beaucoup quand il écrit: « Je n’ai pas le sentiment qu’il ait consacré beaucoup de temps à la lecture d’Aristote. »: il suffit de lire l’introduction au chapitre « Citations d’Aristote » et la longue note (ES, p.171) « Sur les emplois de ἐνέργεια et ἐντελέχεια » pour s’en convaincre.

        Pour moi PJ et Thom ont chacun leur lecture d’Aristote: point barre.

        1 (à l’attention particulière de Yu Li): à la page 96 et aux suivantes de son « Éloge des mathématiques » (Flammarion 2017) le philosophe platonicien Badiou -ainsi se définit-il lui-même- refait la preuve de Cantor du théorème selon lequel tout ensemble a plus de parties que d’éléments, parlant à ce propos de « tour de magie » : je trouve qu’il y a plusieurs points communs entre cette preuve et la preuve « magique » par Gödel de son théorème d’incomplétude.

  14. Avatar de Yu LI
    Yu LI

    Cher Druuh, merci pour votre critiques franches et Pointus!

    Vous avez dit que :
    – « Ceci étant dit, je souhaite faire préciser quelque chose pour qu’il n’y ai pas de malentendu et partir du bon pied : ce sur quoi vous émettez des critiques, est ce le théorème d’incomplétude en tant que tel, ou plutôt sa démonstration par Gödel ? » 

    Mes critiques portent d’abord sur sa démonstration par Gödel, qui peut être examinée sous l’aspect informel (l’idées de la preuve) et sous l’aspect formel (formalisation de l’idée de la preuve). Bien sûr, ces deux aspects sont intrinsèquement liés, mais pour faciliter notre discussion, concentrons-nous pour l’instant sur l’idée de sa preuve.

    Mon analyse est la suivante, la preuve de l’incomplétude de PM est fondamentalement différente des preuve classiques de théorèmes tels que le Théorème de Pythagore : la preuve de l’incomplétude de PM est une preuve « existentielle », qui requiert une « proposition indécidable » qui existe dans PM, alors que la preuve du Théorème de Pythagore est une preuve « universelle », qui prouve que, pour tout triangle rectangle existant dans le plan, la somme des carrés des longueurs de ses deux côtés rectangulaires est égale au carré de la longueur de l’hypoténuse.

    En d’autres termes, pour prouver l’incomplétude de PM, il faut fournir une instance de propositions indécidables qui existent dans PM, mais ce que Gödel a fourni est une proposition Q similaire au Paradoxe du menteur : « Dites que vous êtes indécidable ».

    C’est pourquoi j’ai demandé :
    – Is the paradoxical proposition Q similar to the liar’s paradox an undecidable proposition in PM? 

    Ma question a en fait été aussi exprimée par Russell dans une lettre écrite à 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 »

    Par conséquent, selon la preuve de Gödel, il existe au moins un paradoxe dans PA (Peano Arithmetics), autrement dit, au moins un axiome doit être faux. Alors après toutes ces années, quel axiome qui est faux a été découvert ?

    1. Avatar de BasicRabbit
      BasicRabbit

      Yu LI: « Is the paradoxical proposition Q similar to the liar’s paradox an undecidable proposition in PM? « .

      La proposition (formule close) Q est appelée G (G pour Gödel !) dans (1). Cette formule -qui, soit dit en passant, n’EST PAS paradoxale- est universelle (plus précisément démontrablement -dans Péano- équivalente à une formule universelle (2). Sous cette forme l’énoncé du théorème de Gödel est : 1°) G est une formule d’arithmétique; 2°) G est démontrablement -dans Péano- équivalente à une formule close universelle (c’est comme dans le théorème de Pythagore !); 3°) G n’est pas démontrable dans l’arithmétique de Péano. 4°) G est vraie dans le modèle standard N de l’arithmétique (G a donc le même statut que l’énoncé du théorème de Goodstein, et même, peut-être, que l’énoncé du théorème de Fermat-Wiles: vrais dans le modèle standard N mais non démontrables dan Péano).

      Remarque de (1): « 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 [Péano] , alors que pour chaque entier n, H(n) est démontrable dans T. « .

      YU LI : « Mes critiques portent d’abord sur sa démonstration par Gödel, qui peut être examinée sous l’aspect informel (l’idée de la preuve) et sous l’aspect formel (formalisation de l’idée de la preuve). Bien sûr, ces deux aspects sont intrinsèquement liés, mais pour faciliter notre discussion, concentrons-nous pour l’instant sur l’idée de sa preuve. ».

      Je pense au contraire qu’il faut se concentrer sur la preuve formelle car le théorème est un théorème de logique formelle et, selon moi, rien d’autre que ça. Bien entendu, lors de sa propre tentative de validation (ou invalidation) de la preuve, il faut se concentrer sur l’idée heuristique (3) fondamentale de Gödel qui est un mixte du paradoxe du menteur et de l’argument diagonal de Cantor (le fameux « G est une formule qui dit bien d’elle-même qu’elle n’est pas démontrable dans Péano »), car il y a là selon moi -et pas que selon moi, je crois…- un côté magique à voir un paradoxe se transformer en théorème. (Personnellement il me semble que les arguments fournis par l’article (1) vont suffisamment au fond des choses pour que je valide la preuve à mon niveau. Mais, je le répète, mon niveau a toujours été très très loin d’être au top.)

      Bien à vous,
      BR.

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

      2: Remarque de (1): « 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 [Péano] , alors que pour chaque entier n, H(n) est démontrable dans T. « .

      3: « L’heuristique ou euristique (du grec ancien εὑρίσκω, heuriskô, « je trouve », est « l’art d’inventer, de faire des découvertes » en résolvant des problèmes à partir de connaissances incomplètes. » ( https://fr.wikipedia.org/wiki/Heuristique ). Terme selon moi parfaitement adapté aux théorèmes d’incomplétude de Gödel (« en résolvant des problèmes à partir de connaissances incomplètes ») !

      1. Avatar de BasicRabbit
        BasicRabbit

        @ Yu Li

        Je viens de relire les pages 323 à 326 « Le mathématicien et sa magie » de « Comment la vérité… » où Gödel est qualifié juste auparavant (p.322) de « platonicien pur porc »(1). Je n’ai jamais compris pourquoi PJ n’avait pas choisi René Thom pour cible, sachant que celui-ci se déclarait lui-même platonicien plus qu’aristotélicien (2) (3), même s’il avançait masqué dans ses premiers articles (4). Thom est cité plusieurs fois dans « Comment la vérité… », à mon avis pas en mal (sauf éventuellement p.192) et parfois en bien (p.53). Thom est également cité, conjointement avec Waddington, dans Principes des Systèmes Intelligents, puisque PJ écrit à la fin du chapitre IV, dans la partie « La méthode dite au coup par coup » retenue par lui pour son programme ANELLA:

        « Cela veut dire que sans avoir à définir des règles a priori qui déterminent les parcours légaux à l’intérieur du lexique, on peut imaginer que soient en place de manière constante des « chenaux », des chréodes (*), des passages privilégiés pour se rendre d’un mot à un autre. »

        Dans Stabilité Structurelle et Morphogenèse, la première œuvre non exclusivement mathématique majeure de Thom (sous-titrée « Essai d’une théorie générale des modèles »), celui-ci propose dans le chapitre 9 (épigraphé « Et le Verbe s’est fait chair »…) des modèles locaux en embryologie, le dernier -et selon moi le plus compliqué- étant décrit sous le titre « Chréodes génitales » (2ème ed. p.190). Et dans la deuxième édition de 1977 (mais pas dans celle de 1972), il consacre un paragraphes aux automatismes du langage (pp.311 à 315).

        Dans « Comment la vérité… » PJ daube beaucoup plus -en fait presque exclusivement- sur les mathématiques pythagoriciennes (« Tout est nombre ») et très peu sur les mathématiques platoniciennes (« Tout est géométrie »). Thom est et se proclame géomètre et ne cache pas son désintérêt pour l’arithmétique et l’algèbre pures (en allant jusqu’à écrire « Tout ce qui est rigoureux est insignifiant » ! ):

        « C’est parce que la mathématique débouche sur l’espace qu’elle échappe au décollage sémantique créé par l’automatisme des opérations algébriques ».

        Il modérera ce désintérêt à l’heure du bilan:

        « En mathématique pure, mes propres résultats n’allèrent guère au-delà de développements limités de certaines singularités de potentiel. Il fallut la pertinence de mathématiciens américains (Milnor) ou européens (théorie du déploiement universel, Grauert, J. Martinet) pour sortir la théorie de son marasme initial. Mon seul apport à la théorie mathématique fut d’introduire la notion de « déploiement universel » – corrigé peu après en versel par les collègues algébristes (Mather). Il n’y a pas de doute que des mathématiciens américains (Mather,Milnor), puis soviétiques (Arnold) ont apporté à la théorie des singularités des progrès décisifs. La vision de ces mathématiciens m’a fait comprendre combien la théorie des singularités a des origines profondes en mathématiques. C’est la rencontre de mathématiciens soviétiques comme Arnold (souvent férocement critique de mes procédés rustres) qui m’a fait comprendre à quel point la théorie des singularités tire son origine de structures profondes (Polynômes de Dynkin, carquois de Gabriel, théorie des tresses, immeubles de Tits). L’intérêt de la T.C. est bien d’avoir attiré l’attention sur ces théories « profondes » dont la source reste (pour moi) bien mystérieuse.».

        Pourquoi PJ s’est-il attaqué au « platonicien » Gödel mais pas au platonicien Thom ? Ça restera un mystère pour moi car pour moi Thom est un véritable mathématicien alors que Gödel n’est qu’un logicien formaliste.

        Bien à vous,
        BR.

        1: «La position platoniste est la seule qui soit tenable. Par là, j’entends la position selon laquelle les mathématiques décrivent une réalité non sensible qui existe indépendamment aussi bien des actes que des
        dispositions de l’esprit humain et qui est seulement perçue de façon très incomplète par l’esprit humain.» K. Gödel, Collected Works, 1951, t III, p 323.

        2: Apologie du logos (Hachette 1990), pp. 558 à 568, où Thom critique l’approche formaliste (p.559).

        3: « En dépit de mon admiration pour Aristote, je reste platonicien en ce que… », Esquisse d’une sémiophysique, pp.244 et 245).

        4: Cf. le paragraphe « Mathématiques et réalité », Modèles mathématiques de la morphogenèse, 10/18, 1974, p.24.

        *: « On pense immédiatement aussi au terme de chréode introduit par Waddington (1957 : 32) pour rendre compte de passages obligés tout à fait analogues en embryologie (cf. aussi Thom 1972 : 121-123 ; Thom & Waddington 1967). ».

        1. Avatar de Paul Jorion

          pourquoi PJ n’avait pas choisi René Thom pour cible

          Parce que mon objectif n’a jamais été de choisir des « cibles », j’ai écrit un livre sur l’histoire des notions de « vérité » et de « réalité(-objective) » où le traitement cavalier de la notion de vérité par Gödel trouve sa place. Je n’ai jamais rien lu par contre sous la plume de Thom quant à ce qu’il regarde être la vérité qui m’ait choqué.

  15. Avatar de BasicRabbit
    BasicRabbit

    PJ: « Je n’ai jamais rien lu par contre sous la plume de Thom quant à ce qu’il regarde être la vérité qui m’ait choqué ».

    Et pour cause ! Car je crois que Thom ne s’intéresse que très peu à la vérité. Quelques citations de lui à ce propos :

    « Mais le problème important -en matière de philosophie du langage- n’est pas celui de la vérité (affaire d’accident, Sumbebèkos dirait Aristote), mais bien celui de l’acceptabilité sémantique, qui définit le monde des « possibles », lequel contient le sous-ensemble (éminemment variable) du réel. » ;

    « C’est-à-dire que pour nous, la question de l’acceptabilité sémantique d’une assertion est un problème ontologiquement antérieur à celui de sa vérité. La vérité présuppose une signification. L’idéal des logiciens (et de certains mathématiciens) d’éliminer la signification au bénéfice de la seule vérité est un contre-sens philosophique. » ;

    « (…) la vérité d’une assertion n’est pas un problème pertinent en ce qui concerne son expression linguistique. L’implication marche en sens inverse : toute expression, pour être vraie (ou fausse) doit nécessairement être linguistiquement bien formée, et être susceptible de recevoir un sens (dans un contexte assez général, non fabriqué ad hoc). » ;

    « Ce qui limite le Vrai, ce n’est pas le Faux, mais l’insignifiant. » ;

    « Mais la distinction Vrai-Faux n’a guère d’intérêt métaphysique. Elle n’engage pas la structure de l’être. » .

  16. Avatar de Yu LI
    Yu LI

    Merci beaucoup d’avoir participé à cet échange ! Cela m’a aidé à clarifier mes idées et à voir où elles étaient insuffisantes.

    @BasicRabbit, 1, vous dites:La proposition (formule close) Q est appelée G (G pour Gödel !) dans (1). Cette formule -qui, soit dit en passant, n’EST PAS paradoxale- est universelle (plus précisément démontrablement -dans Péano- équivalente à une formule universelle (2). Sous cette forme l’énoncé du théorème de Gödel est : 1°) G est une formule d’arithmétique; 2°) G est démontrablement -dans Péano- équivalente à une formule close universelle (c’est comme dans le théorème de Pythagore !); 3°) G n’est pas démontrable dans l’arithmétique de Péano. 4°) G est vraie dans le modèle standard N de l’arithmétique (G a donc le même statut que l’énoncé du théorème de Goodstein, et même, peut-être, que l’énoncé du théorème de Fermat-Wiles: vrais dans le modèle standard N mais ne démontrables dan Péano).

    Comment comprenez-vous le sens du mot « vraie » dans la phrase « G est vraie dans le modèle standard N de l’arithmétique » ?

    2,Vous dites:fondamentale de Gödel qui est un mixte du paradoxe du menteur et de l’argument diagonal de Cantor (le fameux « G est une formule qui dit bien d’elle-même qu’elle n’est pas démontrable dans Péano »), car il y a là selon moi -et pas que selon moi, je crois…- un côté magique à voir un paradoxe se transformer en théorème.

    Je partage votre curiosité de voir un paradoxe se transformer magiquement en théorème.

    Mon analyse du premier chapitre du texte original de Gödel (ce billet de blog) montre que un paradoxe se transforme magiquement en théorème, parce que Godel a introduit des « présuppositions impropres » dans sa preuve.

    Mon argument n’est pas suffisant, car je n’ai pas fini de lire le deuxième et le troisième chapitres du texte original de Gödel. Je poursuivrai probablement notre discussion plus tard, lorsque j’aurai lu les deuxième et troisième chapitres,…

  17. Avatar de BasicRabbit
    BasicRabbit

    @ Yu Li: « Comment comprenez-vous le sens du mot « vraie » dans la phrase « G est vraie dans le modèle standard N de l’arithmétique » ? ».

    C’est la définition classique en théorie des modèles formels. Par exemple typique, un groupe additif est un modèle de la théorie des groupes et l’énoncé ∀ x ∀ y (x+y=y+x) est vrai dans tout groupe commutatif et faux dans tout groupe non commutatif. (Puisqu’il existe des groupes commutatifs et des groupes non commutatifs, il suit donc du théorème de complétude (de Gödel !) que cette formule close n’est pas un théorème de la théorie des groupes.)

    Je pense que la référence suivante vous suffira: https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_mod%C3%A8les#Les_mod%C3%A8les_dans_le_calcul_des_pr%C3%A9dicats . (Le premier exemple montre comment on prouve sémantiquement une formule à l’aide du théorème de complétude.)

    Pour une présentation encore plus formelle (dans le cadre de la théorie des ensembles de Zermelo et Fraenkel) : https://fr.wikipedia.org/wiki/Axiomes_de_Peano#Existence_et_unicit%C3%A9

    Je pense qu’on a acquis une bonne idée de la vérité dans le modèle standard N de l’arithmétique de Peano quand on a compris -je crois que c’est mon cas…- le théorème de Tarski (qui est à la vérité ce que le théorème d’incomplétude de Gödel est à la démontrabilité) : https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Tarski

    (Dans une présentation soignée la notion de vérité/satisfaisabilité dans un modèle se définit récursivement.)

    Bien à vous,
    BR.

    1. Avatar de BasicRabbit
      BasicRabbit

      @ Yu Li

      La théorie sémantique de la vérité est due à Tarski (1).

      PJ en écrit ceci dans « Comment la vérité… » (p.131):

      « Une fois qu’on a dit, à la suite de Tarski, que « la neige est blanche » est vrai si la neige est blanche, on peut aussi bien rentrer chez soi : la question de la vérité et de la fausseté des énoncés ne court plus aucun risque de se voir un jour éclairée ».

      Il écrit aussi plus loin (p.300) que dans « le catalogue des types de propositions vraies: il y a celles qui sont vraies parce que leur contenu tombe sous le sens […] Il y a aussi celles qui sont vraies par convention parce qu’elles sont des définitions ».

      Il ne fait guère de doute pour moi que la définition de la vérité par Tarski rentre exactement dans ce cadre car sa définition tombe sous le sens ! Aussi, contrairement à ce qu’écrit PJ p.131, je considère que cette définition n’a pas besoin d’être éclairée puisqu’elle est lumineuse (et fructueuse -au moins du point de vue des logiciens formalistes-).

      La démonstration dans l’arithmétique de Peano de la proposition s0+s0=ss0 -où s est le symbole de la fonction successeur- occupe toute une page des « Principia Mathematica » de Russell et Whitehead . Il suit alors du théorème de complétude que l’on a 1+1=2 dans tous les modèles de cette arithmétique.

      À rapprocher de ce qu’écrit PJ p.300 : « il y a celles [les propositions] qui sont vraies parce que leur contenu tombe sous le sens, et que chacun les tenant pour vraies il est légitime de les faire intervenir comme prémisses dans les raisonnements », et de ce qu’il écrit pp.272 et 273.

      1: https://fr.wikipedia.org/wiki/Th%C3%A9orie_s%C3%A9mantique_de_la_v%C3%A9rit%C3%A9

      1. Avatar de Yu LI
        Yu LI

        Ce dont vous avez parlé est très riche et j’aurai besoin plus de temps pour le digérer.

        Je m’interroge sur la notion de « vrai » , car je voulais comprendre l’expression courante du théorème d’incomplétude de Gödel : il existe des propositions en arithmétique de Peano qui sont «  vraies mais indémontrables » .

        À 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

        D’après ce que j’ai compris, une proposition « vraie mais indémontrable » en l’arithmétique de Peano est une proposition « vraie », c’est-à-dire une proposition qui a une valeur de vérité définie, soit vraie soit fausse, mais qui ne peut être déterminée par une preuve dans l’arithmétique de Peano comme étant vraie ou fausse.

        Par exemple, le « théorème de Goodstein », la séquence de Goodstein impliquée est un objet mathématique réel dans l’arithmétique de Peano avec une valeur de vérité définie, seulement, il n’est pas démontrable dans l’arithmétique de Peano, mais il est démontrable dans la théorie des ensembles.

        Cependant, si une proposition concernant un objet qui n’existe pas du tout, elle n’est bien sûr pas démontrable, comme dans le cas de « le roi de France actuel est chauve » (Russell), qui n’est ni vraie ni fausse, mais il s’agit d’une erreur. Dans ce cas, ce n’est pas du tout la même chose que le « théorème de Goodstein » qui n’est pas démontrable en arithmétique de Peano.

        Si la preuve du théorème d’incomplétude de Gödel construit un paradoxe, alors il s’agit d’une proposition imaginaire et non réelle (vraie).

        Je voulais donc comprendre, comme vous, comment Gödel a transformé par magie un paradoxe «  imaginaire » en une proposition « vraie » au sens « réelle », …

        1. Avatar de Paul Jorion

          Je voulais donc comprendre, comme vous, comment Gödel a transformé par magie un paradoxe « imaginaire » en une proposition « vraie » au sens « réelle »

          Je vous signale à tous deux, que j’en ai offert une explication détaillée dans Comment la vérité et la réalité furent inventées, un livre publié en 2009 :

          Les formules qui « parlent d’elles-mêmes »

          Ce à quoi on assiste, c’est donc ceci : je démontre une proposition et je découvre que – message codé à l’intérieur de cette formule – cette proposition dit d’elle-même « je ne suis pas démontrable ». Soit, à l’inverse, je démontre la négation d’une proposition et je découvre que cette proposition dit d’elle-même « en réalité, je suis démontrable – mais sous mon expression positive ». Qu’est-ce que cela signifie ?

          Le profane en matière de mathématiques notera d’abord qu’une formule arithmétique n’ayant pas de langue, elle ne peut rien dire à propos de quoi que ce soit, et en particulier rien à son propre sujet. Or il n’y a pas eu que des anthropologues et autres philosophes pour faire cette remarque de bon sens, des mathématiciens les ont précédés et précisément à propos du second théorème de Gödel, qui ne fait donc pas nécessairement l’unanimité dans la profession à ce sujet. En effet, en 1945, R. Daval et G.-Th. Guilbaud que j’ai cités plus haut à propos de la récursion, dans leur remarquable ouvrage, Le raisonnement mathématique, font observer que : « Seul le mathématicien peut dire qu’une proposition est démontrable, une proposition ne peut pas dire cela d’elle-même » (Daval & Guilbaud 1945 : 45).

          Quand je démontre une proposition mathématique, disons un théorème, et qu’à l’intérieur de ce théorème se trouve caché l’énoncé « Je ne suis pas démontrable », il s’agit en fin de compte de ma parole à moi, mathématicien, contre celle de cette proposition. En ce qui me concerne, je suis un sujet humain et j’ai la capacité d’expliquer par le raisonnement pourquoi j’affirme que cette proposition est démontrable : c’est parce que je disposais au départ d’un ensemble d’axiomes, de théorèmes et de règles d’inférence qui m’ont permis, une fois tracé le chemin qui mène des axiomes et des théorèmes à la proposition à démontrer, de dire que le balisage du parcours équivaut à affirmer qu’elle a effectivement été démontrée. Au contraire, cette proposition quant à elle ne peut rien produire à l’appui de sa déclaration qu’elle est indémontrable : tout énoncé suppose un sujet qui s’engage – par l’expression d’un degré d’adhésion – vis-à-vis de la vérité de ce qu’il énonce (cf. ce que j’en dis dans la deuxième partie ainsi que dans Jorion 1990a, chapitre 20). Une formule est à ce point de vue impuissante : n’étant pas un sujet humain, elle ne dispose d’aucun des outils de la panoplie discursive qui lui permettraient de prouver sa démontrabilité ou sa non-démontrabilité par les moyens habituels d’inculcation de la preuve. De plus, il m’est impossible de lui assigner aucune des motivations qui pourraient jouer un rôle positif ou négatif vis-à-vis de son engagement, je ne peux pas supposer sans doute qu’elle mente sciemment sur la question, mais à l’inverse je ne suis pas à même de lui assigner une expertise particulière quant à la possibilité ou non de sa démonstration : elle ne dispose ni de la capacité d’être bien ou mal informée sur ses propres caractéristiques, ni de celle de s’exprimer à ce sujet. Ce n’est donc pas parce qu’une formule dit au niveau méta-mathématique qu’elle est démontrable au niveau mathématique, qu’il y a là la moindre garantie de véracité.

          L’origine du fait que cette proposition affirme sa non-démontrabilité nous la connaissons en fait parfaitement : c’est une conséquence, recherchée par son auteur, du système de codage mis en place. Je peux très bien imaginer – puisque cela dépend uniquement de la subtilité du système d’encryptage utilisé – qu’une proposition puisse « se tromper » quant à la démontrabilité de la proposition arithmétique qu’elle est à un autre titre. Je vais présenter plusieurs paradoxes, de complexité croissante qui permettront de cerner la démarche de Gödel.

          Premier paradoxe. Arthur ouvre une boîte. Dans celle-ci il y a un billet sur lequel il est écrit « Il n’y a pas de billet dans la boîte ». Arthur se dit, « Tiens, c’est curieux, j’aurais juré qu’il y avait un billet ». Arthur est un niais. Pourquoi ? Parce qu’il a constaté de la seule manière dont on puisse le faire valablement qu’il y avait un message dans la boîte. Le fait qu’il soit écrit sur celui-ci « Il n’y a pas de billet dans la boîte » ne devrait pas influencer Arthur dont la conviction devrait rester inentamée. Le contenu du message inscrit sur le billet nie les faits, il est erroné et devrait être ignoré par Arthur.

          Deuxième paradoxe. À force d’astuce, Isidore arrive à décoder un message. Sa déception est grande cependant quand il constate que le message décrypté dit : « Coucou ! Tu n’es pas arrivé à me déchiffrer ! » On pourrait imaginer bien sûr qu’il existe plusieurs niveaux possibles d’encryptage et que celui qu’Isidore vient de découvrir n’est que le plus simple. S’il n’existe qu’un seul niveau, Isidore a cependant tort d’être déçu. Pourquoi ? Parce qu’en réalité il est parvenu à décoder le message. Ce que celui-ci exprime n’est qu’une tentative dérisoire de la part du codeur de convaincre le déchiffreur qu’il a échoué dans sa tâche. Le message ne dispose d’aucune autorité pour nier l’évidence : qu’Isidore a au contraire réussi.

          Troisième paradoxe. Eusèbe a inventé un chiffre ingénieux. Á partir d’un texte chinois, le code génère des phrases en français qui disent soit « Ce que dit cette phrase est vrai », soit « Ce que dit cette phrase est faux ». Eusèbe a pu constater que son système fait une analyse irréprochable de l’ensemble des textes chinois qu’il a pu lui soumettre. Un riche éditeur lui fait la proposition suivante : « À chaque phrase commentée avec exactitude je te donne cent euros, mais si ton système se trompe tu auras la tête tranchée ». Eusèbe doit-il accepter l’offre alléchante ? Il y a un rapport entre cette illustration et la question de la récursion dont on a vu qu’il ne s’agit pas à proprement parler d’un mode de preuve mais d’un procédé qui confirme à chaque coup sa réussite, mais sans apporter aucune garantie « quant au fond » qu’il en sera toujours ainsi. À moins qu’Eusèbe ne soit convaincu que son procédé dépasse par ses capacités celles d’un simple système de codage, autrement dit, à moins qu’Eusèbe ne soit certain que son système « comprend » en réalité le chinois, et pose des jugements infaillibles à partir de cette compréhension, nous lui déconseillerions d’accepter l’offre du millionnaire.

          Quatrième paradoxe. Imaginons que Casimir, cryptographe extrêmement habile, ait mis au point le code qui permet de faire la chose suivante, partant du texte de l’Évangile selon Saint Mathieu, le système engendre, phrase après phrase, une version parfaitement correcte des « Trois mousquetaires ». Casimir découvre à sa grande stupéfaction, que – détonnant avec le reste du texte – la phrase qui dit « Je serai assis à la droite de mon Père » est automatiquement traduite par le système d’encryptage en « En réalité, c’est à la droite de son Oncle ». Que faut-il penser de la consternation de Casimir ? Si elle est due au fait qu’il constate ainsi les limites du chiffre qu’il a mis au point, il doit se rassurer : un effort supplémentaire lui permettrait peut-être d’améliorer son système. Si sa stupeur est due au contraire au fait qu’il suppose avoir mis à jour un secret déroutant relatif au christianisme, il est bête : son système fonctionnait jusqu’à la phrase incriminée du texte, et se remet à fonctionner ensuite, mais il fait la preuve de son incapacité à traduire un évangile en un roman d’Alexandre Dumas à cet endroit précis. À voir la perfection avec laquelle l’encodage permet d’établir un lien entre les deux textes, Casimir s’est convaincu que la garantie divine qu’il associe à l’un des deux au moins s’attache aussi au code qu’il a mis au point. C’est lui qui l’a inventé sans doute mais la surréalité qui s’attache à la possibilité même de cette traduction l’a convaincu que seule une inspiration divine expliquait sa genèse. Du coup, la phrase qui seule détonne ne peut manquer d’être significative à ses yeux.

          Qu’ont donc en commun Arthur, Isidore, Eusèbe et Casimir ? Ce qu’ils perdent de vue, c’est que dans chacun des cas, le contenu du message reste en extériorité par rapport à la situation qu’il commente ou exprime. Leur coïncidence apparente n’est pas la conséquence de leur consubstantialité  : elle est le résultat d’un artifice qui révèle en arrière-plan un acteur humain à même d’évaluer la situation en toute connaissance de cause, et qui est alors l’auteur authentique du commentaire. Lorsqu’il s’agit d’un code, comme avec Isidore, Eusèbe et Casimir, quel que soit le talent déployé dans sa mise au point, le message qui résulte du codage et le message codé demeurent étrangers l’un par rapport à l’autre, quel que soit l’effort qui a été consenti pour les lier de manière inextricable. Ils sont bien traduisibles l’un dans l’autre, mais ils n’ont pas acquis pour autant une identité unique qui permettrait d’interroger l’un et d’obtenir de lui une réponse justifiée portant sur l’autre.

          Il est possible que la confusion qu’on constate ici ait été encouragée par l’interchangeabilité dans l’usage courant des mots codage et traduction. Alors qu’une phrase traduite d’une langue renvoie en principe à la même exacte réalité que la phrase originale, une phrase codée ne le fait pas en général : mieux, c’est la finalité même du codage qu’il n’en soit pas ainsi. Si je dis soit « je coupe cette pomme », soit « I’m cutting this apple », c’est la même pomme qui se trouve séparée en deux à la fin du processus. Mais si je dis « Les sanglots longs des violons », ceci veut dire pour ceux qui savent entendre que « le débarquement en Normandie débutera demain ». La consubstantialité des états-de-choses connotés dans la traduction n’est pas due à une capacité dont disposeraient certaines phrases à « parler de la même chose » dans des langues différentes, elle résulte de l’activité délibérée du traducteur visant ce résultat – celui-ci pouvant être plus ou moins talentueux – exactement de la même manière que la dimension cryptique du message encodé résulte de l’intention du codeur d’en cacher la signification initiale. Pour prendre un exemple historique : « À la recherche du temps perdu », est-il traduit de manière plus heureuse par « In search of lost time » ou par « Remembrance of things past » ?

          Quand Gödel écrit à propos de sa proposition démontrable qui dit d’elle-même qu’elle n’est pas démontrable que « … c’est seulement ensuite (et en quelque sorte par hasard) qu’il s’avère que cette formule est précisément celle par laquelle la proposition était elle-même exprimée » (Gödel 1992 [1962] : 41), on est alors en droit de lui demander quelle est la nature exacte de ce « hasard » qui fait qu’un commentaire méta-mathématique sur la démontrabilité d’une proposition se retrouve codé dans son énoncé. Suggère-t-il sérieusement que cet encodage ne résulte pas de l’effort considérable qu’il a lui, mathématicien, consenti pour l’obtenir ? Suggère-t-il, s’il n’y a pas eu effort, qu’il y a eu simple révélation ? À cette dernière question – et comme nous pouvions déjà nous en douter quand nous nous étions demandé plus haut « D’où viennent les propositions vraies ? » – la réponse est en réalité, « Oui ».

  18. Avatar de Druuh
    Druuh

    Yu Li, je crois comprendre que vous faites une confusion entre calcul propositionnel et calcul des predicats.

    En logique mathematique, le calcul propositionnel assigne une valeur (vrai ou faux, 0 ou 1) a chaque proposition elementaire contenue dans une formule complexe, et la valeur de cette derniere est determinee par le calcul dans l’algebre de Boole (0 ET 1 donne 0, 0 OU 1 donne 1, etc..). Je crois que c’est a cela que vous faites reference quand vous evoquez la notion de vrai.

    Cependant, le cadre du theoreme de Godel n’est pas la logique propositionnelle, mais la logique des predicats. La formule dont parle Godel est une formule du calcul des predicats. Ces formules, contrairement aux formules propositionnelles, font intervenir des variables et des quantificateurs. Elles n’ont pas de valeur de verite en soi, mais en relation avec des structures : la meme formule peut etre vraie dans une structure, mais pas dans une autre.
    la formule « pour tout x, pout tout y, xy=yx » est vraie dans un groupe commutatif, mais fausse dans un groupe non commutatif.
    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).

    Cela vous eclaire t il ? Aviez vous deja compris tout cela ? Ou vous ai je mal compris ?

  19. Avatar de Yu LI
    Yu LI

    @Druuh Ce que je voulais discerner, c’est si la proposition « vraie mais indémontrable » construite par Gödel est une réelle proposition qui existe dans un système formel comme PA.

    Si cette proposition « parle d’elle-même » comme le « paradoxe du menteur », alors ce qui apparaît, que ce soit sous la forme d’une formule propositionnelle ou d’une formule de prédicat, n’est pas une proposition réelle pour PA, mais imaginaire.

    En ce qui concerne la proposition qui « parle d’elle-même », je trouve que le passage cité par Paul est instructif :
    « Seul le mathématicien peut dire qu’une proposition est démontrable, une proposition ne peut pas dire cela d’elle-même » (Daval & Guilbaud 1945 : 45).

    En outre, Peirce a discuté très clairement qu’une proposition comme le « paradoxe du menteur » est une proposition non-sens (voir PEIRCE’S PARADOXICAL SOLUTION TO THE LIAR’S PARADOX, EMILY MICHAEL,
    https://www.researchgate.net/publication/266930857_Peirce's_paradoxical_solution_to_the_Liar's_Paradox)

    La question suivante est donc la suivante :
    1. Si la proposition construite par Gödel est, par sa nature, une proposition qui « parle d’elle-même », ça signifie qu’il existe probablement un biais cognitif dans la preuve du théorème d’incomplétude de Gödel.
    2. Si non, quelle est cette proposition ? Quelle est sa nature ? Comment a-t-elle été construite ?

  20. Avatar de Druuh
    Druuh

    Je reprends un commentaire de votre article : « 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)» ».

    Pourquoi trouvez vous étonnant que Godel dise qu’une preuve est une séquence finie de formules ?

  21. Avatar de Yu LI
    Yu LI

    @BasicRabbit Vous dites :
    – Pour moi la question « philosophique » posée par les théorèmes d’incomplétude de Gôdel est de savoir si on peut tirer une connaissance objective (un théorème) d’une connaissance subjective liée à l’auto-référence (« je me mens »). On est là, à mon avis, dans ce que je considère comme le top de la métaphysique (l’étude de l’être en tant qu’être, selon Aristote). Je n’ai pas de réponse…

    En d’autres termes, vous demandez : quelle est la relation entre le « paradoxe du menteur » et la « proposition indémontrable » du système formel ?

    Par conséquent, je pense qu’il est crucial de poser la question suivante :
    – quelle est l’essence de ce qui rend les propositions dans un système formel démontrable ou indémontrable ?
    – la proposition construite par Gödel fournit-elle une explication raisonnable à une telle question ?

    L’approche la plus élémentaire devrait consister à étudier le texte original de Gödel, …

    1. Avatar de BasicRabbit
      BasicRabbit

      @ Yu Li : « L’approche la plus élémentaire devrait consister à étudier le texte original de Gödel, … ».

      Ce n’est pas comme ça que je procéderais. L’histoire des sciences montre en effet que de nombreux « outils » mathématiques ont eu une origine autre que mathématique, en général physique mais pas toujours (origine comptable en ce qui concerne les nombres -invention du zéro et des nombres négatifs-), et que les notions nouvellement introduites ont mis parfois très longtemps avant d’être digérés (dernière en date: la renormalisation en physique quantique). De même les premières démonstrations de plusieurs théorèmes importants ont été erronées (récemment Wiles et Perelman ont revu leur copie plusieurs fois avant que leur preuve soit acceptée par la communauté mathématique): que d’autres refassent les démonstrations, en trouvent de nouvelles plus simples et plus intelligibles, arrivent à affaiblir au maximum les hypothèses, fait qu’à mon avis la meilleure approche consiste à partir de ce qu’il y a de mieux actuellement sur le marché, pour revenir ensuite sur le texte original publié par Gödel, et enfin -éventuellement- sur les bruits de couloir et les notes raturées retrouvées dans une corbeille à papier.

      Je vous ai signalé https://www.lmno.cnrs.fr/archives/dehornoy/Books/Ensembles/chapLI.pdf dans mon commentaire du 15/04 19h02. Je vous ai aussi signalé https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del mais je ne vous le recommande pas car je ne connais pas le niveau de l’auteur (il est question dans la discussion d’une « preuve à revoir » concernant le point crucial de la diagonalisation, ce qui incite à la méfiance).

      Je vous ai dit que j’avais confiance en ce qu’écrit en français Patrick Dehornoy sur le sujet. Il note au début du chapitre VIII de « Complexité et décidabilité » (??) :

      « Sources et compléments. On a cherché ici à isoler les points techniques importants mais en allant au plus vite vers les résultats de la section 4. Un traitement plus détaillé et complet se trouve en particulier dans le livre [109] de P. Smith [que je suppose être en anglais!].

      Pour moi l’idéal consiste à trouver quelqu’un de vivant qui domine le sujet et qui accepte d’en discuter avec vous. Je vous ai dit que ce ne peut être Patrick -qui n’est plus- ni moi non plus, qui suis incompétent (et depuis longtemps plus du tout passionné par le sujet).

    2. Avatar de BasicRabbit
      BasicRabbit

      Je résume là où j’en suis.

      1; La définition par Tarski de la vérité dans un modèle d’une théorie est correcte et respecte en tout point ce que PJ requiert pour une vérité pour lui acceptable dans « Comment la vérité… » (p. 207) : la définition tarskienne de la vérité est celle qui tombe sous le sens.

      2: Le « théorème de Ladrière », que j’appelle ainsi en référence à « Comment la vérité… » p. 298, est correct pour les énoncés de la forme ∃ x P(x) où P est une formule d’arithmétique sans quantificateurs (énoncés classiquement dénommés Σ1 dans le jargon des logiciens).

      3: La formule G de Gödel est (démontrablement dans PA1 -P pour Peano, A pour Arithmétique, 1 pour premier ordre-) équivalente à la négation d’une formule Σ1 (en jargon G est démontrablement équivalente à une formule Π1).

      4: Dans la preuve par Gödel (et par beaucoup d’autres) du théorème d’incomplétude il y a dissymétrie entre vérité et démontrabilité: la formule G de Gödel est vraie dans le modèle standard N si et seulement si elle n’est pas démontrable dans PA1 (et les preuves de la non démontrabilité de G et de la non démontrabilité de non G sont dissymétriques).

      Je pense que c’est une base solide (par prudence à faire cependant valider par plus compétent que moi…) à partir de laquelle vous pourrez progresser dans la compréhension du théorème d’incomplétude (je m’adresse à Yu Li).

      Yu Li: « En d’autres termes, vous demandez : quelle est la relation entre le « paradoxe du menteur » et la « proposition indémontrable » du système formel ? ».

      Pour moi tout ce qui est auto-référent (phrases commençant par « je me » comme « je me connais », « je me mens », ou contenant auto (automate, auto-organisation, auto-reproduction, etc.) renvoie au top de la métaphysique (étude de l’être en tant qu’être). Le théorème d’incomplétude permet de paraphraser le célèbre « L’être est, le non-être n’est pas » de Parménide en « Ce qui est vrai est, ce qui n’est pas vrai n’est pas » et « Ce qui est démontrable est, ce qui n’est pas démontrable n’est pas ». D’après 4 la vérité est plus forte que la démontrabilité -en ce sens que tout ce qui est démontrable est vrai et que G est vraie et non démontrable-, ce qui tend à donner raison à la thèse que défend PJ dans « Comment la vérité… ». À condition de s’appuyer sur le théorème d’incomplétude de Gödel…

      Si ce qui précède a un sens, cela aura pour conséquence de diminuer l’importance de la démonstration en mathématiques, mais pas nécessairement de dévaluer les mathématiques elles-mêmes (considérées comme technologie de l’imaginaire).

      Thom : « Dans sa confiance en l’existence d’un univers idéal, le mathématicien ne s’inquiétera pas outre mesure des limites des procédés formels, il pourra oublier le problème de la non-contradiction. Car le monde des Idées excède infiniment nos possibilités opératoires, et c’est dans l’intuition que réside l’ultima ratio de notre foi en la validité d’un théorème -un théorème étant avant tout, selon une étymologie aujourd’hui bien oubliée, l’objet d’une vision-. (Apologie du logos, Hachette 1990, p.561).

      Au Wittgenstein.1 logiciste anti-psychologiste a succédé un Wittgenstein.2. Un PJ.2 succédant au PJ.1 ?

      1. Avatar de Paul Jorion

        Merci pour cette excellente synthèse et excellent point sur la question.

        1. Avatar de BasicRabbit
          BasicRabbit

          Merci. Je ne m’y attendais pas (« À condition de s’appuyer sur le théorème d’incomplétude de Gödel… « ).

  22. Avatar de Yu LI
    Yu LI

    @Druuh Le titre de l’article de Gödel est «  On Formally Undecidable Propositions of Principia Mathematica and Related Systems I », ça signifie que le sujet de son étude était la  » preuve  » d’une formule.

    Mais dans le chapitre 1 de son article où Gödel introduit son idée de preuve en disant :
    « Similarly, proofs, from a formal point of view, are nothing but finite sequences of formulae (with certain specifiable properties)»

    J’ai été donc frappée par son manque d’attention au statut spécial de la  » preuve « , et je crains que dans le chapitre 2 où il élaborait sa preuve formelle, il confonde  » preuves  » avec « formules », perde la  » preuve  » comme sujet d’étude, et créé un biais cognitif.

    J’espère pouvoir clarifier mes doutes au cours de ma lecture du chapitre 2.

  23. Avatar de BasicRabbit
    BasicRabbit

    Quelques jours avant cet article de Yu Li, PJ a publié (le 9 avril) un article sur le même sujet intitulé « What makes a demonstration worthy of the name? « , traduction anglaise de « Que démontrent les mathématiciens, et le font-ils d’une manière digne de ce nom ? », du 5 mars 2022, titre que je traduis -mes connaissances en anglais sont rudimentaires- : « Qu’est-ce qui fait qu’une démonstration est digne de ce nom? », titre dont on remarque que les mathématiciens ont disparu, titre qui incite donc à retourner l’argument : la démonstration par PJ de la façon dont la vérité et la réalité furent inventées est-elle digne de ce nom?

    J’ai pas mal lu, annoté, relu et réannoté « Comment la vérité… » et j’arrive maintenant à la conclusion à laquelle est arrivé Thom à propos d’Aristote (« Aristote logicien, rhéteur (voire même sophiste quand il critique Platon et les Anciens) »), à savoir que PJ bien souvent un sophiste lorsqu’il critique les pythagoriciens (essentiellement -mais pas que- dans le chapitre IV).

    Une de ses techniques préférées est le sophisme par argument d’autorité (1) dont on a dès ici un aperçu :

    – dans ses brefs échanges avec Druuh qui se terminent par une fin de non recevoir : « Je vous ai dit poliment que je partageais votre sentiment que l’un d’entre nous n’a pas le niveau nécessaire pour poursuivre ce débat. Restons-en là. »;

    – dans son commentaire du 25/04 16h23 dont je ne vois pas d’autre interprétation subliminale que celle-ci : pourquoi continuez-vous à chercher alors que j’ai donné la réponse en 2009 ? (conseil que Yu Li et moi avons visiblement ignoré comme en témoignent les commentaires suivants);

    – dans son commentaire du 27/04 10h39 dont je ne vois pas d’autre interprétation subliminale que celle-ci : ma « lecture circonstanciée » (27/04 9h06) n’a aucun poids devant une édition allemande et une possible édition anglaise de « Comment la vérité… » (PJ m’a déjà fait le coup jadis -quand j’étais commentateur assidu- en terminant un « échange » par « J’ai écrit 19 bouquins ». Point final.)

    À partir du moment où on relit « Comment la vérité… » de ce point de vue, on ne peut s’empêcher de penser que l’impressionnante bibliographie (j’ai compté 272 références) est effectivement là pour impressionner…

    On trouve un exemple précis de « la méthode PJ » dans ma « lecture circonstanciée » (27/04 9h06) à propos de Roger Penrose où, compte tenu de ce que PJ dit de l’hamiltonien dans la page suivante, j’en ai déduit que PJ ne savait pas ce qu’était un hamiltonien. Mais maintenant, après relecture, peut-être PJ a-t-il vraiment pensé qu’il avait raison, faisant ainsi subir au mathématicien Penrose le même sort qu’il a fait subir à Gödel? : ces gens-là font des démonstrations indignes de ce nom, mais heureusement, moi PJ, je suis là pour rectifier le tir !

    Un autre exemple de sophisme, cette fois par généralisation abusive (2), se trouve pp.345 et 346 dans la section « Le calcul différentiel entre mathématiques et physique », où PJ généralise abusivement la notion de limite par Cauchy pour (dé)montrer l’ambiguïté de la définition de celui-ci.

    Mais pour moi le plus beau sophisme de « Comment la vérité… » est de très loin celui qui consiste à faire prendre par les lecteurs une métaphore pour argent comptant, c’est-à-dire pour une vérité, comme le fait PJ à propos de la preuve par Gödel de son théorème d’incomplétude: « Cette formule dit d’elle-même qu’elle n’est pas démontrable » (cf. ci-dessus 22/04 16h23, ou pp.312 à 317 pour la version complète).

    1: https://fr.wikipedia.org/wiki/Sophisme#R%C3%A9f%C3%A9rence_faisant_par_d%C3%A9finition_autorit%C3%A9

    2: https://fr.wikipedia.org/wiki/Sophisme#Les_sophismes_de_g%C3%A9n%C3%A9ralisation

    1. Avatar de Paul Jorion

      Merci d’avoir lu mon livre aussi attentivement. Je doute cependant que vous lui auriez consacré une si grande attention s’il était émaillé de « sophismes » aussi grossiers que ceux dont vous établissez maintenant la liste.

      Autre hypothèse : que ma remarque…

      « BasicRabbit, la différence entre nous, c’est que pour moi René Thom est un mathématicien dont les travaux m’ont toujours fort intéressé et inspiré, mais ce n’est pas un oracle dont la moindre des paroles doit être lue comme du marc de café. (…) Votre révérence à Thom n’est pas d’ordre scientifique mais mystique, c’est cela qui fait que nous ne serons jamais d’accord. »

      … vous soit resté à ce point en travers de la gorge que vous ayez consacré – ce qui doit avoir été des dizaines d’heures – à un ouvrage ne présentant en réalité aucun intérêt 😉 .

      Dernière hypothèse : que les questions que nous soulevons ici, vous, Yu Li et moi, soient à ce point cruciales pour les fondements des mathématiques qu’elles méritent – comme ce fut souvent le cas dans l’histoire – que de grands esprits se crêpent à leur propos abondamment le chignon 😉 .

      1. Avatar de BasicRabbit
        BasicRabbit

        1: Pour moi, je le redis ici, les questions que vous soulevez dans votre livre ne concernent pas les fondements des mathématiques, mais seulement une toute petite partie d’entre elles. Je me range à l’avis de mon gourou Thom, pour qui ce qui la fonde est l’opposition aporétique discret/continu (qui se décline en opposition arithmétique-algèbre/géométrie-topologie ou encore en l’opposition « philosophique » Pythagore (« Tout est nombre »)/Platon (« Tout est géométrie »).

        Je pense que, dans « Comment la vérité… », vous êtes tenu par la déontologie que vous avez fixée p.269 et que vous vous êtes donc astreint à suivre, et que cette contrainte nuit à la qualité de votre essai: pas de considérations analytiques « dont les prémisses doivent être reconnues comme indiscutablement vraies » car, sinon, il y aurait pétition de principe en regard du sujet du livre, pas de dialectique (il s’agit du point de vue d’un matérialiste-nominaliste/conventionnaliste) -mais, à mon avis, des dialogues « à la Platon » auraient été les bienvenus-, et donc seulement de la rhétorique, rhétorique dont vous écrivez : « qui ne connaît pas de contrainte quant à la qualité des prémisses (le discours de fiction, par exemple, en relève) ».

        Vous avez choisi un sujet difficile car d’emblée métaphysique, c’est pour moi incontestable. Il vous faut assumer ce choix: « What makes a demonstration worthy of the name?

  24. Avatar de Druuh
    Druuh

    Je vais rajouter mon grain de sel, en m’efforçant de rester courtois et en évitant soigneusement l’emploi de l’ironie grinçante, qui est sur-employée sur ce blog par beaucoup de commentateurs à mon gout (BasicRabbit et Yu Li je ne pense pas a vous).

    Première remarque : est il raisonnable d’émettre l’hypothèse que Godel aurait cherche a embrouiller ses lecteurs en sortant du chapeau une formule imaginaire, tout en sachant que cela ne constituait pas une preuve de son théorème, et qu’il est facile de démasquer la supercherie ?

    Ou qu’il n’ai même pas été conscient lui même que le coeur de sa preuve reposait sur une formule qui n’en est pas une ?..

    Ma réponse est : non. Pas raisonnable du tout. C’est même naif. Envisager cela, c’est très mal connaitre la nature de l’activité des mathématiciens. Cela ne signifie pas qu’ils soient infallibles, mais si une erreur apparait de temps en temps au cours d’une preuve, elle ne peut être aussi grossière que celle de confondre une vraie formule avec une formule imaginaire !

    On peut douter de la validité du théorème d’incomplétude la première fois qu’on le voit et qu’on se plonge dans sa preuve. C’est tout a fait naturel. On peut en douter quelques jours, quelques semaines peut être. Mais si on continue a en douter des décennies durant, c’est qu’on a tout simplement pas compris la preuve.

    J’ai un échange par mail avec Yu Li en ce moment, qui est de bonne volonté et cherche sincèrement a comprendre la nature de cette fameuse formule. Je ne doute pas que je vais finir par la convaincre que cette formule est une VRAIE formule, pas une chimère basée sur un paradoxe. Pour comprendre cela, il est préférable de se référer a des versions plus modernes de la preuve, car la preuve de 1930, bien que tout a fait correcte, emploie un vocabulaire de l’époque qui peut prêter a confusion.

    Enfin, je ne cesse de le répéter, « vrai sans pour autant être démontrable » signifie dans ce contexte mathématique « vrai dans N mais pas dans tous les modèles de Peano » . Y a t il quelque chose a redire a cela encore à ce stade ?….

    1. Avatar de Paul Jorion

      Cela ne signifie pas qu’ils soient infaillibles, mais si une erreur apparait de temps en temps au cours d’une preuve, elle ne peut être aussi grossière que celle de confondre une vraie formule avec une formule imaginaire !

      Ah oui ? Vous n’êtes apparemment pas familier du débat P vs. NP où certains confondent un dispositif imaginaire : une « machine de Turing à oracle » avec un vrai dispositif : une « machine de Turing ». Une erreur « aussi grossière » vicie le débat tout au long.

      1. Avatar de Druuh
        Druuh

        Je ne connais pas les details de P vs NP, je ne peut donc pas me prononcer la dessus. En revanche, je ne qualifierais pas une machine de Turing d’un vrai dispositif, car sa memoire est infinie. C’est plutot une idealisation du concept de « machine qui realise un algorithme ». Mais ceci est un autre debat…

        1. Avatar de Paul Jorion

          On voit des machines de Turing dans différents musées. Il y a de bonnes vidéos aussi de personnes qui en ont construit. Des rubans suffisamment longs donnent une approximation suffisante d’un ruban infini.

          1. Avatar de BasicRabbit
            BasicRabbit

            Belle définition de l’infini en puissance.

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

            Kronecker : « Dieu créa les nombre entiers et le reste est l’œuvre de l’homme. », citation sur laquelle Thom a ironisé :

            « Cette maxime de l’algébriste Kronecker témoigne plus de son passé de banquier enrichi que de clairvoyance philosophique ».

      2. Avatar de BasicRabbit
        BasicRabbit

        @ PJ. Je soumets à votre sagacité la proportion aristotélicienne suivante:

        Les oracles sont au problème P vs NP ce que les grands cardinaux sont à la théorie des ensembles.

        Votre 29/04 9h19 peut laisser penser que vous n’êtes pas intéressé. Je crois néanmoins que ça peut valoir la peine de voir l’application que Patrick Dehornoy a tirée de l’étude des grands cardinaux (1).

        1: http://www.numdam.org/item/SB_1999-2000__42__7_0.pdf (section 4: Rapport avec la théorie des ensembles)

        1. Avatar de Paul Jorion

          N’interprétez pas mon silence relatif dans les jours qui viennent pour du désintérêt : je dois me consacrer essentiellement à me remettre sur pied – littéralement.

          1. Avatar de Chabian
            Chabian

            Enfin, les béquilles et les épreuves… (je visite un ami dans le platre pour 8 semaines pour les mêmes motifs, il en reste trois). On croise les doigts pour votre rétablissement (au sens propre).

        2. Avatar de BasicRabbit
          BasicRabbit

          C’est le premier jet : analogie cardinaux-oracles, « Le Maître, dont l’oracle est à Delphes, ne dit ni ne cache, il signifie ». Une deuxième miction, si elle existe, serait plutôt selon moi à chercher du côté des rapports entre les démonstrations dans ZF sans ou avec grands cardinaux et les programmes exécutables par machines de Turing sans ou avec oracle. Il faudrait alors regarder du côté de la correspondance preuve-programme de Curry-Howard. Pour moi c’est vieux de 50 ans où j’avais écouté quelques exposés de Krivine et d’autres, sans rien y comprendre (et je n’ai fait aucun progrès depuis).

          Ce qui m’a attiré est dans (1) -je radote- c’est:

          « Le logicien français Jean-Louis Krivine a fait le rapport entre différents théorèmes mathématiques et les programmes informatiques qu’ils représentent :

          – l’absurde (appelé « bottom » : ⊥ correspond à une instruction d’échappement, d’exception, ou à un programme qui ne finit pas (un terme non typable dans le lambda-calcul simplement typé) ;
          – le théorème d’incomplétude de Gödel qui dit qu’il y a des propositions qui sont indécidables correspond à un programme de réparation de fichiers;
          – le théorème de complétude de Gödel correspond lui à un désassembleur interactif de programmes. ».

  25. Avatar de Druuh
    Druuh

    PS : Ce que j’ai dit sur le theoreme de Godel ne remet pas en cause une eventuelle discussion sur la nature de ce que les mathematiciens manipulent, et sur la validité ou non de certaines méhodes de preuve. Je dis juste que le théorème de Godel est un mauvais exemple pour parler de cela, car ce qu’on lui reproche ici (et ailleurs, car c’est une véritable bouteille a encre depuis 90 ans) n’est pas reprochable.

    1. Avatar de Paul Jorion

      Deux de mes maîtres, Chaïm Perelman (logique – ULB) et Georges-Théodule Guilbaud (mathématiques – EPHE) ont critiqué la démonstration de Gödel au moment de sa parution. Leurs critiques restent valides.

      L’idée que l’étrange démonstration de Gödel aurait été unanimement acceptée d’emblée ne s’est imposée que petit à petit. Il existe d’excellents livres (en français et en anglais en tout cas) faisant l’inventaire des faiblesses que présente la démonstration par Gödel de son théorème d’incomplétude de l’arithmétique. J’indique dès la préface de Comment la vérité et la réalité furent inventées (Gallimard 2009), que ma propre critique se situe dans le prolongement de celle (dévastatrice) que fit Wittgenstein à l’époque. En fait, la mienne ne fait que développer celle de Wittgenstein.

      L’argument « Circulez y a rien à voir », n’est pas un argument valide au plan scientifique.

      1. Avatar de Druuh
        Druuh

        Les critiques de Wittgenstein. et Perelman portaient elles sur le fait que la formule « qui dit d’elle meme qu’elle n’est pas demontrable » n’est pas une vraie formule ? et sur le fait que « vrai sans pour autant etre demontrable » est une supercherie intellectuelle ?

        1. Avatar de Paul Jorion

          Faites-nous le plaisir de vous renseigner un minimum sur un débat auquel vous participez maintenant depuis plusieurs semaines.

          1. Avatar de Druuh
            Druuh

            Il est très difficile d’avoir un débat serein avec vous car vous passez une bonne partie du temps à attaquer, comme s’il s’agissait d’un match de boxe. Mon but depuis le début (2014 tout de même) n;est absolument pas de vous mettre KO à tout prix comme vous le pensez peut être.

            Je ne dis pas qu’il n’y a rien a dire sur ce théorème d;un point de vue philosophique ou même méta-mathématique. Je suis prêt à discuter de bonne foi de certains aspects, et même plus généralement de la nature de l’activité mathématique. Cela pourrait être passionnant.

            Je dis simplement que les reproches qui concernent la « formule qui n’en serait pas une » et le « vrai qui n’est pas démontrable=imposture » sont nulles et non avenues car factuellement fausses. Je ne suis pas loin de penser que Yu Li sera convaincue dans peu de temps de cela.

            1. Avatar de Paul Jorion

              Je suis désolé : non seulement vous manifestez à chaque intervention votre méconnaissance totale du débat historique autour de la démonstration du théorème d’incomplétude, mais vos objections ne décollent pas du niveau le plus rudimentaire, comme le fait qu’une proposition qui n’est pas démontrable dans un système puisse être vraie … dans un autre (la belle affaire !).

              Vous dites être mathématicien, pourquoi pas, mais vous n’avez aucune familiarité, ni avec les questions relatives aux fondements des mathématiques, ni même avec l’histoire des mathématiques et surtout, vous ne manifestez aucune intention de jamais vous y intéresser. Comme l’a fait remarquer un commentateur, toutes vos interventions trahissent votre conviction profonde que vous ne voyez pas pourquoi le fait que la logique et les mathématiques soient des productions humaines et aient une histoire a la moindre pertinence puisqu’elles SONT : l’histoire et la philosophie des mathématiques dépassent votre horizon.

              Plutôt que d’admettre que vous êtes incompétent en matière d’histoire et de philosophie des mathématiques, vous persistez à marteler que ces questions ne se posent pas. Dans ce cas-là, cessez de vous en préoccuper : laissez cela à ceux que ces questions passionnent et qui ont pris la peine de les étudier.

              1. Avatar de Druuh
                Druuh

                Sans commentaires…. je laisse juge de vos propos les autres intervenants. Pour ma part je ne les commenterai pas, car votre mauvaise foi et votre jugement sur ce que je suis ou ne suis pas (qu’en savez vous ?) me laissent les bras ballants.

                1. Avatar de Paul Jorion

                  votre jugement sur ce que je suis ou ne suis pas (qu’en savez vous ?)

                  À qui la faute qu’on ne sache rien sur qui vous êtes ? N’est-ce pas vous qui le cachez soigneusement sous le choix courageux du pseudo, la forme ultime d’ailleurs de la mauvaise foi et de l’irresponsabilité … (sorry, c’est vous qui soulevez la question).

              2. Avatar de Druuh
                Druuh

                « vos objections ne décollent pas du niveau le plus rudimentaire, comme le fait qu’une proposition qui n’est pas démontrable dans un système puisse être vraie … dans un autre (la belle affaire !). « .

                Où avez vous vu que j’ai dit cela ? Je parle du même système d’axiomes !
                Je me rends compte a ce genre de commentaires que vous ne comprenez pas ce que je dis. Vous pensez que ce sont des interventions au raz des paquerettes car vous les comprenez de travers ! Oui le fait que « vrai dans un modèle d’une théorie n’implique pas forcement vrai dans tous les autres » est tout a fait élémentaire pour un mathématicien logicien, mais pas pour les raisons que vous croyez !

                1. Avatar de Paul Jorion

                  le fait que « vrai dans un modèle d’une théorie n’implique pas forcement vrai dans tous les autres »

                  Ok. Mais qu’est-ce qui vous autorise alors à invoquer dans un système le fait qu’une proposition soit vraie dans un autre ? Ça n’a aucune pertinence : la vérité n’est pas contagieuse d’un système à un autre ! À moins que vous ne soyez un mystique platonicien « à la Gödel » : « si une proposition est vraie quelque part, alors elle est vraie devant l’Éternel ». Non ! C’est ce que Wittgenstein a dénoncé : chaque jeu a ses règles propres, et c’est pourquoi je vous ai opposé l’autre jour l’exemple du joueur d’échecs qui invoque une règle du jeu de dames pour faire un mouvement interdit aux échecs : « Oui mais la règle est VRAIE (puisqu’elle est vraie aux dames) ». Et c’est ça que beaucoup de mathématiciens sont incapables de comprendre: « C’est vrai parce que c’est vrai … quelque part », sous-entendu du fait de la qualité « une et indivisible » des mathématiques. Non ! on n’est pas dans l’espace d’un catéchisme : on est au sein de l’espace d’un système formel ayant ses règles et doit s’y tenir – qui n’a pas le droit de demander du secours ailleurs (une vérité dans un autre système) ou de cacher un passager clandestin dans sa valise (importer en douce un fait empirique), comme le fait Gödel à tout bout de champ et sans aucune honte.

                  1. Avatar de Druuh
                    Druuh

                    Bon, là on entre en effet dans le coeur de la controverse, et je m’en réjouis. Je vais prendre le temps de comprendre ce que vous dites et de me placer de votre point de vue, et je reviens ce soir ou demain. Mais de grâce, cessez de penser que je veux vous discréditer a tout prix, et tentons de ne plus s’envoyer de scuds ! Je ne suis pas en position offensive contre vous ! Je ne suis pas un vulgaire troll qui ne cherche qu’a pourrir le débat, mes intentions sont sincères.

                  2. Avatar de Druuh
                    Druuh

                    En relisant votre dernier commentaire ce matin tout en essayant de me placer de votre point de vue, je me rends compte que je ne suis pas certain de tout comprendre.

                    Qu’entendez vous par « une proposition vraie dans un systeme? » ?

                    D’autre part, a quel moment de la demonstration Godel « change t il les regles du jeu » comme vous dites ?

                    1. Avatar de Paul Jorion

                      Merci pour votre bonne volonté. À ce stade-ci je crains que vous ne pourrez plus faire l’économie de lire ce que que j’ai écrit sur le sujet.

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

                      P. 6
                      Aristote avait décrit, avec l’analytique, les moyens – les classant du plus convaincant au moins convaincant – qui permettaient de conserver à un raisonnement sa validité, le guidant de prémisses vraies vers une conclusion vraie elle aussi par un nombre de pas potentiellement infini. La démonstration mathématique étant un raisonnement, devait jusqu’alors se plier elle aussi à ces règles. L’accession des mathématiques au statut de description du réel véritable levait ces contraintes de rigueur puisqu’il s’agissait désormais de rendre compte d’un objet auquel on reconnaissait une existence, voilée sans doute mais néanmoins réelle. Tous les modes de la preuve, du plus fiable au plus faible, furent désormais utilisés sans discrimination dans la démonstration mathématique.
                      J’offre de ceci une illustration détaillée : la mise en évidence des faiblesses inhérentes à la démonstration par Kurt Gödel de son théorème « d’incomplétude de l’arithmétique » (1931). Le mathématicien utilisa en effet dans sa fameuse démonstration un ensemble disparate de procédés présentant des degrés variables de valeur probante. Gödel recourut ainsi au mode le plus faible de la preuve analytique qu’est la preuve par l’absurde. Il fit aussi appel à divers types de preuve dialectiques, partant de prémisses seulement vraisemblables, telle que l’induction (dans la « récursion »), il fonda aussi des parties cruciales de son argumentation sur l’évocation de « contradictoires », qualifiés par Hegel de « trivialités », tel « tout n’est pas une preuve de p ». Enfin avec la « gödelisation », qui lui permit de coder des propositions méta-mathématiques en formules arithmétiques, Gödel confondit un artifice produit à l’intérieur d’un espace de modélisation avec un effet dans le réel.

                      P. 7
                      Les lecteurs noteront certainement que mon analyse de la démonstration du second théorème de Gödel prolonge celle esquissée par Ludwig Wittgenstein dans ses Remarks on the Foundations of Mathematics (1937-1944), ils établiront aussi un parallèle entre cette analyse et celle que Hegel fit de la physique newtonienne dans sa dissertation sur Les orbites des planètes (1801) et dans son Précis de l’Encyclopédie des Sciences Philosophiques (1817-1830).

                      P. 203
                      La troisième raison étant que si nous voulons tenir sur le singulier un discours qui ne soit pas contradictoire, il nous faut faire appel aux ressources de la logique et des mathématiques, dont la science nous affirme qu’elles sont indissociables de son propre espace de modélisation qu’est la Réalité-objective. J’ai affirmé précédemment que la Réalité-objective est le mythe que l’analytique engendre nécessairement. Mais, et comme on en verra un exemple dans la démonstration du théorème de Gödel relatif à l’incomplétude de l’arithmétique, la science s’est construite à partir d’une combinaison bien spécifique d’arguments analytiques d’une part et dialectiques d’autre part. Une autre combinaison de déductions fondées d’une part sur le vrai et d’autre part sur le vraisemblable aurait-elle conduit aux mêmes résultats ? Ou bien est-il concevable au contraire que logique et mathématiques puissent être mobilisées dans la construction de mythes différents (au sens où nous entendons ce mot, c’est-à-dire comme édifices discursifs relevant de l’imaginaire, et, partant, nécessairement fictifs) ?

                      P. 244
                      Nous verrons en particulier à propos du « second théorème » de Gödel, à l’aide duquel il prouve l’incomplétude de l’arithmétique, que la faible valeur probante de certaines parties de sa démonstration n’est pas pertinente à ses yeux puisque sa tâche consiste selon lui à décrire un objet existant en soi. Ne se concevant nullement comme l’inventeur de mathématiques nouvelles mais comme un explorateur de l’univers des nombres et de leurs proportions singulières, il n’a que faire d’une méthodologie dont la rigueur seule garantirait le résultat auquel il aboutit.

                      P. 259

                      Le « second théorème de Gödel »
                      Une manière de caractériser la naissance de la Réalité-objective est d’y lire le fruit d’une décadence de l’explication dans la période qui s’étend du Moyen Âge aux Temps Modernes. J’illustrerai un processus de dégradation parallèle dans la démonstration mathématique en analysant le « second théorème de Gödel » relatif à l’incomplétude de l’arithmétique, publié par Kurt Gödel en 1931.
                      Pour autant que je puisse en juger je ne pense pas que Gödel se soit trompé dans sa démonstration d’un point de vue technique, c’est-à-dire aux yeux des autres mathématiciens, ni lui, ni non plus tous ceux qui démontrèrent par la suite des formes plus générales du même argument. Mon propos n’étant donc pas de prouver que le théorème est vrai ou est faux, s’il est en effet indispensable que je démonte tous les rouages de sa démonstration, il n’est pas nécessaire qu’elle soit paraphrasée dans le détail. D’une certaine manière, la complication-même de cette démonstration apparaîtra significative dans mon exposé, cette particularité expliquant sans doute pourquoi une incongruité centrale à l’argumentation de Gödel est restée inaperçue des nombreux profanes non-mathématiciens qui ont fondé sur son théorème certaines des analogies dont ils ont émaillé leurs écrits au cours des dernières soixante-quinze années. Je procéderai donc de manière impressionniste, introduisant d’abord « naïvement » la question que pose Gödel, puis les principaux concepts et techniques qu’il fait intervenir dans son exposé. Arrivé là il me sera possible de concentrer mon attention sur le cœur de la démonstration, le lecteur ayant acquis en cours de route une compréhension adéquate des enjeux.
                      En 1930, Kurt Gödel démontra un premier théorème mettant en évidence que « la logique des prédicats de premier ordre est complète »  ; je n’en dirai pas davantage. Le second théorème de Gödel, publié une année plus tard, prouve lui que « l’arithmétique est incomplète ». Ce dont il est question, c’est de l’arithmétique « intuitive », en gros celle que l’on apprend à l’école, où l’on manipule des nombres à l’aide des opérations élémentaires de l’addition, de la soustraction, de la multiplication et de la division. Le titre officiel du second théorème est « À propos de propositions formellement indécidables de Principia Mathematica et de systèmes apparentés ». Comme j’y ai déjà fait allusion, au début du XXe siècle, Alfred North Whitehead et Bertrand Russell avaient, dans leurs Principia Mathematica exposé l’arithmétique de manière formelle (j’expliquerai plus loin ce que cela veut dire exactement), à partir de la prémisse « logiciste » selon laquelle les mathématiques peuvent être exprimées entièrement dans les termes de la logique.
                      La démonstration de Gödel est extrêmement complexe, si bien que de nombreux mathématiciens s’y sont perdus. Dans un article consacré à la réception du théorème, John W. Dawson rapporte que, non seulement les mathématiciens et logiciens qui soulevèrent des objections peu de temps après sa publication n’avaient pas parfaitement compris sa démonstration, mais qu’il en allait de même de certains qui vinrent au renfort de Gödel. Toute tentative de la présenter sous une forme simplifiée dénature du coup les questions épistémologiques importantes qu’elle soulève. Il existe une introduction fort populaire au théorème due à E. Nagel et J. R. Newman qui n’a pas su éviter cet écueil : dans leur souci de rendre la question « abordable » par les profanes, les auteurs de ce texte de vulgarisation ont « simplifié » leur exposé de la démonstration d’une manière qui rend méconnaissable ses enjeux épistémologiques réels (Nagel & Newman 1959).
                      Ceci dit il existe sur la question une littérature plus intéressante à laquelle je me suis référé. Je pense en particulier à l’Introduction par R. B. Braithwaite à la première publication du théorème en anglais en 1962. Je pense aussi à l’ouvrage magistral de Jean Ladrière : Les limitations internes des formalismes. Étude 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, publié en 1957.
                      Dans la perspective critique que j’adopte ici, deux auteurs surtout ont ouvert la voie. Le premier est sans conteste un géant : le philosophe Ludwig Wittgenstein. Le théorème de Gödel fut l’un de ses objets de réflexion favoris : on le retrouve comme un thème récurrent de ses études sur les fondements des mathématiques et il est évoqué dans plusieurs des ouvrages que ses élèves publièrent après la mort du philosophe à partir de ses notes. Bouveresse a commenté les travaux de Wittgenstein consacrés aux fondements des mathématiques, en particulier dans son Le pays des possibles. Wittgenstein, les mathématiques et le monde réel (1988). Dans le monde anglo-saxon, Stephen Shanker a lui aussi consacré un certain nombre d’articles à une analyse d’inspiration wittgensteinienne du théorème de Gödel, en particulier « Wittgenstein’s Remarks on the Significance of Gödel’s Theorem » (1988). Il a également consacré un livre entier à la philosophie des mathématiques de Wittgenstein (1987).

                      La culture mathématique
                      Ce qui frappe d’abord à la lecture du théorème de Gödel c’est à quel point le profane se retrouve sur des terres éloignées de ce que l’énoncé du théorème semblait annoncer initialement, à savoir apporter la preuve que l’arithmétique est incomplète. Aucun des mots « preuve », « arithmétique », « incomplet » n’est pris dans son sens usuel. Dans les premiers paragraphes de sa démonstration, Gödel écrit : « … il existe en fait des problèmes relativement simples de la théorie des nombres entiers ordinaires qui sont indécidables à partir des axiomes » (Gödel 1992 [1931] : 38). Une proposition est dite « indécidable » au sein d’un système formel où existe un opérateur de négation, si elle est vraie mais que l’on ne peut ni la prouver ni l’infirmer, ce qui veut dire que l’on ne peut ni la prouver elle, ni sa négation. Le second théorème de Gödel démontre qu’il existe en arithmétique des propositions indécidables. Ceci établit que l’arithmétique est « incomplète ». « Incomplet », ne doit donc pas s’entendre au sens où un puzzle peut être incomplet parce qu’on a égaré certaines de ses pièces. Il n’y a pas là de quoi s’étonner : chaque domaine un tant soit peu technique se constitue ses propres outils et son propre vocabulaire. Tout lecteur étranger au sous-domaine des mathématiques spécifique au théorème de Gödel qu’est la théorie de la démonstration (un hybride entre mathématiques et logique) et au climat intellectuel au sein duquel il est apparu (le Programme de Hilbert, sur lequel j’aurai l’occasion de revenir) aurait du mal à imaginer à la lecture du théorème et de sa démonstration que Gödel a « prouvé que l’arithmétique est incomplète ».
                      Autre chose qui frappe : le non-dit à propos des règles du jeu. Voici plusieurs années que j’essaie de comprendre la manière dont se déroule une partie de base-ball. Chaque fois qu’un nouvel aspect du jeu me devient compréhensible, il s’avère qu’il ne s’agissait pas d’une règle qui m’était jusque-là inconnue mais plutôt d’un principe implicite non-formulé, dont on m’affirme alors qu’il ne s’agit pas d’une règle à proprement parler mais de « quelque chose que tout le monde sait ». Bien entendu il s’agit alors de « tout le monde » sauf moi. Par exemple que le pitcher ne doit pas (je ne dis pas n’« a pas le droit ») recourir au moyen simpliste de gagner qui consisterait à systématiquement viser le batter entre les deux yeux. Un peu comme aux échecs, où l’on ne peut pas placer une pièce dans une case où une autre se trouve déjà, sans que ceci fasse partie des règles explicites du jeu. Dans ce postulat que l’on ne vise pas le batter à la tête, il s’agit de ce qu’on appelle le « fair-play ». Mais le fair-play n’est rien d’autre qu’un principe implicite à tout jeu ou tout sport, qui exige qu’en dépit du fait que chaque joueur doit à son équipe de s’efforcer de gagner, il lui faut aussi consacrer une partie non-négligeable de ses efforts et de son talent à assurer simplement la bonne marche du jeu, par-delà ce qu’énoncent les règles explicites. C’est-à-dire en réalité qu’il lui faut dans une certaine mesure collaborer avec son adversaire pour la cause supérieure de la bonne santé du sport (ce qu’Aristote appelait la « philia »). Ce « tout le monde le sait » est bien sûr lié au fait que mes interlocuteurs se sont familiarisés avec ce sport durant leur enfance, et l’ont appris dans leur corps, de la même manière que l’on apprend sa langue maternelle, avant même d’avoir conscience que l’on peut effectuer une tâche particulière en suivant plutôt un ensemble de règles. Il en va de même pour les mathématiciens : ils tiennent compte de règles implicites qu’ils n’ont jamais apprises en tant que telles mais qui font partie de ce savoir intériorisé qui se bâtit parce que l’on fait simplement « comme tout le monde », à savoir comme ses maîtres, puis comme ses collègues.
                      À l’inverse des règles implicites qui correspondent en gros au « fair-play », il y a la réalité du fait que les mathématiciens apparaissent quelquefois tricher délibérément par rapport aux principes qu’ils se sont imposés. Il s’agit alors toujours du même procédé à l’œuvre, celui qu’Émile Meyerson a appelé (dans une transposition audacieuse de Hegel), la rationalité ou ignorance de l’irrationnel : le fait de repérer un obstacle, de tenter de le vaincre, d’y échouer et – au lieu alors de s’y arrêter – de simplement nier au bout d’un moment qu’il ait jamais existé. Cantor, à la fin du XIXe siècle se révéla le champion d’une telle démarche : il nia l’irrationnel à de nombreuses reprises à propos des transfinis, entités d’ordre infini sur lesquelles certains types de calculs peuvent être opérés, et eut recours en particulier à la méthode dite de diagonalisation qui propose un moyen astucieux de le dépasser, méthode sur laquelle je reviendrai beaucoup plus longuement car elle offre une très intéressante illustration de la thèse que je développerai plus loin et qui voit dans les mathématiques, la mise au point d’une « physique virtuelle ». L’indécidabilité de Gödel dans laquelle certains de ses collègues ne virent rien de plus qu’une simple contradiction constitue un tel exemple d’obstacle redéfini de manière optimiste en une ouverture sur de nouveaux horizons.

                      P. 265

                      La démonstration mathématique
                      Comment prouve-t-on, ou démontre-t-on une proposition en mathématiques ? On dispose d’un certain nombre de propositions valides susceptibles de servir de point de départ, généralement appelées « axiomes ». On a également à sa disposition des « règles d’inférence » qui spécifient comment construire d’autres propositions valides à partir des axiomes ; ces nouvelles propositions peuvent alors servir à leur tour de point d’application des règles d’inférence. Wittgenstein dit qu’une « une proposition mathématique […] est le chaînon final d’un enchaînement visant à la preuve » (1975 : § 122). Une fois une proposition prouvée, on peut l’appeler « théorème » lorsqu’elle est particulièrement significative. Ladrière écrit : « Les énoncés vrais sont les axiomes et les théorèmes. Un théorème est un énoncé que l’on peut déduire des axiomes ou de théorèmes déjà démontrés au moyen d’un enchaînement d’énoncés intermédiaires qui constitue une démonstration » (Ladrière 1992 [1957] : 41).
                      On savait certainement démontrer un théorème avant qu’Euclide ne rédige ses Éléments, mais pour ce qui touche aux textes en notre possession, c’est bien lui qui introduisit en mathématiques le style « axiomatique » où de nouvelles propositions, les théorèmes, sont engendrées de manière systématique à partir d’un corpus d’« axiomes », c’est-à-dire à partir de « thèses » non-contradictoires (celles-ci étant soit des hypothèses, soit de simples définitions). L’ensemble de ces termes fonctionnent encore aujourd’hui dans les acceptions qu’en proposa Aristote : « J’utilise le terme thèse pour le premier principe immédiat et indémontrable d’un syllogisme, dont la compréhension n’est pas nécessaire dans l’acquisition de certains types de savoir. Mais celui qui doit être clairement conçu lorsqu’un certain autre type de savoir doit être acquis, celui-là, je l’appelle un axiome ; car il existe certains domaines de ce genre et nous avons coutume alors d’utiliser plus spécialement ce terme. Une thèse où une partie de la proposition est une supposition, c’est-à-dire ou l’on infère que quelque chose existe ou n’existe pas, est une hypothèse ; une thèse dont aucune partie n’implique une supposition est une définition » (Aristote, Analytiques Seconds : 72a 19-25).
                      Il y a dans la République de Platon un passage qui révèle la manière dont était conçu le rôle des axiomes à l’époque où l’on « axiomatisa » les mathématiques pour la première fois : « Supposons ex hypothesi que ce principe est vrai et procédons. Mettons-nous simplement d’accord qu’au cas où – ultérieurement – nous changerions d’avis quant à ce principe, toutes les conclusions auxquelles nous avions abouti grâce à lui seraient invalidées » (Platon 1966, iv 437a) .
                      Au début du XXe siècle, certains mathématiciens, au premier rang desquels David Hilbert, voulurent dépasser l’axiomatisation en s’assurant que les mathématiques soient complètement formalisées, c’est-à-dire fonctionnent entièrement sur la base de symboles non-intuitifs, qui pourraient alors, dans un deuxième temps et séparément, être « interprétés » en termes de réalités empiriques intuitives telles que le temps, les distances, la vitesse, l’accélération, etc. L’une des motivations essentielles d’un tel projet était de libérer les mathématiques de certains paradoxes contrariants tels qu’ils fleurissaient alors dans la théorie des ensembles due à Cantor. Hilbert écrivait : « … je voudrais rendre aux mathématiques leur ancienne prétention à une vérité inattaquable, que les paradoxes de la théorie des ensembles ont paru leur enlever… » (in Ladrière 1992 [1957] : 5). Hilbert lui-même proposa une formalisation de la géométrie euclidienne. En principe, les bases étaient ainsi assurées qui permettraient d’établir une séparation nette entre la syntaxe des mathématiques – les opérations dénuées de signification portant uniquement sur des symboles, et leur sémantique – l’utilisation d’objets mathématiques en tant que modèles permettant de représenter des phénomènes ou des mécanismes empiriques. En promouvant la « formalisation », Hilbert ouvrait la voie à l’utilisation algorithmique « automatique » des mathématiques qui serait au cœur du calcul opéré par des machines, autrement dit, au centre de l’informatique naissante. Alan Turing, Alonzo Church, Stephen Kleene seraient les pionniers de la mise au point de la théorie de la « calculabilité » car tel serait le nom de cette nouvelle spécialité.
                      Gottlob Frege le premier, à la fin du XIXe siècle, ensuite, comme je l’ai dit, Bertrand Russell et Alfred North Whitehead ensemble, au début du XXe, entreprirent de manière ambitieuse de procurer aux mathématiques un fondement purement logique. Si leur tentative ne fut pas entièrement couronnée de succès, elle joua cependant un rôle important dans la tâche de clarification qu’Hilbert avait inaugurée de son côté bien qu’avec une intention différente. Qu’est-ce qui aurait pu fournir en effet à une théorie de la démonstration sa cohérence sinon les principes généraux de la logique ?
                      Au sein d’un objet mathématique, les différents symboles qui le constituent se définissent les uns par rapport aux autres, chacun imposant certaines contraintes sur la manière dont les autres, présents au sein du même contexte, vont pouvoir opérer, jouant vis-à-vis d’eux un rôle de renforcement, d’inhibition, de catalyse, de délimitation de leur territoire, etc. Certains sont purement passifs, n’ayant pas d’autre pouvoir que de refléter les contraintes que les autres leur imposent. Un objet mathématique d’une certaine ampleur articule les éléments « atomiques » que sont des propositions mathématiques liées entre elles de manière cohérente (non-contradictoire).
                      Une proposition mathématique est bien formée ou non. C’est-à-dire que les symboles qui la composent sont utilisés à bon escient ou non, respectant les règles de position et de contexte qui président à l’expression de formules valides. Ainsi 23 + 13 = x est une formule valide. Telle quelle, elle est vraie dans la mesure où elle assigne la valeur 36 à « x ». « Interprétée », à savoir appliquée, c’est-à-dire lorsque des valeurs sont assignées aux symboles représentant des variables telles « x », sa vérité dépend de la valeur de x, du nombre que x représente : si x tient lieu de 36, en plus d’être valide, la formule est aussi vraie. Par contre, 23 + x – =, n’est pas une formule valide : les signes composent une suite « non-grammaticale ».
                      La manière de prouver qu’une formule est vraie consiste à la démontrer. Le fait qu’elle soit vraie dépend donc du fait qu’elle soit démontrable. Il existe cependant une différence évidente entre
                      4 + 5 = 9 (a)
                      et
                      « la proposition (a) est démontrable » (b)
                      La proposition (a) est vraie, la proposition qui lui est liée et qui serait fausse est
                      4 + 5 ≠ 9.
                      La proposition (b) est vraie, la proposition qui lui est liée qui serait fausse serait celle-ci : « la proposition (a) n’est pas démontrable ».
                      C’est donc une chose d’engendrer des propositions mathématiques vraies, c’en est une autre d’énoncer des propositions vraies relatives à la démontrabilité de propositions mathématiques (vraies).
                      [29/5/2021 : La vérité de (a) relève de la conclusion de syllogismes ;
                      La vérité de (b) relève de l’évidence des sens = méthode expérimentale]
                      On prit l’habitude au début du XXe siècle, d’appeler de telles considérations relatives à des propriétés d’objets mathématiques : « méta-mathématiques ».
                      Les mathématiciens considérèrent donc à partir de cette époque que l’on a affaire à deux domaines distincts de l’activité mathématique : celui des propositions mathématiques et celui des propositions méta-mathématiques. En réalité le simple fait d’appeler « 4 + 5 = 9 », « proposition (a) » est déjà en soi une démarche méta-mathématique, mais les mathématiciens établirent la démarcation au-delà. Il y a là comme on le verra, un danger.
                      Pour ce qui touche à leur vérité et leur fausseté, les mathématiques et les méta-mathématiques relèvent de principes différents : les premières disposent de leur propre système de validation, le système de validation des secondes est la logique commune.
                      En mathématiques, je peux faire la chose suivante, je peux dire (a – b) * (a + b) = a2 – b2. Où les variables « a » et « b » tiennent lieu de nombres réels quelconques. Pourquoi ? Parce que la multiplication des expressions entre parenthèses va produire, en sus des a et b qui vont se retrouver au carré (l’un, a2, en tant que nombre positif, l’autre, b2, en tant que nombre négatif, que l’on doit donc soustraire du premier pour obtenir le résultat final), deux expressions supplémentaires a*b, positive, affectée du signe « + » et b*a, négative, affectée du signe « – ». Or celles-ci vont s’annuler parce que la loi de multiplication des nombres réels est commutative : l’ordre dans lequel on multiplie les termes est indifférent : a*b = b*a. Du coup a*b – b*a = a*b – a*b et a*b – a*b = 0. Et on se retrouve avec les seuls carrés, a2 – b2.
                      Le principe, aisé à comprendre, de la formule (a – b) * (a + b) = a2 – b2 est que les variables a et b représentent, tiennent lieu, de nombres réels quelconques. Mais Gödel quand il parle d’arithmétique ne parle plus nécessairement seulement d’opérations sur des nombres : il aborde l’arithmétique par le biais « logiciste » que lui ont imprimé Russell et Whitehead dans leurs Principia Mathematica. Or la logique traite la représentation symbolique de manière très différente. En logique on a ceci : « (si) Certains a sont b » et « (si) Tous les b sont c », alors « (à coup sûr) Certains a sont c ». Par exemple, « (si) Certains Parisiens sont sans emploi » et « (si) Tous ceux qui sont sans emploi ont des soucis d’argent », alors « (à coup sûr) Certains Parisiens ont des soucis d’argent ».
                      J’ai pris la précaution de faire précéder les prémisses d’un « si » et la conclusion d’un « à coup sûr ». Ceux-ci sont toujours sous-entendus, « on sait » que la vérité de la conclusion dépend de celle des prémisses. Avec ma formule mathématique rien de semblable n’est supposé : je ne dois pas écrire “si « (a – b) »“ et “si « (a + b) »” alors “à coup sûr « a2 – b2 »”, non : aucune condition particulière ne doit être remplie, ni par le « a – b », ni par le « a + b » pour que le « a2 – b2 » se réalise, excepté bien entendu le fait que lorsque la formule est interprétée, appliquée, ce sont des nombres qui doivent intervenir aux endroits marqués par les variables « a » et « b ».
                      Autrement dit, il est impossible de traiter de la vérité de propositions du type (a – b) * (a + b) = a2 – b2 de la même manière qui vaut pour des propositions du type « Certains A sont B » et « Tous les B sont C », alors « Certains A sont C ». Et ceci parce que les premières sont vraies du moment que a et b sont des nombres et qu’aucune relation particulière n’est exigée a priori entre les valeurs choisies pour a et b, c’est-à-dire que la proposition (a – b) * (a + b) = a2 – b2 est vraie sous cette forme, alors que des propositions du type « Certains A sont B » et « Tous les B sont C », alors « Certains A sont C », ne sont vraies, comme on l’a vu précédemment, que s’il existe un certain type de rapport préalable entre A et B d’une part, et B et C, d’autre part. À savoir, il faut pour que « Certains A soient C », que les états-de-choses « Certains A sont B » et « Tous les B sont C » soient vrais l’un et l’autre. Ce qui signifie que les propositions logiques du type « Certains A sont B » ne sont vraies qu’une fois interprétées, c’est-à-dire qu’une fois que les A et B ont été remplacés par des données intuitives, des catégorèmes, dénotant des significats. Hartmann rappelait à ce propos « … nous n’oublions pas que la rigueur formelle, en tant que telle, est entièrement indépendante de la vérité comme de la fausseté des conclusions. Elle autorise seulement à dire que la conclusion doit être vraie si les prémisses le sont » (Hartmann 1931 : 24).
                      Ceci dit la logique a aujourd’hui des ambitions plus vastes : elle ne se contente plus comme au temps d’Aristote de définir les conditions à remplir pour produire des conclusions vraies à partir d’affirmations ou de négations contenant des quantificateurs comme « Tous les…» ou « Certains… », elle autorise aussi à prévoir le caractère vrai ou faux des conclusions à partir de la figure composée et de la simple connaissance du fait si les propositions intervenantes expriment un état-de-choses vrai ou faux. À ce point de vue la logique vise à un statut de « méta-connaissance », affirmant ce qui est vrai et faux par rapport à des ensembles de propositions dont la vérité individuelle a été établie préalablement et par ailleurs. La distinction entre des propositions arithmétiques qui n’avancent que des choses vraies dès qu’elles sont « bien formées » et démontrées et des propositions de logique qui énoncent des inférences valides à partir d’ensembles de propositions dont on sait seulement si elles sont vraies ou fausses (et que cette véracité a été établie par ailleurs), ces distinctions cessent d’être évidentes lorsqu’on se met à parler concurremment (comme c’est le cas, on le verra, dans la démonstration du second théorème de Gödel) d’arithmétique et de théorie de la démonstration, laquelle, dans l’approche de Russell et Whitehead n’est qu’une variété de la logique.

                      D’où viennent les propositions mathématiques vraies ?
                      On admet donc qu’une proposition mathématique est vraie si elle est démontrable. Or le théorème de Gödel avance qu’il existe des propositions arithmétiques vraies qui ne peuvent être démontrées. Il y a donc là au moins un paradoxe. Celui-ci se dissipera par la suite. Comme une préparation à la dissipation du mystère je vais cependant rappeler ce que j’ai dit précédemment de l’origine possible des propositions vraies.
                      J’ai déjà cité Ladrière quand il écrit « Les énoncés vrais sont les axiomes et les théorèmes ». Or le second théorème de Gödel établit qu’« il existe en arithmétique des propositions vraies que l’on ne peut ni prouver ni infirmer (prouver leur négation) ». D’où viennent alors ces propositions vraies ? Il ne peut s’agir des axiomes, puisqu’ils sont vrais sans devoir êtres prouvés, faisant partie du cadre de base de la théorie, il ne s’agit pas non plus des théorèmes, puisqu’un théorème est par définition une proposition qui a été démontrée.
                      Il y a là une difficulté d’emblée, difficulté dont Gödel était conscient. Dans l’article de John W. Dawson déjà cité, celui-ci note que « Dans le brouillon d’une réponse à une question posée par un étudiant thésard, Gödel indiquait que c’était précisément sa reconnaissance de la différence de circonstances entre la possibilité de définir formellement la démontrabilité et l’impossibilité de définir formellement la vérité qui le conduisit à la découverte de l’incomplétude. Le fait qu’il ne signala pas ceci [en1931] s’explique peut-être par son observation (dans un passage raturé du même brouillon) que “en raison des préjugés philosophiques de l’époque… le concept d’une vérité mathématique … était reçu avec la plus grande suspicion et le plus souvent rejeté comme sans signification” » (Dawson 1988b : 92).
                      Ceci est très étrange. Il y a là un flou qui – si l’on comprend bien Gödel dans ce brouillon de lettre – résulte de choses que l’on ne pouvait pas dire en 1931, en raison des « préjugés de l’époque ». Peut-être la question des propositions mathématiques vraies qui n’appartiennent cependant pas aux deux variétés de propositions reconnues comme vraies en mathématiques, les axiomes, et les théorèmes, pourra-t-elle s’éclairer en répondant de manière plus générale à une question à la consonance très maoïste : « D’où viennent les propositions mathématiques vraies ? ».
                      Comme on l’a vu, dans la perspective contemporaine, tout jugement (et idéalement toute proposition) est soit vrai soit faux, au sens de l’« adaequatio rei et intellectus » telle qu’on la trouve déjà exprimée chez Platon, de la correspondance adéquate de la chose dite à la chose dont il est dit, et dont il a été question dans la deuxième partie (cf. aussi Jorion 1990a, chapitre 19). Dans cette optique, la négation est perçue comme l’envers authentique de l’affirmation. La finalité de tout discours n’étant plus aujourd’hui essentiellement d’éviter de se contredire mais de dire le vrai, deux moyens sont disponibles, comme pour Platon, pour atteindre cet objectif : soit affirmer le vrai, soit nier le faux. Autrement dit, dire du vrai qu’il est ou dire du faux qu’il n’est pas. La proposition « Cette pomme est rouge » est vraie si la pomme que je vous montre est effectivement rouge. Elle est fausse si cette pomme est de toute autre couleur. Un moyen donc d’établir la vérité d’une proposition est l’évidence des sens : la proposition doit décrire un état-de-choses que l’évidence des sens confirme.
                      Il y a d’autres vérités qui sont de convention parce qu’elles sont des définitions, c’est-à-dire des raccourcis que se donne la langue en remplaçant plusieurs termes par un seul, ce qu’Ernest Mach appelait à la fin du XIXe siècle, une « économie mentale ». Ainsi, pour reprendre l’exemple déjà donné plus haut : « le faon est le petit du cerf ». On pourrait continuer de dire « le petit du cerf », mais on aura la liberté désormais de dire à la place « le faon ». Ou bien « On appelle anticonstitutionnel, un texte législatif dont le contenu est en contradiction avec l’esprit de la constitution ». À partir de là, la proposition « un texte législatif dont le contenu est en contradiction avec l’esprit de la constitution est anticonstitutionnel » est une tautologie, c’est-à-dire dans ce cas-ci, est vraie par définition.
                      On peut aussi parvenir à des propositions vraies de manière déductive. Soit, par exemple, une proposition dont on peut établir la vérité immédiatement par l’évidence des sens, « La pluie mouille », on peut également en établir la vérité de manière déductive, à l’aide d’un syllogisme : « La pluie est faite d’eau », « l’eau mouille » donc « la pluie mouille ». Ou, faisant appel à une définition, « la proposition 22 contredit l’esprit de la constitution, donc la proposition 22 est anticonstitutionnelle ».
                      On me demande s’il existe des chameaux blancs. Si j’ignore la réponse, je peux éventuellement procéder de manière déductive : « Toutes les espèces de mammifères ont une variété à pelage blanc », « le chameau est un mammifère », donc « il existe des chameaux blancs ». On ne parvient cependant pas à établir la vérité de toute proposition de cette manière : si l’on me demande cette fois s’il existe « en Amazonie une coccinelle ayant dix-sept points noirs sur fond jaune », je devrai soit découvrir la réponse dans une faune entomologique, soit entreprendre en Amazonie l’expédition qui apportera éventuellement la confirmation empirique irréfutable de la proposition.
                      A partir de là, il est permis de faire le catalogue des types de propositions vraies : il y a celles qui sont vraies parce que leur contenu tombe sous le sens, et que chacun les tenant pour vraies il est légitime de les faire intervenir comme prémisses dans des raisonnements, il y a celles qui sont vraies pour avoir été prouvées vraies en tant que conclusions de démonstrations syllogistiques – dont les démonstrations mathématiques ordinaires sont des exemples. Il y a aussi celles qui sont vraies par convention, parce qu’elles sont des définitions.
                      Et comme on l’a vu dans la troisième partie : « du fait que de deux prémisses vraies on ne peut tirer qu’une seule conclusion vraie, on sera obligé pour poursuivre ses raisonnements, soit d’introduire de nouvelles définitions – et les nouvelles vérités que l’on générera ainsi seront de simples conséquences de ces définitions, soit d’aller chercher dans le monde de nouveaux faits qui « tombent sous le sens », des observations venant corroborer soit des hypothèses, soit encore des faits d’induction » du genre de ceux évoqués plus haut : « Le fait de vivre longtemps caractérise les animaux sans fiel », « Être sans fiel caractérise l’homme, le cheval et le mulet », « Le fait de vivre longtemps caractérise l’homme, le cheval et le mulet » (Aristote, Analytiques Premiers : II xxiii, 68b 15-19).
                      On l’a vu, le second théorème de Gödel affirme qu’il existe en arithmétique des propositions « indécidables », autrement dit, des propositions vraies que l’on ne peut pas démontrer, c’est-à-dire, des propositions vraies que l’on ne peut pas prouver de manière déductive à l’intérieur de l’arithmétique. À la lumière de ce que je viens de dire ceci ne peut signifier qu’une seule chose : comme la vérité de ces propositions n’a pas été établie déductivement, elle doit résulter de l’une des deux autres sources des propositions vraies : soit, il s’agit de propositions qui sont vraies par définition, soit il s’agit de propositions qui sont vraies parce que leur vérité tombe sous le sens. Or il ne peut s’agir ici de propositions qui sont vraies par définition : une proposition qui ne serait pas déductible parce qu’elle est vraie par définition devrait faire partie des axiomes de la théorie, c’est-à-dire faire partie des propositions de base par rapport auxquelles d’autres propositions vraies (théorèmes) peuvent être déduites. Par conséquent les propositions vraies non-déductibles qu’évoque Gödel doivent être vraies parce que leur vérité tombe sous le sens. La question qu’un profane en matière de mathématiques se doit alors de poser à Gödel et à ceux qui soutiennent sa position est celle-ci : « Peut-on établir la vérité d’une proposition en arithmétique – indépendamment de sa démonstration – de la même manière que l’on fait la preuve qu’il existe en Amazonie une coccinelle à dix-sept points noirs sur fond jaune ? Autrement dit, quel est le type d’expédition à entreprendre qui permettra de confirmer la vérité de propositions dont la vérité ne peut être établie par déduction ? »

                      La « gödelisation »
                      Rien n’interdit de représenter des propositions méta-mathématiques à l’aide d’un système de symboles. C’est ce que fit Gödel qui utilisa le système de représentation mis au point en 1928 par Hilbert et Ackermann (Braithwaite 1992 [1962] : 10). Je peux écrire par exemple « (a) n’est pas démontrable » sous la forme « N(D a) ». Une fois les propositions méta-mathématiques traduites sous forme de formules, rien n’interdit non plus cette fois de coder ces dernières de manière à leur faire correspondre des nombres. Par exemple, pour « N(D a) », « N » ➔ 2, « ( » ➔ 3, « D » ➔ 5, « a » ➔ 7, « ) » ➔ 11. En additionnant ces nombres j’obtiens 28, et je peux désormais évoquer la formule « N(D a) » en disant « 28 ». C’est ce que fit Gödel. La manière dont il définit son codage est beaucoup plus subtile que celle que je viens d’utiliser, mais le principe en est le même : il prit simplement soin de définir les règles du codage de telle manière qu’à un nombre « encodeur » ne puisse correspondre qu’une seule formule « encodée ». Ceci s’obtient aisément en faisant appel aux nombres premiers (supérieurs à 1) et en tirant parti du fait que tout nombre naturel (1, 2, 3, …) constitue une combinaison unique de nombres premiers (théorème fondamental de l’arithmétique ; ibid. : 9). Dans l’exemple présenté plus haut, on peut attribuer à chacun des chiffres un exposant reflétant son rang dans la formule, puis multiplier la suite des nombres trouvés : on obtient ainsi un nombre qui peut être décodé ensuite en la formule unique qui lui correspond. Ainsi, on aurait pour la formule mentionnée plus haut : 21 * 32 * 53 * 74 * 115 = 163.588. Inversement (à condition de maintenir constant le système de correspondance entre nombres premiers et signes), il n’existe qu’une seule manière de décoder le nombre 163.588 et l’on retrouve nécessairement la formule « N(D a) ».
                      On appelle « gödelisation » d’une formule l’opération qui consiste à lui attribuer un « nombre de Gödel ». Il devient possible alors d’effectuer des opérations arithmétiques à partir de ces nombres et de déchiffrer ensuite le résultat (arithmétique) en la formule (méta-mathématique) qui lui correspond. Si je m’y prends habilement dans mon codage, des résultats intéressants pourront résulter de ma technique. Par exemple, et pour prendre un cas qui apparaît dans la démonstration du second théorème de Gödel : « … sa définition 8 définit l’opération arithmétique * sur deux nombres x et y de telle sorte que le nombre x * y qui résulte de cette opération est le nombre gödelien de la formule méta-mathématique que l’on obtient en prenant la formule méta-mathématique dont le nombre gödelien est x et en mettant immédiatement à sa suite la formule méta-mathématique dont le nombre gödelien est y » (ibid. : 10). Lassègue résume bien l’ambition de Gödel : « … une fois constituée l’axiomatique formelle, celle-ci peut, précisément parce qu’elle n’a plus de signification, être recodée de façon rigoureuse sous forme de nombres. L’arithmétique des entiers subit donc une double transformation : on en abstrait tout d’abord l’aspect formel au moyen d’une axiomatique sans contenu et on recode ces signes interprétés, simples signes sur le papier, sous forme de nombres » (Lassègue 1998 : 57). Cette volonté d’ « éliminer la signification » est centrale au Programme de Hilbert.
                      Grâce à un codage de ce type on parvient donc à engendrer non seulement des propositions arithmétiques vraies, mais simultanément des propositions méta-mathématiques vraies. On a réussi, au sein d’un discours unique, à énoncer d’une part des propositions relatives aux nombres et d’autre part des propositions relatives au fait que l’on puisse ou non démontrer ces propositions relatives aux nombres.

                      La force persuasive de la démonstration
                      L’exercice auquel Gödel se livre alors consiste en ceci : construire un système unique se composant à la fois de l’arithmétique et du discours méta-mathématique relatif à l’arithmétique. Le moyen de réussir cette opération consiste à coder les propositions méta-mathématiques sous forme de propositions mathématiques et à effectuer ensuite sur celles-ci des opérations arithmétiques.
                      On conçoit qu’à partir de là il devienne possible de produire en particulier une formule arithmétique telle qu’elle est à la fois, du côté pile, en tant que message codé dans une expression arithmétique, un énoncé méta-mathématique posant un jugement sur la démontrabilité d’une proposition, et du côté face, cette proposition elle-même en qui le commentaire méta-mathématique a été codé. On aura obtenu à l’aide de ce procédé, selon les termes qu’utilisera Gödel, une formule qui « dit quelque chose d’elle-même ». L’objectif est de lier indissolublement à l’intérieur d’une formule unique, une proposition arithmétique et un commentaire méta-mathématique qui s’applique à elle. Opérer un tel codage est bien entendu extrêmement difficile et la plus grande partie de la « démonstration » du théorème consiste pour son auteur à mettre en place les conditions qui autoriseront un encryptage aussi spécial.
                      Gödel sera obligé en particulier de faire intervenir la notion de « classe récursive » qu’il traitera comme une composante légitime de l’arithmétique. Ce faisant il opère un saut que tous les mathématiciens ne sont pas prêts à faire. Daval et Guilbaud en particulier considèrent au contraire que la récursion est elle-même une notion méta-mathématique et non arithmétique. « S’il y a une méta-mathématique elle est constamment menacée d’expropriation par la mathématique. L’induction (récurrence) est-elle autre chose qu’un constat méta-mathématique ? » (Daval & Guilbaud 1945 : 144), commentaient-ils.
                      Sans entrer dans les détails trop techniques, la nécessité pour Gödel de manipuler des classes récursives est due au fait que ceci lui permet de lier encore davantage les notions de démontrabilité et de vérité. On a vu qu’une proposition mathématique démontrable est vraie. La définition d’une « classe récursive » à partir d’une fonction récursive lui permet de faire un pas supplémentaire : lorsqu’une instance d’une telle classe n’est pas démontrable – lorsqu’on ne peut pas la prouver vraie – alors sa négation l’est automatiquement.
                      Une fonction récursive permet d’engendrer des nombres en les envisageant au sein de séries. De manière banale, les nombres naturels peuvent être générés à partir du principe de consécution suivant : « un nombre est égal au nombre précédent plus un ». On produit ainsi la suite 1, 2, 3, … Deux formules seulement suffisent pour engendrer la totalité des nombres naturels : celle que je viens de dire, que j’écrirai sous forme symbolique comme an = an-1 + 1, et une forme initiale qui vaut pour le premier terme, celui qui n’a pas de « précédent » : a0 = 0. Voici un ensemble de deux formules du même type qui permettent d’engendrer la suite des carrés : an = an-1 + n + (n – 1) ; a0 = 0. On peut vérifier pour an le carré de 1 : le carré du nombre précédent est 0, auquel on ajoute n qui est ici 1 et (n – 1) qui est zéro. On a « carré de 1 » égale 0 + 1 + 0. De même pour le carré de 4, par exemple : le carré du nombre précédent 3 est 9, auquel on ajoute 4 lui-même et (4 – 1) égale 3. Le résultat est 9 + 4 + 3 = 16.
                      Pourquoi certains, dont Daval et Guilbaud, considèrent-ils qu’une définition récursive (également appelée par « induction complète ») est d’ordre méta-mathématique, autrement dit qu’il s’agit d’un commentaire, plutôt que d’une propriété d’ordre mathématique, et qu’elle ne peut en conséquence être considérée comme un moyen de démonstration ? La réponse fut apportée au début du XXe siècle par Henri Poincaré qui n’était pas seulement un grand mathématicien et un grand logicien, mais aussi un philosophe des sciences de premier rang. Il écrivait dans La Science et l’Hypothèse : « Le jugement sur lequel repose le raisonnement par récurrence peut être mis sous d’autres formes ; on peut dire par exemple que dans une collection infinie de nombres entiers différents, il y en a toujours un qui est plus petit que tous les autres. On pourra passer facilement d’un énoncé à l’autre et se donner ainsi l’illusion qu’on a démontré la légitimité du raisonnement par récurrence. Mais on sera toujours arrêté, on arrivera toujours à un axiome indémontrable qui ne sera au fond que la proposition à démontrer traduite dans un autre langage. On ne peut donc se soustraire à cette conclusion que le raisonnement par récurrence est irréductible au principe de contradiction. Cette règle ne peut non plus nous venir de l’expérience ; ce que l’expérience pourrait nous apprendre, c’est que la règle est vraie pour les dix, pour les cent premiers nombres par exemple, elle ne peut atteindre la suite indéfinie des nombres, mais seulement une portion plus ou moins longue mais toujours limitée de cette suite » (Poincaré 1925 [1906] : 22-23).
                      Une autre manière de formuler la même observation consiste à constater que la récurrence n’est pas tant comme le disent Daval et Guilbaud, une opération méta-mathématique que, comme ils le disent aussi, une « induction ». Or, avec l’induction, on l’a vu, on sort du domaine de l’analytique au sens aristotélicien, c’est-à-dire du domaine où l’on engendre par la démonstration des conclusions vraies à partir de prémisses vraies, pour opérer au contraire sur le mode dialectique, où l’on « sauve » une prémisse vraisemblable à partir d’une prémisse et d’une conclusion, elles aussi vraisemblables, soit un mode de preuve faible, admissible pour ce qui touche à l’opinion (doxa) mais qui n’a pas sa place dans la démonstration scientifique.
                      Une fois mis au point le procédé effectuant le codage qui permet d’inscrire un commentaire méta-mathématique dans une formule arithmétique, rien n’interdit que celui-ci soit : « la proposition (a) est indémontrable ». Il ne reste plus alors qu’à encrypter ce message dans la proposition arithmétique (a) elle-même. Si l’on parvient dans un deuxième temps à démontrer (a), on aura démontré une proposition (a) qui contient le message « la proposition (a) est indémontrable ».
                      Gödel propose une telle formule dont il déclare qu’elle « dit d’elle-même qu’elle n’est pas démontrable » (Gödel 1992 [1962] : 40-41). Et il ajoute, « En dépit des apparences, il n’y a rien de circulaire dans une telle proposition, parce qu’on commence par affirmer l’impossibilité de prouver une formule parfaitement déterminée […] et c’est seulement ensuite (et en quelque sorte par hasard) qu’il s’avère que cette formule est précisément celle par laquelle la proposition était elle-même exprimée » (ibid. : 41).
                      En fait, Gödel ne démontre pas (a). Il effectue une « expérience mentale » : il recourt à une preuve par l’absurde. Celle qu’on appelle aujourd’hui, « preuve par l’absurde », les anciens l’appelaient eux, comme on l’a vu dans la deuxième partie, preuve « per impossibile » (adunaton). La dénomination originelle s’explique par le fait que, conséquence de l’une des deux prémisses, la conclusion énonce une impossibilité : qu’un état-de-choses et son contradictoire sont tous deux simultanément vrais. Afin d’éliminer l’impossibilité, la prémisse qui contrevient doit être inversée en sa contradictoire.
                      Il convient ici de faire un bref rappel : comme on l’a vu dans la deuxième partie, Aristote a été le premier à établir, dans l’Organon, le catalogue complet des moyens de preuve auxquels on peut recourir dans une démonstration, y compris mathématique. De plus, il évalua chacune de ces méthodes en fonction de son caractère probant, la classant comme forte ou faible et expliquant de manière précise le pourquoi de cette force ou de cette faiblesse.
                      Il en découle, selon un principe général, qu’une démonstration qui ferait intervenir plusieurs modes de preuve aurait automatiquement la valeur probante du plus faible de ses chaînons démonstratifs. Aristote observe par exemple qu’une forme dégénérée de l’induction est le recours au cas isolé. Comme je l’ai déjà signalé, un grand nombre de théorèmes des Éléments d’Euclide utilisent ce procédé dans leur démonstration. Or les mathématiciens n’évaluent pas les démonstrations de théorèmes en fonction de leur valeur probante.
                      Le second théorème de Gödel recourt à certains modes de preuve parmi les plus faibles : comme ici, la preuve « par l’absurde » et comme on l’a vu plus haut, la récursion ou « induction complète », sans que Gödel ni ses commentateurs ultérieurs ne fassent la moindre observation à ce sujet. Or, les adversaires « constructivistes » de Gödel avaient adopté quant à la preuve par l’absurde une position très claire : ils l’avaient exclue des modes de preuve valides. Barrow explique cela : « N’accepter comme arguments logiques que ceux acceptés par les constructivistes, signifie éliminer certains procédés familiers tel que l’argument par contradiction (la reductio ad absurdum) […] Si l’on adopte la philosophie constructiviste, le contenu des mathématiques s’en trouve considérablement réduit » (Barrow 1991 [1990] : 186). Or, et comme le souligne encore Barrow, l’exclusion de la preuve par l’absurde a d’autres conséquences sérieuses : en particulier en physique où elle interdit le recours au « Big Bang » comme principe explicatif : « Les conséquences d’un tel recalibrage sont également significatives pour le scientifique. Nous serions obligés en effet d’abandonner certaines déductions fameuses telles que les « théorèmes de singularité » de la relativité générale qui spécifient les conditions qui, lorsque la structure d’un Univers et de son contenu matériel les satisfont, suffisent à indiquer l’existence d’un moment passé où les lois de la physique ont dû être suspendues – la singularité que nous appelons « Big Bang ». Car ces théorèmes ne constituent pas ce moment explicitement, en fait, ils recourent au procédé de la reductio ad absurdum pour montrer que sa non-existence conduirait à une contradiction logique » (ibid. :187).
                      Le théorème fait également intervenir de manière très cavalière la notion de « contraire » ou plutôt de « contradictoire » d’une proposition. Je peux dire, « Le chat est un mammifère » et le contraire, « Le chat n’est pas un mammifère » ; le contradictoire serait : « Certains chats ne sont pas des mammifères ». D’une chose et son contraire, l’une des deux seule est vraie. Je peux dire aussi « Tous les chats sont des fromages » et « Aucun chat n’est un fromage », ici aussi, une seule des deux propositions est vraie. Dans mes exemples, les deux propositions vraies sont, « Le chat est un mammifère » et « Aucun chat n’est un fromage ». Maintenant imaginons qu’il existe deux livres sur les chats, le premier néglige de mentionner que « le chat est un mammifère », le second oublie de dire qu’« aucun chat n’est un fromage ». Lequel achetez-vous ? La bonne réponse est : le second. Pourquoi ? Parce que la première proposition signale un attribut essentiel du chat, la seconde, un attribut qui, s’il est vrai est néanmoins sans portée, du fait que la liste est quasi infinie des choses que les chats ne sont pas. Hegel écrit à ce propos, « L’op-posé signifie ici simplement le manque, ou plutôt, l’indéterminité ; et la proposition est si insignifiante que ce n’est pas la peine de la dire. Si l’on prend les déterminations doux, vert, carré – et l’on doit prendre tous les prédicats -, et si l’on dit maintenant de l’esprit qu’il est ou bien doux ou bien non doux, vert ou non vert, etc., c’est la une trivialité qui ne conduit à rien » (Hegel 1981 [1816] : 80). Guillaume d’Ockham s’était déjà intéressé à ces questions. Broadie écrit : « … Ockham nie qu’ « Une chimère est un non-homme » soit équivalant à « Une chimère n’est pas un homme ». À ses yeux, la première proposition est fausse alors que la seconde est vraie. En effet, comme Ockham le note, il faut conclure qu’une chimère n’est pas davantage un non-homme qu’un homme » (Broadie 1987 : 30). Or, la démonstration du second théorème de Gödel regorge de ce genre de trivialités. Au début de la Proposition VI on définit la proposition Q’(x, y(u)) comme étant Non [x B y (Gy)]…, « c’est-à-dire que x n’est pas une « preuve » de la formule obtenue en substituant pour la variable dans la classe-signe y(u) le nombre gödelien Gy pour la classe-signe elle-même » (Braithwaite 1992 [1962] : 18). Et un peu plus loin, il est montré que la formule v Gen r(v), n’ayant pas de variable libre, « on peut considérer qu’elle exprime la proposition que tout n’est pas une « preuve » de p(G)p, autrement dit que p(G)p est « improuvable » » (ibid. : 19).
                      La raison pour laquelle Aristote considérait la preuve « per impossibile » comme le plus faible des modes d’inculcation de la preuve auquel on puisse recourir dans la démonstration scientifique (épistémè) est, comme nous l’avons vu dans la deuxième partie, son caractère doublement indirect : elle implique tout d’abord de tester une prémisse ex hypothesi, à titre hypothétique, puis d’examiner ses conséquences ; ensuite, si celles-ci débouchent sur une conclusion « impossible », d’adopter la contradictoire de la prémisse initialement envisagée. Ce qui affaiblit encore davantage ce mode de preuve, c’est que le syllogisme sous-jacent ne s’obtient pas sous sa forme finale pour des raisons positives mais uniquement négatives. La pauvreté du lien résulte bien sûr de la prémisse « inversée », où le contraire est aisément produit en lieu et place du contradictoire, voire pire encore lorsque la prémisse en question n’exprime pas une condition binaire de type « oui ou non » et qu’il existera plusieurs alternatives lorsqu’il s’agira d’« inverser » le contenu.
                      Gödel envisage ex hypothesi deux possibilités. Imaginons que je parvienne à prouver la proposition qui contient, inscrite en elle-même de manière codée, le message « je ne suis pas démontrable », alors, par la démonstration, le contenu se révèle, et il existe une contradiction. Imaginons à l’inverse que cette proposition soit réfutable, autrement dit que je puisse démontrer sa négation, alors il devient possible de déchiffrer le message inscrit en elle sous sa forme négative, « Il est faux que “je ne suis pas démontrable” », autrement dit « je suis démontrable », or ce n’est pas la négation de la proposition originale qui affirme ceci mais la proposition originale sous sa forme positive, ce qui veut dire que sa négation – que l’on vient de démontrer – n’est elle pas démontrable, et l’on obtient également une contradiction. Donc on a bien affaire à une proposition vraie dont on ne peut ni la prouver ni la réfuter, à savoir prouver sa contradictoire, c’est-à-dire précisément ce qu’on est convenu d’appeler une proposition indécidable (Ladrière 1992 [1957] : 104).

                      Les formules qui « parlent d’elles-mêmes »
                      Ce à quoi on assiste, c’est donc ceci : je démontre une proposition et je découvre que – message codé à l’intérieur de cette formule – cette proposition dit d’elle-même « je ne suis pas démontrable ». Soit, à l’inverse, je démontre la négation d’une proposition et je découvre que cette proposition dit d’elle-même « en réalité, je suis démontrable – mais sous mon expression positive ». Qu’est-ce que cela signifie ?
                      Le profane en matière de mathématiques notera d’abord qu’une formule arithmétique n’ayant pas de langue, elle ne peut rien dire à propos de quoi que ce soit, et en particulier rien à son propre sujet. Or il n’y a pas eu que des anthropologues et autres philosophes pour faire cette remarque de bon sens, des mathématiciens les ont précédés et précisément à propos du second théorème de Gödel, qui ne fait donc pas nécessairement l’unanimité dans la profession à ce sujet. En effet, en 1945, R. Daval et G.-Th. Guilbaud que j’ai cités plus haut à propos de la récursion, dans leur remarquable ouvrage, Le raisonnement mathématique, font observer que : « Seul le mathématicien peut dire qu’une proposition est démontrable, une proposition ne peut pas dire cela d’elle-même » (Daval & Guilbaud 1945 : 45).
                      Quand je démontre une proposition mathématique, disons un théorème, et qu’à l’intérieur de ce théorème se trouve caché l’énoncé « Je ne suis pas démontrable », il s’agit en fin de compte de ma parole à moi, mathématicien, contre celle de cette proposition. En ce qui me concerne, je suis un sujet humain et j’ai la capacité d’expliquer par le raisonnement pourquoi j’affirme que cette proposition est démontrable : c’est parce que je disposais au départ d’un ensemble d’axiomes, de théorèmes et de règles d’inférence qui m’ont permis, une fois tracé le chemin qui mène des axiomes et des théorèmes à la proposition à démontrer, de dire que le balisage du parcours équivaut à affirmer qu’elle a effectivement été démontrée. Au contraire, cette proposition quant à elle ne peut rien produire à l’appui de sa déclaration qu’elle est indémontrable : tout énoncé suppose un sujet qui s’engage – par l’expression d’un degré d’adhésion – vis-à-vis de la vérité de ce qu’il énonce (cf. ce que j’en dis dans la deuxième partie ainsi que dans Jorion 1990a, chapitre 20). Une formule est à ce point de vue impuissante : n’étant pas un sujet humain, elle ne dispose d’aucun des outils de la panoplie discursive qui lui permettraient de prouver sa démontrabilité ou sa non-démontrabilité par les moyens habituels d’inculcation de la preuve. De plus, il m’est impossible de lui assigner aucune des motivations qui pourraient jouer un rôle positif ou négatif vis-à-vis de son engagement, je ne peux pas supposer sans doute qu’elle mente sciemment sur la question, mais à l’inverse je ne suis pas à même de lui assigner une expertise particulière quant à la possibilité ou non de sa démonstration : elle ne dispose ni de la capacité d’être bien ou mal informée sur ses propres caractéristiques, ni de celle de s’exprimer à ce sujet. Ce n’est donc pas parce qu’une formule dit au niveau méta-mathématique qu’elle est démontrable au niveau mathématique, qu’il y a là la moindre garantie de véracité.
                      L’origine du fait que cette proposition affirme sa non-démontrabilité nous la connaissons en fait parfaitement : c’est une conséquence, recherchée par son auteur, du système de codage mis en place. Je peux très bien imaginer – puisque cela dépend uniquement de la subtilité du système d’encryptage utilisé – qu’une proposition puisse « se tromper » quant à la démontrabilité de la proposition arithmétique qu’elle est à un autre titre. Je vais présenter plusieurs paradoxes, de complexité croissante qui permettront de cerner la démarche de Gödel.
                      Premier paradoxe. Arthur ouvre une boîte. Dans celle-ci il y a un billet sur lequel il est écrit « Il n’y a pas de billet dans la boîte ». Arthur se dit, « Tiens, c’est curieux, j’aurais juré qu’il y avait un billet ». Arthur est un niais. Pourquoi ? Parce qu’il a constaté de la seule manière dont on puisse le faire valablement qu’il y avait un message dans la boîte. Le fait qu’il soit écrit sur celui-ci « Il n’y a pas de billet dans la boîte » ne devrait pas influencer Arthur dont la conviction devrait rester inentamée. Le contenu du message inscrit sur le billet nie les faits, il est erroné et devrait être ignoré par Arthur.
                      Deuxième paradoxe. À force d’astuce, Isidore arrive à décoder un message. Sa déception est grande cependant quand il constate que le message décrypté dit : « Coucou ! Tu n’es pas arrivé à me déchiffrer ! » On pourrait imaginer bien sûr qu’il existe plusieurs niveaux possibles d’encryptage et que celui qu’Isidore vient de découvrir n’est que le plus simple. S’il n’existe qu’un seul niveau, Isidore a cependant tort d’être déçu. Pourquoi ? Parce qu’en réalité il est parvenu à décoder le message. Ce que celui-ci exprime n’est qu’une tentative dérisoire de la part du codeur de convaincre le déchiffreur qu’il a échoué dans sa tâche. Le message ne dispose d’aucune autorité pour nier l’évidence : qu’Isidore a au contraire réussi.
                      Troisième paradoxe. Eusèbe a inventé un chiffre ingénieux. Á partir d’un texte chinois, le code génère des phrases en français qui disent soit « Ce que dit cette phrase est vrai », soit « Ce que dit cette phrase est faux ». Eusèbe a pu constater que son système fait une analyse irréprochable de l’ensemble des textes chinois qu’il a pu lui soumettre. Un riche éditeur lui fait la proposition suivante : « À chaque phrase commentée avec exactitude je te donne cent euros, mais si ton système se trompe tu auras la tête tranchée ». Eusèbe doit-il accepter l’offre alléchante ? Il y a un rapport entre cette illustration et la question de la récursion dont on a vu qu’il ne s’agit pas à proprement parler d’un mode de preuve mais d’un procédé qui confirme à chaque coup sa réussite, mais sans apporter aucune garantie « quant au fond » qu’il en sera toujours ainsi. À moins qu’Eusèbe ne soit convaincu que son procédé dépasse par ses capacités celles d’un simple système de codage, autrement dit, à moins qu’Eusèbe ne soit certain que son système « comprend » en réalité le chinois, et pose des jugements infaillibles à partir de cette compréhension, nous lui déconseillerions d’accepter l

                  3. Avatar de BasicRabbit
                    BasicRabbit

                    Enfin des idées claires à partir desquelles PJ et Druuh peuvent entamer une disputatio dans les règles de l’art au lieu de passer leur temps à se rentrer dans le lard (là je pense essentiellement à PJ). Sur ce blog je la vois sous l’arbitrage impartial de Maître Cloclo (qui a déjà commencé à compter les points en décernant un strike à PJ).

                    Je suis entièrement d’accord avec ce que dit PJ en substance et je me demande si je n’ai pas déjà répondu jadis sur ce blog à sa question (ou si j’ai seulement rêvé que j’y avais répondu) en disant qu’il fallait se placer dans un modèle de ZF pour pouvoir parler d’un N en acte et non pas seulement en puissance (0, 1, 2, 3, etc.).

                    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).).

                    Si c’était effectivement le cas ça mettrait, je crois, les deux camps d’accord. (Tant pis pour Maître CloClo…).

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

                    1. Avatar de Paul Jorion

                      C’était en effet le sentiment que j’avais : qu’un progrès significatif aurait lieu dans la discussion dès qu’on passerait d’une critique de ce qu’on imaginait que j’aurais pu dire à une critique de ce que j’avais effectivement dit.

                    2. Avatar de BasicRabbit
                      BasicRabbit

                      @ PJ (30/04 12h55)

                      Il me semble avoir jadis parcouru « Le mathématicien et sa magie : Théorème de Gödel et anthropologie des savoirs », sur un site de PJ qui n’était pas son actuel blog (un truc comme un site orange, je crois) et avoir lu chez PJ ou ailleurs que cet article avait été présenté à une revue (« L’homme » ?) et refusé. Si cette info est exacte je ne sais évidemment pas quelle a été la motivation du (ou des) arbitres(s). ()Pour moi cet article se retrouve à peu près exactement dans la partie du chapitre IV de « Comment la vérité… » consacrée à Gödel). Et il est clair que si j’avais été arbitre j’aurais refusé l’article pour des considérations de forme (et j’ai du mal à comprendre pourquoi la prestigieuse maison d’édition Gallimard ne l’a pas fait). Pour dire ça crûment je trouve que la partie du chapitre IV consacrée à Gödel est illisible par quelqu’un -moi par exemple- de l’autre bord, c’est-à-dire de formation exclusivement scientifique. Aussi j’ai été très heureux de lire les éclairantes 8huit lignes de votre commentaire du 29/04 19h18.

                      Ceci dit j’attendais autre chose que votre 30/04 12h15 à mon 30/04/11h39. J’attendais une réponse immédiate à ma question « très facile à confirmer ou infirmer » puisqu’il suffit de lire (la traduction anglaise ou française de) l’énoncé du théorème tel qu’il a été formulé par Gödel lui-même. Mais Gödel a formulé son théorème pour des théories beaucoup plus générales que PA1, comme par exemple typique; la théorie des ensembles de ZF.

                      Ma question demeure. Peut-être Yu Li, très au fait du sujet, aura-t-elle l’amabilité de me répondre?

          2. Avatar de BasicRabbit
            BasicRabbit

            @ PJ. Je me permets de recopier -numéroté- ici le paragraphe intitulé « La force persuasive de la démonstration » pour en discuter avec Druuh.

            La force persuasive de la démonstration

            1. L’exercice auquel Gödel se livre alors consiste en ceci : construire un système unique se composant à la fois de l’arithmétique et du discours méta-mathématique relatif à l’arithmétique. Le moyen de réussir cette opération consiste à coder les propositions méta-mathématiques sous forme de propositions mathématiques et à effectuer ensuite sur celles-ci des opérations arithmétiques. On conçoit qu’à partir de là il devienne possible de produire en particulier une formule arithmétique telle qu’elle est à la fois, du côté pile, en tant que message codé dans une expression arithmétique, un énoncé méta-mathématique posant un jugement sur la démontrabilité d’une proposition, et du côté face, cette proposition elle-même en qui le commentaire méta-mathématique a été codé. On aura obtenu à l’aide de ce procédé, selon les termes qu’utilisera Gödel, une formule qui « dit quelque chose d’elle-même ». L’objectif est de lier indissolublement à l’intérieur d’une formule unique, une proposition arithmétique et un commentaire méta-mathématique qui s’applique à elle. Opérer un tel codage est bien entendu extrêmement difficile et la plus grande partie de la « démonstration » du théorème consiste pour son auteur à mettre en place les conditions qui autoriseront un encryptage aussi spécial.

            2. Gödel sera obligé en particulier de faire intervenir la notion de « classe récursive » qu’il traitera comme une composante légitime de l’arithmétique. Ce faisant il opère un saut que tous les mathématiciens ne sont pas prêts à faire. Daval et Guilbaud en particulier considèrent au contraire que la récursion est elle-même une notion méta-mathématique et non arithmétique. « S’il y a une méta-mathématique elle est constamment menacée d’expropriation par la mathématique. L’induction (récurrence) est-elle autre chose qu’un constat méta-mathématique ? » (Daval & Guilbaud 1945 : 144), commentaient-ils. Sans entrer dans les détails trop techniques, la nécessité pour Gödel de manipuler des classes récursives est due au fait que ceci lui permet de lier encore davantage les notions de démontrabilité et de vérité. On a vu qu’une proposition mathématique démontrable est vraie. La définition d’une « classe récursive » à partir d’une fonction récursive lui permet de faire un pas supplémentaire : lorsqu’une instance d’une telle classe n’est pas démontrable – lorsqu’on ne peut pas la prouver vraie – alors sa négation l’est automatiquement.

            3; Une fonction récursive permet d’engendrer des nombres en les envisageant au sein de séries. De manière banale, les nombres naturels peuvent être générés à partir du principe de consécution suivant : « un nombre est égal au nombre précédent plus un ». On produit ainsi la suite 1, 2, 3, … Deux formules seulement suffisent pour engendrer la totalité des nombres naturels : celle que je viens de dire, que j’écrirai sous forme symbolique comme an = an-1 + 1, et une forme initiale qui vaut pour le premier terme, celui qui n’a pas de « précédent » : a0 = 0. Voici un ensemble de deux formules du même type qui permettent d’engendrer la suite des carrés : an = an-1 + n + (n – 1) ; a0 = 0. On peut vérifier pour an le carré de 1 : le carré du nombre précédent est 0, auquel on ajoute n qui est ici 1 et (n – 1) qui est zéro. On a « carré de 1 » égale 0 + 1 + 0. De même pour le carré de 4, par exemple : le carré du nombre précédent 3 est 9, auquel on ajoute 4 lui-même et (4 – 1) égale 3. Le résultat est 9 + 4 + 3 = 16.

            4. Pourquoi certains, dont Daval et Guilbaud, considèrent-ils qu’une définition récursive (également appelée par « induction complète ») est d’ordre méta-mathématique, autrement dit qu’il s’agit d’un commentaire, plutôt que d’une propriété d’ordre mathématique, et qu’elle ne peut en conséquence être considérée comme un moyen de démonstration ? La réponse fut apportée au début du XXe siècle par Henri Poincaré qui n’était pas seulement un grand mathématicien et un grand logicien, mais aussi un philosophe des sciences de premier rang. Il écrivait dans La Science et l’Hypothèse : « Le jugement sur lequel repose le raisonnement par récurrence peut être mis sous d’autres formes ; on peut dire par exemple que dans une collection infinie de nombres entiers différents, il y en a toujours un qui est plus petit que tous les autres. On pourra passer facilement d’un énoncé à l’autre et se donner ainsi l’illusion qu’on a démontré la légitimité du raisonnement par récurrence. Mais on sera toujours arrêté, on arrivera toujours à un axiome indémontrable qui ne sera au fond que la proposition à démontrer traduite dans un autre langage. On ne peut donc se soustraire à cette conclusion que le raisonnement par récurrence est irréductible au principe de contradiction. Cette règle ne peut non plus nous venir de l’expérience ; ce que l’expérience pourrait nous apprendre, c’est que la règle est vraie pour les dix, pour les cent premiers nombres par exemple, elle ne peut atteindre la suite indéfinie des nombres, mais seulement une portion plus ou moins longue mais toujours limitée de cette suite » (Poincaré 1925 [1906] : 22-23).

            5. Une autre manière de formuler la même observation consiste à constater que la récurrence n’est pas tant comme le disent Daval et Guilbaud, une opération méta-mathématique que, comme ils le disent aussi, une « induction ». Or, avec l’induction, on l’a vu, on sort du domaine de l’analytique au sens aristotélicien, c’est-à-dire du domaine où l’on engendre par la démonstration des conclusions vraies à partir de prémisses vraies, pour opérer au contraire sur le mode dialectique, où l’on « sauve » une prémisse vraisemblable à partir d’une prémisse et d’une conclusion, elles aussi vraisemblables, soit un mode de preuve faible, admissible pour ce qui touche à l’opinion (doxa) mais qui n’a pas sa place dans la démonstration scientifique.

            6. Une fois mis au point le procédé effectuant le codage qui permet d’inscrire un commentaire méta-mathématique dans une formule arithmétique, rien n’interdit que celui-ci soit : « la proposition (a) est indémontrable ». Il ne reste plus alors qu’à encrypter ce message dans la proposition arithmétique (a) elle-même. Si l’on parvient dans un deuxième temps à démontrer (a), on aura démontré une proposition (a) qui contient le message « la proposition (a) est indémontrable ». Gödel propose une telle formule dont il déclare qu’elle « dit d’elle-même qu’elle n’est pas démontrable » (Gödel 1992 [1962] : 40-41). Et il ajoute, « En dépit des apparences, il n’y a rien de circulaire dans une telle proposition, parce qu’on commence par affirmer l’impossibilité de prouver une formule parfaitement déterminée […] et c’est seulement ensuite (et en quelque sorte par hasard) qu’il s’avère que cette formule est précisément celle par laquelle la proposition était elle-même exprimée » (ibid. : 41). En fait, Gödel ne démontre pas (a). Il effectue une « expérience mentale » : il recourt à une preuve par l’absurde. Celle qu’on appelle aujourd’hui, « preuve par l’absurde », les anciens l’appelaient eux, comme on l’a vu dans la deuxième partie, preuve « per impossibile » (adunaton). La dénomination originelle s’explique par le fait que, conséquence de l’une des deux prémisses, la conclusion énonce une impossibilité : qu’un état-de-choses et son contradictoire sont tous deux simultanément vrais. Afin d’éliminer l’impossibilité, la prémisse qui contrevient doit être inversée en sa contradictoire.

            7. Il convient ici de faire un bref rappel : comme on l’a vu dans la deuxième partie, Aristote a été le premier à établir, dans l’Organon, le catalogue complet des moyens de preuve auxquels on peut recourir dans une démonstration, y compris mathématique. De plus, il évalua chacune de ces méthodes en fonction de son caractère probant, la classant comme forte ou faible et expliquant de manière précise le pourquoi de cette force ou de cette faiblesse. Il en découle, selon un principe général, qu’une démonstration qui ferait intervenir plusieurs modes de preuve aurait automatiquement la valeur probante du plus faible de ses chaînons démonstratifs. Aristote observe par exemple qu’une forme dégénérée de l’induction est le recours au cas isolé. Comme je l’ai déjà signalé, un grand nombre de théorèmes des Éléments d’Euclide utilisent ce procédé dans leur démonstration. Or les mathématiciens n’évaluent pas les démonstrations de théorèmes en fonction de leur valeur probante.

            8. Le second théorème de Gödel recourt à certains modes de preuve parmi les plus faibles : comme ici, la preuve « par l’absurde » et comme on l’a vu plus haut, la récursion ou « induction complète », sans que Gödel ni ses commentateurs ultérieurs ne fassent la moindre observation à ce sujet. Or, les adversaires « constructivistes » de Gödel avaient adopté quant à la preuve par l’absurde une position très claire : ils l’avaient exclue des modes de preuve valides. Barrow explique cela : « N’accepter comme arguments logiques que ceux acceptés par les constructivistes, signifie éliminer certains procédés familiers tel que l’argument par contradiction (la reductio ad absurdum) […] Si l’on adopte la philosophie constructiviste, le contenu des mathématiques s’en trouve considérablement réduit » (Barrow 1991 [1990] : 186). Or, et comme le souligne encore Barrow, l’exclusion de la preuve par l’absurde a d’autres conséquences sérieuses : en particulier en physique où elle interdit le recours au « Big Bang » comme principe explicatif : « Les conséquences d’un tel recalibrage sont également significatives pour le scientifique. Nous serions obligés en effet d’abandonner certaines déductions fameuses telles que les « théorèmes de singularité » de la relativité générale qui spécifient les conditions qui, lorsque la structure d’un Univers et de son contenu matériel les satisfont, suffisent à indiquer l’existence d’un moment passé où les lois de la physique ont dû être suspendues – la singularité que nous appelons « Big Bang ». Car ces théorèmes ne constituent pas ce moment explicitement, en fait, ils recourent au procédé de la reductio ad absurdum pour montrer que sa non-existence conduirait à une contradiction logique » (ibid. :187).

            9. Le théorème fait également intervenir de manière très cavalière la notion de « contraire » ou plutôt de « contradictoire » d’une proposition. Je peux dire, « Le chat est un mammifère » et le contraire, « Le chat n’est pas un mammifère » ; le contradictoire serait : « Certains chats ne sont pas des mammifères ». D’une chose et son contraire, l’une des deux seule est vraie. Je peux dire aussi « Tous les chats sont des fromages » et « Aucun chat n’est un fromage », ici aussi, une seule des deux propositions est vraie. Dans mes exemples, les deux propositions vraies sont, « Le chat est un mammifère » et « Aucun chat n’est un fromage ». Maintenant imaginons qu’il existe deux livres sur les chats, le premier néglige de mentionner que « le chat est un mammifère », le second oublie de dire qu’« aucun chat n’est un fromage ». Lequel achetez-vous ? La bonne réponse est : le second. Pourquoi ? Parce que la première proposition signale un attribut essentiel du chat, la seconde, un attribut qui, s’il est vrai est néanmoins sans portée, du fait que la liste est quasi infinie des choses que les chats ne sont pas. Hegel écrit à ce propos, « L’op-posé signifie ici simplement le manque, ou plutôt, l’indéterminité ; et la proposition est si insignifiante que ce n’est pas la peine de la dire. Si l’on prend les déterminations doux, vert, carré – et l’on doit prendre tous les prédicats -, et si l’on dit maintenant de l’esprit qu’il est ou bien doux ou bien non doux, vert ou non vert, etc., c’est la une trivialité qui ne conduit à rien » (Hegel 1981 [1816] : 80). Guillaume d’Ockham s’était déjà intéressé à ces questions. Broadie écrit : « … Ockham nie qu’ « Une chimère est un non-homme » soit équivalant à « Une chimère n’est pas un homme ». À ses yeux, la première proposition est fausse alors que la seconde est vraie. En effet, comme Ockham le note, il faut conclure qu’une chimère n’est pas davantage un non-homme qu’un homme » (Broadie 1987 : 30). Or, la démonstration du second théorème de Gödel regorge de ce genre de trivialités. Au début de la Proposition VI on définit la proposition Q’(x, y(u)) comme étant Non [x B y (Gy)]…, « c’est-à-dire que x n’est pas une « preuve » de la formule obtenue en substituant pour la variable dans la classe-signe y(u) le nombre gödelien Gy pour la classe-signe elle-même » (Braithwaite 1992 [1962] : 18). Et un peu plus loin, il est montré que la formule v Gen r(v), n’ayant pas de variable libre, « on peut considérer qu’elle exprime la proposition que tout n’est pas une « preuve » de p(G)p, autrement dit que p(G)p est « improuvable » » (ibid. : 19).
            La raison pour laquelle Aristote considérait la preuve « per impossibile » comme le plus faible des modes d’inculcation de la preuve auquel on puisse recourir dans la démonstration scientifique (épistémè) est, comme nous l’avons vu dans la deuxième partie, son caractère doublement indirect : elle implique tout d’abord de tester une prémisse ex hypothesi, à titre hypothétique, puis d’examiner ses conséquences ; ensuite, si celles-ci débouchent sur une conclusion « impossible », d’adopter la contradictoire de la prémisse initialement envisagée. Ce qui affaiblit encore davantage ce mode de preuve, c’est que le syllogisme sous-jacent ne s’obtient pas sous sa forme finale pour des raisons positives mais uniquement négatives. La pauvreté du lien résulte bien sûr de la prémisse « inversée », où le contraire est aisément produit en lieu et place du contradictoire, voire pire encore lorsque la prémisse en question n’exprime pas une condition binaire de type « oui ou non » et qu’il existera plusieurs alternatives lorsqu’il s’agira d’« inverser » le contenu.

            10. Gödel envisage ex hypothesi deux possibilités. Imaginons que je parvienne à prouver la proposition qui contient, inscrite en elle-même de manière codée, le message « je ne suis pas démontrable », alors, par la démonstration, le contenu se révèle, et il existe une contradiction. Imaginons à l’inverse que cette proposition soit réfutable, autrement dit que je puisse démontrer sa négation, alors il devient possible de déchiffrer le message inscrit en elle sous sa forme négative, « Il est faux que “je ne suis pas démontrable” », autrement dit « je suis démontrable », or ce n’est pas la négation de la proposition originale qui affirme ceci mais la proposition originale sous sa forme positive, ce qui veut dire que sa négation – que l’on vient de démontrer – n’est elle pas démontrable, et l’on obtient également une contradiction. Donc on a bien affaire à une proposition vraie dont on ne peut ni la prouver ni la réfuter, à savoir prouver sa contradictoire, c’est-à-dire précisément ce qu’on est convenu d’appeler une proposition indécidable (Ladrière 1992 [1957] : 104).

            1. Avatar de Paul Jorion

              Très bien, merci d’avoir cité ce passage de « Vérité & réalité… ». Pour ceux qui ne liront pas la suite il faut ajouter que je démontre ensuite la non-validité de l’argument de Gödel dans le point 10. J’écris entre autre dans la suite :

              [..] Quand Gödel écrit à propos de sa proposition démontrable qui dit d’elle-même qu’elle n’est pas démontrable que « … c’est seulement ensuite (et en quelque sorte par hasard) qu’il s’avère que cette formule est précisément celle par laquelle la proposition était elle-même exprimée » (Gödel 1992 [1962] : 41), on est alors en droit de lui demander quelle est la nature exacte de ce « hasard » qui fait qu’un commentaire méta-mathématique sur la démontrabilité d’une proposition se retrouve codé dans son énoncé. Suggère-t-il sérieusement que cet encodage ne résulte pas de l’effort considérable qu’il a lui, mathématicien, consenti pour l’obtenir ? Suggère-t-il, s’il n’y a pas eu effort, qu’il y a eu simple révélation ? À cette dernière question – et comme nous pouvions déjà nous en douter quand nous nous étions demandé plus haut « D’où viennent les propositions vraies ? » – la réponse est en réalité, « Oui ».

              … et j’explique alors pourquoi : la prédisposition de Gödel à demander du secours ailleurs (une vérité dans un autre système) ou de cacher un passager clandestin dans sa valise (importer en douce un fait empirique).

        2. Avatar de BasicRabbit
          BasicRabbit

          @ Druuh, à propos de Daval et Guilbaud.

          Il y a pour moi deux sortes de lecteurs de « Comment la vérité… »: les curieux qui n’ont aucune idée préconçue sur les sujets traités et qui, attirés par le titre, l’auteur -médiatiquement connu- ou autre, cherchent à se cultiver; et il y a ceux qui arrivent avec des idées sur tout ou partie des sujets traités et, bien naturellement cherchent à les comparer -et éventuellement à les confronter- aux idées défendues dans le bouquin.

          En ce qui me concerne je suis un curieux pour le premier chapitre, dans le second j’ai une idée des idées de PJ parce que j’ai lu auparavant avec une certaine attention les premiers chapitres de Principes des systèmes intelligents et que, étant thomien, je ne suis pas d’accord avec le miracle grec des syllogismes. Pour le troisième il faudra que je le relise. Pour le quatrième j’ai toujours mes idées thomiennes, mais j’ai en plus quelques idées sur les fondements des mathématiques, en particulier sur la théorie des ensembles et la logique formelle « à la Gödel ».

          Je pense bien résumer ma pensée par la métaphore suivante : pour moi PJ est à l’idéologie -au sens étymologique de celui qui étude les idées des autres- ce que Zemmour est à la politique: en tant que curieux subjugué: Ah! qu’il est intelligent! Oh! qu’il est cultivé; dans les autres cas c’est tout autre chose.

          Ici ce qui m’intéresse est de critiquer la force persuasive de la démonstration, celle de Gödel ET celle de PJ lui-même, Je rappelle à ce propos que PJ vient de pondre un article intitulé « What makes a demonstration worthy of the name? », « Texte de l’article qui a été présenté aujourd’hui par ma collègue Yu Li de l’Université de Picardie, au congrès Unilog 2022 qui se tient à Chania en Crète »(1), texte que je traduis en français par « Qu’est-ce qui fait qu’une démonstration est digne de ce nom? ».

          (Les numéros qui suivent renvoie à la numérotation du paragraphe « La force persuasive de la démonstration », qu’on trouve un peu plus loin -et non ici- par suite d’une fausse manœuvre.)

          Je n’ai rien à dire de spécial à propos de 1. sinon que le « fil rouge » est contenu dans « L’objectif [de Gödel] est de lier indissolublement à l’intérieur d’une formule unique, une proposition arithmétique et un commentaire méta-mathématique qui s’applique à elle. Opérer un tel codage est bien entendu extrêmement difficile et la plus grande partie de la « démonstration » du théorème consiste pour son auteur à mettre en place les conditions qui autoriseront un encryptage aussi spécial. », sachant que la position que défend PJ -et bien d’autres philosophes des sciences- est que c’est impossible.

          Je passe au 3. Là je sursaute dès la première phrase: « Une fonction récursive permet d’engendrer des nombres en les envisageant au sein de séries. », et je me dis que c’est du charabia, les fonctions récursives ayant en logique mathématique une définition bien précise (2). Et il faut que je me force à lire la suite pour m’apercevoir que PJ voulait en fait parler de fonctions définies par récurrence, ce qui n’est pas la même chose (quoiqu’il y ait quand même un rapport).

          4. Nous voilà dès la première phrase -interrogative- dans le cœur du sujet. Et j’ai hâte d’avoir une réponse car je ne vois pas en quoi une définition -et une démonstration (3)- par récurrence serait d’ordre méta-mathématique. Or que nous apprennent les lignes suivantes? Elle nous apprennent de Henri Poincaré, « pas seulement un grand mathématicien et un grand logicien, mais aussi un philosophe des sciences de premier rang », que, quoiqu’on fasse, le raisonnement par récurrence n’est pas conséquence des autres axiomes de l’arithmétique de Peano, et ne nous dit absolument rien sur la question de savoir si le problème est d’ordre mathématique ou méta-mathématique. Pour moi le problème est mathématique lorsqu’on contrôle les propriétés auxquelles il est possible d’appliquer le raisonnement par récurrence (PA1, PA2, etc), et est typiquement méta-mathématique lorsque l’on accepte toutes les propriétés quelles qu’elles soient, vaguement exprimables dans le langage naturel, propriétés auxquelles on peut appliquer ce raisonnement. (Pour moi l’appel à « pas seulement un grand mathématicien et un grand logicien, mais aussi un philosophe des sciences de premier rang » (Henri Poincaré) est typiquement un sophisme par argument d’autorité, d’ailleurs doublé d’un sophisme par généralisation abusive car le propos principal est étendu, dans une substantielle note de bas de page, de Gödel à Hilbert dans une substantielle note de bas de page.) Personnellement, pour éclairer le lecteur, j’aurais opposé la notion méta-mathématique de calculabilité effective et la notion mathématique de récursivité, puis, éventuellement, lancé les violons sur l’historique de la chose, tout ça, bien entendu, sans quitter de vue le théorème d’incomplétude de Gödel.

          4&5. Récurrence et induction. Pourquoi un raisonnement par récurrence est-il qualifié de raisonnement par induction, sachant que le raisonnement inductif est un mode de raisonnement, une opération mentale, qui consiste à remonter du singulier au général, à l’universel? La raison est, mon avis, simple mais subtile: c’est parce qu’elle permet de passer du « chaque » au « tout » (un lecteur non averti dira sans doute que c’est de la sodomisation de mouche). En effet par récurrence on montre pas à pas que si P(0) est vraie alors P(n) est vraie pour chaque entier n considéré comme un être singulier, alors la propriété P est globalement (universellement) vraie pour tout entier n (passage du vrai « en puissance » au vrai « en acte »). C’est, à mon avis, pour cela que dans les hypothèses du théorème d’incomplétude, la cohérence de PA1 doit être sémantique (la cohérence syntaxique ne suffisant pas). Pour moi, contrairement à la position de PJ exprimée en 5, on ne sort pas de l’analytique: on y reste; mais alors que dans l’analytique déductive la conclusion est une forme affaiblie de l’hypothèse (c’est une perte d’information, Socrate est mortel » renseignant moins que « Socrate est un homme » (thermodynamiquement c’est un affaiblissement entropique), au contraire dans l’analytique inductive la conclusion est un renforcement de l’hypothèse (thermodynamiquement c’est un renforcement néguentropique). Si l’argumentation qui précède a un sens alors, contrairement à PJ, dans la hiérarchie des forces probantes je placerais volontiers le raisonnement par récurrence au-dessus du syllogisme classique. Au fond l’axiome de récurrence n’est-il pas vrai tout bêtement parce qu’il tombe sous le sens (peut-être un lecteur non averti répondrait-il : oui, évidemment oui.)?

          6. à 10 ; éventuellement à suivre.

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

          2: Une fonction récursive permet d’engendrer des nombres en les envisageant au sein de séries.

          3: Tout apprenti mathématicien a été invité à « sécher » sur des propriétés à démontrer par récurrence des fonctions définies par récurrence.

          1. Avatar de BasicRabbit
            BasicRabbit

            Point 8.

            Dans le jargon logicien de mon temps, on parlait d’intuitionnisme plutôt que de constructivisme -je n’ai jamais su ce que l’intuition venait faire là-dedans-. J’ai lu dans ma source de base (1) que le théorème d’incomplétude valait aussi en logique intuitionniste, la note 1 ne revoyant pas à un article mais à une explication directe qui me paraît sujette à caution car, comme PJ, je pense que la démonstration du théorème de Gödel par Gödel (et par quiconque?) est une preuve par contradiction. Ceci appelle deux remarques:

            1: Il faut se méfier de Wikipédia car on n’a aucune indication sur le niveau de compétence de l’auteur (et je l’ai dit à Yu Li à propos de (1) en lui suggérant une autre référence).

            2: Je pense qu’il faut spécifier dans tout énoncé de logique mathématique de quelque importance, de quelle logique il s’agit (classique, intuitionniste, paracohérente, etc.), en précisant soit la syntaxe (règles de déduction), soit la sémantique (algèbre de Boole, de Heiting, de Brouwer, etc.). Je suis curieux de savoir si c’est précisé dans l’énoncé original du théorème d’incomplétude et, dans l’affirmative, comment. Yu Li connaît très certainement la réponse.

            Point 9.

            Le raisonnement par contraposition apparaît au logicien basique comme allant de soi. Mais il implique (?) que P->Q est équivalent à Q ou non P et donc le paradoxe de Hempel (2) qui permet de faire de l’ornithologie en chambre, c’est-dire qui transforme de tels ornithologues en sophistes.

            PJ s’est-il jamais posé la question de savoir si, parfois, il ne faisait pas lui aussi de l’épistémologie en chambre? (Je n’ai pas la réponse.) Plus sérieusement je me demande si en couplant algèbre de Boole et théorème de Bayes on n’aboutit pas à de la pédagogie en chambre, ce que pourrait bien faire, il me semble, Stéphane Dehaene, du Collège de France et conseiller pédagogique de Blanquer.

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

            2: https://fr.wikipedia.org/wiki/Paradoxe_de_Hempel

            1. Avatar de BasicRabbit
              BasicRabbit

              Point 10.

              PJ (30/04 16h52) : « Très bien, merci d’avoir cité ce passage de « Vérité & réalité… ». Pour ceux qui ne liront pas la suite il faut ajouter que je démontre ensuite la non-validité de l’argument de Gödel dans le point 10; »;

              Pour moi la preuve du théorème est correcte à condition de considérer que c’est un théorème de ZF (et surtout pas un théorème d’arithmétique…). Tout simplement parce que ce qui est méta-mathématique en arithmétique devient mathématique dans ZF, théorie plus puissante que l’arithmétique (1).

              Mais ne comptez pas sur moi pour en débattre avec vous: je suis thomien maintenant, et très éloigné de l’étude des modèles formels auxquels j’ai substitué celle les modèles continus. Ne prenez pas non plus pour argent comptant tout ce que je dis depuis que j’ai fait un petit retour sur votre blog. Mais tant mieux si quelques uns de mes commentaires alimentent votre propre réflexion.

              1: Patrick Dehornoy a écrit « La théorie des ensembles. Introduction à une théorie de l’infini et des grands cardinaux ». Je ne l’ai pas lu mais je suis certain que ça pourrait vous intéresser. Du temps, maintenant lointain, où j’étais à peu près dans le coup, je crois maintenant me souvenir que c’est ça qui circulait entre nous: le théorème d’incomplétude de Gödel est un théorème de ZF.

              1. Avatar de BasicRabbit
                BasicRabbit

                Thom : « Avant Frege il y a eu Boole, et c’est le début de la catastrophe » (extrait du chapeau de « structures cycliques en sémiotique » (Apologie du logos, Hachette, 1990).

  26. Avatar de Yu LI
    Yu LI

    Pour moi, la communication n’est pas seulement une question de mots ou de messages, mais l’interaction profonde des énergies de la vie, c’est pourquoi j’apprécie nos discussions actuelles !

    Comme je l’ai suggéré au début de la discussion, le plus important pour le moment est d’écouter ce que Gödel a dit, afin que notre discussion soit constructive et ne gaspille pas notre précieuse énergie.

    Donc, je continue à questionner.

    Il y a deux points principaux dans la preuve de Gödel :
    1. Il existe un « problème indécidable » en PA.
    2. Ce « problème indécidable » peut être exprimé, par exemple, par une proposition qui parle de sa propre provabilité (démontrabilité ).

    Si nous acceptons la preuve de Gödel, pouvons-nous donner un exemple concrète d’un tel « problème indécidable » en PA, c’est-à-dire, une proposition qui parle de sa provabilité ?

    1. Avatar de Druuh
      Druuh

      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.

      1. Avatar de Paul Jorion
  27. Avatar de Druuh
    Druuh

    « pouvons-nous donner un exemple concrète d’un tel « problème indécidable » en PA, c’est-à-dire, une proposition qui parle de sa provabilité ? » : oui tout à fait, il s’agit de la proposition epsilon(a) dans le texte que je vous ai envoyé par mail !

    1. Avatar de CloClo
      CloClo

      Ah bah si vous communiquez aussi par mail ça va pas le faire !

      Merci de mettre tout en lecture dans ce topic. Je suis entrain de chercher dans mes archives Carambar si je n’ai pas déjà lu la solution au problème qui vous occupe. Il me semble que si…

      1. Avatar de juannessy
        juannessy

        Ça me rappelle que j’avais trouvé dans une papillote Révillon cette sentence attribuée à Confucius , qui aurait pu servir d’énoncé pour examiner P vs NP:

         » On a 2 vies . La deuxième commence quand on s’aperçoit qu’on qu’on n’en a qu’une . »

        Mais  » s’apercevoir  » doit d’abord passer à la moulinette de la démontrabilité .

        1. Avatar de Yu LI
          Yu LI

          @juannessy
           “On a 2 vies . La deuxième commence quand on s’aperçoit qu’on qu’on n’en a qu’une . ”
          – Cela me fait penser à la relation entre le méta-langage et le langage objet.

          Mais  “ s’apercevoir ” doit d’abord passer à la moulinette de la démontrabilité
          – Cela signifie que le sens de « démonstration (preuve) » devrait être élargi.

      2. Avatar de Yu LI
        Yu LI

        @CloClo Druuh m’a communiqué par mail, c’est parce qu’une fois il n’arrivait pas à poster ses commentaires.

      3. Avatar de CloClo
        CloClo

        Ah y est trouvé bien rangé à mon rayon blague pour Mathoto, cadeau :
        —————————
        C’est un logicien (L) et un arithméticien (A) :

        L : – Gödel a prouvé que AP est incomplète.
        A éclate de rire et dit : -oui, on peut appeler cela comme cela.
        L : – Pourquoi toi tu appelles cela comment ?
        A : – Gödel a prouvé que l’arithmétique ne peut-être logiquement théorisé.
        C : – Ce n’est pas parce que la logique a échoué, qu’il n’existe pas un raisonnement pour en rendre compte.
        —————————–
        Celle là elle me casse à chaque fois rien que de la relire je me bidonne comme un fou.

        1. Avatar de 2Casa
          2Casa

          C’est qui « C » ? Le tiers exclu ?

          1. Avatar de juannessy
            juannessy

            La conclusion , j’imagine .

            1. Avatar de 2Casa
              2Casa

              On peut mettre « -1 » à un commentaire quelque part ?

              1. Avatar de CloClo
                CloClo

                Oui dans les commentaires imaginaires mais il ne faut pas être très rationnel pour le faire.

                En tout cas excellente blague, j’en ris encore.

                1. Avatar de BasicRabbit
                  BasicRabbit

                  Pour noter les commentaires imaginaires, il faudrait des boutons +i et -i.

                  1. Avatar de Ruiz

                    @BasicRabbit et seul le commentaire hideux vaudrait -1

                    1. Avatar de BasicRabbit
                      BasicRabbit

                      1 est à réserver pour les commentaires très marrants (hihihihi) .

        2. Avatar de Yu LI
          Yu LI

          Votre blague me dit quelques choses, mais j’ai du mal à l’exprimer.

          Je cite donc un passage du livre de Mélika Ouelbani, La philosophie de Wittgenstein – Repère (p. 155), où je suppose que Wittgenstein joue le rôle du tiers exclu (C).

          – La question du fondement logique des mathématiques revient souvent car pour lui, la logique comme les mathématiques sont deux langages différents régis de manière autonome par leurs propres règles. C’est ainsi que pour Wittgenstein, dans les Principia, Russell ne fait que traduire un langage dans un autre : «  Que Russell ait relié les procédures mathématiques à la logique pourrait vouloir dire qu’il les a tout simplement traduits dans un nouveau langage. Mais c’est une source de confusion de croire que c’est une explication, comme si, en venant aux prédicats et aux fonctions prédicatives, nus voyions ce sur quoi les mathématiques portent vraiment » ( (Cours sur les fondements des mathématiques de Wittgenstein, trad. fr. E. Rigal, XXVII, 286)

    2. Avatar de Yu LI
      Yu LI

      Le cœur de notre discussion est de savoir quelle est exactement cette proposition « vraie mais indémontrable » (« problème indécidable » en PA)construite par Gödel?

      @Druuh Pouvez-vous expliquer cette proposition epsilon(a) en des termes que tout le monde peut comprendre, lorsque vous êtes disposable ? Je pense que cette explication serait une grande aide pour avancer notre discussion !

  28. Avatar de Yu LI
    Yu LI

    Nous avons beaucoup discuté des propositions indécidables (vraie mais undémontrable). Je présente ici la fameuse conjecture de Collatz qui pourrait inspirer notre discussion.

    1. La conjecture de Collatz

    La conjecture de Collatz en mathématiques demande si la répétition de deux opérations arithmétiques simples transformera finalement tous les entiers positifs en un seul.

    Elle concerne les suites d’entiers dans lesquelles chaque terme est obtenu à partir du terme précédent de la manière suivante : si le terme précédent est pair, le terme suivant est la moitié du terme précédent. Si le terme précédent est impair, le terme suivant est égal à 3 fois le terme précédent plus 1. La conjecture est que ces séquences atteignent toujours 1, quel que soit le nombre entier positif choisi pour commencer la séquence.

    Définir une fonction récursive fCollatz(n,i) pour représenter le i-ième terme n de la suite de Collatz :

    fCollatz(n, i) = 1 (n=1)
    fCollatz(n, i) = fCollatz(n/2, i+1) (n est pair)
    fCollatz(n, i) = fCollatz(3n+1, i+1) (n est impair)

    Par exemple :
    fCollatz(5, 1) : 5, 16, 8, 4, 2, 1
    fCollatz(27, 1) : une série de 112 termes qui monte et descend avant d’atteindre 1, avec une valeur maximale de 9232.
    fCollatz(40, 1) : 40, 20, 10, 5, 16, 8, 4, 2, 1

    À ce jour, la conjecture a été vérifiée par ordinateur pour toutes les valeurs de départ jusqu’à près de 300 milliards de milliards et chaque nombre finit par atteindre 1.

    La plupart des chercheurs pensent que la conjecture est vraie. Elle a séduit des multitudes de mathématiciens et de non-mathématiciens, mais personne n’en a apporté la preuve. Au début des années 1980, le mathématicien hongrois Paul Erdős a déclaré : « Les mathématiques ne sont pas encore prêtes pour de tels problèmes. »

    2. J’ai fait un programme en C et vous pouvez le tester avec un compilateur en ligne :
    https://www.onlinegdb.com/online_c_compiler

    #include

    int fCollatz(int n , int i) {
    printf(« %d « ,n);
    if(n<=1) {
    printf("\nThe number takes %d steps to converge to 1 \n",i);
    return 1;
    }
    else if(n%2==0) {
    i++;
    return fCollatz(n/2,i);
    }
    else {
    i++;
    return fCollatz(n*3+1,i);
    }
    }

    int main() {
    int n;
    scanf("%d",&n);
    fCollatz(n,1);
    return 0;
    }

    Reference :
    [1]https://fr.wikipedia.org/wiki/Conjecture_de_Syracuse
    [2] https://www.technologyreview.com/2021/07/02/1027475/computers-ready-solve-this-notorious-math-problem/

  29. Avatar de BasicRabbit
    BasicRabbit

    Bonjour Yu Li.

    En cherchant à me renseigner sur vous sur Internet pour savoir quelles étaient vos préoccupations scientifiques, je suis tombé -entre autres- sur (1) qui parle des problèmes de décision en un autre sens que celui de Gödel (qui, lui, parle de décidabilité). Je pense qu’il faut ici -sur les commentaires de cet article-ci- en rester au passionnant problème de la résolution des paradoxes. Aussi je verrais bien se limiter ici au paradoxe du menteur (sujet central), au paradoxe de Achille et de la tortue, mentionné dans votre article, au paradoxe chinois « du-blanc-cheval-qui-n’est-pas-cheval » (paradoxe dont parle PJ dans le premier chapitre de « Comment la vérité… »).

    Pour moi les problèmes de décision ne sont pas des problèmes de décidabilité : en français on fait nettement la distinction entre ces deux mots, décidabilité renvoyant à « puissance » et décision à « acte ».

    En décision il y a, selon moi, à distinguer le problème P vs NP dans les théories décidables dont les plus simples sont les théories admettant l’élimination des quantificateurs : corps algébriquement clos, corps réels fermés, etc. (2). La conjecture de Collatz, comme la conjecture des nombres premiers jumeaux, sont des conjectures qui seront peut-être décidées un jour dans l’arithmétique de Peano, arithmétique dont « on » sait (« on » n’est pas tout-à-fait tout le monde…) qu’elle est une théorie indécidable; je ne pense pas qu’il y ait grand chose de général à tirer de ça avant longtemps (au cas par cas, c’est autre chose: la conjecture de Collatz peut être résolue demain!).

    Bien à vous,
    BR

    1: https://home.mis.u-picardie.fr/~yli/docs/DdR-4/chap3.pdf

    2: Éléments de logique mathématique: théorie des modèles, Georg Kreisel, Jean Louis Krivine, Dunod, 1967 – 214 pages

  30. Avatar de Yu LI
    Yu LI

    @BasicRabbit Merci beaucoup pour votre attention !

    Vous dites:Je pense qu’il faut ici -sur les commentaires de cet article-ci- en rester au passionnant problème de la résolution des paradoxes.

    Je suis tout à fait d’accord, et c’est exactement le débat et la signification que le théorème d’incomplétude de Gödel soulève !

    Pour la conjecture de Collatz, un exemple apparemment simple qui pourrait avoir des matières plus riches qu’on ne le pense, le propos du mathématicien hongrois Paul Erdős est remarquables : « Mathematics is not yet ready for such problems”, …

Répondre à Yu LI Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

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

Contact

Contactez Paul Jorion

Commentaires récents

Articles récents

Catégories

Archives

Tags

Allemagne Aristote bancor BCE Bourse Brexit capitalisme centrale nucléaire de Fukushima ChatGPT Chine Confinement Coronavirus Covid-19 dette dette publique Donald Trump Emmanuel Macron Espagne Etats-Unis Europe extinction du genre humain FMI France Grèce intelligence artificielle interdiction des paris sur les fluctuations de prix Italie Japon John Maynard Keynes Karl Marx pandémie Portugal psychanalyse robotisation Royaume-Uni Russie réchauffement climatique Réfugiés spéculation Thomas Piketty Ukraine ultralibéralisme Vladimir Poutine zone euro « Le dernier qui s'en va éteint la lumière »

Meta