Récurrence transfinie - Définition

Domaine d'application

La récurrence transfinie s'applique à des ensembles ou des classes 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.

Construction par récurrence transfinie

Par récurrence transfinie, on peut construire des applications de l'ensemble des ordinaux vers un ensemble E quelconque : c'est-à-dire des sortes de suites. Pour définir une telle « suite » U, il suffit de savoir exprimer U (l'ordinal α) en fonction F de l'ensemble des ordinaux strictement inférieurs à α : bref il suffit de savoir écrire : U(α) = F({U(β),β < α}). L'ordre défini entre ordinaux étant bien fondé, tout ordinal a bien une image par U.

[supposons en effet que ce ne soit pas le cas : soit α₁ n'ayant pas d'image par U : si α₁ n'est pas le plus petit dans ce cas, soit α₂ n'ayant pas d'image par U et strictement plus petit que α₁ : si α₂ n'est pas le plus petit dans ce cas, soit α₃, etc. : la suite des ordinaux α_i qu'on construit ici est strictement décroissante : puisque l'ordre entre ordinaux est bien fondé, elle doit avoir une fin : c’est-à-dire qu'on doit trouver un α_n qui soit le plus petit ordinal sans image par U. Mais alors pour tout β < α_n, une image par U de β est définie : donc F({U(β),β < α_n}) peut être définie comme l'image de α_n par U : or on vient de dire qu'α_n n'avait pas d'image par U : c'est absurde]

Définition par récurrence transfinie

Voir aussi le théorème de définissabilité de Beth

Là l'objectif est de définir un objet mathématique par récurrence au delà du fini. Ceci en exhibant une fonction construisant un objet mathématique nouveau à partir d'un autre préalablement défini. Cela passe par la démonstration de l'existence et de l'unicité de la fonction.

Et là encore un théorème dérivé du précédant le permet.

Nous nous restreindrons à ne l'énoncer que pour la classe (mais via valable aussi pour les ensembles) des ordinaux (mais donc aussi généralisable via le théorème de Zermelo à tout ensemble bien ordonné).

Principe de définition par récurrence sur la classe des ordinaux

• Théorème général:

Soit F(x, y, z) une formule avec x, y, z comme variables libres, telle que :

∀x∀y (On (x) et y est une application de domaine x) ⇒ il existe un unique z tq F(x, y, z)

Alors il existe une et une seule fonction g, à paramètres dans On, telle que :

Pour tout ordinal α, g(α) est l'unique ensemble u tel que F[α, g|α, u].

( Où « g|α » signifie « g restreint à α », « On(x) » signifie « x est un ordinal » et « On » désigne la classe des ordinaux. )

• Plus simplement :

Soit V la classe de tous les ensembles, et On la classe des ordinaux, on a théorème :

Soit f une fonction de On * V dans V, alors il existe une unique fonction g de On dans V telle que pour tout ordinal α :

g(α) = f(α, g|α).

( Où « g|α » signifie « g restreint à α », et où f et g correspondent à l'extension de la notion de fonction des ensembles aux classes. )

• On appelle ∈-récursion la généralisation de ce théorème avec f fonction de V * V dans V et g fonction de V dans V.