Notes

• [1]
  Opinion subjective. J’espère faire partager mon engouement...
• [2]
  Vous les connaissez peut-être : ∃ pour « il existe », et ∀ pour « quel que soit ».
• [3]
  Exclues de la salle de concert, les « paralogiques », comme les nomme le logicien Jean-Yves Girard, composées des logiques dites « paraconsistantes, non monotones, épistémiques et floues ». En tant que sommité française de la discipline, il sera fréquemment cité dans ce chapitre.
• [4]
  Eh oui, au second balcon, on a une vue plus large, mais on entend moins bien !
• [5]
  Cet opérateur majeur, noté « ⇒ », peut s’interpréter, avec des pincettes, comme la locution « si... alors... ».
• [6]
  Car dès qu’il y a une centaine de variables, même le meilleur ordinateur du monde ne vous répondra pas.
• [7]
  Du type du modus ponens, que l’on a déjà vu au chapitre VI.
• [8]
  Soyons fous : « 1 + 1 = 4 », ou encore « la Maison Blanche est dirigée par un Martien ».
• [9]
  Comme nous n’aborderons pas le sujet en profondeur, et ne souhaitons pas laisser entendre que la pensée du grand Hilbert était étriquée, nous renvoyons le lecteur intéressé par des informations sur le « programme de Hilbert » au chapitre 1 de [22] et à l’article [23].
• [10]
  Les professionnels parlent de « signature ».
• [11]
  L’hypothèse de cohérence de la théorie est peu coûteuse, puisque l’on a bien compris que seule une théorie cohérente possède un intérêt.
• [12]
  Grosso modo, Dém ⇒ Vrai, dans une théorie cohérente. Une théorie cohérente ne devrait pas permettre de prouver des énoncés faux. En effet, si la théorie est incohérente, on peut démontrer un résultat et son contraire, de telle sorte que l’on n’a plus nécessairement Dém ⇒ Vrai. En réalité, on entrevoit ici une subtilité réclamant un peu plus que la cohérence. Toutefois, une version à peine retravaillée de la preuve du théorème permet d’obtenir le même résultat avec la seule hypothèse de cohérence.
• [13]
  On la trouve même chez de grands matheux, exemple dans [26] (p. 89) où Cédric Villani écrit que Gödel démontra qu’« aucune théorie mathématique n’est complète et qu’il subsiste toujours des énoncés qui ne sont ni vrais ni faux ». Evidemment, dans une volonté de vulgarisation, on peut tout de même lui pardonner !
• [14]
  Sauf, peut-être pour les positivistes, cf. l’article « Mathématique constructive », de Roger Apéry, dans [12] : « Tous les logiciens utilisent la méthode formaliste pour préciser les types de déductions valables ; la philosophie formaliste considère le texte formalisé non comme un outil commode, mais comme la seule réalité mathématique (les physiciens connaissent une distinction analogue entre la méthode positive, qui est la méthode de tous, et le positivisme, qui est la philosophie de quelques-uns). »
• [15]
  Le vrai terme : par « contraposition ».
• [16]
  Ainsi en est-il du calcul propositionnel et du calcul des prédicats, i.e. de la logique pure, système de déduction considéré en tant que théorie, sans le langage qui lui permet, par exemple, de faire de l’arithmétique. La complétude de ces logiques trace une réciprocité entre les règles logiques (le système formel de déduction) et leur interprétation.
• [17]
  Traduction de Patrice Blanchard reprise de [3], p. 151.
• [18]
  Même si l’arithmétique a été démontrée cohérente par la théorie des ensembles, beaucoup plus puissante, et donc, sauf à ce que cette dernière soit incohérente, il ne devrait pas pouvoir être démontré de « non-théorème de Gödel ».
• [19]
  L’implication de gauche à droite est la partie intéressante. La réciproque n’est que ex falso quodlibet, comme établi plus haut : l’existence d’un indécidable implique la cohérence...
• [20]
  Si l’on revient un instant sur la formule G, l’interprétation en termes de valeurs de vérité consiste elle-même à introduire un discours métamathématique, quelque chose qui n’est pas codé dans la théorie de l’arithmétique. Dans la présentation que nous avons faite du premier théorème d’incomplétude, notre pseudo-démonstration dit que G annonçant sa non-prouvabilité et n’étant pas prouvable est donc vraie. Il n’y a pas beaucoup d’arithmétique dans ce raisonnement, quoi qu’il soit parfaitement exact. La non-représentabilité de la vérité dans l’arithmétique est connue sous le nom de « théorème de Tarski », un sous-produit des théorèmes de Gödel qui leur est postérieur (cf. [22]).
• [21]
  Séminaire Droit et mathématique organisé par l’IHEJ à l’ENM, le 6 décembre 2018.
• [22]
  « D’ailleurs, j’avoue que, malgré mon énorme admiration pour ce mathématicien de première grandeur qu’était Hilbert, je n’ai jamais compris comment il avait pu croire qu’une machine pourrait donner automatiquement toutes les réponses à tous les problèmes diophantiens. », Jean Dieudonné dans [12]. Le mathématicien fait ici référence à la résolution, par Matiasevich, du dixième problème de Hilbert qui concerne un énoncé typique de l’arithmétique, les équations diophantiennes (c’est-à-dire polynomiales entières). La conclusion du génie russe est qu’il n’existe pas d’algorithme pouvant se prononcer sur la résolubilité de toutes les équations diophantiennes.
• [23]
  Ce serait énervant, et cette impossibilité imaginaire renseigne sur la frustration de ceux qui essayent de démontrer un indécidable. Il y a de quoi devenir chèvre !
• [24]
  Toujours avec les mêmes méthodes, essentiellement par réduction du problème à la question de l’arrêt, elle-même indécidable.
• [25]
  Saint Thomas d’Aquin : « Veritas est adæquatio rei et intellectus. »
• [26]
  Par souci pédagogique, je reprends toujours le même exemple, mais on se doute bien qu’une entreprise aura plutôt créé une IA permettant de classifier toute seule des pièces d’usage courant dans son activité...
• [27]
  A sa faible marge d’erreur près.
• [28]
  Une autre manière de voir les choses : créer cet algorithme de vérification du classifieur revient à demander à ce dernier de déterminer, en même temps que sa prédiction, si celle-ci est juste, ou au moins de donner une probabilité absolue de confiance sur son résultat. Mais pour la mesurer, il faudrait que l’algorithme puisse se comparer de lui-même (i.e. sans intervention extérieure) à la réalité, et donc qu’il ait connaissance du vrai résultat. Si c’était le cas, pourquoi vous enverrait-il sa réponse peut-être erronée, autant vous donner la bonne tout de suite !
• [*]
  Des philosophes, comme J. R. Lucas (1961), ont affirmé que ce théorème [Gödel] prouve que les machines sont mentalement inférieures aux humains parce que ce sont des systèmes formels limités par le théorème d’incomplétude. »
• [29]
  Et on voit, tout de suite, que l’on n’ira pas très loin, le terme de « fondements » étant impropre dans ce contexte. Accordons magnanimement le bénéfice du doute : peut-être une erreur de traduction ?
• [30]
  Soit : dépourvue des contingences de ce monde ; car la machine de Turing n’est pas une machine au sens propre, juste un algorithme, assez inefficace d’ailleurs.