Kurt Gödel - Le théorème d'Incomplétude

Gödel est assurément la figure scientifique marquante du 20^ème et on peut l’affirmer sans crainte d’être contredit, le plus éminent logicien depuis le « père » de la logique, Aristote. Gödel a révolutionné la logique et les mathématiques.

Kurt Gödel a fait des mathématiques et plus précisément de la logique un domaine de prédilection dans lequel il allait laisser éclater tout son génie très tôt. Loin de se targuer d’avoir révolutionné la pensée de son époque, Gödel fuira la notoriété toute sa vie durant au contraire de son ami Einstein, rencontré aux Etats-Unis, qui lui profitera d’une célébrité exacerbée.

Gödel répond exactement à l’image que l’on peut se faire d’un génie, personnage totalement décalé et novateur.

C'est en sepenchant sur la personnalité de l’Homme et ses idées sur le monde intellectuelle de l'époque que l'on peut au mieux appréhender ses travaux et comprendre dans quelles mesures ses résultats sont effectivement les plus marquants que les mathématiques aient connus.

a)    L’axiome du choix et l’hypothèse du continu

Gödel a travaillé simultanément sur l’axiome du choix (AC) et sur l’hypothèse du continu (HC) : il a effectivement démontré en 1938 que l’ajout de l’AC et de l’HC à l’axiomatisation de la théorie des ensembles de Georg Cantor ne change en rien la cohérence de la théorie.

 Rappelons dans un premier temps ce que sont ces deux « problèmes » et les questions qu’ils soulevèrent à l’époque du programme de David Hilbert.

L’axiome du choix peut s’énoncer comme suit ; quelle que soit la classe d’ensembles non vides et disjoints (en nombre finis ou non) il existe une fonction de choix, un algorithme permettant d’extraire un élément unique dans chaque ensemble afin de constituer un nouvel ensemble non vide également.

On peut à ce propos expliciter le propos en donnant pour exemple « l’analogie » de Bertrand Russell qui disait que « pour choisir une chaussette plutôt que l’autre pour chaque paire d’une collection infinie, on a besoin de l’axiome du choix. Mais pour les chaussures, ce n’est pas la peine. » Le choix de la chaussure est régi par ce que l’on pourrait nommer un axiome du choix naturel, tandis que rien ne différencie a priori une chaussette gauche d’une droite : c’est en ce sens que l’axiome du choix est utile. Il permettrait à coup sûr de déterminer la gauche de la droite, il s’agit bien du même problème dans la théorie ensembliste. L’axiome du choix instaure une fonction assurant la mise en exergue d’un élément.

On pensait ces deux problèmes liés à l’époque de l’initiation du programme de Hilbert (Paul Cohen démontrera en 1963 que l’HC est en fait indécidable dans la théorie des ensembles de Zermelo-Fraenkel (ZF) montrant ainsi l’indépendance de AC et HC). Voilà pourquoi Gödel s’attela à travailler sur ces deux problèmes conjointement.

Gödel va répondre au premier des 23 problèmes du programme de Hilbert en démontrant l’indécidabilité de la question suivante : Peut-on prouver l’hypothèse du continu de Cantor ?

 L’existence comme la non-existence d’un sous-ensemble des réels pouvant être mis en bijection avec l’ensemble des entiers ou des réels lui-même est donc indécidable.

b)  L’argument ontologique quant à la preuve d’une existence divine

   Durant la seconde moitié de sa vie, Gödel a développé de fortes idées philosophiques et s’est décidé vers la fin de sa vie à construire une démonstration formelle de l’existence de Dieu. La démarche peut paraître saugrenue pour un athée et scientifique dont la rigueur mathématique était la force. Cependant, cette démonstration fut plus qu’un simple exercice de formalisation.

  Toute l’idée repose sur le terme d’ « ontologie ». En effet, l’ontologie s’intéresse à l’être en qu’Etre nécessaire et non en tant qu’Etre existant. On voit bien que Gödel avait dans l’idée d’asseoir encore un peu plus son platonisme mathématique le poussant à croire en des objets non accidentels, nécessaires. Reprenant les idées de son idole philosophique Leibniz, voici l’idée que Gödel va ensuite formaliser : si l’on admet l’existence possible d’un être parfait, donc d’une existence divine, c’est qu’inévitablement celle-ci existe effectivement et il ne peut en aller autrement. L’Homme a cette idée de l’existence de choses nécessaires ; au contraire des êtres soumis à la contingence. En pensant l’existence de Dieu possible, c’est déjà admettre qu’il existe. C’est un des aspects important de la philosophie gödelienne, le passage du possible au réel est légitime.

  C’est entreprise de démonstration (qui s’avérera être formellement inattaquable bien qu’irrecevable pour de multiples raisons philosophiques et physiques) révèle en fait le platonisme philosophico-mathématique du logicien, son attachement à la pensée de Leibniz et cette idée du lien entre possible et réel (problème qui sous-tend ses réflexions sur sa théorie de l’Univers de Gödel).

 Gödel refusera cependant de publier ce travail de son vivant, par crainte d’être considéré comme croyant et surtout de décrédibiliser encore un peu plus la philosophie émanant de ses travaux en physique relativiste. 

 

 

