Representation of the ordinal numbers up to ω^{ω}. Each turn of the spiral represents one power of ω. Transfinite induction requires proving a base case (used for 0), a successor case (used for those ordinals which have a predecessor), and a limit case (used for ordinals which don't have a predecessor).
Transfinite induction is an extension of mathematical induction to wellordered sets, for example to sets of ordinal numbers or cardinal numbers.
Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true (including the case that P(0) is true given the vacuously true statement that P(α) is true for all \alpha\in\emptyset). Then transfinite induction tells us that P is true for all ordinals.
That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.
Usually the proof is broken down into three cases:

Zero case: Prove that P(0) is true.

Successor case: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α).

Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(β) for all β < λ].
Notice that 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 a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.
Contents

Transfinite recursion 1

Relationship to the axiom of choice 2

See also 3

Notes 4

References 5

External links 6
Transfinite recursion
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, a basis for a (possibly infinitedimensional) vector space can be created by choosing a vector v_0 and for each ordinal α choosing a vector that is not in the span of the vectors \{v_{\beta}\beta<\alpha\}. 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^{[1]} G: V → V (where V is the Class (set theory) of all sets), there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that

F(α) = G(F \upharpoonright α) for all ordinals α, where \upharpoonright denotes the restriction of F'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 set g_{1}, and class functions G_{2}, G_{3}, there exists a unique function F: Ord → V such that

F(0) = g_{1},

F(α + 1) = G_{2}(F(α)), for all α ∈ Ord,

F(λ) = G_{3}(F \upharpoonright λ), for all limit λ ≠ 0.
Note that we require the domains of G_{2}, G_{3} to be broad enough to make the above properties meaningful. The uniqueness of the sequence satisfying these properties can be proven using transfinite induction.
More generally, one can define objects by transfinite recursion on any wellfounded relation R. (R need not even be a set; it can be a proper class, provided it is a setlike relation; that is, for any x, the collection of all y such that y R x must be a set.)
Relationship to the axiom of choice
Proofs or constructions using induction and recursion often use the axiom of choice to produce a wellordered relation that can be treated by transfinite induction. However, if the relation in question is already wellordered, one can often use transfinite induction without invoking the axiom of choice.^{[2]} For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already wellordered, so the axiom of choice is not needed to wellorder them.
The following construction of the Vitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:

First, wellorder the real numbers (this is where the axiom of choice enters via the wellordering theorem), giving a sequence \langle r_{\alpha}  \alpha < \beta \rangle , where β is an ordinal with the cardinality of the continuum. Let v_{0} equal r_{0}. Then let v_{1} equal r_{α1}, where α_{1} is least such that r_{α1} − v_{0} is not a rational number. Continue; at each step use the least real from the r sequence that does not have a rational difference with any element thus far constructed in the v sequence. Continue until all the reals in the r sequence are exhausted. The final v 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 wellorder 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 a unique value for A_{α+1}, given the sequence up to α, but will specify only a condition that A_{α+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 of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–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.
See also
Notes

^ A class function is a rule assigning each element in the lefthand class to an element in the righthand class. It is not a function because its domain and codomain are not sets.

^ 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 setlike: for any x, the collection of all y such that y R x must be a set.
References
External links
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.