Fixed-point lemma for normal functions explained

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

f from the class Ord of ordinal numbers to itself such that:f is strictly increasing: f(\alpha)<f(\beta) whenever \alpha<\beta .f is continuous: for every limit ordinal λ (i.e. λ is neither zero nor a successor), f( λ ) = \sup\{f(\alpha):\alpha< λ \} .It can be shown that if f is normal then f commutes with suprema; for any nonempty set A of ordinals,f(\sup A) = \sup f(A) = \sup\{f(\alpha):\alpha \in A\} .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

\beta such that 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

\alpha , there exists an ordinal \beta such that \beta\geq\alpha and 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(\gamma)\ge\gamma for all ordinals \gamma and that f commutes with suprema. Given these results, inductively define an increasing sequence \langle\alpha _{n\rangle} _{n<\omega} by setting \alpha _{0} = \alpha , and \alpha _{n+1} = f(\alpha _{n)} for n\in\omega . Let \beta = \sup _{n<\omega} \alpha _{n} , so \beta\ge\alpha . Moreover, because f commutes with suprema, f(\beta) = f(\sup _{n<\omega} \alpha _{n)} = \sup _{n<\omega} f(\alpha _{n)} = \sup _{n<\omega} \alpha _{n+1} = \beta The last equality follows from the fact that the sequence \langle\alpha _{n\rangle} _{n} increases. \square

As an aside, it can be demonstrated that the

\beta found in this way is the smallest fixed point greater than or equal to \alpha .

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

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