Récurrence transfinie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques on parle de récurrence transfinie ou d’induction transfinie[1] 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é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[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

Article détaillé : 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 un bon ordre large, soit

  • ≤ est une relation d'ordre sur A
  • tout sous-ensemble non vide de A possède un plus petit élément pour l'ordre ≤.
Théorème (récurrence) — Soit (A, <) un bon ordre strict. On a, pour tout sous-ensemble B de A,
si ∀ xA [∀ yA(y < xyB) ⇒ xB] alors B = A.

Ce théorème se généralise à n'importe quelle propriété F(x) (plutôt que xB) en considérant { xA | F(x) }. C'est un énoncé de la propriété de récurrence pour les ensembles bien ordonnés (on dit également induction).

Pour un ordre strict total (A, <), la propriété de récurrence (celle énoncée par le théorème) équivaut au fait d'être un bon ordre strict.

Ordinal[modifier | modifier le code]

Un ordinal est un ensemble bien ordonné, la relation d'ordre strict étant la relation d'appartenance. L'énoncé généralisé du paragraphe précédent, appliqué à A = un ordinal δ, devient donc : pour toute propriété F(x), si ∀ x ∈ δ [ ( (∀ yx) F(y) ) ⇒ F(x) ] alors (∀ x ∈ δ) F(x).

Utilisation du théorème[modifier | modifier le code]

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

Récurrence noethérienne ou bien fondée[modifier | modifier le code]

Article détaillé : relation bien fondée.

La récurrence transfinie est un cas particulier de récurrence sur une relation bien fondée. En effet l'ordre strict associé à un bon ordre est une relation bien fondée. Par exemple la récurrence usuelle sur les entiers est la récurrence sur la relation bien fondée y = x + 1.

Sur la classe des ordinaux[modifier | modifier le code]

Le principe de récurrence se généralise à la classe des ordinaux. Une classe propre est une « collection » d'ensembles qui est bien définie mais ne peut sans contradiction être considérée 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 strictement 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 — ∀ α { On(α) ⇒ [ ∀ β ( β ∈ α ⇒ F(β) ) ⇒ F(α) ] } ⇒ ∀ γ { On(γ) ⇒ F(γ) } où On(α) signifie : α est un ordinal.

En effet si, pour tout ordinal α, l'implication ((∀ β ∈ α) F(β)) ⇒ F(α) est vraie alors, pour tout ordinal γ, F(γ) est vrai, d'après le théorème de récurrence appliqué à l'ordinal δ = γ ∪ {γ} (l'ordinal successeur de γ).

Définition par récurrence transfinie[modifier | modifier le code]

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[modifier | modifier le code]

Une définition par récurrence d'une fonction f sur un ensemble bien ordonné A, autorise à définir pour tout en xA l'image f(x) en fonction d'une ou de plusieurs images de ses minorants, soient les f(y) pour y < x (yA), 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 classe fonctionnelle[modifier | modifier le code]

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

xyy’ [(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 :

xy 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 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 à 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[modifier | modifier le code]

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 certaine 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), que cette formule définit une classe fonctionnelle, et que deux classes A[x,y] et B[x,y] vérifiant cette propriété ont les mêmes éléments. Cette dernière propriété s'écrit

xx’yy’ [ (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[modifier | modifier le code]

Note[modifier | modifier le code]

  1. Ces deux mots peuvent avoir un sens différent chez certains mathématiciens comme Halmos ou Birkhoff.

Bibliographie[modifier | modifier le code]