Induction transfinie

L'induction transfinie est une prolongation de l'induction mathématique aux ensembles well-ordered , par exemple aux ensembles de nombres ordinaux ou de cardinaux .

Induction transfinie

Supposer toutes les fois que pour tous les β < α, P (β) est vrai, puis P (α) est également vrai. Alors l'induction transfinie nous indique que P est vrai pour tous les nombres ordinaux.

C'est-à-dire, si P (α) est vrai toutes les fois que P (β) est vrai pour tous les β < α, puis P (α) est vrai pour tout le α. Ou, plus pratiquement : afin de prouver une propriété P pour tout le α de nombres ordinaux, on peut supposer qu'on le connaît déjà pour tous les plus petits β < α.

Habituellement la preuve est décomposée en trois cas :
cas du zéro de

: montrent que P (0) est vrai.
caisse de successeur de de

: montrent que pour n'importe quel successeur ordinal β+1, P de (β+1) suit de P (β) (et, au besoin, P (α) pour tous les α < β).
cas de limite de de

: montrent que pour n'importe quel λ ordinal de la limite , P (λ) suit pour de tous les α < λ.

Noter que le deuxième et troisième cas sont identique excepté le type de nombre ordinal considéré. Ils n'ont pas besoin formellement d'être prouvés séparément, mais dans la pratique les preuves sont typiquement si différent quant à exiger les présentations séparées.

Récursion transfinie

La récursion transfinie est une méthode de construire ou de définir quelque chose et est étroitement liée au concept de l'induction transfinie. Comme exemple, un ordre du A _α d'ensembles est défini pour chaque α ordinal, en spécifiant trois choses :
Quel A ₀ est
Comment déterminer le A _α+1 du A _α (ou probablement de l'ordre entier jusqu'à A _α)
Pour un λ ordinal de limite, comment déterminer le A _λ de l'ordre du A _α pour le α < le λ

Plus formellement, nous pouvons énoncer le théorème transfini de récursion comme suit. Les fonctions données G₁, G₂, G₃ de classe, existe là un ordre transfini de unique F avec les DOM (F) = $\ mathrm {Ord}$ (le $\ mathrm {Ord}$ est la classe appropriée de tous les nombres ordinaux) tels que
F (0) = G₁ ( $\ emptyset$ )
F ( $\ alpha + 1$ ) = G₂ (F ( $\ alpha$ )), pour tous les $\ alpha \ dans \ mathrm {Ord}$
F ( $\ alpha$ ) = G₃ (F $\ upharpoonright \ alpha$ ), pour tous les $de limite \ alpha \ quantité nette de substance explosive 0$

Noter que nous exigeons des domaines de G₁, G₂, G₃ d'être assez larges pour rendre les propriétés ci-dessus signicatives. L'unicité de l'ordre satisfaisant ces propriétés peut être prouvée using l'induction transfinie.

Plus généralement, on peut définir des objets par récursion transfinie sur n'importe quelle relation bien fondée R. de (le R n'a pas besoin même d'être un ensemble ; ce peut être une classe appropriée , si c'est un placer-comme la relation de ; c'est-à-dire, pour tout X , la collection de tout le y tels que le yRx de doit être un ensemble.)

Rapport avec l'axiome du choix

Il y a une idée fausse populaire que l'induction transfinie, ou récursion transfinie, ou toutes les deux, exigent l'axiome de du choix (C. L'induction transfinie peut être appliquée à l'ensemble well-ordered. C'est, cependant, très souvent le cas que les preuves ou les constructions using l'induction transfinie emploient également l'axiome de du bien-ordre du choix un ensemble.

Par exemple, considérer la construction suivante du Vitali réglé : D'abord, Bien-ordre que les reals indiquent dans un ordre < un r _α | α, où c est la cardinalité de du continuum . Laisser le égal r ₀ du v ₀. Laisser alors le égal r _α1 du v ₁, où α1 est moindre tel que le r _α1 ; &minus ; ; le v ₀ n'est pas un nombre raisonnable . Continuer ; à chaque étape choisir moins le vrai de l'ordre du r qui n'a pas une différence raisonnable avec aucun élément jusqu'ici construit dans l'ordre du v . Continuer jusqu'à ce que tous les reals dans l'ordre du r soient épuisés. L'ordre final du v énumérera l'ensemble de Vitali.

L'argument ci-dessus emploie le C. d'une manière flagrante au tout début, bien-en commandant les reals. D'autres utilisations sont plus subtiles. Par exemple, fréquemment une construction par récursion transfinie ne spécifiera pas une valeur unique du pour le A _α+1, donnée l'ordre jusqu'au α, mais spécifiera seulement une condition de que le A _α+1 doit satisfaire, et argue du fait qu'il est possible de remplir cette condition. S'il n'est pas possible de définir un exemple unique d'un tel ensemble à chaque étape, alors il peut être nécessaire d'appeler le C. pour choisir un tels à chaque étape. Pour des inductions/récursions de longueur comptable du , l'axiome plus faible de du choix dépendant , C.

Voir également

Epsilon-induction

Random links: