Utilisateur:Proz/Gödel

Brouillon repris très partiellement dans théorème d'incomplétude, et pour la seconde partie dans programme de Hilbert

Introduction

Les théorèmes de Gödel traitent des théories mathématiques, de leur axiomatisation, et des conséquences de ces axiomes. Le premier théorème énonce que, sous des hypothèses raisonnables pour les théories mathématiques usuelles, une théorie suffisante pour faire de l'arithmétique est nécessairement incomplète, au sens où il existe forcément des énoncés qui ne sont pas démontrables et dont la négation n'est pas non plus démontrable. Le second théorème affirme, toujours sous le même genre d'hypothèses, qu'il existe un énoncé exprimant la cohérence de la théorie -- le fait qu'elle ne permette pas de démontrer tout et donc n'importe quoi -- et que cet énoncé n'est pas démontrable dans la théorie elle-même. Dit de façon équivalente mais peut-être plus percutante, si on démontre la cohérence d'une théorie de l'arithmétique dans elle-même, c'est que celle-ci est incohérente.

Ces théorèmes, et surtout leurs conséquences sur la conception de leur discipline qu'avaient les mathématiciens de l'époque, en particulier Hilbert et ses élèves, étaient très inattendus. Peu de mathématiciens comprirent tout d'abord ces théorèmes et ce qu'ils impliquaient. Il faut compter parmi ceux-ci John Von Neumann, qui après avoir assisté au premier exposé de Gödel en 1930 sur le premier théorème d'incomplétude, lui envoya une lettre mentionnant un corollaire qui était le second théorème (que Gödel connaissait déjà). Paul Bernays également, proche collaborateur de David Hilbert, comprit très vite les conséquences de ces théorèmes sur les conceptions de ce dernier, et le premier donna une démonstration détaillée du second théorème dans l'ouvrage Grundlagen der Mathematik, (co-écrit avec Hilbert). Enfin, Gödel se rendit plusieurs fois aux Etats-Unis dans les années 30. Ses travaux eurent une grande audience auprès d'Alonzo Church et de ses élèves, Stephen Cole Kleene et John Barkley Rosser, et jouèrent un rôle important dans la naissance de la théorie de la calculabilité.

Le programme de Hilbert

Pour comprendre l'impact des théorèmes de Gödel sur les recherches concernant les fondements des mathématiques, il faut dire quelques mots des conceptions scientifiques de Hilbert, car elles avaient une grande influence sur les mathématiciens de l'époque. Hilbert s'opposait fermement au pessismisme scientifique prôné en particulier par le physiologiste Emil du Bois-Reymond, pour qui il est des questions en sciences qui resteront toujours sans réponse, une doctrine connue sous le nom d'« Ignorabimus », du latin ignoramus et ignorabimus : nous ne savons pas et nous ne saurons jamais. Pour Hilbert, « il n'y a pas d'Ignorabimus en mathématiques », « Wir müssen wissen. Wir werden wissen », « Nous devons savoir. Nous saurons », déclare-t-il en 1930 dans une allocution radio-diffusée restée célèbre.

La découverte de paradoxes dans les théories proposées par Cantor et Frege pour les fondements des mathématiques avait ébranlé la confiance en ceux-ci. Certes, on avait de nouvelles théories des ensembles qui étaient exemptes des paradoxes connus, mais comment s'assurer qu'on n'en trouverait pas de nouveaux ? Hilbert s'opposait également violemment à l'intuitionnisme du mathématicien néerlandais Brouwer, que promouvait ce dernier pour résoudre la crise des fondements, et qui est une remise en cause radicale de ceux-ci. Brouwer jugeait que le tiers-exclu, un principe logique qui affirme qu'une proposition est soit vraie soit fausse, s'il repose sur une intuition solide quand on manipule le fini, ne peut être un principe du raisonnement, dès que l'on manipule l'infini. Une preuve d'existence doit être effective. Il ne suffit pas, pour montrer telle proposition, de montrer que sa négation entraînerait une contradiction. Cette position, cohérente sur le plan des idées, et qui séduisit des mathématiciens de valeur - outre Brouwer lui-même, Hermann Weyl pendant un temps - a pour principal défaut, de remettre en cause des pans entiers des mathématiques.

