Récurrence transfinie

Un bon ordre sur un ensemble A est une relation d'ordre ≤ sur A pour laquelle tout sous-ensemble non vide de A possède un plus petit élément, ou encore : c'est un ordre total ≤ sur A bien fondé, c'est-à-dire dont l'ordre strict associé < est une relation bien fondée.

L'induction transfinie est le cas particulier suivant de l'induction bien fondée :

La propriété de récurrence (celle énoncée par le théorème) équivaut à la bonne fondation de la relation <.

Ce théorème se généralise à n'importe quelle propriété F(x) — c'est-à-dire n'importe quelle formule F(x) avec pour seule variable libre x — (plutôt que la propriété x ∈ B) en considérant { x ∈ A | F(x) }. C'est un énoncé de la propriété de récurrence pour les ensembles bien ordonnés (on dit également induction).

Un ordinal est un ensemble transitif bien ordonné, pour une relation d'ordre strict qui est la relation d'appartenance sur cet ordinal. Pour toute propriété F(x), l'énoncé généralisé du paragraphe précédent, appliqué à A = un ordinal δ, devient donc :

Soit δ un ordinal. Si ∀ α ∈ δ [ (∀ β ∈ α F(β)) ⇒ F(α) ] alors ∀ γ ∈ δ F(γ).

Il faut démontrer F(α) en supposant F(β) pour tout β appartenant à α, cette preuve peut se scinder en 3 cas selon que α est l'ensemble vide, un ordinal successeur, ou un ordinal limite (le plus petit élément, un point successeur, ou un point limite dans le cas d'un bon ordre).

Qu'il faille aussi envisager le cas où α est limite constitue la nouveauté dans les utilisations du principe de récurrence qui sont présentées sur les seuls entiers dans l'article « Raisonnement par récurrence ».

Le principe de récurrence se généralise à la classe des ordinaux, qui est une classe propre (c'est le paradoxe de Burali-Forti).

En effet, sous cette hypothèse, on déduit F(γ) du théorème de récurrence appliqué à l'ordinal δ = γ ∪ {γ} (l'ordinal successeur de γ).

Une définition par récurrence d'une fonction f sur un ordinal α autorise à définir f(β), pour tout β ∈ α (c'est-à-dire tout ordinal β < α), en fonction des images de ses minorants stricts (les f(γ) pour tous les ordinaux γ < β) ou plus exactement : en fonction de la restriction f|β de f à β (donnée par l'ensemble des couples (γ, f(γ)) pour γ < β). En effet, plus généralement[2] :

Définition par récurrence sur un bon ordre (Z). — Pour tout ensemble bien ordonné U et toute application g, à valeurs dans un ensemble E et définie sur l'ensemble des applications d'une partie de U dans E, il existe une application f : U → E et une seule telle que tout x ∈ U, f(x) = g( f_|seg(x) ), où f_|seg(x) désigne la restriction de f à l'ensemble seg(x) des minorants stricts de x.

Un énoncé plus général est possible dans la théorie des ensembles de Zermelo-Fraenkel : si l'on dispose du schéma d'axiomes de remplacement, on n'a pas besoin de supposer que g est une fonction au sens ensemble de couples, il peut s'agir aussi d'une classe de couples ; on parle de classe fonctionnelle, de relation fonctionnelle, ou simplement de fonctionnelle.

Dans les théories des ensembles de ce genre (les classes ne sont pas des objets du langage), parler de classe fonctionnelle ou de fonctionnelle est une façon de parler d'un prédicat à 2 variables libres A[x, y] défini dans le langage de la théorie des ensembles vérifiant :

∀x ∀y ∀y’ [(A[x, y] et A[x, y’]) ⇒ y = y’]

La classe fonctionnelle A est définie sur une classe C (représenté par un prédicat C[x]) quand :

∀x(C[x] ⇒ ∃y A[x, y]).

En particulier elle est partout définie (définie sur l'univers de tous les ensembles) quand :

∀x ∃y A[x, y].

Il est possible alors d'adopter une notation fonctionnelle y = G(x) pour A. Pour une formule F[z], la notation F[G(x)] se définit par exemple comme ∃y(F[y] et y = G(x)). L'énoncé précédent se généralise ainsi.

Définition par récurrence sur un ordinal α (ZF). — Soit un ordinal α et une fonctionnelle y = G(x) définie sur toutes les fonctions dont le domaine est un ordinal strictement inférieur à α. Alors il existe une et une seule fonction f définie sur α (au sens : un seul graphe de fonction) telle que pour tout β ∈ α, f(β) = G( f_|β ).

La démonstration de ce théorème (par induction sur α) nécessite le schéma d'axiomes de remplacement, qui permet d'affirmer que la fonctionnelle de domaine α que l'on construit définit une « vraie » fonction f (au sens : ensemble de couples), du fait que α est un ensemble.

On trouve aussi des versions où G est une fonctionnelle partout définie. Ce n'est pas moins général : on se ramène facilement à ce cas en complétant arbitrairement G, par exemple en prenant pour image ∅ partout où elle n'est pas définie initialement.

Ce dernier résultat se généralise, dans ZF, pour montrer l'existence et l'unicité d'une fonctionnelle définie sur la classe des ordinaux.

Une classe est vue à extensionnalité près : dire qu'il existe une unique classe fonctionnelle vérifiant une certaine propriété, c'est dire qu'il existe une formule A[x, y] vérifiant cette propriété (on le prouve en produisant explicitement une telle formule), que cette formule définit une classe fonctionnelle, et que deux classes vérifiant cette propriété ont les mêmes éléments. Cette dernière propriété s'écrit : pour tout autre tel prédicat B[x,y],

∀x ∀x’ ∀y ∀y’ [ (A[x, y] et B[x,y]) ⇒ (x = x’ et y = y’) ],

mais la quantification sur B fait que cette unicité ne peut être un énoncé de la théorie des ensembles : c'est un métathéorème[3], une proposition à propos de ces énoncés.

La restriction d'une fonctionnelle à un ensemble est une fonction, au sens ensemble de couples, par le schéma d'axiomes de remplacement. On note dans la suite F_|a la restriction de la classe fonctionnelle F à l'ensemble a (F_|a est donc un ensemble).

Définition par récurrence sur la classe des ordinaux[4] (ZF). — Soit une fonctionnelle définie sur toutes les fonctions, notée y = G(x), alors il existe une et une seule fonctionnelle F définie sur la classe des ordinaux et vérifiant pour tout ordinal α :

F(α) = G( F_|α ).

En présence de l'axiome de fondation, ce théorème se généralise tel quel pour définir une fonctionnelle sur tout l'univers ensembliste.

Nombre surréel

• René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions], chapitre 7
• Jean-Louis Krivine, Théorie des ensembles [détail des éditions]
• Nicole Bopp et Michel Émery, « Deux exemples de récurrence transfinie » (théorème de la base incomplète et théorème de Cantor-Bendixson)