1. Axiomes de ZF. La version la plus courante de la théorie des ensembles est celle qui fut proposée en 1908 par Ernst Zermelo, à laquelle on rajoute un axiome (Schéma Axiome de Remplacement) dû à Abraham Fraenkel et Thoralf Skolem. Cette théorie est désignée par le sigle ZF sans l’Axiome du Choix, par ZFC si on y adjoint l’Axiome du Choix.

Le langage de la théorie des ensembles comporte (outre l’égalité) deux symboles : une relation binaire notée ∈, et un symbole de constante (parfois omis) noté ∅. La relation x ∈ y se lit “x est un élément de y”, ou bien “x est dans y”. Le symbole ∅ s’appelle l’ensemble vide.

Il est habituel d’utiliser des “quantificateurs restreints” : ∀t ∈ x(P (t)) signifie ∀t((t ∈ x) ⟹ (P (t))), et ∃t ∈ x(P (t)) signifie ∃t((t ∈ x) ∧ (P (t))).

Les axiomes sont :

Axiome d’Extension. Si x et y ont les mêmes éléments alors x = y.

∀x∀y((∀z(z ∈ x ⟺ z ∈ y)) ⟹ (x = y))

Discussion : On notera x ⊆ y (ou y ⊇ x) pour dire que tous les éléments de x sont dans y, i.e. ∀z(z ∈ x ⟹ z ∈ y) : on dit alors que x est une \underline{partie} de y, ou que x est un \underline{sous-ensemble} de y. ou que x est \underline{inclus} dans y. L’Axiome d’Extension s’écrit alors

∀x∀y(((x ⊆ y) ∧ (x ⊇ y)) ⟹ (x = y))

Axiome du Vide. L’ensemble vide n’a aucun élément.

∀x(¬x ∈ ∅)

Axiome des Paires. Donnés deux ensembles x et y il existe un ensemble ayant x et y pour seuls éléments.

∀x∀y∃z∀t((t ∈ z) ⟺ ((t = x) ∨ (t = y)))

Discussion : Cet ensemble (unique par Extension) sera not’e {x, y}. Dans le cas où x = y, on note {x}. On notera de plus (x, y) = {{x}, {x, y}} (et on dit qu’il s’agit du couple dont la première coordonnée est x et la seconde y). On vérifie aisément que (x, y) = (x′, y′) ssi x = x′ et y = y′. On définit également (x, y, z) = ((x, y), z), et plus généralement, par récurrence, (x_{1}, …, x_{n}) = ((x_{1}, …, x_{n−1}), x_{n}).

Axiome de l’Union. Donné un ensemble x il existe un ensemble y dont les éléments sont exactement les éléments des éléments de x.

∀x∃y∀z((z ∈ y) ⟺ (∃t ∈ x(z ∈ t)))

Discussion : Cet ensemble (unique par Extension) se note ⋃ x ou bien ⋃_{t∈x} t. On dira qu’il s’agit de l’\underline{union} des éléments de x. Si x = \{u, v\}, on notera u ∪ v, et on dit qu’il s’agit de l’union de u et de v.

Schéma Axiome de Sélection. Soit φ(t, p) un prédicat ayant (au plus) deux variables libres. Pour tous ensembles p et x il existe un y dont les éléments sont exactement les éléments t de x vérifiant φ(t, p).

∀p∀x∃y∀t((t ∈ y) ⟺ ((t ∈ x) ∧ (φ(t, p))))

Discussion : On notera qu’il s’agit là d’une infinité dénombrable d’axiomes, un pour chaque prédicat φ. L’ensemble (unique par Extension) ainsi défini se note {t ∈ x: φ(t, p)}. On trouve souvent le Schéma Axiome de Sélection énoncé avec plusieurs paramètres p_{1}, …, p_{n} au lieu d’un. Ces deux formes sont équivalentes car

{t ∈ x: φ(t, p_{1}, …, p_{n})} = {t ∈ x: φ̂(t, (p_{1}, …, p_{n}))}

où φ̂(t, p) vaut par définition :

