Fixed-point lemma for normal functions: Difference between revisions

Revision as of 02:05, 8 April 2011

Latest revision as of 06:27, 20 December 2024

(28 intermediate revisions by 24 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]] stating that any [[normal function]] has arbitrarily large [[fixed point (mathematics)|fixed point]]s (Levy 1979: p. 117). It was first proved by [[Oswald Veblen]] in 1908.

The '''fixed-point lemma for normal functions''' is a basic result in [[axiomatic set theory]] stating that any [[normal function]] has arbitrarily large [[fixed point (mathematics)|fixed point]]s (Levy 1979: p.  117). It was first proved by [[Oswald Veblen]] in 1908.

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

The first 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. Given these results, inductively define an increasing sequence &lt;α<submath>''\langle\alpha_n\rangle_{n''<\omega}</submath>&gt; (''n'' &lt; ω) by setting α_{0</submath>\alpha_0 = α\alpha</math>, and α<submath>''\alpha_{n''+1}} = ''f''(α<sub>''n''\alpha_n)</submath>) for ''<math>n'' ∈ ω\in\omega</math>. Let β<math>\beta = sup \sup_{α_''n'' : ''n'' ∈ &\omega;} \alpha_n</math>, so β ≥ α<math>\beta\ge\alpha</math>. Moreover, because ''<math>f''</math> commutes with suprema,

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

:''f''(β) = ''f''(sup {α_''n'' : ''n'' &lt; ω})

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

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = sup {''f''(α_''n'') : ''n'' &lt; ω}

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

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = sup {α_''n''+1 : ''n'' &lt; ω}

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

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = β.

The last equality follows from the fact that the sequence &lt;α<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 ==

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

{{refbegin}}

* {{cite book

| author = Levy, A.

Line 32 ⟶ 37:

| year = 1979

| publisher = Springer

| id = Republished, Dover, 2002.
| ISBNisbn = 978-0-486387-4207908417-56

| isbnurl-access = 0387084177}}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

| id = Available via [http://links.jstor.org/sici?sici=0002-9947%28190807%299%3A3%3C280%3ACIFOFA%3E2.0.CO%3B2-1 JSTOR].

| doi= 10.2307/1988605

| issue = 3

| publisher= American Mathematical Society

| jstor= 1988605

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

}}

{{refend}}

[[Category:Ordinal numbers]]

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

[[Category:Lemmas in set theory]]

[[Category:Articles containing proofs]]

[[es:Lema del punto fijo para funciones normales]]