Récurrence transfinie

En mathématiques, on parle de récurrence transfinie ou de récursion transfinie pour deux principes reliés mais distincts.

Les définitions par récursion transfinie — permettent de construire des objets infinis, et généralisent les définitions de suite par récurrence sur l'ensemble N des entiers naturels en considérant des familles indexées par un ordinal infini quelconque, au lieu de se borner au plus petit d'entre eux qu'est N, appelé ω en tant que nombre ordinal.

Les démonstrations par récurrence transfinie — ou induction transfinie — généralisent de même à un ordinal quelconque les récurrences ordinaires sur les entiers. Une fois acquis le concept d'ordinal, on dispose là d'un outil très commode, que l'on peut utiliser conjointement avec l'axiome du choix à la place du lemme de Zorn, pour faire des constructions conformes à l'intuition et où l'on dispose de renseignements précis pour une étude approfondie.

Domaine d'application

La récurrence transfinie s'applique à des ensembles munis d'une relation de bon ordre.

• Comme tout ensemble muni d'un bon ordre est isomorphe (pour l'ordre) à un et un seul ordinal (où le bon ordre est la relation d'appartenance), nous étudierons essentiellement la récurrence transfinie sur les seuls ordinaux, les résultats étant transposables par isomorphisme.
• L'extension de la méthode à tout ensemble est possible via le théorème de Zermelo, équivalent (modulo ZF) à l'axiome du choix ; il affirme que tout ensemble peut être muni d'un bon ordre.

Démonstration par récurrence transfinie

L'objectif est de démontrer qu'une certaine propriété vaut pour tout objet d'un domaine considéré.

• En arithmétique du premier ordre on dispose d'un schéma d'axiomes permettant de le faire sur l'ensemble des entiers, voir « Raisonnement par récurrence ».
• En théorie des ensembles c'est un théorème applicable à tout ensemble bien ordonné (les entiers compris), les ordinaux étant les archétypes d'ensembles bien ordonnés. Il s'étend à la classe des ordinaux, sous la forme d'un schéma d'axiomes.

Ensemble bien ordonné

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 :

Théorème (récurrence) — Soient ≤ un bon ordre sur un ensemble A et < l'ordre strict associé. Pour tout sous-ensemble B de A,si ∀ x ∈ A [(∀ y ∈ A(y < x ⇒ y ∈ B)) ⇒ x ∈ B] alors B = A.

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).

Ordinal

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(γ).

Utilisation du théorème

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 ».

Sur la classe des ordinaux

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).

Théorème — Si, pour tout ordinal α, [ (∀ β ∈ α F(β)) ⇒ F(α) ] alors, pour tout ordinal γ, F(γ).

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

Définition par récurrence transfinie

Dans la définition d'une fonction f par récurrence, sa valeur en un point donné fait appel à la valeur de f en d'autres points. Une telle définition récursive est possible si le domaine de définition est bien ordonné et si les appels pour calculer f en x se font toujours pour des y tels que y < x. Plus généralement il suffit que < soit une relation bien fondée (définie par un ensemble de couples). Le fait que f soit bien définie repose sur un principe de définition par récurrence, un énoncé d'existence et d'unicité qui se démontre en théorie des ensembles.

La définition par récurrence bien fondée se généralise encore au cas d'une classe relationnelle bien fondée ≺, à condition que pour tout élément a du domaine de la relation, les x tels que x ≺ a forment un ensemble (on parle en anglais de relation set-like).

Définition par récurrence sur un ordinal

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 :

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.

Définition par récurrence sur un ordinal pour une classe fonctionnelle

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.

Définition par récurrence sur la classe des ordinaux

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, 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 (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.

Voir aussi

Article connexe

Nombre surréel

Bibliographie

• 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)