{{Short description|Mathematical result on ordinals}}
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>f</math> from the class Ord of ordinal numbers to itself such that: * <math>f</math> is '''strictly increasing''': <math>f(\alpha)<f(\beta)</math> whenever <math>\alpha<\beta</math>. * <math>f</math> is '''continuous''': for every limit ordinal <math>\lambda</math> (i.e. <math>\lambda</math> is neither zero nor a successor), <math>f(\lambda)=\sup\{f(\alpha):\alpha<\lambda\}</math>. It can be shown that if <math>f</math> is normal then <math>f</math> commutes with suprema; for any nonempty set <math>A</math> of ordinals, :<math>f(\sup A)=\sup f(A) = \sup\{f(\alpha):\alpha \in A\}</math>. Indeed, if <math>\sup A</math> is 0 or a successor ordinal then <math>\sup A</math> is an element of <math>A</math> and the equality follows from the increasing property of <math>f</math>. If <math>\sup A</math> is a limit ordinal then the equality follows from the continuous property of <math>f</math>.
A '''fixed point''' of a normal function is an ordinal <math>\beta</math> such that <math>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>\alpha</math>, there exists an ordinal <math>\beta</math> such that <math>\beta\geq\alpha</math> and <math>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>f(\gamma)\ge\gamma</math> for all ordinals <math>\gamma</math> and that <math>f</math> commutes with suprema. Given these results, inductively define an increasing sequence <math>\langle\alpha_n\rangle_{n<\omega}</math> by setting <math>\alpha_0 = \alpha</math>, and <math>\alpha_{n+1} = f(\alpha_n)</math> for <math>n\in\omega</math>. Let <math>\beta = \sup_{n<\omega} \alpha_n</math>, so <math>\beta\ge\alpha</math>. Moreover, because <math>f</math> commutes with suprema, :<math>f(\beta) = f(\sup_{n<\omega} \alpha_n)</math> :<math>\qquad = \sup_{n<\omega} f(\alpha_n)</math> :<math>\qquad = \sup_{n<\omega} \alpha_{n+1}</math> :<math>\qquad = \beta</math> The last equality follows from the fact that the sequence <math>\langle\alpha_n\rangle_n</math> increases. <math> \square </math>
As an aside, it can be demonstrated that the <math>\beta</math> found in this way is the smallest fixed point greater than or equal to <math>\alpha</math>.
== Example application == The function ''f'' : Ord → Ord, ''f''(''α'') = ω<sub>''α''</sub> is normal (see initial ordinal). Thus, there exists an ordinal ''θ'' such that ''θ'' = ω<sub>''θ''</sub>. In fact, the lemma shows that there is a closed, unbounded class of such ''θ''.
==References== {{refbegin}} * {{cite book | author = Levy, A. | title = Basic Set Theory | year = 1979 | publisher = Springer | id = Republished, Dover, 2002. | isbn = 978-0-387-08417-6 | url-access = registration | url = https://archive.org/details/basicsettheory00levy_0 }} *{{cite journal | author= Veblen, O. | authorlink = Oswald Veblen | title = Continuous increasing functions of finite and transfinite ordinals | journal = Trans. Amer. Math. Soc. | volume = 9 | year = 1908 | pages = 280–292 | doi= 10.2307/1988605 | issue = 3 | jstor= 1988605 | issn= 0002-9947| doi-access = free }} {{refend}}
Category:Ordinal numbers Normal Functions Category:Lemmas in set theory Category:Articles containing proofs