The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function

Normal function

In axiomatic set theory, a function f : Ord → Ord is called normal iff it is continuous and strictly monotonically increasing. This is equivalent to the following two conditions:...

 has arbitrarily large fixed point

Fixed point (mathematics)

In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...

s (Levy 1979: p. 117). It was first proved by Oswald Veblen

Oswald Veblen

Oswald Veblen was an American mathematician, geometer and topologist, whose work found application in atomic physics and the theory of relativity. He proved the Jordan curve theorem in 1905.-Life:...

 in 1908.

Background and formal statement

A normal function

Normal function

In axiomatic set theory, a function f : Ord → Ord is called normal iff it is continuous and strictly monotonically increasing. This is equivalent to the following two conditions:...

 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

Supremum

In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...

; 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

Club set

In mathematics, particularly in mathematical logic and set theory, a club set is a subset of a limit ordinal which is closed under the order topology, and is unbounded relative to the limit ordinal...

 class.

Proof

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 α₀ = α, 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.

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