A boundedness lemma for iterations^{∗}

Greg Hjorth

July 3, 2000

0. Introduction

The purpose of this paper is to present a kind of boundedness lemma for direct limits of coarse structural mice, and to indicate some applications to descriptive set theory. For instance, this allows us to show that under large cardinal or determinacy assumptions there is no prewellorder ≤ of length δ_{∼}_{2}^{1} such that for some formula ψ and parameter z

x ≤ y

if and only if

L[x, y, z] ⊧ ψ(x, y, z).

It is a peculiar experience to write up a result in this area. Following the work of Martin, Steel, Woodin, and other inner model theory experts, there is an enormous overhang of theorems and ideas, and it only takes one wandering pebble to restart the avalanche. For this reason I have chosen to center the exposition around the one pebble at 1.7 which I believe to be new. The applications discussed in section 2 involve routine modifications of known methods.

A detailed introduction to many of the techniques related to using the Martin-Steel inner model theory and Woodin’s free extender algebra is given in the course of [1]. Certainly a familiarity with the Martin-Steel papers, [5] and [6], is a prerequisite, as is some knowledge of the free extender algebra. Probably anyone interested in this paper will already know the necessary descriptive set theory, most of which can be found in [4]. Discussion of earlier results in this direction can be found in [3] or [2].

Acknowledgments I wish to thank Itay Neeman for a number of helpful conversations, most of which took place by e-mail.

1. The lemma

In what follows, all iteration trees are +2 and normal. We will frequently have call to consider illfounded models, and I will without comment then identify the wellfounded part of such a model with its transitive collapse.

Throughout this section assume there exists a Woodin cardinal with a measurable above; by the determinacy proofs of [5] this is certainly enough to ensure Π ∼_{4}^{1} absoluteness between V and generic extensions obtained by forcing with posets of size less than the Woodin. Some version of 1.7 makes sense and can be proved only assuming determinacy assumptions, but the statement becomes more intricate without requiring anything genuinely new for the proof.

∗Partially supported by NSF grant DMS 96-22977 and a fellowship from the Sloan foundation

1.1 Definition An expanded premouse M = (M, ∈, δ, F, ν⃗) is said to be an M-model if:

(i) (M, ∈) models ZF+DC_{δ} and the F sequence is an element of M; (ii) M = L(M_{δ}) where M_{δ} = (V_{δ})^{M}, and M_{δ} is countable in V; (iii) M_{δ} satisfies ZFC; δ is Woodin in both M and L(E⃗|_{δ}), where E⃗ is the

extender sequence derived from the Doddage F; (iv) no δ̄ less than δ is Woodin in L(Mδ̄);

(v) the Doddage F witnesses that δ is Woodin in M: for all A ⊂ δ in M there is some κ < δ which is witnessed by F to be < δ A-strong, in the sense that for all λ strictly between κ and δ there is some E on the F sequence such that (V_{λ})^{M} ∈ Ult(M, E) and for j_{E} : M → Ult(M, E) the ultrapower map we have j_{E}(A) ∩ λ = A ∩ λ;

(vi) M is fully iterable for countable length iteration trees, both in the sense that II has a winning strategy for the iteration game where I presents the iteration trees using extenders on the F sequence of limit length and II gets to choose the cofinal branches, and further that:

given a sequence of countable length iteration trees T_{0}, T_{1}... T_{n}...where the cofinal branches are chosen according to the winning strategy^{1}, with T_{0} an iteration tree on M with final model M_{1}, and embedding ρ_{T_{0}} : M → M_{1} given by the direct limit along the main branch, T_{i} an iteration tree on M_{i} with final model M_{i+1}, and embedding ρ_{T_{i}} : M_{i} → M_{i+1} given by the direct limit along the main branch, then the direct limit model

DirLim(M_{i}, ρ_{T_{i}})

is wellfounded. For z ∈ M ∩ ω^{ω} we then let v_{l}(M, z) be the sup of the ordinals less than

δ definable in M from z, and F, and the first l many uniform indiscernibles, u_{1}, u_{2}, ..., u_{l}; thus v_{0}(M, z) is the sup of the ordinals less than δ that are definable from just z and F. Note that we could have equivalently defined v_{l}(M, z) to be the sup of the ordinals less than δ definable in (L_{u_{l+1}}(M_{δ}), ∈, δ, F, ν⃗) from z, F, and the first l many uniform indiscernibles. Thus the ordinal v_{i}(M, z) will be definable from u_{1}, u_{2}, ..., u_{i}, u_{i+1} and z.

Note that (iv) above entails the sequence (v_{i}(M), z)_{i∈ω} being cofinal in δ. Given T_{0}, T_{1}... T_{n}... and ρ_{T_{0}}, ρ_{T_{i}}, ...ρ_{T_{n}}... as in (vi) above, and k ∈ ω, we let

ρ_{T_{0}T_{1}...T_{k}} : M → M_{k+1}

be the composition ρ_{T_{k}} ∘ ρ_{T_{k−1}} ∘ ...ρ_{T_{0}}. In general I will use the phrase “iterate” of M to include not just models arising from a single iteration tree applied to M, but by also the models arising from finitely many compositions of iteration trees, such as the M_{i}’s appearing in (vi).

As a helpful but not quite correct abuse of notation, let us agree to write M = L(M_{δ}), suppressing mention of the extra structure provided by the Doddage.

Below we will be working entirely with coarse structural premice from [6], which admittedly gives the exposition a kind of antiquated style. Certainly many of the ideas will work in a wider context. On the other hand I do not want to spell out what kinds of mice can be used and how the various arguments can be trivially modified, but rather choose to give the lemma 1.7 in the simplest form.

1Though by 1.5 below there can be only one choice of a fully wellfounded cofinal branch, and therefore at this level the winning strategy for II plays a trivial part.

Until the end of this section, fix M = L(M_{δ}), some M-model, and z ∈ M ∩ ω^{ω}.

1.2 Definition Let X_{n} be the space of all finite sequences

(T_{0}, M_{1}, T_{1}, M_{2}, ...M_{k}, α)

where if we define M_{0} = M, each T_{i} is a countable iteration tree on M_{i} having final model M_{i+1}, with cofinal branches chosen according to the winning strategy for II, and associated embedding ρ_{T_{i}} : M_{i} → M_{i+1} along the main branch, and

