Fixed-point lemma for normal functions

The fixed-point lemma for normal functions is a basic result in axiomatic set theory; it states that any normal function has arbitrarily large fixed points. A formal version and proof (using the Zermelo-Fraenkel axioms) follow.

Table of contents

1 Formal version 2 Proof 3 Notes

Formal version

Let f : Ord → Ord be a normal function. Then for every α ∈ Ord, there exists a β ∈ Ord such that β ≥ α and f(β) = β.

Proof

First of all, it is clear that for any α ∈ Ord, f(α) ≥ &alpha. If this was not the case, we could choose a minimal α with f(α) < α; then, since f is normal and thus monotone, f(f(α)) < f(α), which is a contradiction to α being minimal.

We now declare a sequence <α_n> (n < ω) by setting α₀ = α, and α_{n + 1} = f(α_n) for n < ω, and define β = sup <α_n>. There are three possible cases:

1. β = 0. Then we have α_n = 0 for all n, and thus f(β) = 0.
2. β = δ + 1 for an ordinal number δ. Then there exists m < ω such that for all n ≥ m, α_n = δ + 1. It follows that f(δ + 1) = f(α_m) = α_{m + 1} = δ + 1, and thus f(β) = β.
3. β is a limit ordinal. We first observe that sup <f(ν) : ν < β> = sup <f(α_n) : n < ω>. "≥" is trivial; for ≤, we choose ν < β, then find an n with α_n > ν, and since f is monotone, we have f(α_n) > f(ν). Now we have f(β) = sup <f(ν) : ν < β> (since f is continuous), and thus f(β) = sup <f(α_n) : n < ω> = sup < α_n : n < ω > = β.

Notes

It is easily checked that the function f : Ord → Ord, f(α) = א_α is normal; thus, there exists an ordinal Θ such that Θ = א_Θ. In fact, the above lemma shows that there are infinitely many such Θ.