∃p_{1} ⋯ ∃p_{n}((p = (p_{1}, …, p_{n})) ∧ φ(t, p_{1}, …, p_{n}))

Si x est un ensemble non vide, u un élément de x, on définit l’\underline{intersection} des éléments de x, notée ⋂ x ou ⋂_{t∈x} t par :

{z ∈ u: ∀t ∈ x(z ∈ t)}

Cet ensemble est unique par Extension, et ne dépend pas du choix de u. Lorsque x = {u, v}, on note u ∩ v. Lorsque u ∩ v = ∅, on dit que u et v sont \underline{disjoints}.

Axiome des Parties. Donné un ensemble x il existe un ensemble y dont les éléments sont les parties de x.

∀x∃y∀t((t ∈ y) ⟺ (t ⊆ x))

Discussion : Cet ensemble (unique par Extension) se note P(x) et s’appelle \underline{ensemble des parties} de x.

Axiome de l’Infini. Il existe un ensemble contenant ∅ et stable par t ↦ t ∪ {t}.

∃x((∅ ∈ x) ∧ (∀t ∈ x(t ∪ {t} ∈ x)))

Discussion : Un tel ensemble s’appelle \underline{inductif}. On vérifie immédiatement qu’une intersection quelconque d’ensembles inductifs est inductive. Il existe donc un plus petit ensemble inductif. On le notera ω : ainsi, ω est inductif, et si I ⊆ ω est inductif alors I = ω (“postulat de récurrence”). L’ensemble ω se note aussi ℕ, et ses éléments s’appellent les \underline{entiers naturels} ou les \underline{ordinaux finis}.

Schéma Axiome de Remplacement. Soit ψ(u, v, p) un prédicat ayant (au plus) trois variables libres. Pour tout ensemble p, si ψ(u, v, p) est fonctionnel^{∗} en v alors pour tout ensemble x il existe un y dont les éléments sont exactement les images des éléments de x.

\begin{matrix}∀p( & (∀u∀v∀w(((ψ(u, v, p)) ∧ (ψ(u, w, p))) ⟹ (v = w))) \\ ⟹ & (∀x∃y∀v((v ∈ y) ⟺ (∃u ∈ x(ψ(u, v, p)))))) \end{matrix}

Discussion : Comme pour le Schéma Axiome de Sélection, on peut en déduire une version à plusieurs paramètres. On remarquera que le Schéma Axiome de Sélection découle du Schéma Axiome de Remplacement : il suffit pour le voir de considérer le prédicat ψ(u, v, p) donné par (u = v) ∧ (φ(u, p)), lequel est clairement fonctionnel en v.

Axiome de Régularité. Tout ensemble x non vide a un élément y qui lui est disjoint.

∀x((x ≠ ∅) ⟹ (∃y ∈ x(y ∩ x = ∅)))

Discussion : Cet axiome n’est jamais utilisé en mathématique, mais il est très utile en métamathématique. Il ne coûte rien de l’ajouter à notre liste, puisqu’on peut (aisément) montrer qu’il est consistant relatif aux autres. Entre autres conséquences de l’Axiome de Régularité, on ne peut pas avoir t ∈ t (sans quoi l’ensemble {t} ne vérifierait pas l’axiome), ni, plus généralement,

t_{0} ∋ t_{1} ∋ t_{2} ∋ ⋯

(considérer l’ensemble {t_{0}, t_{1}, …}).

Le dernier axiome, l’Axiome du Choix, ne fait pas partie de la théorie ZF, mais de ZFC. On peut l’énoncer ainsi :

Axiome du Choix. Si x est un ensemble dont les éléments sont non vides et deux à deux disjoints il existe un ensemble y dont l’intersection avec tout élément de x est réduite à un singleton.

∀x(((∀t ∈ x(t ≠ ∅)) ∧ (∀u ∈ x∀v ∈ x(u ∩ v = ∅))) ⟹ (∃y∀t ∈ x∃z(t ∩ y = {z})))

