Comment fonctionne la preuve de Gödel

Ses théorèmes incomplets ont détruit la recherche d’une théorie mathématique de tout. Près d’un siècle plus tard, nous en subissons encore les conséquences. Voici une explication de Quanta magazine.

En 1931, le logicien autrichien Kurt Gödel a réalisé l’une des plus grandes réussites intellectuelles de l’histoire.

Wikipédia

Les mathématiciens de l’époque recherchaient une base solide pour les mathématiques : un ensemble de faits mathématiques de base, ou axiomes, à la fois cohérent – n’entraînant jamais de contradictions – et complet, servant de base à toutes les vérités mathématiques.

Mais les choquants théorèmes d’incomplétude de Gödel, publiés alors qu’il n’avait que 25 ans, ont écrasé ce rêve. Il a prouvé que tout ensemble d’axiomes que l’on peut poser comme fondement possible des mathématiques sera inévitablement incomplet ; il y aura toujours des faits réels sur les nombres qui ne pourront être prouvés par ces axiomes. Il a également montré qu’aucun ensemble d’axiomes candidats ne peut jamais prouver sa propre cohérence.

Ses théorèmes d’incomplétude signifient qu’il ne peut y avoir de théorie mathématique de tout, ni d’unification de ce qui est prouvable et de ce qui est vrai. Ce que les mathématiciens peuvent prouver dépend de leurs hypothèses de départ, et non d’une quelconque vérité de base fondamentale d’où découlent toutes les réponses.

Au cours des 89 années qui ont suivi la découverte de Gödel, les mathématiciens sont tombés par hasard sur le type de questions auxquelles ses théorèmes prédisaient qu’il était impossible de répondre. Par exemple, Gödel lui-même a contribué à établir que l’hypothèse du continuum, qui concerne les tailles de l’infini, est indécidable, tout comme le problème de l’arrêt, qui demande si un programme informatique alimenté par une entrée aléatoire fonctionnera éternellement ou s’arrêtera finalement. Des questions indécidables se sont même posées en physique, suggérant que l’incomplétude Gödelienne n’affecte pas seulement les mathématiques, mais – d’une manière mal comprise – la réalité.

Voici un récapitulatif simplifié et informel de la façon dont Gödel a prouvé ses théorèmes.

Numérotation de Gödel

La principale manœuvre de Gödel consistait à faire correspondre des énoncés sur un système d’axiomes à des énoncés à l’intérieur du système, c’est-à-dire à des énoncés sur des nombres. Ce mappage permet à un système d’axiomes de parler de lui-même de manière convaincante.

La première étape de ce processus consiste à faire correspondre tout énoncé mathématique possible, ou toute série d’énoncés, à un nombre unique appelé nombre de Gödel.

La version légèrement modifiée du schéma de Gödel présentée par Ernest Nagel et James Newman dans leur livre de 1958, La preuve de Gödel, commence avec 12 symboles élémentaires qui servent de vocabulaire pour exprimer un ensemble d’axiomes de base. Par exemple, l’affirmation que quelque chose existe peut être exprimée par le symbole ∃, tandis que l’addition est exprimée par +. Il est important de noter que le symbole s, qui désigne le « successeur de », donne une façon de spécifier des nombres ; ss0, par exemple, se réfère à 2.

Ces douze symboles se voient alors attribuer les nombres de Gödel 1 à 12.

Ensuite, les lettres représentant des variables, commençant par x, y et z, s’appliquent aux nombres premiers supérieurs à 12 (c’est-à-dire 13, 17, 19, …).

Ensuite, toute combinaison de ces symboles et variables – c’est-à-dire toute formule arithmétique ou séquence de formules pouvant être construite – obtient son propre nombre de Gödel.

Par exemple, considérons que 0 = 0. Les trois symboles de la formule correspondent aux nombres de Gödel 6, 5 et 6. Gödel doit transformer cette séquence de trois nombres en un seul et unique nombre – un nombre qu’aucune autre séquence de symboles ne générera. Pour ce faire, il prend les trois premiers nombres premiers (2, 3 et 5), les élève chacun au nombre de Gödel du symbole qui se trouve à la même position dans la séquence, et les multiplie ensemble. Ainsi, 0 = 0 devient 26 × 35 × 56 soit 243 000 000.