α < v_{n}(M_{k}, z).

For

(T_{0}, M_{1}, T_{1}, M_{2}, ...M_{k}, α)

and

(S_{0}, N_{1}, S_{1}, N_{2}, ...N_{l}, β)

both in X_{n} we set

(T_{0}, M_{1}, T_{1}, M_{2}, ...M_{k}, α)R_{n}(S_{0}, N_{1}, S_{1}, N_{2}, ...N_{l}, β)

if k ≤ l, and S_{i} = T_{i} for i ≤ k, and

ρ_{S_{k}S_{k+1}...S_{l−1}}(α) > β,

where ρ_{S_{k}S_{k+1}...S_{l−1}} : N_{k} → N_{l} is the embedding indicated by the iteration trees as in 1.1.

In 1.2 the notation could be made more explicit by writing X_{n}(M, z) and R_{n}(M, z) to indicate the dependence on M and z, but since these are fixed throughout this section there should be no confusion.

1.3 Lemma R_{n} is wellfounded, in the sense of there being no infinite sequence (x_{i})_{i∈ω} of elements in X_{n} with x_{i}R_{n}x_{i+1} at each i.

Proof. Otherwise let T_{i} be the iteration tree occuring in x_{j} all sufficiently large j and let M_{i} be the ith model in x_{j} for all large enough j. We then obtain that (T_{i})_{i∈ω} is a sequence of iteration trees, with T_{i} an iteration tree on M_{i} with final model M_{i+1}, with embedding

ρ_{T_{i}} : M_{i} → M_{i+1},

all arranged so that the direct limit model DirLim(M_{i}, ρ_{T_{i}}) is illfounded. This is in direct contradiction to our iterability assumption on the M-model M. □

The next lemma is well known, and in some form dates back to the original papers by Martin and Steel.

1.4 Lemma Let N = L(Nδ̄) where Nδ̄ = (Vδ̄)^{N} and no γ < δ̄ is Woodin in L((V_{γ})^{N}). Let T be an iteration tree of limit length on N, and let b and c be cofinal branches through T . Let

i_{b} : N → N_{b}

i_{c} : N → N_{c}

be the direct limit maps along these cofinal branches. Suppose α < δ̄ is such that i_{b}(α) and i_{c}(α) are in the wellfounded parts of N_{b} and N_{c} and moreover

i_{b}(α) = i_{c}(α)

and

i_{b}(δ̄) = i_{c}(δ̄).

Then i_{b} and i_{c} agree up to α – i.e.

i_{b}|_{α} = i_{c}|_{α}.

Proof. Let γ be the greatest ordinal in the intersection of b and c; this ordinal exists since both branches are closed subsets of the ordinals. Without loss we may assume that the least ordinal after γ in b ∪ c is in b rather than c. Call it γ_{0} + 1 (we are justified in the assumption it be a successor, since the limit ordinals are all at limit levels of the tree).

Let N_{β} represent the βth model on T for β less than the length of T . Let E_{β} be the extender used in definition of N_{β+1} from its preceding model – so that N_{β+1} = Ult(N_{β^{∗}}, E_{β}), where β^{∗} is the predecessor ordinal to β + 1 in the tree ordering provided by T .

Following the proof of the uniqueness theorem from [6] we obtain a sequence γ_{0} < γ_{1} < γ_{2} < ... and λ_{0} < λ_{1} < λ_{2}... such that λ_{i} + 1 is the least place on c after γ_{i} + 1 and γ_{i+1} + 1 is the least place on b after λ_{i} + 1. Note then that the length of the tree is equal to both ⋃_{i∈ω} γ_{i} and ⋃_{i∈ω} λ_{i}.

The normality of the iteration tree entails

cp(E_{λ_{i}}) < lh(E_{γ_{i}}),
cp(E_{γ_{i+1}}) < lh(E_{λ_{i}}),
cp(E_{λ_{i}}) < cp(E_{λ_{i+1}}),
cp(E_{γ_{i}}) < cp(E_{γ_{i+1}}).

By 2.2 [6] we have that

δ(T ) = ⋃_{i∈ω} cp(E_{λ_{i}}) = ⋃_{i∈ω} cp(E_{γ_{i}})

is Woodin in

L_{i_{b}(δ̄)}(M(T )),

where

M(T ) = ⋃_{α∈i_{b}(δ̄)} Lim_{i→ω}(V_{α})^{N_{γ_{i}+1}} = ⋃_{α∈i_{b}(δ̄)} Lim_{i→ω}(V_{α})^{N_{λ_{i}+1}}.

Thus

δ(T ) = i_{b}(δ̄) = i_{c}(δ̄)

by minimality of δ̄ in N.

Thus we obtain:

(1) for all β ≥ inf(cp(E_{γ_{0}}), cp(E_{λ_{0}})) with β < δ̄, we have that

i_{γ,b}(β) ≠ i_{γ,c}(β),

lh(E_{γ_{i}}) cp(E_{γ_{i}})  E_{γ_{i+1}} E_{γ_{i}}  E_{λ_{i}} b  c

Figure 1: Overlap among the extenders on the two branches

where

i_{γ,b} : N_{γ} → N_{b}

and

i_{γ,c} : N_{γ} → N_{c}

are the respective direct limits along these cofinal branches.

(2) Conversely for all β <inf(cp(E_{γ_{0}}), cp(E_{λ_{0}})) we have that

i_{γ,b}(β) = i_{γ,c}(β).

So by (1) we have i_{0,γ}(α) <inf(cp(E_{γ_{0}}), cp(E_{λ_{0}})), where

i_{0,γ} : N → N_{γ}

is the canonical embedding along the iteration tree. Thus for all β < α we have

i_{b}(β) = i_{γ,b}(i_{0,γ}(β)) = i_{γ,c}(i_{0,γ}(β)) = i_{c}(β)

by (2), just as required. □

1.5 Theorem(Woodin) Let T be a countable iteration tree on an M-model N of limit length. Then T has exactly one wellfounded cofinal branch.

Proof. See 5.5 of [6]. □

1.6 Corollary The property of being an M-model is Π ∼_{4}^{1}, and hence absolute to all small generic extensions.

