Premier exposé : rappels de logique et de théorie des ensembles

David A. Madore

11 octobre 1998

Table des matières

1 Rappels de logique du premier ordre 1

2 Logique du second ordre 2

3 Théorie des ensembles 4 3.1 Les axiomes de ZF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2 Ensembles bien ordonnés et ordinaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3 Cardinalités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 L’axiome du choix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Exponentiation cardinale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.6 L’axiome de régularité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Modèles de la théorie des ensembles 12

1 Rappels de logique du premier ordre

Sans donner de définition rigoureuse, rappelons simplement qu’une formule du premier ordre dans un langage L donné est formée à partir des connecteurs du calcul propositionnel (qui sont ⇒, ∧, ⊤, ∨ et ⊥), des quantificateurs ∀ et ∃, de variables (dites variables d’objets), et des symboles du langage, qui peuvent être des symboles de constantes, de fonctions ou de relations.

Une L-structure est un ensemble M muni d’un élément c_{i} pour chaque symbole de constante c̄_{i} du langage L, d’une fonction f_{i}: M^{n} → M pour chaque symbole de fonction f̄_{i} d’arité n du langage, et d’une relation R_{i} ⊆ M^{n} pour chaque symbole de relation R̄_{i} d’arité n du langage. Lorsqu’on a une telle L-structure M, on peut alors définir une notion de satisfaction des formules du premier ordre, par induction sur la complexité de celles-ci. Par exemple, on a M ⊨ ∀x∃yR̄(x, y, c̄) (avec R̄ une relation d’arité 3 du langage, et c̄ une constante du langage) si et seulement si pour tout x de M il existe y de M tel que R(x, y, c), où R ⊆ M^{3} est la fonction qui représente le symbole R̄, et c ∈ M l’élément qui représente le symbole c̄.

Par ailleurs, on a une notion de démonstration formelle, dont nous ne rappelons pas les mécanismes (ceux-ci seront étudiés en détail et beaucoup plus élégamment que de la façon “classique” dans la partie du groupe de travail consacrée à la logique catégorique). Voici cependant les règles fondamentales :

A ⊢ A (identité)

\frac{Γ ⊢ A}{Γ, Δ ⊢ A} (affaiblissement) \frac{Γ, C, C ⊢ A}{Γ, C ⊢ A} (rasoir)

\frac{Γ ⊢ A Δ, A ⊢ B}{Γ, Δ ⊢ B} (coupure)

\frac{Γ, A ⊢ B}{Γ ⊢ A ⇒ B} (théorème de déduction) \frac{Γ ⊢ A ⇒ B}{Γ, A ⊢ B} (modus ponens)

\frac{Γ ⊢ A Γ ⊢ B}{Γ ⊢ A ∧ B} (∧intro)  \frac{Γ ⊢ A ∧ B}{Γ ⊢ A} (∧elimL)  \frac{Γ ⊢ A ∧ B}{Γ ⊢ B} (∧elimR)
Γ ⊢ ⊤ (⊤intro)
\frac{Γ ⊢ A}{Γ ⊢ A ∨ B} (∨introL)  \frac{Γ ⊢ B}{Γ ⊢ A ∨ B} (∨introR)  \frac{Γ, A ⊢ C  Γ, B ⊢ C}{Γ, A ∨ B ⊢ C} (∨elim)
Γ, ⊥ ⊢ A (⊥elim)

\frac{Γ ⊢ A(x)}{Γ ⊢ ∀x(A(x))} (∀intro, x pas libre dans Γ) \frac{Γ ⊢ ∀x(A(x))}{Γ ⊢ A(t)} (∀elim)

\frac{Γ ⊢ A(t)}{Γ ⊢ ∃x(A(x))} (∃intro) \frac{Γ, A(x) ⊢ B}{Γ, ∃x(A(x)) ⊢ B} (∃elim, x pas libre dans Γ ou B)

\frac{Γ, A ⇒ ⊥ ⊢ ⊥}{Γ ⊢ A} (par l’absurde)

On a le théorème très important suivant : Théorème 1.1 (de complétude). Si Γ est un ensemble de formules closes du premier ordre dans un langage L et A une telle formule, alors Γ ⊢ A si et seulement si pour toute M-structure qui vérifie M ⊨ Γ on a M ⊨ A.

Une M-structure telle que M ⊨ Γ est appelée un modèle de Γ. Autrement dit, une formule A est un théorème de la théorie Γ si et seulement si elle est vraie dans tout modèle. Le “seulement si” signifie que la structure sémantique apportée par les modèles est \underline{pertinente} à la logique étudiée, et le “si” signifie que cette structure sémantique (lorsqu’on considère tous les modèles) est \underline{complète}.

D’autre part, on rappelle le Théorème 1.2 (de compacité). Une théorie Γ est consistante (i.e. Γ ⊬ ⊥) si et seulement si toute partie finie de Γ est consistante.

Et enfin le Théorème 1.3 (de Löwenheim-Skolem). Si 𝔐 est une structure d’un langage L, alors il existe un sous-modèle élémentaire 𝔐_{0} ⊆ 𝔐 (c’est-à-dire que les formules du premier ordre avec constantes dans 𝔐_{0} ont la même valeur de vérité dans 𝔐_{0} et dans 𝔐) dont le cardinal est card L + ℵ_{0}.

La démonstration du théorème de Löwenheim-Skolem se fait de la façon suivante : pour toute formule φ(x, x_{1}, …, x_{n}) à n + 1 variables libres, on trouve une fonction h_{φ}: 𝔐^{n} → 𝔐 telle que, pour tous a_{1}, …, a_{n} de 𝔐, si 𝔐 ⊨ ∃xφ(x, a_{1}, …, a_{n}), alors 𝔐 ⊨ φ(h_{φ}(a_{1}, …, a_{n}), a_{1}, …, a_{n}). Autrement dit, on choisit un témoin de chaque formule existentielle. On dit que h_{φ} est une fonction de Skolem pour la formule φ. On construit alors 𝔐_{0} comme la plus petite partie de 𝔐 close sous l’opération de toutes les formules de Skolem.

Précisons un dernier point de terminologie : une partie A d’une structure 𝔐 d’un langage L est dite définissable si et seulement si il existe une formule φ(x, x_{1}, …, x_{n}) et des éléments a_{1}, …, a_{n} ∈ A tels que a ∈ A si et seulement si 𝔐 ⊨ φ(a, a_{1}, …, a_{n}). On dit alors que A est définissable à partir de a_{1}, …, a_{n}. On dit que a ∈ 𝔐 est définissable à partir de a_{1}, …, a_{n} ssi {a} l’est.

2 Logique du second ordre

Dans la logique du second ordre, on autorise la quantification non seulement sur les objets mais aussi sur les prédicats (d’arité quelconque). Par exemple, le principe de récurrence, qui en logique du premier ordre doit se formuler comme une infinité d’axiomes (un pour chaque formule, ce qui revient à n’affirmer le principe que pour les parties définissables de ℕ), s’énonce en logique du second ordre comme

∀P ((P (0) ∧ ∀n(P (n) ⇒ P (Sn))) ⇒ (∀n(P (n))))

La question est alors de savoir comment on définit un modèle en logique du second ordre. Lorsque l’on décide que la quantification sur les prédicats concerne toutes les parties du modèle, on parlera de \underline{modèle plein}. Par exemple, la formule écrite ci-dessus s’interprète dans un modèle plein 𝔐 comme signifiant que toute partie A de 𝔐 qui contient l’élément qui représente le symbole 0 et contient l’image par la fonction qui représente le symbole S de tout élément qu’elle contient, est égale à 𝔐. Mais on peut aussi décider de considérer des modèles dans lesquels la quantification sur les prédicats ne concerne pas toutes les parties de 𝔐. Il faut alors rajouter, dans les données qui définissent une structure 𝔐, un ensemble de parties de 𝔐; le cas des modèles pleins est celui où cet ensemble est justement 𝒫(𝔐).

