Page 56 - Textos de Matemática Vol. 38

48 PETER KOEPKE
The most important transfinite construction principle is construction by recursion along the ordinals.
Theorem 2.11. Let G : V → V be a definable function. Then there is a unique definable function F : Ord → V which for every α ∈ Ord satisfies the recursion equation
F(α)=G(F ↾α).
Proof. The function F may be defined as the union of all set-sized approxi-
mations behaving similarly:
F = {f|∃γ ∈ Ord(f : γ → V ∧ ∀α ∈ γf(α) = G(f ↾ α))}.
Using the axioms of replacement and union the existence of sufficiently many compatible approximations f can be shown by ordinal induction. ✷
The recursion rule G will usually be described separately for successor and limit ordinals and the initial case 0:
Theorem2.12. LetG0 ∈V andletGsucc :V →V andGlim :V →V be definable functions. Then there is a unique definable function F : Ord → V such that
− F(0)=G0,
− ∀α ∈ OrdF(α + 1) = Gsucc(F(α)),
− ∀α ∈ Ord(α is a limit ordinal → F(α) = Glim(F ↾ α)).
Exercise 2. Prove this form of the recursion theorem from the recursion Theorem 2.11. An example of a recursive construction is the von Neumann hierarchy
(Vα|α ∈ Ord) with − V0 = ∅,
− Vα+1 = P(Vα),
− Vλ = α<λ Vα = range((Vα|α < λ)).
Here P(.) denotes the power set operation which by the powerset axiom maps
sets to sets.
2.3 Ordinal arithmetic
The standard arithmetic operations have well-known recursive definitions which can be extended to all the ordinals by transfinite recursion.