Proof. For instance the statement that for all countable iteration trees there exists a full wellfounded branch is transparently Π ∼_{4}^{1}, while the requirement that wellfoundedness be maintained under direct limits is Π ∼_{3}^{1}. □

1.7 Lemma The rank of R_{n} is less than u_{n+2}.

Proof. In V^{Coll(ω,u_{n+1})} let us define an auxiliary relation R̂_{n} as follows. First we let X̂_{n} be the collection of all sequences

(T_{0}, L_{u_{n+1}}(M_{δ_{1}}^{1}), ..., T_{k−1}, L_{u_{n+1}}(M_{δ_{k}}^{k}), α)

where:

(i) setting L_{u_{n+1}}(M_{δ_{0}}^{0}) = L_{u_{n+1}}(M_{δ}), each T_{i} is a countable iteration tree on L_{u_{n+1}}(M_{δ_{i}}^{i}) with final model L_{u_{n+1}}(M_{δ_{i+1}}^{i+1}); (ii) for

ρ_{T_{i}} : L_{u_{n+1}}(M_{δ_{i}}^{i}) → L_{u_{n+1}}(M_{δ_{i+1}}^{i+1})

the embedding provided by the main branch we have that for each j ≤ n

ρ_{T_{i}}(u_{j}) = u_{j};

(iii) α is less than the sup of the ordinals below δ_{k} definable from z, ρ_{T_{0}T_{1}...T_{k−1}}(F), and u_{1}, u_{2}, ..., u_{n} in L_{u_{n+1}}(M_{δ_{k}}^{k}).

For

x = (T_{0}, L_{u_{n+1}}(M_{δ_{0}}^{0}), ..., T_{k−1}, L_{u_{n+1}}(M_{δ_{k}}^{k}), α)

and

y = (S_{0}, L_{u_{n+1}}(N_{γ_{0}}^{0}), ..., S_{l−1}, L_{u_{n+1}}(N_{γ_{k}}^{l}), β)

two elements in X̂_{n} we set xR̂_{n}y if l ≤ k, T_{i} = S_{i} for i < k, and ρ_{S_{k}...S_{l−1}}(α) > β.

Thus X̂_{n} and R̂_{n} are like Σ ∼_{1}^{1} analogs of X_{n} and R_{n} in V^{Coll(ω,u_{n+1})}. The main issue is to show that R̂_{n} is again wellfounded.

The next two claims observe that we can try to copy over an infinite sequence in R̂_{n} to an infinite sequence in R_{n}. It may not quite work, since the “copied” tree may diverge at the very last place in the choice of the cofinal branch. However this is the only possible failure, and it can only happen in a manner material to the embedding below v_{n}(M, z) finitely many times.

Claim(1). Let (T_{0}, L_{u_{n+1}}(M_{δ_{1}}^{1}), ..., T_{i−1}, L_{u_{n+1}}(M_{δ_{i}}^{i}), ...) be an infinite sequence such that at each k ∈ ω

(T_{0}, L_{u_{n+1}}(M_{δ_{1}}^{1}), ..., T_{k−1}, L_{u_{n+1}}(M_{δ_{k}}^{k}), 0) ∈ X̂_{n}.

Let θ_{i} + 1 equal the length of each T_{i}.

Then there are trees S_{0}, S_{1}, ..., S_{i}, ..., models N_{0} = M, N_{1}, ....N_{i}, ..., N_{i} = L(N_{κ_{i}}^{i}), and inclusion maps τ_{i} : M_{δ_{i}}^{i} → N_{κ_{i}}^{i}, such that:

(i) each S_{i} is an iteration tree on N_{i} with final model N_{i+1};

(ii) each S_{i}|_{θ_{i}} equals the tree on N_{i} obtained by copying T_{i} over using the inclusion map τ_{i} : M_{δ_{i}}^{i} → N_{κ_{i}}^{i}, and moreover M_{δ_{i}}^{i} is a rank initial segment of N_{κ_{i}}^{i}; (iii) each S_{i} has length θ_{i} + 1.

Proof of Claim: We obtain this by induction on i. So suppose inductively that we have N_{i} = L(N_{κ_{i}}^{i}) and an inclusion map

τ_{i} : M_{δ_{i}}^{i} → N_{κ_{i}}^{i}.

We then have T_{i} on M_{i} which we attempt to copy over to a tree S_{i} on N_{i}.

By elementarity of the maps (ρ_{T_{j}})_{j<i} and ρ_{T_{j}}(u_{1}) = u_{1} all j < i we have that δ_{i} is the least δ̄ which is Woodin in L_{u_{1}}((Vδ̄)^{M_{i}}). Thus for each γ < θ_{i} it follows from 2.2 of [6] that there is a unique cofinal branch through T_{i}|_{γ} which is wellfounded up to u_{1}. This in turn must be the branch we chose at stage γ, since the γth model appearing in T_{i} is wellfounded. In this manner we may define by transfinite induction on γ a tree S_{i}|_{γ} on N_{i} obtained by the copying the tree T_{i}|_{γ} over as in §3 of [6] and conclude that for γ < θ_{i} we have a unique cofinal wellfounded branch through S_{i}|_{γ}.

Now at the very last stage of the process it will be exactly as before if T_{i}|_{θ_{i}} has a unique u_{1}-wellfounded cofinal branch, since it will then simply copy over to the (necessarily unique) wellfounded cofinal branch through S_{i}|_{θ_{i}}. So let us suppose instead that there are several u_{1}-wellfounded cofinal branches. Then we will have a common “piece together” model M_{δ(T_{i})}^{i+1}, where δ(T_{i}) is the supremum of the lengths of the extenders used on T_{i}, such that M_{δ(T_{i})}^{i+1} will be the δ(T_{i}) rank initial segment of all the models appearing as the direct limits along the various u_{1}-wellfounded branches . We obtain by 2.2 [6] that δ(T_{i}) is Woodin in L_{u_{1}}(M_{δ(T_{i})}^{i+1}), and hence since ρ_{T_{i}}(u_{1}) = u_{1} we must in fact have that M_{δ_{i+1}}^{i+1} = M_{δ(T_{i})}^{i+1}. The mechanics of the copying construction imply that the piece together model M_{δ(T_{i})}^{i+1} is a rank initial segment of the model obtained as the direct limit along the cofinal wellfounded branch through S_{i}. (Claim □)

