Fixed-point lemma for normal functions
From Wikipedia, the free encyclopedia
The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function has arbitrarily large fixed points (Levy 1979: p. 117). It was first proved by Oswald Veblen in 1908.
Contents |
[edit] Background and formal statement
A normal function is a class function f from the class Ord of ordinal numbers to itself so that:
- f is increasing: f(α) ≤ f(β) whenever α ≤ β.
- f is continuous: for every limit ordinal λ, f(λ) = sup { f(α) : α < λ }.
It can be shown that if f is normal then f commutes with suprema; for any set A of ordinals,
- f(sup A) = sup {f(α) : α ∈ A }.
A fixed point of a normal function is an ordinal β such that f(β) = β.
The fixed point lemma states that the class of fixed points of any normal function is nonempty and in fact is unbounded: given any ordinal α, there exists an ordinal β such that β ≥ α and f(β) = β.
The continuity of the normal function implies the class of fixed points is closed (the supremum of any subset of the class of fixed points is again a fixed point). Thus the fixed point lemma is equivalent to the statement that the fixed points of a normal function form a closed and unbounded class.
[edit] Proof
The first step of the proof is to verify that f(γ) ≥ γ for all ordinals γ and that f commutes with suprema. Given these results, inductively define an increasing sequence <αn> (n < ω) by setting α0 = α, and αn+1 = f(αn) for n ∈ ω. Let β = sup {αn : n ∈ ω}, so β ≥ α. Moreover, because f commutes with suprema,
- f(β) = f(sup {αn : n < ω})
- = sup {f(αn) : n < ω}
- = sup {αn+1 : n < ω}
- = β
The last equality follows from the fact that the sequence <αn> increases.
[edit] Example application
The function f : Ord → Ord, f(α) = אα is normal (see aleph number). Thus, there exists an ordinal Θ such that Θ = אΘ. In fact, the lemma shows that there is a closed, unbounded class of such Θ.
[edit] References
- Levy, A. (1979). Basic Set Theory. Springer. Republished, Dover, 2002. ISBN 0-486-42079-5.
- Veblen, O. (1908). "Continuous increasing functions of finite and transfinite ordinals.". Trans. Amer. Math Soc. 9: 280–292. doi: . Available via JSTOR..