Discussion : Cet axiome est un peu particulier, puisqu’il affirme l’existence d’un ensemble sans le définir, i.e. d’un ensemble qui n’est pas unique^{†}. Il a donné lieu à bien des controverses au XIXème siècle (notamment de la part de l’école française) ; en tout cas, il est assez important de savoir ce qu’on peut et ce qu’on ne peut pas faire sans l’Axiome du Choix.

Dans toute la suite, nous signalerons explicitement les résultats qui dépendent de l’Axiome du Choix.

∗ Cela signifie que pour tout u il existe au plus un v (l’\underline{image} de u) tel que ψ(u, v, p). † Il est vrai que c’était aussi le cas de l’Axiome de Régularité. D’ailleurs, ces deux axiomes ont quelques

points communs.

2. Bon ordre et ordinaux.

Nous supposons connues toutes les notions classiques de la théorie naïve des ensembles (relation, relation d’équivalence, relation d’ordre, fonctions, injections, surjections, bijections, etc.)

On dira qu’une relation d’ordre ≤ sur un ensemble W est une relation de \underline{bon ordre} (ou que W est \underline{bien ordonné} par ≤) ssi toute partie non vide de W admet un plus petit élément pour ≤. En considérant les parties à deux éléments, on voit aussitôt que ≤ est un ordre total.

Si T est un ensemble totalement ordonné, alors pour tout a ∈ T on note s(a) = {t ∈ T : t < a} (le \underline{segment initial} de a).

Le théorème suivant, bien que trivial, est fondamental :

Théorème de l’induction transfinie. Soit W un ensemble bien ordonné, et I ⊆ W tel que pour tout a ∈ W, s(a) ⊆ I ⟹ a ∈ I. Alors I = W.

Démonstration : Dans le cas contraire, considérer le plus petit élément a de W \ I.

Il existe également un théorème permettant la définition par induction transfinie, que nous laissons le soin au lecteur de formuler et de démontrer.

Un ensemble T est dit \underline{transitif} ssi T ⊆ P(T), soit ∀x ∈ T (x ⊆ T). Il s’ensuit que la relation ∈ restreinte à T est transitive.

Un \underline{ordinal} est un ensemble transitif α tel que pour tous x, y ∈ α distincts on ait x ∈ y ou bien y ∈ x.

Proposition. Soit α un ordinal. Alors la relation ∈ restreinte à α est une relation de bon ordre strict sur α.

Démonstration : Elle est transitive par définition. D’après l’Axiome de Régularité, elle est irréflexive et antisymétrique. Il s’agit donc d’une relation d’ordre strict. Par définition, cet ordre est total. Soit enfin A ⊆ α non vide. D’après l’Axiome de Régularité, il existe x ∈ A tel que x∩A = ∅. Or ceci signifie précisément que x est minimal dans A ; comme l’ordre est total, x est le plus petit élément de A, et α est bien ordonné.

L’importance des ordinaux vient du théorème suivant :

Théorème. Tout ensemble bien ordonné est isomorphe (en tant qu’ensemble ordonné) à un unique ordinal. De plus, l’isomorphisme en question est unique.

(Ce théorème se montre par induction transfinie, et c’est facile, quoique assez pénible.)

Pour deux ordinaux α, β distincts, il revient au même de dire que α ∈ β, que α ⊂ β, ou que α est isomorphe à un segment initial de β. Lorsque l’une quelconque de ces affirmations est vérifiée, on dit que α est inférieur à β, et on note α < β. Un ordinal n’est autre que l’ensemble des ordinaux strictement plus petits que lui.

Tout ensemble d’ordinaux admet un plus petit élément, qui n’est autre que l’intersection de ses éléments, une borne supérieure (le plus petit de ses majorants), qui n’est autre que l’union de ses éléments, et une borne supérieure stricte (le plus petit de ses majorants stricts). La borne supérieure stricte de {α}, où α est un ordinal, est le plus petit ordinal strictement supérieur à α : on vérifie sans mal qu’il s’agit de α ∪ {α}, on le note α + 1, et on l’appelle \underline{successeur} de α. Ainsi, la borne supérieure stricte d’un ensemble d’ordinaux n’est autre que la borne supérieure des successeurs des ordinaux en question. Un ordinal qui n’est pas le successeur d’un autre ordinal s’appelle un \underline{ordinal limite}.