Claim(2). Let

(T_{0}, L_{u_{n+1}}(M_{δ_{1}}^{1}), ..., T_{i−1}, L_{u_{n+1}}(M_{δ_{i}}^{i}), ...),
S_{0}, S_{1}, ..., S_{i}, ...,
N_{0}, N_{1}, ....N_{i}, ...,

all be as in the previous claim. Then for all but finitely many i we have that

ρ_{S_{i}}(δ_{i}) = ρ_{T_{i}}(δ_{i})

and for all j ≤ n

ρ_{S_{i}}(u_{j}) = u_{j};

and hence

ρ_{S_{i}}|_{ρ_{ToT_{1}...T_{i−1}} (v_{n}(Mz))} = ρ_{T_{i}}|_{ρ_{ToT_{1}...T_{i−1}} (v_{n}(Mz))}.

Proof of claim. Let N_{∞} be the direct limit model

DirLim(N_{i}, ρ_{S_{i}}).

For each i let

ρ_{i∞} : N_{i} → N_{∞}

be the canonical embedding into the direct limit.

For each i, δ_{i} is Woodin in L_{u_{n+1}}(M_{δ_{i}}^{i}). By (ii) of the previous claim M_{δ_{i}}^{i} = N_{δ_{i}}^{i} so δ_{i} is Woodin in L_{u_{n+1}}(N_{δ_{i}}^{i}). Using the elementarity of ρ_{S_{i}} and since ρ_{S_{i}}(u_{n+1}) ≥ u_{n+1} we see that ρ_{S_{i}}(δ_{i}) is Woodin in L_{u_{n+1}}(N_{ρ_{S_{i}} (δ_{i})}^{i+1}). The minimality of δ_{i+1} together with (ii) of the previous claim now implies that ρ_{S_{i}}(δ_{i}) ≥ δ_{i+1} – in other words,

ρ_{S_{i}}(δ_{i}) ≥ ρ_{T_{i}}(δ_{i}).

If there is an infinite increasing sequence (m(i))_{i∈ω} of natural numbers where

ρ_{S_{m(i)}}(δ_{m(i)}) > ρ_{T_{m(i)}}(δ_{m(i)})

then

ρ_{m(i),∞}(δ_{m(i)})

provides an infinite descending chain in N_{∞} contradicting that M is an Mmodel in both V and V^{Coll(ω,u_{n+1})}.

A similar contradiction arises from assuming that there is some j for which

ρ_{S_{i}}(u_{j}) > u_{j} = ρ_{T_{i}}(u_{j})

at infinitely many i. (Claim □)

Claim(3). Let

(T_{0}, L_{u_{n+1}}(M_{δ_{1}}^{1}), ..., T_{i−1}, L_{u_{n+1}}(M_{δ_{i}}^{i}), ...),
S_{0}, S_{1}, ..., S_{i}, ...,
N_{0}, N_{1}, ....N_{i}, ...,

be as in the previous claim. Then for all but finitely many i we have that if ζ < δ_{i+1} is definable from u_{1}, u_{2}, ..., u_{n}, ρ_{T_{0}...T_{i}}(F), and z over L_{u_{n+1}}(M_{δ_{i+1}}^{i+1}) then

ρ_{T_{i}}|_{ζ} = ρ_{S_{i}}|_{ζ}.

Proof of claim. By the conclusion of claim(2) and 1.4. (Claim □)

Claim(4). R̂_{n} is wellfounded.

Proof of claim. Otherwise we may choose (T_{0}, L_{u_{n+1}}(M_{δ_{1}}^{1}), ..., T_{i}, L_{u_{n+1}}(M_{δ_{i+1}}^{i+1}), ...), non-decreasing k(i) in ω such that

k(i) → ∞

as i → ∞ and ordinals α_{i} less than the sup of the ordinals below δ_{k(i)+1} definable from u_{1}, u_{2}, ..., u_{n}, ρ_{T_{0}...T_{k(i)}}(F), and z over L_{u_{n+1}}(M_{δ_{k(i)+1}}^{k(i)+1}), coordinated so that for

x_{i} = (T_{0}, L_{u_{n+1}}(M_{δ_{0}}^{0}), ..., T_{k(i)}, L_{u_{n+1}}(M_{δ_{k(i)+1}}^{k(i)+1}), α_{i})

we have x_{i}R̂_{n}x_{i+1}, and hence

ρ_{T_{k(i)+1}T_{k(i)+2}...T_{k(i+1)}}(α_{i}) > α_{i+1}.

Following claims (1) to (3) we may find a corresponding S_{0}, S_{1}, ..., S_{i}, ... and N_{0}, N_{1}, ....N_{i}, ... such that at all but finitely many i

ρ_{S_{k(i)+1}S_{k(i)+2}...S_{k(i+1)}}(α_{i}) = ρ_{T_{k(i)+1}T_{k(i)+2}...T_{k(i+1)}}(α_{i}) > α_{i+1}.

This gives that

DirLim(N_{i}, ρ_{S_{i}})

is illfounded, with a contradiction to the absoluteness between V and V^{Coll(ω,u_{n+1})} of being an M-model. (Claim□)

Claim(5) The rank of R̂_{n} in V^{Coll(ω,u_{n+1})} is at least as great as R_{n} in V.

Proof of claim. We can embed R̂_{n} into R_{n}, and the prove the claim by transfinite induction on the ranking functions. (Claim □)

But now note that R̂_{n} is Σ_{1}^{1}(w) for some w appearing in L(M)^{Coll(ω,u_{n+1})}. Since it is wellfounded it has rank less ω_{1}^{ck(w)}, which in turn is below u_{n+2}. □

2. Prewellorderings definable from the uniform indiscernibles

2.1 Definition Let us say that a subset C of some finite product (ω^{ω})^{m} of Baire space is Γ_{1,n}(z) if for some formula ψ we have that for all x ∈ ω^{ω}

x ∈ C

if and only if

L[x, z] ⊧ ψ(x, z, u_{1}, u_{2}, ..., u_{n}).

Then bolderize as usual, with

Γ ∼_{1,n} = ⋃_{z∈ω^{ω}} Γ_{1,n}(z).

Thus the Γ ∼_{1,0} prewellorders include all the Π ∼_{2}^{1} prewellorders, as well as those prewellorderings defined by sets appearing in the σ-algebra generated by Π ∼_{2}^{1}.

The next result can be proved from Π ∼_{2}^{1} determinacy using Hugh Woodin’s fine analysis of the connections between determinacy and large cardinals; to avoid distracting details I will merely argue for it under large cardinal hypotheses; the assumptions of 2.2 do imply Π ∼_{2}^{1} determinacy in light of [5].

2.2 Theorem Assume there is a Woodin cardinal and a measurable above. Then any Γ ∼_{1,n} prewellorder has rank less than u_{n+2}.

Proof. Let ≤_{1,n} be a Γ ∼_{1,n} prewellorder. For x ∈ ω^{ω} let Rk_{≤_{1,n}}(x) denote the rank of x with respect to ≤_{1,n}. We will milk out a contradiction from the proposition that { Rk_{≤_{1,n}}(x) : x ∈ ω^{ω}} includes u_{n+2}.

Let (τ_{m})_{m∈ω} be some reasonable enumeration of the Skolem functions definable over a class model constructed from a real. Appealing to the coding lemma for the point class Σ ∼_{3}^{1} we may find some z_{0} ∈ ω^{ω} and some Σ_{3}^{1}(z_{0}) set A such that:

(i) for all β < u_{n+2} there exists x_{0}, x_{1} ∈ ω^{ω} and m ∈ ℕ such that

A(x_{0}, x_{1}, m)

and

τ_{m}^{L[x_{0}]}(x_{0}, u_{1}, ..., u_{n+1}) = β;

(ii) for all x_{0}, x_{1} ∈ ω^{ω} and m ∈ ℕ,

A(x_{0}, x_{1}, m)

implies

τ_{m}^{L[x_{0}]}(x_{0}, u_{1}, ..., u_{n+1}) = Rk_{≤_{1,n}}(x_{1}).

Write A as ∃yB(x_{0}, x_{1}, y, m) where B ∈ Π_{2}^{1}(z_{0}).

Choose z_{1} and ψ defining the prewellorder, so that for x, y ∈ ω^{ω} we have

x ≤_{1,n} y

if and only if

L[x, y, z_{1}] ⊧ ψ(z_{1}, u_{1}, ..., u_{n}, x, y).

Let z = ⟨z_{0}, z_{1}⟩, so that it is Turing above z_{0} and z_{1}. Let M be an M-model containing z; this does exist by the large cardinal assumptions (compare 3.12 of [6]). Let E⃗ be the extender sequence derived from the Doddage in M. Let 𝔹(E⃗, L[E⃗, z]) be the free extender algebra for adding a real obtained from E⃗ in L[E⃗, z] (compare [1] for further discussion of the notation).

Claim(1). In L[E⃗, z] there is a maximal antichain A ⊂ 𝔹(E⃗, L[E⃗, z]) such that for all p ∈ A we have that (p, p) forces in 𝔹(E⃗, L[E⃗, z]) × 𝔹(E⃗, L[E⃗, z]) that

L[z_{1}, x(Ġ_{l}), x(Ġ_{r})] ⊧ ψ(z_{1}, u_{1}, ..., u_{n}, x(Ġ_{l}), x(Ġ_{r}))∧ψ(z_{1}, u_{1}, ..., u_{n}, x(Ġ_{r}), x(Ġ_{l})).

Proof of claim:^{2} Otherwise we may proceed down the usual construction to obtain a perfect set of reals with distinct ranks in the prewellorder:-

In V let (D_{n})_{n∈ω} enumerate the dense open subsets of 𝔹(E⃗, L[E⃗, z]) × 𝔹(E⃗, L[E⃗, z]) which lie in L[E⃗, z]. We choose q ∈ 𝔹(E⃗, L[E⃗, z]) such that no p ≤ q satisfies the statement of the lemma.

Then the usual diagonalization enables us to produce (q_{s})_{s∈2^{<ω}} below q such that:

(i) for s ≠ t ∈ 2^{n} we have (q_{s}, q_{t}) ∈ D_{0} ∩ D_{1} ∩ ... ∩ D_{n}; (ii) s ⊂ t implies q_{t} ≤ q_{s}; (iii) for s ∈ 2^{<ω} we have either

(q_{s^{⌢}0}, q_{s^{⌢}1}) ⊩_{𝔹(E⃗,L[E⃗,z])×𝔹(E⃗,L[E⃗,z])} L[z_{1}, x(Ġ_{l}), x(Ġ_{r})] ⊧ ¬ψ(z_{1}, u_{1}, ..., u_{n}, x(Ġ_{l}), x(Ġ_{r}))

or

(q_{s^{⌢}0}, q_{s^{⌢}1}) ⊩_{𝔹(E⃗,L[E⃗,z])×𝔹(E⃗,L[E⃗,z])} L[z_{1}, x(Ġ_{l}), x(Ġ_{r})] ⊧ ¬ψ(z_{1}, u_{1}, ..., u_{n}, x(Ġ_{r}), x(Ġ_{l}))^{3}.

Then for w ∈ 2^{ω} we can let G_{w} be the filter generated by {q_{w|n} : n ∈ ω}, and use

w ↦ x(G_{w})

to obtain a continuous map from Cantor space to Baire space; by (iii) we have that the map is one-to-one and distinct points in 2^{ω} are assigned differing positions in the prewellorder; thus we obtain a Σ ∼_{3}^{1} wellorder of 2^{ω}, which contradicts Π ∼_{2}^{1} determinacy. (Claim(1) □)

Now we may assume that A is definable from z, E⃗, and u_{1}, ..., u_{n}. For p, q ∈ A let us write

p ≤^{∗} q

if there is a generic extension of L[E⃗, z] in which there appear generic filters G_{p}, G_{q} ⊂ 𝔹(E⃗, L[E⃗, z]) below p and q respectively with

ψ(z, u_{1}, u_{2}, ..., u_{n}, x(G_{p}), x(G_{q})).

Note that this prewellorder is definable over L[E⃗, z] from the indicated parameters so we may choose a ranking function

π : A → ζ

