Transfinite recursion

Transfinite recursion defines a sequence of objects along the ordinals, specifying each value from earlier values and, at limit ordinals, from the preceding sequence.

Successor ordinal: An ordinal of the form α + 1, immediately following an ordinal α. At successor stages, the next value is computed from the value at the preceding stage.
Ordinal: An order type of a well-ordered set, represented in set theory by a transitive set well-ordered by membership. Ordinals index the stages of the recursion and distinguish successor stages from limits.
Cumulative hierarchy: The hierarchy of sets built in stages by repeatedly taking power sets and unions at limit stages. Its stages are defined directly by transfinite recursion along the ordinals.
Primitive recursion: A scheme defining natural-number functions from initial functions by finitely iterated successor-step rules. It recurses over natural numbers rather than arbitrary ordinal stages.
Limit ordinal: A nonzero ordinal that is not a successor ordinal. At limit stages, a rule combines or otherwise depends on the entire earlier sequence.
Ordinal arithmetic: Arithmetic operations on ordinals whose results depend on the order of their operands. Expressions such as α + 1 identify successor stages and describe recursion lengths.
Constructible universe: The class of sets built in stages using definability over earlier stages. The levels Lα are formed by a recursive successor rule and unions at limits.
Structural recursion: A definition over inductively generated objects that computes each value from values on immediate substructures. Its stages follow object structure, not a single ordinal-indexed sequence.
Well-ordering: A linear ordering in which every nonempty subset has a least element. Ordinals provide the well-ordered stages that make the recursive definition proceed without circularity.
Function: A relation assigning exactly one output to each element of a specified domain. A transfinite recursive definition determines a function whose domain is an ordinal.

Linked from 9 pages