Fixed-point lemma for normal functions: Difference between revisions

Revision as of 11:42, 14 February 2006

Latest revision as of 06:27, 20 December 2024

(46 intermediate revisions by 33 users not shown)

Line 1:

{{Short description|Mathematical result on ordinals}}

The '''fixed-point lemma for normal functions''' is a basic result in [[axiomatic set theory]]; it states that any [[normal function]] has arbitrarily large [[fixed point (mathematics)|fixed point]]s and can often be used to construct [[ordinal number]]s with interesting properties. A formal version and proof (using the [[Zermelo-Fraenkel axioms]]) follows.

The '''fixed-point lemma for normal functions''' is a basic result in [[axiomatic set theory]]; it statesstating that any [[normal function]] has arbitrarily large [[fixed point (mathematics)|fixed point]]s and(Levy can1979: often be used to construct [[ordinal number]]s with interesting propertiesp. 117). AIt formalwas versionfirst andproved proof (using theby [[Zermelo-FraenkelOswald axiomsVeblen]]) followsin 1908.

== Formal version ==

Let ''f'' : [[ordinal number|Ord]] → Ord be a [[normal function]]. Then for every α ∈ Ord, there exists a β ∈ Ord such that β ≥ α and ''f''(β) = β.

== Background and formal statement ==

A [[normal function]] is a [[proper class|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 [[supremum|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 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 [[club set|closed and unbounded]] class.

== Proof ==

WeThe knowfirst 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. WeGiven nowthese declareresults, inductively define an increasing sequence &lt;&alpha;<submath>''\langle\alpha_n\rangle_{n''<\omega}</submath>&gt; (''n'' &lt; &omega;) by setting &alpha;_{0</submath>\alpha_0 = &\alpha;</math>, and &alpha;<submath>''\alpha_{n''+1}} = ''f''(&alpha;<sub>''n''\alpha_n)</submath>) for ''<math>n'' &lt; &\in\omega;,</math>. andLet define &<math>\beta; = sup\sup_{n<\omega} &lt;&alpha;<sub>''n''\alpha_n</submath>&gt;. Clearly, &beta;so &<math>\beta\ge; &\alpha;</math>. SinceMoreover, ''because <math>f''</math> commutes with [[supremum|suprema]], we have

:''<math>f''(&\beta;) = ''f''(sup \sup_{&alpha;_''n'' : ''n'' &lt; &\omega;} \alpha_n) </math>

:<math>\qquad = \sup_{n<\omega} f(\alpha_n)</math>

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = sup {''f''(&alpha;_''n'') : ''n'' &lt; &omega;}

:<math>\qquad = \sup_{n<\omega} \alpha_{n+1}</math>

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = sup {&alpha;_''n''+1 : ''n'' &lt; &omega;}

:<math>\qquad = \beta</math>

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = &beta;

(The last stepequality usesfollows from the fact that the sequence &lt;&alpha;<submath>''n''\langle\alpha_n\rangle_n</submath>&gt; 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 ==

It is easily checked that theThe function ''f'' : Ord &rarr;→ Ord, ''f''(&alpha;''α'') = &#1488;ω_{&alpha;''α''} is normal (see [[alephinitial numberordinal]]);. thusThus, there exists an ordinal &Theta;''θ'' such that &Theta;''θ'' = &#1488;ω_{&Theta;''θ''}. In fact, the above lemma shows that there areis infinitelya manyclosed, unbounded class of such &Theta;''θ''.

==References==

{{unreferencedrefbegin}}

* {{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&ndash;292

| doi= 10.2307/1988605

| issue = 3

| jstor= 1988605

| issn= 0002-9947| doi-access = free

}}

{{refend}}

[[Category:SetOrdinal theorynumbers]]

[[Category:Fixed-point pointstheorems|Normal Functions]]

[[Category:Lemmas in set theory]]

[[Category:Articles containing proofs]]