Transfinite Induction - Transfinite Recursion

Transfinite recursion is a method of constructing or defining something and is closely related to the concept of transfinite induction. As an example, a sequence of sets A_α is defined for every ordinal α, by specifying how to determine A_α from the sequence of A_β for β < α.

More formally, we can state the Transfinite Recursion Theorem as follows. Given a class function G: V → V, there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that

F(α) = G(F α) for all ordinals α.

As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is that given a set g₁, and class functions G₂, G₃, there exists a unique function F: Ord → V such that

• F(0) = g₁,
• F(α + 1) = G₂(F(α)), for all α ∈ Ord,
• F(λ) = G₃(F λ), for all limit λ ≠ 0.

Note that we require the domains of G₂, G₃ 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 well-founded relation R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; that is, for any x, the collection of all y such that y R x must be a set.)