Logique et ensemblesNotion · Glossaire
Transfinie (récurrence)
La récurrence transfinie est une méthode de preuve et de construction qui généralise la récurrence ordinaire aux ordinaux transfinis. Elle repose sur le principe que si une propriété est vraie pour 0, si sa validité pour tout ordinal entraîne sa validité pour son successeur et si, pour tout ordinal limite, sa validité pour tous les ordinaux strictement inférieurs entraîne sa validité à cette limite, alors elle est vraie pour tous les ordinaux. Cette technique est fondamentale en théorie des ensembles et en logique mathématique.
Sommaire
Ce que vous allez apprendre
- Distinguer l’initialisation, l’étape successeur et l’étape limite.
- Suivre un raisonnement de 0 à ω + 2 sans inventer de prédécesseur à ω.
- Séparer récurrence transfinie, récurrence ordinaire et définition par récurrence transfinie.
En clair
Imaginez que l’on vérifie une propriété à 0, puis à 1, à 2, et ainsi de suite. La récurrence ordinaire suit cette chaîne de nombres entiers. La récurrence transfinie poursuit le raisonnement sur les ordinaux, qui décrivent des positions dans un bon ordre.
Un nouveau geste apparaît lorsqu’on atteint un ordinal limite comme ω, le premier ordinal après tous les entiers naturels. Il faut alors s’appuyer sur tous les cas antérieurs, et non sur un unique prédécesseur. Après cette étape limite, les étapes successeurs reprennent avec ω + 1, ω + 2, et au-delà.
Définition
La récurrence transfinie est un principe de preuve portant sur les ordinaux. Un ordinal repère une position dans un ordre où toute partie non vide possède un plus petit élément. Pour établir une propriété notée P pour chaque ordinal, on traite trois situations : l’ordinal initial 0, les ordinaux successeurs et les ordinaux limites.
L’ordinal courant est noté α. Son successeur est α + 1. Un ordinal limite, noté λ, n’est ni 0 ni le successeur d’un ordinal. Enfin, β désigne un ordinal strictement inférieur à λ. Les trois conditions s’écrivent :
;
;
.
;
;
.
Si ces conditions sont satisfaites, P vaut pour tous les ordinaux. La formulation compacte équivalente demande, pour chaque ordinal α, de déduire P(α) de P(β) pour tout β strictement inférieur à α. Le cas limite est indispensable : contrairement à un successeur, un ordinal limite n’a pas de prédécesseur immédiat dont la propriété suffirait à elle seule.
Un exemple, pas à pas
On veut vérifier jusqu’à ω + 2 le mécanisme d’une preuve portant sur une propriété P. Données : P est vraie à 0 ; P passe de chaque ordinal α à α + 1 ; à tout ordinal limite λ, P(λ) découle de P(β) pour chaque β inférieur à λ. Le parcours représenté distingue le saut conceptuel vers la limite des passages au successeur.
1. L’initialisation donne P(0).
2. La règle du successeur donne successivement P(1), P(2), puis P(n) pour chaque entier naturel n.
3. Comme P vaut pour tout ordinal β inférieur à ω, la règle de limite donne P(ω).
4. Deux nouvelles applications de la règle du successeur donnent P(ω + 1), puis P(ω + 2).
Le contrôle consiste à classer chaque passage : 0 est le départ, ω est l’unique étape limite de ce parcours, et 1, 2, ω + 1 et ω + 2 sont obtenus par succession. Aucun passage vers ω ne vient d’un prétendu ordinal ω − 1.
En pratique
Pour prouver une propriété indexée seulement par les entiers naturels, la récurrence ordinaire suffit : on vérifie le départ, puis le passage de n à n + 1. La version transfinie devient pertinente quand l’index parcourt réellement des ordinaux au-delà des entiers.
Face à une preuve transfinie, on commence par repérer le type de l’ordinal courant. S’il vaut 0, on initialise ; s’il possède un prédécesseur immédiat, on applique l’étape successeur ; sinon, on vérifie l’hypothèse portant sur tous les ordinaux antérieurs à la limite.
La méthode sert aussi à organiser des constructions par étapes ordinales. Dans ce cas, une récurrence prouve que chaque étape possède une propriété, tandis qu’une définition par récurrence transfinie précise l’objet fabriqué à chaque étape.
À ne pas confondre
Récurrence ordinaire. Elle est indexée par les entiers naturels et ne comporte pas d’étape limite distincte. Dès qu’une preuve doit traiter ω comme un indice, les seules étapes 0 et successeur ne suffisent plus.
Définition par récurrence transfinie. Elle construit une valeur à chaque ordinal ; la récurrence transfinie établit une propriété à chaque ordinal. Définir une suite d’objets et prouver qu’ils vérifient tous une condition sont deux tâches différentes, même si leurs étapes se ressemblent.
Induction bien fondée. Elle raisonne sur une relation bien fondée quelconque, pas nécessairement sur l’ordre des ordinaux. Le critère est donc le support du raisonnement : des ordinaux pour la récurrence transfinie, une relation bien fondée plus générale pour l’autre principe.
Limites et pièges
Oublier l’étape limite. Une preuve qui traite 0 et α + 1, puis conclut pour tous les ordinaux, s’arrête avant ω. Il faut ajouter une justification propre à chaque ordinal limite.
Chercher le prédécesseur d’une limite. Une écriture comme ω − 1 ne fournit pas l’étape immédiatement antérieure à ω : aucun ordinal n’a ω pour successeur. Il faut utiliser les propriétés établies pour tous les β inférieurs à ω.
Remplacer tous les antécédents par une suite. Une suite dénombrable ne suffit pas à traiter arbitrairement chaque ordinal limite. La condition sûre porte sur tout ordinal β strictement inférieur à la limite considérée, sauf si un argument supplémentaire établit qu’une famille plus petite suffit.
Supposer l’hérédité sans la démontrer. Le fait que P soit vraie pour de nombreux ordinaux antérieurs ne garantit pas automatiquement P à l’étape courante. Chaque implication successeur ou limite doit être prouvée dans le problème étudié.
Pour aller plus loin
Le prolongement naturel consiste à préciser les objets ordonnés sur lesquels ce raisonnement devient possible.
nombre ordinal — Pour approfondir les indices transfinis, leurs successeurs et leurs limites.
Bon ordre — Pour relier la méthode à l’existence d’un plus petit élément dans toute partie non vide.
Bien ordonné (ensemble) — Pour reconnaître la structure d’ordre qui autorise un raisonnement sans descente infinie.
Induction — Pour situer le raisonnement inductif général dont la récurrence transfinie est une forme ordinale.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres