Théorème 2Ordinaux, cardinaux

Principe d'induction transfinie

Énoncé

Soit $\varphi(x)$ une formule. Si, pour tout ordinal $\alpha$ , la propriété « $\varphi(\beta)$ pour tout $\beta < \alpha$ » entraîne $\varphi(\alpha)$ , alors $\varphi(\alpha)$ est vraie pour tout ordinal $\alpha$ .

Sous forme équivalente : si $\varphi(\varnothing)$ , si $\varphi(\alpha)$ entraîne $\varphi(\alpha^+)$ , et si, pour tout ordinal limite $\lambda$ , « $\varphi(\beta)$ pour tout $\beta < \lambda$ » entraîne $\varphi(\lambda)$ , alors $\varphi$ est vraie pour tout ordinal.

Démonstration

Supposons $\neg\varphi(\alpha)$ pour un ordinal $\alpha$ . L'ensemble $\{\beta \in \alpha^+ : \neg\varphi(\beta)\},$ obtenu par séparation, est non vide puisqu'il contient $\alpha$ ; soit $\gamma$ son plus petit élément (Comparaison des ordinaux). Tout $\beta < \gamma$ vérifie $\beta < \alpha^+$ et $\varphi(\beta)$ , par minimalité ; l'hypothèse donne $\varphi(\gamma)$ , ce qui est contradictoire.

La seconde forme se ramène à la première : pour $\alpha$ donné, l'un des trois cas du nœud Successeurs, limites se produit, et l'hypothèse correspondante donne $\varphi(\alpha)$ dès que $\varphi$ est vraie au-dessous de $\alpha$ .

□

Remarque

C'est un schéma, un énoncé par formule $\varphi$ , comme le schéma de séparation : on ne peut quantifier sur les propriétés dans $\mathsf{ZF}$ (Logique du premier ordre). L'erreur la plus répandue est d'oublier le cas limite, qui n'a pas d'analogue dans la récurrence sur les entiers.

Repose sur

Ordinaux successeurs et ordinaux limites

Sert à

Définition par récursion transfinie