Transfinite induction
Extension of mathematical induction to ordinal numbers.
Last updated
Its correctness in ZF set theory relies on ordinals being well-ordered, so any false statement has a minimal counterexample.[1] The principle also holds for any well-ordered set, but ordinals suffice because every well-ordered set can be indexed by ordinals.[1] Ordinal numbers are the domain for a generalization of ordinary mathematical induction known as transfinite induction.[1]
Quick Facts
- Field
- Set theory, mathematical logic
Facts from the source article.
Key facts and history
Transfinite induction is a theorem of ZF set theory.[1] Special cases of recursion define F(0), F(α+1), and F(λ) for limit ordinals λ separately.[2] Proofs using transfinite induction often require the axiom of choice to produce a well-ordered relation.[3] For example, results about Borel sets use transfinite induction on their ordinal rank, which is already well-ordered.[3]
Transfinite induction can be applied without the axiom of choice when the underlying relation is already well-ordered, as occurs with the ordinal ranks of Borel sets.[3]
References
- Wikipedia, "Transfinite induction" (CC BY-SA 4.0), which cites: J. Schlöder, Ordinal Arithmetic. Accessed 2022-03-24. (original not read by us) en.wikipedia.org
- Wikipedia, "Transfinite induction" (CC BY-SA 4.0), which cites: A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a func (original not read by us) en.wikipedia.org
- Wikipedia, "Transfinite induction" (CC BY-SA 4.0), which cites: In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation R is set-like: for any x, the collectio (original not read by us) en.wikipedia.org
Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Transfinite induction (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.
More in Sets And Logic
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Transfinite induction (CC BY-SA 4.0).
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced