La partie C de ce cours, qui commence maintenant, prend un tournant décisif par rapport à ce qui précède. Même si on a rencontré précédemment des résultats non triviaux, on est restés dans le domaine de la théorie des ensembles basique. On va désormais s'intéresser à la théorie des ensembles avancée, celle qui jongle avec les modèles de ZFC. Pour ce faire nous allons devoir débuter par deux chapitres préliminaires, le premier concernant les théorèmes de complétude et de compacité, le second consacré aux théorèmes d'incomplétude.

A la section 1 on revient sur le calcul propositionnel. On commence par le théorème de compacité, qui dit qu'un ensemble de formules est satisfaisable ssi tout sous-ensemble fini l'est. On donne deux démonstrations de ce résultat, une basée sur la logique propositionnelle, l'autre sur la topologie et le théorème de Tychonoff. Ensuite, après quelques rappels sur l'axiomatique du calcul propositionnel, on démontre le théorème de complétude : toute tautologie est un théorème. En d'autres termes, si une formule F est vraie quelle que soit la distribution des valeurs de vérité des variables qui ont une occurrence dans F , alors il existe une démonstration de F à partir des axiomes et des règles du calcul propositionnel.

La section 2 est consacrée au calcul des prédicats du premier ordre. Après quelques rappels sur l'axiomatique et quelques préliminaires syntaxiques, dont le lemme de la déduction, on démontre le théorème de complétude généralisé : une théorie est consistante (c'est-à-dire non contradictoire) ssi elle a un modèle. Plus généralement, si σ est un énoncé vrai dans tous les modèles de T, alors il en existe une démonstration à partir des axiomes de T et du calcul des prédicats. On en déduit alors le théorème de complétude simple : un énoncé est vrai dans toutes les réalisations du langage ssi il est démontrable à partir des axiomes du calcul des prédicats. On en déduit également le théorème de compacité : une théorie T est consistante ssi toute sous-théorie finie de T l'est. Enfin, on montre comment le théorème de compacité permet de prouver l'existence de modèles non standards, par exemple pour l'arithmétique du premier ordre PA1.

A la section 3 on découvre les notions de produits réduits, ultraproduits et ultrapuissances. Le théorème de Los (prononcer Wosh) nous permet de donner une deuxième démonstration, topologique, du théorème de compacité du calcul des prédicats. On termine par une description des modèles non standards de l'arithmétique.

A la section 4 on donne quelques bases avancées de théorie des modèles. On commence par la notion d'équivalence élémentaire et de théorie complète. On donne un critère simple permettant d'affirmer qu'une théorie est complète, puis on en déduit quelques exemples. Viennent ensuite les notions de sous-structure élémentaire et de plongement élémentaire, qui vont nous permettre de démontrer les théorèmes de Löwenheim-Skolem et d'en donner une application.

Enfin, à la section 5 on fait une brève intrusion dans le monde des logiques d'ordre supérieur. L'essentiel de cette section porte sur la logique du second ordre. On en décrit la syntaxe, la sémantique et le pouvoir d'expression. On donne ensuite l'axiomatique de la logique du second ordre, et on en déduit qu'elle ne satisfait qu'un théorème de complétude faible. Pour des raisons assez évidentes, les théorèmes de compacité et de Löwenheim-Skolem y sont faux. On donne l'exemple de l'arithmétique du second ordre PA2, dont on montre qu'elle n'admet qu'un seul modèle à isomorphisme près. On termine par un bref descriptif des logiques du m-ième ordre et des logiques multisortées. Puis on conclut par une analyse des avantages et des inconvénients de chacune de ces logiques : en particulier la logique du second ordre a un pouvoir d'expression supérieur à celle du premier ordre et elle exclut l'existence de modèles non standard. En revanche, elle nous prive des théorèmes de compacité et de Löwenheim-Skolem, et le théorème de complétude y est fortement insatisfaisant.

Téléchargement du chapitre 14

Avertissement préliminaire : Roughly speaking (vulgairement parlant), le premier théorème d'incomplétude de Gödel est une trivialité. Fondamentalement, il repose sur le paradoxe du menteur.

