Généralisation de l'induction mathématique aux ensembles bien ordonnés indexés par des ordinaux : pour prouver une propriété P(α) pour tout ordinal α on montre P(0), on prouve que P(β) implique P(β+1) pour tout successeur β+1, et pour tout ordinal limite λ on montre que la vérité de P(γ) pour tout γ < λ entraîne P(λ).

Principe

Le bien-ordonnancement impose une induction en trois temps : base (zéro), étape successeur et étape limite ; la clôture par ces étapes propage la propriété à tous les ordinaux par récurrence ou induction transfinie.

Démonstration

Construire la hiérarchie cumulative de von Neumann V_α ou montrer que tout ordinal est soit 0, soit un successeur, soit un limite utilise l'induction transfinie : au stade limite on vérifie une propriété à partir de sa vérité pour tous les stades antérieurs, ce qui permet des constructions et des preuves couvrant tous les ordinaux.

Mauvaise application

Omettre l'étape limite (ne traiter que les étapes zéro et successeur) invalide les preuves aux ordinaux limites ; appliquer l'induction transfinie à des relations qui ne sont pas bien ordonnées détruit l'argument et peut donner des résultats faux.

Conséquence

L'induction et la récurrence transfinies permettent des définitions et des preuves sur des ensembles indexés bien ordonnés arbitrairement grands, soutenant les constructions d'ordinaux et de cardinaux, les définitions récursives sur des classes et de nombreux arguments en théorie des ensembles et logique.

Inversion

Sur des ordres non bien fondés, l'induction transfinie n'est pas disponible ; symétriquement, l'induction noethérienne traite la bien-fondation sous l'angle opposé de la condition de finitude, et l'induction ordinaire est l'analogue du cas fini.

Limite

Nécessite un domaine bien ordonné (ordinaux ou autre classe bien ordonnée) ; en travaillant avec des classes propres ou dans des théories faibles des ensembles il convient de surveiller les limites fondationnelles (remplacement, récursion sur les classes) ; elle ne s'applique pas à des ensembles partiellement ordonnés sans bien-ordres.

Tension sémantique

L'induction transfinie est souvent vue comme une généralisation directe de l'induction sur les nombres naturels mais diffère crucialement par la nécessité d'une étape limite distincte ; confondre les deux peut occulter des phénomènes ordinals essentiels.

Synthèse

L'induction transfinie généralise le schème inductif aux ordinaux en combinant vérifications de la base, du successeur et des limites pour propager une propriété à chaque étape bien ordonnée, permettant des définitions et preuves au-delà des indices finis.