Ses théorèmes d'incomplétude ont vaincu la recherche d'une théorie mathématique de tout. Près de cent ans plus tard, nous essayons toujours d'en comprendre les conséquences.
En 1931, le logicien autrichien Kurt Gödel a fait ce qui est sans doute l'un des tours intellectuels les plus étonnants de l'histoire.
Les mathématiciens de cette époque recherchaient les fondements inébranlables des mathématiques: un ensemble de faits de base, d'axiomes cohérents et complets, jouant le rôle des éléments constitutifs de toutes les vérités mathématiques.
Cependant, les théorèmes d'incomplétude choquants de Gödel, publié par lui à seulement 25 ans, a brisé ce rêve. Il a prouvé que tout ensemble d'axiomes que vous pouvez proposer comme fondement des mathématiques sera inévitablement incomplet. Il y aura toujours de vraies déclarations sur les nombres qui ne peuvent pas être prouvées en utilisant ces axiomes. Il a également montré qu'aucun ensemble d'axiomes ne peut être utilisé pour prouver leur propre cohérence.
Ses théorèmes d'incomplétude signifient qu'il ne peut y avoir de théorie mathématique de tout et qu'il est impossible de combiner l'ensemble des énoncés prouvables avec l'ensemble des vrais. Ce que les mathématiciens peuvent prouver dépend des hypothèses initiales et non d'une vérité fondamentale dont toutes les réponses proviennent.
Au cours des 89 années qui se sont écoulées depuis la découverte de Gödel, les mathématiciens sont tombés sur des questions similaires sans réponse, dont l'existence prédit par ses théorèmes. Par exemple, Gödel lui-même a aidé à établir que l' hypothèse du continuum concernant les cardinalités des infinis est indécidable - tout comme le problème d'arrêt, dans lequel il est nécessaire de déterminer si l'exécution d'un programme informatique se terminera un jour avec certaines données d'entrée ou si elle fonctionnera pour toujours. Des questions insolubles se sont posées même en physique , ce qui suggère que l'incomplétude de Gödel affecte non seulement les mathématiques, mais dans un certain sens (pas tout à fait clair), la réalité.
Ce qui suit est un résumé bref, simplifié et informel de la façon dont Gödel a prouvé ses théorèmes.
Numérotation Gödel
Le mouvement principal de Gödel a été la comparaison des déclarations sur le système axiome avec les déclarations faites dans ce système - avec des déclarations sur les nombres. Cette juxtaposition permet au système d'axiomes de raisonner calmement sur lui-même.
La première étape consiste à faire correspondre tout énoncé mathématique possible, ou séquence d'énoncés, avec un numéro unique appelé le nombre de Gödel .
Une version légèrement révisée de la numérotation de Gödel telle que présentée dans le livre 1958 Gödel's Proof d' Ernest Nagel et James Newman, commence par 12 symboles élémentaires, qui servent de dictionnaire pour exprimer un ensemble d'axiomes de base. Par exemple, une déclaration sur l'existence de quelque chose peut être exprimée par le symbole ∃ et l'addition par le symbole +. Le s, qui signifie "élément suivant", permet de désigner des nombres: par exemple, ss0 signifie deux.
Ces douze caractères reçoivent ensuite les numéros Gödel 1 à 12.
| Notation constante | Numérotation Gödel | Signification commune |
| ~ | 1 | ne pas |
| ∨ | 2 | ou |
| ⊃ | 3 | si donc .. |
| ∃ | 4 | existe |
| = | cinq | équivaut à |
| 0 | 6 | zéro |
| s | 7 | prochain point |
| ( | 8 | signe de ponctuation |
| ) | neuf | signe de ponctuation |
| , | Dix | signe de ponctuation |
| + | Onze | un plus |
| × | 12 | multiplier |
Ensuite, les lettres désignant des variables, commençant par x, y et z, sont mises en correspondance avec des nombres premiers supérieurs à 12 (13, 17, 19, ..).
Ensuite, chacune des combinaisons de ces symboles et variables - c'est-à-dire toute formule arithmétique ou séquence de formules qui peut être composée - obtient son propre numéro de Gödel.
Prenons, par exemple, l'instruction 0 = 0. Ses trois symboles correspondent aux nombres de Gödel 6, 5 et 6. Gödel doit remplacer cette séquence de trois nombres par un unique - un nombre qu'aucune autre séquence de symboles ne produira. Pour ce faire, il prend les trois premiers nombres premiers (2, 3 et 5), élève chacun d'eux à la puissance égale au nombre correspondant dans la séquence, et les multiplie. Donc 0 = 0 devient 2 6 × 3 5 × 56 ou 243 000 000.
Ce balisage fonctionne car deux formules ne donneront pas le même numéro de Gödel. Les nombres de Gödel sont des nombres entiers, et les nombres peuvent être décomposés en facteurs premiers d'une manière unique. Par conséquent, la seule façon de factoriser 243 000 000 en facteurs est 2 6 × 3 5 × 5 6 , c'est-à-dire qu'il n'y a qu'une seule façon de déchiffrer ce nombre de Gödel: en écrivant la formule 0 = 0.
Puis Gödel est allé encore plus loin. Une preuve mathématique consiste en une séquence de formules. Par conséquent, Gödel a attribué à chaque séquence de formules son propre numéro de Gödel. Dans ce cas, il commence également par une séquence de nombres premiers - 2, 3, 5, etc. Puis il élève chacun d'eux à la puissance correspondant au nombre de Gödel pour la formule dans la même position ordinale dans la séquence (disons, 2 243 000 000 , si la formule 0 = 0 vient en premier), et multiplie tout ensemble.
Mathématiques arithmétiques
Il est remarquable que même les déclarations concernant les formules arithmétiques, les soi-disant. les déclarations métamathématiques peuvent être traduites en formules et attribuées à leurs propres numéros de Gödel.
Considérons d'abord la formule ~ (0 = 0), qui signifie «zéro n'est pas zéro». C'est clairement faux. Cependant, il a un nombre de Gödel: 2 à la puissance 1 (le nombre de Gödel pour le caractère ~), multiplié par 3 à la 8e puissance (le nombre de Gödel pour la parenthèse gauche), et ainsi de suite, ce qui donne finalement 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 .
Puisque nous pouvons générer des nombres de Gödel pour toutes les formules, même les fausses, nous pouvons raisonnablement les raisonner en utilisant leurs nombres de Gödel.
Considérez la déclaration «Le premier caractère de la formule ~ (0 = 0) est un tilde». Cette véritable déclaration métamathématique sur ~ (0 = 0) se transforme en une déclaration sur le nombre de Gödel d'une formule particulière - à savoir que son premier degré est 1, c'est-à-dire le nombre de Gödel pour le tilde. En d'autres termes, notre déclaration dit qu'il n'y a qu'un seul facteur «2» dans 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 . Si ~ (0 = 0) commençait par un caractère autre qu'un tilde, il y aurait au moins deux facteurs dans son nombre . Donc, pour le dire plus précisément, 2 est un facteur de 2 1 × 3 8 × 5 6 × 7 5× 11 6 × 13 9 , mais 2 2 ne l'est pas.
Nous pouvons convertir la dernière phrase en une formule mathématique exacte et l'écrire à l'aide de symboles élémentaires. Cette formule, naturellement, aura son propre nombre de Gödel, que nous pouvons calculer en faisant correspondre ses symboles aux puissances des nombres premiers.
Si vous êtes intéressé, alors la formulation se présente comme suit: il existe un entier x tel que x, multiplié par 2, sera égal à 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , mais il n'y a pas d'entier x tel qu'il multiplié par 4 a donné 2 1 × 3 8 × 5 6× 7 5 × 11 6 × 13 9 . La formule correspondante ressemble à ceci:
(∃x) (x × ss0 = sss… sss0) ⋅ ~ (∃x) (x × ssss0 = sss… sss0)
Où sss… sss0 signifie 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 copies du caractère de l'élément suivant a. Le symbole ⋅ signifie «et», et est une notation plus courte pour le vocabulaire fondamental: p ⋅ q signifie ~ (~ p ∨ ~ q).
Cet exemple, comme l'écrivaient Nagel et Newman, «illustre une idée générale et profonde sous-jacente à la découverte de Gödel: on peut parler très précisément des propriétés typographiques de longues séquences de caractères, mais pas directement, mais à travers les propriétés de la factorisation des grands entiers.
Les déclarations métamathématiques peuvent également être transformées en symboles. «Il y a une certaine séquence de formules avec le nombre de Gödel x, qui prouve une formule avec le nombre de Gödel k» - ou, en bref, «une formule avec le nombre de Gödel k est prouvable». C'est la capacité à «calculer» de telles déclarations qui a jeté les bases du coup d'État.
G seul
En outre, Gödel s'est rendu compte qu'il était possible de substituer le numéro de Gödel, désignant une formule, dans la formule elle-même - et cela conduit déjà à des problèmes sans fin.
Pour comprendre comment fonctionne cette substitution, considérons la formule (∃x) (x = sy). Cela signifie "il y a une variable x qui est l'élément suivant pour y", ou, plus simplement, "y" "" a l'élément suivant ". Comme toutes les formules, il a son propre nombre de Gödel - un grand entier, appelons-le m.
Entrons maintenant le nombre m dans la formule au lieu du symbole y. Le résultat est une nouvelle formule (∃x) (x = sm), ce qui signifie «m a l'élément suivant». Quel est le nombre de Gödel pour cette formule? Nous devons transmettre trois caractéristiques: nous avons commencé avec une formule qui a le nombre m de Gödel. Dans celui-ci, nous avons remplacé le symbole y par le symbole m. Et, selon le schéma de comparaison décrit précédemment, le nombre de Gödel du symbole y est 17. Notons alors le nombre de Gödel de la nouvelle formule sub (m, m, 17).
La substitution constitue la base de la preuve de Gödel.
L'élève Kurt Gödel à Vienne. Il a publié des théorèmes d'incomplétude en 1931, un an après avoir reçu son diplôme.
Il a considéré l'énoncé mathématique suivant: "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'adopter, nous savons que nous obtenons la formule avec le nombre de Gödel sub (y, y, 17) en prenant la formule avec le nombre de Gödel y (une variable inconnue) et en substituant cette variable y partout où le symbole avec Le nombre 17 de Gödel (c'est-à-dire partout où y apparaît).
La tête commence déjà à tourner, mais, néanmoins, nous pouvons certainement traduire notre déclaration métamathématique, «une formule avec le nombre de Gödel sous (y, y, 17) ne peut pas être prouvée», en une formule avec un nombre de Gödel unique. Appelons ça n.
Et la dernière étape des substitutions: Gödel crée une nouvelle formule, en substituant le nombre n partout où y apparaît dans la formule précédente. Sa nouvelle formule est la suivante: «La formule avec le nombre de Gödel sub (n, n, 17) ne peut être prouvée». Appelons cette formule G.
G a naturellement un nombre de Gödel. Quel est le nombre? Voila - il devrait être sous (n, n, 17). Par définition, sub (n, n, 17) est le nombre de Gödel pour la formule, qui est obtenu en prenant la formule avec le nombre de Gödel n et en remplaçant n partout où un symbole avec le nombre de Gödel égal à 17 apparaît dans la formule. Et G est exactement une telle formule et il y a! Puisque les entiers sont décomposés en facteurs premiers d'une manière unique, il devient clair pour nous que la formule G ne nous dit que sur la formule G elle-même, et rien d'autre.
G dit que lui-même ne peut pas être prouvé.
Mais G peut-il être prouvé? Si cela était possible, cela signifierait qu'il existe une séquence de formules prouvant une formule avec un numéro de Gödel sub (n, n, 17). Mais c'est le contraire de la formule G, qui dit qu'il n'y a pas de telle preuve. Les déclarations opposées, G et ~ G, dans un système cohérent d'axiomes ne peuvent pas être simultanément vraies. Par conséquent, G doit être indémontrable.
Cependant, même si G ne peut être prouvé, c'est certainement vrai. G dit que «la formule avec le nombre de Gödel sub (n, n, 17) ne peut pas être prouvée», ce que nous avons exactement établi! Puisque G est un énoncé vrai mais non démontrable qui existe dans le système axiomatique que nous avons utilisé pour le construire, ce système est incomplet.
Vous pourriez penser que nous pouvons simplement ajouter un axiome supplémentaire, l'utiliser pour prouver G et résoudre ce paradoxe. Mais c'est impossible. Gödel a montré que le système augmenté d'axiomes permettra de créer une nouvelle vraie formule G 'selon le même schéma que précédemment, ce qui ne peut être prouvé dans le cadre du nouveau système augmenté. En essayant de construire un système mathématique complet, vous ne poursuivrez sans succès que votre propre queue.
Manque de preuve de cohérence
Nous savons maintenant que si un ensemble d'axiomes est cohérent, il est incomplet. C'est le premier théorème d'incomplétude de Gödel. Le second en découle facilement - aucun ensemble d'axiomes ne peut prouver sa cohérence.
Que signifierait-il si un ensemble d'axiomes pouvait prouver qu'il ne serait jamais controversé? Cela signifierait qu'il existe une séquence de formules construites sur ces axiomes, prouvant une formule qui signifie métamathématiquement «cet ensemble d'axiomes est cohérent». Mais alors, selon le premier théorème, cet ensemble d'axiomes serait nécessairement incomplet.
Cependant, dire que «l'ensemble des axiomes est incomplet» revient à dire «il y a une vraie formule qui ne peut être prouvée». Et cela équivaut à notre formule G.Et nous savons que les axiomes ne peuvent pas prouver G.
Donc Gödel a construit une preuve par contradiction: si un ensemble d'axiomes pouvait prouver leur propre cohérence, alors nous pourrions prouver G. Mais nous ne pouvons pas. Par conséquent, aucun ensemble d'axiomes ne prouve sa propre cohérence.
La preuve de Gödel a tué la quête d'un système mathématique cohérent et complet. Les mathématiciens «n'ont pas réussi à saisir toute la profondeur» de l'incomplétude, écrivaient Nagel et Newman en 1958. Et aujourd'hui, cette affirmation reste vraie.
Voir également: