\documentclass{article}
 
%\input{amssymb.def}
%\input{amssymb.tex}
 
 
\usepackage{graphicx}
\usepackage{amssymb}
 
 



% Set left margin - The default is 1 inch, so the following 
% command sets a 1.25-inch left margin.


% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
%\setlength{\textwidth}{6.5in}

% Set top margin - The default is 1 inch, so the following 
% command sets a 0.75-inch top margin.
\setlength{\topmargin}{-0.25in}

% Set height of the header
\setlength{\headheight}{0.3in}

% Set height of the text
\setlength{\textheight}{8.5in}

% Set vertical distance between the text and the
% bottom of footer
\setlength{\footskip}{0.3in}

% Set the beginning of a LaTeX document









\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\Bbb R}}
\def\V{{\Bbb V}}
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}} 
\def\o{{\omega}}
\def\oo{{\omega^{\omega}}}
\def\lo{{\omega^{<\omega}}}
\def\d{{\dot{\bigcup}}} 
\def\h{{\cal H}} 
\def\no{\noindent} 
\def\m{{\cal M}}
\def\n{{\cal N}}
\def\t{{\cal T}}
\def\s{{\cal S}} 
\def\B{{\Bbb B}}
\def\Box{\square}


\newsymbol\game 2061 


\begin{document}

