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

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

$f$ is strictly increasing: $f(\alpha) whenever \alpha<\beta .$
$f$ is continuous: for every limit ordinal $\lambda$ (i.e. $\lambda$ is neither zero nor a successor), $f(\lambda)=\sup\{f(\alpha):\alpha<\lambda\}$ .

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) = \sup\{f(\alpha):\alpha \in 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 $\beta$ such that $f(\beta)=\beta$ .

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 $\alpha$ , there exists an ordinal $\beta$ such that $\beta\geq\alpha$ and $f(\beta)=\beta$ .

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 $f(\gamma)\ge\gamma$ for all ordinals $\gamma$ and that $f$ commutes with suprema. Given these results, inductively define an increasing sequence $\langle\alpha_n\rangle_{n<\omega}$ by setting $\alpha_0 = \alpha$ , and $\alpha_{n+1} = f(\alpha_n)$ for $n\in\omega$ . Let $\beta = \sup_{n<\omega} \alpha_n$ , so $\beta\ge\alpha$ . Moreover, because $f$ commutes with suprema,

: $f(\beta) = f(\sup_{n<\omega} \alpha_n)$

: $\qquad = \sup_{n<\omega} f(\alpha_n)$

: $\qquad = \sup_{n<\omega} \alpha_{n+1}$

: $\qquad = \beta$

The last equality follows from the fact that the sequence $\langle\alpha_n\rangle_n$ increases. $\square$

As an aside, it can be demonstrated that the $\beta$ found in this way is the smallest fixed point greater than or equal to $\alpha$ .

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

References

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

}}

Category:Ordinal numbers

Normal Functions

Category:Lemmas in set theory

Category:Articles containing proofs