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
[edit]A normal function is a class function from the class Ord of ordinal numbers to itself such that:
- is strictly increasing: whenever .
- is continuous: for every limit ordinal (i.e. is neither zero nor a successor), .
It can be shown that if is normal then commutes with suprema; for any nonempty set of ordinals,
- .
Indeed, if is a successor ordinal then is an element of and the equality follows from the increasing property of . If is a limit ordinal then the equality follows from the continuous property of .
A fixed point of a normal function is an ordinal such that .
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 .
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
[edit]The first step of the proof is to verify that for all ordinals and that commutes with suprema. Given these results, inductively define an increasing sequence by setting , and for . Let , so . Moreover, because commutes with suprema,
The last equality follows from the fact that the sequence 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
[edit]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
[edit]- 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.