Page 55 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 47
There are further important structural properties of ordinals:
Exercise1. a)Forα,β∈Ordwehaveαβiffα⊆β.b)Ifx⊆Ordisasetof ordinals then x ∈ Ord and x ∈ Ord. c) For every α ∈ Ord the set α+1 = α∪{α} is the immediate successor of α with respect to <.
Definition 2.6. An ordinal α is a successor ordinal if it is of the form α = β + 1. An ordinal α is a limit ordinal if α is not a successor ordinal and α ̸= 0.
The axiom of infinity states that there exists a limit ordinal.
Definition 2.7. Let ω be the smallest limit ordinal. A set n is a natural number
if n < ω. So ω is the set of natural numbers. The latter definition is justified by
Theorem 2.8. The structure (ω, 0, +1) satisfies the Peano axioms. In particular the principle of complete induction holds:
∀X ⊆ ω(0 ∈ X ∧ ∀n(n ∈ X → n + 1 ∈ X) → X = ω).
2.2 Induction and recursion
The natural numbers form an initial segment of the ordinal numbers:
n ∈ ω → n ∈ Ord .
The most remarkable fact about ordinals is that the principles of induction and recursion can be extended from the natural numbers to all the ordinals.
Theorem 2.9. Let φ(v,w⃗) be an ∈-formula. Then
∀w⃗(∃α ∈ Ordφ(α,w⃗) → ∃α ∈ Ord(φ(α,w⃗) ∧ ∀β < α¬φ(β,w⃗))).
Proof. Assume φ(α,w⃗). Let x = {β α|φ(β,w⃗)}. Then x ̸= ∅. By the axiom of foundation take an ∈-minimal element α′ ∈ x. Then ∀β < α′¬φ(β,w⃗) and
φ ( α ′ , w⃗ ) ∧ ∀ β < α ′ ¬ φ ( β , w⃗ ) ) .

This theorem can be reformulated as an induction principle which looks more like the familiar principle of complete induction. According to the various types of ordinals one distinguishes the initial case 0, the successor case, and the limit case.
Theorem 2.10. Let φ(v,w⃗) be an ∈-formula and assume that − φ(0,w⃗),
− ∀α∈Ord(φ(α,w⃗)→φ(α+1,w⃗)),
− ∀α(α is a limit ordinal → (∀β < αφ(β,w⃗) → φ(α,w⃗))). T h e n ∀ α ∈ O r d φ ( α , w⃗ ) .