En effet, soit T une théorie contenant au moins l'arithmétique classique, et soit F la formule du langage qui dit d'elle-même : je ne suis pas démontrable à partir de T. Si F est fausse, c'est qu'elle est démontrable à partir de T, donc T⊢F.

Mais alors, T démontre une formule fausse, ce qui signifie que T est contradictoire.

Par contraposée, on en déduit que si T est consistante, alors elle ne démontre pas F... et du coup F a raison quand elle dit qu'elle n'est pas démontrable à partir de T , c'est-à-dire que F est vraie.

Moralité : On a réussi à fabriquer une formule qui est vraie mais non démontrable... et c'est exactement ce que dit le premier théorème d'incomplétude.

Bien entendu, le raisonnement ci-dessus est extrêmement simplifié, et toute la difficulté de ce chapitre va consister à prouver qu'il existe effectivement une formule qui dit d'elle-même qu'elle n'est pas démontrable. Cette preuve va passer par des constructions alambiquées et des lemmes extrêmement techniques. C'est la raison pour laquelle certaines démonstrations seront seulement esquissées, d'autres purement et simplement omises, renvoyant à des références spécialisées pour les détails.

Ce chapitre constitue une exception dans la structure générale de ce livre. En effet, nous n'allons pas y faire du tout de théorie des ensembles (ou presque pas), et très peu de logique. Par contre nous y ferons beaucoup de récursivité / calculabilité. L'idée est d'introduire une notion convenable de fonction calculable, qui puisse nous servir à arithmétiser la syntaxe et à introduire progressivement les outils qui nous permettront ensuite de démontrer les paradoxes qui mènent aux théorèmes d'indécidabilité et d'incomplétude.

A la section 1 on introduit la première notion de fonction calculable qui puisse venir à l'esprit, à savoir celle de fonction récursive primitive (en abrégé 𝓡𝓟). On donne plusieurs approches de cette notion, ainsi que les premiers exemples de fonctions 𝓡𝓟. On montre ensuite comment les fonctions 𝓡𝓟 vont nous permettre d'aborder avec succès des notions un peu plus subtiles : quantifications bornées, opérateur de minimalisation, codage des suites finies d'entiers, énumération des suites. La section se termine par un résultat négatif. On montre de deux façons différentes que la notion de fonction récursive primitive est inadéquate par rapport à la calculabilité : d'abord par un argument théorique, appelé diagonalisation, puis par l'exhibition d'une fonction calculable qui n'est pas 𝓡𝓟 : la fonction d'Ackermann.

La section 2 étudie une classe plus générale de fonctions, à savoir celle des fonctions récursives. Dans un premier temps, une réflexion simple nous permet de constater que le passage à des fonctions partielles rend caduc l'argument diagonal évoqué ci-dessus. On donne alors la définition des fonctions récursives (partielles) et les premières propriétés qui en découlent. On expose ensuite la thèse de Church, qui dit en substance que les fonctions récursives sont exactement les fonctions calculables en un certain sens.

A la section 3 on rentre dans un domaine plus technique avec la complexité des formules. On se place dans la structure 𝓝=⟨ℕ 0, S, +, ∗, ≤⟩ , où on définit les formules Δ0_0 , Σ0_1 et Π0_1 . On généralise ensuite cette définition aux formules Σ et Π , dont on montre l'identité avec les formules Σ0_1 et Π0_1 dans le cadre de la 𝓝-équivalence. On termine par la définition des fonctions Δ0_0-rudimentaires, qui joueront un rôle important dans les sections 4 et 5.

La section 4 est consacrée à l'énumération Δ0_0-rudimentaire des suites finies. Après quelques préliminaires algébriques on définit la fonction β-tilda de Gödel, puis on montre que les fonctions récursives partielles sont exactement les fonctions à graphe Σ0_1 . On termine par la forme normale de Kleene, dont on donne quelques conséquences pratiques.

