Fixed-point lemma for normal functions

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.

Background and formal statement

A normal function is a class function ${\displaystyle f}$ from the class Ord of ordinal numbers to itself such that:

• ${\displaystyle f}$ is strictly increasing: ${\displaystyle f(\alpha )<f(\beta )}$ whenever ${\displaystyle \alpha <\beta }$.
• ${\displaystyle f}$ is continuous: for every limit ordinal ${\displaystyle \lambda }$ (i.e. ${\displaystyle \lambda }$ is neither zero nor a successor), ${\displaystyle f(\lambda )=\sup\{f(\alpha ):\alpha <\lambda \}}$.

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

${\displaystyle f(\sup A)=\sup f(A)=\sup\{f(\alpha ):\alpha \in A\}}$.

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

A fixed point of a normal function is an ordinal ${\displaystyle \beta }$ such that ${\displaystyle f(\beta )=\beta }$.

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 ${\displaystyle \alpha }$, there exists an ordinal ${\displaystyle \beta }$ such that ${\displaystyle \beta \geq \alpha }$ and ${\displaystyle f(\beta )=\beta }$.

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,

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. ${\displaystyle \square }$

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 θ.

References

• Levy, A. (1979). Basic Set Theory. Springer. ISBN 978-0-387-08417-6. Republished, Dover, 2002.
• Veblen, O. (1908). "Continuous increasing functions of finite and transfinite ordinals". Trans. Amer. Math. Soc. 9 (3): 280–292. doi:10.2307/1988605. ISSN 0002-9947. JSTOR 1988605. Available via JSTOR.