Récurrence transfinie

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant.

La récurrence transfinie, appelée aussi sous l'influence anglaise induction transfinie, permet de construire des objets et de démontrer des théorèmes ; elle généralise la récurrence ordinaire sur N en considérant des familles indexées par un ordinal infini quelconque au lieu de se borner au plus petit qu'est N. Une fois un peu compris ce qu'est un ordinal, on dispose là d'un outil très commode pour faire des constructions conformes à l'intuition et on dispose de renseignements précis pour une étude approfondie (ce que ne permet pas le lemme de Zorn, qui a été introduit pour éviter l'usage des ordinaux transfinis).

Sommaire

1 Les ordinaux
2 Construction par récurrence transfinie
3 Démonstration par récurrence transfinie
4 Articles connexes

[modifier] Les ordinaux

L'axiome du choix a pour conséquence le théorème de Zermelo, qui assure que tout ensemble peut être bien ordonné ; d'autre part tout ensemble bien ordonné est isomorphe (pour l'ordre) à un ordinal. Un ordinal est en théorie axiomatique des ensembles un ensemble transitif bien ordonné par la relation ∈ comme ordre strict, si bien que tout élément d'un ordinal est lui-même un ordinal ; nous n'avons pas besoin de cette sophistication ici, nous contentant de considérer des ensembles bien ordonnés dont les éléments seront appelés ordinaux par commodité de langage.

Nous nous donnons un ensemble bien ordonné (J,≤) de cardinalité suffisante (dépendant du contexte) admettant un plus grand élément Ω (sinon, on lui en adjoint un), et désignons, pour α∈J, par C_α l'ensemble des β ∈J strictement inférieurs à α. Soit ℵ un cardinal majoré (au sens large) par le cardinal de J (par exemple ℵ₁, premier cardinal non dénombrable, si J est non dénombrable). L'ensemble des

[modifier] Construction par récurrence transfinie

Les ordinaux sont des sortes de nombres. C'est à dire que le début de l'ensemble des ordinaux (ceux plus petits que $Ω$ ) peut être identifié à l'ensemble N des nombres naturels, et que les relations donnant à N sa structure (successeur, somme, produit ...?) peuvent être étendues à cet ensemble des ordinaux.

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 $α 1$ n'ayant pas d'image par U : si $α 1$ n'est pas le plus petit dans ce cas, soit $α 2$ n'ayant pas d'image par U et strictement plus petit que $α 1$ : si $α 2$ n'est pas le plus petit dans ce cas, soit $α 3$ , etc. : la suite des ordinaux $α i$ qu'on construit ici est strictement decroissante : 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]

Finalement, la definition par récurrence transfinie n'est rien d'autre qu'une définition par récurrence noetherienne sur un ensemble bien ordonné, ici celui des ordinaux (un ordre est un bon ordre si et seulement s'il est total et bien fondé ; la récurrence noetherienne est celle qu'on peut faire sur tout ensemble bien fondé : "si [(pour tout $β < α$ , $P(\beta) \Rightarrow P(\alpha)$ ], alors [pour tout $α$ , $P (α)$ ]").