Pour régler la question des fondements de façon définitive, Hilbert conçut un programme dont il avait établi les prémisses en 1900 dans l'introduction à sa célèbre liste de problèmes, le second problème étant justement celui de la cohérence de l'arithmétique. Il développa ensuite ce programme dans les années 1920, avec ses collaborateurs, parmi lesquels Paul Bernays et Wilhelm Ackermann. L'idée est grossièrement la suivante.

Tant que l'on manipule le fini, les mathématiques sont sûres. L'arithmétique élémentaire (en un sens qui doit se préciser) est sûre. Pour justifier l'utilisation d'objets abstraits ou idéaux, en particulier infinis, il suffit de montrer que la théorie qui les utilise est cohérente, mais bien sûr cette cohérence doit elle-même être démontrée par des moyens finitaires. On peut alors affirmer l'existence de ces objets. Cette approche est ce que l'on a appelé le formalisme.

Le théorème de complétude démontré par Gödel dans sa thèse en 1929, indique, sommairement, que l'on ne pourra trouver de nouveaux principes de raisonnement purement logiques autres que ceux déjà connus. Cela semble aller dans le sens de Hilbert.

Mais, même si Hilbert n'a pas explicitement formalisé le système des mathématiques finitaires, ce dernier contient une théorie de l'arithmétique pour laquelle Gödel a pu démontrer les théorèmes d'incomplétude. Le second théorème montre que l'on ne pourra pas prouver dans cette théorie sa propre cohérence, et donc certainement pas celle de théories plus fortes qui assureraient la fondation des mathématiques. C'est donc l'échec du programme de Hilbert. Il est d'ailleurs probable que Gödel, motivé par le programme de Hilbert, avait tout d'abord voulu prouvé la cohérence de l'arithmétique.

John von Neumann avoua plus tard qu'il n'avait jamais imaginé à l'époque que cet échec fût possible. Il en tira une grande admiration pour Gödel ... et abandonna à peu près toute recherche sur les fondements des mathématiques.

Si les conséquences des théorèmes de Gödel sur le programme de Hilbert sont peu contestées, il n'en est pas de même en ce qui concerne sa position sur «  l'ignorabimus ». Le théorème de Gödel dit qu'il y a des énoncés que l'on ne saura ni démontrer ni réfuter dans une théorie donnée, pas en mathématiques en général. Tout au plus permet-il d'écarter des réponses trop simples, qui ne tiendraient pas compte du caractère dynamique des mathématiques, des ses rapports aux autres sciences, physique et maintenant peut-être informatique, enfin qui de façon générale évacuent trop facilement la question du sens des mathématiques.

L'intuitionnisme, que le théorème de Gödel ne remet pas en cause, n'a pas pour autant gagné la partie. Il est resté très minoritaire en mathématiques, et doit son renouveau depuis les années 1970 au développement de l'informatique (voir isomorphisme de Curry-Howard), et à une vision devenue souvent moins critique des mathématiques classiques, qu'il pourrait servir à mieux comprendre.

Les preuves de cohérence

Il y eut des tentatives pour remédier à l'échec du programme de Hilbert en précisant et en étendant la notion de méthode finitaire, même si, d'après le second théorème de Gödel, on ne peut espérer définir une fois pour toutes une théorie mathématique raisonnable pour de telles méthodes finitaires. Ainsi Gentzen a prouvé en 1936 la cohérence de l'arithmétique de Peano en utilisant un principe de récurrence transfini (jusqu'à l'ordinal dénombrable ε₀), donc plus fort que le principe de récurrence de l'arithmétique de Peano, mais utilisée de façon plus immédiate. Cette preuve développe des outils qui se sont révélés fondamentaux en théorie de la démonstration. Elle reste bien sûr une preuve de cohérence relative. On l'interprètera plus volontiers aujourd'hui comme une façon de mesurer la « force » de l'arithmétique de Peano (par un ordinal).

La suite de l'article ne cherche pas à suivre exactement le contenu de l'article de Gödel. Quelques points se sont précisés depuis. On commence par une présentation encore un peu informelle. Des esquisses des preuves des théorèmes, ainsi que des précisions sur leurs énoncés, sont donnés en fin d'article.