2Here as elsewhere I am following [1], and for G ⊂ 𝔹(E⃗, L[E⃗, z]) an L[E⃗, z]-generic filter we have x(G) as the real obtained in the canonical manner; any generic H ⊂ 𝔹(E⃗, L[E⃗, z]) × 𝔹(E⃗, L[E⃗, z]) can be written in the form H = G_{l} × G_{r} where G_{l} and G_{r} are mutually generic filters on 𝔹(E⃗, L[E⃗, z]) – consequently Ġ_{l} and Ġ_{r} name these respective filters on the left and right copies of 𝔹(E⃗, L[E⃗, z]).

3Where here s^{⌢}i is the sequence of length lh(s) + 1 obtained by (s^{⌢}i)(n) = s(n) for n smaller than the length of s, but (s^{⌢}i)(lh(s)) = i

definable from z, E⃗, and u_{1}, ..., u_{n}, such that for all p, q ∈ A

p ≤^{∗} q

if and only if

π(p) ≤ π(q).

We want to work with the rank of this ordinal ζ, showing that the bound of 1.7 contradicts our assumption of the Γ ∼_{1,n} prewellorder being long.

Definition Let M′ be an iterate of M. Let us say that an ordinal β is stable for M′ if for all future iterates M^{∗} of M′ and corresponding embeddings

τ : M′ → M^{∗}

(obtained in the usual way, by composing the maps along the main branches of the iteration trees leading from M′ to M^{∗}) we have

τ(β) = β.

It follows from condition (vi) of being an M-model that given any iterate M′ of M and ordinal β we can iterate M′ to some M′′ in which β is now stable. The point is that otherwise we obtain a sequence of iteration trees of successor length, T_{i} on M_{i}, M_{0} = M, such that at infinitely many i

ρ_{T_{i}}(β) > β.

But then if we let (i_{n})_{n∈ω} enumerate the i’s at which this takes place, and let

ρ_{i_{n},∞} : M_{i_{n}} → Dir Lim(M_{i}, ρ_{i})

be the direct limit, then in M_{∞} =_{df} Dir Lim(M_{i}, ρ_{i}) we have that (ρ_{i_{n},∞}(β))_{n∈ω} is an infinite descending chain, contradicting 1.1(vi)’s assertion that this direct limit M_{∞} should be wellfounded.

Claim(2). If β < u_{n+2} is stable over M′, and E⃗′ is the extender sequence derived from the Doddage over M′, then there are m ∈ ℕ and q ∈ 𝔹(E⃗′, L[E⃗′, z]) forcing

τ_{m}^{L[x_{0}(Ġ)]}(x_{0}(Ġ), u_{1}, ..., u_{n}) = β,
B(x_{0}(Ġ), x_{1}(Ġ), x_{2}(Ġ), m),

where we are using the notation

x(Ġ) = ⟨x_{0}(Ġ), x_{1}(Ġ), x_{2}(Ġ)⟩,

to indicate that x(Ġ) is coding the reals x_{0}(Ġ), x_{1}(Ġ), x_{2}(Ġ) using the usual pairing function. Proof of Claim. We can fix

x = ⟨x_{0}, x_{1}, x_{2}⟩

such that, as in the claim,

τ_{m}^{L[x_{0}]}(x_{0}, u_{1}, ..., u_{n}) = β,
B(x_{0}, x_{1}, x_{2}, m).

Now we may use Woodin’s genericity iteration (see the introduction of [1]) to find an iterate M^{∗} of M′, and iteration map

τ : M′ → M^{∗}

such that x becomes generic over the model τ(L[E⃗′, z]) for τ(𝔹(E⃗′, L[E⃗′, z])); since β is unmoved under τ by assumption of stability we can use the elementarity of τ to pull back the conclusion of the claim from τ(L[E⃗′, z]) to L[E⃗′, z]. (Claim(2)□)

Note that in the context of the claim, if G ⊂ 𝔹(E⃗′, L[E⃗′, z]) is L[E⃗′, z]-generic below q, where

x(G) = ⟨x_{0}(G), x_{1}(G), x_{2}(G)⟩

indeed satisfies

τ_{m}^{L[x_{0}(G)]}(x_{0}, u_{1}, ..., u_{n}) = β,
B(x_{0}(G), x_{1}(G), x_{2}(G), m),

then we may find some L[E⃗′, z]-generic G_{1} ⊂ 𝔹(E⃗′, L[E⃗′, z]) with x(G_{1}) = x_{1}(G). (The introduction of [1] discusses this and related features of the free extender algebra.) Thus we may choose some

q_{β}^{M′} ∈ ρ_{T_{0}T_{1}...T_{k}}(A)

(where ρ_{T_{0}T_{1}...T_{k}} : M → M′ is the iteration map) such that in some generic extension of L[E⃗′, z] there are x_{0}, x_{1}, x_{2} and G_{1} ⊂ 𝔹(E⃗′, L[E⃗′, z]) an L[E⃗′, z]-generic filter such that (a) q_{β}^{M′} ∈ G_{1};

(b) τ_{m}^{L[x_{0}]}(x_{0}, u_{1}, ..., u_{n}) = β;
(c) B(x_{0}, x_{1}, x_{2}, m);
(d) x(G_{1}) = x_{1}.

Claim(3). Let M′ be some iterate of M with α and β stable over M′ with q_{α}^{M′}, q_{β}^{M′} ∈ ρ_{T_{0}T_{1}...T_{k}}(A), each satisfying that there exist in a generic extension of L[E⃗′, z] corresponding m^{α}, m^{β},

x_{0}^{α}, x_{1}^{α}, x_{2}^{α},
x_{0}^{β}, x_{1}^{β}, x_{2}^{β},

G_{1}^{α}, G_{1}^{β} ⊂ 𝔹(E⃗′, L[E⃗′, z]) both L[E⃗′, z]-generic filters such that (a) q_{α}^{M′} ∈ G_{1}^{α}; q_{β}^{M′} ∈ G_{1}^{β};

(b) τ_{m^{α}}^{L[x_{0}^{α}]}(x_{0}, u_{1}, ..., u_{n}) = α; τ_{m^{β}}^{L[x_{0}^{β}]}(x_{0}, u_{1}, ..., u_{n}) = β;
(c) B(x_{0}^{α}, x_{1}^{α}, x_{2}^{α}, m^{α}); B(x_{0}^{β}, x_{1}^{β}, x_{2}^{β}, m^{β});
(d) x(G_{1}^{α}) = x_{1}^{α}; x(G_{1}^{β}) = x_{1}^{β}.

(That is to say q_{α}^{M′}, τ_{m^{α}}, x_{0}^{α}, ..., and q_{β}^{M′}, τ_{m^{β}}, x_{0}^{β},..., satisfy (a) through (d) from before.)

If

q_{α}^{M′} ≤^{∗} q_{β}^{M′}

then α ≤ β.

Proof of claim. Choose x_{0}^{α}, x_{1}^{α}, x_{2}^{α}, G_{1}^{α}, m^{α} and x_{0}^{β}, x_{1}^{β}, x_{2}^{β}, G_{1}^{β}, m^{β} as above for q_{α}^{M′}, q_{β}^{M′}. Then by assumption of q_{α}^{M′} ≤^{∗} q_{β}^{M′} we may find^{4} filters K^{α} and K^{β} which are L[E⃗′, z]-generic below q_{α}^{M′} and q_{β}^{M′} with

x(K^{α}) ≤_{1,n} x(K^{β}).

Then we may choose H^{α} and H^{β} below q_{α}^{M′} and q_{β}^{M′} which are generic over L[E⃗′, z, G_{1}^{α}, G_{1}^{β}, K^{α}, K^{β}].

By assumption of

q_{α}^{M′}, q_{β}^{M′} ∈ ρ_{T_{0}T_{1}...T_{k}}(A)

we obtain

x(H^{α}) ≤_{1,n} x(K^{α}) ≤_{1,n} x(H^{α})
x(H^{β}) ≤_{1,n} x(K^{β}) ≤_{1,n} x(H^{β}),
x(H^{α}) ≤_{1,n} x_{1}^{α} ≤_{1,n} x(H^{α})

and

x(H^{β}) ≤_{1,n} x_{1}^{β} ≤_{1,n} x(H^{β}),

which by the transitivity of ≤_{1,n} finally gives us

x_{1}^{α} ≤_{1,n} x_{1}^{β}.

Then by our choice of A = ∃yB and

B(x_{0}^{α}, x_{1}^{α}, x_{2}^{α}, m^{α}),
B(x_{0}^{β}, x_{1}^{β}, x_{2}^{β}, m^{β}),

we obtain

α ≤ β.
(Claim(3)□)

Now if we associate to each β < u_{n+2} a corresponding

(T_{0}, M_{0}, T_{1}, M_{1}, ...M_{k}, γ) ∈ X_{n}

where

γ = (ρ_{T_{0}T_{1}...T_{k}}(π))(q_{β}^{M_{k}})

and β < u_{n+2} is stable for M_{k} and q_{β}^{M_{k}} is chosen as in claim(2), then we embed u_{n+2} into R_{n}, obtaining that the rank of R_{n} is at least u_{n+2} with a contradiction to 1.7. □

The bound of 2.2 is optimal; for each ζ < u_{n+2} there is a Γ ∼_{1,n} prewellorder of length ζ.

For instance in the case n = 0 and ζ < u_{2} we can define for x ∈ 2^{ℕ} with ((ω_{1}^{V})^{+})^{L[x]} > ζ a corresponding prewellorder on ω× WO as follows: For n, m ∈ ω, w, v in WO, with ||w|| = α, ||v|| = β, we set

(n, w) <_{x^{♯},0} (m, v)

4We may actually find the filters in the generic extension of L[E⃗′, z] obtained by collapsing some ordinal less than ω_{1}^{V} , since L_{u_{1}}[E⃗′, z] is an elementary substructure of L[E⃗′, z].

if

τ_{n}^{L[x]}(α, u_{1}, ..., u_{a(n)−2}, x) < τ_{m}^{L[x]}(β, u_{1}, ..., u_{a(m)−2}, x),

where a(n) and a(m) are the respective arities of the Skolem functions τ_{n} and τ_{m}. From the point of view of calculating the inequality on display, the u_{1}, u_{2}, ... can just be treated like any other arbitrarily large L[x]-indiscernibles, and hence the relation (n, w) <_{x^{♯},0} (m, v) is uniformly definable over L[x^{♯}, w, v] using x^{♯}, w, v, n, m as parameters. Since every subset of (ω_{1}^{V})^{L[x]} is definable from some α < ω_{1}^{V} and finitely many indiscernibles, this prewellorder has rank equal to at least ((ω_{1}^{V})^{+})^{L[x]}.

More generally if ζ < u_{n+3} we find x ∈ 2^{ℕ} with ((u_{n+2})^{+})^{L[x]} > ζ. We then define <_{x^{♯},n+1} on ω^{2} × {y^{♯} : y ∈ 2^{ℕ}} by

(m_{1}, m_{2}, y^{♯}) <_{x^{♯},n+1} (k_{1}, k_{2}, z^{♯})

if for

α = τ_{m_{1}}^{L[y]}(u_{1}, u_{2}, ..., u_{n+1}, y),
β = τ_{k_{1}}^{L[z]}(u_{1}, u_{2}, ..., u_{n+1}, z),

we have

τ_{m_{2}}^{L[x]}(α, u_{n+2}, u_{n+3}, ..., x) < τ_{k_{2}}^{L[x]}(β, u_{n+2}, u_{n+3}, ..., x).

In this way we obtain a prewellorder on a Π_{2}^{1} set which can be uniformly calculated from x^{♯} and u_{1}, u_{2}, ..., u_{n+1}. Again the indiscernibles u_{n+2}, u_{n+3}, ... vanish into insignificance from the point of view of complexity, since we simply substitute for them any sufficiently large indiscernible over L[x].

3 Addendum: How far will this go?

The method of 2.2 can be used to show under appropriate large cardinal assumptions that there is no u_{n+2}-sequence of distinct Γ ∼_{n}^{1} sets in L(ℝ). Assuming for a contradiction that (C_{β})_{β<u_{n+2}} is such sequence, one can open as in 2.2 and the proof of the main result in [2] by appealing to the coding lemma to obtain a Σ ∼_{3}^{1} set A such that

(i) for all β < u_{n+2} there exists x_{0}, x_{1} ∈ ω^{ω} and m ∈ ℕ such that

A(x_{0}, x_{1}, m)

and

