Les théorèmes d'incomplétude de Gödel

Au congrès international des mathématiciens de 1900, David Hilbert proposa vingt-trois problèmes qui structurèrent les travaux mathématiques du XX^e siècle. Pour conforter son idée axiomatique, il proposa de « démontrer la consistance de l’arithmétique de Peano », c’est-à-dire qu’à partir des axiomes de l’arithmétique et des règles de déduction formelles, on ne peut avoir à la fois une assertion et son contraire. Il s’agit de bon sens direz-vous, « 2 + 2 = 5 » ou non ! Pourtant, personne ne l’avait démontré dans cette généralité avant que Hilbert pose ce problème… et Kurt Gödel prouva trente ans plus tard que c’était faux !

En réalité, le logicien autrichien démontra bien plus : dans tout système axiomatique contenant l’axiomatique de Peano, il existe des assertions dont on ne peut prouver ni la vérité ni la fausseté. Les mathématiciens le savaient déjà dans le cas de la géométrie. Le postulat des parallèles est improuvable dans le cadre des axiomes de la géométrie d’Euclide excluant le postulat. Il s’agit d’un axiome qui s’exprime de la façon suivante de nos jours : « Un point A et une droite D étant donnés, il passe par A une et une seule droite parallèle à D. »

En le remplaçant par un axiome niant l’existence de parallèles, on obtient une autre géométrie, la géométrie sphérique. En le remplaçant par un axiome affirmant l’existence de plusieurs parallèles, on obtient la géométrie hyperbolique.

Des assertions improuvables

En tenant compte du temps et de l’énergie qui nous sont alloués, il est facile de démontrer qu’il existe des assertions dont il est humainement impossible de prouver la vérité ou la fausseté. On dit que de telles assertions sont indécidables. Pour cela, il suffit de considérer la notion de longueur d’une preuve. Comme il existe une infinité d’assertions prouvables (par exemple les assertions du type « le nombre n est premier ») et que leurs preuves sont distinctes, il en existe d’aussi longues que l’on veut. On peut considérer qu’au-delà d’une certaine longueur (10¹⁰⁰ par exemple, ce qui représente plus que le nombre d’électrons dans l’univers), une preuve est humainement inaccessible, même avec l’aide d’un puissant ordinateur. Cela n’est que bon sens, mais Gödel affirme bien plus que cela. L’arithmétique (avec les axiomes de Peano) contient des assertions indécidables… et il en exhibe. L’exemple donné en encadré peut faire penser que le problème tient à ce que l’on a « oublié » un axiome (ici celui du choix) dans l’arithmétique de Peano. Vous pouvez l’ajouter : il existera d’autres assertions improuvables dans ce nouveau système (par le théorème de Gödel), et ainsi de suite. L’ajout de nouveaux axiomes ne permet en aucun cas de contourner le résultat de Gödel.

Le surprenant résultat de Gödel justifie que l’on puisse se poser la question suivante : une conjecture comme celle de Goldbach est-elle prouvable ? Ou est-elle simplement non prouvable avec les axiomes donnés (voir FOCUS) ? Faut-il alors l’ajouter comme nouvel axiome ? Pour mémoire, la conjecture de Goldbach date de 1742 et a été remodelée par Leonhard Euler, à qui elle a résisté, comme à tous les mathématiciens depuis. Sa simplicité apparente ajoute à la fascination qu’elle exerce : tout nombre pair (à partir de 4) est somme de deux nombres premiers. Ce résultat est facile à vérifier pour de petits nombres :

4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = 5 + 7… 98 = 19 + 79… 1 000 = 17 + 983… 

389 965 026 819 938 = 5 569 + 389 965 026 814 369…

Mais cela ne suffit pas pour le démontrer !

Même si l’on démontrait que la conjecture de Goldbach est improuvable dans l’arithmétique de Peano, on imagine mal donner à cette conjecture le statut d’axiome. À l’opposé du postulat d’Euclide, il manquerait singulièrement de naturel. Quel intérêt y aurait-il à choisir des axiomes de ce type ? Quelles applications pourrait-on en attendre ?

[encadre]

Une assertion improuvable sans l'axiome du choix

Pour donner un exemple un peu naturel d’une assertion vraie avec l’axiome du choix mais non prouvable avec les seuls axiomes de Peano, on a besoin de quelques définitions. Soient k un entier et E une partie finie de  \( \mathbb{N}\)  ayant plus de k éléments. Considérons E_k l’ensemble des parties à k éléments de E.

Soit r un entier (le « nombre de couleurs disponibles »). Intéressons-nous aux coloriages à r couleurs de E_k , c’est-à-dire aux applications f de E_k dans l’ensemble {1, 2, ..., r} des couleurs (ou plutôt de leurs numéros). Si P est une partie à k éléments de E, f (P) est appelée sa couleur.

Enfin, une sous-partie F de E est dite monochrome (pour un coloriage f ) si toutes les parties à k éléments de F ont la même couleur. Ces définitions faites, formulons l’assertion en question :

Pour tout couple (k, r) d’entiers, il existe un entier n tel que, pour tout coloriage à r couleurs de l’ensemble des parties à k éléments de {k + 1, k + 2… n}, il existe une partie monochrome de {k + 1, k + 2… n} dont le plus petit élément (k + 1) est strictement inférieur au nombre d’éléments (n – k).

Cette assertion peut être prouvée en utilisant l’axiome du choix. On démontre par contre qu’elle ne peut être prouvée avec les seuls axiomes de Peano. L’axiome du choix étant communément admis en mathématiques, notre assertion est considérée comme vraie mais est improuvable dans l’arithmétique de Peano.

 [/encadre]

De la vertu des menteurs

Le problème fondamental derrière le théorème de Gödel est celui de l’autoréférence : un système formel suffisamment riche ne peut démontrer sa propre cohérence. La démonstration par Gödel de son théorème est d’ailleurs une amélioration du raisonnement fallacieux suivant dû à un logicien français du nom de Richard. Les assertions sur les entiers peuvent être ordonnées suivant l’ordre lexicographique. Imaginons donc qu’elles soient toutes écrites dans cet ordre. Soit A_n l’assertion portant le numéro n. Appelons richardiens les nombres n ne vérifiant pas A_n. Cela a un sens puisque A_n est une assertion qu’un entier peut vérifier ou non (et pourquoi pas l’entier n ?). « Être richardien » est lui-même une assertion. Elle porte donc un numéro, soit m. Ce nombre m est-il richardien ?

Si m est richardien, alors, par définition, il ne vérifie pas A_m et donc il n’est pas richardien. Si m n’est pas richardien, alors il vérifie A_m, donc il est richardien. On retrouve le paradoxe du menteur affirmant « je mens ». S’il dit la vérité, il ment et s’il ment, il dit la vérité.

Le côté fallacieux du raisonnement de Richard tient à l’autoréférence. Plus précisément, « être richardien » n’est pas une assertion de la liste de propriétés envisagées puisque sa définition suppose la construction préalable de cette liste. L’idée de Gödel est la même mais il réussit à écrire effectivement et explicitement un énoncé arithmétique signifiant « cet énoncé est indémontrable ». Le rêve de Hilbert s’écroule : tous les résultats vrais d’une théorie ne sont pas prouvables à partir des seuls axiomes de cette théorie et du raisonnement logique. Par contre, la porte s’ouvre sur la logique moderne et ses richesses !