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 [math]\displaystyle{ f }[/math] from the class Ord of ordinal numbers to itself such that:
- [math]\displaystyle{ f }[/math] is strictly increasing: [math]\displaystyle{ f(\alpha)\lt f(\beta) }[/math] whenever [math]\displaystyle{ \alpha\lt \beta }[/math].
- [math]\displaystyle{ f }[/math] is continuous: for every limit ordinal [math]\displaystyle{ \lambda }[/math] (i.e. [math]\displaystyle{ \lambda }[/math] is neither zero nor a successor), [math]\displaystyle{ f(\lambda)=\sup\{f(\alpha):\alpha\lt \lambda\} }[/math].
It can be shown that if [math]\displaystyle{ f }[/math] is normal then [math]\displaystyle{ f }[/math] commutes with suprema; for any nonempty set [math]\displaystyle{ A }[/math] of ordinals,
- [math]\displaystyle{ f(\sup A)=\sup f(A) = \sup\{f(\alpha):\alpha \in A\} }[/math].
Indeed, if [math]\displaystyle{ \sup A }[/math] is a successor ordinal then [math]\displaystyle{ \sup A }[/math] is an element of [math]\displaystyle{ A }[/math] and the equality follows from the increasing property of [math]\displaystyle{ f }[/math]. If [math]\displaystyle{ \sup A }[/math] is a limit ordinal then the equality follows from the continuous property of [math]\displaystyle{ f }[/math].
A fixed point of a normal function is an ordinal [math]\displaystyle{ \beta }[/math] such that [math]\displaystyle{ f(\beta)=\beta }[/math].
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 [math]\displaystyle{ \alpha }[/math], there exists an ordinal [math]\displaystyle{ \beta }[/math] such that [math]\displaystyle{ \beta\geq\alpha }[/math] and [math]\displaystyle{ f(\beta)=\beta }[/math].
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 [math]\displaystyle{ f(\gamma)\ge\gamma }[/math] for all ordinals [math]\displaystyle{ \gamma }[/math] and that [math]\displaystyle{ f }[/math] commutes with suprema. Given these results, inductively define an increasing sequence [math]\displaystyle{ \langle\alpha_n\rangle_{n\lt \omega} }[/math] by setting [math]\displaystyle{ \alpha_0 = \alpha }[/math], and [math]\displaystyle{ \alpha_{n+1} = f(\alpha_n) }[/math] for [math]\displaystyle{ n\in\omega }[/math]. Let [math]\displaystyle{ \beta = \sup_{n\lt \omega} \alpha_n }[/math], so [math]\displaystyle{ \beta\ge\alpha }[/math]. Moreover, because [math]\displaystyle{ f }[/math] commutes with suprema,
- [math]\displaystyle{ f(\beta) = f(\sup_{n\lt \omega} \alpha_n) }[/math]
- [math]\displaystyle{ \qquad = \sup_{n\lt \omega} f(\alpha_n) }[/math]
- [math]\displaystyle{ \qquad = \sup_{n\lt \omega} \alpha_{n+1} }[/math]
- [math]\displaystyle{ \qquad = \beta }[/math]
The last equality follows from the fact that the sequence [math]\displaystyle{ \langle\alpha_n\rangle_n }[/math] increases. [math]\displaystyle{ \square }[/math]
As an aside, it can be demonstrated that the [math]\displaystyle{ \beta }[/math] found in this way is the smallest fixed point greater than or equal to [math]\displaystyle{ \alpha }[/math].
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. Republished, Dover, 2002.. ISBN 978-0-387-08417-6. https://archive.org/details/basicsettheory00levy_0.
- Veblen, O. (1908). "Continuous increasing functions of finite and transfinite ordinals". Trans. Amer. Math. Soc. 9 (3): 280–292. doi:10.2307/1988605. Available via JSTOR.. ISSN 0002-9947.
 |  |
