Main Page | See live article | Alphabetical index

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 α0 = α, and αn + 1 = fn) 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 nm, αn = δ + 1. It follows that f(δ + 1) = fm) = αm + 1 = δ + 1, and thus f(β) = β.
  3. β is a limit ordinal. We first observe that sup <f(ν) : ν < β> = sup <fn) : n < ω>. "≥" is trivial; for ≤, we choose ν < β, then find an n with αn > ν, and since f is monotone, we have fn) > f(ν). Now we have f(β) = sup <f(ν) : ν < β> (since f is continuous), and thus f(β) = sup <fn) : 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 Θ.