Transfinite induction
Extension of mathematical induction to ordinal numbers.
Transfinite induction takes the familiar idea of mathematical induction and applies it to ordinal numbers. The method works because ZF set theory proves that the ordinals are well-ordered: if a statement isn’t true for every ordinal, there must be a smallest ordinal where it fails. This same reasoning holds for any well-ordered set, but since any such set can be matched up with ordinals in an order-preserving way, it’s enough to prove the principle for ordinals themselves.
A proof by transfinite induction usually splits into three cases, based on the type of ordinal: - **Zero case:** Show the statement holds for 0. - **Successor case:** Show that if it holds for an ordinal α, then it holds for α+1 (sometimes also using that it holds for all smaller ordinals). - **Limit case:** Show that if it holds for every ordinal less than a limit ordinal λ, then it holds for λ.
These cases don’t have to be treated separately in theory—the same logic covers them all—but in practice the proofs often look quite different. Zero is sometimes considered a limit ordinal, and then it may be grouped with the limit case.
Transfinite recursion is a related technique: instead of proving a property for all ordinals, you build a sequence of objects, one for each ordinal. For example, you can construct a basis for a vector space (possibly infinite-dimensional) by starting with the empty set and, at each ordinal α > 0, picking a vector not in the span of the vectors already chosen. The process stops when no such vector remains.
A formal statement of transfinite recursion is: Given a class function G that takes sets to sets, there is a unique transfinite sequence F defined on all ordinals such that for every ordinal α, F(α) = G(F restricted to ordinals less than α). An alternative version breaks the definition into three parts: set F(0) to a given value g1; for successor ordinals, set F(α+1) = G2(F(α)); and for nonzero limit ordinals λ, set F(λ) = G3(F restricted to λ). The uniqueness of such a sequence can be proved using transfinite induction. More broadly, objects can be defined by transfinite recursion on any well-founded relation, as long as the relation is set-like (each element has only a set of predecessors).
Transfinite induction and recursion often rely on the axiom of choice to produce a well-ordering that can be worked with. But if the relation is already well-ordered—fo
- field
- Set theory, mathematical logic
- known_for
- Extending mathematical induction to ordinal numbers; transfinite recursion; relationship to the axiom of choice
Lore & Background
The principle of transfinite induction can be proved by considering the contrapositive form, where a minimal counterexample exists because the class of ordinal numbers is well-ordered. A proof by transfinite induction is often broken down into three cases: the zero case (prove P(0) is true), the successor case (prove P(α+1) follows from P(α) and possibly P(β) for all β<α), and the limit case (prove P(λ) holds if P(β) holds for all β<λ). All three cases are identical except for the type of ordinal considered, though in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and may be treated in proofs in the same case as limit ordinals.
Reader's Guide
Transfinite induction is closely related to transfinite recursion, which constructs a sequence of objects for each ordinal rather than proving a property holds for all ordinals. For example, a basis for a possibly infinite-dimensional vector space can be created by starting with the empty set and for each ordinal α > 0 choosing a vector not in the span of previously chosen vectors. The Transfinite Recursion Theorem states that given a class function G: V → V, there exists a unique transfinite sequence F: Ord → V such that F(α) = G(F ↾ α) for all ordinals α. Proofs using transfinite induction often use the axiom of choice to produce a well-ordered relation, but if the relation is already well-ordered, the axiom of choice may not be needed. For inductions of countable length, the weaker axiom of dependent choice is sufficient.
Did You Know?
- Transfinite induction is an extension of mathematical induction to ordinal numbers.
- Its correctness is a theorem of ZF and relies on the well-ordering of ordinal numbers.
- A proof by transfinite induction is often broken down into zero, successor, and limit cases.
- Transfinite recursion constructs a sequence of objects for each ordinal, similar to transfinite induction.
More in Sets And Logic 1-24
Elsewhere in the Sets And Logic universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record