D’autre part, il faut se demander comment la notion de démonstration formelle se transpose en logique du second ordre. Les règles habituelles restent bien entendu valables ; en particulier, si on a démontré une formule du type ∃P (⋯), avec P une variable de prédicat, on peut la concrétiser et “choisir un tel P ”. La règle ∃elim ne pose donc pas de problème, pas plus que la règle ∀intro (qui ne peut, bien sûr, que s’appliquer à des variables de prédicats). Les règles ∀elim et ∃intro, en revanche, posent plus de problèmes sur les variables du second ordre, car on ne sait pas quoi prendre comme “termes” de prédicats. On veut bien sûr pouvoir utiliser n’importe quelle formule ayant une variable-objet libre à cette place. La solution est alors de formuler un schéma d’axiomes (comme on fait en logique du premier ordre pour le principe de récurrence), le schéma d’axiomes de compréhension : pour toute formule libre φ(x, x_{1}, …, x_{n}), on postule

∀t_{1} ⋯ ∀t_{n}∃P ∀x(P (x, x_{1}, …, x_{n}) ⇔ φ(x, x_{1}, …, x_{n}))

Une façon légèrement différente, et néanmoins équivalente, de procéder, consiste à autoriser la formation de termes de prédicats (plutôt que simplement postuler leur existence, comme cidessus) avec une notation λ : si on a une formule φ(x, x_{1}, …, x_{n}), on peut former un terme λx.φ(x, x_{1}, …, x_{n}) qui est un prédicat.

On se doute bien qu’avec un tel système de démonstration, les théories du deuxième ordre ne vont pas être plus puissantes que les théories du premier ordre correspondantes. Cependant, elles sont beaucoup plus expressives, puisqu’elles permettent de parler non seulement d’éléments de leur domaine, mais aussi de parties de celui-ci.

Les relations entre démonstrations et sématique sont plus complexes en logique du deuxième ordre qu’en logique du premier ordre. Avant toute chose, on note que tout modèle du deuxième ordre (plein ou non) vérifie l’axiome suivant

∀P ∀Q((∀x(P (x) ⇔ Q(x))) ⇒ P = Q)

dit axiome d’extension. On le prendra donc comme axiome de la logique du second ordre, à côté de l’axiome de compréhension.

Malgré cette addition, les modèles pleins continuent à ne pas former une structure sémantique complète pour la logique du second ordre. Pour le voir, considérons les axiomes de Peano du second ordre, c’est-à-dire la théorie sur le langage (0, S) avec les axiomes suivants

∀x(¬(Sx = 0))
∀x∀y((Sx = Sy) ⇒ (x = y))
∀P ((P (0) ∧ ∀n(P (n) ⇒ P (Sn))) ⇒ (∀n(P (n))))

Contrairement à ce qui se passe en logique du premier ordre, on n’a ici pas besoin de prendre + et × comme symboles du langage pour capturer l’arithmétique : en effet, la formule u + v = w peut se traduire par

∀Q(((∀x(Q(x, 0, x))) ∧ (∀x∀y∀z(Q(x, y, z) ⇒ Q(x, Sy, Sz)))) ⇒ (Q(u, v, w)))

Cette arithmétique du second ordre a de remarquable par rapport à sa consœur du premier ordre qu’elle est catégorique : autrement dit, elle a un seul modèle plein (à isomorphisme près), et c’est ℕ (muni de son zéro et de sa fonction successeur habituels). En effet, si (𝔐, 0, S) est un modèle des axiomes écrits ci-dessus, on peut définir ψ: ℕ → 𝔐 par ψ(n) = S^{n}0. Il est facile de voir que ψ est un isomorphisme de ℕ sur une sous-structure de 𝔐, et le seul point restant à montrer est que ψ est surjectif ; mais pour cela on applique le troisième axiome à l’image de ψ, et on a immédiatement le résultat. Quand on se rappelle qu’en logique du premier ordre toutes les théories catégoriques ont des modèles finis, cela a de quoi surprendre.

Quoi qu’il en soit, cela suffit à prouver que le théorème de complétude ne tient pas : toute affirmation arithmétique vraie dans ℕ est vrai dans tous les modèles de l’arithmétique du second ordre (puisqu’il n’y en a qu’un justement, et c’est ℕ). Mais toutes sont loin d’être démontrables (ne serait-ce que parce que le système de démonstration que nous avons proposé est récursif, donc il ne peut certainement pas énumérer les affirmations vraies dans ℕ).

3 Théorie des ensembles

3.1 Les axiomes de ZF

La théorie des ensembles (ZF) est une théorie sur le langage ayant un seul symbole, une relation binaire notée ∈.

Les axiomes sont : Axiome 3.1 (d’extension). Si X et Y ont les mêmes éléments alors X = Y.

(La réciproque est conséquence des propriétés logiques de l’égalité.) Axiome 3.2 (de la paire). Pour tous x et y il existe un ensemble, noté {x, y}, dont les éléments sont x et y et seulement eux. Schéma axiome 3.3 (de séparation). Soit φ(x, x_{1}, …, x_{n}) une formule. Pour tout ensemble X et tous a_{1}, …, a_{n} il existe un ensemble dont les éléments sont exactement les a tels que a ∈ X et que φ(a, a_{1}, …, a_{n}). On le note {x: φ(x, a_{1}, …, a_{n})}.

Il faut naturellement formuler un tel axiome pour chaque formule φ du premier ordre. En fait, on peut se contenter de formules ayant deux variables libres (puisqu’on peut coder tout n-uplet (a_{1}, …, a_{n}) dans un seul ensemble). Si on formule ZF en logique du second ordre, on n’a alors plus naturellement qu’un seul axiome de séparation, qui quantifie sur tous les prédicats, et c’est l’axiome de compréhension qui fait le travail. Axiome 3.4 (de l’union). Pour tout X il existe un ensemble Y (noté ⋃ X) dont les éléments sont précisément les éléments des éléments de X. Axiome 3.5 (de l’ensemble des parties). Pour tout X il existe un ensemble (noté 𝒫(X)) dont les éléments sont précisément les parties de X. Axiome 3.6 (de l’infini). La classe des naturels est un ensemble.

Il y a beaucoup de façons de formuler cet axiome. On dit qu’un ensemble est inductif si et seulement si il contient ∅ et contient x ∪ {x} pour chacun de ses éléments x. Un ensemble est appelé entier naturel si et seulement s’il appartient à tout ensemble inductif. La classe des naturels ω est donc l’intersection de tous les ensembles inductifs. L’axiome de l’infini postule que cette classe est un ensemble. Cela revient en fait (grâce à l’axiome de séparation) à postuler qu’il existe un ensemble inductif.

Accessoirement, l’axiome de l’infini est la seule façon dont on dispose pour prouver l’existence d’un ensemble. Toutefois, si on considère la théorie des ensembles sans l’axiome de l’infini, on postulera explicitement l’existence d’un ensemble (ou, ce qui revient au même, de l’ensemble vide). Schéma axiome 3.7 (de remplacement). Soit φ(x, y, x_{1}, …, x_{n}) une formule. Soient X et a_{1}, …, a_{n} des ensembles. On suppose que pour tout u ∈ X il existe au plus un ensemble v tel que φ(u, v, a_{1}, …, a_{n}). Alors il existe un ensemble dont les éléments sont exactement les v tels que φ(u, v, a_{1}, …, a_{n}) pour un certain u ∈ X.

Axiome 3.8 (de régularité (ou de fondation)). Si X est un ensemble non vide, alors il existe un élément Y de X tel que Y ∩ X = ∅.

En présence de l’axiome du choix dénombrable (voir plus loin), l’axiome de régularité équivaut à l’inexistence de suites X_{0} ∋ X_{1} ∋ X_{2} ∋ ⋯ d’ensembles. Une formulation beaucoup plus constructive de l’axiome de régularité, qui a l’avantage d’éviter les recours au tiers exclu, est la suivante

∀X∀X_{0}((∀z ∈ X(z ∩ X ⊆ X_{0} ⇒ z ∈ X_{0})) ⇒ X_{0} ⊇ X)

Elle a l’inconvénient que les gens qui essayent de la comprendre finissent en général par se cogner la tête contre les murs. Pourtant, c’est un simple principe d’induction : si X_{0} contient un élément z de X dès qu’il contient tous les éléments de z qui sont aussi dans X, alors X_{0} contient tous les éléments de X. Lorsque l’ensemble X est transitif, ce qui signifie ∀z ∈ X(z ⊆ X) (ou encore, X ⊆ 𝒫(X)), alors le principe s’énonce plus simplement :

