L’informatique au cœur des limites de l’esprit

Motivations

Les mathématiques se sont développées naturellement au fil des siècles en tant qu’outil au service d’une représentation abstraite de la réalité. Cet état de fait est par exemple flagrant en sciences physiques pour lesquelles les mathématiques rendent compte avec précision d’un ensemble varié de phénomènes. Avec le temps, les notions étudiées sont devenues de plus en plus complexes, de plus en plus abstraites, et les connexions entre les mathématiques et le monde réel sont devenues de plus en plus incertaines. Pendant longtemps cependant, la discipline a pu compter sur le sens logique inné de l’esprit humain pour parler de choses qu’on ne « voyait plus » tout en gardant un cadre rigoureux. Les nombres complexes en constituent un exemple frappant : ces nombres de carré négatif qui n’existent a priori que dans l’imagination du mathématicien sont baptisés en 1545 « quantités sophistiquées » par l’Italien Gerolamo Cardano (dit Jérôme Cardan). De la sophistication il en fallait sans doute pour accepter cet ovni comme objet d’étude sérieux. Pourtant ces « quantités sophistiquées » trouvent leur utilité dans la résolution de problèmes, eux, très concrets. Il a fallu un certain saut conceptuel pour accepter le développement d’un cadre mathématique rigoureux et cohérent autour des nombres complexes. Malgré tout, disons que ce concept, pour aussi surprenant qu’il soit, reste encore « relativement simple ». Les réels problèmes arrivent vers la fin du XIX^e siècle avec les travaux du mathématicien allemand Georg Cantor sur l’infini.

L’infini avant Cantor

L’infini est présent en mathématiques depuis l’Antiquité, en premier lieu via la considération qu’il n’existe pas de plus grand nombre entier : pour tout entier \(n\), l’entier \(n+1\) existe. Il s’agit d’un infini qualifié de potentiel, par opposition à l’infini actuel qui considère l’existence simultanée de tous les nombres entiers, via l’ensemble \(\mathbb{N}\) qui les contient. Bien avant Cantor, les mathématiciens avaient remarqué que l’infini actuel obéissait à des lois contre-intuitives, voire paradoxales ; la méfiance était alors de mise et il convenait de se tenir à bonne distance de cet animal imprévisible. Galilée fait une exposition lumineuse de cet état de fait dans son ouvrage « Discours concernant deux sciences nouvelles » à travers un dialogue savoureux entre deux personnages, Salviati et Simplicio :

– Salviati : J’estime que les épithètes comme “plus grand”, “plus petit” et “égal” ne conviennent pas aux grandeurs infinies, dont il est impossible de dire que l’une est plus grande, plus petite ou égale à une autre. Mais voici pour le prouver un raisonnement qui me revient à l’esprit. Vous savez parfaitement je suppose quels nombres sont carrés et quels nombres ne le sont pas.

– Simplicio : Je sais parfaitement qu’un nombre carré provient de la multiplication d’un autre nombre par lui-même ; ainsi quatre, neuf, etc… sont des nombres carrés résultant de la multiplication de deux, trois, etc… par eux-mêmes.

– Salviati : Fort bien, quant aux nombres qui ne proviennent pas de nombres multipliés par eux-mêmes, ce ne sont pas des carrés. Par conséquent si je dis que les nombres pris dans leur totalité, en incluant les carrés et les non-carrés, sont plus nombreux que les carrés seuls, j’énoncerai, n’est-ce pas, une proposition vraie ?

– Simplicio : Très certainement.

– Salviati : Si je demande maintenant combien il y a de nombres carrés, on peut répondre sans se tromper qu’il y en a autant que de racines correspondantes, attendu que tout carré a sa racine et toute racine son carré, qu’un carré n’a pas plus d’une racine et une racine pas plus d’un carré.

– Simplicio : Exactement.

– Salviati : Mais si je demande combien il y a de racines, on ne peut nier qu’il y en a autant que de nombres, puisque tout nombre est la racine de quelque carré, il faudrait admettre que les carrés sont aussi nombreux que tous les nombres pris ensemble.

À travers ce raisonnement, Galilée en conclut fort à propos qu’il n’y a aucun sens à comparer les tailles d’ensembles infinis : cela mène à des paradoxes.

La révolution de Cantor

Georg Cantor (1845-1918).

Cantor balayera les objections de Galilée en remarquant que si l’on est précis sur nos définitions, il n’y a finalement aucun paradoxe ; simplement une situation contre-intuitive : le tout n’est pas nécessairement plus grand que ses parties. Si l’on note \( \mathbb{N}^2 = \{ 0, 1, 4, 9, 16, \ldots \}\) l’ensemble des nombres qui sont des carrés d’autres nombres, effectivement \(\mathbb{N}^2\) est strictement inclus dans l’ensemble des entiers naturels \( \mathbb{N} = \{ 0, 1, 2, 3, 4, \ldots \}\), mais l’on ne peut rien en déduire sur la taille de \( \mathbb{N}^2\). On dira que deux ensembles ont la même taille si l’on peut faire correspondre chaque élément du premier ensemble à un élément du deuxième, de telle sorte que tout élément du deuxième a bien un unique élément du premier qui lui correspond : il s’agit en langage mathématique d’une bijection. Ainsi la fonction \( f(n) = n^2\) est bien une bijection entre \( \mathbb{N}\) et \(\mathbb{N}^2\). Les deux ensembles ont donc la même taille. Cela semble paradoxal car \( \mathbb{N}^2\) est strictement inclus dans \( \mathbb{N}\). Il faut simplement accepter qu’un ensemble infini – contrairement à un ensemble fini – n’est pas forcément plus grand que ses parties.

