Transfinite induction is an extension ofmathematical induction towell-ordered sets, for example to sets ofordinal numbers orcardinal numbers. Its correctness is a theorem ofZFC.^[1]

Let${\displaystyle P(\alpha )}$ be aproperty defined for all ordinals${\displaystyle \alpha }$. Suppose that whenever${\displaystyle P(\beta )}$ is true for all, then${\displaystyle P(\alpha )}$ is also true.^[2] Then transfinite induction tells us that${\displaystyle P}$ is true for all ordinals.

Usually the proof is broken down into three cases:

• Zero case: Prove that${\displaystyle P(0)}$ is true.
• Successor case: Prove that for anysuccessor ordinal${\displaystyle \alpha +1}$,${\displaystyle P(\alpha +1)}$ follows from${\displaystyle P(\alpha )}$ (and, if necessary,${\displaystyle P(\beta )}$ for all).
• Limit case: Prove that for anylimit ordinal${\displaystyle \lambda }$, if${\displaystyle P(\beta )}$ holds for all, then${\displaystyle P(\lambda )}$.

All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered alimit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.

Transfinite recursion is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal.

As an example, abasis for a (possibly infinite-dimensional)vector space can be created by starting with the empty set and for each ordinalα > 0 choosing a vector that is not in thespan of the vectors. This process stops when no vector can be chosen.

More formally, we can state the Transfinite Recursion Theorem as follows:

Transfinite Recursion Theorem (version 1). Given a class function^[3]G:V →V (whereV is theclass of all sets), there exists a uniquetransfinite sequenceF: Ord →V (where Ord is the class of all ordinals) such that

${\displaystyle F(\alpha )=G(F\upharpoonright \alpha )}$ for all ordinalsα, where${\displaystyle \upharpoonright }$ denotes the restriction ofF's domain to ordinals < α.

As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is the following:

Transfinite Recursion Theorem (version 2). Given a setg₁, and class functionsG₂,G₃, there exists a unique functionF: Ord →V such that

• F(0) =g₁,
• F(α + 1) =G₂(F(α)), for allα ∈ Ord,
• ${\displaystyle F(\lambda )=G_3(F\upharpoonright \lambda )}$, for all limitλ ≠ 0.

Note that we require the domains ofG₂,G₃ to be broad enough to make the above properties meaningful. The uniqueness of the sequence satisfying these properties can be proved using transfinite induction.

More generally, one can define objects by transfinite recursion on anywell-founded relationR. (R need not even be a set; it can be aproper class, provided it is aset-like relation; i.e. for anyx, the collection of ally such thatyRx is a set.)

Proofs or constructions using induction and recursion often use theaxiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice.^[4] For example, many results aboutBorel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.

The following construction of theVitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:

First,well-order thereal numbers (this is where the axiom of choice enters via thewell-ordering theorem), giving a sequence, where β is an ordinal with thecardinality of the continuum. Letv₀ equalr₀. Then letv₁ equalr_α1, whereα₁ is least such thatr_α1 − v₀ is not arational number. Continue; at each step use the least real from ther sequence that does not have a rational difference with any element thus far constructed in thev sequence. Continue until all the reals in ther sequence are exhausted. The finalv sequence will enumerate the Vitali set.

The above argument uses the axiom of choice in an essential way at the very beginning, in order to well-order the reals. After that step, the axiom of choice is not used again.

Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify aunique value forA_α+1, given the sequence up toα, but will specify only acondition thatA_α+1 must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step. For inductions and recursions ofcountable length, the weakeraxiom of dependent choice is sufficient. Because there are models ofZermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.

• Mathematical induction
• ∈-induction
• Transfinite number
• Well-founded induction
• Zorn's lemma

• Suppes, Patrick (1972), "Section 7.1",Axiomatic set theory,Dover Publications,ISBN 0-486-61630-4

• Emerson, Jonathan;Lezama, Mark &Weisstein, Eric W."Transfinite Induction".MathWorld.

• Mathematical induction
• Ordinal numbers
• Recursion

• Articles with short description
• Short description is different from Wikidata