transfinite induction

== English == === Noun === transfinite induction (plural transfinite inductions) (mathematics, set theory) An extension of mathematical induction to well-ordered sets of transfinite cardinality, such as sets of ordinal numbers or cardinal numbers. 1970 [Addison-Wesley], Howard DeLong, A Profile of Mathematical Logic, Dover, 2004, page 218, Just what kinds of transfinite inductions are to be considered finitary is debatable. Transfinite induction up to an arbitrary ordinal is certainly not finitary. However, it can be shown that certain transfinite inductions are reducible to ordinary mathematical inductions. For example, induction up to ω ω {\displaystyle \omega ^{\omega }} is reducible to ordinary induction. Gentzen in his proof used transfinite induction up to ε 0 {\displaystyle \varepsilon _{0}} . ==== Usage notes ==== Suppose P ( α ) {\displaystyle P(\alpha )} is a property defined for any ordinal number α {\displaystyle \alpha } , and that whenever P ( β ) {\displaystyle P(\beta )} is true for all β < α {\displaystyle \beta <\alpha } , then P ( α ) {\displaystyle P(\alpha )} is also true. Then transfinite induction tells us that P {\displaystyle P} is true for all ordinals. A transfinite induction proof is typically broken down into three cases: Zero case: P ( 0 ) {\displaystyle P(0)} . Successor case: For any ordinal number α + 1 {\displaystyle \alpha +1} that is the successor of some ordinal α {\displaystyle \alpha } , P ( α ) ⟹ P ( α + 1 ) {\displaystyle P(\alpha )\implies P(\alpha +1)} . (Alternatively, if necessary, [ ∀ β < α , P ( β ) ] ⟹ P ( α ) {\displaystyle [\forall \beta <\alpha ,P(\beta )]\implies P(\alpha )} .) Limit case: For any limit ordinal (non-successor ordinal) λ {\displaystyle \lambda } , [ ∀ β < λ , P ( β ) ] ⟹ P ( λ ) {\displaystyle [\forall \beta <\lambda ,P(\beta )]\implies P(\lambda )} . Some proofs involve first using the (historically controversial) axiom of choice to construct a well-ordered relation (enabling transfinite induction over its equivalence classes). If a well-ordered relation already exists, this step is unnecessary. For many purposes, transfinite induction is used only up to the smallest epsilon number, ε 0 {\displaystyle \varepsilon _{0}} . ==== Synonyms ==== (extension of mathematical induction to well-ordered sets of transfinite cardinality): Noetherian induction, structural induction, well-founded induction ==== Hyponyms ==== (extension of mathematical induction to well-ordered sets of transfinite cardinality): ε-induction, epsilon-induction ==== Related terms ==== transfinite number transfinite recursion ==== Translations ==== === See also === well-founded relation === Further reading === Epsilon-induction on Wikipedia.Wikipedia Mathematical induction on Wikipedia.Wikipedia Transfinite number on Wikipedia.Wikipedia Well-founded relation on Wikipedia.Wikipedia