Il ne s’agit là que des balbutiements des contributions de Cantor, qui établira une liste de théorèmes très profonds sur l’infini, en commençant par montrer qu’il en existe bel et bien plusieurs tailles. Il montre en particulier que l’ensemble des nombres réels \( \mathbb{R} \) est un infini distinct de celui des nombres entiers \( \mathbb{N}\), dans le sens donné ci-dessus : il est impossible de trouver une bijection entre les deux ensembles. Comme \( \mathbb{N} \subseteq \mathbb{R} \), l’infini des réels est en fait strictement plus grand que celui des entiers. Cantor se posera naturellement la question de l’existence d’autres tailles d’infini, et notamment la suivante : existe-t-il un ensemble infini \( A \subseteq \mathbb{R} \) dont la taille est strictement plus grande que celle de \( \mathbb{N}\), et strictement plus petite que celle de \( \mathbb{R} \) ? Cantor cherchera toute sa vie et sans succès à montrer que ce n’est pas le cas ; sa conjecture est connue sous le nom d’hypothèse du continu : « Il n’y a aucun ensemble infini dont la taille est strictement comprise entre celle de \( \mathbb{N} \) et celle de \( \mathbb{R}\). »

Quelques dizaines d’années plus tard, en 1938, le logicien autrichien Kurt Gödel montrera qu’il est impossible de démontrer que l’hypothèse du continu est fausse. Et encore vingt-cinq ans plus tard, en 1963, le mathématicien américain Paul Cohen (1934-2007) montrera qu’il est impossible de démontrer que l’hypothèse du continu est vraie, apportant une conclusion magistrale à une aventure intellectuelle qui dura près d’un siècle, ce qui lui vaudra la médaille Fields en 1966.

L’hypothèse du continu est un énoncé mathématique indécidable, c’est-à-dire indépendant du reste de mathématiques. Il s’agit d’un résultat d’une grande profondeur, et qui porte non pas sur l’algèbre, l’analyse ou encore la géométrie, mais qui porte sur les mathématiques elles-mêmes. Voyons plus précisément de quoi il s’agit.

L’étude mathématique des mathématiques

Avec ses travaux à la fin du XIX^e siècle, Cantor ouvre grand la porte sur un gouffre sans fond qui nous emmène bien au-delà de ce que peut appréhender avec confiance l’esprit humain : l’étude de l’infini. La question de savoir ce qu’est l’activité mathématique s’est alors faite de plus en plus pressante : peut-on raisonner vraiment sur tout, et même sur l’infini, concept qui nous dépasse ? Et si l’on accepte, comme c’est le cas aujourd’hui que l’on peut raisonner sur l’infini, on ne peut certainement pas le faire n’importe comment. Au fond qu’est-ce faire des mathématiques ? En particulier quand on commence à manipuler des objets sur lesquels nous n’avons plus tellement d’intuition, comment être sûr que ce dont on parle a réellement un sens ? Ces considérations ont trouvé leur apogée lors de la fameuse « crise des fondements » qui va de la fin du XIX^e siècle au début du XX^e. Il est alors question de définir des règles pour encadrer l’activité mathématique. Il s’agit en fait de définir précisément l’étude mathématique non pas d’objets comme les entiers, les réels ou encore les fonctions, mais de définir l’étude mathématique des mathématiques elles-mêmes. Il est a posteriori remarquable de constater le succès de cette entreprise : les mathématiques sont un outil suffisamment puissant pour pouvoir se définir et s’étudier elles-mêmes, avec la rigueur inhérente à la discipline ! Voyons de quoi il retourne.

Qu’est-ce qu’une démonstration ?

Si l’on veut démontrer un énoncé, ce dernier doit pouvoir s’obtenir par des opérations de déduction logique à partir d’autres énoncés, qui eux-mêmes s’obtiennent par déduction logique d’autres énoncés, etc. On voit ici qu’il faut bien commencer quelque part. Il nous faut des énoncés que l’on considérera « vrais », sans chercher à les démontrer. Nous appelons axiomes de tels énoncés. Il s’agit des briques de base de nos démonstrations. Le choix des axiomes est capital. Il faut en avoir suffisamment pour démontrer des choses intéressantes, et il convient dans le même temps de se restreindre aux énoncés dont l’évidence s’impose à l’esprit avec suffisamment de force pour que personne ne songe à les remettre en question. Un axiome du type « les nombres premiers sont en quantité infinie » n’est pas acceptable. Il ne s’agit pas du tout d’une évidence éclatante, mais de l’aboutissement d’un raisonnement assez complexe. En revanche, un énoncé du type « tout ensemble non-vide d’entiers naturels possède un plus petit élément » est bien quelque chose d’évident et que a priori personne ne cherchera à remettre en question. Il s’agit de l’un des axiomes classiques de l’arithmétique, en particulier nécessaire à la démonstration du fait que les nombres premiers sont en quantité infinie.

Les axiomes