La cartographie fonctionne parce qu’il n’y a pas deux formules qui finissent par avoir le même nombre de Gödel. Les nombres de Gödel sont des entiers, et les entiers ne sont pris en compte dans les nombres premiers que d’une seule manière. Ainsi, la seule factorisation des nombres premiers de 243 000 000 est 26 × 35 × 56, ce qui signifie qu’il n’y a qu’une seule façon possible de décoder le nombre de Gödel : la formule 0 = 0.

Gödel est ensuite allé plus loin. Une preuve mathématique consiste en une séquence de formules. Gödel a donc également donné à chaque séquence de formules un nombre de Gödel unique. Dans ce cas, il commence par la liste des nombres premiers comme précédemment – 2, 3, 5 et ainsi de suite. Il élève ensuite chaque nombre premier au nombre de Gödel de la formule à la même position dans la séquence (2243,000,000 × …, si 0 = 0 vient en premier, par exemple) et multiplie le tout.

Arithmétique des métamathématiques

La véritable aubaine est que même les énoncés sur les formules arithmétiques, appelés énoncés métamathématiques, peuvent eux-mêmes être traduits en formules avec leurs propres nombres de Gödel.

Considérons d’abord la formule ~(0 = 0), qui signifie « zéro n’est pas égal à zéro ». Cette formule est clairement fausse. Néanmoins, elle a un nombre de Gödel : 2 élevé à la puissance 1 (le nombre de Gödel du symbole ~), multiplié par 3 élevé à la puissance 8 (le nombre de Gödel du symbole « parenthèse ouverte »), et ainsi de suite, donnant 2¹ × 3× 5× 7× 11× 139.

Parce que nous pouvons générer des nombres de Gödel pour toutes les formules, même fausses, nous pouvons parler raisonnablement de ces formules en parlant de leurs nombres de Gödel.


Abstractions navigue entre des idées prometteuses en sciences et en mathématiques.
Voir tout le blog Abstractions

Considérons l’énoncé suivant : « Le premier symbole de la formule ~(0 = 0) est un tilde. Cette (vraie) affirmation métamathématique sur ~(0 = 0) se traduit par une affirmation sur le nombre de Gödel de la formule – à savoir que son premier exposant est 1, le nombre de Gödel pour un tilde. En d’autres termes, notre déclaration dit que 2¹ × 3× 5× 7× 11× 139 n’a qu’un seul facteur de 2. Si ~(0 = 0) avait commencé par un symbole autre qu’un tilde, son nombre de Gödel aurait au moins deux facteurs de 2. Donc, plus précisément, 2 est un facteur de 2¹ × 3× 5× 7× 11× 139, mais 22 n’est pas un facteur.

Nous pouvons convertir la dernière phrase en une formule arithmétique précise que nous pouvons écrire* à l’aide de symboles élémentaires. Cette formule comporte bien sûr un nombre de Gödel, que nous pourrions calculer en faisant correspondre ses symboles à des puissances de nombres premiers.

Cet exemple, écrit Nagel et Newman, « illustre une idée très générale et profonde qui est au cœur de la découverte de Gödel : on peut parler des propriétés typographiques de longues chaînes de symboles de manière indirecte mais parfaitement précise en parlant plutôt des propriétés des factorisations premières de grands nombres entiers ».

La conversion en symboles est également possible pour l’énoncé métamathématique : « Il existe une séquence de formules avec le nombre de Gödel x qui prouve la formule avec le nombre de Gödel k » – ou, en bref, « La formule avec le nombre de Gödel k peut être prouvée ». La capacité à « arithmétiser » ce genre d’affirmation a préparé le terrain pour le coup.

G Lui-même

Gödel a également compris qu’il pouvait substituer le numéro de Gödel d’une formule dans la formule elle-même, ce qui n’a pas empêché les ennuis.

Pour voir comment fonctionne la substitution, il suffit de considérer la formule (∃x)(x = sy). (Elle dit : « Il existe une variable x qui est le successeur de y », ou, en bref, « y a un successeur »). Comme toutes les formules, elle comporte un nombre de Gödel – un grand nombre entier que nous appellerons simplement m.

Introduisons maintenant m dans la formule à la place du symbole y. Cela forme une nouvelle formule, (∃x)(x = sm), qui signifie « m a un successeur ». Comment appellerons-nous le nombre de Gödel de cette formule ? Il y a trois éléments d’information à transmettre : Nous avons commencé par la formule qui a le numéro de Gödel m. Dans cette formule, nous avons substitué m au symbole y. Et selon le schéma de cartographie introduit précédemment, le symbole y a le numéro de Gödel 17. Désignons donc le sous-ensemble du nombre de Gödel de la nouvelle formule (m, m, 17).

