Fixed-point lemma for normal functions (original) (raw)

From Wikipedia, the free encyclopedia

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

[edit]

A normal function is a class function f {\displaystyle f} {\displaystyle f} from the class Ord of ordinal numbers to itself such that:

It can be shown that if f {\displaystyle f} {\displaystyle f} is normal then f {\displaystyle f} {\displaystyle f} commutes with suprema; for any nonempty set A {\displaystyle A} {\displaystyle A} of ordinals,

f ( sup A ) = sup f ( A ) = sup { f ( α ) : α ∈ A } {\displaystyle f(\sup A)=\sup f(A)=\sup\{f(\alpha ):\alpha \in A\}} {\displaystyle f(\sup A)=\sup f(A)=\sup\{f(\alpha ):\alpha \in A\}}.

Indeed, if sup A {\displaystyle \sup A} {\displaystyle \sup A} is a successor ordinal then sup A {\displaystyle \sup A} {\displaystyle \sup A} is an element of A {\displaystyle A} {\displaystyle A} and the equality follows from the increasing property of f {\displaystyle f} {\displaystyle f}. If sup A {\displaystyle \sup A} {\displaystyle \sup A} is a limit ordinal then the equality follows from the continuous property of f {\displaystyle f} {\displaystyle f}.

A fixed point of a normal function is an ordinal β {\displaystyle \beta } {\displaystyle \beta } such that f ( β ) = β {\displaystyle f(\beta )=\beta } {\displaystyle 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 α {\displaystyle \alpha } {\displaystyle \alpha }, there exists an ordinal β {\displaystyle \beta } {\displaystyle \beta } such that β ≥ α {\displaystyle \beta \geq \alpha } {\displaystyle \beta \geq \alpha } and f ( β ) = β {\displaystyle f(\beta )=\beta } {\displaystyle 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.

The first step of the proof is to verify that f ( γ ) ≥ γ {\displaystyle f(\gamma )\geq \gamma } {\displaystyle f(\gamma )\geq \gamma } for all ordinals γ {\displaystyle \gamma } {\displaystyle \gamma } and that f {\displaystyle f} {\displaystyle f} commutes with suprema. Given these results, inductively define an increasing sequence ⟨ α n ⟩ n < ω {\displaystyle \langle \alpha _{n}\rangle _{n<\omega }} {\displaystyle \langle \alpha _{n}\rangle _{n<\omega }} by setting α 0 = α {\displaystyle \alpha _{0}=\alpha } {\displaystyle \alpha _{0}=\alpha }, and α n + 1 = f ( α n ) {\displaystyle \alpha _{n+1}=f(\alpha _{n})} {\displaystyle \alpha _{n+1}=f(\alpha _{n})} for n ∈ ω {\displaystyle n\in \omega } {\displaystyle n\in \omega }. Let β = sup n < ω α n {\displaystyle \beta =\sup _{n<\omega }\alpha _{n}} {\displaystyle \beta =\sup _{n<\omega }\alpha _{n}}, so β ≥ α {\displaystyle \beta \geq \alpha } {\displaystyle \beta \geq \alpha }. Moreover, because f {\displaystyle f} {\displaystyle f} commutes with suprema,

f ( β ) = f ( sup n < ω α n ) {\displaystyle f(\beta )=f(\sup _{n<\omega }\alpha _{n})} {\displaystyle f(\beta )=f(\sup _{n<\omega }\alpha _{n})}

= sup n < ω f ( α n ) {\displaystyle \qquad =\sup _{n<\omega }f(\alpha _{n})} {\displaystyle \qquad =\sup _{n<\omega }f(\alpha _{n})}

= sup n < ω α n + 1 {\displaystyle \qquad =\sup _{n<\omega }\alpha _{n+1}} {\displaystyle \qquad =\sup _{n<\omega }\alpha _{n+1}}

= β {\displaystyle \qquad =\beta } {\displaystyle \qquad =\beta }

The last equality follows from the fact that the sequence ⟨ α n ⟩ n {\displaystyle \langle \alpha _{n}\rangle _{n}} {\displaystyle \langle \alpha _{n}\rangle _{n}} increases. ◻ {\displaystyle \square } {\displaystyle \square }

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

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