Vers 1900, un paradoxe menace de faire s’écrouler tout l’édifice. La réponse des mathématiciens : faire de la logique un outil mathématique pour étudier… les mathématiques elles-mêmes.
« Au tournant du XXᵉ siècle, des paradoxes (notamment le paradoxe de Russell sur les ensembles) ont menacé la cohérence interne des mathématiques. La logique est alors devenue l’outil mathématique servant à étudier les mathématiques elles-mêmes : définir précisément ce qu’est une démonstration, un axiome ou un théorème ; fonder l’édifice mathématique sur une base solide, notamment via la théorie des ensembles (ZFC). »
Un paradoxe est un raisonnement apparemment correct qui aboutit à une contradiction : un énoncé et son contraire à la fois. La cohérence d’une théorie, c’est l’absence de contradiction. Planches 1 et 2 : d’où vient le paradoxe de Russell, et pourquoi une seule contradiction ruine tout.
Un axiome est un énoncé admis au départ ; une démonstration est une suite finie d’énoncés dont chacun est un axiome ou découle des précédents par une règle fixée ; un théorème est la dernière ligne d’une démonstration. Planches 3 et 4 : une démonstration vérifiée par une machine, des axiomes testés par des modèles.
La théorie des ensembles de Zermelo-Fraenkel avec l’axiome du choix (ZFC) sert de socle commun : nombres, fonctions, figures, tout y devient ensemble, et un seul symbole de relation suffit, l’appartenance ∈. Planche 5 : ce que coûte l’écriture complète d’un énoncé avec ∈ seul.
Chez Frege, toute propriété P définit un ensemble : S = {x : P(x)}, qui contient exactement les objets ayant la propriété. C’est la compréhension illimitée. Mais une fois S fabriqué, S est lui-même un objet : il doit, lui aussi, être dedans ou dehors. La machine teste les deux réponses possibles.
On pourrait croire qu’un paradoxe isolé ne gêne qu’un coin de la théorie. C’est faux : d’une contradiction, on peut déduire n’importe quel énoncé. On le voit avec trois énoncés élémentaires P, Q, R. Une valuation attribue à chacun « vrai » ou « faux » (8 possibilités) ; un modèle des axiomes est une valuation qui les rend tous vrais ; un énoncé est une conséquence des axiomes s’il est vrai dans tous les modèles.
Supposons démontrés X et ¬X. Pour un énoncé C quelconque (« 1 = 2 », par exemple) :
Contrôle par table de vérité de (X ∧ ¬X) → C :
Hilbert et ses élèves ont réduit la démonstration à un objet précis. On fixe trois schémas d’axiomes (des modèles de phrases où φ, ψ, χ peuvent être remplacées par n’importe quelle formule) et une seule règle, le modus ponens : de α et de α → β, on tire β. Une démonstration est alors une liste de lignes, chacune justifiée ; la vérifier ne demande aucune intelligence, seulement de comparer des symboles.
Le bouton « altérer » modifie un seul symbole de la ligne : observez ce que le vérificateur en pense, et ce qui en découle pour les lignes suivantes.
La logique ne se contente pas d’écrire des axiomes : elle les étudie. Deux questions reviennent sans cesse. Sont-ils cohérents ? Il suffit d’exhiber un modèle, un objet qui les vérifie tous. Un axiome est-il indépendant des autres (impossible à démontrer à partir d’eux) ? Il suffit d’exhiber un modèle des autres où il est faux. Laboratoire : les relations sur un petit ensemble, et cinq axiomes classiques.
Le socle retenu est une théorie où tout objet est un ensemble et où le seul symbole propre est l’appartenance ∈. Neuf axiomes (dont deux schémas, c’est-à-dire des familles infinies d’axiomes de même forme) disent quels ensembles existent. Aucun ne permet de former « l’ensemble de tous les ensembles » : le paradoxe de Russell y devient un simple théorème, « aucun ensemble ne contient tous les ensembles ».
| Axiome | Ce qu’il affirme | À quoi il sert |
|---|---|---|
| Extensionnalité | Deux ensembles qui ont les mêmes éléments sont égaux. | Un ensemble n’est rien d’autre que ses éléments. |
| Paire | Pour a et b, il existe {a, b}. | Singletons, couples (a, b) = {{a}, {a, b}}. |
| Réunion | Pour une famille d’ensembles, il existe la réunion de ses membres. | A ∪ B, successeur n ∪ {n}. |
| Parties | Pour A, il existe l’ensemble de ses parties 𝒫(A). | Produits cartésiens, relations, fonctions, ℝ. |
| Séparation (schéma) | Pour A et une propriété P, il existe {x ∈ A : P(x)}. | La compréhension, mais à l’intérieur d’un ensemble donné : c’est le remède à Russell. |
| Remplacement (schéma) | L’image d’un ensemble par une règle fonctionnelle est un ensemble. | Grands ordinaux, constructions par récurrence transfinie (Fraenkel, Skolem, 1922). |
| Infini | Il existe un ensemble contenant ∅ et stable par x ↦ x ∪ {x}. | L’ensemble ℕ des entiers naturels. |
| Fondation | Tout ensemble non vide a un élément qui n’a aucun élément en commun avec lui. | Interdit x ∈ x et les chaînes infinies descendantes. |
| Choix (le « C ») | Pour toute famille d’ensembles non vides, on peut choisir un élément dans chacun. | Bases de tout espace vectoriel, théorème de Tychonov ; indépendant de ZF (Gödel, Cohen). |
Fonder les mathématiques sur ZFC, c’est affirmer que tout énoncé mathématique pourrait être réécrit avec seulement des variables, ∈, les connecteurs (¬ ∧ ∨ → ↔) et les quantificateurs (∀ « pour tout », ∃ « il existe »). Faisons-le vraiment pour l’énoncé le plus simple : « w est l’entier n », avec les entiers de von Neumann 0 = ∅ et n + 1 = n ∪ {n}.
Deux manières d’éliminer l’abréviation « n » dans « w = n + 1 », c’est-à-dire « les éléments de w sont ceux de n, plus n lui-même ». En nommant : « il existe p qui est n, et … » — la définition de n est écrite une fois. En recopiant : partout où « n » apparaît, on colle sa définition — elle apparaît deux fois, puisque n intervient deux fois (« être dans n » et « être n »).
En recopiant, chaque étape double la longueur : 25·2n − 19 symboles. C’est ce qui arrive aux formalismes qui remplacent chaque abréviation par sa définition complète. Le cas célèbre est celui de Bourbaki, dont le terme désignant le nombre 1, entièrement déplié, compte 4 523 659 424 929 symboles (calcul d’Adrian Mathias, 2002).
Une formule de plusieurs centaines de symboles dit-elle vraiment « w est l’entier n » ? On la fait évaluer, sans rien lui expliquer, dans un petit univers d’ensembles : V₃ (4 ensembles) ou V₄ (16 ensembles), tous les ensembles qu’on peut bâtir à partir de ∅ en trois ou quatre étages. Chaque ensemble est codé par un entier (codage d’Ackermann : a ∈ b quand le chiffre binaire de rang a de b vaut 1). La machine essaie chacun comme valeur de w.
La compréhension illimitée de Frege exige un ensemble qui ne peut ni se contenir ni ne pas se contenir. Et une contradiction, dans une théorie, rend tout démontrable.
Axiome, démonstration, théorème deviennent des objets précis, vérifiables par une machine. Cohérence et indépendance se démontrent par des modèles.
Neuf axiomes sur la seule relation ∈. La séparation désamorce Russell ; tout le reste des mathématiques s’y récrit — en principe.
Ce que la quête n’a pas obtenu. Hilbert espérait prouver la cohérence des mathématiques par des moyens sûrs et élémentaires. Le second théorème d’incomplétude de Gödel (1931) montre que ZFC, si elle est cohérente, ne peut pas démontrer sa propre cohérence. On sait en revanche que ZFC est cohérente si ZF l’est (Gödel, 1938) : l’axiome du choix n’ajoute aucun risque.
Complétude. Pour la logique du premier ordre, Gödel a démontré en 1929 que tout énoncé vrai dans tous les modèles possède une démonstration : les deux points de vue des planches 2 et 3 (modèles et preuves) coïncident. Pour le calcul propositionnel de la planche 3, c’est un résultat de Post (1921).
D’autres fondements. La théorie des types (Russell, puis Church et Martin-Löf), la théorie des catégories et, récemment, la théorie homotopique des types proposent d’autres socles. Les assistants de preuve (Coq/Rocq, Lean, Isabelle) vérifient mécaniquement des démonstrations entières, exactement comme la machine de la planche 3, mais sur des milliers de pages.
Dans la même série. Les pages sur les fondements de la théorie des ensembles (axiomes un par un, axiome du choix), sur la logique comme branche des mathématiques (Aristote, Boole, Frege, Peano, Gödel) et sur les raisonnements par récurrence et par l’absurde prolongent celle-ci.