∀X_{0}((∀z ∈ X(z ⊆ X_{0} ⇒ z ∈ X_{0})) ⇒ X_{0} ⊇ X)

L’axiome suivant ne fait pas partie de ZF mais de ZFC : Axiome 3.9 (du choix). Si 𝔛 est un ensemble ne contenant pas l’ensemble vide, alors il existe une fonction qui à chaque élément X de 𝔛 associe un élément de X.

Ou encore, le produit cartésien d’une famille d’ensembles non vide est non vide. C’est cet axiome qui permet de remplacer la suite de quantificateurs ∀x ∈ X∃y ∈ Y (P (x, y)) par la suite ∃f: X → Y ∀x ∈ X(P (x, f(x))).

Pour le moment, on travaille sans l’axiome du choix et sans l’axiome de régularité.

Bien que les seuls objets permis en théorie des ensembles soient les ensembles, on se permettra de parler de classes d’ensembles : par une classe d’ensembles, on entend une expression formelle {x : φ(x, a_{1}, …, a_{n})}, où φ(x, x_{1}, …, x_{n}) est une certaine formule du premier ordre, et a_{1}, …, a_{n} des ensembles. (On dit alors que la classe en question est définissable à partir de a_{1}, …, a_{n}.) Par exemple, si a est un ensemble, alors en prenant x ∈ x_{1} pour φ(x, x_{1}) et a pour a_{1}, on voit que {x : x ∈ a} est une classe. Grâce à l’axiome d’extension, on peut l’identifier à a. Comme autre classe importante, on a la classe universelle V = {x : x = x}. La théorie des ensembles ZF ne permet pas vraiment de manipuler les classes. Une formule portant sur une classe précise ne pose pas de problème, mais la quantification est plus ennuyeuse. En fait, la seule chose qu’on puisse plus ou moins faire, c’est quantifier universellement sur les classes, ce qui se traduit par une infinité de formules ; par exemple, l’axiome de séparation traduit précisément le fait que l’intersection d’une classe et d’un ensemble est un ensemble, et il y a bien quantification universelle sur les classes, au prix d’une infinité de formules. La quantification existentielle sur les classes n’est pas possible, cependant : une affirmation telle que “Il existe un bon ordre sur la classe V.” n’est pas formulable dans ZF (car un bon ordre sur V serait une classe), même si pour une classe < donnée l’affirmation “La classe < est un bon ordre sur la classe V.” a un sens dans ZF. (Il s’agit là de versions fortes de l’axiome du choix.)

3.2 Ensembles bien ordonnés et ordinaux

On dit qu’un ensemble ordonné W est \underline{bien ordonné} ssi toute partie non vide de W a un plus petit élément. Clairement, W est alors totalement ordonné. Une formulation plus constructive de la définition est le principe suivant : Théorème 3.10 (principe d’induction transfinie). Si W_{0} est un ensemble, et que pour tout z ∈ W tel que {t ∈ W : t < z} ⊆ W_{0} on a z ∈ W_{0}, alors W_{0} ⊇ W.

Un ensemble totalement ordonné vérifie le principe d’induction transfini si et seulement si il est bien ordonné. (Si W est bien ordonné, considérer le plus petit élément de W qui n’est pas dans W_{0}. Si W vérifie le principe d’induction transfinie et P ⊆ W n’a pas de plus petit élément, considérer pour W_{0} le complémentaire de P.)

On appelle segment initial d’un ensemble bien ordonné W une partie W_{0} de W telle que si x ∈ W_{0} et y < x alors y ∈ W_{0}. On montre facilement que tout segment initial de W est soit W soit est le segment initial strict d’un x ∈ W, c’est-à-dire s(x) = {y ∈ W : y < x}.

Les ensembles totalement ordonnés forment une catégorie rigide : si W est bien ordonné, le seul automorphisme de W (bijection croissante de W sur lui-même) est l’identité. Par conséquent, un isomorphisme entre deux ensembles bien ordonnés est unique s’il existe. Plus généralement, si W est bien ordonné et f: W → W est injective croissante alors f(x) ≥ x pour tout x ∈ W. Si W_{1} et W_{2} sont deux ensembles bien ordonnés, alors soit W_{1} et W_{2} sont isomorphes (et cet isomorphisme est unique), soit W_{1} est isomorphe (par un isomorphisme unique) au segment initial s(b) = {y ∈ W_{2} : y < b} d’un b ∈ W_{2}, lequel est alors uniquement déterminé, soit W_{2} est isomorphe (par un isomorphisme unique) au segment initial s(a) = {x ∈ W_{1} : x < a} d’un a ∈ W_{1}, lequel est alors uniquement déterminé, et de plus ces trois possibilités sont mutuellement exclusives. (L’idée clef dans la démonstration est d’introduire l’ensemble I des a ∈ W_{1} tels que s(a) soit isomorphe à un certain s(b) avec b ∈ W_{2} (lequel est alors clairement uniquement déterminé), et l’ensemble J des b ∈ W_{2} tels que s(b) soit isomorphe à un certain s(a) avec a ∈ W_{1} uniquement déterminé. Il est clair que I et J sont des segments initiaux. Le seul cas à exclure est celui où tous deux sont stricts, disons I = s(u) et J = s(v). Mais en associant à a ∈ I l’unique b ∈ J tel que s(a) et s(b) soient isomorphes, on définit un isomorphisme entre I = s(u) et J = s(v) donc u ∈ I et v ∈ J, contradiction.)

Un ensemble X est dit \underline{transitif} ssi X ⊆ 𝒫(X), autrement dit ssi ∀z ∈ X(z ⊆ X), soit ∀z ∈ X∀t ∈ z(t ∈ X), soit encore ⋃ X ⊆ X. Grâce à l’axiome de l’infini, si X est un ensemble quelconque, on peut considérer la suite définie par récurrence X_{0} = X et X_{n+1} = ⋃ X_{n}. L’union de tous les X_{i} est le plus petit ensemble transitif contenant X et on l’appelle la clôture transitive de X.

Si X est transitif, on peut considérer la relation ∈ entre les éléments de X. Si cette relation est une relation de bon ordre strict, on dit que X est un \underline{ordinal}. En fait, si on suppose vérifié l’axiome de régularité, il suffit de supposer que la relation est transitive, autrement dit que tout élément de X est lui-même transitif. Théorème 3.11 (du comptage (Cantor)). Tout ensemble bien ordonné est isomorphe à un ordinal unique (et l’isomorphisme est lui-même unique).

Si α et β sont deux ordinaux, il revient au même de dire que α ∈ β, que α ⊆ β avec α ≠ β, ou encore que α est isomorphe (en tant qu’ensemble bien ordonné) à un segment initial strict de β. Dans ces conditions, on dit que α < β. Avec cette relation d’ordre, la classe On des ordinaux est elle-même une classe transitive bien ordonnée.

Il existe des ordinaux : ∅ en est un, noté 0. Si α est un ordinal, alors α∪{α} est un ordinal, noté α+1 et appelé successeur de α, qui est le plus petit ordinal strictement supérieur à α. Tout ensemble d’ordinaux est bien ordonné, et de plus l’union de ses éléments en est la borne supérieure dans la classe des ordinaux ; l’union des successeurs de ses éléments est le plus petit ordinal strictement supérieur à tous les éléments de l’ensemble (la borne supérieure stricte de l’ensemble).

Tout ordinal n’est pas le successeur d’un autre ordinal : la preuve, 0 n’en est pas un. Un ordinal autre que 0 qui n’est pas un successeur est dit \underline{limite}. La plus petite classe contenant 0 et clos par l’opération successeur est notée ω. C’est soit un ordinal soit la classe de tous les ordinaux : l’axiome de l’infini assure que ω < On, autrement dit que ω est un ordinal (est un ensemble).

