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

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.