$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Fondements > Logique >

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

  L'un des buts de Hilbert, au début du XXè s., était de créer des théories mathématiques formelles, c'est-à-dire avoir :
  • un ensemble de règles qui permettent d'écrire des formules.
  • un ensemble d'axiomes, c'est-à-dire de formules vraies (à comprendre : que l'on pose comme vraies).
  • un ensemble de règles d'inférence, c'est-à-dire de moyens de tranformer une formule en une autre, de sorte que l'on puisse à partir de théorèmes ou d'axiomes en déduire de nouveaux.
  Tout cela devait être assez précis pour qu'un automate puisse réaliser les déductions mécaniquement. L'idée d'Hilbert était que les mathématiciens ne se laissent plus aveugler par leur intuition. Par exemple, en géométrie, il est tentant de se conforter à l'observation, et le 5ème axiome d'Euclide : " Par un point, il passe une parallèle à une autre droite et une seule" semble évident. Pourtant, au cours du XIXè s., Lobachevsky notamment a réussi à construire des géométries ne respectant pas cet axiome.

  Un système formel (au sens précédent) est dit consistant si on ne peut pas démontrer une formule et son contraire. Il est dit complet si pour toute formule du système formel, il existe un processus de transformation qui permet de prouver qu'elle est vraie ou fausse.

Théorème : (incomplétude de Gödel)
  1. Tout système formel consistant, et susceptible de formaliser en son sein l'arithmétique des entiers, est incomplet.
  2. Aucun système formel consistant, et capable de définir l'arithmétique des entiers, ne peut prouver sa propre consistance.

  La première partie du théorème de Gödél dit qu'en particulier, il existe des énoncés sur les entiers dont on ne sait pas démontrer, à partir des seuls axiomes de la logique construisant les entiers, s'ils sont vrais ou s'ils sont faux. Par exemple, jusqu'à un passé récent, personne n'avait réussi à démontrer la conjecture de Fermat. Celle-ci stipule que pour tout entier n supérieur à 2, il n'existe aucun triplet d'entiers x,y,z tels que :
xn+yn = zn.
Alors que pour n=2, il existe des valeurs évidentes de x,y,z, par exemple (3,4,5), les mathématiciens ont eu beau chercher, ils ne trouvaient aucune solution à l'équation pour n>2. Ils ont donc cherché à démontrer qu'il n'y avait aucune solution, certains y ont même passé leur vie, sans résultat. Or, précisément, d'après le théorème de Gödel, il était possible que cette conjecture soit vraie mais indémontrable, autrement dit, que ce soit un axiome à rajouter à l'arithmétique des entiers. Beaucoup de mathématiciens ont alors abandonné leurs travaux … jusqu'à ce que Andrew Wiles, en 1995 parvienne enfin à démontrer la véracité de cette conjecture. L'axiome était en réalité un théorème ! C'est dans la théorie classique des ensembles qu'on peut trouver des exemples concrets de propositions indécidables, par exemple l'axiome du choix ou l'hypothèse du continu.

  La deuxième partie du théorème donne elle une réponse au 2ème des 23 problèmes qu'Hilbert avait énoncés en 1900 : peut-on prouver la consistance de l'arithmétique en utilisant seulement les axiomes de l'arithmétique?

Cette entrée du dictionnaire a été rédigée avec l'aide du professeur Jean-Marc Salotti.
Consulter aussi...