A la section 5 nous étudions un exemple concret de fonctions calculables. Il en existe divers modèles, et nous avons choisi celui des machines à registres. Nous commençons par une description de ces machines, puis donnons quelques exemples de fonctions calculables et de programmes exécutables par machines à registres. Le résultat essentiel de cette section est que la classe des fonctions récursives coïncide exactement avec celle des fonctions calculables par machines à registres. On explique alors rapidement en quoi ce résultat abonde fortement dans le sens de la thèse de Church.

La section 6 est consacrée à l'étude des ensembles récursivement énumérables, ou semi-récursifs, qui est une classe plus large que celle des ensembles récursifs. Après quelques préliminaires sur les fonctions et relations universelles, on donne trois définitions des ensembles récursivement énumérables (dont on montre qu'elles sont équivalentes), et on les compare avec les ensembles récursifs. On s'intéresse ensuite au problème de la halte, où on montre que la question de savoir si un algorithme converge (c'est-à-dire s'arrête en un temps fini) est indécidable. On termine par quelques compléments sur les relations Σ0_1 et Π0_1 .

A la section 7 on rentre enfin dans le vif du sujet : la représentabilité d'une fonction de ℕ puissance p dans ℕ puissance q. On décrit la théorie PA faible , dite aussi arithmétique Q de Robinson, qui n'est autre que PA1 "amputée" du schéma d'induction, et on étudie de façon très superficielle la structure des modèles de cette théorie. On en vient ensuite aux fonctions représentables, qui sont les fonctions dont les résultats peuvent être "représentés en un certain sens" par une formule du langage de PA faible . L'étude de la représentabilité passe en particulier par la fonction β de Gödel, qui permet de coder les suites d'entiers. On termine par l'exposé du théorème de représentation, qui dit que toute fonction récursive totale est représentable.

A la section 8 on arithmétise la syntaxe : on commence par coder les formules, puis les démonstrations, et on termine par la notion de théorie récursive.

Enfin, à la section 9 on présente les différents théorèmes d'indécidabilité et d'incomplétude, dits aussi théorèmes de limitation. On commence par le théorème d'indécidabilité de Church, qui énonce l'indécidabilité de l'arithmétique et du calcul des prédicats. Viennent ensuite le lemme diagonal, qui contient en substance l'essentiel de ce qui suit, puis enfin les célèbres théorèmes d'incomplétude de Gödel. En conclusion, on explique en quoi le second théorème d'incomplétude va nous servir en théorie des ensembles.

Téléchargement du chapitre 15

Ce chapitre marque un tournant décisif dans la démarche que nous avons suivie jusqu'ici. En effet, pour l'instant nous avons fait comme si nous vivions dans un certain univers U composé d'ensembles (voire même d'ensembles purs) et avons cherché à déterminer quelles étaient les propriétés que nous souhaitions attribuer à cet univers. A partir de maintenant nous allons jongler avec plusieurs univers, ou modèles de ZFC. Le pas à franchir est difficile, mais compensé par le fait que nous sommes maintenant mieux armés, puisque nous disposons désormais du théorème de complétude, ainsi que des théorèmes d'incomplétude de Gödel.

A la section 1 on rappelle la notion de modèle de ZFC, et on montre, via le second théorème d'incomplétude, l'impossibilité d'exhiber un tel modèle. Si ZFC est consistante (ce qu'on supposera toujours à l'avenir), le théorème de Löwenheim-Skolem montre l'existence d'un modèle dénombrable de ZFC. C'est ce qu'on appelle le paradoxe de Skolem. On explique alors que ce paradoxe n'en est pas un, et on revient sur des notions élémentaires de prouvabilité en théorie des ensembles. En particulier, on montre comment des outils sémantiques vont nous permettre de rédiger des preuves d'indépendance. On termine la section par une réflexion philosophique et totalement personnelle sur la notion de modèle de ZFC.

La section 2 est consacrée à la notion de standardicité. Dans un premier temps on donne la définition de ce qu'est un modèle ω -standard (qu'on abrégera par la suite par standard) et un modèle α-standard pour n'importe quel ordinal α. On montre ensuite que si ZFC est consistante elle admet nécessairement des modèles non standards, mais que la consistance de ZFC ne permet pas de prouver l'existence d'un modèle standard. S'ensuit une âpre discussion sur la standardicité ou la non-standardicité de l'univers réel.

A la section 3 on donne un premier aperçu sur les modèles transitifs de ZFC. Après quelques préliminaires on donne la définition : un modèle (M,E) est dit transitif si sa relation d'appartenance E est la restriction à M de la relation d'appartenance dans l'univers réel. On explique qu'un modèle transitif est nécessairement standard (et même α -standard pour tout ordinal α). Les questions plus délicates d'absoluité pour les modèles transitifs sont reportées au Chapitre 17.

A la section 4 on fait le lien entre la notion de modèle de ZFC et la hiérarchie cumulative des Vα . Plus précisément on essaie de répondre à la question suivante : pour chaque axiome de ZFC, quelle valeur faut-il donner à α pour que Vα soit modèle de cet axiome ? On y répond de façon favorable dans tous les cas, sauf pour le schéma de remplacement, où on sent la nécessité de l'existence d'un gros cardinal. Mais ce cadre général permet de donner les premières preuves d'indépendance, qui ne présentent aucune difficulté particulière : on montre la non-redondance de l'axiome de l'infini, de l'axiome des parties, du schéma de remplacement et de l'axiome de fondation. Pour finir on dit un mot des autres axiomes de ZFC.

A la section 5 on revient sur les cardinaux fortement inaccessibles, qui ont été définis au Chapitre 12. On montre que si κ est fortement inaccessible, alors (Vκ, ∈) est modèle de ZFC. On en déduit, via le second théorème d'incomplétude, que, non seulement ZFC ne prouve pas l'existence d'un inaccessible, mais aussi que la consistance de ZFC n'entraîne pas la consistance de ZFC+ "Il existe un inaccessible". On en vient alors tout naturellement à la notion de consistency strength et d'hypothèse strictement plus forte que ZFC, ce qui permet de donner dès maintenant un aperçu très vague de la hiérarchie des grands cardinaux.

On termine à la section 6 par un petit complément, dans lequel on montre que ZF "est inhéremment infinie", au sens où elle n'est pas finiment axiomatisable, ni même finiment axiomatisable au-dessus de Z.

Téléchargement du chapitre 16

Dans ce chapitre on présente un certain nombre de notions techniques qui nous seront nécessaires pour l'étude de l'univers des constructibles de Gödel, pour le forcing et pour les grands cardinaux. L'essentiel des difficultés tourne autour de la notion d'absoluité.

