# 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.

## Contents

## Background and formal statementEdit

A normal function is a class function *f* from the class Ord of ordinal numbers to itself such that:

*f*is**strictly increasing**:*f*(α) < f(β) whenever α < β.*f*is**continuous**: for every limit ordinal λ (i.e. λ is neither zero nor a successor),*f*(λ) = sup { f(α) : α < λ }.

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*}.

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 β such that *f*(β) = β.

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 *f*(β) = β.

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.

## ProofEdit

The first step of the proof is to verify that *f*(γ) ≥ γ for all ordinals γ and that *f* commutes with suprema. Given these results, inductively define an increasing sequence <α_{n}> (*n* < ω) by setting α_{0} = α, and α_{n+1} = *f*(α_{n}) for *n* ∈ ω. Let β = sup {α_{n} : *n* ∈ ω}, so β ≥ α. Moreover, because *f* commutes with suprema,

*f*(β) =*f*(sup {α_{n}:*n*< ω})- = sup {
*f*(α_{n}) :*n*< ω} - = sup {α
_{n+1}:*n*< ω} - = β.

The last equality follows from the fact that the sequence <α_{n}> 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 applicationEdit

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 θ.

## ReferencesEdit

- 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.