Un énoncé est une suite de symboles, une démonstration une suite d’énoncés, une théorie un ensemble d’axiomes. On peut donc les compter, les coder, les comparer à des structures… et démontrer des théorèmes sur eux.
« En logique mathématique, les énoncés et les théories deviennent des objets mathématiques à part entière. On leur applique des théorèmes rigoureux : complétude de Gödel (1929), tout énoncé logiquement valide est démontrable ; incomplétude de Gödel (1931), dans tout système formel cohérent capable de faire de l’arithmétique, il existe des énoncés vrais mais indémontrables ; théorie des modèles, étude des structures mathématiques qui satisfont un ensemble donné d’axiomes. »
Tout repose sur la distinction entre deux mondes. La syntaxe : les suites de symboles et les règles qui permettent d’en déduire d’autres ; on y parle de démontrable. La sémantique : les structures (ensembles munis d’opérations) dans lesquelles un énoncé est vrai ou faux ; on y parle de valide (vrai dans toutes les structures) et de modèle (structure où tous les axiomes sont vrais). La métamathématique étudie les ponts entre les deux.
Pour la logique du premier ordre (quantificateurs sur des éléments), le pont est parfait : valide ⟹ démontrable. Ce qui est vrai partout a une preuve ; ce qui n’a pas de preuve a un contre-modèle. Planche 2.
Mais pour une théorie particulière, comme l’arithmétique, le pont vers la structure visée (les entiers ℕ) est rompu : certains énoncés vrais dans ℕ ne sont pas démontrables. Planches 1, 3 et 4.
On étudie pour elles-mêmes les structures qui satisfont des axiomes donnés : combien y en a-t-il, en quoi diffèrent-elles, quels énoncés les séparent. Planche 5.
Il n’y a pas de contradiction entre les deux théorèmes de Gödel : un énoncé indécidable de l’arithmétique est vrai dans ℕ mais faux dans un autre modèle des axiomes. Il n’est donc pas valide, et la complétude ne lui promet aucune preuve.
Première étape de Gödel : transformer chaque énoncé de l’arithmétique en un entier, de façon à ce que les questions sur les énoncés deviennent des questions sur les entiers. On donne un numéro à chacun des 13 symboles ; un énoncé s₁s₂…sk reçoit le nombre de Gödel 2code(s₁) × 3code(s₂) × 5code(s₃) × …, les nombres premiers successifs portant les symboles successifs. Comme la décomposition en facteurs premiers est unique, on retrouve l’énoncé à partir du nombre.
Que tel entier soit le code d’une formule se vérifie par un calcul fini : factoriser, lire les exposants, contrôler la grammaire. C’est donc une propriété arithmétique, au même titre que « être premier ». Gödel montre qu’il en va de même pour « être le code d’une démonstration de telle formule ». La théorie peut alors parler, à travers les nombres, de ses propres démonstrations.
Une formule est valide si elle est vraie dans toutes les situations (ici, les 8 valuations de P, Q, R). La méthode des tableaux (Beth, Hintikka, Smullyan) cherche méthodiquement une situation où la formule serait fausse : on suppose sa négation et on la décompose. Si toutes les branches aboutissent à une contradiction (un énoncé et son contraire), la recherche a échoué partout : l’arbre fermé est une démonstration. Sinon, une branche ouverte fournit un contre-modèle.
Le cœur de la preuve de Gödel est une phrase qui dit « je ne suis pas démontrable ». Une phrase ne peut pas contenir sa propre citation (elle serait plus longue qu’elle-même) ; l’astuce consiste à décrire une opération qui la fabrique. Voici la version en français due à Quine : l’opération « faire précéder un texte de sa propre citation ». Appliquez-la au texte entre guillemets : vous obtenez la phrase entière.
Une « quine » est un programme qui produit son propre texte. Elle suit exactement le même schéma : un gabarit a, et l’instruction « remplace le trou @ de a par la citation de a ».
(sortie)
Soit F un système formel qui fait de l’arithmétique, et G la phrase de Gödel de F, qui affirme « G n’est pas démontrable dans F ». Trois questions à deux réponses : F démontre-t-il G ? démontre-t-il non-G ? G est-elle vraie ? La machine essaie les 8 combinaisons et élimine celles qui contredisent les hypothèses choisies.
L’énoncé « F est cohérent » s’écrit aussi en arithmétique : « aucun entier n’est le code d’une démonstration de 0 = S0 ». Gödel montre que F démontre « si F est cohérent, alors G ». Si F démontrait sa propre cohérence, il démontrerait donc G, ce que l’on vient d’exclure. Un système cohérent qui fait de l’arithmétique ne peut pas démontrer sa propre cohérence.
G a la même forme que la conjecture de Goldbach, « tout nombre pair ⩾ 4 est somme de deux nombres premiers » : un « pour tout n » suivi d’une propriété que l’on vérifie par un calcul fini. Pour un tel énoncé, un contre-exemple serait démontrable (il suffirait d’écrire le calcul). Donc, s’il était indémontrable dans l’arithmétique de Peano, il n’aurait pas de contre-exemple : il serait vrai. Personne ne sait aujourd’hui si Goldbach est démontrable ; la machine vérifie seulement les cas un par un.
Un modèle d’un ensemble d’axiomes est une structure concrète qui les vérifie tous. Les axiomes de groupe (une loi associative, un neutre e, un symétrique pour chaque élément) ont une multitude de modèles, qui ne se ressemblent pas ; d’autres axiomes, au contraire, n’admettent au fond qu’un seul modèle d’une taille donnée. La machine cherche elle-même tous les modèles.
Pour n éléments {0, 1, …, n − 1} avec 0 comme neutre, la machine remplit les tables de multiplication case par case, en rejetant tout choix qui viole l’associativité ou fait apparaître deux fois le même élément dans une ligne ou une colonne. Elle classe ensuite les tables trouvées : deux tables décrivent « le même » groupe (sont isomorphes) si l’on passe de l’une à l’autre en renommant les éléments.
Les cinq groupes d’ordre 8 vérifient tous les axiomes de groupe. Un énoncé écrit dans le langage des groupes y est vrai ou faux selon le modèle. S’il est vrai dans tous, il est une conséquence des axiomes (et du fait qu’il y a 8 éléments) ; s’il est vrai dans certains et faux dans d’autres, les axiomes ne le décident pas.
Axiomes d’un ordre dense sans extrémités : un ordre total, entre deux éléments il y en a toujours un troisième, pas de plus petit ni de plus grand élément. Deux modèles dénombrables très différents d’allure : les fractions dyadiques k/2m de ]0 ; 1[ (en haut) et toutes les fractions de ]0 ; 1[ (en bas). Cantor a démontré en 1895 que deux tels ordres dénombrables sont toujours isomorphes. La méthode du va-et-vient (Huntington, Hausdorff) construit l’isomorphisme en alternant : on prend le premier élément non apparié d’en haut et on lui trouve une image en bas à la bonne place (aller), puis l’inverse (retour).
Énoncés, démonstrations et théories se codent par des entiers ; « être démontrable » devient une propriété arithmétique, qu’une théorie peut exprimer sur elle-même.
Complétude : ce qui est vrai dans tous les modèles est démontrable. Incomplétude : ce qui est vrai dans le modèle voulu (ℕ) ne l’est pas toujours, car d’autres modèles existent.
Compter, comparer et séparer les structures qui vérifient des axiomes : c’est la théorie des modèles. Un énoncé que des modèles départagent est indépendant des axiomes.
Complétude et compacité. Le théorème de complétude a pour conséquence le théorème de compacité : si chaque partie finie d’un ensemble d’axiomes a un modèle, l’ensemble entier en a un. Appliqué aux axiomes de Peano augmentés de « c > 0 », « c > 1 », « c > 2 », …, il fournit un modèle de l’arithmétique contenant un entier c plus grand que tous les entiers ordinaires.
Indécidabilité. Complétude ne veut pas dire décidabilité : l’ensemble des formules valides du premier ordre peut être énuméré (on produit toutes les démonstrations), mais on ne peut pas décider mécaniquement si une formule donnée y figure (Church, Turing, 1936).
Exemples d’indépendance. L’axiome du choix et l’hypothèse du continu sont indépendants de ZF (Gödel 1938, Cohen 1963) ; le théorème de Goodstein et celui de Paris-Harrington sont vrais mais indémontrables dans l’arithmétique de Peano ; le postulat des parallèles est indépendant des autres axiomes de la géométrie.
Dans la même série. Les pages sur la quête des fondements (paradoxe de Russell, vérificateur de démonstrations, ZFC), sur la logique comme branche des mathématiques et sur les fondements de la théorie des ensembles (suites de Goodstein) complètent celle-ci.