On distinguera deux types d’axiomes. Il y a d’abord les axiomes de la logique. Par exemple si \(A\), \(B\) sont des énoncés, l’énoncé \( (A \Rightarrow B ) \Leftrightarrow ( \neg B \Rightarrow \neg A) \) est un axiome de la logique. Il exprime que la phrase « si l’on a \(A\), alors on a \(B\) » est logiquement équivalente à la phrase « si l’on n’a pas \(B\), alors on n’a pas \(A\) ». Il est très utilisé pour faire ce que l’on appelle des raisonnements par contraposé, et nous en verrons quelques exemples dans la suite de cet article. Il y a enfin les axiomes relatifs au sujet que l’on étudie. Dans le cadre de l’arithmétique, un axiome sera par exemple : « pour tous entiers \(x\), \(y\), on a \( x \times (y+1) = x \times y + x\) », ou comme nous l’avons mentionné précédemment, « tout ensemble non-vide d’entiers naturels possède un plus petit élément ». Les protagonistes de la crise des fondements réussiront le tour de force de trouver un système d’axiomes – le système ZFC – permettant de formaliser la totalité des mathématiques. Pour montrer que l’hypothèse du continu est indépendante du reste des mathématiques, Gödel et Cohen ont prouvé qu’il n’existe aucune démonstration de cette hypothèse ou de sa négation à partir des axiomes de ZFC.

Les règles de déduction logique

Afin de prouver qu’il n’existe aucune démonstration de quelque chose, il faut s’entendre sur ce qu’est une démonstration. Cela aussi fut formalisé durant la crise des fondements : une démonstration est une suite d’énoncés mathématiques \( F_1, F_2, \ldots , F_k\) telle que chaque phrase \(F_i\) est soit un axiome, soit une phrase obtenue en appliquant des règles de déduction logique à des phrases précédant \(F_i\). Chaque phrase \(F_i\) dans la liste est considérée comme démontrée, la démonstration consistant en la suite \(F_1, \ldots , F_i\). Les règles de déduction sont en nombre fini et il en existe plusieurs systèmes tous équivalents entre eux. La plus emblématique de ces règles est certainement le « Modus Ponens«  qui est la base de tout raisonnement déductif : si l’énoncé \( G \Rightarrow H \) est démontré et si l’énoncé \(G\) est démontré alors on peut en déduire \(H\), qui sera ainsi lui aussi démontré.

Le programme de Hilbert

David Hilbert (1862-1943).

Rappelons que ce travail de formalisation était motivé par l’éloignement entre les mathématiques et les réalités sensibles de notre monde, en particulier suite aux travaux de Cantor sur l’infini. Il y avait à l’époque des « pro-Cantor », qui considéraient valides et même tout à fait pertinents les raisonnements sur l’infini, et les « anti-Cantor », qui considéraient que de tels raisonnements présentent un risque de paradoxes, et n’ont de toute façon pas leur place en mathématiques, dont l’objet principal est de fournir des outils pour les sciences qui expliquent le monde, notamment les sciences physiques. Le mathématicien allemand David Hilbert – qui contribua largement à la formalisation mathématique des démonstrations – fut certainement l’un des plus fervents défenseurs de Cantor. Il avait pour ambition de faire reconnaître la validité des raisonnements sur l’infini, en fondant ces derniers sur des raisonnements « finitistes ». Son objectif était d’identifier un système axiomatique finitiste – c’est-à-dire ne traitant que des objets finis – considéré comme sûr, et de montrer que l’intégralité des théorèmes, même ceux portant sur l’infini, pouvaient se démontrer au sein du système finitiste. C’est ce que l’on a appelé le programme de Hilbert, développé dans les années 1920 et qui fut au bout du compte de courte durée : en 1931, le jeune logicien Kurt Gödel fera preuve d’une ingéniosité et d’une profondeur de vue exceptionnelles, en donnant le premier exemple d’énoncé « impossible à démontrer ou à réfuter ». Contrairement à l’hypothèse du continu, l’énoncé fourni par Gödel ne parle pas de l’infini, mais d’objets finis beaucoup plus tangibles. Nous allons à présent tenter d’expliquer en quoi consiste ces énoncés « impossibles à démontrer ou à réfuter ».

Le premier théorème d’incomplétude

Kurt Gödel (1906-1978).

Gödel va se baser sur la théorie – ou encore le système d’axiomes – nommé « PA », qui permet de formaliser les mathématiques finitaires. Donner ici les détails de cette théorie nous ferait entrer dans trop de technicité. Mentionnons simplement que PA permet de manipuler les objets finis. Par exemple, l’énoncé \(F \equiv \) “il existe un nombre entier impair qui est multiple de 4” est un énoncé exprimable dans PA. Les objets dont parle cet énoncé sont les nombres entiers, des objets finis donc. Dans le cas de \(F\), nous avons affaire à un énoncé faux. Les axiomes de PA sont en effet capables de démontrer qu’aucun entier impair n’est multiple de 4. Voyons un autre exemple avec l’énoncé \(G \equiv \) “tout nombre pair est la somme de deux nombres premiers”. Il s’agit là aussi d’un énoncé exprimable dans PA, connu sous le nom de « conjecture de Goldbach« . Malgré sa simplicité, nous ne savons toujours pas aujourd’hui si la conjecture de Goldbach est vraie ou fausse : aucun mathématicien n’est encore parvenu à trouver une démonstration de cette conjecture ou bien de sa négation. On pensait avant Gödel que « la vérité » d’une conjecture se confondait avec sa « prouvabilité » : si un énoncé mathématique de PA est vrai, alors on en trouvera forcément une démonstration à l’aide des axiomes de PA, permettant d’en attester la vérité, et à l’inverse, si l’énoncé est faux, on pourra trouver une démonstration de sa négation à l’aide des axiomes de PA. Le premier théorème d’incomplétude de Gödel dispose au contraire que la « vérité » d’un énoncé ne se confond pas avec sa prouvabilité, et qu’il existe des énoncés mathématiques « concrets » en ce sens qu’ils ne parlent que d’objets finis, qui ne sont ni démontrables, ni réfutables à l’aide des axiomes de PA. De tels énoncés sont dits indécidables dans PA. Nous présentons à présent les grandes lignes de la démonstration de Gödel.