A la section 1 on définit la complexité des formules ensemblistes (notion qui a déjà été abordée au Chapitre 15 dans le domaine de l'arithmétique). On commence par les formules Δ_0 et Δ0_T, T étant une théorie contenant au moins Z. Puis viennent les formules Σ1 , Π1 , Σ1_T , Π1_T, ainsi que leurs généralisations aux formules Σn , Πn , Σn_T, Πn_T. Enfin, on dit un mot des formules Σ1_n, Π1_n, Σm_n, Πm_n, qui joueront un rôle important au Chapitre 24.

A la section 2 on aborde les questions d'absoluité. On donne la définition générale, suivie de quelques propriétés simples. On explique qu'en général le problème est complexe, mais qu'on peut obtenir des résultats intéressants dans le cas des modèles transitifs. On démontre alors l'absoluité des formules Δ0_ZF pour lesdits modèles, dont on donne quelques applications. On montre en particulier un théorème de dichotomie : si M est un sous-modèle transitif de (V,∈) , alors ou bien M est modèle intérieur de ZF (c'est-à-dire que M est une classe propre qui contient les mêmes ordinaux que V ), ou bien M est un ensemble, inclus dans un certain Vα . On en vient ensuite à l'extension aux formules Σ1_ZF , Π1_ZF et Δ1_ZF. On montre la semi-absoluité ascendante des formules Σ1_ZF, la semi-absoluité descendante des formules Π1_ZF et l'absoluité des formules Δ1_ZF. Cette dernière propriété nous permet de démontrer l'absoluité des bons ordres, résultat fondamental pour la suite. Enfin, dans un dernier paragraphe, on justifie a posteriori les rares résultats qui avaient été laissés en suspens au Chapitre 16.

La section 3 est consacrée au lemme d'effondrement de Mostowski. Les modèles transitifs ayant montré de bonnes propriétés, il s'agit de prouver que, sous certaines conditions, une classe relationnelle peut être projetée sur une classe transitive. Après quelques préliminaires il nous faut généraliser les théorèmes de récursion qui ont été établis au Chapitre 8 pour la relation d'appartenance à des relations binaires quelconques. On peut alors énoncer, puis démontrer le lemme d'écrasement de Mostowski et en donner quelques applications.

Téléchargement du chapitre 17

Dans ce chapitre nous définissons la classe L des ensembles constructibles de Gödel, qui lui a permis, en 1938, de démontrer la non-contradiction relative de l'axiome du choix et de l'hypothèse généralisée du continu avec la théorie des ensembles de Zermelo-Fraenkel, l'article fondateur ayant été publié en 1940.

A la section 1 on présente les motivations, qui sont multiples. La première est de montrer que, si ZF est consistante (donc si elle admet un modèle de référence (V ,∈) ), il est possible de construire un modèle intérieur "minimal" de V (noté L) au sens où tout modèle intérieur M contient L. L'autre grande motivation consiste à prouver que L satisfait à la fois AC et HGC, ce qui, via la partie facile du théorème de complétude, permet bien d'atteindre l'objectif fixé ci-dessus.

La section 2 est consacrée à des préliminaires un peu techniques. La première difficulté consiste à reformaliser, à l'intérieur de l'univers V, l'ensemble des formules ensemblistes qui a été défini de façon naïve au Chapitre 4. On définit la valeur d'une formule, la restriction d'une formule à un ensemble, et on démontre une variante ensembliste du théorème de Löwenheim-Skolem. On explique ensuite ce que sont les ensembles définissables en termes d'ordinaux, définissant ainsi les classes OD et HOD . On donne au passage une propriété des énoncés d'arithmétique, puis on termine par l'énoncé du "principe du choix", dont on donne l'équivalence avec V=OD .

A la section 3 on introduit la classe L des ensembles constructibles. Pour ce faire on part de la notion de sous-ensembles définissables avec paramètres, puis on définit la hiérarchie des L_α pour α ordinal. Le principe est le même que pour la hiérarchie cumulative des V_α , sauf qu'à l'étape α+1 on ne prend que les parties définissables de L_α. On définit alors la classe L par la formule 

x∈L↔∃α (ON(α)∧x∈L_α) . On énonce ensuite l'axiome de constructibilité, noté V=L, puis on montre que L est modèle intérieur de ZF.

La section 4 est consacrée à la vérification du fait que l'axiome de constructibilité est satisfait dans L, ce qu'on note L⊨(V=L). Le résultat est moins trivial qu'il n'y paraît, pour des raisons d'absoluité. On en déduit que L est minimal, au sens où tout modèle intérieur de ZF le contient.

A la section 5 on montre que le modèle L satisfait AC, ce qui permet de donner une preuve de la consistance de l'axiome du choix avec ZF.

Le résultat phare de ce chapitre est donné à la section 6 : L satisfait l'hypothèse généralisée du continu. Là encore on en déduit un résultat de consistance relative, puis on revient un instant sur les énoncés d'arithmétique.

A la section 7 on donne une construction alternative de L à l'aide des opérations de Gödel et des classes stratifiées, ce qui permet d'en déduire une deuxième preuve du fait que L⊨ZFC .

La section 8 est consacrée à la notion de constructibilité relative (qui est une généralisation de la constructibilité usuelle) et à la description de quelques autres modèles intérieurs de ZF. On définit ainsi les classes L[A], L(A) , puis on revient aux classes OD et HOD , et on définit les classes HOD(A) . On donne au passage et très brièvement quelques propriétés élémentaires de ces classes.

Enfin, la section 9 consiste en une discussion philosophique sur l'opportunité d'adopter ou non l'axiome de constructibilité V=L dans notre étude de la théorie des ensembles.

Téléchargement du chapitre 18