Si α et β sont deux ordinaux, on peut définir la somme de α et β de la façon suivante : on ordonne l’union disjointe de α et de β en mettant les éléments de α avant ceux de β, ce qui définit un bon ordre, et on appelle α + β l’unique ordinal qui est isomorphe à ce bon ordre (en vertu du théorème du comptage de Cantor). De même, en mettant l’ordre lexicographique sur le produit cartésien qui donne le poids le plus fort aux éléments de β, on définit αβ. Enfin, en considérant les fonctions presque nulles de β dans α, et en les munissant de l’ordre lexicographique qui donne le poids le plus fort aux valeurs lointaines (sur les grands éléments de β), on définit α^{β} (exponentiation ordinale, à ne pas confondre avec l’exponentiation cardinale qui sera définie ultérieurement). L’addition et la multiplication sont associatives, et 0 et 1 y sont respectivement élément neutre bilatère. On a de plus α(β + β′) = αβ + αβ′ et α^{β+β′} = α^{β}α^{β′}. Pour tout ordinal α, l’ordinal α + ω est le plus petit ordinal limite strictement supérieur à α.

Signalons au passage que le théorème du comptage utilise l’axiome de remplacement de manière essentielle : sans lui (i.e. avec seulement l’axiome de séparation), on ne peut pas montrer que ω2 est un ensemble — et de fait il est consistant que ω2 = On.

Le principe d’induction transfinie sert non seulement à démontrer des résultats sur les ensembles bien ordonnés, mais aussi à y définir des fonctions : de même que si dans un ensemble S on se donne a ∈ S et f: S → S on peut définir une fonction u: ℕ → S telle que u(0) = a et u(n + 1) = f(u(n)), et que cette fonction est unique — et d’ailleurs cette propriété caractérise ℕ = ω —, de même si W est bien ordonné, on peut définir une fonction W → S en supposant à chaque étape la fonction déjà définie à toutes les étapes précédentes. Pour être précis, si W est un ensemble bien ordonné et S un ensemble, et que pour chaque a ∈ W on a une fonction f_{a}: S^{s(a)} → S, où s(a) = {x ∈ W : x < a}, alors il existe une unique fonction u: W → S telle que pour chaque a ∈ W on ait u(a) = f_{a}(u|_{s(a)}). Ce principe de définition par induction transfinie peut même servir sur des classes : si W est une classe bien ordonnée dont tous les segments initiaux sont des ensembles, S une classe, et f une fonction classe définie sur toutes les fonctions de s(a) vers S (pour un certain a ∈ W), alors il existe une unique fonction classe u: W → S telle que u(a) = f(u|_{s(a)}) pour chaque a. Le principal problème dans cette assertion est la quantification existentielle sur une classe (u), mais en fait l’affirmation est quand même formulable dans ZF, puisqu’on peut expliciter u, et c’est la classe des couples (a, u_{a}) tels qu’il existe une fonction u: s(a) → S vérifiant u(x) = f(u|_{s(x)}) pour tout x ∈ s(a), et que de plus u_{a} = f(u).

Cette définition par induction transfinie est surtout utilisée pour définir des fonctions sur la classe des ordinaux. Par exemple, α + β peut se définir par induction transfinie de la façon suivante :

α + 0 = α
α + (β + 1) = (α + β) + 1
α + β = sup_{γ<β} α + γ si β est limite

(ou, plus succintement, α + β est le plus petit ordinal au moins égal à α et strictement supérieur à α + γ pour tout γ < β : ceci capture les trois cas). De même, pour la multiplication et l’exponentiation,

