Fixed point lemma for normal functions

Background and formal statement

A normal function is a class function f from the class Ord of ordinal numbers to itself such that:

It can be shown that if f is normal then f commutes with suprema; for any nonempty set A of ordinals,

Indeed, if sup A is a successor ordinal then sup A is an element of A and the equality follows from the increasing property of f. If sup A is a limit ordinal then the equality follows from the continuous property of f.

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.

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 α₀ = α, and α_n+1 = f(α_n) for n ∈ ω. Let β = sup {α_n : n ∈ ω}, so β ≥ α. Moreover, because f commutes with suprema,

The last equality follows from the fact that the sequence <α_n> increases. ◻

As an aside, it can be demonstrated that the β found in this way is the smallest fixed point greater than or equal to α.

Example application

The function f : Ord → Ord, f(α) = ω_α is normal (see initial ordinal). Thus, there exists an ordinal θ such that θ = ω_θ. In fact, the lemma shows that there is a closed, unbounded class of such θ.