τ_{m}^{L[x_{0}]}(x_{0}, u_{1}, ..., u_{n+1}) = β;

(ii) for all x_{0}, x_{1} ∈ ω^{ω} and m ∈ ℕ,

A(x_{0}, x_{1}, m)

implies x_{1} codes the C_{β} for β such that

τ_{m}^{L[x_{0}]}(x_{0}, u_{1}, ..., u_{n+1}) = β.

More difficulties arise in generalizing to the higher point classes.

The first problem is an analog of coding large ordinals using the indiscernibles; here one requires of course that the statement “x and y code the same ordinal” be absolute to the generic extensions by the free extender algebra over the appropriate level of mouse.

This problem seems to be met by [7]. If we let M_{2k}(x, y, z) always denote a sufficiently iterable model in which 2k many ordinals below ω_{1}^{V} are Woodin, and which contains x, y, and z, then Neeman shows that for every ⅁^{2k+1}(ω · n − Π ∼_{1}^{1}) prewellorder ⪯ there is some m ∈ ω, z ∈ ω^{ω}, and formula ψ such that

x ⪯ y

if and only

M_{2k}(x, y, z) ⊧ ψ(x, y, z, u_{1}, ..., u_{m}).

Since the such prewellorders (as n ranges over ω) are by the periodicity theorems unbounded in the predecessor of δ_{∼}_{2k+3}^{1}, this certainly provides sufficient room to begin as before. Given say a Π ∼_{2k+2}^{1} prewellorder of rank greater than δ_{∼}_{2k+2}^{1} we can use the coding lemma to pair up it up with some long ⪯ as above. This implies that if δ is Woodin in M and M includes all C_{2k+2} in the codes subsets of δ, then there will be a maximal antichain A analogous to the one appearing in claim(1) of 2.2, so that any p ∈ A will be such that (p, p) in the product of the free extender algebra will decide the position of the generic real in the ⪯ prewellorder.

The second new difficulty is in trying to understand how we can “stably” code ordinals less than the predecessor of δ_{∼}_{2k+3}^{1}.

This seems surmountable under sufficient large cardinal assumptions using ideas related to Woodin’s proof of AD^{L(ℝ)} in the symmetric extension obtained by collapsing a limit of Woodin cardinals. We begin with a premouse M ∈ V^{Coll(ω,ℝ)} where

(i) M is sufficiently iterable;

(ii) M has ω-many Woodins, cofinal in ω_{1}^{V};

(iii) every initial segment M|α for α < ω_{1}^{V} appears in V;

(iv) every real in V is M-generic over some free extender algebra associated with a Woodin cardinal less than ω_{1}^{V}.

So in particular L(ℝ)^{V} is a symmetric extension of M. This again gives us a method of stably coding ordinals less than Θ^{L(ℝ)}. The point is that as we iterate the model, restricting our attention only to iterates of M in which the iteration trees live in V, and take place only on some bounded piece M|_{α} some α < ω_{1}^{V}, and as we gradually add finitely many generic reals to these iterates of M, we must at some point reach a stability for any ordinal β under the iterations. Since L(ℝ)^{V} (in effect) continues to be a symmetric generic extension of the various iterations, we obtain a kind of stable coding for ordinals less than Θ^{L(ℝ)} using prewellorders in L(ℝ). Here the right place to apply the analog of 1.7 is to the model L^{C_{2k+2}}((V_{δ})^{M}) where

(*) in general L^{C_{2k+2}}(X) is the smallest class model containing X and closed under the C_{2k+2} operation through all its generic extension (see [4] for a discussion of Q-theory); (**) and here δ is chosen to be least such that δ is Woodin in L^{C_{2k+2}}((V_{δ})^{M}).

Thus we these two difficulties solved it should be possible to obtain precise bounds for prewellorders of the form

x ≤ y

if and only if

C_{2k+2}(x, y, z) ⊧ ψ(x, y, z),

where z ∈ ω^{ω}, ψ a formula in second order arithmetic, and C_{2k+2}(x, y, z) is being used to denote the reals of C_{2k+2}-degree less than or equal to ⟨x, y, z⟩.

However even granting all this I do not see how to give any reasonable bounds for prewellorders of the form

x ≤ y

if and only

M_{2k}(x, y, z) ⊧ ψ(x, y, z, u_{1}, ..., u_{m}),

where k > 0. The further evolution of this problem would seem to require Jackson’s deep analysis of the projective ordinals.

A rather different direction in which this might lead is towards a finer analysis of HOD^{L(ℝ)}. It is known from [8] that HOD^{L(ℝ)} is a core model, obtained by a direct limit of countable fine structural mice. Lemma 1.7 can obviously be used to provide some information regarding the large cardinal properties of the first ω many uniform indiscernibles in HOD^{L(ℝ)}, but seems on its own to fall short of providing a complete characterization in terms of their properties over this inner model.

References

[1] G. Hjorth, Some applications of coarse inner model theory, Journal of Symbolic Logic, vol. 62(1997), pp. 337-365.

[2] G. Hjorth, Two applications of inner model theory to Σ ∼_{2}^{1} sets, Bulletin of Symbolic Logic, vol. 2(1996), pp. 94-107.

[3] S. Jackson, Partition properties and well-ordered sequences, Annals of Pure and Applied Logic, vol. 48(1990), pp. 81-101.

[4] A.S. Kechris, D.A. Martin, R.M. Solovay, Introduction to Q-theory, Cabal seminar 79-81, pp. 199-282, Lecture Notes in Mathematics, 1019, Springer, Berlin, 1983

[5] D.A. Martin, J.R. Steel, A proof of projective determinacy, Journal of the American Mathematical Society, vol. 2(1989), pp. 71-125.

[6] D.A. Martin, J.R. Steel, Iteration trees, Journal of the American Mathematical Society, vol. 7(1994), pp. 1-73

[7] I. Neeman, Optimal proofs of determinacy, Bulletin of Symbolic Logic, vol. 1(1995), 327-339.

[8] J.R. Steel, HOD^{L(ℝ)} is a core model below Θ, Bulletin of Symbolic Logic, vol. 1(1995), 75-84.

6363 MSB

Mathematics

UCLA

CA90095-1555

greg@math.ucla.edu

www.math.ucla.edu/˜ greg