\{ \begin{matrix}α0 & = & 0 \\ α(β + 1) & = & αβ + α \\ αβ & = & sup_{γ<β} αγ si β est limite \end{matrix}  \{ \begin{matrix}α^{0} & = & 1 \\ α^{β+1} & = & α^{β}α \\ α^{β} & = & sup_{γ<β} α^{γ} si β est limite \end{matrix}

Tout ordinal α peut être muni d’une topologie définie par son ordre naturel. Les points d’accumulation de cet espace topologique sont les ordinaux limites inférieurs à α. L’espace est compact si et seulement si α est un ordinal successeur. Si α est limite et (γ_{ι})_{ι<α} est une famille d’ordinaux indicée par les éléments de α (appelée une α-séquence d’ordinaux), on dit comme d’habitude que γ_{ι} tend vers β lorsque ι tend vers α si et seulement si pour tous β_{1} < β < β_{2} il existe α_{0} < α tel que β_{1} < γ_{ι} < β_{2} dès que ι ≥ α_{0}. Lorsque β est successeur, cela signifie que la séquence est stationnaire de valeur β. Si la séquence est croissante, elle a toujours une limite (la borne supérieure de tous ses termes).

On dit qu’une α-séquence d’ordinaux (pour α limite) est continue ssi sa limite en tout ordinal limite β < α est précisément sa valeur en ce point. Une α-séquence à la fois continue et strictement croissante est appelée normale. Ces notions sont encore valables pour une séquence indicée par la classe On tout entière. Si (γ_{ι})_{ι∈On} est une On-séquence normale d’ordinaux, alors il existe des ordinaux ι arbitrairement grands tels que γ_{ι} = ι (en effet, si α est un ordinal, on considère α_{1} = γ_{α}, α_{2} = γ_{α_{1}} et ainsi de suite, et on appelle ι la limite de la séquence α_{n}). On en déduit que pour tout α il existe des β arbitrairement grands tels que α + β = β, que si α > 0 il existe des β arbitrairement grands tels que αβ = β, et que si α > 1 il existe des β arbitrairement grands tels que α^{β} = β. Le ι-ième point fixe de la fonction β ↦ ω^{β} est appelé ε_{ι}.

On définit un ordre sur On^{2} (la classe des couples d’ordinaux) de la façon suivante :

(α_{1}, α_{2}) < (β_{1}, β_{2}) ⇔ max(α_{1}, α_{2}) < max(β_{1}, β_{2})
ou max(α_{1}, α_{2}) < max(β_{1}, β_{2}) et α_{1} < β_{1}
ou max(α_{1}, α_{2}) < max(β_{1}, β_{2}) et α_{1} = β_{1} et α_{2} < β_{2}

Cet ordre est un bon ordre sur On^{2}, et tous les α^{2} pour α ∈ On en sont des segments initiaux. En notant Γ(α, β) l’ordinal du segment initial strict de (α, β) pour l’ordre en question, on en déduit une bijection Γ entre On^{2} et On, qui par ailleurs se restreint à une bijection entre α^{2} et γ(α) = Γ(α, α) pour tout ordinal α. La fonction α ↦ γ(α) est normale donc il existe des α arbitrairement grands tels que γ(α) = α, i.e. tels que Γ induise une bijection entre α^{2} et α. Le plus petit tel α est ω.

Si α est un ordinal limite, une partie S ⊆ α est dite \underline{cofinale} ssi pour tout γ < α il existe γ′ ∈ S tel que γ < γ′. Une β-séquence (γ_{ι})_{ι<β} strictement croissante d’éléments de α est dite cofinale ssi elle tend vers α : il y a évidemment correspondance bijective entre une partie cofinale S de α et une β-séquence cofinale, où β est l’ordinal de S comme ensemble bien ordonné. Le plus petit tel β s’appelle la cofinalité de α et se note cf α. On a cf α ≤ α et cf cf α = cf α puisque si β = cf α, disons (γ_{ι})_{ι<β} tend vers α, et que (η_{ι})_{ι<δ} tend vers β, alors (γ_{η_{ι}})_{ι<δ} tend vers α. Il est donc raisonable d’appeler régulier un ordinal limite α tel que cf α = α.

3.3 Cardinalités

Si X et Y sont deux ensembles, et qu’il existe une bijection entre X et Y, on dit que X et Y ont même cardinalité, ou qu’ils sont équipotents, et on note |X| = |Y |. Il s’agit là clairement d’une relation d’équivalence sur l’univers.

On pourrait utiliser l’axiome de régularité pour donner un sens à |X| (comme l’ensemble des ensembles équipotents à X et de rang minimal) ou encore l’axiome du choix (comme on le verra plus loin). Ce n’est pas absolument nécessaire : on peut se contenter de dire que les cardinalités ne sont qu’une commodité de langage, et traduire les assertions qui en parlent en termes d’ensembles.

Si X est équipotent à une partie de Y, on dit que la cardinalité de X est inférieure ou égale à celle de Y, et on note |X| ≤ |Y |. L’intérêt de cette définition est justifiée par le théorème bien connu suivant : Théorème 3.12 (de Cantor-Bernstein). Si |X| ≤ |Y | et |Y | ≤ |X| alors |X| = |Y |.

Autrement dit, les cardinalités sont partiellement ordonnées. On notera bien entendu |X| < |Y | lorsque |X| ≤ |Y | mais que |X| ≠ |Y | (i.e. non |X| = |Y |). On emploiera sans plus d’explications des signes tels que >, ≥, ≱ entre cardinalités.

Si un ensemble X se surjecte sur un ensemble Y, on dira que |Y | est une projection de |X| et on notera |Y | ⊴ |X|. Il va de soi que si |Y | ≤ |X| et que |Y | > 0 (i.e. Y ≠ ∅) alors |Y | ⊴ |X|.

La cardinalité de l’union de X et Y, dans la mesure où ceux-ci sont disjoints, ne dépend que des cardinalités de X et Y : cette cardinalité est notée |X| + |Y |. La cardinalité du produit cartésien de X et Y définit encore une opération sur les cardinalités, notée |X| |Y |. Enfin, in en va de même de la cardinalité de l’ensemble des fonctions de Y dans X, notée |X|^{|Y |}. On identifie un entier naturel (un élément de ω) à sa cardinalité : ainsi, |𝒫(Y)| = 2^{|Y |}.

On note de plus ℵ_{0} la cardinalité de ω. On dira qu’un ensemble X est \underline{fini} ssi |X| < ℵ_{0}, ou, ce qui revient au même, ssi |X| = n pour un certain n ∈ ω. On dira qu’un ensemble X est \underline{D-fini} (pour “Dedekind-fini”) ssi |X| ≱ ℵ_{0}, autrement dit ss’il n’existe pas de suite d’éléments deux à deux distincts de X; cela revient à exiger que |X| > |Y | pour toute partie Y ⊆ X autre que X.

Le résultat suivant est dû à Cantor : Théorème 3.13 (Cantor). Pour tout ensemble X, on a 2^{|X|} ⋬ |X| (et en particulier, 2^{|X|} ≰ |X|) ; comme de plus |X| ≤ 2^{|X|}, on en déduit |X| < 2^{|X|}.

Si α et β sont des ordinaux, il est évident que α ≤ β implique |α| ≤ |β|. Si κ est un ordinal tel que |α| < |κ| dès que α < κ, autrement dit que κ est le plus petit ordinal ayant sa cardinalité, alors on dit que κ est un \underline{cardinal}. Il est clair que tout ordinal, donc tout ensemble bien ordonné, est équipotent à un unique cardinal (et, réciproquement, tout ensemble équipotent à un cardinal peut être bien ordonné) : les cardinaux sont les cardinalités des ensembles bien ordonnés. Cela étant, pour κ un cardinal, on identifiera κ à |κ|. On vérifie facilement (whatever it’s worth for) que si |X| ⊴ κ, où κ est un cardinal, alors |X| ≤ κ.

Si X est un ensemble quelconque, on appellera \underline{nombre de Hartogs} de X le plus petit ordinal α tel qu’on n’ait pas |α| ≤ |X|, autrement dit le plus petit ordinal qui n’est pas l’ordinal d’un bon ordre sur une partie de X (un tel ordinal existe car les bons ordres sur des parties de X forment clairement un ensemble). Le nombre de Hartogs h(X) de X est clairement un cardinal. Si |X| était déjà un cardinal (autrement dit si X peut être bien ordonné), alors h(X) > |X|. Ceci montre que tout les cardinaux sont cofinaux dans les ordinaux (tout ordinal est majoré par un cardinal) : en particulier, pour tout cardinal κ il existe un plus petit cardinal supérieur à κ noté κ^{+}. Par ailleurs, il est facile de vérifier que le sup (en tant qu’ordinal) d’une famille de cardinaux est un cardinal.

Cela étant, on peut légitimement définir ℵ_{0} = ω, pour tout ordinal successeur α + 1, poser ℵ_{α+1} = ℵ_{α}^{+}, et pour tout ordinal limite α, poser ℵ_{α} = sup_{β<α} ℵ_{β}. Ainsi, les ℵ_{α} sont des cardinaux, et décrivent même tous les cardinaux infinis. Pour cette raison, lorsque la distinction entre cardinalités et cardinaux est cruciale, on préférera dire “un aleph” plutôt que “un cardinal” (infini), ce qui revient au même. En tant que séquence ordinale, la fonction α ↦ ℵ_{α} est normale (i.e. strictement croissante et continue), donc elle possède des points fixes arbitrairement grands. Un aleph ℵ_{α} dont l’indice α est un ordinal successeur (resp. limite) est appelé un cardinal successeur (resp. limite). Lorsqu’on veut parler de ℵ_{α} en tant qu’ordinal, on note plutôt ω_{α}; ainsi, ω_{0} = ω, et ω_{1} est le plus petit ordinal indénombrable, qui est aussi l’ordinal de l’ensemble des façons de bien ordonner ω.

Revenant à la bijection canonique Γ établie entre On^{2} et On, on a vu qu’il existait des ordinaux α arbitrairement grands tels que γ(α) = α, c’est-à-dire que Γ induit une bijection entre α^{2} et α. On montre assez facilement par induction transfinie sur γ que c’est le cas de ℵ_{γ} pour tout γ, i.e. que tout cardinal κ = ℵ_{γ} vérifie κ^{2} = κ (il s’agit là de l’exponentiation cardinale et non de l’exponentiation ordinale pour laquelle on a α^{2} > α pour tout α). Par conséquent, pour tout cardinaux κ et λ dont au moins un est infini, on a

κλ = κ + λ = max(κ, λ)

Tout cardinal infini est un ordinal limite. On a défini précédemment, pour tout ordinal limite α, la cofinalité cf α de α comme le plus petit ordinal limite β pour lequel il existe une β-séquence d’éléments de α (qu’on peut toujours supposer strictement croissante) qui tend vers α. Cette cofinalité est nécessairement un cardinal, car si cf α est en bijection avec un ordinal β, alors en composant une cf α-séquence de limite α avec la bijection sur β, on voit qu’il existe une β-séquence de limite α, donc que β ≥ cf α. Ainsi, tout ordinal régulier est un cardinal, et on parle donc plutôt de cardinaux réguliers. La réciproque n’est pas vraie : ℵ_{ω}, étant la limite de la ω-séquence (ℵ_{n})_{n<ω}, est un cardinal mais n’est pas régulier, et on dit alors que c’est un cardinal singulier. En fait, en l’absence de l’axiome du choix, on ne sait pas si on peut montrer la régularité d’un cardinal indénombrable quelconque (et on pense qu’on ne peut pas).

On a vu (théorème de Cantor) que 2^{κ} > κ pour toute cardinalité κ, et en particulier pour tout cardinal κ. Une autre inégalité importante dans ce genre est la suivante : Théorème 3.14. Si κ est un cardinal infini, alors κ^{cf κ} > κ.

Démonstration. On a clairement κ^{cf κ} ≥ κ. Il s’agit de montrer que cette inégalité est stricte. Supposons donc par l’absurde qu’on ait une énumération (f_{α})_{α<κ} des fonctions de cf κ dans κ. Soit (γ_{ι})_{ι<cf κ} une suite strictement croissante d’éléments de κ qui tend vers κ. On définit g: cf κ → κ comme suit. Si ι < cf κ alors les f_{α}(ι), pour α ≤ ι ne remplissent pas κ, et on appelle g(ι) le plus petit élément de κ qui diffère de tous ces éléments. La fonction g: cf κ → κ est alors différente de tous les f_{α}.

Cependant, en l’absence de l’axiome du choix, il y a peu d’autres choses qu’on puisse dire sur les κ^{λ}. Entre autres, on ne peut pas montrer que κ^{λ} soit un aleph.

Un cardinal est dit faiblement inaccessible ss’il est limite et régulier et indénombrable. Entre autres, puisque cf ℵ_{α} = cf α lorsque α est limite, un cardinal faiblement inaccessible λ doit vérifier ℵ_{λ} = λ. Le plus petit point fixe de la fonction α ↦ ℵ_{α} est la limite de la suite ℵ_{0}, ℵ_{ω}, ℵ_{ω_{ω}}, ℵ_{ω_{ωω}} , ⋯, et il est donc de cofinalité ω (donc il est “très loin” d’être inaccessible).

3.4 L’axiome du choix

L’axiome du choix à la conséquence très importante suivante : Théorème 3.15 (du bon ordre). Tout ensemble peut être bien ordonné.

Démonstration. Soit X un ensemble. D’après l’axiome du choix, on peut trouver une fonction f qui à toute partie non vide de X associe un élément de cette partie. On définit alors par induction sur l’ordinal ι la fonction x_{ι} = f(X \{x_{ξ} : ξ < ι}) tant que {x_{ξ} : ξ < ι} n’est pas tout X. Cette fonction est injective donc par l’axiome de remplacement elle ne peut pas s’étendre à tous les ordinaux, ce qui montre qu’il existe un ordinal α tel que {x_{ι} : ι < α} soit exactement X, et alors on a une bijection entre X et α, donc X est bien ordonnable.

La démonstration a été donnée pour montrer à quel point les ordinaux sont un outil puissant : on évite ici le recours au lemme de Zorn. D’ailleurs, grâce aux ordinaux, le lemme de Zorn se montre aussi très simplement : Lemme 3.16 (Kuratowski-Zorn). Soit P un ensemble partiellement ordonné dont toute chaîne (i.e. sous-ensemble bien ordonné) a un majorant. Alors P a un élément maximal.

Démonstration. Supposons par l’absurde que P n’ait pas d’élément maximal. Soit x_{0} un élément de P. On définit une séquence x_{ι} d’éléments de P comme suit : x_{ι+1} est un élément de P strictement supérieur à x_{ι} (qui existe car x_{ι} n’est pas maximal), et si ι est limite alors x_{ι} est un majorant strict de la chaîne {x_{ξ} : ξ < ι}. L’axiome du choix permet de faire ces choix. On a alors une fonction injective des ordinaux dans P, ce qui est une contradiction.

Grâce à l’axiome du choix, il est possible d’identifier cardinalités et cardinaux : toute cardinalité infinie est un aleph (c’est précisément le contenu du théorème du bon ordre). Ceci a plusieurs conséquences agréables. Premièrement, deux cardinalités sont toujours comparables : autrement dit, si X et Y sont deux ensembles, il existe toujours soit une injection de X dans Y soit une injection de Y dans X. Le fait d’être fini ou D-fini coïncide. Ensuite, grâce à ce qu’on a déjà montré sur les cardinaux, on voit que la somme ou le produit de deux cardinalités dont une au moins est infinie est le maximum de ces deux cardinalités. Entre autres, X^{2} est équipotent à X lorsque X est infini. Aussi, dès que X ≠ ∅, dire que |X| ⊴ |Y | ou |X| ≤ |Y | revient au même : toute surjection admet une section. Enfin, l’axiome du choix permet de montrer le résultat suivant : Proposition 3.17. Le cardinal de ⋃_{i∈I} X_{i} est majoré par |I| sup_{i∈I} |X_{i}|. Corollaire 3.18. Tout cardinal successeur, i.e. tout ℵ_{α+1}, est régulier.

(Sans quoi ω_{α+1} serait la réunion de au plus ℵ_{α} ensembles de cardinal au plus ℵ_{α}, ce qui contredit la proposition vu que ℵ_{α}^{2} = ℵ_{α}.)

En particulier, le plus petit cardinal singulier est ℵ_{ω}, qui est de cofinalité ω.

Par ailleurs, l’axiome du choix permet de définir un sens à la somme ou au produit d’une famille quelconque de cardinaux, comme suit. Si κ_{i} sont des cardinaux, X_{i} des ensembles deux à deux disjoints de cardinal κ_{i}, alors le cardinal de ⋃_{i} X_{i} ne dépend pas du choix des X_{i} et on le note ∑_{i} κ_{i}. De même, le produit cartésien permet de définir le produit d’une famille de cardinaux. Pour les calculer, on dispose du lemme suivant : Lemme 3.19. Soit (κ_{ι})_{ι<λ} une λ-séquence de cardinaux tous non nuls, où λ est un cardinal infini. Alors ∑_{ι<λ} κ_{ι} = λ sup_{ι<λ} κ_{ι}. Si de plus la séquence (κ_{ι}) est croissante alors ∏_{ι<λ} κ_{ι} = (sup_{ι<λ} κ_{ι})^{λ}.

On a par ailleurs le résultat suivant : Théorème 3.20 (König). Si κ_{i} < λ_{i} pour tout i ∈ I alors ∑_{i∈I} κ_{i} < ∏_{i∈I} λ_{i}.

En particulier, comme 1 < 2, on retrouve κ < 2^{κ}, et en écrivant κ comme somme de cf κ cardinaux κ_{i} < κ, on retrouve κ < κ^{cf κ}.

3.5 Exponentiation cardinale

On suppose toujours vérifié l’axiome du choix.

L’axiome du choix décrète péremptoirement que κ^{λ} est un aleph (i.e. peut être bien ordonné). La question naturelle est alors de se demander quelle est sa valeur précise. On ne peut pas répondre à cette question : en fait, on ne peut même pas dire ce que vaut 2^{ℵ_{0}}. On peut cependant trouver certains résultats positifs. On sait déjà que 2^{ℵ_{0}} > ℵ_{0}, et donc que 2^{ℵ_{0}} ≥ ℵ_{1} (cette dernière inégalité fait appel à l’axiome du choix). D’autre part, par exemple, 2^{ℵ_{0}} ne peut pas être ℵ_{ω} puisque (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}^{2}} = 2^{ℵ_{0}} tandis que (ℵ_{ω})^{ℵ_{0}} > ℵ_{ω} car cf ℵ_{ω} = ω.

Si on connait les fonctions κ ↦ 2^{κ} (la fonction du continu) et κ ↦ ℷ(κ) = κ^{cf κ} (la fonction gimel), alors on peut calculer κ^{λ} pour tous κ et λ d’après le théorème suivant :

Théorème 3.21 (calcul inductif de ℵ_{α}^{ℵ_{β}}). Soit ℵ_{β} un cardinal infini fixé. Alors ℵ_{α}^{ℵ_{β}} peut être calculé inductivement comme suit :

1. Si α ≤ β alors ℵ_{α}^{ℵ_{β}} = 2^{ℵ_{β}}.

2. Si pour un certain γ < α on a ℵ_{γ}^{ℵ_{β}} ≥ ℵ_{α}, alors ℵ_{α}^{ℵ_{β}} = ℵ_{γ}^{ℵ_{β}}.

3. Si α > β et ℵ_{γ}^{ℵ_{β}} < ℵ_{α} pour tous γ < α, alors

(a) Si cf ℵ_{α} > ℵ_{β} (entre autres si ℵ_{α} est régulier), alors ℵ_{α}^{ℵ_{β}} = ℵ_{α}.

(b) Si cf ℵ_{α} ≤ ℵ_{β} alors ℵ_{α}^{ℵ_{β}} = ℵ_{α}^{cf ℵ_{α}}. En fait, on montre même que la fonction du continu est elle-même déterminée par la fonction

gimel.

La question est alors de savoir quels comportements sont possibles pour la fonction du continu et la fonction gimel, moyennant les axiomes de la théorie des ensembles. L’hypothèse la plus simple, et aussi la plus célèbre, et la suivante : Hypothèse généralisée du continu 3.22. Pour tout cardinal κ, on a 2^{κ} = κ^{+}.

Cette hypothèse détermine alors complètement la fonction gimel et du même coup toute l’exponentiation des cardinaux.

Théorème 3.23. Sous l’hypothèse généralisée du continu, ℵ_{α}^{ℵ_{β}} vaut – ℵ_{α} si ℵ_{β} < cf ℵ_{α}.

– ℵ_{α+1} si cf ℵ_{α} ≤ ℵ_{β} ≤ ℵ_{α}.

– ℵ_{β+1} si ℵ_{α} ≤ ℵ_{β}.

En fait, l’hypothèse du continu est indépendante des axiomes de la théorie des ensembles. Mais on a beaucoup plus : il est consistant, par exemple, que 2^{ℵ_{0}} = ℵ_{42}, 2^{ℵ_{1}} = ℵ_{42}, 2^{ℵ_{2}} = ℵ_{ω_{1729}} et 2^{ℵ_{3}} = ℵ_{ω_{1729}+ε_{0}^{2}+666}. Le théorème précis est le théorème d’Easton, qui affirme que toute fonction croissante F des cardinaux réguliers vers les cardinaux, qui vérifie cf F(κ) > κ pour tout κ, est susceptible d’“être” la fonction du continu. (Cet énoncé est un peu vague : on renvoie au Jech pour une formulation précise.) La fonction du continu (ou la fonction gimel) sont beaucoup plus difficiles à contrôler sur les cardinaux singuliers. Par exemple, si l’hypothèse du continu généralisée est vraie sur tous les cardinaux inférieurs à ℵ_{ω_{1}}, alors elle est vraie en ℵ_{ω_{1}} (un théorème de Silver, théorème 23 dans le Jech). Ceci est encore vrai pour ℵ_{ω} en l’absence d’une hypothèse très forte, l’existence de 0^{♯} (qui est par exemple impliquée par l’existence d’un cardinal mesurable). D’autre part, si la fonction du continu est stationnaire en-dessous d’un cardinal singulier, alors sa valeur sur ce cardinal est la valeur à laquelle elle stationne (théorème de Bukovský-Hechler).

3.6 L’axiome de régularité

L’axiome de régularité permet une forme d’induction : si C est une classe telle que x ⊆ C ⇒ x ∈ C (autrement dit, C contient un ensemble x dès qu’elle contient tous les éléments de x), alors C = V (induction bien-fondée).

Comme tout principe d’induction, l’induction bien-fondée donne aussi un principe de définition par induction bien-fondée. Précisément : si S est une classe, et f une fonction classe de V × V vers S, alors il existe une unique fonction classe u: V → S telle que u(x) = f(x, u|_{x}) pour chaque x. Autrement dit, on peut, quand on définit une fonction sur l’univers (ou sur une classe ou un ensemble transitif en général) supposer qu’elle est déjà définie sur tous les éléments de x avant de la définir sur x.

Comme application, on définit une application “rang” de V vers les ordinaux par

rg(x) = sup{rg y + 1 : y ∈ x}

Autrement dit, le rang de x est le plus petit ordinal strictement supérieur au rang de tous les éléments de x. (On trouve parfois la définition alternative rg(x) = sup{rg y : y ∈ x} + 1, qui est toujours de 1 supérieure à la définition que nous donnons.) On a ainsi rg(∅) = 0, rg({∅}) = 1, et plus généralement rg(α) = α pour tout ordinal α, rg(𝒫(x)) = rg(x) + 1.

Si C est une classe, on peut définir une classe ℋ C, par induction bien-fondée : on pose ℋ C = {x ∈ C: x ⊆ ℋ C}. Il s’agit là de la plus grande classe transitive contenue dans C : on dit que ses éléments sont les ensembles “hériditairement dans C” (ils sont dans C, ainsi que tous leurs éléments, les éléments de leurs éléments et ainsi de suite).

(Un autre exemple, plus amusant, de définition par induction bien-fondée est la fonction de Grundy : sa valeur sur un ensemble x est le plus petit ordinal qui n’est pas la fonction de Grundy d’un élément de x. La fonction de Grundy de x vaut alors 0 si et seulement si le jeu dans lequel chaque joueur tour à tour choisit un élément de l’ensemble proposé par le précédent, en commençant par x, est gagnant pour le deuxième joueur — i.e. est un jeu nul au sens de Conway. L’axiome de régularité assure précisément que ce jeu termine toujours.)

Pour tout ordinal α, on appelle V_{α} l’ensemble des ensembles dont le rang est strictement inférieur à α. Pour montrer qu’il s’agit bien d’un ensemble, il suffit de remarquer que V_{α} peut encore se définir par induction transfinie sur α par

V_{0} = ∅
V_{α+1} = 𝒫(V_{α})
V_{α} = ⋃_{β<α} V_{β} si β est limite

On note V_{∞} = ⋃_{α∈On} V_{α} : cette classe est bien définie puisque les V_{α} peuvent se définir uniformément pour tout α par une formule. L’axiome de régularité montre que V_{∞} = V. En fait, les V_{α} et V_{∞} peuvent se définir même en l’absence de l’axiome de régularité, et l’axiome de régularité est justement équivalent à l’assertion V_{∞} = V.

L’axiome de régularité a une vague similarité avec l’axiome du choix en ce sens : il permet pour chaque classe de choisir un ensemble d’éléments de celle-ci qui est non vide si la classe était non vide. En effet, si C est une classe, on peut appeler Ĉ l’ensemble des éléments de C ayant rang minimal. En quelque sorte, on choisit donc “un petit nombre” (seulement un ensemble !) d’éléments de C. Ceci permet par exemple de définir les cardinalités en l’absence de l’axiome du choix : on appelle cardinalité d’un ensemble A l’ensemble de tous les ensembles équipotents à A et ayant rang minimal pour cette propriété.

4 Modèles de la théorie des ensembles

Un modèle de la théorie des ensembles est bien entendu un ensemble 𝔐 muni d’une relation ε tel que 𝔐 ⊨ Φ pour tout axiome Φ de la théorie ZF (ou ZFC selon le cas). Il faut remarquer que l’assertion “(𝔐, ε) est un modèle de ZF” est traduisible dans ZF (bien qu’il y ait une infinité d’axiomes de ZF). D’après le théorème d’incomplétude de Gödel, on ne peut pas montrer dans ZF l’existence d’un couple (𝔐, ε) qui soit un modèle de ZF.

On peut cependant généraliser la définition d’un modèle aux classes : si 𝔐 est une classe et ε est une relation binaire dessus, on peut définir 𝔐 ⊨ Φ de la façon évidente, et définir ce que signifie le fait que (𝔐, ε) soit un modèle de ZF. Le cas le plus évident est celui où la classe 𝔐 est précisément la classe universelle V, et où ε est justemement la relation ∈ sur celle-ci. Ainsi, ZF n’est pas assez fort pour montrer qu’un ensemble est modèle de ZF, mais il peut montrer qu’une classe est modèle de ZF (et, comme on le verra, V n’est pas le seul exemple en général).

Il faut toutefois noter le fait important suivant : bien que pour une formule Φ quelconque fixée, l’assertion “𝔐 ⊨ Φ” soit toujours traduisible dans ZF, elle ne l’est pas forcément uniformément en Φ lorsque 𝔐 est une classe, c’est-à-dire que pour une numérotation de Gödel Φ_{n} des formules, l’assertion “𝔐 ⊨ Φ_{n}” (dans laquelle n est une variable libre) ne peut pas se traduire dans le langage de ZF.

On prêtera une attention tout particulière aux modèles transitifs de la théorie des ensembles, c’est-à-dire aux modèles (𝔐, ε) dans lesquels 𝔐 est un ensemble ou une classe transitif, et ε est la relation ∈ sur cette classe. C’est le cas entre autres de V.

On dit qu’une relation ε sur une classe 𝔑 est \underline{bien-fondée} si et seulement si

– Pour tout x ∈ 𝔑 la classe ext_{ε}(x) des y ∈ 𝔑 tels que yεx est un ensemble.

– Si S ⊆ 𝔑 est un ensemble quelconque, alors il existe x ∈ S tel que ext_{ε}(x)∩S = ∅ (autrement

dit, un x ∈ S minimal pour la relation ε). On dit de plus que la relation ε est \underline{extensionnelle} ssi ext_{ε}(x) = ext_{ε}(y) implique x = y pour tous x, y ∈ 𝔑 (autrement dit, ssi ((N), ε) modélise l’axiome d’extension). Ainsi, l’axiome de régularité équivaut à l’affirmation que la classe V munie de la relation ∈ est bien-fondée, et l’axiome d’extension à l’affirmation que cette relation est extensionnelle. Réciproquement, on a le résultat suivant : Théorème 4.1 (d’écrasement (Mostowski)). Soit 𝔑 une classe munie d’une relation binaire ε bien-fondée et extensionnelle. Alors il existe une classe transitive 𝔐 unique telle que les structures (𝔑, ε) et (𝔐, ∈) soient isomorphes. De plus, l’isomorphisme entre celles-ci est unique.

Si Φ est une formule, comportant éventuellement des variables libres, et 𝔐 une classe transitive, on notera Φ^{𝔐} la formule obtenue en restreignant tous les quantificateurs de Φ à 𝔐. Par exemple, si Φ est la formule ∀z((∀t ∈ z(t ∈ x)) ⇒ z ∈ y), la formule Φ^{𝔐} sera ∀z ∈ 𝔐((∀t ∈ z(t ∈ x)) ⇒ z ∈ y) (il n’est pas nécessaire de restreindre le second quantificateur puisqu’il est déjà restreint à z, qui est un élément donc une partie de 𝔐). On a alors 𝔐 ⊨ Φ si et seulement si Φ^{𝔐}. Autrement dit, il est très facile de tester si une formule est vérifiée dans une classe transitive. Ceci est d’autant plus facile lorsque la formule Φ ne comporte que des quantificateurs déjà restreints (on dit que Φ est une formule restreinte), car alors on a 𝔐 ⊨ Φ si et seulement si Φ est vraie (i.e. V ⊨ Φ). On dit que les formules restreintes sont “absolues”. Par exemple, en prenant pour Φ la formule ∀z ∈ x(z ∈ y), on voit que si 𝔐 est une classe transitive et x, y ∈ 𝔐, on a 𝔐 ⊨ x ⊆ y si et seulement si x ⊆ y.

Ceci nous permet de voir qu’une classe transitive 𝔐 modélise l’axiome de la paire si et seulement si pour tous x, y ∈ 𝔐 on a {x, y} ∈ 𝔐. De même, 𝔐 modélise l’axiome de l’union si et seulement si pour tout x ∈ 𝔐 on a ⋃ x ∈ 𝔐. Et 𝔐 modélise l’axiome de l’infini si et seulement si ω ∈ 𝔐. En ce qui concerne l’axiome des parties, il faudra faire plus attention : 𝔐 le modélise si et seulement si pour tout x ∈ 𝔐 on a 𝒫(x) ∩ 𝔐 ∈ 𝔐.

On rappelle qu’on a défini précédemment la classe V_{∞} des ensembles réguliers. Au sujet de cette classe, on montre, sans utiliser l’axiome de régularité Théorème 4.2. La classe V_{∞} est un modèle de ZF (et de ZFC si l’axiome du choix tient) avec l’axiome de régularité. Entre autres, l’axiome de régularité est consistant avec les autres axiomes de la théorie des ensembles.

Démonstration. Toute classe transitive modélise l’axiome d’extension. Si α est soit un ordinal limite soit ∞, alors V_{α} contient {x, y} dès qu’il contient x et y, donc V_{α} modélise l’axiome de la paire. De même V_{α} modélise alors l’axiome de l’ensemble des parties puisque si x ∈ V_{β}, on a 𝒫(x) ∩ V_{β} = 𝒫(x) ∈ V_{β+1}. Pour tout α ∈ On ∪{∞}, la classe V_{α} modélise l’axiome de l’union.

Pour l’axiome de séparation, il s’agit de montrer que si φ(x, x′) est une formule (on peut se contenter de deux variables libres) et y ∈ V_{α}, alors pour tout x′ ∈ V_{α} on a {x ∈ y : V_{α} ⊨ φ(x, x′)} ∈ V_{α}. Mais ceci est évidemment vrai (pour tout α ∈ On ∪{∞}) puisque l’ensemble en question est une partie de y.

L’axiome de l’infini est vérifié dès que α > ω. L’axiome de régularité est vérifié pour tout α. Le cas de l’axiome du choix (si nécessaire) est également facile.

Reste l’axiome de remplacement. Si x ∈ V_{α} et que y est un ensemble obtenu en remplaçant chaque élément de x par un certain élément de V_{α}, on voudrait montrer que y est dans V_{α}. Ceci est clairement le cas pour α = ∞ (puisqu’un ensemble est régulier si et seulement si tous ses éléments sont réguliers). C’est encore le cas pour α = ω (puisque x est alors fini et que le rang de y est donc le sup d’un ensemble fini de nombres finis). Plus généralement, si κ est un cardinal régulier et tel que 2^{λ} < κ dès que λ < κ, alors α = κ convient (on dit que κ est régulier et fortement limite, ou encore fortement inaccessible).

On notera au passage que V_{ω} (l’ensemble des ensembles hériditairement finis) est un modèle de tous les axiomes de la théorie des ensembles sauf l’axiome de l’infini, ce qui montre que l’axiome de l’infini est indépendant des autres axiomes. Et que V_{ω2} est un modèle de tous les axiomes sauf l’axiome de remplacement, ce qui montre que l’axiome de remplacement est indépendant des autres axiomes. La classe V_{∞} est un modèle de ZF(C), et c’est aussi le cas des ensembles V_{κ} où κ est un cardinal fortement inaccessible (voir plus haut). Comme on ne peut pas montrer l’existence d’un modèle ensemble de la théorie des ensembles, ceci montre que l’existence de cardinaux inaccessibles n’est pas une conséquence de ZF(C). En fait, on montre assez facilement que si κ est le premier cardinal inaccessible, alors V_{κ} est un modèle de “ZF + il n’existe aucun cardinal fortement inaccessible”. Si IC désigne l’axiome “il existe un cardinal fortement inaccessible”, on voit que ZF+IC montre la consistance de ZF ; or ZF+IC ne peut pas montrer la consistance de ZF+IC d’après le théorème d’incomplétude de Gödel ; ainsi, la consistance de ZF+IC ne peut pas être démontrée, même relativement à celle de ZF.

À partir de maintenant, nous supposerons sans aucun scrupule vérifié l’axiome de régularité. On termine par le résultat suivant :

Théorème 4.3 (principe de réflexion). Soient φ_{i}(x_{1}, …, x_{n}), pour i = 1, …, m des formules. Alors pour chaque ensemble M_{0} il existe un ensemble M ⊇ M_{0} tel que

∀i∀x_{1}, …, x_{n}(((M, ∈) ⊨ φ_{i}(x_{1}, …, x_{n})) ⇔ φ_{i}(x_{1}, …, x_{n}))

(on dit que M reflète les formules φ_{1}, …, φ_{m}).

1. De plus, on peut choisir un tel ensemble M transitif. Plus précisément, on peut trouver α un ordinal limite tel que V_{α} ⊇ M_{0} reflète les formules φ_{1}, …, φ_{m}.

2. Supposant l’axiome du choix, on peut trouver M de sorte que card M ≤ card M_{0} + ℵ_{0}. En

particulier, il existe M dénombrable qui reflète φ_{1}, …, φ_{m}. (On peut choisir M soit transitif soit dénombrable, mais pas les deux à la fois.)

En particulier, si σ_{1}, …, σ_{m} sont des formules closes vraies dans l’univers, on peut trouver un modèle ensemble de celles-ci. A fortiori, la théorie ZF n’est pas finiment axiomatisable (sans quoi on aurait démontré l’existence d’un modèle ensemble de celle-ci).

Le principe de réflexion est extrêmement puissant quand on le combine à la remarque que toute démonstration mathématique n’utilise qu’un nombre fini d’axiomes.

Le principe de réflexion est à mettre en parallèle avec le théorème de Löwenheim-Skolem : on construit en quelque sorte un sous-modèle élémentaire de l’Univers pour ce qui concerne les fonctions φ_{1}, …, φ_{m}. La démonstration en est semblable : pour le deuxième point (utilisant l’axiome du choix), on choisit des fonctions de Skolem pour toutes les formules φ_{m} (écrites sans le quantificateur universel) et toutes leurs sous-formules. En l’absence d’axiome du choix, on utilise l’axiome de régularité pour choisir un ensemble de témoins pour chaque formule existentielle (plutôt qu’un seul témoin comme dans une fonction de Skolem). On renvoie au Jech pour plus de détails.