Gödel fait les considérations suivantes :

Première considération. La théorie PA est suffisamment puissante pour formaliser la notion de programmes informatiques. Il est tout à fait remarquable de la part de Gödel d’identifier cela dans les années 1930, alors que l’ordinateur n’existe pas encore. En fait, la naissance des premiers ordinateurs viendra en partie des travaux de Gödel, qui fut parmi les premiers à formaliser mathématiquement la notion de programme informatique et d’algorithme, sous une forme bien sûr éloignée de ce dont nous avons aujourd’hui l’habitude, mais qui est en substance la même chose.

Deuxième considération. Les axiomes de la théorie PA sont calculables par un programme informatique. Cela signifie que l’on peut écrire un programme informatique qui prend en paramètre un énoncé mathématique (sous forme de chaîne de caractères par exemple) et retourne vrai s’il s’agit d’un axiome de PA, et faux sinon. Il s’agit de quelque chose de tout à fait normal, qui est nécessairement le cas pour tous les systèmes d’axiomes utilisés par les mathématiciens : un humain devrait être capable de distinguer parmi les énoncés mathématiques quels sont ceux qui sont des axiomes, sinon comment pourrait-il faire ses démonstrations ? Le processus de réflexion utilisé par le mathématicien pour faire cette distinction peut normalement être formalisé par un algorithme. C’est le cas pour tous les systèmes d’axiomes connus et en particulier pour PA.

Troisième considération. Le système de démonstration développé durant la crise des fondements permet de vérifier mécaniquement la validité d’une preuve. On peut en particulier créer un programme informatique, qui prend en paramètre une démonstration mathématique (là encore, sous la forme d’une chaîne de caractères), et retourne vrai s’il s’agit d’une démonstration valide, et faux sinon. Notons que de tels programmes existent aujourd’hui très concrètement et sont utilisés au quotidien en recherche et en entreprise : le logiciel libre d’aide à la démonstration Coq, développé au sein d’Inria depuis les années 1980 est aujourd’hui un des plus répandus. Il en existe d’autres, comme Isabelle ou Mizar.

Notations préliminaires. Nous allons utiliser cela pour créer un énoncé mathématique impossible à démontrer ou à réfuter. L’énoncé en question va porter sur les programmes informatiques, et on considérera en particulier les programmes consistant en une unique fonction de signature :

int P(string str)

la ligne qui précède signifie que la fonction P prend en paramètre une chaîne de caractère str et retourne un entier. On parle ici de programme informatique, mais dans quel langage de programmation ? Cela n’a en fait pas d’importance, le lecteur ou la lectrice peut choisir son langage de programmation favori – C++, java, python, javascript, etc. – comme socle sur lequel appuyer son intuition pour les développements à venir. Étant donnés un tel programme P, une chaîne de caractère str et un entier i, on note P(str)↓=i pour signifier que le programme P s’arrête et renvoie i quand on l’exécute avec le paramètre str, et P(str)↑≠i pour signifier l’inverse : l’exécution de P sur l’entrée str se bloque dans une boucle infinie, ou bien s’arrête et retourne une valeur différente de i.

Nous avons en fait besoin d’étendre un peu ces deux notations : nous manipulerons nos programmes P via des chaînes de caractères les représentant. Étant donnée une chaîne de caractère P, on la confondra avec le programme qu’elle contient. Cependant les chaînes de caractères ne contiennent pas nécessairement des programmes informatiques. Si P et str sont deux chaînes de caractères, et i un entier, on notera donc P(str)↓=i pour signifier que :

• Le programme contenu dans P est bien un programme syntaxiquement correct, qui prend en paramètre une chaîne de caractère et retourne un entier. Nous dirons alors que P est valide.
• L’exécution du programme contenu dans P avec le paramètre str s’arrête et retourne \(i\).

On notera à l’inverse P(str)↑≠\(i\) pour signifier soit que P est invalide, soit que l’exécution de P sur le paramètre str se bloque dans une boucle infinie, soit s’arrête mais ne retourne pas \(i\).

Création du programme Trouve. Créons à présent un programme informatique de signature boolean Trouve(string P, string str) prenant en paramètre deux chaînes de caractères P et str. Le programme Trouve sera normalement appelé avec un paramètre P qui contiendra un programme informatique valide (P pouvant toutefois être arbitraire). Le programme Trouve(P, str) renvoie vrai s’il existe une démonstration de P(str)↓= 0 en utilisant les axiomes de PA, et renvoie faux s’il existe une démonstration de P(str)↑≠ 0 en utilisant les axiomes de PA. Voici le programme en question :

boolean Trouve(string P, string str) {
   Variable i = 0
   Répéter {
      Lister toutes les démonstrations possibles dans PA contenant au plus i Énoncés, eux-mêmes composés d’au plus i symboles les uns à la suite des autres.
      Si l’on trouve dans la liste une démonstration de P(str)↓= 0, on retourne vrai.
      Si l’on trouve dans la liste une démonstration de P(str)↑≠ 0, on retourne faux.
      i = i+1
   }
}

