Transfinite Recursion

Set Theory · Axiom Academy

Defining functions on ordinals recursively using zero, successor, and limit cases. To define a function f on ordinals recursively, we specify three components: The key insight: at each stage, we define f in terms of values already computed at earlier ordinals. We can define ordinal addition α + β recursively in the second argument: This definition builds addition step by step, starting from α and incrementing through the ordinals. 3. The Cumulative Hierarchy V α The cumulative hierarchy of sets is defined by transfinite recursion on ordinal α: Each level builds on all previous levels, creating a hierarchy that contains all sets in ZFC. 4. Well-Foundedness Guarantees Termination Why does transfinite recursion always produce a unique function? Because the ordinals are well-founded: every non-empty set of ordinals has a least element. This is analogous to why recursion on natural numbers terminates: we always eventually reach 0. 5. Recursion Theorem for Ordinals The formal justification for transfinite recursion is the Recursion Theorem: This theorem guarantees that recursive definitions are legitimate and produce well-defined functions.

This is the written version of the interactive lesson above. See the full Set Theory course.