Récurrence transfinie

En mathématiques on parle de récurrence transfinie ou d’induction transfinie pour deux principes reliés mais distincts.

Les définitions par récurrence transfinie permettent de construire des objets infinis, et généralisent les définitions de suite par récurrence sur l'ensemble des entiers naturels N 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 généralisent de même à un ordinal quelconque les récurrence ordinaire 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.

Notions préliminaires

Comme nous parlerons beaucoup des ordinaux dans cet article, il peut être pertinent de rappeler que les ordinaux sont des sortes de nombres, c’est-à-dire que le début de la classe des ordinaux (ceux plus petits que $\omega$) peut être identifié à l'ensemble $\N$ des nombres naturels, et que les relations donnant à $\N$ sa structure (successeur, somme, produit ...) peuvent être étendues à la classe des ordinaux (avec quelques différences importantes, par exemple $1+\omega=\omega\ \ne\ \omega+1$).

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

Sur la classe des ordinaux

Une classe propre est un « rassemblement » d'ensembles qui est bien défini mais ne peut sans contradiction être considéré comme un ensemble, comme la classe V de tous les ensembles. Voir classe. Les ordinaux forment une classe propre (c'est le paradoxe de Burali-Forti), car sinon leur type de bon ordre serait un ordinal plus grand que tous les ordinaux, ce qui est évidemment absurde.

Soit F(x) une formule avec pour seule variable libre x, on a alors :

• Théorème : $\forall \alpha \{ On(\alpha) \to [ \forall \beta ( \beta \in \alpha \to F(\beta) ) \to F(\alpha) ] \} \to \forall \gamma \{ On(\gamma) \to F(\gamma) \}$ (théorème *)

où $On(\alpha)$ signifie : $\alpha$ est un ordinal.

• La démonstration se fait de la manière suivante :

Supposons que : $\forall \alpha \{ On(\alpha) \to [ \forall \beta ( \beta \in \alpha \to F(\beta) ) \to F(\alpha) ] \}$ (prop. 1)

S'il existait un ordinal $\alpha$ tel que $F(\alpha)$ soit fausse, alors il en existerait un qui soit le plus petit (la classe des ordinaux est elle-même bien ordonnée par la relation d'appartenance) ; soit $\alpha_0$ cet ordinal. Pour tout ordinal $\beta$ plus petit que lui, on aura donc $F(\beta)$ ; ainsi $\beta \in \alpha_0 \to F(\beta)$ est vrai (car $F(\beta)$ est vrai ou $\alpha_0 = 0 = \emptyset$ et $\beta \in \alpha_0$ est faux). Et donc par hypothèse (prop.1) $F(\alpha_0)$ est vrai aussi ; contradiction.

Cela montre que l'hypothèse qu'il existe un ordinal $\alpha$ tel qu'on n'ait pas $F(\alpha)$ est fausse ; par contraposition, il en découle que la prop.1 implique que pour tout ordinal $\gamma$, $F(\gamma)$, ce qu'il fallait démontrer.

Ensemble bien ordonné

Voir aussi l'article : Ensemble bien ordonné

Un ensemble A muni d'une relation de bon ordre strict < est une structure $(A, <)$ telle que l'ordre large ≤ associé à la relation binaire <

• est une relation d'ordre strict
• telle que tout sous-ensemble non vide de A ait un plus petit élément.

Théorème. — Pour tout sous-ensemble B de A

si ∀ x ∈ A [∀ y ∈ A(y < x ⇒ y ∈ B) ⇒ x ∈ B]

alors B = A.

Ce théorème se généralise à n'importe quelle propriété F(x) (plutôt que x ∈ B) en considérant { x ∈ A | F(x) }.

Ordinal

Un ordinal est un ensemble bien ordonné, l'énoncé est donc celui donné au paragraphe précédent pour A = α ordinal. La relation d'ordre strict < est aussi la relation d'appartenance. L'énoncé généralisé devient : pour toute propriété F(x),

si ∀ x ∈ α[ ( (∀ y < x) F(y) ) ⇒ F(x) ]

alors ∀ x ∈ α F(x).

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 peit é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és dans l'article raisonnement par récurrence sur les seuls entiers.

Récurrence noethérienne ou bien fondée

La récurrence transfinie est un cas particulier de la récurrence noethérienne ou bien fondée, dans laquelle l'ordre bien fondé est bien ordonné, autrement dit total et bien fondé ; la récurrence noethérienne s'énonce ainsi : « si [(pour tout $\beta < \alpha$, $P(\beta) \Rightarrow P(\alpha)$], alors [pour tout $\alpha$, $P(\alpha)$] »).

Définition par récurrence transfinie

Une fonction f est définie par récurrence quand sa définition en un point donnée fait appel à la valeur de f en un autre point, et ce un nombre fini de fois. Une telle définition récursive est possible, si l'ensemble de définition est bien ordonnée 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 y soit en relation avec x pour une relation bien fondée. 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.

Définition par récurrence sur un ordinal

Une définition par récurrence d'une fonction f sur un ensemble bien ordonné A, autorise à définir pour tout en x ∈ A l'image f(x) en fonction d'une ou de plusieurs images de ses minorants, soient les f(y) pour y < x (y ∈ A), et éventuellement des y eux-mêmes.

Quand l'ensemble A est un ordinal α, les éléments de α sont des ordinaux β, les éléments de β étant eux mêmes les ordinaux minorant strictement β. En théorie des ensembles une fonction est vue comme un ensemble de couples. Si f est une fonction définie sur un ordinal α, on parle aussi de suite définie sur les ordinaux, sa restriction à β, élément de α est donc l'ensemble des couples (γ,f(γ)) pour γ minorant strict de β. On obtient donc un principe de définition par récurrence très général en autorisant f(β) à dépendre de sa restriction à β f|β (les ordinaux strictement inférieurs à β et leurs images).

Définition par récurrence sur un ordinal α. — Soit un ordinal α et g une fonction définie sur l'ensemble des fonctions définies sur un ordinal β < α et à valeurs dans un ensemble E. Alors il existe une et une seule fonction f définie sur α à valeur dans E telle que f(β) = g( f|β ).

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

Un énoncé plus général est possible dans la théorie des ensembles ZF : si 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 (propre) de couples, on parle de classe fonctionnelle, de relation fonctionnelle, ou simplement de fonctionnelle.

Dans les théorie des ensembles du genre ZFC (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 y = G(x)) une fonctionielle définie sur toutes les fonctions dont le support est un ordinal β < α . Alors il existe une et une seule fonction f définie sur α telle que f(β) = G( f|β ).

Cette version utilise nécessairement le schéma de remplacement. Pour que la définition ait un sens, on a besoin de montrer que G( f|β ) est un ensemble, ce qui est une conséquence immédiate du remplacement, sachant que f|β est un ensemble (de couples).

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 à se 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 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 certaines propriété, c'est dire qu'il existe une formule A[x,y] vérifiant cette propriété (ce ne peut donc être un énoncé de la théorie des ensembles, mais une proposition à propos de ces énoncés), et que deux classes A[x,y] et B[x,y] vérifiant cette propriété

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

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. — Soit une fonctionnelle définie sur toutes les fonctions à support ordinal, 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.

Articles connexes

• Raisonnement par récurrence
• Définition par récurrence
• Nombre ordinal
• 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]