Théorème d'incomplétude de Gödel

Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (en) « Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »).

Ces théorèmes ont trait aux mathématiques. Énoncé de façon certes approximative, le premier dit essentiellement qu'une théorie suffisante pour faire de l'arithmétique est nécessairement incomplète, au sens où il existe dans cette théorie des énoncés qui ne sont pas démontrables et dont la négation n'est pas non plus démontrable : c'est-à-dire qu'il existe des énoncés que l'on ne pourra jamais déterminer en restant dans le cadre de la théorie. Sous le même genre d'hypothèses sur les théories considérées, le second théorème affirme 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é ne peut pas être démontré dans la théorie elle-même. À cause des hypothèses des théorèmes, toute théorie qui prétend formaliser l'ensemble des mathématiques, comme la théorie des ensembles, est concernée. Faut-il pour autant renoncer à ce qu'un discours mathématique ait une valeur de vérité universelle ? Sur quoi se fonder pour savoir s'il est cohérent, puisqu'il semble que l'on ne puisse y arriver par des moyens purement internes aux mathématiques ? Les théorèmes de Gödel ne donnent pas de réponse mais permettent d'écarter celles qui sont trop simples. Il faut déjà noter que ces deux limitations (énoncés dont la vérité est inaccessible, cohérence du discours) sont seulement relatives.

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 David 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 donna la première démonstration détaillée du second théorème1 dans l'ouvrage Grundlagen der Mathematik (en), (co-signé avec Hilbert). Enfin, Gödel se rendit plusieurs fois aux États-Unis dans les années 1930. Ses travaux eurent une grande audience auprès d'Alonzo Church et de ses élèves, Stephen Cole Kleene et J. Barkley Rosser (en), et jouèrent un rôle important dans la naissance de la théorie de la calculabilité.

Le second problème de la célèbre liste que Hilbert présenta en 1900 à Paris était celui de la démonstration de la cohérence de l'arithmétique. Toute la question, qui n'est pas éludée par Hilbert, est de savoir quels moyens on se donne pour une telle preuve. Le second théorème d'incomplétude montre qu'il faut une théorie « plus forte » (en un sens qu'il faudrait préciser) que l'arithmétique elle-même. On considère généralement que la réponse apportée au second problème de Hilbert est négative. Gerhard Gentzen donna cependant en 1936 une preuve de cohérence de l'arithmétique, de façon compatible bien sûr avec le second théorème de Gödel. La preuve est fort intéressante, mais sa signification en tant que preuve de cohérence reste discutable (voir les articles sur Gentzen et sur le programme de Hilbert). Ce dernier article est plus détaillé sur le contexte historique qui a conduit Gödel à démontrer ses théorèmes et l'impact de ceux-ci à l'époque.

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. Une présentation légèrement informelle commence l'article. Des esquisses des preuves des théorèmes, ainsi que des précisions sur leurs énoncés, sont données en fin.