En 1931, le logicien autrichien Kurt Gödel a réalisé sans doute l’une des plus étonnantes réalisations intellectuelles de l’histoire.
Les mathématiciens de l’époque cherchaient une base solide pour les mathématiques : un ensemble de faits mathématiques de base, ou axiomes, qui était à la fois cohérent – ne menant jamais à des contradictions – et complet, servant d’éléments constitutifs de toutes les vérités mathématiques.
Mais les théorèmes d’incomplétude choquants 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 vous pourriez poser comme fondement possible des mathématiques sera inévitablement incomplet ; il y aura toujours des faits vrais sur les nombres qui ne pourront pas être prouvés par ces axiomes. Il a également montré qu’aucun ensemble d’axiomes candidat ne peut jamais prouver sa propre cohérence.
Ses théorèmes d’incomplétude signifiaient qu’il ne peut y avoir aucune théorie mathématique de tout, aucune 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 vérité fondamentale de base d’où jaillissent toutes les réponses.
Dans les 89 ans qui ont suivi la découverte de Gödel, les mathématiciens sont tombés sur exactement le genre de questions sans réponse que ses théorèmes annonçaient. 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 la halte, qui demande si un programme informatique alimenté par une entrée aléatoire fonctionnera éternellement ou finira par s’arrêter. Des questions indécidables sont même apparues en physique, ce qui suggère que l’incomplétude gödelienne n’afflige pas seulement les mathématiques, mais – d’une manière mal comprise – la réalité.
Voici un récapitulatif simplifié et informel de la manière dont Gödel a prouvé ses théorèmes.
Numérotation de Gödel
La principale manœuvre de Gödel consistait à mettre en correspondance les énoncés d’un système d’axiomes avec les énoncés du système – c’est-à-dire avec les énoncés relatifs aux nombres. Cette mise en correspondance permet à un système d’axiomes de parler de façon convaincante de lui-même.
La première étape de ce processus consiste à mettre en correspondance tout énoncé mathématique possible, ou toute série d’énoncés, avec 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, Gödel’s Proof, commence par 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 +. Fait important, le symbole s, qui désigne le » successeur de « , donne un moyen de spécifier les nombres ; ss0, par exemple, fait référence à 2.
Ces douze symboles se voient ensuite attribuer les nombres de Gödel de 1 à 12.
| Signe constant | Numéro de Gödel | Signification usuelle |
| ~ | 1 | not | ∨ | 2 | or |
| ⊃ | 3 | si…alors… | ∃ | 4 | il y a… est un… |
| = | 5 | equals |
| 0 | 6 | zero |
| s | 7 | le successeur de |
| ( | 8 | signe de ponctuation |
| ) | 9 | marque de ponctuation |
| , | 10 | marque de ponctuation |
| + | 11 | plus |
| × | 12 | times |
Suivant , les lettres représentant les variables, en commençant par x, y et z, correspondent à des nombres premiers supérieurs à 12 (c’est-à-dire 13, 17, 19, …).
Puis 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 0 = 0. Les trois symboles de la formule correspondent aux nombres de Gödel 6, 5 et 6. Gödel doit changer cette séquence de trois nombres en un seul et unique nombre – un nombre qu’aucune autre séquence de symboles ne pourra générer. Pour ce faire, il prend les trois premiers nombres premiers (2, 3 et 5), élève chacun d’eux au nombre de Gödel du symbole situé à la même position dans la séquence, puis les multiplie ensemble. Ainsi, 0 = 0 devient 26 × 35 × 56, soit 243 000 000.
Cette mise en correspondance fonctionne parce que deux formules n’aboutiront jamais au même nombre de Gödel. Les nombres de Gödel sont des entiers, et les entiers ne se factorisent en nombres premiers que d’une seule manière. Ainsi, la seule factorisation en 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 a ensuite fait un pas de plus. Une preuve mathématique consiste en une séquence de formules. Gödel a donc donné à chaque séquence de formules un numéro de Gödel unique également. 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 située à la même position dans la séquence (2243 000 000 × …, si 0 = 0 vient en premier, par exemple) et multiplie le tout ensemble.
Arithmétisation des métamathématiques
La véritable aubaine est que même les énoncés concernant les formules arithmétiques, appelés énoncés métamathématiques, peuvent eux-mêmes être traduits en formules possédant leur propre nombre de Gödel.
Premièrement, considérons la formule ~(0 = 0), qui signifie » zéro n’est pas égal à zéro. » Cette formule est clairement fausse. Néanmoins, elle possède 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, ce qui donne 2¹ × 38 × 56 × 75 × 116 × 139.
Parce que nous pouvons générer des nombres de Gödel pour toutes les formules, même les fausses, nous pouvons parler de manière sensée de ces formules en parlant de leurs nombres de Gödel.
Considérez l’affirmation suivante : » Le premier symbole de la formule ~(0 = 0) est un tilde. » Cet énoncé métamathématique (vrai) sur ~(0 = 0) se traduit par un énoncé 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 affirmation dit que 2¹ × 38 × 56 × 75 × 116 × 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 eu au moins deux facteurs de 2. Donc, plus précisément, 2 est un facteur de 2¹ × 38 × 56 × 75 × 116 × 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 a bien sûr un nombre de Gödel, que nous pourrions calculer en faisant correspondre ses symboles à des puissances de nombres premiers.
Cet exemple, écrivent Nagel et Newman, » exemplifie une intuition très générale et profonde qui se trouve 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 exacte en parlant plutôt des propriétés des factorisations premières des grands entiers. »
La conversion en symboles est également possible pour l’énoncé métamathématique : « Il existe une certaine séquence de formules de numéro x de Gödel qui prouve la formule de numéro k de Gödel » – ou, en bref, « La formule de numéro k de Gödel peut être prouvée. » La capacité à « arithmétiser » ce type d’énoncé a préparé le terrain pour le coup.
G Itself
La perspicacité supplémentaire de Gödel était qu’il pouvait substituer le propre nombre de Gödel d’une formule dans la formule elle-même, ce qui n’a pas manqué d’entraîner des problèmes.
Pour voir comment la substitution fonctionne, considérez la formule (∃x)(x = sy). (Elle se lit comme suit : » Il existe une variable x qui est le successeur de y « , ou, en bref, » y a un successeur « ). Comme toutes les formules, elle a un nombre de Gödel – un grand entier que nous appellerons simplement m.
Maintenant, introduisons m dans la formule à la place du symbole y. Cela forme une nouvelle formule, (∃x)(x = sm), ce qui signifie : » m a un successeur. » Comment appeler le nombre de Gödel de cette formule ? Il y a trois informations à transmettre : Nous avons commencé avec la formule qui a le numéro de Gödel m. Dans celle-ci, nous avons substitué m au symbole y. Et selon le schéma de correspondance introduit plus tôt, le symbole y a le numéro de Gödel 17. Désignons donc le nombre de Gödel de la nouvelle formule par sub(m, m, 17).
La substitution constitue le nœud de la preuve de Gödel.
Il a envisagé un énoncé métamathématique du type : » La formule avec le nombre de Gödel sub(y, y, 17) ne peut pas être prouvée. » En 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 certaine 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 deviennent triviales, mais néanmoins, notre énoncé métamathématique – » La formule avec le nombre de Gödel sub(y, y, 17) ne peut pas être prouvée » – est sûr 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 se lit comme suit : » La formule avec le nombre 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 bien 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 de la prise de la formule de nombre de Gödel n et de la substitution de n partout où il y a un symbole de nombre de Gödel 17. Et G est exactement cette formule ! En raison de l’unicité de la factorisation première, nous voyons maintenant que la formule dont parle G 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 certaine séquence de formules qui prouve la formule dont le nombre de Gödel est sub(n, n, 17). Mais c’est le contraire de G, qui dit qu’une telle preuve n’existe pas. Des énoncés opposés, G et ~G, ne peuvent pas être tous deux vrais dans un système axiomatique cohérent. Donc la vérité de G doit ê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 pas être prouvée « , et c’est exactement ce que nous avons trouvé être le cas ! Puisque G est vrai mais indécidable dans le système axiomatique utilisé pour le construire, ce système est incomplet.
Vous pourriez penser que vous pourriez simplement poser un axiome supplémentaire, l’utiliser pour prouver G, et résoudre le paradoxe. Mais ce n’est pas le cas. Gödel a montré que le système axiomatique augmenté permettra la construction d’une nouvelle formule vraie Gʹ (selon un plan similaire au précédent) qui ne peut pas être prouvée dans le nouveau système augmenté. En s’efforçant d’obtenir un système mathématique complet, on ne peut jamais attraper sa propre queue.
Pas de 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 – qu’aucun ensemble d’axiomes ne peut prouver sa propre cohérence – s’ensuit facilement.
Qu’est-ce que cela signifierait si un ensemble d’axiomes pouvait prouver qu’il ne donnera jamais une contradiction ? Cela signifierait qu’il existe une séquence de formules construites à partir de ces axiomes qui prouve la formule qui signifie, métamathématiquement, « Cet ensemble d’axiomes est cohérent. » Par le premier théorème, cet ensemble d’axiomes serait alors nécessairement incomplet.
Mais « L’ensemble d’axiomes est incomplet » revient à dire : « Il existe une formule vraie qui ne peut être prouvée. » Cette affirmation est équivalente à notre formule G. Et nous savons que les axiomes ne peuvent pas prouver G.
Donc Gödel a 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 le 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 sondée », écrivaient Nagel et Newman en 1958. Cela reste vrai aujourd’hui.
*Pour les curieux, l’énoncé se lit comme suit : « Il existe un certain nombre d’entiers x tel que x multiplié par 2 est égal à 2¹ × 38 × 56 × 75 × 116 × 139, et il n’existe pas d’entier x tel que x multiplié par 4 est égal à 2¹ × 38 × 56 × 75 × 116 × 139. » La formule correspondante est :
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
où sss … sss0 représente 2¹ × 38 × 56 × 75 × 116 × 139 exemplaires du symbole successeur s. Le symbole ⋅ signifie » et « , et est un raccourci pour une expression plus longue du vocabulaire fondamental : p ⋅ q représente ~(~p ∨ ~q).
Cet article a été repris sur Wired.com.