1933, Gödel alors âgé de 27 ans, s’illustre lors du colloque de Menger, du nom de Karl Menger, ami et collègue de Hans Hahn, qui ne fut autre que le directeur de thèse de Kurt Gödel quand il était encore à Vienne.

 Oswald Veblen, mathématicien engagé peu avant à l’Institute of Advanced Study, fut particulièrement impressionné par l’exposé du logicien sur le lien entre logiques classique et intuitionniste. Veblen se mue alors en chasseur de tête pour le compte de l’institut américain qui a réussi par ailleurs à séduire un autre génie de ce temps, Einstein.

 Veblen redoubla d’efforts pour sortir le jeune prodige de sa Vienne, lui promettant des collaborations qui seraient des plus prolifiques, avec des cerveaux éminents tant en matière de logique, de mathématique…et de physique. Attiser la curiosité et la soif de découverte de Gödel en lui faisant miroiter une kyrielle de projets mathématiques comme physiques était astucieux, quand on sait l’intérêt que portait alors Gödel pour le monde quantique.

 Malgré tout, Gödel fut manifestement frappé par ce qu’on peut appeler le Syndrome de Vienne, tel l’Einstein allemand. Il est vrai que l’Europe centrale de l’époque abritait une telle communauté intellectuelle, à la fois enracinée, profonde et très créatrice, que le monde intellectuellement au-delà de ce théâtre en effervescence aurait été fade, pour Gödel comme pour d’autres éminents scientifiques qui s’y sont formés. Il faudra attendre fin 1939 et la dégradation de la situation politico/religieuse (Gödel souffrait de l’image qu’il rendait malgré lui, il était pourtant athée mais fut finalement agressé par un groupe de nazillons et passait pour juif car portait la communauté et la cause juive en sympathie) pour que Gödel décide de quitter sa Vienne pour rejoindre les Etats-Unis et Princeton. Il débarque en Amérique le 4 mars 1940. Il allait y rencontrer une amitié discrète en la personne d’Einstein, dont l’excentricité et le génie lui valait une notoriété exacerbée.

 

Gödel, personnage sérieux et habitué à peu de compagnie, s’accommoda facilement à une période de solitude, où seules quelques relations scientifiques lui furent «agréables». Parmi eux se trouve Oskar Morgenstern, Karl Menger (cité plus haut), Georg Kreisel , Abraham Robinson ou encore Hao Wang, qui fut l’un des derniers collaborateurs de Gödel et dont on trouve la marque à la lecture de l’œuvre de Palle Yourgrau (Eintein/Gödel - Quand deux génies refont le monde). L’auteur a en effet eu le bonheur de faire sa rencontre et les deux hommes ont ainsi pu échanger des idées fortes intéressantes sur des sujets souvent passés sous silence et pourtant chers à Gödel durant toute la seconde moitié de sa vie. Son amitié humaine et scientifique avec Einstein, sa philosophie phénoménologique, ses réflexions sur les temps idéal et réel et la philosophique (influencées par ses idoles philosophiques) n’eurent injustement que très peu d’échos dans les sphères scientifique et philosophique. Les uns voyaient en Gödel un logicien tentant en vain de s’initier à la physique tandis que les autres eurent la critique rapide devant des réflexions philosophiques tellement originales qu’elles ne laissèrent que l’impression d’élucubrations.