Il a considéré une affirmation métamathématique du type « La formule avec le nombre de Gödel sub(y, y, 17) ne peut être prouvée ». Rappelant la notation que nous venons d’apprendre, la formule avec le nombre de Gödel sub(y, y, 17) est celle obtenue en prenant la formule avec le nombre de Gödel y (une variable inconnue) et en substituant cette variable y partout où il y a un symbole dont le nombre de Gödel est 17 (c’est-à-dire partout où il y a un y).

Les choses se compliquent, mais néanmoins, notre affirmation métamathématique – « La formule avec le nombre de Gödel sub(y, y, 17) ne peut être prouvée » – est sûre de se traduire par une formule avec un nombre de Gödel unique. Appelons-le n.

Maintenant, un dernier tour de substitution : Gödel crée une nouvelle formule en substituant le nombre n partout où il y a un y dans la formule précédente. Sa nouvelle formule est la suivante : « La formule avec le numéro de Gödel sub(n, n, 17) ne peut être prouvée ». Appelons cette nouvelle formule G.

Naturellement, G a un nombre de Gödel. Quelle est sa valeur ? Et voilà, il doit être sub(n, n, 17). Par définition, sub(n, n, 17) est le nombre de Gödel de la formule qui résulte du fait de prendre la formule avec le nombre de Gödel n et de substituer n partout où il y a un symbole avec le nombre de Gödel 17. Et G est exactement cette formule ! En raison du caractère unique de la factorisation première, nous voyons maintenant que la formule dont G parle n’est autre que G lui-même.

G affirme de lui-même qu’il ne peut pas être prouvé.

Mais G peut-il être prouvé ? Si oui, cela signifierait qu’il existe une séquence de formules qui prouve la formule avec le nombre de Gödel sub(n, n, 17). Mais c’est le contraire de G, qui dit qu’une telle preuve n’existe pas. Les affirmations opposées, G et ~G, ne peuvent pas être toutes deux vraies dans un système axiomatique cohérent. La vérité de G doit donc être indécidable.

Cependant, bien que G soit indécidable, il est clairement vrai. G dit : « La formule avec le nombre de Gödel sub(n, n, 17) ne peut être prouvée », et c’est exactement ce que nous avons constaté ! Puisque G est vrai mais indécidable dans le système axiomatique utilisé pour le construire, ce système est incomplet.

On pourrait penser qu’il suffit de poser un axiome supplémentaire, de l’utiliser pour prouver G, et de résoudre le paradoxe. Mais ce n’est pas le cas. Gödel a montré que le système axiomatique augmenté permettra de construire une nouvelle formule vraie Gʹ (selon un schéma similaire à celui de la précédente) qui ne peut pas être prouvée dans le cadre du nouveau système augmenté. En s’efforçant d’obtenir un système mathématique complet, on ne peut jamais se prendre la queue.

Aucune preuve de cohérence

Nous avons appris que si un ensemble d’axiomes est cohérent, alors il est incomplet. C’est le premier théorème d’incomplétude de Gödel. Le second – selon lequel aucun ensemble d’axiomes ne peut prouver sa propre cohérence – suit facilement.

Qu’est-ce que cela signifierait si un ensemble d’axiomes pouvait prouver qu’il ne produira jamais de contradiction ? Cela signifierait qu’il existe une séquence de formules construite à partir de ces axiomes qui prouve la formule qui signifie, métamathématiquement, « Cet ensemble d’axiomes est cohérent ». Selon le premier théorème, cet ensemble d’axiomes serait alors nécessairement incomplet.

Mais « L’ensemble des axiomes est incomplet » revient à dire « Il y a une vraie formule qui ne peut être prouvée ». Cette affirmation est équivalente à notre formule G. Et nous savons que les axiomes ne peuvent pas prouver G.

Gödel a donc créé une preuve par contradiction : Si un ensemble d’axiomes pouvait prouver sa propre cohérence, alors nous serions en mesure de prouver G. Mais nous ne pouvons pas. Par conséquent, aucun ensemble d’axiomes ne peut prouver sa propre cohérence.

La preuve de Gödel a tué la recherche d’un système mathématique cohérent et complet. La signification de l’incomplétude « n’a pas été entièrement sonder », écrivaient Nagel et Newman en 1958. Il reste vrai aujourd’hui.

 

Via Quanta magazine

Laisser un commentaire

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