Rappelons qu’une démonstration est une suite d’énoncés \(F_1, \ldots F_k\). Il n’y a qu’un nombre fini d’énoncés mathématiques de taille au plus \(i\) (c’est-à-dire contenant au plus \(i\) symboles), et donc un nombre fini de démonstrations composées d’au plus \(i\) énoncés de taille au plus \(i\). Les instructions au sein de la boucle du programme ci-dessus peuvent donc se programmer, en listant toutes les possibilités – qui sont en nombre fini – et en ne retenant que celles correspondant à des démonstrations valides. Une démonstration est nécessairement finie. Donc s’il existe une démonstration de P(str)↓= 0 ou bien de P(str)↑≠ 0, le programme ci-dessus finira par la trouver (et sinon l’exécution de Trouve(P, str) ne s’arrête jamais).

L’énoncé indécidable. Nous utilisons à présent le programme Trouve au sein du programme suivant :

int Paradoxe(string str) {
   var = Trouve(str, str)
   si (var == vrai)
      Arrêter le programme et retourner 1
   sinon
      Arrêter le programme et retourner 0
}

Le programme ci-dessus peut paraître perturbant au premier abord, notamment avec l’appel de fonction Trouve(str, str), au sein duquel la première occurrence de str correspond à un programme informatique, et la deuxième au paramètre de ce programme : Trouve(str, str) va renvoyer vrai s’il trouve une démonstration de str(str)↓= 0, et faux s’il trouve une démonstration de str(str)↑≠ 0. Notons que str est une chaîne de caractères et que nous n’avons aucune garantie que celle-ci contienne un programme informatique valide. Dans ce cas, selon nos notations on aura str(str)↑≠ 0.

Nous prétendons alors que l’énoncé “Paradoxe(Paradoxe)↓= 0” est indécidable à l’aide des axiomes de PA : PA ne peut pas démontrer Paradoxe(Paradoxe)↓= 0, et PA ne peut pas non plus démontrer sa négation, c’est-à-dire Paradoxe(Paradoxe)↑≠ 0.

Preuve de l’indécidabilité. Paradoxe(Paradoxe) fait référence à l’exécution du programme Paradoxe, sur la chaîne de caractère contenant le programme Paradoxe lui-même. Notons que Paradoxe est un programme valide. Afin de montrer que “Paradoxe(Paradoxe)↓= 0” est indécidable, nous supposons au contraire que ce n’est pas le cas, afin d’arriver à une contradiction. Supposons donc que notre système PA est suffisamment puissant pour démontrer Paradoxe(Paradoxe)↓= 0 si effectivement l’exécution de Paradoxe(Paradoxe) renvoie 0, et pour démontrer Paradoxe(Paradoxe)↑≠ 0 si au contraire cette exécution ne renvoie pas 0. Notons une première chose : sous ces hypothèses, l’exécution du programme Trouve(Paradoxe, Paradoxe) s’arrête nécessairement, puisque l’on finira par trouver une preuve d’un cas ou de l’autre.

Voyons à présent d’où vient la contradiction. Il y a deux cas possibles. Supposons d’abord que l’exécution de Paradoxe(Paradoxe) renvoie 0. En examinant le programme, on voit que l’on est nécessairement arrivé dans le cas où Trouve(Paradoxe, Paradoxe) renvoie faux. Mais justement en examinant le programme Trouve, on constate que l’on est alors nécessairement dans le cas où l’on a trouvé une preuve dans PA de Paradoxe(Paradoxe)↑≠ 0. À moins que notre système PA ne démontre des choses fausses, on en déduit alors que Paradoxe(Paradoxe) ne renvoie pas 0, ce qui est une contradiction.

Supposons à présent que l’exécution de Paradoxe(Paradoxe) ne renvoie pas 0. Souvenons-nous que d’après nos hypothèses, l’exécution du programme Trouve(Paradoxe, Paradoxe) s’arrête nécessairement. Donc si l’exécution de Paradoxe(Paradoxe) ne renvoie pas 0, ça ne peut pas être parce que l’exécution de Trouve est bloquée dans une boucle infinie. Donc là encore, en examinant le programme Paradoxe, on voit que l’on est nécessairement arrivé dans le cas où Trouve(Paradoxe, Paradoxe) a renvoyé vrai. Mais justement en examinant le programme Trouve, on voit que l’on est alors nécessairement dans le cas où l’on a trouvé une preuve dans PA de Paradoxe(Paradoxe)↓= 0. Là encore, à moins que notre système PA ne démontre des choses fausses, on en déduit alors que Paradoxe(Paradoxe) renvoie 0, ce qui est également une contradiction.

On a donc dans tous les cas une contradiction. Cela signifie que notre hypothèse de départ est fausse ! Il n’existe aucune démonstration que Paradoxe(Paradoxe) renvoie 0, et aucune démonstration non plus que Paradoxe(Paradoxe) ne renvoie pas 0. Il s’agit là du premier théorème d’incomplétude de Gödel : le système d’axiomes PA ne peut ni démontrer Paradoxe(Paradoxe)↓= 0, ni démontrer Paradoxe(Paradoxe)↑≠ 0.

L’hypothèse de cohérence. Notons ce passage de notre démonstration du premier théorème d’incomplétude : “… à moins que notre système PA ne démontre des choses fausses…”. À travers cette phrase, nous nous sommes informellement encombré dans notre démonstration de l’hypothèse suivante :