Sa rencontre avec Einstein va révolutionner le monde scientifique, puis philosophique sous-jacent, car la pensée de Gödel était véritablement un monde à lui seul. Gödel, dans son monde, n’avait de cesse de démontrer ce qu’il nous est permis d’espérer en sciences : après avoir anéanti le rêve hilbertien d’un formalisme absolu en mathématique, Gödel s’apprêtait à explorer le monde physique …

Einstein dont la bonhomie était communicative, était de nature sociable et profitait de la vie. Gödel, dont l’hypocondrie grandissante l’obligeait à sortir par tout temps affublé d’une écharpe et d’un long manteau, était un génie marginal (pléonasme pourrait-on penser mais l’adjective ne s’appliquait pas à Einstein qui aimait la compagnie féminine et qui pouvait être reconnu dans la rue par un enfant…). L’analogie avec le duo Laurel et Hardy est possible : Einstein était plutôt grand, bon vivant tandis que Gödel n’avait pas la prestance impressionnante et était gracile. Clairement, les deux amis s’opposaient sur bien des points, ils avaient souvent des points de vue divergents mais c’est exactement pour cela qu’ils trouvèrent tous deux un complémentaire en l’autre.

Einstein avoua en fin de carrière retourner au bureau uniquement pour avoir le privilège de faire la marche avec Kurt Gödel. Gödel avait soif de découvrir plus amplement le monde de la physique. Durant leur promenade ces deux génies étaient coupés du monde, et la science pouvait bien s’affairer autour d’eux, chacun trouvait son compte dans ces discussions affranchies de toutes contraintes.

 

 

 

« Il n’est pas nécessaire de comprendre les équations de Gödel pour comprendre le théorème. On peut même les connaître parfaitement et n’avoir rien compris. Il faut vivre avec le théorème de Gödel, le méditer, jusqu’à ce que vous envahissent la beauté, l’évidence, la lumière, la douceur dont il est porteur. C’est le premier […] \"théorème poétique\". »

Jean Staune, Poésie d’un théorème

 

  Au-delà des mathématiques et de la logique, le théorème de Gödel a une portée philosophique indéniable et ce n’est en rien la technicité de la démonstration qui a troublé parmi les grands noms des mathématiques de l’époque. En effet, lorsque l’on parle de comprendre le résultat de l’incomplétude c’est en fait comprendre les conséquences à la fois scientifiques et philosophiques que celle-ci peut avoir notamment sur les notions de vérité et de déductibilité.

C’est ainsi que l’on peut parler du premier théorème poétique car le théorème de Gödel, bien plus que se comprendre, doit se ressentir. Finalement ce théorème met en lumière l’idée que l’essentiel ne peut ni être dit, ni être écrit ou vu (on retrouve ici l’attachement de Gödel à l’intuition mathématique). L’essentiel est dans l’intangible, dans ce qui nous échappera toujours…

Hilbert avait appelé son programme « La Solution Finale » … que penser alors d’un monde où la curiosité n’existerait plus, où toute question trouverait réponse. Voici ce que serait le véritable désastre : à désirer des mathématiques réduites on y perdrait la beauté d’une philosophie, réduite en conséquence. Avec son théorème d’incomplétude, Gödel est loin de détruire les mathématiques, au contraire il les ravive : jamais l’Homme n’aura à s’ennuyer.

Gödel est véritablement un génie puisqu’il parvient à montrer, mais surtout a soupçonné l’idée, que c’est la vérité transcendante, l’intangible, le détail dans la théorie qui donne sens et consistance à tout le reste.

On peut conclure sur cette thématique avec un écrit de Saint-Exupéry qui parlerait au nom d’un Dieu qui serait l’erreur dans le calcul :

  Tant l’énoncé du théorème que sa démonstration, tels qu’ils ont été rédigés par Kurt Gödel en 1931, et regroupés sous le titre traduit de « Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés », sont d’une complexité qu’il serait bien malaisée et inutile de retranscrire ici. Disons simplement que la magnificence de la démonstration ne réside pas comme on pourrait le penser dans la difficulté technique, mais bien plus dans l’originalité de la démarche du logicien.

L’idée de Gödel émane tellement d’un raisonnement allant à l’encontre du courant scientifique de l’époque, que son originalité a perdu bon nombre de ses contemporains les plus érudits en matière de logique.