Le plus petit ordinal est ∅, que l’on note aussi 0. Son successeur est {∅}, que l’on note aussi 1. Son successeur est {∅, {∅}}, que l’on note aussi 2. Et ainsi de suite. Le plus petit ordinal successeur autre que 0 est ω.

On définit des opérations sur les ordinaux par induction transfinie sur β : l’\underline{addition} par :

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

la \underline{multiplication} par :

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

et l’\underline{exponentiation ordinale} par :

α^{[β]} = \{ \begin{matrix}1 si β = 0 \\ α^{[γ]}α si β = γ + 1 \\ sup_{γ<β} α^{[γ]} si β est limite \end{matrix}

Ces opérations ne jouissent pas des propriétés sympathiques qu’on leur connaît sur les naturels. En particulier, l’addition et la multiplication ne sont pas commutatives en général. Certaines propriétés sont néanmoins valables, par exemple, l’associativité de l’addition et de la multiplication, la neutralité (à gauche et à droite) de 0 pour l’addition et de 1 pour la multiplication et la distributivité à gauche de la multiplication sur l’addition (i.e. α(β + γ) = αβ + αγ).

3. Cardinaux et alephs. Si A et B sont deux ensembles, on dit que A et B sont \underline{équipotents}, et on note |A| = |B| ss’il existe une bijection entre A et B. On dit que A est \underline{subpotent} à B, et on note |A| ≤ |B| (ou |B| ≥ |A|) ssi A est équipotent à une partie de B. (La notation |A| ≤ |B| est justifiée par le fait que ceci reste vrai si on remplace A, B par deux ensembles A′, B′ qui leur sont respectivement équipotents.) On a le théorème fondamental suivant :

Théorème de Cantor-Schröder-Bernstein. Si |A| ≤ |B| et |A| ≥ |B| alors |A| = |B|.

(Nous n’en donnerons pas la démonstration ici ; il faut cependant signaler qu’elle n’utilise pas l’Axiome du Choix.)

Il serait possible de donner une définition de |A| pour un ensemble A quelconque, en utilisant l’Axiome de Régularité (à savoir, l’ensemble des ensembles équipotents à A et de rang minimal). Nous n’en aurons cependant pas besoin. Nous dirons que |A| est le \underline{cardinal} de A, sans trop préciser ce que c’est. La relation ≤ est une relation d’ordre entre les cardinaux (en l’absence de l’Axiome du Choix, elle n’a aucune raison d’être totale). Bien sûr, on notera |A| < |B| (ou |B| < |A|) pour dire (|A| ≤ |B|) ∧ ¬(|A| = |B|). Le cardinal du vide sera noté 0.

Si A est l’image de B par une surjection, on notera |A|⊴|B|, ou |B|⊵|A|, et on dira que A est une \underline{projection} de B.

Proposition. Si |A| ≤ |B| avec |A| > 0 alors |A|⊴|B|.

Démonstration : Soit f: A → B injective. Puisque |A| > 0, on peut trouver x ∈ A. On définit g: B → A par g(y) = f^{−1}(y) si y ∈ im f, et g(y) = x sinon. g est clairement surjective, donc |A|⊴|B|.

Un ordinal α tel que |β| < |α| pour tout β < α s’appelle un \underline{aleph}. Par exemple, ω est un aleph, et en tant que tel, on le note ℵ_{0}. Il est d’usage d’identifier un aleph avec son cardinal, et on notera donc |A| = ℵ_{0} pour dire |A| = |ω|. Un tel ensemble A est dit \underline{dénombrable}. Tout ordinal fini (élément de ω) est un aleph.

Proposition. Si |F |◁ℵ_{0} alors |F | ≤ ℵ_{0}.

Démonstration : Soit g: ω → F surjective. On définit f: F → ω par :

f(a) = min{n ∈ ω: g(n) = a}

f est manifestement injective.

Un ensemble F tel que |F | = n pour un certain n ∈ ω s’appelle \underline{fini}. Un sous-ensemble d’un ensemble fini est fini, et de cardinal inférieur.

Proposition. Pour tout ensemble F, les affirmations suivantes sont équivalentes :

(i) |F | = n pour un certain n ∈ ω (i.e. F est fini). (ii) Toute partie non vide de P(F) admet un élément maximal pour l’inclusion. (iii) |F | < ℵ_{0}.

Démonstration : (i)⟹(ii) : Si A ⊆ P(F), tous les éléments de A ont pour cardinal un certain m ∈ ω, avec m ≤ n. Considérer un élément de A ayant un cardinal maximal. (ii)⟹(iii) : Considérer le A ⊆ P(F) formé des E ⊆ F tels que |E| < ℵ_{0}. On a ∅ ∈ A donc A n’est pas vide. Soit M ∈ A maximal pour l’inclusion. Si M ≠ F, alors il existe x ∈ F \ M, et on voit aisément que M ∪ {x} < ℵ_{0}. Ceci contredit la maximalité de M. (iii)⟹(i) : Puisque |F | < ℵ_{0}, on peut supposer F ⊆ ω. On définit alors f(0) comme le plus petit élément de F, f(1) comme le plus petit élément de F \ {f(0)} et ainsi de suite, jusqu’à ce que ce ne soit plus possible. Ceci définit soit f: ω → F bijective, ce qui n’est pas possible, soit f: n → F bijective, et alors |F | = n.

Un ensemble F tel que tout A ⊆ P(F) totalement ordonné pour l’inclusion admet un élément maximal s’appelle T -fini.

Proposition. Pour tout ensemble F, les affirmations suivantes sont équivalentes :

(i) Il n’existe pas de suite strictement croissante A_{0}⫋A_{1}⫋ ⋯ dans P(F). (i’) Il n’existe pas de suite strictement décroissante A_{0}⫌A_{1}⫌ ⋯ dans P(F). (ii) Toute suite croissante A_{0} ⊆ A_{1} ⊆ ⋯ dans P(F) est stationaire. (ii’) Toute suite décroissante A_{0} ⊇ A_{1} ⊇ ⋯ dans P(F) est stationaire. (iii) |F | ⋭ℵ_{0}.

Démonstration : (i)⟺(i’) et (ii)⟺(ii’) : Passer au complémentaire. (i)⟹(ii) : Donnée une suite croissante non stationaire, en éliminant les répétitions, on obtient une suite strictement croissante. (ii)⟹(i) : Trivial. (i)⟹(iii) : Si g: F → ω est surjective, alors en posant A_{n} = g^{−1}({0, …, n − 1}), on obtient une suite strictement croissante dans P(F). (iii)⟹(i) : Si (A_{n}) est une suite strictement croissante dans P(F), alors on pose g(x) = n lorsque x ∈ A_{n+1} \ A_{n}, et g(x) = 0 si x n’est dans aucun des A_{n+1} : g: F → ω ainsi définie est clairement surjective.

Un ensemble qui vérifie les conditions équivalentes de la proposition sera dit P -fini.

Proposition. Pour tout ensemble F, les affirmations suivantes sont équivalentes :

(i) F n’a pas de sous-ensemble dénombrable. (ii) |F | ≱ ℵ_{0}.

Démonstration : Trivial.

Un ensemble qui vérifie les conditions équivalentes de la proposition sera dit D-fini.

Proposition. (a) Un ensemble fini est T -fini. (b) Un ensemble T -fini est P -fini. (c) Un ensemble P -fini est D-fini.

Démonstration : (a) : Trivial (utiliser la caractérisation (iii) des ensembles finis). (b) : S’il existe une suite strictement croissante (A_{n}) dans P(F), alors {A_{n}: n ∈ ω} est une partie totalement ordonnée de P(F) sans élément maximal. (c) : On sait que si |ω| ≤ |F | alors |ω|⊴|F | (car |ω| > 0).