ω-COH(PA) : “le système PA ne peut pas démontrer de choses fausses.”

Cette hypothèse est-elle réellement nécessaire ? Nous supposons bien entendu par défaut que les mathématiques ne peuvent pas démontrer de choses fausses… mais au fond… comment en être sûr ? N’y a-t-il pas un moyen de se débarrasser de cette hypothèse, idéalement en la démontrant ? Nous allons voir que la réponse à cette question est proprement stupéfiante, et constitue le deuxième théorème d’incomplétude de Gödel : informellement, il est impossible de démontrer mathématiquement que les mathématiques ne démontrent pas de choses fausses !

Pour cela, nous allons d’abord voir que l’on peut affaiblir un peu l’hypothèse ω-COH(PA), afin d’obtenir une version forte du premier théorème d’incomplétude, démontrée quelques années plus tard par le mathématicien américain John Barkley Rosser.

À propos de la vérité et de la cohérence

Nous avons utilisé à quelques reprises dans cet article le concept de vérité ; pourtant celui-ci relève davantage de la philosophie que des mathématiques. Souvenons-nous par exemple de l’hypothèse du continu, mentionnée dans la partie « Motivations » : “Il n’existe pas d’infini strictement compris entre celui des nombres entiers et celui des nombres réels”. Nous savons aujourd’hui que cet énoncé ne peut pas être démontré à l’aide des axiomes mathématiques usuels. Mais est-il vrai ou faux ? Il s’agit ici d’un énoncé mathématique portant sur des concepts trop éloignés de notre réalité sensible, et il n’est pas évident qu’il y ait beaucoup de sens à se prononcer sur cette question.

Le cas de l’énoncé Paradoxe(Paradoxe)↓= 0 est différent. Les programmes Trouve et Paradoxe sont des objets “concrets”, dans le sens où il est parfaitement possible de les programmer ; on peut en particulier programmer Paradoxe dans un langage de programmation quelconque (C++, java, python, etc…) et l’exécuter sur un ordinateur, avec comme paramètre la chaîne de caractère contenant notre programme Paradoxe. Nous avons vu que l’on ne peut démontrer dans PA ni que cette exécution renvoie 0, ni qu’elle ne renvoie pas 0. Mais en pratique, si on lance cette exécution, que se passera-t-il ?

L’exécution Paradoxe(Paradoxe) ne s’arrête pas. De fait étant donné que PA ne peut démontrer ni Paradoxe(Paradoxe)↓= 0 ni Paradoxe(Paradoxe)↑≠ 0, l’exécution de Trouve (Paradoxe, Paradoxe) va faire sa recherche en vain, au sein d’une boucle infinie. Voyons une autre manière de montrer que l’exécution de Paradoxe(Paradoxe) ne s’arrête pas. Si au contraire cette exécution s’arrête, elle renvoie nécessairement 0 ou 1. Supposons par exemple que Paradoxe(Paradoxe)↓= 0. Alors les successions des états de la machine à chaque étape de calcul forment un objet fini, car le programme s’arrête après un nombre fini de ces étapes. Le système PA étant constitué des axiomes permettant de parler des mathématiques finitaires, il sera alors suffisamment puissant pour démontrer Paradoxe(Paradoxe)↓= 0 : intuitivement, il suffit de retracer les états de la machine qui exécute le programme, depuis la première jusqu’à la dernière, où le programme stoppe. Donc si Paradoxe(Paradoxe)↓= 0, on peut le démontrer dans PA. Comme nous avons vu que PA ne pouvait démontrer Paradoxe(Paradoxe)↓= 0, on en déduit alors nécessairement que le programme ne renvoie pas 0 (mais qu’il est impossible de le démontrer dans le système PA). Un raisonnement similaire fonctionne pour montrer que Paradoxe(Paradoxe) ne renvoie pas 1 : si au contraire c’est le cas, alors PA démontre Paradoxe(Paradoxe)↓= 1, et donc en particulier Paradoxe(Paradoxe)↑≠ 0, puisque \(1 \neq 0\). Mais comme PA ne démontre pas Paradoxe(Paradoxe)↑≠ 0, alors le programme ne renvoie pas 1 non plus. La seule possibilité est donc que le programme ne s’arrête pas. Extrayons ici l’argument clé que nous avons utilisé de façon intuitive, et que nous réutiliserons encore un peu plus tard sous le nom de “lemme de prouvabilité de l’arrêt” :

Lemme (Lemme de prouvabilité de l’arrêt) : Pour tout programme \(P\), toute chaîne de caractère \(n\) et tout entier \(i\), si \(P(n)\)↓= \(i\), alors PA démontre \(P(n)\)↓= \(i\).

Notons que le lemme ne fonctionne que pour l’arrêt : si un programme s’arrête, PA démontre que ce programme s’arrête, mais si à l’inverse un programme ne s’arrête pas, PA ne pourra pas forcément le démontrer. C’est en particulier le cas pour Paradoxe(Paradoxe).

Les systèmes axiomatiques cohérents. Nous allons voir que nous pouvons affaiblir un peu l’hypothèse ω-COH(PA) présentée ci-dessus, afin d’appuyer nos démonstrations sur quelque chose de moins ambigu que la vérité. Nous allons utiliser à la place l’hypothèse suivante :

COH(PA) : “le système PA ne peut pas démontrer une chose et son contraire.”

Au lieu de supposer que les mathématiques ne démontrent pas des choses fausses, on suppose maintenant que les mathématiques ne peuvent démontrer une chose et son contraire. Les deux hypothèses sont similaires, sans être exactement équivalentes.