C’est donc sur la démarche du raisonnement que l’intérêt doit se porter ; nous laisserons de côté autant que possible les difficultés d’ordre technique. L’idée est de mettre en lumière toute l’ingéniosité d’une démonstration mathématique étincelante d’une clarté philosophique indéniable, pour qui parviendrait, plus qu’à une compréhension brute de la démonstration, à un ressenti de la portée philosophique et scientifique du résultat.

Gödel est parvenu à deux résultats majeurs.

Nous allons ici clarifier au possible son énoncé original, ce qui mènera indubitablement à une vulgarisation. Quoique préjudiciable si l’on avait voulu respecter la rigueur mathématique, elle permettra de voir au-delà de la mécanique de démonstration tout en restant fidèle à l’idée de Gödel.

On appelle T une théorie récursivement axiomatisable, c’est-à-dire qu’il devient possible la mise en exergue d’une fonction récursive dont l’ensemble image contient tous les théorèmes ; théorèmes découlant donc d’un ensemble d’axiomes récursifs.

On attribue à T la qualité de cohérence. La théorie dans laquelle Gödel travaille est alors ∑-cohérente et démontre toutes les formules ∑₀  vraies dans l’ensemble N. Il existe alors une formule appelée G, négation d’une formule ∑₁, vraie dans N et pourtant indémontrable au sein de la théorie T.

  Plus généralement, il existe des assertions (nommées formules pour les besoins de la démonstration) que l’on sait vraies dans l’ensemble des entiers mais qui ne sont pas démontrables par l’utilisation exclusive de l’arithmétique (qui est la représentation générale de notre théorie T). Bien plus, Gödel montre que, quelle que soit la puissance d’une théorie ou son nombre d’axiomes, il existera inexorablement au moins une formule indécidable, autrement dit dont on ne peut démontrer ni G ni non-G.

  Gödel va habilement calquer une partie de la structure de sa démarche sur un raisonnement mené en 1905 par le français Jules Richard sur une antinomie logique alors baptisée « Paradoxe de Richard ». Jules Richard construit son raisonnement en utilisant l’argument diagonal initié par Georg Cantor, qui a prouvé la non-bijection entre les ensembles des entiers et des réels. En numérotant chaque nombre réel définissable en un nombre fini de mots, on peut légitimement construire un réel x « n’appartenant pas à cette liste », grâce à l’argument diagonal. On définit alors x comme richardien s’il satisfait la propriété désignée par sa définition. Au contraire x n’est pas richardien s’il ne la satisfait pas. On voit alors se dessiner le paradoxe logique : le réel x que l’on a construit hors de la liste des réels pouvant être définis par un nombre fini de mot sera richardien très exactement si et seulement si il n’est pas richardien (la définition de x conduit à la conclusion que x est défini par un nombre finis de mots, mais qu’il n’appartient pas à la liste des réels numérotés).

Le raisonnement menant à ce paradoxe est cependant fallacieux car introduit une sémantique qui nuit sérieusement à la logique formelle. Toute la prouesse de Gödel réside dans le fait d’avoir su utilisé le potentiel tacite de ce résultat : c’est le concept de projection qui va être la clé du succès du raisonnement de Gödel. 

  En affirmant qu’il est possible de représenter ces assertions métamathématiques (c’est ici que le bât blesse pour le paradoxe de richard, la métamathématique n’était pas un outil d’analyse autorisé) par des formules arithmétiques sur lesquels on pourrait désormais travailler, Gödel peut dès lors débuter un raisonnement sur des bases qui mèneront à des résultats irréfutables, car absous du sophisme dont souffrait le Paradoxe de Richard.

Gödel introduit la « numération de Gödel » et attribue ainsi un unique nombre à un unique symbole que l’on peut maîtriser sans peine. Le 1 correspond au symbole « ┐ » (qui représente le « non » sémantique), le 2 correspond au « V » ( « ou » sémantique ), et ainsi de suite… la numération sert l’arithmétisation et permet à Gödel de transposer chaque proposition, aussi complexe soit-elle, en unique nombre de Gödel. Le produit des nombres premiers sert de base (et il en sera ainsi pour tout nombre de Gödel) auquel Gödel ajoute en exposant de chaque nombre premier chaque numéro correspond à un symbole.

Par exemple, la formule ( Ǝ x ) ( x = s y ) aura pour nombre de Gödel 2⁸ * 3⁴ * 5¹¹ * 7 * 11⁸ * 13¹¹ * 17⁵ * 19⁷ * 23¹³ * 29⁹ ( puisque l’on a les correspondances suivantes : « ( » correspond au 8, « Ǝ » correspond au 4 etc)

Réciproquement, à partir d’un nombre de Gödel on retrouve la formule exprimée formellement et on peut construire toute une démonstration uniquement à base de nombres de Gödel.

  Gödel travaille sur 3 langages. L’arithmétique intuitive (AI) exprime les vérités arithmétiques grâce à la langue, de manière intuitive. L’arithmétique formelle (AF) contient des formules dénuées de contenu sémantique, elle est le miroir de l’AI puisque représente les vérités de l’AI. Enfin la métathéorie de l’arithmétique formelle (MAF) est en quelque sorte le « mode d’emploi » de l’AF, elle décide quelles formules sont bien formées et règle la théorie de la démonstration.

Gödel a montré que l’AF représente l’AI (entreprise déjà réalisée par Peano, Frege) mais il eut alors l’idée géniale et jusqu’alors insoupçonnée de montrer que l’AF pouvait représenter aussi la MAF, donc sa propre théorie. De cela découlera la construction d’une formule G à l’interprétation spéciale.

  Faisons correspondre l’assertion métamathématique « la suite de formules qui porte le nombre x n’est pas une démonstration de la formule qui porte le nombre de Gödel z » alors on voit bien que son arithmétisation est rigoureuse : « ┐Dem(x,z) »

 Après différentes étapes, qu’il ne sont pas indispensables de détailler, on désigne par « sub(y,13,y) » le nombre de Gödel de la formule que l’on a obtenu à partir d’une formule antécédente y ( le nombre de Gödel correspondant à « y » est 13) dans laquelle on a substitué à la variable portant le nombre de Gödel 13 le chiffre de y.

 Gödel définit alors la formule « (x) ┐Dem(x,sub(y,13,y)) » qui correspond à l’assertion métamathématique « La formule portant le nombre de Gödel sub(y,13,y) n’est pas démontrable »avec (x) qui fait référence au « pour tout x ».

  Gödel entend partir de cette formule générale pour montrer qu’un cas particulier n’est pas démontrable. En substituant à la variable y un chiffre n (une constante) on obtient naturellement (x)┐Dem(x,sub(n,13,n)). On appelle cette formule G dont le nombre de Gödel associé est (n,13,n). G est inhérente au calcul arithmétique et par définition G est l’image de l’assertion métamathématique « La formule qui porte le nombre de Gödel sub(n,13,n) n’est pas démontrable ». Enfin par une sorte de mise en abyme, il s’ensuit que la formule (x)┐Dem(x,sub(n,13,n)), intérieure à l’arithmétique, est associé à l’assertion : « La formule « (x)┐Dem(x,sub(n,13,n) »n’est pas démontrable ».

  Il reste alors à montrer formellement que la construction de G est légitime et que donc G est bien indémontrable. Gödel montre alors que si G était démontrable alors sa négation que l’on a désignée plus avant comme une formule ∑₁ le serait également (on voit bien ici l’impact du Paradoxe de Richard appliqué au système arithmétisé) et réciproquement bien évidemment.

 Cependant, et là réside la touche finale du raisonnement, si l’on démontrait une formule et sa négation alors on prouverait l’inconsistance de la théorie, or en introduisant l’hypothèse d’une théorie T récursivement axiomatisable (comme définie dans l’énoncé du théorème), on conclut qu’il est impossible de démontrer G et ∑_1. Dans tout système arithmétique quel qu’il soit, il existe bien une formule au moins indécidable.

On peut donc en conclure que l’assertion « la formule qui porte le notre de Gödel sub(n,13,n) (c’est-à-dire G) n’est pas démontrable » est une assertion vraie.

 La seconde partie du théorème d’incomplétude de Gödel est tout aussi surprenante que la première partie.

Elle consiste en effet à dire que « La consistance de tout système consistant contenant une théorie des nombres finitaires ne saurait être démontrée à l’intérieur de ce système ». Plus clairement, pour une théorie T (vue dans le premier énoncé du théorème), il est impossible de prouver sa consistance (c’est-à-dire le fait qu’aucune des assertions vraies dans T ne se contredise). Bien que le théorème d’incomplétude de Gödel soit séparé en deux parties, ce deuxième énoncé, ainsi que sa démonstration est la suite logique de ce que nous venons de voir.

La démonstration de Gödel, succinctement expliquée et donc forcément simplifiée se fait en plusieurs parties. Tout d’abord, Gödel montre que la même formule G, bien qu’elle ne soit pas démontrable, elle n’en reste pas moins vraie.

Pour ce faire, il en montre la preuve par le biais des métamathématiques. Rappelons que G représente le nombre de Gödel associé (n,13,n). Dans la première partie, nous avons montré que l’assertion métamathématiques « la formule « (x) ┐Dem(x,sub(n,13,n)) » n’est pas démontrable » est vraie. Grâce au mécanisme de projection déjà évoqué dans la première partie, on peut en conclure que G est vraie. En effet, l’assertion citée ci-dessus, par la formule qu’elle cite (à savoir G) est représentée à l’intérieur de l’arithmétique. Comme l’assertion métamathématique est vraie, la formule arithmétique citée dans l’assertion est également vraie.

Nous venons de démontrer que G est vraie, malgré le fait qu’elle soit indécidable. Or, nous ne sommes pas arrivés à cette conclusion par le biais des axiomes. S’il y a des théorèmes que l’on ne peut pas déduire que axiomes, alors les axiomes sont incomplets. On peut donc en conclure que les axiomes de l’arithmétique sont incomplets, sous la réserve faite au début que les axiomes de l’arithmétique sont consistants.

Néanmoins si on ajoutait G aux axiomes, on parviendrait toujours à trouver une formule indécidable et pourtant vraie. Cela veut dire qu’à partir des axiomes de l’arithmétique on ne peut pas systématiser la vérité arithmétique (puisqu’il y a des « vérités » auxquelles on ne peut pas arriver par les axiomes). Ensuite, Gödel prouve que la consistance de l’arithmétique ne peut être prouvée par un calcul arithmétique.

 Pour démontrer cela, il faut poser (A), une formule arithmétique telle que « L’arithmétique est consistante ». Il est évident que (A) peut se traduire par « Il existe au moins une formule de l’arithmétique qui n’est pas démontrable ».

En effet, si l’on prend une théorie dont tous les axiomes sont des tautologies, il est aisé de prouver cette dernière formule. Comme la propriété d’être une tautologie est héréditaire, toute formule qui n’est pas une tautologie n’est pas un théorème. En trouvant une formule qui n’est pas un théorème (donc qui n’est pas une tautologie) on montre aisément que si les axiomes de cette théorie n’étaient pas consistants, toutes les formules seraient des théorèmes. Donc, en trouvant une formule qui n’est pas un théorème (donc qui n’est pas décidable), on montre que les axiomes sont consistants.

Donc (A) devient l’assertion « Il existe au moins une formule de l’arithmétique qui n’est pas démontrable. En la traduisant sous la forme arithmétique, on trouve (A) : (Il existe y)(x) ┐Dem(x,y).

(A) constitue également l’antécédent de « Si l’arithmétique est consistante, elle est incomplète ».

Effectivement, on reconnaît la formule citée ci-dessus ainsi que notre précédente conclusion.

  La clé du raisonnement de Gödel consiste à poser A Ↄ G (c’est-à-dire « Si A alors G ») démontrable. On a donc : Si A démontrable, A Ↄ G démontrable et donc G démontrable. Or, nous avons montré dans la première partie du théorème d’incomplétude que G n’est pas démontrable.

On arrive à la conclusion que A n’est pas démontrable (à part si l’arithmétique n’est pas consistante). Plus précisément, nous avons démontré que l’assertion « L’arithmétique est consistante » n’est pas démontrable.

On pourrait prouver (A), si l’on trouvait une démonstration dans le calcul arithmétique (grâce au principe de projection, (A) serait elle-même démontrable). Malheureusement, si on suppose l’arithmétique consistante, elle est indécidable.

 En conclusion, on ne peut pas déduire la consistance de l’arithmétique par un raisonnement arithmétique ou métamathématique représenté dans l’arithmétique.