Théorème 3Ordinaux, cardinaux

Définition par récursion transfinie

Énoncé

Dans ce nœud et dans ceux qui emploient la récursion transfinie, on identifie une application à son graphe. Une application de domaine $\delta$ est ici un ensemble $f$ de couples dont les premiers termes sont dans $\delta$ et tel que, pour tout $\alpha \in \delta$ , il existe un unique $y$ avec $(\alpha, y) \in f$ , noté $f(\alpha)$ : c'est le graphe d'une application, au sens de Application, de $\delta$ dans n'importe quel ensemble qui contient ses valeurs. Sa restriction $f|_\alpha$ à $\alpha \subset \delta$ est l'ensemble de ses couples de premier terme dans $\alpha$ , et les réunions d'applications s'entendent des réunions de ces ensembles de couples.

Soit $\psi(f, y)$ une formule telle que, pour tout ensemble $f$ , il existe un unique $y$ vérifiant $\psi(f, y)$ ; on note $y = G(f)$ . Pour tout ordinal $\delta$ , il existe une unique application $F_\delta$ de domaine $\delta$ telle que $\begin{aligned} F_\delta(\alpha) &= G\big(F_\delta|_\alpha\big) \\ &\text{pour tout } \alpha < \delta, \end{aligned}$ et pour $\delta \leqslant \delta'$ , $F_\delta$ est la restriction de $F_{\delta'}$ à $\delta$ .

On note $F(\alpha)$ la valeur commune des $F_\delta(\alpha)$ , $\delta > \alpha$ : c'est la fonction définie par récursion transfinie à partir de $G$ . On note $F[\alpha] = \{F(\beta) : \beta < \alpha\}$ l'image de sa restriction à $\alpha$ .

Démonstration

Unicité. Si $F_\delta$ et $F'_{\delta}$ conviennent, l'ensemble des $\alpha < \delta$ où elles diffèrent, s'il était non vide, aurait un plus petit élément $\alpha$ ; alors $F_\delta|_\alpha = F'_\delta|_\alpha$ , donc $F_\delta(\alpha) = G(F_\delta|_\alpha) = F'_\delta(\alpha),$ contradiction. Le même argument montre que la restriction de $F_{\delta'}$ à $\delta$ , qui vérifie l'équation sur $\delta$ , est $F_\delta$ .

Existence. Raisonnons par induction transfinie sur $\delta$ (Induction transfinie) : supposons que $F_\beta$ existe pour tout $\beta < \delta$ .

Par le schéma de remplacement, appliqué à $\delta$ et à la formule « $y$ est l'unique $F_\beta$ », l'ensemble $\{F_\beta : \beta < \delta\}$ existe. Sa réunion $g$ est une application, puisque ces applications coïncident là où elles sont toutes deux définies, de domaine $\bigcup \delta$ .

Si $\delta$ est vide ou limite, $\bigcup \delta = \delta$ (Successeurs, limites), et l'on pose $F_\delta = g$ . Pour $\alpha < \delta$ , il existe alors $\beta < \delta$ avec $\alpha < \beta$ , et $\begin{aligned} F_\delta(\alpha) &= F_\beta(\alpha) = G(F_\beta|_\alpha) \\ &= G(F_\delta|_\alpha). \end{aligned}$

Si $\delta = \beta^+$ , on pose $F_\delta = F_\beta \cup \{(\beta, G(F_\beta))\},$ application de domaine $\beta \cup \{\beta\} = \delta$ . Pour $\alpha < \beta$ , l'équation est celle de $F_\beta$ ; pour $\alpha = \beta$ , elle s'écrit $F_\delta(\beta) = G(F_\beta) = G(F_\delta|_\beta).$

□

Remarque

Le schéma de remplacement est ici indispensable : sans lui, on ne pourrait rassembler les approximations $F_\beta$ en un ensemble. C'est l'usage qu'annonçait la remarque du nœud Remplacement.

Remarque

$F$ n'est pas un ensemble, puisque son domaine serait l'ensemble de tous les ordinaux. On ne manipule que ses restrictions $F_\delta$ , qui en sont, et l'énoncé est, comme l'induction, un schéma.

Repose sur

Principe d'induction transfinie

Sert à

Théorème de Zermelo Lemme de Zorn