Notons qu’un système axiomatique qui peut montrer une chose et son contraire n’a aucune valeur. Outre le côté douteux d’un tel système, cela est dû au principe d’explosion qui dit que “d’une contradiction, on peut déduire n’importe quoi”. Étant donné un énoncé \(F\) quelconque, on note \( \neg F\) la négation de \(F\). L’énoncé “\(F\) et \(\neg F\)” est nécessairement toujours faux, car on ne peut avoir en même temps \(F\) et sa négation. Dès lors, pour tout énoncé \(G\), l’énoncé“\( (F\) et \(\neg F) \Rightarrow G\)” est alors logiquement toujours vrai. De ce fait, si un système d’axiome est capable de démontrer “\(F\) et \(\neg F\)”, il peut alors en utilisant le Modus Ponens, démontrer \(G\), et ce pour tout énoncé \(G\). Un système qui peut démontrer une chose et son contraire peut ainsi démontrer n’importe quoi. On dira que de tels systèmes sont contradictoires, les systèmes non-contradictoires étant quant à eux des systèmes cohérents.

Avec le principe d’explosion, on déduit qu’un système contradictoire peut démontrer des choses fausses, puisqu’il peut tout démontrer. En particulier par contraposé, un système qui ne peut démontrer des choses fausses est forcément cohérent. On a donc ω-COH(PA) implique COH(PA). Il est en revanche possible d’imaginer des systèmes qui sont cohérents, tout en étant capables de démontrer des choses fausses. Il s’agit d’une distinction subtile sur laquelle nous ne nous attarderons pas davantage. Notons seulement que le théorème originel démontré par Gödel utilisait l’hypothèse ω-COH(PA), et que cette dernière fut affaiblie quelques années plus tard par le mathématicien américain John Barkley Rosser pour obtenir le théorème dit de Gödel-Rosser :

Le théorème de Gödel-Rosser. Nous redéroulons ici avec les mêmes bases, mais de manière un peu différente la démonstration du premier théorème d’incomplétude, en utilisant l’hypothèse COH(PA) à la place de ω-COH(PA). Pour montrer que PA ne démontre pas Paradoxe(Paradoxe)↓= 0, nous supposons au contraire que PA démontre Paradoxe(Paradoxe)↓= 0 afin d’arriver à une contradiction. Voyons en détail l’utilisation de l’hypothèse COH(PA) :

(1) On suppose que PA démontre Paradoxe(Paradoxe)↓= 0.

(2) On suppose aussi COH(PA), et donc en particulier que PA ne démontre pas Paradoxe(Paradoxe)↑≠ 0.

(3) L’exécution du programme Trouve(Paradoxe, Paradoxe) va lister toutes les preuves possibles jusqu’à trouver une preuve de Paradoxe(Paradoxe)↓= 0 ou bien de Paradoxe(Paradoxe)↑≠ 0.

(3a) D’après (2) cette exécution ne trouvera jamais de preuve de Paradoxe(Paradoxe)↑≠ 0.

(3b) D’après (1) cette exécution finira par trouver une preuve de Paradoxe(Paradoxe)↓= 0.

(4) On en déduit, d’après la définition de Paradoxe, que Paradoxe(Paradoxe) finit par renvoyer 1. Donc Paradoxe(Paradoxe)↓= 1. D’après le lemme de prouvabilité de l’arrêt ci-dessus, PA démontre Paradoxe(Paradoxe)↓= 1 et donc PA démontre Paradoxe(Paradoxe)↑≠ 0, puisque \(1 \neq 0\). On a donc une contradiction.

Insistons sur le fait que (3a) est tout aussi essentiel que (3b) : sans (3a), il est possible que Trouve(Paradoxe, Paradoxe) trouve une preuve de Paradoxe(Paradoxe)↑≠ 0 avant de trouver la preuve de Paradoxe(Paradoxe)↓= 0. Dans ce cas l’exécution de Paradoxe(Paradoxe) renvoie 0, et il n’y a aucune contradiction.

Avec le même raisonnement, en supposant que PA démontre Paradoxe(Paradoxe)↑≠ 0 (et dans le même temps ne démontre pas Paradoxe(Paradoxe)↓= 0), on arrive à la conclusion que Paradoxe(Paradoxe)↓= 0 et donc d’après le lemme de prouvabilité de l’arrêt, que PA démontre Paradoxe(Paradoxe)↓= 0, ce qui est aussi une contradiction.

Le deuxième théorème d’incomplétude

Nous avons vu dans la section précédente que l’exécution de Paradoxe(Paradoxe) ne s’arrête pas. L’énoncé Paradoxe(Paradoxe)↑≠ 0 est donc vrai, mais indémontrable. Cela a de quoi laisser dubitatif. Quand on affirme que l’énoncé Paradoxe(Paradoxe)↑≠ 0 est vrai, ce n’est pas arbitraire, mais bien le résultat d’un raisonnement logique. Ce raisonnement logique ne consiste-t-il pas justement en une démonstration de Paradoxe(Paradoxe)↑≠ 0, et n’y a-t-il pas là une contradiction avec la preuve donnée précédemment que PA ne peut démontrer Paradoxe(Paradoxe)↑≠ 0 ? Nous allons voir que non. Le raisonnement qui nous conduit à dire que l’énoncé Paradoxe(Paradoxe)↑≠ 0 est vrai, est effectivement une démonstration mathématique valide, mais rappelons-le, sa formalisation précise nécessite l’hypothèse COH(PA). La conséquence de cette constatation est le deuxième théorème d’incomplétude de Gödel : si COH(PA) est vrai, c’est-à-dire si le système d’axiomes PA est bien exempt de contradiction, alors ce système ne peut pas démontrer lui-même son absence de contradiction.

