transfinite induction
Jump to navigation
Jump to search
English
[edit]Noun
[edit]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.
- 1967, Kam-Tim Leung, Doris Lai-chue Chen, Elementary Set Theory, Parts I and II, Hong Kong University Press, page 108:
- The validity of the principle of transfinite induction for well-ordered sets enables us to carry out proofs by transfinite induction and definitions by transfinite induction. A proof by transfinite induction is a direct application of the principle when it is required to show that each element of a well-ordered set A has a property P. […] To understand the method of definition by transfinite induction some preparation is necessary.
- 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 is reducible to ordinary induction. Gentzen in his proof used transfinite induction up to .
- 2009, Jan von Plato, “Gentzen's Logic”, in Dov M. Gabbay, John Woods, editors, Handbook of the History of Logic, Volume 5: Logic from Russell to Church, Elsevier (North-Holland), page 667:
- The published version of 1936 had a different proof based on the famous principle of transfinite induction up to the ordinal by which consistency[of Peano arithmetic] followed. A third proof of 1938 used transfinite induction but the logical system was a sequent calculus.
Usage notes
[edit]- Suppose is a property defined for any ordinal number , and that whenever is true for all , then is also true. Then transfinite induction tells us that is true for all ordinals.
- A transfinite induction proof is typically broken down into three cases:
- Zero case: .
- Successor case: For any ordinal number that is the successor of some ordinal , . (Alternatively, if necessary, .)
- Limit case: For any limit ordinal (non-successor ordinal) , .
- 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, .
Synonyms
[edit]- (extension of mathematical induction to well-ordered sets of transfinite cardinality): Noetherian induction, structural induction, well-founded induction
Hyponyms
[edit]- (extension of mathematical induction to well-ordered sets of transfinite cardinality): ε-induction, epsilon-induction
Related terms
[edit]Translations
[edit]extension of mathematical induction to well-ordered sets of transfinite cardinality
|
See also
[edit]Further reading
[edit]Epsilon-induction on Wikipedia.Wikipedia
Mathematical induction on Wikipedia.Wikipedia
Transfinite number on Wikipedia.Wikipedia
Well-founded relation on Wikipedia.Wikipedia