% Redefine "plain" pagestyle
\makeatletter	   % `@' is now a normal "letter' for LaTeX

\title{\LARGE {\bf A boundedness lemma for iterations}\footnote{Partially 
supported by NSF grant DMS 96-22977 and a fellowship from 
the Sloan foundation}}         
\author{Greg Hjorth}        
\date{\today}          

\maketitle

% Set to use the "plain" pagestyle

\pagestyle{plain} 

\noindent{\large{\bf 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 $\leq$ of length $\ubf{\delta}^1_2$ 
such that for some formula $\psi$ and parameter $z$ 
$$x\leq y$$ 
if and only if 
$$L[x, y, z]\models \psi(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 \cite{hj1}. 
Certainly a familiarity with the Martin-Steel papers, \cite{ms0} and \cite{ms}, 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 
\cite{kms}. 
Discussion of earlier results in this direction can be found in 
\cite{jackson} or \cite{hj2}. 

\bigskip 

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

\bigskip


\noindent{\large {\bf 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 \cite{ms0} this 
is certainly enough to ensure $\Ubf{\Pi}^1_4$ 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. 



\bigskip 

\noindent{\bf 1.1 Definition} An expanded premouse $\m=(M, \in, \delta, 
{\cal F}, \vec \nu)$ is said to be an $M$-{\it model} if: 

(i) $(M, \in)$ models ZF+DC$_{\delta}$ and the ${\cal F}$ sequence is an element 
of $M$; 

(ii) $M=L(M_{\delta})$ where $M_{\delta}=(V_{\delta})^M$, and 
$M_{\delta}$ is countable in $V$; 

(iii) $M_{\delta}$ satisfies ZFC; $\delta$ is Woodin in both $\m$ and 
$L(\vec E|_{{\delta}})$, 
where $\vec E$ is the extender sequence derived from the Doddage ${\cal F}$; 

(iv) no $\bar{\delta}$ less than $\delta$ is Woodin in 
%$L(\vec E|_{\bar{\delta}})$ or 
$L(M_{\bar{\delta}})$; 

(v) the Doddage ${\cal F}$ witnesses that $\delta$ is Woodin in $M$:  
for all $A\subset \delta$ in $M$ there is some $\kappa<\delta$ which is witnessed 
by ${\cal F}$ to be $<\delta$ $A$-strong, in the sense that for all $\lambda$ 
strictly between $\kappa$ and $\delta$ there is some $E$ on the ${\cal F}$ sequence 
such that $(V_{\lambda})^M\in$ Ult$(M, E)$ and for $j_E:M\rightarrow$ Ult$(M, E)$ the 
ultrapower map we have $j_E(A)\cap \lambda =A\cap \lambda$; 

(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 ${\cal F}$ sequence of limit length and II gets 
to choose the cofinal branches, and further that: 

\leftskip 0.4in  


\no 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\footnote
{Though 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.}, with 
$\t_0$ an iteration tree on $\m$ with final model $\m_1$, and embedding 
$\rho_{\t_0}: \m\rightarrow \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 
$\rho_{\t_{i}}: \m_i\rightarrow \m_{i+1}$ given by the direct limit along the main branch, 
then the direct limit model 
$${\rm DirLim}(\m_i, \rho_{\t_i})$$ is wellfounded. 

\leftskip 0in 

For $z\in \m\cap \omega^{\omega}$ we then 
let $v_l(\m, z)$ be the sup of the ordinals less than $\delta$ definable in 
$\m$ from $z$, and ${\cal 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 $\delta$ that are definable from just $z$ and ${\cal F}$. Note that we could 
have 
equivalently defined $v_l(\m, z)$ to be the sup of the ordinals less than $\delta$ definable in 
$(L_{u_{l+1}}(M_{\delta}), \in, \delta, 
{\cal F}, \vec \nu)$ from $z$, ${\cal 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$.  
%Write $v_l(\m)$ in place of $v_l(\m, z)$  
%in the special case that $z$ is recursive. 

Note that (iv) above entails the sequence $(v_i(\m), z)_{i\in\o}$ being cofinal in $\delta$. 


Given $\t_0$, $\t_1$...
$\t_n$... and $\rho_{\t_0}, \rho_{\t_i}, ...\rho_{\t_n}$... as in (vi) above, and 
$k\in\omega$, we let 
$$\rho_{\t_0 \t_{1}...\t_k}: \m\rightarrow \m_{k+1}$$ 
be the composition $\rho_{\t_k}\circ\rho_{\t_{k-1}}\circ...\rho_{\t_0}$. 
In general I will use the phrase ``iterate" of ${\cal M}$ to include
not just models arising from a single iteration tree applied to ${\cal 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_{\delta})$,  suppressing  mention of the extra structure provided by 
the Doddage. 

%I will also only be interested in trees using extenders on the 
%${\cal F}$ sequence, so let us further agree that in all that follows the iteration 
%trees are formed solely by use of extenders on ${\cal F}$ -- in other words, where 
%below is written ``iteration tree" the reader should in fact read ``iteration tree 
%formed using only extenders on the ${\cal F}$ sequence;" 
Below we will be working entirely with coarse structural premice from 
\cite{ms}, 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. 




\bigskip 

Until the end of this section, fix $\m=L(M_{\delta})$, some $M$-model, and 
$z\in \m\cap \o^\o$.  

\bigskip 

\no{\bf 1.2 Definition} Let $X_n$ be the space of all finite sequences 
\[(\t_0, \m_1, \t_1, \m_2, ...\m_k, \alpha)\] 
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 
$\rho_{\t_i}: \m_i\rightarrow \m_{i+1}$ along the main branch, 
and 
$$\alpha <v_n(\m_k, z).$$  

For 
\[(\t_0, \m_1, \t_1, \m_2, ...\m_k, \alpha)\] 
and 
\[(\s_0, \n_1, \s_1, \n_2, ...\n_l, \beta)\] 
both in 
$X_n$ we set 
$$(\t_0, \m_1, \t_1, \m_2, ...\m_k, \alpha) 
R_n (\s_0, \n_1, \s_1, \n_2, ...\n_l, \beta)$$ 
if $k\leq l$, and $\s_i=\t_i$ for $i\leq k$, and 
$$\rho_{\s_{k}\s_{k+1}...\s_{l-1}}(\alpha)>\beta,$$ 
where $\rho_{\s_{k}\s_{k+1}...\s_{l-1}}: \n_k\rightarrow \n_l$ is the embedding indicated 
by the iteration trees as in 1.1. 

\bigskip 

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. 

\bigskip 

\no{\bf 1.3 Lemma} $R_n$ is wellfounded, in the sense of there being no infinite 
sequence $(x_i)_{i\in\omega}$ 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 $i$th model in $x_j$ for all large enough $j$. We then 
obtain that $(\t_i)_{i\in \omega}$ is a sequence of iteration trees, with 
$\t_{i}$ an iteration tree on $\m_i$ with final model 
$\m_{i+1}$, with embedding 
$$\rho_{\t_{i}}: \m_i\rightarrow \m_{i+1},$$  all arranged so that the 
direct limit model DirLim$(\m_i, \rho_{\t_i})$ is illfounded. 
This is in direct contradiction to our iterability assumption on the $M$-model 
$\m$. \hfill $\Box$ 

\bigskip 

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

\bigskip 

\no{\bf 1.4 Lemma} Let $\n=L(N_{\bar{\delta}})$ 
where $N_{\bar{\delta}}=(V_{\bar{\delta}})^{\n}$ and 
no $\gamma<\bar{\delta}$ is Woodin in $L((V_{\gamma})^{\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\rightarrow \n_b$$ 
$$i_c:\n\rightarrow \n_c$$ 
be the direct limit maps along these cofinal branches. 
Suppose $\alpha<\bar{\delta}$ is such that $i_b(\alpha)$ and $i_c(\alpha)$ are in the 
wellfounded parts of $\n_b$ and $\n_c$ and moreover 
$$i_b(\alpha)=i_c(\alpha)$$ 
and 
$$i_b(\bar{\delta})=i_c(\bar{\delta}).$$ 

Then $i_b$ and $i_c$ agree up to $\alpha$ -- i.e. 
$$i_b|_{\alpha}=i_c|_{\alpha}.$$ 

Proof. Let $\gamma$ 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 
$\gamma$ in $b\cup c$ is in $b$ rather than $c$. Call it $\gamma_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_\beta$ represent the $\beta$th model on $\t$ for $\beta$ less than 
the length of $\t$. Let $E_{\beta}$ be the extender used in definition of 
$\n_{\beta+1}$ from its  preceding  model -- so that $\n_{\beta+1}=$ 
Ult$(\n_{\beta^*}, E_{\beta})$, where $\beta^*$ is the predecessor 
ordinal to $\beta+1$ in the tree ordering provided by $\t$. 

Following the proof of the uniqueness theorem from \cite{ms} 
we obtain a sequence $\gamma_0<\gamma_1<\gamma_2<...$ and 
$\lambda_0<\lambda_1<\lambda_2...$ such that $\lambda_i+1$ is the 
least place on $c$ after $\gamma_i+1$ and $\gamma_{i+1}+1$ is the 
least place on $b$ after $\lambda_i+1$. Note then that the length of the 
tree is equal to both $\bigcup_{i\in\o}\gamma_i$ 
and $\bigcup_{i\in\o}\lambda_i$. 
%We then let 
%$\hat{\lambda}_i$ be the greatest ordinal on $c$ before $\lambda_i+1$ and 
%$\hat{\gamma}_{i}$ be the least ordinal on $b$ before 
%$\gamma_i+1$ -- so $\lambda_i^*=\hat{\lambda}_i$ and 
%$\gamma_i^*=\hat{\gamma}_i$. 

The normality of the iteration tree entails 
\[{\rm cp}(E_{\lambda_i})< {\rm lh}(E_{\gamma_{i}}),\]
\[{\rm cp}(E_{\gamma_{i+1}})< {\rm lh}(E_{\lambda_i}),\]
\[{\rm cp}(E_{\lambda_i})< {\rm cp}(E_{\lambda_{i+1}}),\]
\[{\rm cp}(E_{\gamma_{i}})< {\rm cp}(E_{\gamma_{i+1}}).\] 
By 2.2 \cite{ms} we have that 
$$\delta(\t)=\bigcup_{i\in\o}{\rm cp}(E_{\lambda_i}) =\bigcup_{i\in\o}{\rm cp}(E_{\gamma_i}) $$ 
is Woodin in 
$$L_{i_b({\bar{\delta}})}(\m(\t)),$$ 
where 
$$\m(\t)=\bigcup_{\alpha\in i_b({\bar{\delta}})}{\rm Lim}_{i\rightarrow \o} 
(V_{\alpha})^{\n_{\gamma_i+1}}= \bigcup_{\alpha\in i_b({\bar{\delta}})}{\rm Lim}_{i\rightarrow \o}
(V_{\alpha})^{\n_{\lambda_i+1}}.$$ 
Thus 
$$\delta(\t)=i_b({\bar{\delta}})=i_c({\bar{\delta}})$$ 
by minimality of $\bar{\delta}$ in $\n$. 
%and hence $\deltaequal to 
%$$i_b(\bar{\delta})=i_c(\bar{\delta}).$$ 


 


%\begin{figure}[ht]
 
 
%{\psfig{figure=tree.eps}}
 
 
 
%\caption{Overlap among the extenders on the two branches}
 
 
 
 
%\end{figure}
 

\leftskip 5in 

\begin{figure}

\begin{picture}(0,0)%   
{\includegraphics{tree.pstex}}%
%\epsfig{file=tree.pstex}%
\end{picture}%
\setlength{\unitlength}{0.00050000in}%
\begin{picture}(4951,4599)(1801,-4199)
\put(1876,-1261){\makebox(0,0)[lb]{lh$(E_{\gamma_i})$}}              
\put(1801,-2236){\makebox(0,0)[lb]{cp$(E_{\gamma_i})$}}                 
\put(3676,-136){\makebox(0,0)[lb]{$E_{\gamma_{i+1}}$}}                  
\put(3676,-1561){\makebox(0,0)[lb]{$E_{\gamma_i}$}}                     
\put(6526,-736){\makebox(0,0)[lb]{$E_{\lambda_i}$}}                    
\put(4501,-586){\makebox(0,0)[lb]{b}}                                   
\put(6526, 89){\makebox(0,0)[lb]{c}}                                    
\end{picture} 

\leftskip 0in 

\caption{Overlap among the extenders on the two branches}

\end{figure}

\leftskip 0.4in 

\no Thus we obtain: 

\no(1) for all $\beta\geq$ inf(cp$(E_{\gamma_0})$, cp$(E_{\lambda_0})$) 
with $\beta<\bar{\delta}$, we have that 
$$i_{\gamma, b}(\beta)\neq i_{\gamma, c}(\beta), $$ 
where 
$$i_{\gamma, b}:\n_{\gamma}\rightarrow \n_b$$ 
and 
$$i_{\gamma, c}:\n_{\gamma}\rightarrow \n_c$$ are the 
respective direct limits along these cofinal branches. 


\no(2) Conversely for all $\beta<$inf(cp$(E_{\gamma_0})$, cp$(E_{\lambda_0})$) 
we have that 
$$i_{\gamma, b}(\beta)= i_{\gamma, c}(\beta). $$ 

\leftskip 0in 

\no So by (1) we have $i_{0, \gamma}(\alpha)< $inf(cp$(E_{\gamma_0})$, cp$(E_{\lambda_0})$), where 
$$i_{0, \gamma}:\n\rightarrow \n_{\gamma}$$ 
is the canonical embedding along the iteration tree. 
Thus for all $\beta<\alpha$ we have $$i_b(\beta)=
i_{\gamma, b}(i_{0, \gamma}(\beta))=i_{\gamma, c}(i_{0, \gamma}(\beta))=
i_c(\beta)$$ by (2), just as required. \hfill $\Box$ 

\bigskip 



\no{\bf 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 \cite{ms}. \hfill $\Box$ 

%Let $b$ and $c$ be wellfounded cofinal branches and let 
%$$i_b:\n\rightarrow \n_b$$
%$$i_c:\n\rightarrow \n_c$$ 
%be the associated elementary embeddings. 
%Note then that $i_b(\bar{\delta})=i_c(\bar{\delta})$ since both are equal to 
%the Woodin cardinal of the common model. 
%Note then as in the 
%proof of 1.4 that $\n_b=\n_d$ and that the 
%Woodin cardinal of this common model is equal to the sup of the lengths of 
%the extenders used in $\t$. In particular $i_b(\bar{\delta})=
%i_c(\bar{\delta})$, where $\bar{\delta}$ is the Woodin cardinal in $\n$. 

%Now choose $D$ to be a club class of ordinals that are fixed under $i_b$ and 
%$i_c$. Since this club class is definable from countable objects, it includes 
%all the uniform indiscernibles. As remarked in the course of 1.1, the sequence 
%$(v_i(\n))_{i\in\o}$ will be cofinal in the Woodin cardinal $\bar{\delta}$. 
%Since the uniform indiscernibles 
%are fixed by the two embeddings, 
%$$i_b(v_i(\n))=i_c(v_i(\n))$$ 
%at each $i$. Since $i_b(\bar{\delta})=i_c(\bar{\delta})$ it follows that 
%$i_b|_{\bar{\delta}}=i_c|_{\bar{\delta}}$, and so $b=c$. \hfill $\Box$ 

\bigskip 

\no{\bf 1.6 Corollary} The property of being an $M$-model is $\Ubf{\Pi}^1_4$, 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 $\Ubf{\Pi}^1_4$, while the requirement that 
wellfoundedness be maintained under direct limits is $\Ubf{\Pi}^1_3$. \hfill $\Box$ 

\bigskip 

\no{\bf 1.7 Lemma} The rank of $R_n$ is less than $u_{n+2}$. 

Proof. In $V^{{\rm Coll}(\omega, u_{n+1})}$ let us define an  auxiliary relation 
$\hat{R}_n$ as follows. First we let $\hat{X}_n$ be the collection of all sequences 
\[(\t_0, L_{u_{n+1}}(M^1_{\delta_1}), ..., 
\t_{k-1}, L_{u_{n+1}}(M^k_{\delta_k}), \alpha)\] 
where: 

\leftskip 0.4in 


\no (i) setting $ L_{u_{n+1}}(M^0_{\delta_0})= L_{u_{n+1}}(M_{\delta})$,  
each $\t_{i}$ is a countable iteration tree on 
$ L_{u_{n+1}}(M^i_{\delta_i})$ with final model $ L_{u_{n+1}}(M^{i+1}_{\delta_{i+1}})$; 

\no (ii) for 
$$\rho_{\t_i}: L_{u_{n+1}}(M^i_{\delta_i})\rightarrow L_{u_{n+1}}(M^{i+1}_{\delta_{i+1}})$$ 
the embedding provided by the main branch we have that for each $j\leq n$ 
$$\rho_{\t_i}(u_j)=u_j;$$ 

\no (iii) $\alpha$ is less than the sup of the 
ordinals below $\delta_k$ definable from $z$, $\rho_{\t_0\t_1...\t_{k-1}}({\cal F})$, and 
$u_1, u_2, ..., u_n$ in $ L_{u_{n+1}}(M^k_{\delta_k})$. 

\leftskip 0in 

For 
$$x=(\t_0, L_{u_{n+1}}(M^0_{\delta_0}), ..., \t_{k-1}, L_{u_{n+1}}(M^k_{\delta_k}), \alpha)$$  
and 
$$y=(\s_0, L_{u_{n+1}}(N^0_{\gamma_0}), ..., \s_{l-1}, L_{u_{n+1}}(N^l_{\gamma_k}), \beta)$$  
two elements in $\hat{X}_n$ we set $x\hat{R}_n y$ 
if $l\leq k$, $\t_i=\s_i$ for $i< k$, 
and $\rho_{\s_{k}...\s_{l-1}}(\alpha)>\beta.$ 

Thus $\hat{X}_n$ and $\hat{R}_n$ are like $\Ubf{\Sigma}^1_1$ analogs of $X_n$ and 
$R_n$ in $V^{{\rm Coll}(\omega, u_{n+1})}$. The main issue is to show that $\hat{R}_n$ is 
again wellfounded. 

The next two claims observe that we can try to copy over an infinite sequence in $\hat{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. 

\medskip 

Claim(1). Let $(\t_0, L_{u_{n+1}}(M^1_{\delta_1}), 
..., \t_{i-1}, L_{u_{n+1}}(M^i_{\delta_i}),...)$ be 
an infinite sequence such that at each $k\in\o$ 
$$(\t_0, L_{u_{n+1}}(M^1_{\delta_1}), ..., \t_{k-1}, L_{u_{n+1}}(M^k_{\delta_k}),  0)\in \hat{X}_n.$$ 
Let $\theta_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_{\kappa_i})$, and inclusion maps 
$\tau_i: M^i_{\delta_i}\rightarrow N^i_{\kappa_i}$, 
such that: 

\leftskip 0.4in 

\no (i) each 
$\s_{i}$ is an iteration tree on $\n_i$ with final model 
$\n_{i+1}$; 

\no (ii) each $\s_i|_{\theta_i}$ equals the tree on $\n_i$ obtained by copying 
$\t_i$ over using the inclusion map $\tau_i: M^i_{\delta_i}\rightarrow N^i_{\kappa_i}$, 
and moreover $ M^i_{\delta_i}$ is a rank initial segment of 
$N^i_{\kappa_i}$; 

\no (iii) each $\s_i$ has length $\theta_i+1$. 

\leftskip 0in 

Proof of Claim: We obtain this by induction on $i$. So suppose inductively 
that we have $\n_i=L(N_{\kappa_i}^i)$ and an inclusion map 
$$\tau_i:M^i_{\delta_i}\rightarrow N_{\kappa_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 $(\rho_{\t_j})_{j<i}$ and 
$\rho_{\t_j}(u_1)=u_1$ all $j<i$ we have that $\delta_i$ is the 
least $\bar{\delta}$ which is Woodin in $L_{u_1}((V_{\bar{\delta}})^{\m_i})$. 
Thus for each $\gamma<\theta_i$ it follows from 2.2 of \cite{ms} 
that there is a unique cofinal branch through $\t_i|_{\gamma}$ which is 
wellfounded up to $u_1$. This in turn must be the branch we  chose  at stage 
$\gamma$, since the $\gamma$th model appearing in $\t_i$ is wellfounded. 
In this manner we may define by transfinite induction on $\gamma$ a 
tree $\s_i|_\gamma$ on $\n_i$ obtained by the copying the tree $\t_i|_\gamma$ 
over as in $\S$3 of \cite{ms} and conclude that for $\gamma<\theta_i$ we have a 
unique cofinal wellfounded branch through $\s_i|_\gamma$. 

Now at the very last stage of the process it will be exactly as before if 
$\t_i|_{\theta_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|_{\theta_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^{i+1}_{\delta(\t_i)}$, where 
$\delta(\t_i)$ is the supremum of the lengths of the extenders 
used on $\t_i$, such that  $M^{i+1}_{\delta(\t_i)}$ will be the 
$\delta(\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 \cite{ms} that $\delta(\t_i)$ is Woodin 
in $L_{u_1}(M^{i+1}_{\delta(\t_i)})$, and hence since $\rho_{\t_i}(u_1)=u_1$ 
we must in 
fact have that $M^{i+1}_{\delta_{i+1}}=M^{i+1}_{\delta(\t_i)}$. The mechanics of 
the copying construction imply that the piece together model 
$M^{i+1}_{\delta(\t_i)}$ is a rank initial segment of the model obtained as the 
direct limit along the cofinal wellfounded branch through $\s_i$. 
\hfill (Claim $\Box$) 

\medskip 

Claim(2). Let 
$$(\t_0, L_{u_{n+1}}(M^1_{\delta_1}), ..., \t_{i-1}, L_{u_{n+1}}(M^i_{\delta_i}),...){\rm ,}$$ 
$$\s_0, \s_1, ..., \s_i,...{\rm ,}$$  
$$\n_0, \n_1, ....\n_i,...{\rm ,}$$ all be as in the previous claim. 
Then for all but finitely many $i$ we have that 
$$\rho_{\s_i}(\delta_i)=\rho_{\t_i}(\delta_i)$$ 
and 
for all $j\leq n$ 
$$\rho_{\s_i}(u_j)=u_j;$$ 
and hence 
$$\rho_{\s_i}|_{\rho_{\t_o\t_1...\t_{i-1}}(v_n(\m z))}=
 \rho_{\t_i}|_{\rho_{\t_o\t_1...\t_{i-1}}(v_n(\m z))}.$$ 

Proof of claim. Let $\n_{\infty}$ be the direct limit model 
$${\rm DirLim}(\n_i, \rho_{\s_i}).$$ 
For each $i$ let 
$$\rho_{i\infty}: \n_i\rightarrow \n_{\infty}$$ 
be the canonical embedding into the direct limit. 

%Note that since at each $i$ we have $\delta_i$ is the least $\bar{\delta}$ Woodin in 
%$L_{u_{n+1}}(M^i_{\bar{\delta}})$ it follows from the uniqueness lemma of 
%\cite{ms} that 
%we always have $$\rho_{\s_i}(\delta_i)\geq\rho_{\t_i}(\delta_i).$$
For each $i$, $\delta_i$ is Woodin in $L_{u_{n+1}}(M^i_{\delta_i})$. By
(ii) of the previous claim $M^i_{\delta_i}=N^i_{\delta_i}$ so $\delta_i$ 
is Woodin in $L_{u_{n+1}}(N^i_{\delta_i})$. Using the elementarity of
$\rho_{{\cal S}_i}$ and since $\rho_{{\cal S}_i}(u_{n+1})\geq u_{n+1}$ we
see that $\rho_{{\cal S}_i}(\delta_i)$ is Woodin in
$L_{u_{n+1}}(N^{i+1}_{\rho_{{\cal S}_i}(\delta_i)})$. The minimality of
$\delta_{i+1}$ together with (ii) of the previous claim now implies that
$\rho_{{\cal S}_i}(\delta_i)\geq\delta_{i+1}$  -- in other words, 
$$\rho_{{\cal S}_i}(\delta_i)\geq \rho_{{\cal T}_i}(\delta_i).$$

If there is an infinite increasing sequence $(m(i))_{i\in \o}$ of natural numbers where 
$$\rho_{\s_{m(i)}}(\delta_{m(i)})>\rho_{\t_{m(i)}}(\delta_{m(i)})$$ 
then 
$$\rho_{m(i), \infty}(\delta_{m(i)})$$ 
provides an infinite descending chain in $\n_{\infty}$ contradicting that 
$\m$ is an $M$-model in both $V$ and $V^{{\rm Coll}(\omega, u_{n+1})}$. 

A similar contradiction arises from assuming that there is some $j$ for which 
$$\rho_{\s_i}(u_j)>u_j=\rho_{\t_i}(u_j)$$ 
at infinitely many $i$.             
\hfill (Claim $\Box$) 

\medskip 

Claim(3). Let $$(\t_0, L_{u_{n+1}}(M^1_{\delta_1}), ..., \t_{i-1}, 
L_{u_{n+1}}(M^i_{\delta_i}),...){\rm ,}$$ 
$$\s_0, \s_1, ..., \s_i,...{\rm ,}$$
$$\n_0, \n_1, ....\n_i,...{\rm ,}$$ 
be as in the previous claim. 
Then for all but finitely many $i$ 
we have that if $\zeta<\delta_{i+1}$ is definable from 
$u_1, u_2, ..., u_n$, $\rho_{\t_0...\t_i}({\cal F})$, and $z$ over 
$L_{u_{n+1}}(M^{i+1}_{\delta_{i+1}})$ then 
$$\rho_{\t_i}|_{\zeta}=\rho_{\s_i}|_{\zeta}.$$ 

Proof of claim. By the conclusion of claim(2) and 1.4. \hfill (Claim $\Box$) 

\medskip 

Claim(4). $\hat{R}_n$ is wellfounded. 

Proof of claim. Otherwise we may choose 
$(\t_0, L_{u_{n+1}}(M^1_{\delta_1}), ..., \t_{i}, 
L_{u_{n+1}}(M^{i+1}_{\delta_{i+1}}),...)$, 
non-decreasing $k(i)$ in $\omega$ such that 
$$k(i)\rightarrow \infty$$ 
as $i\rightarrow \infty$ and 
ordinals $\alpha_i$ less than the sup of the ordinals below 
$\delta_{k(i)+1}$ definable from 
$u_1, u_2, ..., u_n$, $\rho_{\t_0...\t_{k(i)}}({\cal F})$, 
and $z$ over $L_{u_{n+1}}(M^{k(i)+1}_{\delta_{k(i)+1}})$, 
coordinated so that for 
$$x_i=(\t_0, L_{u_{n+1}}(M^0_{\delta_0}), ..., 
\t_{k(i)}, L_{u_{n+1}}(M^{k(i)+1}_{\delta_{k(i)+1}}),\alpha_i)$$ 
we have $x_i\hat{R}_nx_{i+1}$, and hence 
$$\rho_{\t_{k(i)+1}\t_{k(i)+2}...\t_{k(i+1)}}(\alpha_i)>\alpha_{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$ 
$$\rho_{\s_{k(i)+1}\s_{k(i)+2}...\s_{k(i+1)}}(\alpha_i)
=\rho_{\t_{k(i)+1}\t_{k(i)+2}...\t_{k(i+1)}}(\alpha_i)>\alpha_{i+1}.$$ 
This gives that $${\rm DirLim}(\n_i, \rho_{\s_i})$$ is illfounded, with a 
contradiction to the  absoluteness between $V$ and  
$V^{{\rm Coll}(\omega, u_{n+1})}$ of being an $M$-model. \hfill (Claim$\Box$) 

\medskip 

Claim(5) The rank of $\hat{R}_n$ in  $V^{{\rm Coll}(\omega, u_{n+1})}$ is at least as great as 
$R_n$ in $V$. 

Proof of claim. We can  embed  $\hat{R}_n$ into $R_n$, and the prove the 
claim by transfinite induction on the ranking 
functions. \hfill (Claim $\Box$) 

\medskip 

But now note that $\hat{R}_n$ is $\Sigma^1_1(w)$ for some $w$ appearing in 
$L(\m)^{{\rm Coll}(\omega, u_{n+1})}$. Since it is wellfounded it has rank 
less $\omega_1^{{\rm ck}(w)}$, which in turn is below $u_{n+2}$. \hfill $\Box$ 


\bigskip 
\bigskip 
\bigskip 
\bigskip 
\bigskip 

\empty 

\bigskip
\bigskip

\newpage

\no{\large {\bf 2. Prewellorderings definable from the uniform indiscernibles}} 

\bigskip 

\no{\bf 2.1 Definition} Let us say that a subset $C$ of some finite 
product $(\o^\o)^m$ of Baire space is 
$\Gamma_{1, n}(z)$ if for some formula $\psi$ we have that 
for all $x\in \o^\o$ 
$$x\in C$$ 
if and only if 
$$L[x,  z]\models \psi(x,  z, u_1, u_2, ..., u_n).$$ 
Then bolderize as usual, with 
$$\Ubf{\Gamma}_{1, n}=\bigcup_{z\in \o^\o} \Gamma_{1, n}(z).$$ 

\bigskip 

Thus the $\Ubf{\Gamma}_{1, 0}$ prewellorders include all the $\Ubf{\Pi}^1_2$ 
prewellorders, as well as those prewellorderings defined by sets appearing in the 
$\sigma$-algebra generated by $\Ubf{\Pi}^1_2$. 

The next result can be proved from $\Ubf{\Pi}^1_2$ 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 {\it do} imply 
$\Ubf{\Pi}^1_2$ determinacy in light of \cite{ms0}. 

\bigskip 

\def\l{\leq_{1, n}} 

\no {\bf 2.2 Theorem} Assume there is a Woodin cardinal and a measurable above. 
Then any $\Ubf{\Gamma}_{1, n}$ prewellorder has rank less than $u_{n+2}$. 

Proof. Let $\leq_{1, n}$ be a $\Ubf{\Gamma}_{1, n}$ prewellorder.  
For $x\in \o^\o$ let Rk$_{\l}(x)$ denote the rank of 
$x$ with respect to $\l$. We will milk out a contradiction from the 
proposition that $\{$ Rk$_{\l}(x): x\in \o^\o\}$ includes $u_{n+2}$. 


Let $(\tau_m)_{m\in\o}$ 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 $\Ubf{\Sigma}^1_3$ we may find 
some $z_0\in \o^\o$ and some $\Sigma^1_3(z_0)$ set $A$ such that: 

\leftskip 0.4in 

\no (i) for all $\beta<u_{n+2}$ there exists $x_0, x_1\in \o^\o$ and $m\in\N$ such that 
$$A(x_0, x_1, m)$$ 
and 
$$\tau_m^{L[x_0]}(x_0, u_1, ..., u_{n+1})=\beta;$$ 



\no (ii) for all  $x_0, x_1\in \o^\o$ and $m\in\N$, 
$$A(x_0, x_1, m)$$ 
implies 
$$\tau_m^{L[x_0]}(x_0, u_1, ..., u_{n+1})={\rm Rk}_{\l}(x_1).$$ 

\leftskip 0in 

\no Write $A$ as $\exists y B(x_0, x_1, y, m)$ where $B\in \Pi^1_2(z_0)$. 


Choose $z_1$ and $\psi$ defining the prewellorder, so that for $x, y\in\o^\o$ we have 
$$x\l y$$ 
if and only if 
$$L[x, y, z_1]\models \psi( z_1, u_1, ..., u_n, x, y).$$ 


Let $z=\langle z_0, z_1\rangle$, 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 \cite{ms}). Let $\vec E$ be the extender sequence 
derived from the Doddage in $\m$. Let $\B(\vec E, L[\vec E, z])$ be the 
free extender algebra for adding a real 
obtained from $\vec E$ in $L[\vec E, z]$ (compare 
\cite{hj1} for further discussion of the notation). 

\medskip 

Claim(1). In $L[\vec E, z]$ there is a maximal antichain ${\cal A}\subset 
\B(\vec E, L[\vec E, z])$ such that for all $p\in {\cal A}$ we have that $(p, p)$ forces 
in $\B(\vec E, L[\vec E, z])\times \B(\vec E, L[\vec E, z])$ that 
$$L[z_1, x(\dot{G}_l), x(\dot{G}_r)]\models \psi(z_1, u_1, ..., u_n, x(\dot{G}_l), x(\dot{G}_r)) 
\wedge \psi(z_1, u_1, ..., u_n, x(\dot{G}_r), x(\dot{G}_l)).$$ 

Proof of claim:\footnote{Here as elsewhere I am following \cite{hj1}, and for $G\subset 
\B(\vec E, L[\vec E, z])$ an $L[\vec E, z]$-generic filter we have $x(G)$ as the 
real obtained in the canonical manner; any generic $H\subset \B(\vec E, L[\vec E, z]) 
\times \B(\vec E, L[\vec E, z])$ can be written in the form 
$H=G_l\times G_r$ where $G_l$ and $G_r$ are mutually generic filters on 
$\B(\vec E, L[\vec E, z])$ -- consequently $\dot{G}_l$ and $\dot{G}_r$ 
name these respective filters on the left and right copies of 
$\B(\vec E, L[\vec E, z])$.} 
Otherwise we may proceed down the usual construction to obtain a 
perfect set of reals with distinct ranks in the prewellorder:- 


In $V$ let $({\cal D}_n)_{n\in\o}$ enumerate the dense open subsets of 
$ \B(\vec E, L[\vec E, z]) 
\times \B(\vec E, L[\vec E, z])$ which lie in $L[\vec E, z]$. We choose $q\in 
\B(\vec E, L[\vec E, z])$ such that no $p\leq q$ satisfies the statement of the lemma. 

Then the usual diagonalization enables us to produce $(q_s)_{s\in 2^{<\o}}$ below 
$q$ such that: 

\leftskip 0.4in 

(i) for $s\neq t\in 2^n$ we have $(q_s, q_t)\in {\cal D}_0\cap 
{\cal D}_1\cap ...\cap {\cal D}_n$; 

(ii) $s\subset t$ implies $q_t\leq q_s$; 

(iii) for $s\in 2^{<\o}$ we have either 
$$(q_{s^\smallfrown 0}, q_{s^\smallfrown 1})\Vdash_{\B(\vec E, L[\vec E, z]) 
\times \B(\vec E, L[\vec E, z])} 
L[z_1, x(\dot{G}_l), x(\dot{G}_r)]\models \neg \psi(z_1, u_1, ..., u_n, x(\dot{G}_l), x(\dot{G}_r))$$ 
or 
$$(q_{s^\smallfrown 0}, q_{s^\smallfrown 1})\Vdash_{\B(\vec E, L[\vec E, z]) 
\times \B(\vec E, L[\vec E, z])} 
L[z_1, x(\dot{G}_l), x(\dot{G}_r)]\models 
\neg \psi(z_1, u_1, ..., u_n, x(\dot{G}_r), x(\dot{G}_l))\footnote{Where 
here $s^\smallfrown i$ is the 
sequence of length lh$(s)+1$ obtained by $(s^\smallfrown i)(n)=s(n)$ for 
$n$ smaller than the length of $s$, but $(s^\smallfrown i)$(lh$(s))=i$}.$$ 

\leftskip 0in 


Then for $w\in 2^\o$ we can let $G_w$ be the filter generated by 
$\{q_{w|n}:n\in\o\}$, and use 
$$w\mapsto 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^\o$ are assigned differing positions in the prewellorder; 
thus we obtain a $\Ubf{\Sigma}^1_3$ wellorder of $2^\o$, which contradicts $\Ubf{\Pi}^1_2$ 
determinacy. \hfill (Claim(1) $\Box$) 




Now we may assume that ${\cal A}$ is definable from $z$, $\vec E$, and $u_1, ..., u_n$. 
For $p, q\in {\cal A}$ let us write 
$$p\leq^* q$$
if there is a generic extension of $L[\vec E, z]$ in which there appear 
generic filters 
$G_p, G_q\subset \B(\vec E, L[\vec E, z])$ below $p$ and $q$ respectively with 
$$\psi(z,  u_1, u_2, ..., u_n, x(G_p), x(G_q)).$$ 
Note that this prewellorder is definable over $L[\vec E, z]$ from the indicated 
parameters so we may choose a ranking function 
$$\pi:{\cal A}\rightarrow \zeta$$ 
definable from $z$, $\vec E$, and $u_1, ..., u_n$, such that for all $p, q\in {\cal A}$ 
$$p\leq^* q$$
if and only if 
$$\pi(p)\leq \pi(q).$$ 

We want to work with the rank of this ordinal $\zeta$, showing that the bound of 
1.7 contradicts our assumption of the $\Ubf{\Gamma}_{1, n}$ 
prewellorder being long. 

\medskip 

\no{\bf Definition} Let $\m'$ be an iterate of $\m$. Let us say that an ordinal 
$\beta$ is {\it stable} for $\m'$ if for all future iterates $\m^*$ of $\m'$ and 
corresponding embeddings 
$$\tau:\m'\rightarrow \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 
$$\tau(\beta)=\beta.$$ 

\medskip 

It follows from condition (vi) of being an $M$-model that given any iterate 
$\m'$ of $\m$ and ordinal $\beta$ we can iterate $\m'$ to some $\m''$ in which 
$\beta$ 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$ 
$$\rho_{\t_i}(\beta)>\beta.$$ 
But then if we let $(i_n)_{n\in\omega}$ enumerate the $i$'s at 
which this takes place, and let 
$$\rho_{i_n, \infty}: \m_{i_n}\rightarrow {\rm \: Dir \: Lim} 
(\m_i, \rho_i)$$ be the 
direct limit, then in $\m_\infty=_{df} {\rm \: Dir \: Lim} 
(\m_i, \rho_i)$ we have that 
$(\rho_{i_n,\infty}(\beta))_{n\in\omega}$ is an infinite descending 
chain, contradicting 1.1(vi)'s assertion that this direct limit 
$\m_\infty$ should be wellfounded. 


\bigskip 

Claim(2). If $\beta<u_{n+2}$ is stable over $\m'$, and $\vec E'$ is the extender 
sequence derived from the Doddage over $\m'$, then there are $m\in \N$  and  
$q\in \B(\vec E ', L[\vec E ', z])$ forcing 
$$\tau_m^{L[x_0(\dot{G})]}(x_0(\dot{G}), u_1, ..., u_n)=\beta,$$
$$B(x_0(\dot{G}), x_1(\dot{G}), x_2(\dot{G}), m),$$ 
where we are using the notation 
$$x(\dot{G})=\langle x_0(\dot{G}),x_1(\dot{G}),x_2(\dot{G})\rangle,$$ 
to indicate that $x(\dot{G})$ is coding the reals 
$x_0(\dot{G}),x_1(\dot{G}),x_2(\dot{G})$ using the usual pairing function. 

\no Proof of Claim. We can fix 
$$x=\langle x_0, x_1, x_2\rangle$$ such that, as in the claim, 
$$\tau_m^{L[x_0]}(x_0, u_1, ..., u_n)=\beta,$$
$$B(x_0, x_1, x_2, m).$$ 
Now we may use Woodin's genericity iteration (see the introduction of 
\cite{hj1}) to find an iterate $\m^*$ of $\m'$, and 
iteration map 
$$\tau:\m'\rightarrow \m^*$$ 
such that $x$ becomes generic over the model $\tau(L[\vec E ', z])$ for 
$\tau(\B(\vec E ', L[\vec E ', z]))$; since $\beta$ is unmoved under $\tau$ by assumption 
of stability we can use the elementarity of $\tau$ to pull back the conclusion of the 
claim from $\tau(L[\vec E ', z])$ to $L[\vec E ', z]$. \hfill (Claim(2)$\Box$) 

\bigskip  

Note that in the context of the claim, if $G\subset \B(\vec E ', L[\vec E ', z])$ is 
$L[\vec E ', z]$-generic below $q$, where 
$$x(G)=\langle x_0(G), x_1(G), x_2(G)\rangle$$ indeed satisfies  
$$\tau_m^{L[x_0(G)]}(x_0, u_1, ..., u_n)=\beta,$$
$$B(x_0(G), x_1(G), x_2(G),m),$$ 
then we may find some 
$L[\vec E ', z]$-generic $G_1\subset \B(\vec E ', L[\vec E ', z])$ with 
$x(G_1)=x_1(G)$. (The introduction of \cite{hj1} discusses this 
and related features of the free extender algebra.) 
Thus we may choose some 
$$q_{\beta}^{\m'}\in\rho_{\t_0\t_1...\t_k}({\cal A})$$ (where 
$\rho_{\t_0\t_1...\t_k}:\m\rightarrow \m'$ is the iteration map) such that 

\leftskip 0.4in 

\no in some generic extension of $L[\vec E ', z]$ there are $x_0, x_1, x_2$ and 
$G_1\subset \B(\vec E ', L[\vec E ', z])$ an $L[\vec E ', z]$-generic filter 
such that 

\leftskip 1in 

\no (a) $q_{\beta}^{\m'}\in G_1$; 

\no (b) $\tau_m^{L[x_0]}(x_0, u_1, ..., u_n)=\beta$; 

\no (c) $B(x_0, x_1, x_2, m)$; 

\no (d) $x(G_1)=x_1$. 

\leftskip 0in 

\bigskip 

\no Claim(3). Let $\m'$ be some iterate of $\m$ with $\alpha$ and $\beta$ 
stable over $\m'$ with $q^{\m'}_{\alpha}$, 
$q^{\m'}_{\beta}\in\rho_{\t_0\t_1...\t_k}({\cal A})$, 
each satisfying that there exist in a generic extension of $L[\vec E ', z]$   
corresponding $m^\alpha$, $m^\beta$, 
$$x_0^\alpha, x_1^\alpha, x_2^\alpha{\rm ,}$$
$$x_0^\beta, x_1^\beta, x_2^\beta{\rm ,}$$ 
$G_1^\alpha, G_1^\beta \subset \B(\vec E ', 
L[\vec E ', z])$ both $L[\vec E ', z]$-generic 
filters
such that
 
\leftskip 1in
 
\no (a) $q_{\alpha}^{\m'}\in G_1^\alpha$;  
$q_{\beta}^{\m'}\in G_1^\beta$;
 
\no (b) $\tau_{m^\alpha}^{L[x_0^\alpha]}(x_0, u_1, ..., u_n)=\alpha$; 
$\tau_{m^\beta}^{L[x_0^\beta]}(x_0, u_1, ..., u_n)=\beta$; 
 
\no (c) $B(x_0^\alpha, x_1^\alpha, x_2^\alpha, m^\alpha)$; 
$B(x_0^\beta, x_1^\beta, x_2^\beta, m^\beta)$;  
 
\no (d) $x(G_1^\alpha)=x_1^\alpha$; $x(G_1^\beta)=x_1^\beta$. 
 
\leftskip 0in
 
\bigskip 

\noindent (That is to say  $q_{\alpha}^{\m'}$, $\tau_{m^\alpha}$, 
$x_0^\alpha$, ..., and $q_{\beta}^{\m'}$, $\tau_{m^\beta}$,
$x_0^\beta$,..., satisfy (a) through (d) from before.) 

If $$q^{\m'}_{\alpha}\leq^* q^{\m'}_{\beta}$$ then $\alpha\leq \beta$. 

\no Proof of claim. Choose $x_0^{\alpha}, x_1^{\alpha}, x_2^{\alpha}, G_1^{\alpha}, m^{\alpha}$ 
and $x_0^{\beta}, x_1^{\beta}, x_2^{\beta}, G_1^{\beta}, m^{\beta}$ as 
above for 
$q^{\m'}_{\alpha}$, $q^{\m'}_{\beta}$. 
Then by assumption of $q^{\m'}_{\alpha}\leq^* q^{\m'}_{\beta}$ we may find\footnote{We 
may actually find the filters in the generic extension of 
$L[\vec E', z]$ obtained by collapsing some ordinal less than $\omega_1^V$, since 
$L_{u_1}[\vec E', z]$ is an elementary substructure of $L[\vec E', z]$.} 
filters 
$K^\alpha$ and $K^\beta$ which are $L[\vec E', z]$-generic below 
$q^{\m'}_{\alpha}$ and $q^{\m'}_{\beta}$ with 
$$x(K^\alpha)\l x(K^\beta).$$  
Then we may choose $H^{\alpha}$ and $H^{\beta}$ 
below $q^{\m'}_{\alpha}$ and $q^{\m'}_{\beta}$ which are 
generic over $L[\vec E', z, G_1^{\alpha}, 
G_1^{\beta}, K^\alpha, K^\beta]$. 

By assumption of 
$$q^{\m'}_{\alpha}, q^{\m'}_{\beta}\in\rho_{\t_0\t_1...\t_k}({\cal A})$$ 
we obtain 
$$x(H^{\alpha}) \l x(K^\alpha)\l x(H^{\alpha})$$  
$$x(H^{\beta}) \l x(K^\beta) \l x(H^{\beta}),$$
$$x(H^{\alpha}) \l x_1^{\alpha}\l x(H^{\alpha})$$ 
and 
$$x(H^{\beta}) \l x_1^{\beta}\l x(H^{\beta}),$$ 
which by the transitivity of $\l$ finally gives us 
$$x_1^\alpha\l x_1^\beta.$$  
%By assumption of 
%$$q^{\m'}_{\alpha}\leq q^{\m'}_{\alpha}$$ 
%we get 
%$$x(H_{\alpha}) \leq x(H_{\beta}),$$
%which combined with the previous lines yields 
%$$x_1^{\alpha}\leq x_1^{\beta}.$$
Then by our choice of $A=\exists yB$ and 
$$B(x_0^{\alpha}, x_1^{\alpha}, x_2^{\alpha}, m^{\alpha}),$$ 
$$B(x_0^{\beta}, x_1^{\beta}, x_2^{\beta}, m^{\beta}),$$ 
we obtain 
$$\alpha\leq \beta.$$ 
\hfill (Claim(3)$\Box$) 

\bigskip 


Now if we associate to each $\beta<u_{n+2}$ a corresponding  
$$(\t_0, \m_0, \t_1, \m_1, ...\m_k, \gamma)\in X_n$$ 
where 
$$\gamma=(\rho_{\t_0\t_1...\t_k}(\pi))(q^{\m_k}_{\beta})$$
and $\beta<u_{n+2}$ is stable for $\m_k$ and $q^{\m_k}_{\beta}$ 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. \hfill $\Box$ 

\bigskip 

The bound of 2.2 is optimal; for each $\zeta<u_{n+2}$ there is a 
$\Ubf{\Gamma}_{1, n}$ prewellorder of length $\zeta$. 

For instance in the case $n=0$ and $\zeta<u_2$ we can define for 
$x\in 2^\N$ with $((\omega_1^V)^+)^{L[x]}>\zeta$ a corresponding 
prewellorder on $\omega\times$ WO as follows: For $n, m\in \omega$, 
$w, v$ in WO, with $||w||=\alpha$, $||v||=\beta$, we set 
$$(n, w)<_{x^\sharp, 0} (m, v)$$ 
if 
$$\tau_n^{L[x]}(\alpha, u_1, ..., u_{a(n)-2}, x)< 
\tau_m^{L[x]}(\beta, u_1, ..., u_{a(m)-2}, x),$$ 
where $a(n)$ and $a(m)$ are the respective arities of the 
Skolem functions $\tau_n$ and $\tau_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^\sharp, 0} (m, v)$ is uniformly definable over 
$L[x^\sharp, w, v]$ using $x^\sharp, w, v, n, m$ as 
parameters. Since every subset of $(\omega_1^V)^{L[x]}$ is 
definable from some $\alpha<\omega_1^V$ and finitely many 
indiscernibles, this prewellorder has rank equal to at least 
$((\omega_1^V)^+)^{L[x]}$. 


More generally if $\zeta<u_{n+3}$ we find $x\in 2^\N$ with 
$((u_{n+2})^+)^{L[x]}>\zeta$. We then define $<_{x^\sharp, n+1}$ on 
$\omega^2\times \{y^\sharp: y\in 2^\N\}$ by 
$$(m_1, m_2, y^\sharp)<_{x^\sharp, n+1} (k_1, k_2, z^\sharp)$$ if for 
$$\alpha=\tau_{m_1}^{L[y]}(u_1, u_2, ..., u_{n+1}, y),$$ 
$$\beta=\tau_{k_1}^{L[z]}(u_1, u_2, ..., u_{n+1}, z),$$ we have 
$$\tau_{m_2}^{L[x]}(\alpha, u_{n+2}, u_{n+3}, ..., x)
<\tau_{k_2}^{L[x]}(\beta, u_{n+2}, u_{n+3}, ..., x).$$ 
In this way we obtain a prewellorder on a $\Pi^1_2$ set 
which can be uniformly calculated from $x^\sharp$ 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]$. 


%The method of 2.2 can also be used to show under appropriate large cardinal 
%assumptions that there is no $u_{n+2}$-sequence of distinct 
%$\Ubf{\Gamma}^1_n$ sets in $L(\R)$. Assuming for a contradiction that 
%$(C_{\beta})_{\beta<u_{n+2}}$ is such sequence, one can open as in 2.2 and 
%the proof of the main result in \cite{hj2} by appealing to the coding lemma to 
%obtain a $\Ubf{\Sigma}^1_3$ set $A$ such that 

%\leftskip 0.4in 

%\no (i) for all $\beta<u_{n+2}$ there exists $x_0, x_1\in \o^\o$ and $m\in\N$ such that 
%$$A(x_0, x_1, m)$$ 
%and 
%$$\tau_m^{L[x_0]}(x_0, u_1, ..., u_{n+1})=\beta;$$ 



%\no (ii) for all  $x_0, x_1\in \o^\o$ and $m\in\N$, 
%$$A(x_0, x_1, m)$$ 
%implies $x_1$ codes the $C_{\beta}$ for $\beta$ such that 
%$$\tau_m^{L[x_0]}(x_0, u_1, ..., u_{n+1})=\beta.$$ 


%\leftskip 0in 



%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 \cite{neeman}. If we let $M_{2k}(x,y, z)$ always denote a  
%sufficiently iterable model in which $2k$ many ordinals below $\omega_1^V$ are Woodin, 
%and which contains $x$, $y$, and $z$, then 
%Neeman shows that for every $\game^{2k+1}(\omega\cdot n-\Ubf{\Pi}^1_1)$ prewellorder 
%$\preceq$ there is some $m\in\o$, $z\in \o^\o$, and formula $\psi$ such that 
%$$x\preceq y$$ 
%if and only 
%$$M_{2k}(x, y, z)\models \psi(x, y, z, u_1, ..., u_m).$$
%Since the such prewellorders (as $n$ ranges over $\o$) are by the periodicity theorems 
%unbounded in 
%the predecessor of $\ubf{\delta}^1_{2k+3}$, this certainly provides sufficient room 
%to begin as before. Given say a $\Ubf{\Pi}_{2k+2}^1$ prewellorder of rank 
%greater than 
%$\ubf{\delta}^1_{2k+2}$ we can use the coding lemma to pair up it up with some 
%long $\preceq $ as above. 
%This implies that if $\delta$ is Woodin in $\m$ and $\m$ includes 
%all $C_{2k+2}$ in the codes subsets of $\delta$, then there will be a maximal 
%antichain ${\cal A}$ analogous to the one appearing in claim(1) of 
%2.2, so that any $p\in {\cal 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 $\preceq $ prewellorder. 

%The second new difficulty is in trying to understand how we can ``stably" code 
%ordinals less than the predecessor of $\ubf{\delta}^1_{2k+3}$. 

%This seems surmountable under sufficient large cardinal assumptions using ideas 
%related to Woodin's proof of AD$^{L(\R)}$ in the symmetric extension obtained by 
%collapsing a limit of Woodin cardinals. We begin with a premouse 
%$\m\in V^{{\rm Coll}(\omega, \R)}$ where 

%\leftskip 0.4in 

%\no (i) $\m$ is sufficiently iterable; 

%\no (ii) $\m$ has $\o$-many Woodins, cofinal in $\omega_1^V$; 

%\no (iii) every initial segment $\m|{\alpha}$ for $\alpha<\omega_1^V$ 
%appears in $V$; 

%\no (iv) every real in $V$ is $\m$-generic over some free extender algebra 
%associated with a Woodin cardinal less than $\omega_1^V$. 

%\leftskip 0in 

%\no So in particular $L(\R)^V$ is a symmetric extension of $\m$. 
%This again gives us a method of stably coding ordinals less than $\Theta^{L(\R)}$. 
%Here the right place to apply the analog of 1.7 is to the model $L^{C_{2k+2}}((V_{\delta})^\m)$ 
%where 

%\leftskip 0.4in 

%\no (*) 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 \cite{kms} for a discussion of 
%Q-theory); 

%\no (**) and here $\delta$ is chosen to be least such that $\delta$ is Woodin in 
%$L^{C_{2k+2}}((V_{\delta})^\m)$. 

%\leftskip 0in 

%Thus we these two difficulties solved 
%it should be possible to obtain precise bounds for prewellorders of the form 
%$$x\leq y$$ 
%if and only if 
%$$C_{2k+2}(x, y, z)\models \psi(x, y, z),$$ 
%where $z\in \o^\o$, $\psi$ 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 $\langle x, y, z\rangle$. 

%However even granting all this I do not see how to give any  
%reasonable bounds for prewellorders of the form 
%$$x\leq y$$ 
%if and only 
%$$M_{2k}(x, y, z)\models \psi(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(\R)}$. It is known from \cite{steel} that HOD$^{L({\R})}$ 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 $\o$ many uniform indiscernibles in HOD$^{L({\R})}$, but seems on its 
%own to fall short of providing a complete characterization in terms of their 
%properties over this inner model. 

\bigskip 

\noindent {\bf 3 Addendum: How far will this go?} 

\bigskip 

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
$\Ubf{\Gamma}^1_n$ sets in $L(\R)$. Assuming for a contradiction that
$(C_{\beta})_{\beta<u_{n+2}}$ is such sequence, one can open as in 2.2 and
the proof of the main result in \cite{hj2} by appealing to the coding lemma to
obtain a $\Ubf{\Sigma}^1_3$ set $A$ such that
 
\leftskip 0.4in
 
\no (i) for all $\beta<u_{n+2}$ there exists $x_0, x_1\in \o^\o$ and $m\in\N$ such that
\[A(x_0, x_1, m)\]
and
\[\tau_m^{L[x_0]}(x_0, u_1, ..., u_{n+1})=\beta;\]
 
 
 
\no (ii) for all  $x_0, x_1\in \o^\o$ and $m\in\N$,
\[A(x_0, x_1, m)\]
implies $x_1$ codes the $C_{\beta}$ for $\beta$ such that
\[\tau_m^{L[x_0]}(x_0, u_1, ..., u_{n+1})=\beta.\]   
 
 
\leftskip 0in

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 \cite{neeman}. If we let $M_{2k}(x,y, z)$ always denote a
sufficiently iterable model in which $2k$ many ordinals below $\omega_1^V$ are Woodin,
and which contains $x$, $y$, and $z$, then
Neeman shows that for every $\game^{2k+1}(\omega\cdot n-\Ubf{\Pi}^1_1)$ prewellorder
$\preceq$ there is some $m\in\o$, $z\in \o^\o$, and formula $\psi$ such that
\[x\preceq y\]
if and only
\[M_{2k}(x, y, z)\models \psi(x, y, z, u_1, ..., u_m).\]
Since the such prewellorders (as $n$ ranges over $\o$) are by the periodicity theorems
unbounded in
the predecessor of $\ubf{\delta}^1_{2k+3}$, this certainly provides sufficient room
to begin as before. Given say a $\Ubf{\Pi}_{2k+2}^1$ prewellorder of rank
greater than
$\ubf{\delta}^1_{2k+2}$ we can use the coding lemma to pair up it up with some
long $\preceq $ as above.
This implies that if $\delta$ is Woodin in $\m$ and $\m$ includes
all $C_{2k+2}$ in the codes subsets of $\delta$, then there will be a maximal
antichain ${\cal A}$ analogous to the one appearing in claim(1) of
2.2, so that any $p\in {\cal 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 $\preceq $ prewellorder.
 
The second new difficulty is in trying to understand how we can ``stably" code
ordinals less than the predecessor of $\ubf{\delta}^1_{2k+3}$.
 
This seems surmountable under sufficient large cardinal assumptions using ideas
related to Woodin's proof of AD$^{L(\R)}$ in the symmetric extension obtained by
collapsing a limit of Woodin cardinals. We begin with a premouse
$\m\in V^{{\rm Coll}(\omega, \R)}$ where
 
\leftskip 0.4in
 
\no (i) $\m$ is sufficiently iterable;
 
\no (ii) $\m$ has $\o$-many Woodins, cofinal in $\omega_1^V$;
 
\no (iii) every initial segment $\m|{\alpha}$ for $\alpha<\omega_1^V$
appears in $V$;
 
\no (iv) every real in $V$ is $\m$-generic over some free extender algebra 
associated with a Woodin cardinal less than $\omega_1^V$.
 
\leftskip 0in
 
\no So in particular $L(\R)^V$ is a symmetric extension of $\m$.
This again gives us a method of stably coding ordinals less than $\Theta^{L(\R)}$. 
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|_\alpha$ some $\alpha<\omega_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 
$\beta$ under the iterations. Since $L(\R)^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 $\Theta^{L(\R)}$ using prewellorders in 
$L(\R)$. 
Here the right place to apply 
the analog of 1.7 is to the model $L^{C_{2k+2}}((V_{\delta})^\m)$
where
 
 
\leftskip 0.4in
 
\no (*) 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 \cite{kms} for a discussion of
Q-theory);
 
\no (**) and here $\delta$ is chosen to be least such that $\delta$ is Woodin in
$L^{C_{2k+2}}((V_{\delta})^\m)$.
 
\leftskip 0in  
 
Thus we these two difficulties solved
it should be possible to obtain precise bounds for prewellorders of the form
\[x\leq y\]
if and only if
\[C_{2k+2}(x, y, z)\models \psi(x, y, z),\]
where $z\in \o^\o$, $\psi$ 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 $\langle x, y, z\rangle$.
 
 
However even granting all this I do not see how to give any
reasonable bounds for prewellorders of the form
\[x\leq y\]
if and only
\[M_{2k}(x, y, z)\models \psi(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(\R)}$. It is known from \cite{steel} that HOD$^{L({\R})}$ 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 $\o$ many uniform indiscernibles in HOD$^{L({\R})}$, but seems on its
own to fall short of providing a complete characterization in terms of their
properties over  this inner model.



\bigskip 

\begin{thebibliography}{99} 

\bibitem{hj1} G. Hjorth, {\it Some applications of coarse inner model 
theory,} {\bf Journal of Symbolic Logic,} vol. 62(1997), pp. 337-365. 


\bibitem{hj2} G. Hjorth, {\it Two applications of inner model theory 
to $\Ubf{\Sigma}^1_2$ sets,} 
{\bf Bulletin of Symbolic Logic,} vol. 2(1996), 
pp. 94-107. 

\bibitem{jackson} S. Jackson, {\it Partition properties and well-ordered 
sequences,} 
{\bf Annals of Pure and Applied  Logic,} vol. 48(1990), pp. 81-101. 

\bibitem{kms} A.S. Kechris, D.A. Martin, R.M. Solovay, 
{\it Introduction to $Q$-theory,}  {\bf Cabal seminar 79-81}, pp. 199-282, 
Lecture Notes in Mathematics,  1019, Springer, Berlin, 1983

\bibitem{ms0} D.A. Martin, J.R. Steel, 
{\it A proof of projective determinacy,} 
{\bf Journal of the American Mathematical Society,} vol. 2(1989), 
pp. 71-125. 

\bibitem{ms} D.A. Martin, J.R. Steel, {\it Iteration trees,} 
{\bf Journal of the American Mathematical Society,} vol. 7(1994), pp. 1-73

\bibitem{neeman} I. Neeman, {\it Optimal proofs of determinacy,} 
{\bf Bulletin of Symbolic Logic,} vol. 1(1995), 327-339.

\bibitem{steel} J.R. Steel, {\it HOD$^{L({\R})}$ is a core model below $\Theta$,} 
{\bf Bulletin of Symbolic Logic,} vol. 1(1995), 75-84. 

\end{thebibliography}

\bigskip 

6363 MSB

Mathematics

UCLA

CA90095-1555

greg@math.ucla.edu

www.math.ucla.edu/\~{}greg 

\end{document} 