Pour résumer :

Notons assez ironiquement que si COH(PA) est faux, alors par le principe d’explosion, PA peut démontrer n’importe quoi, et en particulier COH(PA). Une telle démonstration (comme toute autre démonstration dans un tel système) n’aura toutefois aucune valeur. Il est donc capital que COH(PA) soit vrai. Ce que dit le second théorème d’incomplétude de Gödel, c’est en quelque sorte justement que l’on n’en sait rien, et même qu’il est impossible de le savoir. En particulier dans le cas de la cohérence de PA, ce système est impuissant à démontrer sa propre cohérence.

Le deuxième théorème d’incomplétude. Efforçons-nous dans ce dernier paragraphe d’expliciter les grandes lignes de la preuve :

(1) Nous avons montré que sous l’hypothèse COH(PA), PA ne démontre pas Paradoxe(Paradoxe)↑≠ 0 (et ne démontre pas non plus Paradoxe(Paradoxe)↓= 0).

(2) Nous avons aussi explicité le lemme de prouvabilité de l’arrêt : si Paradoxe(Paradoxe) renvoie 0, alors PA démontre Paradoxe(Paradoxe)↓= 0. En utilisant le principe de raisonnement par contraposé, on en déduit alors que si PA ne démontre pas Paradoxe(Paradoxe)↓= 0, cela implique que Paradoxe(Paradoxe) ne renvoie pas 0. Et justement d’après (1), si l’on se place sous l’hypothèse COH(PA), alors PA ne démontre pas Paradoxe(Paradoxe)↓= 0. Nous en déduisons donc que Paradoxe(Paradoxe) ne renvoie pas 0. En résumé, on a donc COH(PA) implique Paradoxe(Paradoxe)↑≠ 0.

(3) Il faut ensuite établir – mais les détails de cette étape nous emmèneraient trop loin – que notre argumentation pour arriver à “COH(PA) implique Paradoxe(Paradoxe)↑≠ 0”, peut être formalisée dans le système PA lui-même. En particulier PA démontre que COH(PA) implique Paradoxe(Paradoxe)↑≠ 0.

(4) De ce fait, si de plus PA démontre COH(PA), alors en utilisant le Modus Ponens, on arrive à la conclusion que PA démontre Paradoxe(Paradoxe)↑≠ 0, rappelons alors (1) : sous l’hypothèse COH(PA), PA ne démontre pas Paradoxe(Paradoxe)↑≠ 0. Nous avons donc, sous l’hypothèse COH(PA), à la fois que PA démontre Paradoxe(Paradoxe)↑≠ 0, et à la fois que PA ne démontre pas Paradoxe(Paradoxe)↑≠ 0.

On arrive à une contradiction. L’hypothèse COH(PA) n’est donc pas démontrable dans PA (à condition que PA soit effectivement exempt de contradiction…)

Conclusion

Ce deuxième théorème d’incomplétude est aussi exceptionnel qu’inattendu. Rappelons l’objectif d’Hilbert, qui était de partir d’un système d’axiomes “sûr”, capturant les mathématiques finitaires, afin de montrer l’ensemble des théorèmes mathématiques. Mais qu’est-ce qu’un système “sûr” ? C’est un système ne contenant que des axiomes qui ne laissent pas place au doute, mais c’est aussi un système cohérent, qui ne permet justement pas de démontrer une chose et son contraire ! Hilbert avait aussi pour ambition de démontrer que le système PA des mathématiques finitaires est cohérent. Gödel a d’abord démontré que si c’est bien le cas, alors PA est impuissant à montrer ou réfuter certains énoncés des mathématiques finitaires, l’exemple étant l’énoncé Paradoxe(Paradoxe)↑≠ 0. Gödel a enfin démontré que le système d’axiomes PA est incapable de démontrer sa propre cohérence.

On peut bien entendu considérer des systèmes axiomatiques plus puissants, qui sont capables de démontrer la cohérence de PA. En particulier le système ZFC, permettant de faire des mathématiques infinitaires, permet de montrer COH(PA). Cependant, comment savoir si ZFC lui-même ne peut démontrer une chose et son contraire ? En fait, les raisonnements que nous avons menés peuvent se faire avec n’importe quel système d’axiomes T, à condition que :

• T soit suffisamment puissant pour formaliser la notion de programmes informatiques.
• Les axiomes de T soient calculables par programme informatique (il existe un processus algorithmique permettant de distinguer les énoncés de T des autres).
• Et bien sûr, à condition que T soit un système cohérent.

Si ces trois conditions sont vérifiées, alors T ne peut pas démontrer sa propre cohérence. Le système d’axiomes ZFC est bien calculable, et tombe donc lui aussi sous la coupe du théorème de Gödel, à condition qu’il soit cohérent bien sûr, mais nous ne pourrons jamais démontrer si c’est bien le cas…

L’impact épistémologique des théorèmes de Gödel est considérable. Les mathématiques, mère des sciences exactes, sont non seulement tributaires d’une croyance (à savoir la cohérence des axiomes utilisés), mais sont en plus capables de démontrer qu’il en sera toujours ainsi !