Les indécidables
Sémantique
Logique
Infini
Mesure
Probas
Nombres
Physique
Nous parlons ici de pseudoparadoxes, càd de situations contraires à l'intuition sinon choquantes, mais où aucune contradiction interne ne doit être résolue.
Dans un système formel, on étudie une théorie en se basant sur un certain nombre d'axiomes. On dispose de règles de démonstration qui permettent d'en déduire des théorèmes. Tout ceci peut avoir lieu -- du moins, théoriquement -- dans un langage formalisé dont le contenu est parfaitement contrôlé. Seules certaines formules, écrites selon les règles précises du calcul propositionnel, sont valides. On espère que la théorie construite est consistante, càd qu'il n'existe aucune formule F qui soit un théorème en même temps que non F (car alors, toute formule serait un théorème).
Il serait aussi souhaitable que pour toute formule F, F ou non F soit un théorème. La théorie serait alors complète. Dans un tel système, tous les théorèmes s'obtiendraient par application méthodique des règles de démonstration. Cette conviction formaliste était fortement ancrée au début du XXème siècle. Le programme de Hilbert initié en 1928 par le célèbre mathématicien se donnait pour objectif déterminer en un nombre fini d'étapes si une formule valide était un théorème. Les premier résultats de logique semblaient encourageants.
Mais en 1930, le logicien Kurt Gödel publie un obscur article fort judicieusement intitulé Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme [1]. Il y démontre son premier théorème d'incomplétude au sujet des systèmes formels suffisamment puissants pour engendrer l'arithmétique de Peano (ce qui est le cas de la théorie des ensembles). Le théorème énonce que dans ces systèmes, il est possible d'écrire des formules valides qui ne sont pas des théorèmes, non plus que leur négation (de telles formules sont appelées indécidables). Autrement dit, un tel système est nécessairement incomplet.
Pour sa démonstration, Gödel associe astucieusement à chaque formule un nombre entier qui l'identifie complètement. Il transforme ainsi les démonstrations du système en calculs arithmétiques. Puis, de façon très technique et rigoureuse, il met en place une formule G valide qui signifie "G n'est pas démontrable''. C'est en quelque sorte le paradoxe d'Epimenide qui se trouve transporté au coeur de la démonstration de Gödel (à une différence près : la formule G est en fait un nombre ; il n'est pas question de remettre en cause son existence en arguant de l'imprécision du langage courant). C'en était fini du rêve formaliste d'Hilbert et de ses contemporains.
L'année suivante, Gödel enfonçait le clou. Parmi les indécidables d'un système donné figure précisément la formule qui affirme la consistance du système lui-même. Il est possible de l'énoncer dans le système, mais pas de l'y démontrer, ni de l'infirmer. Donc, dès qu'une théorie est assez puissante (pour fonder l'arithmétique), elle est incapable de prouver qu'elle est elle-même exempte de contradictions.
Note
[1] Les Principia Mathematica, de B. Rusell et A. Whitehead, étaient le traité de logique qui faisait autorité à l'époque.