Vol. 38, No. 1, 2008, 177-181
AN APPLICATION OF HIGHER ORDER FIXED POINTS OF NORMAL FUNCTIONS
Boris ˇSobot1
Abstract. We define higher order fixed points of normal functions, de- scribe them and apply to obtain a constructive proof that, ifκis the least ordinal such that the ultrapowerκI/Fis non-trivial, then that ultrapower has at leastκ+elements.
AMS Mathematics Subject Classification (2000): 03E04, 03E20, 03C20.
Key words and phrases:ultrapower, normal function
Let F be a nonprincipal ultrafilter over a set I. By αI/F we denote the ultrapower Q
i∈I
α/F. The element of αI/F which is the equivalence class of a functionf will be denoted byfF.
It is well known (see [1], page 134) that an ultraproduct of infinite ordinals modulo ultrafilter F is well-ordered iff F isσ-complete. Thus throughout this work we suppose that F is a fixed σ-complete ultrafilter over some I. The following proposition is easy to prove.
Proposition 1. If α < β, then αI/F is isomorphic to an initial segment of βI/F.
Thus we can identifyαI/F with an initial segment ofβI/F. Therefore for α∈Ordwe let, as in [4],
Aα= (αI/F)\ [
β<α
Aβ.
Obviously,Aα+1has exactly one element forα∈Ord; it isfαF, wherefα(i) =α fori∈I. Hence we will be interested only in the case whenαis a limit ordinal.
Also, the described elementfαF is the image ofαunder the natural elementary embedding d : β → βI/F (see [2]), and thus every βI/F contains a copy of β. The main question we consider here is: how many more elements canβI/F have, and on whichAαlevels?
Definition 1. Let αbe a limit ordinal. An ultrafilter F over I is α-descen- dingly incomplete if there is a sequencehXβ :β < αiof elements ofF such that Xβ1 ⊇Xβ2 forβ1 < β2< α and T
β<αXβ =∅; otherwise it isα-descendingly complete.
1Department of Mathematics and Informatics, University of Novi Sad, Trg Dositeja Obradovi´ca 4, 21000 Novi Sad, Serbia, e-mail: [email protected]
Proposition 2. Ifαis a limit ordinal, thenAα=∅iffFis cf(α)-descendingly complete.
But it is known (see [1], page 114) that the following proposition holds.
Proposition 3. The least ordinal α, such that F is α-descendingly incom- plete, is equal to the least cardinalαsuch thatF is α+-incomplete, and it is a measurable cardinal.
So the firstκsuch thatAκ6=∅must be an uncountable measurable cardinal (we will need only the fact thatκis regular). From this point on,κwill denote that cardinal. It is easy to prove that, ifF is κ-descendingly incomplete, then
|Aκ| ≥κ. One can prove (see [3], page 291) the following proposition.
Proposition 4. If F is a nonprincipal κ-complete ultrafilter over κ, then
|Aκ| ≥2κ.
The result we are about to prove is weaker, but the proof gives a better insight into the structure of elements ofAκ. We begin with a lemma analogous to the Cantor Normal Form Theorem and emphasize that all operations that appear in its formulation are ordinal operations.
Lemma 1. Every nonzero ordinal less than κ+ can be represented uniquely in the form
κα0β0+κα1β1+· · ·+καnβn,
whereκ+> α0> α1>· · ·> αn and 0< βk< κ for 0≤k≤n.
Ifξ=κα0β0+κα1β1+· · ·+καnβn is an ordinal represented as in the lemma above, with ¯ξwe shall denoteκα0β0+κα1β1+· · ·+καn−1βn−1. For every such ξ, we will call the set{ξ¯+καnβ : 0 < β < κ} a level (of course, ξ belongs to this set). Thus, if ξand η are on the same level, then ¯ξ= ¯η (but the opposite does not hold).
Definition 2. Letp:κ+→κ+ be a normal function. We define the sequence of functionshpξ:ξ < κ+iin this way:
1) p0=p;
2) pξ+1(α) is theα-th fixed point of pξ;
3) if ξ is a limit ordinal,pξ(α) is the αth ordinal that is fixed for all pη for η < ξ.
It is easy to prove that all the functionspξ forξ < κ+ are normal and map κ+toκ+. We need some more information, contained in the following lemmas:
Lemma 2. The function pξ+1 can be calculated in the following way:
1) pξ+1(0) = supn<ωθn, where θ0= 1 andθn+1=pξ(θn) forn < ω;
2) pξ+1(α+ 1) = supn<ωθn, whereθ0=pξ+1(α) + 1 andθn+1 =pξ(θn) for n < ω;
3) ifαis a limit ordinal, thenpξ+1(α) = supβ<αpξ+1(β).
Lemma 3. If δ is a limit ordinal, then the function pδ can be calculated in the following way:
1) pδ(0) = supξ<δθξ, where θ0 = 1, for ξ < δ θξ+1 = pξ(θξ), and θξ = supη<ξθη for a limit cardinalξ;
2)pδ(α+ 1) = supξ<δθξ, whereθ0=pδ(α) + 1, forξ < δ θξ+1=pξ(θξ), and θξ = supη<ξθη for a limit cardinal ξ < δ;
3) ifαis a limit ordinal, thenpδ(α) = supβ<αpδ(β).
Before we begin with the proof of the main theorem, let us notice that if p(0) > 0 then for every ζ ∈ ran (p) there is the greatest ξ < κ+ such that ζ ∈ ran (pξ). This is beacuse pξ+1(0) > pξ(0) for all ξ < κ+ (easy proof by induction), so the sequencehpξ(0) :ξ < κ+iis cofinal inκ+. Knowing this, let us callζ < κ+ a fixed point of orderδifζbelongs to ran (pδ)\ran (pδ+1).
In the rest of this article, we will consider the functionp:κ+ →κ+ given byp(γ) =κγ. Obviously, it is normal andp(0)>0, so all the preceding results apply to it. Let us also introduce the abbreviation eδ,α=pδ(α), and note that κeδ,α=eδ,α forδ >0.
Theorem 1. If κ is the least cardinal such that the ultrafilter F over I is κ+-incomplete, then|Aκ| ≥κ+.
Proof. We will construct, by recursion onξ, a sequencehgξ:ξ < κ+iof functions such thatYηξ ={i∈I :gη(i)< gξ(i)} ∈F forη < ξ < κ+, thus obtaining an ascending sequence hgFξ :ξ < κ+iof elements ofAκ. So let us define for every ξ < κ+ an elementgξ ∈Aκ such that for allη < ξ
(Iη,ξ) gη<∗gξ
holds. First, letg0be such thatg0F is the minimal element ofAκ, and forξ >0:
1◦ Ifξ=η+ 1, we definegξ(i) =gη(i) + 1.
2◦ Ifξ= ¯ξ+καβ,α=α1+ 1 andβ =β1+ 1, we defineηµ = ¯ξ+καβ1+κα1µ forµ < κ. By Proposition 3F isκ-descendingly incomplete, so there is a sequencehXζ :ζ < κiof elements ofF such that X0 =I,Xζ1 ⊇Xζ2 for ζ1 < ζ2 < κ and T
ζ<κXζ =∅. Now let us definegξ(i) = gηµ(i), where µ= min{ζ < κ:i6∈Xζ}.
3◦ Ifξ= ¯ξ+καβ and β is a limit ordinal, then we define ηµ = ¯ξ+καµfor µ < β and gξ(i) = supµ<βgηµ(i). Since β < κ and κis regular, we have gξ(i)< κ.
4◦ Ifξ= ¯ξ+καβ,αis a limit ordinal not fixed forpandβ =β1+ 1, then we defineηµ = ¯ξ+καβ1+κµforµ < α, and letgξ be defined byhgηµ :µ < αi in the same way gα was defined by hgµ : µ < αi. (This means that we look up which of the rules 2◦−7◦was used for constructinggαand use it to constructgξ too; this depends of the ordinalα. It does not mean that we have to use all elements of the sequencehgηµ :µ < αi.)
5◦ If ξ = ¯ξ+eδ,νβ, eδ,ν is a fixed point of order δ, whereδ =δ1+ 1, β = β1+ 1 andν = ν1+ 1, then gξ is defined in the following way: we set ηn= ¯ξ+eδ,νβ1+θn, whereθ0=eδ,ν1+ 1 andθn+1=pδ1(θn) forn < ω;
finally, letgξ(i) = supn<ωgηn(i).
6◦ Ifξ= ¯ξ+eδ,νβ,eδ,ν is a fixed point of orderδ, whereδis a limit ordinal, β = β1+ 1 and ν = ν1+ 1, gξ is defined in the following way: we set ηµ= ¯ξ+eδ,νβ1+θµ, whereθ0=eδ,ν1+ 1,θµ+1=pµ(θµ) forµ < δand, if µ < δis a limit ordinal, thenθµ= supζ<µθζ. Finally, letgξ be defined by the sequence hgηµ :µ < δiin the same way we definedgδ by the sequence hgµ:µ < δi. Sinceeδ,ν1 is a fixed point of order at leastδ, it follows that ξ≥eδ,ν > eδ,ν1 ≥δ.
7◦ Ifξ= ¯ξ+eδ,νβ, eδ,ν is a fixed point of orderδ, whereν is a limit ordinal andβ =β1+ 1, letηµ= ¯ξ+eδ,νβ1+eδ,µ forµ < ν, and letgξ be defined by hgηµ : µ < νi in the same way as gν by hgµ : µ < νi. Note that ξ≥eδ,ν> ν, because otherwisepδ(ν) =eδ,ν =ν would imply thateδ,ν is a fixed point of order at leastδ+ 1.
Let us show by induction onξ >0 that the conditions (Iη,ξ) are satisfied for all η < ξ. Let us assume (Iζ,η) holds forζ < η < ξ. We will proveYηξ∈F for each of the cases in the definition:
1◦ Obvious.
2◦ Let us first prove that Yηµξ ∈ F for µ < κ. If Y = T
ν<µYηνηµ, since (Iην,ηµ) holds for ν < µ and F is κ-complete, we have Y ∈ F. But gην(i)< gηµ(i) for alli∈Y and allν < µ. It follows from the definition of gξ that Yηµξ ⊇Xµ∩Y, henceYηµξ ∈F. Butξ= supµ<κηµ, so for every η < ξ there is ηµ > η, and by (Iη,ηµ) we have Yηηµ ∈ F and therefore, sinceYηξ⊇Yηηµ∩Yηµξ, we concludeYηξ∈F.
3◦ For everyµ < ξ we have (Iηµ,ηµ+1) and, sincegηµ+1(i)≤gξ(i) fori∈I, it follows thatYηµξ ∈F as well. Now, as in case 2◦, for everyη < ξ we can findηµ such thatη < ηµ, thusYηηµ ∈F. This impliesYηξ∈F.
4◦ We can proveYηµξ ∈F in the same way we proved Yµα ∈F, depending of which of the cases of the construction was used in defining gα by gµ
(µ < α), and proceed as in 2◦.
5◦ By Lemma 2 ξ= supn<ωηn, so the proof is analogous to case 3◦. 6◦ By Lemma 3 ξ= supµ<δηµ, so the proof is analogous to case 4◦.
7◦ Analogous to 4◦, using Lemmas 2 and 3. 2
It is easy to see that a similar construction can be done in anyAβforβ such that cf(β) =κ:
Corollary. Ifκis the least ordinal such that the ultrafilterF isκ+-incomplete and cf(β) =κ, then|Aβ| ≥κ+.
Adding to results from [5], we get another direct corollary:
Corollary. Letκbe the least ordinal such that the ultrafilterF isκ+-incom- plete, cf(β) =κ, andB ={tξ :ξ < α} be a branch of a treeT. Then there are at leastκ+ elements in TI/F greater than all tξ for ξ < β and (if β < α) less thantβ.
References
[1] Bell J. L. Slomson A. B. Models and Ultraproducts: an introduction. North- Holland, Amsterdam, 1969.
[2] Chang C. C. Keisler H. J. Model Theory. Amsterdam: North-Holland, 1973.
[3] Jech T. Set Theory, 3rd Edition. Berlin: Springer, 2002.
[4] Jovanovi´c A. Ultraproducts of Well Orders. Publications de l’Institut Mat´ematique, nouvelle s´erie 27 (1980), 99-102.
[5] ˇSobot B. Ultraproducts of trees. In: Extended abstracts of 4th Panhellenic Logic Symposium, Thessaloniki, 2003.
Received by the editors May 15, 2008
