% LaTeX Article Template - using defaults
\documentclass{article}
 
\usepackage{amssymb}
\usepackage{latexsym}
\pagestyle{myheadings}

 
%\usepackage[notref]{showkeys}
\usepackage{graphicx} 
\usepackage{amssymb}
\usepackage{latexsym}  
\markright{G. Hjorth} 
 
% Set left margin - The default is 1 inch, so the following
% command sets a 1.25-inch left margin.
\setlength{\oddsidemargin}{-0.15in}
 
% 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.1in}
 
% Set height of the header
\setlength{\headheight}{0.3in}
 
% Set height of the text
\setlength{\textheight}{8.1in}

 
% Set vertical distance between the text and the
% bottom of footer
\setlength{\footskip}{0.8in}
 
 
 
% Set the beginning of a LaTeX document
\begin{document}
 

 
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{fact}[theorem]{Fact} 

  \newenvironment{proof}[1][Proof]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\hfill$\Box$\medskip}
     \newenvironment{definition}[1][Definition]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\medskip}
     \newenvironment{example}[1][Example]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\medskip}
     \newenvironment{remark}[1][Remark]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\medskip}
     \newenvironment{notation}[1][Notation]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\medskip}
     \newenvironment{question}[1][Question]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\medskip}
 
\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\V{{\mathbb V}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\K{{\mathbb K}}
\def\B{{\mathbb B}}
\def\Q{{\mathbb Q}}
\def\o{{\omega}}
\def\oo{{\omega^{\omega}}}
\def\lo{{\omega^{<\omega}}}
\def\d{{\dot{\bigcup}}}
\def\h{{\cal H}}
\def\no{\noindent}
\def\a{{\mathcal A}}
\def\b{{\mathcal B}}
\def\l{{\mathcal L}}
\def\n{{\mathcal N}}
\def\m{{\mathcal M}}
\def\p{\varphi}
\def\lone{\l_{\omega_1, \omega}}
\def\mod{{\rm Mod}(\l)} 
\def\mods{{\rm Mod}(\sigma)}
\def\modss{{\rm Mod}_{\Omega}(\sigma)}
\def\Lck{L_{\omega_1^{\rm ck}}}
\def\hl{\hat{\mathcal L}}
\def\hlone{\hl_{\omega_1, \omega}}

\large 
 
\title{\huge A dichotomy theorem for isomorphism}         % Enter your title between curly braces
\author{Greg Hjorth}        % Enter your name between curly braces
\date{\today}          % Enter your date or \today between curly braces
\maketitle
 
\tableofcontents   
 
 
\section{Introduction}
\label{introduction} 


This paper contains a dichotomy theorem for the isomorphism 
relation on a class of countable structures. The statement of the 
theorem is cleanest when the isomorphism relation is Borel and 
the class of models is defined by a sentence in 
$\lone$, and  therefore this is where we begin. 

We display a canonical obstruction which must be present whenever 
we are unable to reduce the isomorphism relation to a countable 
Borel equivalence relation. 

\begin{theorem} Let 
{\rm Mod}$(\l)$ the space of countable $\l$ structures in either the 
(Polish) topology generated 
by quantifier free formulas or the topology generated by first 
order logic.  
Let $\sigma\in\lone$ be such that $\cong\!|_{\mods}$ is Borel and 
let $\mods$ be the space of countable models of $\sigma$. 
 
Then exactly one of the following occurs:- 

\leftskip 0.5in 

\no (I) there is a Borel function $\theta: \mods\rightarrow X$, 
some Polish space $X$, and there is a Borel equivalence relation 
$E$ on $X$ all of whose equivalence classes are countable, such that 
for all $\m_0, \m_1\in\mods$ 
\[\m_0\cong\m_1\Leftrightarrow \theta(\m_0) E\theta (\m_1);\] 

\no (II) there is a Borel function 
\[\theta: (2^\o)^\o\rightarrow \mods\] 
such that for all $(x_n)_{n\in\o}, (y_n)_{n\in\o}$ with each 
$x_n, y_n: \o\rightarrow \{0, 1\},$ we have 
\[\theta((x_n)_{n\in\o})\cong \theta ((y_n)_{n\in\o})\] 
if and only if for all $n\in\o$ there is $K_n\in\o$ 
such that for all $i> K_n$ 
\[x_n(i)=y_n(i).\] 

\leftskip 0in 

\end{theorem} 

By \cite{hjorthkechris2} and a result by Kechris at 5.1 of 
\cite{hjorthclassical} we obtain that (I) is equivalent to each of 
the following: 


\leftskip 0.5in

\no (I') there is a Borel function 
\[f:\mods\rightarrow {\mathbb R}\] 
such that 

\leftskip 1in 

\no (a) $f$ has countable image on each isomorphism type: 
$|\{f(\n): \n\cong\n_0\}|\leq \aleph_0$ for each $\n_0\in\mods$; 

\no (b) $f$ assigns disjoint countable sets: for if 
$|\{f(\n): \n\cong\n_0\}|
\cap 
|\{f(\n): \n\cong\n_1\}| \neq \emptyset$ then $\n_0\cong \n_1$. 

\smallskip 

\leftskip 0.5in 

\no (I'') there is a countable fragment $F\subset\lone$ such that 
for every $\m\models\sigma$ we have some $\vec a\in\m$ with the 
model 
\[\langle \m; \vec a\rangle\] 
atomic over the fragment $F$; 

\no (I''') there is a countable fragment $F\subset\lone$ such that
for every $\m\models\sigma$ we have some $\vec a\in\m$ with the
$F$-theory of the model 
\[\langle \m; \vec a\rangle\] 
$\aleph_0$-categorical. 

\leftskip 0in 

\bigskip 

Very loosely one might think of (I), (I'), 
(I''), and (I''') as expressing the idea that the 
models of $\sigma$ all have ``finite rank." A specific 
case of this is when the models are all finitely generated, 
in the sense that every $\m\in\mods$ has 
\[\m=\{t(\vec a): t {\rm \: is \: a \: term}\},\] 
for some $\vec a\in\m$. 


On the other side, 
(II) may be thought of expressing that the models 
of $\sigma$ {\it interpret} -- in some very generous 
notion of interpretation -- a canonical theory which has 
infinite rank. For the purposes of illustrating that let 
us take an example. 

Consider the language $\hat{\l}$ with a single binary 
relation $<$ and countably many unary 
predicates $(U_n)_{n\in\o}$. Let $\varphi\in \hat{\l}_{\omega_1, \omega}$ 
be the sentence all of whose models are linearly ordered by 
$<$ with order type equal to $\Z\cdot \omega$ (in the reverse lexicographic 
ordering); that is to say, if we start with $\Z\cdot \omega$ the linear 
ordering given by $\omega$-many $\Z$-blocks, then 
Mod$(\varphi)$ consists in the 
the expansions of this structure by 
countably many unary predicates. 

With all this in place, we can rephrase (II) as 

\leftskip 0.5in 

\no (II') there is a Borel function 
\[\theta: {\rm Mod}(\varphi)\rightarrow \mods\] 
such that for all $\n_0, \n_1\in {\rm Mod}(\varphi)$ we have 
\[\n_0\cong\n_1\Leftrightarrow \theta(\n_0)\cong
\theta(\n_1).\] 

\leftskip 0in 

\bigskip 

The method of proof allows certain modifications. We can work 
on $\Ubf{\Sigma}^1_1$ subsets of the space of all countable models, 
instead of just those defined by a countably infinitary formula. 
Thus in particular if $F$ is a Borel equivalence relation, on a Polish space 
$Y$,  and if $F$ allows a Borel reduction 
to the isomorphism relation on some 
space of countable structures, then we have, as in the theorem 
above, exactly one of the following: 

\leftskip 0.5in

\no (I$^*$) there is a Borel function $\theta: Y\rightarrow X$,
some Polish space $X$, and there is a Borel equivalence relation
$E$ on $X$ all of whose equivalence classes are countable, such that
for all $y_0, y_1\in Y$
\[y_0 F y_1\Leftrightarrow \theta(y_0) E\theta (y_1);\]

\no (II$^*$) there is a Borel function
\[\theta: (2^\o)^\o\rightarrow Y\]
such that for all $(x_n)_{n\in\o}, (y_n)_{n\in\o}$ with each
$x_n, y_n: \o\rightarrow \{0, 1\},$ we have
\[\theta((x_n)_{n\in\o}) F \theta((y_n)_{n\in\o})\]
if and only if for all $n\in\o$ there is $K_n\in\o$
such that for all $i> K_n$
\[x_n(i)=y_n(i).\]

\leftskip 0in

\bigskip 

The situation for general, not necessarily Borel, isomorphism 
relations is more subtle. The first point to make is that the 
theorem {\it does} fail in this wider context. A counter example 
is given by the abelian $p$-groups, $p$ a prime, as discussed in 
\cite{ulm}. Here one has an explicit bijection between 
the isomorphism types and $2^{<\aleph_1}$; as may seem very plausible, 
and has been discussed in \cite{frst}, 
there is no definable method of injecting $2^{<\aleph_1}$ into countable 
sets of reals, as would happen at (I) above; alternatively the 
equivalence relation described at (II) is certainly not reducible to 
 $2^{<\aleph_1}$, as \cite{ulm} even shows the 
equivalence relation $E_0$, of eventual agreement just on a single 
copy of $2^\o$, to refuse subsets of the ordinals as complete invariants 
in any kind of definable, let alone Borel or $\Ubf{\Delta}^1_2$, manner. 

With this problem noted, and bearing in mind the extrapolations past Borel 
appearing in earlier papers such as 
\cite{ulm}, one can find the right statement for $\Sigma^1_1$ 
isomorphism relations. There are various ways of stating this. 
For instance bearing 
in mind (I') above: 

\begin{theorem} 

Let $\sigma\in\lone$ and
let $\mods$ be the space of countable models of $\sigma$.

Then exactly one of the following occurs:-

\leftskip 0.5in

\no ($\hat{I}$) there is a $\Ubf{\Delta}^1_2$ in the codes 
function $f: \mods\rightarrow 2^{<\aleph_1} $,     

\leftskip 1in

\no (a) $f$ has countable image on each isomorphism type:
$|\{f(\n): \n\cong\n_0\}|\leq \aleph_0$ for each $\n_0\in\mods$;

\no (b) $f$ assigns disjoint countable sets: for if
$|\{f(\n): \n\cong\n_0\}|
\cap
|\{f(\n): \n\cong\n_1\}| \neq \emptyset$ then $\n_0\cong \n_1$.

\smallskip

\leftskip 0.5in


\no (II) there is a Borel function
\[\theta: (2^\o)^\o\rightarrow \mods\]
such that for all $(x_n)_{n\in\o}, (y_n)_{n\in\o}$ with each
$x_n, y_n: \o\rightarrow \{0, 1\},$ we have
\[\theta((x_n)_{n\in\o})\cong \theta((y_n)_{n\in\o})\]
if and only if for all $n\in\o$ there is $K_n\in\o$
such that for all $i> K_n$
\[x_n(i)=y_n(i).\]

\leftskip 0in

\end{theorem}


\bigskip 

The proof of the main theorem is fairly 
long and there are several parts. 
In section \ref{definition} we present the main definition which 
is used to define a split into cases. In some rough sense 
the idea here is to 
consider the $\Sigma^1_1$ sets which a given  
\[\langle \m; \vec a\rangle \] 
falls inside, and ask when we can produce a new type, over 
a given fragment $F$, realized by some 
\[\langle \n;\vec b\rangle ,\] 
where $\m$ allows a ``highly elementary" embedding into $\n$. 
The branching into three possibilities, at 
\ref{case(I)}, \ref{case(IIa)}, and 
\ref{case(IIb)}, 
and the consequent rank function which appears 
when there is no such $\n$, constitutes the main idea. 

In \ref{consequences} we step through various standard reflection 
arguments, many of which are similar to parallel points in 
\cite{hakelo}, and show that the various sets we need to 
be $\Sigma^1_1$ are indeed $\Sigma^1_1$. 

Section \ref{aside} turns off into an aside. 
It uses ideas closely related to 
\ref{definition} to obtain a characterization of when an infinitary 
sentence allows a countable model; this characterization appears natural, 
to the author at least, given the arguments of section \ref{split} and 
following. It can be viewed as the generalization of \cite{gao}, which 
completely described when a countable model allows an uncountable model of 
its Scott's sentence and has as a consequence a result by Keisler and Shelah 
to the effect that a set of infinitary sentences allowing an uncountable 
model is $\Sigma^1_1$ in the codes. 

\ref{split} returns to the main road. Here there is a fork into 
three possibilities. 
The first, case(I), 
corresponds to when we are appropriately able to add to the $F$-types 
for some suitable set of $\m\models\sigma$. The second and third, labeled 
(IIa) and (IIb), are when we are unable to add to the $F$-types for any 
countable $\Delta^1_1$ fragment $F$, and therefore have a kind of rank 
function definable over the models of $\sigma$, which ranks the tree of 
partial attempts corresponding to case(I); this rank function can be finite 
everywhere, giving us case(IIa), or somewhere it may be infinite, giving 
(IIb). 

In \ref{case(I)} we show that case(I) entails that we are in (II) of 
the theorem: 
\[(E_0)^\omega\leq_B\cong\!|_{\mods}.\] 
The rough idea is to try to build a generic sequence of models, each 
one elementary in the next, each one realizing many more types than the 
last, and squeeze in between successive models a copy of $E_0$, the 
equivalence relation of eventual agreement on infinite binary sequences. 

Section \ref{case(IIb)} handles case(IIb), when the rank function 
exists and for some models 
it is always infinite. Here we argue that we can assume that the rank 
function has as its supremum some countable recursive limit ordinal. 
Then we can try to stratify our generic model into countably many levels, 
classifying a tuple $\vec b$ from $\m$ on the basis of its rank. 
Once this is set in place we mimic the argument from 
\ref{case(I)}, interpreting a different copy of $E_0$ on different 
levels. 

Finally we are left with \ref{case(IIa)} and the discussion of 
case(IIa), which is in  some ways  the easiest case, or at least the 
most familiar, being almost identical to a parallel argument from 
\cite{hjorthkechris}. This is the one place we use that 
$\cong\!|_{\rm \mods}$ is Borel. By assuming that the rank function 
is finite over all fragments, and iterating this observation 
through as many ordinal steps as the Borel complexity of the 
isomorphism relation, we finally obtain (I'). 



There are several sections of background material. 
Certainly \ref{set}, \ref{model}, and \ref{borel} with their 
discussion of set theoretical and model theoretic prerequisites, 
as well as the general theory of Borel equivalence relations, 
are standard for this kind of paper. 

On the other hand 
\ref{descriptive} is a little bit more than the usual thumbnail 
sketch of the well known. 
Here there are several short proofs on the boundary of effective 
descriptive set theory and admissible set theory, all of which are 
commonplace but strangely difficult to find precisely in the 
literature. In the arguments of 
\ref{consequences}, \ref{case(I)}, \ref{case(IIb)}, 
\ref{case(IIa)}, and even \ref{definition}, it will be helpful to 
continually pass back and forward from the descriptive set theory 
of $\Sigma^1_1$ sets to the ``inner model theory" of admissible 
sets, and while it would be theoretically possible to do everything 
just using effective descriptive set theory, the arguments would become 
unintuitive and hard to follow. 

Given the length of the proof, the reader may already be planning how 
it might be possible to avoid reading most of it. 
This is a reasonable desire, so I should state forthrightly what is 
most peripheral. 

Two sections which can be skipped are 
\ref{aside} and \ref{something}. The first, as remarked 
above, plays out the ideas of the proof for a result whose 
actual statement is unrelated; it is never referenced again. 
 
The situation with the \ref{something} is more ambiguous. 
It came about after considering arguments invoking Gandy-Harrington 
forcing. Often when becoming involved in calculations that use 
the ``geometry" of $\Sigma^1_1$ sets it becomes easier if we fix 
a kind of ``generic" member of the $\Sigma^1_1$, and  perform  our 
various calculations with repeated appeals to its genericity. 
The main point of \ref{something} is the somewhat philosophical one, 
that the entire  usefulness  of a generic member of a 
$\Sigma^1_1$ set is that it is low, in the sense of having its 
Church-Kleene ordinal equal to $\omega_1^{\rm ck}$; for the rest of 
the paper we therefore refer only to reals that are low, never to 
reals which arise from a Gandy-Harrington generic filter. 
While it is true that there are isolated references back to 
\ref{something}, they are 
only made to 
\ref{low}, \ref{A6.b}, and \ref{A7}, all of which are well known. 

\newpage 




\section{Set theoretical notation} 
\label{set} 

\begin{notation} For us the set of  natural numbers is  
\[\omega=\{0, 1, 2, 3, ...\}.\] 
We identify each natural number with its set of 
predecessors: 
\[n=\{0, 1, 2,..., n-1\};\] 
zero has no predecessors, and thus equals the 
empty set: 
\[0=\emptyset.\]   
With this in hand $2=\{0, 1\}$ and 
for any natural number $n$ 
\[2^n=\{f| \: f:\{0, 1, 2,..., n-1\}\rightarrow \{0, 1\}\};\] 
$2^\o$ is the set of all functions from $\o$ to $\{0,1\}$, and 
in general given sets $X$ and $Y$ we let 
\[X^Y=\{f: Y\rightarrow X\}.\] 


Given a set $X$ and $n\in\omega$, we 
use $X^n$ for the set of all sequences of length 
$n$ from $X$: 
\[X^n=\{f| \: f:\{0, 1, 2,..., n-1\}\rightarrow X\};\] 
this may be naturally identified with the $n$-fold 
product of $X$: 
\[X\times X\times \cdots [n  {\rm \: times}]\times X.\] 
Then $X^{<\omega}$ is the set of all finite sequences 
from $X$: 
\[X^{<\omega}=\bigcup_{n\in\omega}X^n.\] 
\end{notation} 

\begin{definition} Given sets $X_1,X_2,...X_n$, {\it tree} on 
$X_1\times X_2\times... X_k$ 
is a subset of 
\[\bigcup_{n\in\o}X_1^n\times X_2^n\times ...X^n_k\] 
closed under subsequences in the natural way -- so that 
given $(u_1,..., u_k)\in 
X_1^n\times X_2^n\times ...X^n_k$ in the tree we require that for any 
$l<n$ we have 
that $(u_1|_l, u_2|_l,...,u_k|_l)$ is again in the 
tree. 

For $T$ a tree on $X_1,X_2,...X_n$, an {\it infinite branch 
through} $T$ is some $(f_1,f_2,..., f_k)$, 
each 
\[f_i: \o\rightarrow X_i\] 
with $f_i|_l\in T$ all $l\in\o$. We let $[T]$ denote the 
collection of all infinite branches. 
\end{definition} 

\begin{notation} 
Given two finite sequences $s$ and $t$, we use 
\[s^\smallfrown t\] to indicate the concatenation, 
obtained by following $s$ by $t$. 

Thus if $s\in X^k$ and $t\in X^n$ then we have 
$s^\smallfrown t\in X^{k+n}$ 
defined by 
\[(s^\smallfrown t)(i)=s(i)\] for $i<k$ and 
\[(s^\smallfrown t)(k+i)=t(i)\] for $i<n$. 

In the case that $t=\langle a\rangle$ 
has length 1 we may write 
\[s^\smallfrown a\] 
instead of $s^\smallfrown \langle a\rangle.$ 
\end{notation} 

\begin{notation} Frequently I will write 
\[\vec s\] 
to indicate that $\vec s$ is a sequence. In this 
case 
\[s_j\] 
will refer to the $j$th term. 

For $\vec s$ a sequence we can use $lh(\vec s)$ to indicate the length 
of $s$. Thus if $\vec s\in X^k$ then $lh(\vec s)=k$. 
\end{notation} 

\begin{notation} For $R$ a well founded relation or $<$ a well ordering, 
we let $||R||$ or $||<||$ denote the ordinal  corresponding  to their ranks. 
Thus for $R$ a relation on a set $X$ 
and assuming that there is no infinite descending chain 
$(x_i)_{i\in\o}$ such that at each $i$ we have 
\[x_i Rx_{i+1}\] we let 
$||R||$ be the least ordinal $\gamma$ such that there is some 
\[\rho: X\rightarrow \gamma\] such that whenever 
$xRy$ we have $\rho(y)\in \rho(x)$. 
\end{notation} 


I will assume basic notions of 
constructibility. In particular for $X$ a recursive 
Polish space and $x\in X$ I need to ask that the 
reader can make sense the constructible hierarchy built 
over $x$ -- that is to say, the collection of transitive 
structures of the form 
\[L_\alpha[x]\] 
where $\alpha$ is an ordinal. 

This is easily understood when $X$ is a space 
such as $2^\omega$ or $\omega^\omega$ but requires more 
creativity when $X$ is a recursive space whose elements 
cannot be viewed as infinite subsets of the hereditarily 
finite sets. For these less friendly spaces we need 
to work out some method of coding, and since the precise 
details will be irrelevant, I will leave them 
undiscussed. Alternatively the reader may choose to 
view all our statements about 
recursive spaces as holding only for those that are 
rudimentarily definable 
subsets of 
\[{\cal P}({\rm HF})\] 
and whose elements are therefore 
subject to relative constructibility in the 
usual way. Indeed this would be an appropriate attitude, since 
we will be primarily interested in the recursive Polish spaces 
$2^\o$, $\oo$, Mod$({\cal L})$ (see section \ref{model} below) and 
their products; in all these cases the individual points 
of the space are subsets of the hereditarily finite sets. 

\begin{definition} LO is the subset of $2^{\o\times\o}$ 
consisting of $x$ such that 
\[<^x=\{(n, m): x(n, m)=1\}\] defines a linear ordering. 
WO is the subset of LO consisting of $x$ with 
$<^x$ defining a linear ordering of $\omega$ which is a well ordering, 
in the sense that there is no infinite sequence $(n_i)_{i\in\o}$ 
such that at each $i$ 
\[n_{i+1}<^x n_i.\] 
\end{definition} 


\newpage 

\section{Descriptive set theoretical prerequisites} 
\label{descriptive} 

We presume a robust familiarity with low level 
effective  
descriptive set theory, as applying to $\Sigma^1_1$, $\Pi^1_1$, and 
$\Delta^1_1$ subsets of recursive Polish spaces; a development 
of recursive spaces adequate to our needs can be found in 
\cite{moschovakis}; a presentation specific to the space $\oo$ is 
given in \cite{jech}, which should already be good enough since 
our recursive spaces can naturally be thought of as recursive 
closed subsets of $\oo$. 

We will also use the theory of admissible sets. 
This is developed 
\cite{barwise} and to a lesser extent 
\cite{keisler}. 

While \cite{barwise} completely covers the 
theory of admissible sets and while \cite{moschovakis} thoroughly 
chronicles the effective theory for $\Sigma^1_1$, there 
seems to be no canonical reference for the connections between 
these two topics. Thus we sketch a few isolated proofs below. 

\begin{definition} For $x\in 2^\omega$ we let 
$\omega_1^{{\rm ck}(x)}$ be the supremum of the ranks 
of the well orders of $\o$ recursive in $x$. 
$\omega_1^{{\rm ck}}$ indicates the supremum of the ranks of the 
well orderings that are outright recursive. 
\end{definition} 

\begin{theorem} \label{kunenmartin} 
Any $\Sigma^1_1(x)$ well founded 
relation on $2^\o$ has rank less than $\omega_1^{{\rm ck}(x)}$. 
\end{theorem} 

\begin{proof} We let $R$ be our relation which is well founded 
in the sense of there being no sequence $(y_i)_{i\in\o}$ with 
\[y_iRy_{i+1}\] at each $i$. We let 
\[T\subset \bigcup_{n\in\o}2^n\times \o^n\times 2^n\] 
be a recursive in $x$ tree with 
\[yRz\] 
if and only if there is $f\in\oo$ such that at all $n$ 
\[(y|_n, f|_n, z|_n)\in T.\] 

With this set up, we can just go ahead and apply the 
usual proof of Kunen-Martin as found at 2G \cite{moschovakis}. We 
let $H$ be the set of all triples of the form 
\[(s_1, u_1, s_2, u_2,...u_n, s_{n+1})\] 
where $n\in\o$ and each $s_i\in 2^n$, each $u_i\in \o^n$, 
and each $(s_i, u_i, s_{i+1})\in T$. This gives rise to 
a well founded relation by defining  
\[(s_1, u_1, s_2, u_2,...u_n, s_{n+1})
S(s_1', u_1', s_2', u_2',...u_n', s_{m+1}')\] 
if $m\geq n$ and for each $j\leq n$ we have $u_j\subset u'_j$ and 
$s_j\subset s_j'$.  
We may  embed  the well founded relation $R$ into $S$ in the usual 
way: For any 
$(y_1, y_2,..., y_{n+1})$ and $(f_1, ..., f_n)$ with 
\[(y_i, f_i, y_{i+1})\in [T]\] 
all $i\leq n$, we can associate 
\[(y_1|_n, f_1|_n,..., f_n|_n, y_{n+1}|_n)\in S\] 
and observe that it must have rank at least equal to 
$y_{n+1}$. 


Thus the rank of $S$ is at least that of $R$. 
The usual Kleene Brower ordering on $S$ given at 
4A of \cite{moschovakis} gives a  well ordering  of the 
sequences in $S$ with rank at least that of $R$. Since $H$ is 
a recursive in $x$ 
subset of the hereditarily finite sets, we 
obtain a well ordering of $\omega$ which is recursive in $x$ and 
has rank at least that of $R$. 
\end{proof} 

Recall that no ordinal between $\omega$ and 
$\omega_1^{{\rm ck}(x)}$ can be admissible, since any 
$\omega$-model 
of Kripke-Platek set theory can provide 
ordinals for all its 
orderings of $\omega$ which are actually 
well orderings in $V$. 

\begin{corollary} 
$L_{\omega_1^{{\rm ck}(x)}}[x]$ is admissible. 
\end{corollary} 

\begin{proof} The main issue is to verify the 
characteristic $\Sigma_1$ reflection axiom. So suppose that 
$A\in L_{\omega_1^{{\rm ck}(x)}}[x]$ and 
\[\forall a\in A\exists \alpha< \omega_1^{{\rm ck}(x)} 
(L_\alpha[x]\models \varphi(x, a))\] 
for some formula $\varphi$ of set theory. 

 Unraveling  the usual recursive definition of the 
well ordering of $L[x]$ and using that $A$ appears at 
a level coded by a recursive in $x$ well ordering, we 
may assume that $A=\omega$. We then define a well ordering 
on $\o\times\o$ by 
\[(n, m)<(n', m')\] 
if and only if either: 

\leftskip 0.5in 

\noindent (i) $n<n'$; or 

\noindent (ii) $n=n'$ and for $<_n$ the first 
recursive in $x$ well ordering of $\o$ such that 
\[L_{||<_n||}[x]\models \varphi(x, n)\] 
we have $m<_n m'$. 

\leftskip 0in 

It is easily checked that this is a 
$\Sigma^1_1(x)$ well ordering of $\o\times \o$, and thus it has rank 
less than $\omega_1^{{\rm ck}(x)}$. If we let $\gamma$ be its rank, 
then the definitions at once give 
\[\forall n\in \o\exists \alpha<\gamma 
(L_\alpha[x]\models \varphi(x, a)).\]
\end{proof} 

This granted we can take a further step with the 
notation. 

\begin{definition} For $a$ a  set, $\omega_1^{{\rm ck}(a)}$ is the least 
ordinal $\alpha>\omega$  for which 
\[L_{\alpha}[a]\] 
is admissible. 
\end{definition} 

This is not our original definition, but equivalent to it in 
the case that $a\subset\omega$. 
We can then go on and let $\omega_2^{{\rm ck}(a)}$ be the next 
admissible ordinal for $a$ and in general let 
$\omega_\delta^{{\rm ck}(a)}$ be the $\delta$th ordinal 
$\alpha>\omega$ with 
\[L_{\alpha}[a]\]
admissible. 
 

\begin{notation} 
One easily sees that for $\varphi$ a formula of set theory there 
are corresponding $P_\varphi\in \Pi^1_1$ and $A_\varphi\in \Sigma^1_1$ 
such that for all $x\in 2^\o$ and 
$e\in\o$ with $\{e\}^x$, the $e$th recursive in $x$ relation on 
$\o$, providing a well ordering 
of 
$\o$ with rank $\gamma<\omega_1^{{\rm ck}(x)}$ 
one has 
\[L_\gamma[x]\models \varphi(x)\] 
if and only if 
\[(x, e)\in P_{\varphi}\] 
if and only if 
\[(x, e)\in A_\varphi.\]  
\end{notation} 




\begin{theorem} 
\label{spector-gandy} 
(Spector-Gandy) 

(1) 
A set $P\subset \oo$ is $\Pi^1_1$ if and only if there is a 
recursive closed set $C\subset\oo\times\oo$ 
such that 
\[x\in P\Leftrightarrow \exists y\in \Delta^1_1(x)((x, y)\in C).\] 

(2) A  set $P\subset \oo$ is $\Pi^1_1$ if and only if there is a            
formula $\varphi$ of set theory 
such that
\[x\in P\Leftrightarrow \exists \alpha
<\omega_1^{{\rm ck}(x)}(L_{\alpha}[x]\models \varphi(x)).\] 
\end{theorem} 

\begin{proof} (1) is given at 4F.3 \cite{moschovakis}, so this 
leaves us facing down (2). 

So suppose that $\varphi$ is given. Then we may find 
$P_\varphi\in \Pi^1_1$ as above 
so that for all $x\in 2^\o$ and
$e\in\o$ with $\{e\}^x$ presenting a recursive in $x$ 
well ordering of
$\o$ of rank $\gamma< \omega_1^{{\rm ck}(x)}$ one has
\[L_{||\{e\}^x||}[x]\models \varphi(x)\]
if and only if
\[(x, e)\in P_{\varphi}.\] 
Thus $x\in P$ if and only if there is $e\in\o$ with $\{e\}^x$ a 
well ordering and $(x, e)\in P_{\varphi}$. 

The converse direction follows since given 
\[P=\{x\in 2^\o:\forall f\in \oo \exists n ((x|_n, f|_n)\notin T)\}\] 
for $T$ some recursive tree on $x$, we have $x\in P$ if and 
only if the least admissible structure containing $x$ can 
provide a ranking function for the recursive in $x$ tree 
\[T_x=\{u: (x|_{lh(u)}, u)\in T\}.\] 
\end{proof} 



(2) implies that a subset of $\omega$ is $\Pi^1_1$ if and only if 
it is $\Sigma_1$ over ${\Lck}$. 





\begin{theorem} (Boundedness for $\Sigma^1_1$.) 
\label{boundedness} Assume: 

\begin{enumerate} 

\item $A\subset\oo$ is $\Sigma^1_1$; 
\item $\psi(v_0, v_1)$ is a $\Sigma_1$ formula of set theory; 

\item for all $x\in A$ there exists 
$d\in L_{\omega_1^{{\rm ck}(x)}}[x]$ 
with 
\[L_{\omega_1^{{\rm ck}(x)}}[x]\models\psi(x, d).\] 

\end{enumerate} 

Then there is some $\gamma_0<\omega_1^{\rm ck}$ such that 
for all $x\in A$ there exists $d\in L_{\gamma_0}[x]$ with 
\[L_{\gamma_0}[x]\models\psi(x, d).\]
\end{theorem} 

\begin{proof} 

We let $B$  be the set of  $(x,e)\in 2^\o\times\o$ such that 
$\{e\}^x$ is a recursive linear ordering on $\o$ and for all 
other $e^*\in\o$ we have either 

\leftskip 0.5in 

(i) $\{e^*\}^x$ is not a well ordering of $\omega$; or 


(ii) $(x, e^*)\in A_{\neg\exists d\psi(v_0, d)}$; or 

(iii) there is an ordering preserving map of $\{e\}^x$ 
into $\{e^*\}^x$. 

\leftskip 0in 

By our assumptions this implies that $(x, e)\in B$ 
if and only if $\{e\}^x$ is a well ordering of 
$\o$ with rank no greater than $\alpha$ 
where $\alpha$ is least such that 
\[L_{\alpha}[x]\models\exists d\psi(x, d).\] 
And then we can obtain a well founded $\Sigma^1_1$ 
relation on $B\times B$ by 
setting 
\[(x, e, n)>(x', e', m)\] 
if and only if $x=x'$ and $e=e'$ and $n$ occupies a higher 
position in the linear of $\o$ provided by $\{e\}^x$ than 
does $m$. 

Now the result follows by \ref{kunenmartin}. 
\end{proof} 

Note that the property indicated for $\gamma_0$ in the conclusion of 
\ref{boundedness} is uniformly $\Pi^1_1$ in any recursive well ordering 
of length $\gamma_0$. Thus the property will be uniformly 
in any index for the $\Sigma^1_1$ set  
$\Sigma_1$ over ${\Lck}$. 


\newpage

\section{Equivalence relations} 
\label{borel} 

\begin{definition} 
For $X$ and $Y$ Polish spaces and $E$ and $F$ we 
write 
\[E\leq_B F\] 
if there is a Borel function 
\[\theta: X\rightarrow Y\] 
such that for all $x_1, x_2\in X$ 
\[x_1 Ex_2 \Leftrightarrow \theta(x_1) F\theta(x_2).\]
Here we say that $E$ is {\it Borel reducible} to $F$ and that 
$\theta$ is a reduction
If we can find a reduction $\theta$ 
which is not only Borel but continuous, then we write $E\leq_c F$. 

We write $E\sqsubseteq_B F$ if we may find a Borel reduction which is 
one to one and $E\sqsubseteq_c F$ if we can find a continuous reduction 
which is one to one. 
\end{definition} 

\begin{definition} An equivalence relation $E$ on a Polish space 
$X$ is {\it Borel} if it appears in the $\sigma$-algebra generated 
by the open sets in the product topology on $X \times X$; in other words, 
it is Borel with respect to the canonical Polish topology on 
$X\times X$. 

An equivalence relation is {\it countable} if every equivalence class 
is countable. 
\end{definition} 

Perhaps the simplest of the Borel equivalence relations are the 
identity relations on various Polish spaces. 

\begin{notation} For $X$ a Polish space we let id$(X)$ be the 
identity relation on $X$, so that $x_1$id$(X)$$x_2$ if and only 
if $x_1=x_2$. 
\end{notation} 

These simplest of equivalence relations are the subject of Silver's theorem 
from \cite{silver}, restated below in modern notation. This theorem is 
also sometimes called the {\it first dichotomy theorem} for Borel equivalence 
relations. 

Here it should be understood as implicit in its statement that we view 
$\o$ as a discrete space, so that it is certainly Polish, and we view 
$2^\o$ as a Polish space in the product topology. 

\begin{theorem} (Silver) Let $E$ be a Borel equivalence relation. 
Then exactly one of the following happens: 

\leftskip 0.5in 

\no (I) $E\leq_B {\rm id}(\o)$; 

\no (II) ${\rm id}(2^\o)\leq_B E$. 

\leftskip 0in 

\end{theorem} 

In fact the statement of the theorem can be slightly 
embellished. In (II) we at once have that the reduction must be 
one to one, and so  ${\rm id}(2^\o) \sqsubseteq_B  E$; then one can 
obtain a comeager subset of $2^\o$ on which the reduction is continuous, 
since every Borel function is continuous on a comeager set, and this 
comeager set must in turn contain a homeomorphic copy of the 
Cantor space, and thus in fact 
${\rm id}(2^\o) \sqsubseteq_c  E$. 

Just beyond the identity relations one has the Vitali 
equivalence relation. 

\begin{definition} We let $E_v$, the {\it Vitali 
equivalence relation,}  
be the equivalence relation on $\R$ arising 
from the cosets of $\Q$; thus $x E_v y$ if and only if 
$x-y\in\Q$. 

We let $E_0$ be the equivalence relation of eventual agreement on 
$2^\o$. Thus for $f_0, f_1\in 2^\o$ we let $f_0 E_0 f_1$ if there is 
some $N\in\o$ such that for all $k>N$ 
\[f_0(k)=f_1(k).\] 
\end{definition} 

\begin{fact} (See \cite{dojake}) 
$E_v\leq_B E_0\leq E_v$. 
\end{fact} 

Here one has the {\it second dichotomy theorem:} 

\begin{theorem} (Harrington-Kechris-Louveau; see \cite{hakelo}) 
Let $E$ be a 
Borel equivalence relation. Then exactly one of the following happens:

\leftskip 0.5in

\no (I) $E\leq_B {\rm id}(2^\o)$;

\no (II) $E_0\leq_B E$.

\leftskip 0in

\end{theorem}

In fact in (II) they obtain $E_0\sqsubseteq_c  E$. In any case a 
short Baire category argument shows that for all equivalence relations 
$F$, if $E_0\leq_B F$ then $E_0\sqsubseteq_c F$. 

Among the Borel equivalence relations an important type are those induced 
by the continuous action of a Polish group on a Polish space. In the 
case that a Polish group $G$ acts continuously on a Polish space $X$ we 
use $E^X_G$ to denote the orbit equivalence relation. 

Here there is essentially only one {\it known} 
Borel equivalence relation not 
reducible to some such $E^X_G$. 

\begin{definition} We view $(2^\o)^\o$ as a Polish space in 
the product topology. 
For $\vec x=\langle x_0, x_1, x_2,...\rangle, 
\vec y=\langle    y_0, y_1,...\rangle\in (2^\o)^\o$ we 
set 
\[\vec x E_1 \vec y\] 
if there is some $N\in\o$ such that 
\[\forall k>N (x_k=y_k).\] 
\end{definition} 

\begin{theorem} (Kechris-Louveau; see \cite{kechrislouveau}) 
If $G$ is a Polish group acting continuously on a Polish space 
$X$, then 
\[E_1\not\leq_B E^X_G.\] 
\end{theorem} 

$E_1$ is also the subject of the {\it third dichotomy 
theorem} of \cite{kechrislouveau}: 


\begin{theorem} (Kechris-Louveau) 
If $E \leq_B E_1$, then 
exactly one of the following happens:

\leftskip 0.5in

\no (I) $E\leq_B E_0$;

\no (II) $E_1\leq_B E$.

\leftskip 0in

\end{theorem}

A parallel result was obtained in 
\cite{hjorthkechris} for the countable product of 
$E_0$. 

\begin{definition} For $\vec x, \vec y\in (2^\o)^\o$ 
we set $\vec x (E_0)^\o \vec y$ 
\[\forall n\in\o (x_n E_0 y_n).\] 
\end{definition} 

\begin{theorem} (Hjorth-Kechris) 
If $E \leq_B (E_0)^\o$, then
exactly one of the following happens:

\leftskip 0.5in
   
\no (I) $E\leq_B E_0$;

\no (II) $(E_0)^\o\leq_B E$.   

\leftskip 0in

\end{theorem}

Among the Borel equivalence relations an especially important 
class are those arising in the form 
\[E^X_H,\] 
where $H$ is a closed subgroup of 
the Polish group $S_\infty$, consisting of all permutations 
of $\o$ in the topology of pointwise convergence, acts  continuously  
on the Polish space $X$. It is shown in \cite{beckerkechris} 
that these are up to Borel reducibility exactly the Borel 
isomorphism relations on classes of countable structures. 


\cite{hjorthkechris} further proved that whenever $H$ a is 
sufficiently nice closed subgroup of $S_\infty$  
-- for instance, abelian -- acting continuously on a Polish 
space $X$ with a Borel orbit equivalence relation, 
we have either 
\[E^X_H\leq E\] 
for some {\it countable} 
Borel equivalence relation $E$ or 
\[(E_0)^\o\leq_B E^X_H.\] 
Without any great conviction, and mainly out of a desire to 
be provocative, it was then conjectured that this result should 
hold for $H$ an arbitrary closed subgroup of $S_\infty$. 

This paper proves that conjecture. 

\newpage 








\section{Model theoretic generalities} 
\label{model} 

\begin{definition} For $\l$ a countable language, we let $\lone$ be the 
countably infinitary logic obtained from the atomic formulas of $\l$ by 
closing under countable conjunction 
\[\bigwedge\] 
countable disjunction 
\[\bigvee\] 
as well as the first order operations of $\wedge$, $\vee$, 
$\neg$, $\exists x$ and $\forall x$, but allowing only formulas 
with finitely many variables. 

$\l_{\omega, \omega}$ is the set of first order formulas 
generated by $\l$. 

\end{definition} 

We will use the term ``fragment" in a specific sense; our meaning 
is more narrow than the usual model theoretic definition, in as much 
as we require that $F$ be countable and that it include all atomic 
formulas, and hence determine the language from which it was cleaved.  

\begin{definition} 
A set of formulas $F\subset \lone$ is a {\it fragment} if  

\leftskip 0.5in 

\noindent (i) $F$ is countable; 

\noindent (ii) $F$ is closed under the first order operations of 
$\wedge$, $\vee$, 
$\neg$, $\exists x$ and $\forall x$; 

\noindent (iii) $F$ is closed under all substitution instances; 

\noindent (iv) $F$ includes all atomic  formulas; 

\noindent (v) $F$ is closed under subformulas. 

\leftskip 0in 

\end{definition} 



\begin{definition} For $\l$ a countable language, we let 
Mod$({\cal L})$ be the space of all countable $\l$-structures whose 
underlying set is $\omega$. We equip this with the topology 
generated by quantifier free formulas, so that the basic open sets 
have the form 
\[\{\m\in\mod : \m\models \varphi(\vec a)\}\] 
for some $\varphi\in \l_{\omega, \omega}$ in which no quantifiers 
appear and some $\vec a\in \o^{<\omega}$. 
We may naturally identify Mod$(\l)$ with 
\[\prod_k(\prod_{\sigma_0(k)}\o^{(\o^k)}\prod_{\sigma_1(k)}2^{(\o^k)}),\]
where each $\sigma_0(k)\in\{0, 1, 2,...,\aleph_0\}$ is 
the number of function symbols of arity $k$ and 
$\sigma_1(k)\in\{0, 1, 2,...,\aleph_0\}$ is
the number of relation symbols of arity $k$.  
\end{definition} 

Thus $\mod$ in the topology of quantifier free formulas is 
a recursive Polish space all of whose elements are subsets of 
the hereditarily finite sets. Thus as remarked at the end of 
section \ref{set}, there is no controversy in forming 
\[L_\alpha[\m]\] 
for $\alpha$ an ordinal and $\m\in\mod$. 

It is also well known, and can be found at \cite{hjorth} 2.3, that the 
resulting space $\mod$ equipped with the topology of {\it all first order 
formulas} is again Polish. Thus for any theory $T$ the set 
\[\{\m\in\mod :\m\models T\}\] 
is a closed subset and hence a Polish space in its own 
right. Both these topologies, first order and quantifier free, 
give rise to the same Borel structure; thus from our point of 
view they are largely interchangeable. 



\begin{notation} 
From now on let us take part in the usual model theoretic 
convention regarding sequences from a structure, thus using 
\[\vec a\in \m\] 
(rather than $\vec a\in \m^{<\o}$) to indicate that $\vec a$ 
is a sequence in $\m$. 

In the case that 
\[\rho:\m\rightarrow \n\] 
is a mapping between two models and 
$\vec a=\langle a_0, a_1,..., a_l\rangle$ is a sequence 
from $\m$ of length $l+1$ let us simply write 
\[\rho(\vec a)\] 
for the sequence $\langle \rho(a_0), 
\rho(a_1),..., \rho(a_l)\rangle\in \n$. 

\end{notation} 


 
\begin{definition} For $F$ a fragment and $\m$ and $\n$ models, let us 
say that a map 
\[\rho: \m\rightarrow \n\] 
is {\it $F$-elementary} if for all $\vec a\in \m$ and and 
$\varphi(\vec x)\in F$ we have 
\[(\m\models \varphi(\vec a))\Leftrightarrow 
(\n\models \varphi(\rho(\vec a))).\] 
\end{definition} 
 
\begin{notation} For each language $\l$ let us fix a 
corresponding infinite sequence $({\bf c}_i)_{i\in\omega}$ of 
fresh constants. 
For $k\in \omega$ we
let $\l^k$ be the extension of $\l$ obtained by adding the
constant symbols $({\bf c}_i)_{i<k}$.
 
For $\m\in\mod$ and
$\vec a\in\m$ we define
\[\langle \m;\vec a\rangle\]
to be the expansion of $\m$ to $\l^{lh(\vec a)}$ obtained
by insisting that at each $i<lh(\vec a)$
\[\langle \m;\vec a\rangle\models {\bf c}_i=a_i.\]
Naturally we may also write 
\[\langle \m;\vec a, \vec b,...\rangle\] 
in place of $\langle \m;\vec a^\smallfrown \vec b^\smallfrown 
...\rangle$. 
\end{notation}
 
For $F$ a fragment in $\l$ and $\l^k$ as in the previous 
definition, we may view $F$ as giving rise to a canonical 
fragment for $\l^k$ by simply closing $F$ under all substitution 
instances of the larger language. 
When there seems to be no threat of confusion it will be notationally 
convenient to identify $F$ with this canonical extension 


\begin{definition} For $\l$ a recursive language, 
$F$ a fragment for $\l$, $\m\in$ Mod$(\l)$, and 
$\vec a\in\m$ we let 
\[F{\rm -type}_\m(\vec a)\] 
be the $F$ type of $\vec a$ from the point of view of $\m$. 
Explicitly: 
\[\{\psi(\vec x): \psi\in F, \m\models\psi(\vec a)\}.\] 
\end{definition} 


\begin{notation} For $\m\in\mod$ and $\l'\subset \l$, we let 
\[\m|_{\l'}\] 
denote the reduction of $\m$ to the language $\l'$. 
\end{notation} 

\begin{definition} For $\sigma\in \lone$ we let 
\[{\rm Mod}(\sigma)\] 
be the set of $\m\in\mod$ with 
\[\m\models\sigma.\] 
\end{definition} 

Of course the space ${\rm Mod}(\sigma)$ may no longer be a Polish space, 
and we have an understandable bias in favor of not stepping too far 
away from this nice class of spaces. 
One solution would be to take the topology indicated by the smallest fragment 
containing $\sigma$; another is provided by the next definition and lemma. 

\begin{definition} A formula $\psi\in\lone$ is $\Pi^0_1$ if it has the form 
\[\bigwedge_{i\in\omega}\psi_{ j}\] 
where each $\psi_j$ is a quantifier free first order formula. 
A formula is $\Sigma^0_1$ if it 
has the form 
\[\bigvee_{i\in\omega}\psi_{ j}\]                      
where each $\psi_j$ is  quantifier free and first order. 
After this we just iterate through the ordinals in the usual 
fashion, with 
formulas of the form 
\[\bigvee_{j\in\omega}\exists \vec x \psi_j(\vec y, \vec x)\] 
being $\Sigma^0_\alpha$ if each $\psi_j$ is $\Pi^0_\beta$ for some 
$\beta<\alpha$ and 
\[\bigwedge_{j\in\omega}\forall \vec y \psi_j(\vec y, \vec x)\]
being $\Pi^0_\alpha$ if each $\psi_j$ is $\Sigma^0_\beta$ for some
$\beta<\alpha$. 


\end{definition} 


The set of models satisfying a ${\Pi}^0_\alpha$ formula will be a 
$\Ubf{\Pi}^0_\alpha$ subset of $\mod$. 

\begin{lemma}\label{polish} Let $\l$ be a recursive language and let 
$\sigma\in \lone$. Then there is a countable language 
$\hat{\l}\supset \l$ and 
$\hat{\sigma}\in \hat{\l}_{\omega_1, \omega}$ such that 

\leftskip 0.5in 

\noindent (i) $\hat{\sigma}\in {\Pi^0_2}$; 

\noindent (ii) the reduction map 
\[{\rm Red}:{\rm Mod}({\hat{\l}})\rightarrow \mod\] 
\[\m\mapsto \m|_{\l}\] 
restricted to  {\rm Mod}$(\hat{\sigma})$  
witnesses 
\[\cong|_{{\rm Mod}(\hat{\sigma})}\leq_B
\cong|_{{\rm Mod}({\sigma})}\leq_B
\cong|_{{\rm Mod}(\hat{\sigma})}.\] 
\end{lemma} 

\begin{proof} Let $F$ be the fragment generated by $\sigma$. For each 
$\psi(\vec x)\in F$ we introduce a new relation $R_{\psi(\vec x)}$ into 
our language $\hat{\l}$. Then for $\n\in\mod$ we define 
\[{\rm Exp}(\n)\in {\rm Mod}(\hat{\l})\] 
to be the expansion of $\n$ given by 
\[{\rm Exp}(\n)\models R_{\psi(\vec x)}(\vec a)\] 
if and only if 
\[\n\models \psi(\vec a).\] 
We also obtain that 
\[{\rm Red}\circ {\rm Exp}:\mod\rightarrow\mod\] 
is the identity map. 

The set 
\[\{{\rm Exp}(\n): \n\in \mod\}\] 
is easily seen to be defined by a ${\Pi}^0_2$ formula in 
Mod$({\hat{\l}})$ and 
\[\{{\rm Exp}(\n): \n\models \sigma\}\] 
equals 
\[\{{\rm Exp}(\n): {\rm Exp}(\n)\models \forall aR_{\psi(x)}(a)\}\] 
where $\psi(x)$ is the formula 
\[(x=x)\wedge \sigma.\] 
\end{proof} 

Thus by the statement at  3C \cite{classical} that $\Ubf{\Pi}^0_2$ 
subspaces of Polish spaces are Polish, 
we may identify any space Mod$(\sigma)$ 
with a Polish subspace of some Mod$(\hat{\l})$



\begin{definition} 
We let $S_{\infty}$ be the group of all permutations of $\omega$ equipped with the 
topology of pointwise convergence; we 
let it act in the natural manner on any space of the form $\mod$.  
(See \cite{beckerkechris} or \cite{hjorth} $\S$2.1.) 
\end{definition} 

\begin{definition} For $\sigma\in\lone$ we let 
$\cong\!|_{{\rm Mod}(\sigma)}$ denote the isomorphism 
relation on models of $\sigma$ in $\mod$. 
\end{definition} 

Here of course the orbit equivalence relation arising from the 
action of $S_\infty$ on $\mod$ is just the relation 
$\cong\!|_{{\rm Mod}(\sigma)}$ 
of isomorphism. 

\begin{theorem} (Becker-Kechris; see \cite{beckerkechris}) 
Let $H$ be a closed subgroup of $S_\infty$ and $X$ a Polish space on 
which $H$ acts continuously with orbit equivalence relation 
$E^X_H$. 
Then there is a countable language $\l$ and $\sigma\in\lone$ such that 
\[E^X_H\leq_B \cong\!|_{{\rm Mod}(\sigma)}\leq_B E^X_H.\] 
\end{theorem}
 

%We shall take for granted a fact that can also be found in 
%\cite{beckerkechris}. 

%\begin{lemma} $\cong\!|_{{\rm Mod}(\sigma)}$ is Borel if and only if 
%there is a countable ordinal $\gamma$ such that every model of $\sigma$ has 
%Scott height less than $\gamma$. 
%\end{lemma} 

%Strictly speaking Becker and Kechris only state this lemma for countable 
%models of $\sigma$, but an easy absoluteness argument shows that 
%$\gamma<\aleph_1$ provides a bound on the Scott heights of countable models 
%if and only if it provides a bound on the Scott heights of all the 
%models. 


It will be helpful at some point to make the assumption that 
all our models have something close to a 
pairing function, which enables us to encode the 
type of any finite tuple by the type of a single point. 

\begin{lemma} \label{(a1)} 
Let $\l$ be a recursive 
language and $\sigma\in \l_{\omega_1, 
\omega}$. Then there is a richer recursive 
language $\hl\supset \l$ and $\hat{\sigma}\in \hl$ 
such that: 

\leftskip 0.5in 

\noindent (i) for each $\m\in$ {\rm Mod}$(\hat{\sigma})$ and 
$\vec a\in \m$ there is some point $b_{\vec a}\in \m$ 
for any fragment $F$ we have $F${\rm-type}$_\m(\vec a)$ first 
order definable from 
$F${\rm -type}$_\m(b_{\vec a})$; 

\noindent (ii) $\cong|_{{\rm Mod}(\hat{\sigma})}\leq_B 
\cong|_{{\rm Mod}({\sigma})}\leq_B
\cong|_{{\rm Mod}(\hat{\sigma})}$. 
\end{lemma} 

\leftskip 0in 


\begin{proof} There are many ways to see this. 

We can for instance 
pass from $\m$ to $\m^{eq}$ in the sense 
$\S$4.3 \cite{hodges}. The relevant processes of going back 
and forth are clearly Borel. 
\end{proof} 

It will also be convenient at some stage to assume that each point 
in our model is repeatedly infinitely often. 

\begin{lemma} \label{(a2)}
Let $\l$ be a recursive
language and $\sigma\in \l_{\omega_1,
\omega}$. Then there is a richer recursive
language $\hl\supset \l$ and $\hat{\sigma}\in \hl$
such that:
 
\leftskip 0.5in
 
\noindent (i) for each $\m\in$ {\rm Mod}$(\hat{\sigma})$ and $\vec a 
\in \m$ and $b\in \m$ there are infinitely many 
$b'\in \m$ such that 
\[\langle \m; \vec a^\smallfrown b\rangle \cong 
\langle \m; \vec a^\smallfrown b'\rangle;\] 
 
\noindent (ii) $\cong|_{{\rm Mod}(\hat{\sigma})}\leq_B
\cong|_{{\rm Mod}({\sigma})}\leq_B
\cong|_{{\rm Mod}(\hat{\sigma})}$; 

\noindent (iii) moreover if each $\m\in$ {\rm Mod}$(\sigma)$ satisfies 
\ref{(a1)}(ii) then so too each $\hat{\m}\in$ {\rm Mod}$(\hat{\sigma})$ 
satisfies \ref{(a1)}(ii). 


\end{lemma}
  
\leftskip 0in
 
 
\begin{proof} 
We introduce an equivalence relation $E$ to the language $\l$ and let $\hat{\sigma}$ 
express that each $E$-equivalence class is infinite and that $E$ is a congruence 
with respect to the language $\l$ and that 
\[\m/E,\] 
the result of quotienting out of 
the model $\m$ by the equivalence relation $E$, is 
a model of $\sigma$ in the natural interpretation of $\l$. 
\end{proof} 

\newpage 

\section{Aside: Something about Gandy-Harrington} 
\label{something} 

%Some mathematicians consider Gandy-Harrington and see a 
%topology generated 
%by the $\Sigma^1_1$ sets; for us it will be a notion of forcing.  
%The main interest here is that it is frequently useful to consider 
%a ``generic" member of a $\Sigma^1_1$ set. While this style of 
%presentation is never indispensable, it can save us numerous quantifiers in 
%describing a construction or proof.  

%At section \ref{aside}, specifically the non-trivial implication in 
%\ref{aside6}, it will also turn out important to be able 
%to carry the property of being a ``generic" point through the limit 
%stages of some process. For this reason it is helpful to quantify 
%the precise level of genericity which will be sufficient and to 
%show that the set of generic points is itself $\Sigma^1_1$ and 
%hence by \ref{limit} that it may be preserved. 

%In fact it turns out that the property of $x$ being {\it low} -- 
%that is to say $\omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}$ -- already 
%suffices for all the purposes to which we place Gandy-Harrington 
%forcing and in some sense this is the main conclusion of 
%\ref{A5}. Thus one might want to view the arguments in section 
%\ref{aside} and to a lesser extent the main proof of \ref{case(I)} 
%and beyond as being performed just using the notion of a real 
%$x$ which is low and making little or no appeal to Gandy-Harrington 
%forcing. 
%While this is possible way to think about these proofs I am not 
%sure it is especially natural and in any case the lemmas below 
%seem to have some independent interest. 

We momentarily  detrain  for  
a kind of extended philosophical 
aside on Gandy-Harrington forcing viewed as a device 
to obtain ``generic" members of a non-empty 
$\Sigma^1_1$ set; the main arguments of 
section \ref{case(I)} and beyond are always 
working with the combinatorics of $\Sigma^1_1$ sets and 
this naturally requires us to consider 
``typical" elements which are devoid of 
accidental properties. 
We present 
a sequence of little 
lemmas trying to suggest that the useful 
content of considering a 
{\it generic member} $x$ of a $\Sigma^1_1$ set 
$A$ is exhausted by the specification 
$\omega_1^{{\rm ck}(x)}=
\omega_1^{\rm ck}.$ 

Most of this section is never quoted again; only 
\ref{A6.b} and \ref{A7} reappear. 
These are in any case well known and have  
direct proofs. 


We state everything for the point class 
of lightfaced $\Sigma^1_1$. It should be clear that they all hold 
in a relativized form for the relativized class $\Sigma^1_1(z)$ 
whenever $z$ is an element of a recursive Polish space. 


\begin{definition} For $X$ a recursive Polish space we let 
${\cal P}_X$ denote the non-empty $\Sigma_1^1$ subsets of 
$X$ ordered by inclusion. We write $A_1\leq A_2$, read as ``$A_1$ is 
stronger than $A_2$", if 
\[A_1\subset A_2.\] 
In this way ${\cal P}_X$ becomes a partial order. 

A subset $G\subset {\cal P}_X$ is a {\it filter} if 

\leftskip 0.5in 

\noindent (i) for any $A_1, A_2\in G$ 
there is some $B\in G$ with $B\leq A_1$, $B\leq A_2$; 

\noindent (ii) if $A_1\leq A_2$ and $A_1\in G$ then $A_2\in G$.

\leftskip 0in 

A set $D\subset {\cal P}_X$ is {\it dense} if for all $A_1\in 
{\cal P}_X$ there is some $A_2\leq A_1$ with $A_2\in D$. For 
${\cal D}$ a collection of dense sets, we say that a filter $G$ is 
${\cal D}$-generic if for all $D\in {\cal D}$ we have 
\[G\cap D\neq \emptyset.\] 

\end{definition} 

For the accuracy and clarity of later computations it is helpful 
to isolate the precise degree of genericity required of our filters. 

\begin{definition} A filter $G\subset {\cal P}_X$ is {\it sufficiently 
generic} if whenever 
\[C\subset X\times \oo\] 
is a recursive closed set either 

\leftskip 0.5in

\noindent (i) there is $A\in G$ such that for all $x\in A$ and $f\in \oo$ 
\[(x, f)\notin C;\] 

or  

\noindent (ii) there is $A\in G$ and $n\in\o$ such that for all $x\in A$ 
there is some $f\in\oo$ with 
\[f(0)=n\]
and
\[(x, f)\in C.\] 

\leftskip 0in 

\end{definition} 

Here are two easy facts about this definition, the second of which helps justify 
our choice of terminology. Neither of them should 
require a proof. 

\begin{fact} \label{Ai} 
$G$ is sufficiently generic if and only if for $k\in \omega$ and 
\[C\subset X\times \oo\]
either: 
 
\leftskip 0.5in
 
\noindent (i) there is $A\in G$ such that for all $x\in A$ and $f\in \oo$
\[(x, f)\notin C;\]

\noindent or 
 
\noindent (ii) there is $A\in G$ and $s\in\o^k$ such that for all $x\in A$
there is some $f\in\oo$ with
\[f|_k=s\]
and
\[(x, f)\in C.\]
 
\leftskip 0in 
 
\end{fact} 

\begin{fact} \label{Aii} 
There is a  countable collection of dense sets, ${\cal D}=\{D_i: i\in\omega\}$, 
such 
that a filter $G$ is sufficiently generic if and only if it is 
${\cal D}$-generic. 
\end{fact} 


It turns out that a sufficiently generic filter gives rise to and can be 
encoded by a corresponding point in $X$. The next two lemmas are in some 
form standard and well known, and one can certainly find in 
\cite{sacks}, or in \cite{hakelo} working with a topological 
formulation, that there is a countable ${\cal D}$ which will 
enforce the conclusions of \ref{A0} and \ref{A1} for any 
${\cal D}$-generic $G$. 

We give fragmentary proofs only to dispel doubts whether 
the notion of ``sufficiently generic" really is sufficient. 

\begin{lemma} 
\label{A0} For $G\subset {\cal P}_X$ sufficiently generic there is a 
unique 
\[x(G)\in X\] 
such that for all ${\cal O}$ basic open we have 
\[x(G)\in {\cal O}\] 
if and only 
\[{\cal O}\in G.\] 
\end{lemma} 


\begin{proof} First to see that there is at most one such $x(G)$, 
note that for each 
rational number 
$q>0$ we may let 
$(U_n)_{n\in\omega}$ be an enumeration of open sets such that 

\leftskip 0.5in 

\noindent (i) $X=\bigcup_{n\in\omega} U_n$; 

\noindent (ii) $d_X(U_n)<q$, where $d_X$ is the complete metric for 
$X$ and $d_X(U_n)$ is the diameter of $U_n$ with respect to that metric; 

\noindent (iii) $C=\{(x, f): x\in \overline{U_{f(0)}}\}$ is a recursive 
closed subset of $X\times \oo$. 

\leftskip 0in 

\noindent If $G\subset {\cal P}_X$ is sufficiently generic then there 
will be some $k$ and $A\in G$ such that for all $x\in A$ one has that there 
is some $f\in\oo$ with $f(0)=k$ and $(x, f)\in C$. This amounts to saying that 
for all $x\in A$ we have 
\[x\in {\overline{U_k}}.\] 
Thus 
\[A\subset \overline{U_k}\] 
and thus 
\[\overline{U_k}\in G\] 
since $G$ is a filter. But then for all 
\[x_1, x_2\in \bigcap\{{\cal O}: {\cal O} {\rm \: basic \: open} \in G\}\] 
we have 
\[d_X(x_1, x_2)<q.\] 
Tending $q\rightarrow 0$ we have $x_1=x_2.$ 

To see the converse we retrieve the argument from the first half of 
the proof to find an infinite sequence of basic open sets 
\[(W_n)_{n\in\omega}\] 
such that at each $n$ 
\[\overline{W_{n+1}}\subset \overline{W_n}\] 
\[d(W_n)<\frac{1}{n}\] 
\[\overline{W_n}\in G\] 
and for any basic open set ${\cal O}\in G$ we have some $n$ with 
\[\overline{W_{n}}\subset {\cal O}.\] 
Then we may find a point 
\[x(G)\in \bigcap_{n\in \omega} \overline{W_n},\] 
which must be as required. 
\end{proof} 

\begin{notation} In the case that 
\[X=X_0\times X_1\times ...\times X_n\] 
is the product of $n+1$ many recursive Polish spaces, we define for 
each $i\leq n$ the projection map 
\[p_i: {\cal P}_X\twoheadrightarrow {\cal P}_{X_i}\] 
given by 
\[A\mapsto \{x_i\in X_i: \exists x_0\exists x_1...\exists x_{i-1}\exists x_{i+1}...
((x_0, x_1, ..., x_{i-1}, x_i, x_{i+1},...)\in A)\}.\] 
This is parallel to the usual definition of the projection map 
\[\pi_i: X\twoheadrightarrow X_i\]
\[(x_0, x_1, ..., x_i, x_{i+1},...)\mapsto x_i.\]  
%For $G\subset {\cal P}_X$ sufficiently generic we define 
%\[x_i(G)\in X_i\] 
%by 
%\[x_i(G)=\pi_i(x(G)).\] 
\end{notation} 

The three lemmas are essentially due to Gandy, just 
rephrased in the context of our technical notion of sufficient 
genericity. 

\begin{lemma} 
\label{A1} If $G\subset {\cal P}_X$ is sufficiently generic then 
for all $A\subset X$ in $\Sigma^1_1$ we have 
\[A\in G\] 
if and only if 
\[x(G)\in A.\] 
\end{lemma} 

\begin{proof} For the forward direction with $A\in G$ we recall that 
any 
such $\Sigma^1_1$ set has the form 
\[A=\{x: \exists f((x, f)\in C)\}\] 
for some $C\subset X\times \oo$ recursively closed. 

Thus 
we 
can apply \ref{Ai} as in \cite{sacks} to successively obtain 
\[s_0\subset s_1\subset...\subset s_i\subset s_{i+1}...,\]
each $s_n\in \o^n$, and  
\[A_0\supset A_1\supset....\supset A_i\supset A_{i+1}...\] 
with each $A_i\in G$ and 
\[\forall x\in A_i\exists f\supset s_i((x, f)\in A_i).\] 
Then for 
\[f=\bigcup_{i\in \o} s_i\] 
we have that for all basic open ${\cal O}\in G$ and $i\in\o$ 
\[A_i\cap {\cal O}\neq \emptyset\] 
and hence there is some $y\in {\cal O}$ with 
\[(y, f)\in C.\] Since 
the collection of basic open sets appearing in $G$ forms a neighbourhood 
basis for $x(G)$ we indeed have 
\[(x(G), f)\in C.\] 

Conversely if $A \notin G$ then there will be some $B\in G$ with 
\[B\cap A=\emptyset.\] 
Then since $x(G)\in B$ by the only if direction above, 
we have 
\[x(G)\notin A,\] as demanded. 
\end{proof} 

\begin{lemma} \label{A3} 
If $G\subset {\cal P}_X$ is sufficiently generic, 
then for all $A\in \Sigma^1_1$ with $A\subset X$ we have either: 

\leftskip 0.5in 

\noindent (i) $x(G)\in A$; or 

\noindent (ii) there is $B\in G$ with $A\cap B=0$. 

\leftskip 0in 

\end{lemma} 

\begin{proof} 
If we let $C\subset X\times \oo$ be a recursive closed set 
such that 
\[A=\{x: \exists f((x, f)\in C)\}\] 
then the lemma follows from \ref{A1} and the definition of 
$G$ being sufficiently generic. 
\end{proof} 

\begin{theorem} (Gandy) \label{A4} 

If $G\subset {\cal P}_X$ is sufficiently generic, then 
\[\omega^{{\rm ck}(x(G))}_1=\omega_1^{{\rm ck}}.\] 
\end{theorem} 

\begin{proof} This is {\it exactly} as in the usual proof, since 
if \[\{e\}^{x(G)}\] codes a recursive well ordering then 
by \ref{A3} there will be 
some $B\in G$ such that for all $y\in B$ one has 
that 
\[\{e\}^y\] 
codes a well ordering. Then by the boundedness theorem for 
$\Sigma^1_1$ there must be some $\gamma<\omega_1^{{\rm ck}}$ 
such that for all $y\in B$ we have $\{e\}^y$ as a well ordering 
of rank less than $\gamma$. 
Since $x(G)\in B$ by \ref{A1} we are done. 
\end{proof} 

\begin{corollary} (Gandy) \label{low} 
Any non-empty $A\in\Sigma^1_1$  
contains some $x$ with 
\[\omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}.\] 
\end{corollary} 

\begin{proof} Since we can clearly diagonalize in a filter below $A$ 
to meet the countably many dense sets of \ref{Aii}. 
\end{proof} 

The combination of \ref{A1} and \ref{A4} allows a converse, which we 
present below along with two other characterizations of being sufficiently 
generic which have a much more set theoretical flavor. 

\begin{lemma} 
\label{A5} 
The following are equivalent: 

\leftskip 0.5in 



\noindent  (0) $G$ is sufficiently generic; 

\noindent (i) there is some $x(G)$ in the intersection of the
basic open sets appearing in $G$ and for this $x(G)$ we have that 
\[G=\{A\in \Sigma^1_1: x(G)\in A\}\] 
and for all $A\in \Sigma^1_1$ 
either 

\leftskip 1in 

\no (a) $x(G)\in A$, or 

\no (b) there is some $\Sigma^1_1$ set $B$ with $A\cap B=0$ and 
$x(G)\in B$; 

\leftskip 0.5in 

\noindent (ii) there is some $x(G)$ in the intersection of the 
basic open sets appearing in $G$ and for this $x(G)$  we have 
\[G=\{A\in \Sigma^1_1: x(G)\in A\}\] 
and 
\[\omega_1^{{\rm ck}(x(G))}=\omega_1^{{\rm ck}};\] 


\noindent (iii) 
there is some $x(G)$ with 
\[G=\{A\in \Sigma^1_1: x(G)\in A\}\] 
and for this $x(G)$ 
there is an $\omega$-model $M$ of ZFC minus 
the power set axiom and an $M$-generic filter 
\[H\subset ({\cal P}_X)^M\] such that 

\leftskip 1in 

\noindent  $x(H)=x(G)$; 

\leftskip 0.5in

\noindent (iv) 
there is some $x(G)$ with  
\[G=\{A\in \Sigma^1_1: x(G)\in A\}\]
and for this $x(G)$ and any $B\in G$ 
there is an $\omega$-model $M$ of ZFC minus
the power set axiom and an $M$-generic filter
\[H\subset ({\cal P}_X)^M\] such that
 
\leftskip 1in

\noindent  (a) $x(H)=x(G)$;

\noindent (b) $M[H]\models x(G)\in B$. 

\leftskip 0in 

\end{lemma} 

\begin{proof} The equivalence of (0) and (i) 
is given by \ref{A1} and \ref{A3} and the 
definition of being sufficiently generic. 

%(ii)$\Rightarrow$(0): This is contained 
%in the results due to Gandy quoted above. 

(ii)$\Rightarrow$(0):  Let us fix $C\subset X\times \oo$ a recursive closed set 
as in the definition of being sufficiently generic. 

If there exists $f_0$ with $(x(G), f_0)\in C$ then for $k=f_0(0)$ we 
have that $x(G)$ is an element of the $\Sigma^1_1$ set 
\[A=\{x\in X: \exists f((x, f)\in C\wedge f(0)=k)\}\] and we are done. 

Instead then suppose that  $x(G)$ is an element of the $\Pi^1_1$ set 
\[P=\{x: \forall f((x, f)\notin C)\}.\] 
Fix a recursive continuous function 
\[\rho: X\rightarrow {\rm LO}\] such that 
\[\rho^{-1}[{\rm WO}]=P.\] 
Since $\omega_1^{{\rm ck}(x(G))}=\omega_1^{\rm ck}$ we have some 
$\gamma<\omega_1^{\rm ck}$ with 
\[||\rho(x(G))||=\gamma.\] 
Then the $\Delta^1_1$ set 
\[B=\{x\in X: ||\rho(x)||=\gamma\}\] 
will be in $G$ by our assumptions and is 
exactly as required for the 
definition of sufficient genericity. 

(i)$\Rightarrow$(iv): Given $x(G)$ arising from a sufficiently 
generic $G$, and given a specific $B\in G$, we have that the conclusion 
of (iv) refers to $x$ being in a certain $\Sigma^1_1$ set. Thus  
it 
will fail the conclusion of (iv) if and only if there is some 
$\Sigma^1_1$ set $A_0\in G$ necessitating that failure. But 
this is 
plainly impossible, since given $A_0, B\in G$ we may choose a 
countable  
elementary submodel of some rank initial segment $V_\delta$ of $V$ and 
force below $A_0\cap B$ meeting all the dense sets existing in our 
countable submodel. 

(iv)$\Rightarrow$(iii): Obviously. 

(iii)$\Rightarrow$(ii): Fix $M$ our $\omega$-model and $x=x(G)\in M$. 
There are two possibilities. The first being that 
the ordinal (or an isomorphic copy of the ordinal) $\omega_1^{{\rm ck}}$ 
is in $M[H]$, whence $M[H]$ correctly calculates the structure 
$L_{\omega_1^{{\rm ck}}}[x]$, and thus by internalizing the proof of 
\ref{A4} to $M[H]$ we have that $L_{\omega_1^{{\rm ck}}}[x]$ is indeed admissible. 
Alternatively the ordinal does 
not appear in $M[H]$, which since $M[H]$ satisfies 
Kripke-Platek set theory gives that there is no well ordering of $\omega$ 
in $M$ of length $\omega_1^{{\rm ck}}$, and in particular that there is 
no $x$-recursive well ordering of $\o$ of length $\omega_1^{{\rm ck}}$. 


\end{proof} 



\begin{corollary} 
\label{A6} 
The set of $x\in X$ for which there is some sufficiently generic 
$G$ with $x(G)=x$ is $\Sigma^1_1$. 
\end{corollary} 

\begin{proof} It is well known that 
\[\{x\in X: \omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}\}\] 
is $\Sigma^1_1$, and indeed it follows at once from the 
statement of  (iii) from \ref{A5}.  
\end{proof} 


\begin{corollary} 
\label{A6.b} 
For any non-empty $A\in \Sigma^1_1$ the set 
\[\{x\in A: \omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}\}\] 
is a non-empty $\Sigma^1_1$ set. 
\end{corollary} 

\begin{corollary} 
\label{A7} 
If $\omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}$ 
then for all $A\in\Sigma^1_1$ we have either 

\leftskip 0.5in 

(i) $x\in A$; or 

(ii) there is $B\in \Sigma^1_1$ with 
\[x\in B\] 
and 
\[A\cap B=0.\] 
\end{corollary} 



\begin{corollary} 
\label{A2} If $X=X_0\times X_1$ is a recursive Polish space and 
\[G_0\subset {\cal P}_{X_0}\] is a sufficiently generic filter, 
with $A\in \Sigma^1_1$ such that 
\[\{x_0: \exists x_1 \in X_1((x_0, x_1)\in A)\}\in G,\] 
then 
there is a sufficiently generic filter 
$G\subset {\cal P}_X$ with 
\[A\in G\] 
\[p_0[G]=G_0.\] 
\end{corollary} 

\begin{proof} 
Since 
\[ \omega_1^{{\rm ck}(x(G_0))}=\omega_1^{\rm ck}\] 
we can apply the relativized version of \ref{low} to 
find some $x_1$ with 
\[(x(G_0), x_1)\in A\] and 
\[ \omega_1^{{\rm ck}(x(G_0), x_1)}=\omega_1^{{\rm ck}(x(G_0))}=\omega_1^{\rm ck}.\]
Then by \ref{A5} we have that 
\[G=\{B\in {\cal P}_X: (x(G_0), x_1)\in B\}\] 
is as required. 
\end{proof} 


\newpage

\section{The central definition} 
\label{definition}  

We do everything below for $\Sigma^1_1$ sets, 
a recursive language $\l$, 
and formulas and fragments in $\Lck$. It should be clear that 
the entire sequence of statements relativizes to $\Sigma^1_1(z)$ 
and recursive in $z$. 
 

\begin{notation} For ${\cal L}$ a recursive language 
and $A\subset$ Mod$({\cal L})$ a 
$\Sigma^1_1$ set, $\m\in$ Mod$({\cal L}),$  and 
\[\vec a=\langle a_0, a_1,...,a_n\rangle
\in \m,\] 
let us write 
\[{\cal M}\models A(\vec a)\] 
if there is some 
$\pi\in S_\infty$ with 
\[\pi(a_l)=l\] all $l\leq n$ and 
\[\pi\cdot \m\in A.\] 

\end{notation} 

\begin{notation} For each recursive language ${\l}$ 
fix a $\Sigma^1_1$ set 
\[{\cal U}^{{\l}}\subset 
\omega\times {\rm Mod}({\cal L})\] 
that is 
universal in the sense that any $\Sigma^1_1$ set $A\subset 
{\rm Mod}({\cal L})$ appears as 
\[A={\cal U}^{{\l}}_n=\{\m: (n, \m)\in {\cal U}^{{\l}}\}\] 
for some suitable choice of $n$. 
\end{notation} 


\begin{fact} 
\label{*} For ${\l}$ a recursive language 
we may find a function 
\[{\cal R}: \omega\times\omega \times\omega_1\rightarrow 
{\l}_{\omega_1, \omega}\] 
\[(n,l, \alpha)\mapsto \psi^{{\l}}_{n, \alpha}\] such that 

\leftskip 0.5in 

\noindent (i) ${\cal R}|_{\omega\times\omega\times\delta}$ is uniformly 
$\Delta_1^{L_\delta}$ for any countable 
admissible ordinal $\delta$; 

\noindent (ii) for $\m\in{\rm Mod}({\cal L})$ and $\vec a\in\m$ with 
$lh(\vec a)=l$ we have  
\[\m\models {\cal U}^{{\l}}_n(\vec a)\] 
if and only if for all $\alpha <\omega_1^{{\rm ck}(\m)}$ 
\[\m\models \neg \psi_{n,l,\alpha}^{{\l}}(\vec a),\] 
which in turn happens if and only if 
for all $\beta<\aleph_1$ 
\[\m\models \neg \psi_{n,l,\beta}^{{\l}}(\vec a).\] 
\end{fact} 

\begin{proof} Fix ${\l}$, $n$, and $l$. 
Let $A$ be the $\Sigma^1_1$ set 
\[\{\n: \exists \pi\in S_\infty: \forall k<l (\pi(k)=k)\wedge 
\pi\cdot \n\in {\cal U}^{{\l}}_n\}\] 
obtained by suitably saturating 
${\cal U}^{{\l}}_n$. 
Fix a recursive continuous 
\[\rho: {\rm Mod}({\cal L})\rightarrow {\rm LO}\] 
with 
\[\rho^{-1}[{\rm WO}]={\rm Mod}({\cal L})\setminus A.\] 
Following \cite{vaught} or 16.C \cite{classical} we obtain 
$\psi^{{\l}}_{n, l,\alpha}\in {\l}_{\omega_1, \omega}$ 
for each $\alpha$ with 
\[\m\models \psi^{{\l}}_{n, l,\alpha}(\vec a)\] 
if and only 
if for a relatively comeager 
set of $\pi\in S_\infty$ in the set of permutations sending 
each $a_j$ to $j$  
we have 
\[||\rho(n, \pi\cdot \m)||\leq \alpha.\] 
The various calculations of these 
$\psi^{{\l}}_{n, l,\alpha}$ proceed in the effective category, and we 
have that 
\[(n,l, \alpha)\mapsto \psi^{{\l}}_{n, l,\alpha}\] 
is as required. 
\end{proof} 

The notation of \ref{*} is convoluted when given in explicit  
detail, so it seems 
wise to tolerate an abbreviation. 

\begin{notation} 
For $B$ a $\Sigma^1_1$ set in 
Mod$({{\l}})$ with $B={\cal U}^{{\l}}_n$ let us write 
\[\psi_{B, \alpha}\] 
for 
\[\psi^{{\l}}_{n, l,\alpha},\] 
where $l$ is given by context and the formula 
$\psi^{{\l}}_{n, l,\alpha}$ is given by \ref{*}. 
\end{notation} 

Strictly speaking the formula 
$\psi^{ {\l}}_{n, l,\alpha}$ depends not just on $B$, $l$, and 
$\alpha$, but 
also the choice of the index $n$ with 
$B={\cal U}^{ {\l}}_n$. Although the notation is therefore not 
completely correct, this 
will never lead to problems and we will always understand the 
expression 
\[\m\models \psi_{B, \alpha}(\vec a)\] 
to indicate that 
\[\m\models \psi^{ {\l}}_{n, l,\alpha}(\vec a)\] 
where $ {\l}$ is the language of $\m$, $n$ is some 
fixed choice of an index for $B$, and $l$ is the length of 
the sequence $\vec a$. 


\begin{definition} For $\l\in \Lck$ and $\m, \n\in$ Mod$(\l)$ let us say 
that an embedding 
\[i:\m\rightarrow \n\] 
is {\it $\omega_1^{{\rm ck}(\m,\n)}$-elementary} if for 
all $\psi\in L_{\omega_1^{{\rm ck}(\m,\n)}}\cap\lone$ and $\vec a\in \m$ we have 
\[\m\models \psi(\vec a)\] 
if and only if 
\[\n\models \psi(i(\vec a)).\] 
\end{definition} 

Note here that the we only consider constructible $\psi$. The collection of 
formulas depends only on the size of the least $(\m,\n)$-admissible ordinal, 
and {\it not} on the exact composition of say the model 
$ L_{\omega_1^{{\rm ck}(\m,\n)}}[\m,\n] $. 

However even with this restriction to this seemingly modest set of 
formulas we are already able to prove: 

\begin{fact} 
\label{**} Let 
\[i:\m\rightarrow \n\] 
be $\omega_1^{{\rm ck}(\m,\n)}$-elementary. Then 
for all $\vec a\in\m$ and 
$A\in\Sigma^1_1$ we have 
\[\m\models A(\vec a)\] 
if and only if 
\[\n\models A(i(\vec a)).\] 
\end{fact} 

\begin{proof} Tracing through the implications given by the definitions,  
and \ref{*}  we have 
\[\m\models \neg A(\vec a)\] 
if and only if 
\[\exists \alpha <\omega_1^{{\rm ck}(\m,\n)}(\m\models 
\neg \psi_{A, \alpha}(\vec a))\] 
if and only if (by elementarity assumption on $i$) 
\[\exists \alpha <\omega_1^{{\rm ck}(\m,\n)}(\n\models
\neg \psi_{A, \alpha}(i(\vec a)))\] 
if and only if 
\[\n\models \neg A(i(\vec a)).\] 
\end{proof} 

Up until now this section has consisted in 
technicalities; the next definition is central 
to what will follow. 

\begin{definition} Let $F\in \Lck$ be a fragment for 
some recursive language $\l$. A $\Sigma^1_1$ set $A$ is 
{\it $F$-barren} for $l$ if for all $\m_0, \m_1\in$ Mod$(\l)$ and 
\[i:\m_0\rightarrow \m_1\] 
$\omega_1^{{\rm ck}(\m_0,\m_1)}$-elementary 
and $\vec b\in \m_1$ with $lh(\vec b)=l$ we have if 
\[\m_1\models A(\vec b)\] 
then 
\[F-{\rm type}_{\m_1}(\vec b)\in \{F-{\rm type}_{\m_0}(\vec a): 
\vec a\in \m_0\}.\] 
\end{definition} 


\newpage 

\section{Consequences of the definition} 
\label{consequences} 

We fix $\l$ a recursive language and prove various 
facts about the notion of being barren. They 
relativize smoothly to languages which are recursive in 
$z$. 

First of all: The property of being $F$-barren is 
$\Pi^1_1$ in the indices for $\Sigma^1_1$ sets. 

\begin{lemma} 
\label{B1}
Let ${\cal U}^{\l}$ be a 
$\Sigma^1_1$ subset of $\omega\times {\rm Mod}(\l)$ which 
is universal in the sense of \ref{*}. Let $F\in \Lck$ 
be a fragment for $\l$. 

Then  
\[\{n\in \omega: {\cal U}^{\cal L}_n {\rm \: is \:} 
F{\rm-barren\: for\:}l\}\] 
is a $\Pi^1_1$ subset of $\omega$. 
\end{lemma} 

\begin{proof} The set of $(\m, \n, i)$ such that 
\[i:\m\rightarrow \n\] 
is $\omega_1^{{\rm ck}(\m, \n)}$-elementary is 
$\Sigma^1_1$ by Spector-Gandy. The set of all 
$(\m, \n, i, \vec a)$ such that $F$-type$_\n(\vec a)$ is 
not realized in $\m$ is $\Delta^1_1$. 

That said, the lemma follows by the usual kinds of 
manipulation and counting of quantifiers. 
\end{proof} 

Clearly the proof of \ref{B1} is uniform in $F$ and $\l$. 
If we let $P$ be 
the set of 
\[(n, m, k)\in \omega\times\omega\times\omega\] 
such that $k$ gives the index for a recursive language, call it 
$\l_k$, 
$\{m\}$ is a recursive well order of $\omega$, and 
$\alpha_m$ its rank,  
the $\alpha_m$th object in $\Lck$ is a fragment $F_m$ for 
$\l_k$, and ${\cal U}^\l_n$ is $F_m$-barren, 
then we obtain that $P$ is $\Pi^1_1$ set. 


\begin{corollary}
\label{B2} 
Let $F\in \Lck$ be a fragment for $\l$. Let $A\in\Sigma^1_1$ be 
$F$-barren for $l$. 
Then there is a $\Delta^1_1$ set $D\supset A$ which is again 
$F$-barren. 
\end{corollary} 

\begin{proof} There are a couple of ways to see this, the 
most brutal of which is to simply read it off from 
the statement of $\Pi^1_1$ reflection from \cite{hamash} 
after quoting \ref{B1}. 
 
Alternatively we may apply the boundedness theorem in 
the following way. 
Consider the $\Sigma^1_1$ set $B$ 
of $(\m, \n, i, \vec a)$ with 
\[i:\m\rightarrow \n\]
$\l_{\omega, \omega}$-elementary and the 
$F$-type$_\n(\vec a)$ 
not realized in $\m$. We then let 
$(\psi_{A, \alpha})_{\alpha\in\aleph_1}$ 
be as in \ref{*} and the notational remark it 
precedes. We have then that for all 
$(\m, \n, i, \vec a)\in B$ there is some 
$\alpha<\omega_1^{{\rm ck}(\m, \n)}$ such that 
\[\exists \beta<\alpha (\n\models \psi_{A, \beta}(\vec a)).\] 

But then by \ref{boundedness} we may find a single 
$\gamma_0<\omega_1^{\rm ck}$ such that for all 
$(\m, \n, i, \vec a)\in B$
\[\exists \beta<\gamma_0 (\n\models \psi_{A, \beta}(\vec a)).\] 
Thus we may take $D$ to be 
\[\{\n\in\mod: \n\models \bigwedge_{\beta<\gamma_0}
\neg\psi_{A,\beta}(0, 1, ..., l-1)\}.\] 
\end{proof} 

\begin{definition} 
A formula $\psi(x_0, x_1,..., x_{l-1})$ is {\it $F$-barren} for $l$ 
if the corresponding 
set 
\[D_{\psi(\vec x)}=\{\m: \m\models \psi(0,1,...,{l-1})\}\] 
is $F$-barren in the above sense. 
\end{definition} 

Thus in the proof of 
\ref{B2} we actually obtained: 

\begin{corollary} 
\label{B2.a} 
If $A$ is an $F$-barren for $l$ $\Sigma^1_1$ set 
then there is an $F$-barren for $l$ formula 
$\psi(x_0, x_1,..., x_{l-1})\in \Lck$ with 
\[D_{\psi(\vec x)}\supset A.\] 
\end{corollary} 

%\begin{proof} 
%Repeatedly applying \ref{B2} we obtain a sequence $(D_n)_{n\in\omega}$ 
%of $\Delta^1_1$ sets and a sequence $(A_n)_{n\in\omega}$ 
%of $\Sigma^1_1$ sets 
%\[A_0=A\subset D_0\subset A_1\subset D_1\subset...\] 
%such that at each $n\in\omega$: 

%\leftskip 0.5in 

%\noindent (i) $A_{n+1}$ is the set of $\m$ for which there exists 
%an isomorphism 
%\[\pi:\m\cong\n\] 
%with 
%\[\n\models D_n(\pi(0), \pi(1), ..., \pi(l-1)),\] 
%and in this way is like an 
%invariantization or saturation of $D_n$; 

%\noindent (ii) $D_n$ is $F-$barren. 

%\leftskip 0in 

%The proof of \ref{B2} allows us to find this sequence 
%effectively, and thus we may assume 
%\[D_\infty=\bigcup_{n\in\omega} D_n\] 
%is again $\Delta^1_1$. Since it is clearly invariant we can appeal 
%to \cite{vaught} to find a formula $\psi(\vec x)\in\Lck$ with 
%\[D_\psi(\vec x)=D_\infty.\] 
%\end{proof} 

\begin{corollary} 
\label{B3} 
For $F\in\Lck$ a fragment and $l\in\o$ we have a set 
$A_F^l\in\Sigma^1_1$ such that 
\[\m\models A_F^l(\vec a)\] if and only if for no $A\in\Sigma^1_1$ 
that is $F$-barren for $l$ do we have 
\[\m\models A(\vec a).\] 
\end{corollary} 

\begin{proof} 
At once from \ref{B2.a} and Spector-Gandy. 

\end{proof} 

\begin{definition} For each $l\in\o$ and $F\in\Lck$ let 
$A_F^l$ be the set of $m$ such that there is no $F$-barren 
for $l$ set $A\in \Sigma^1_1$ with 
\[\m\models A(0, 1,...,l-1).\] 
\end{definition} 

It is not so elegant to continually be writing a superscript $l$, so 
we just use $A_F$ where context indicates $l$. Similarly we 
use the abbreviated term {\it $F$-barren} when there 
seems no danger of confusion. 

\begin{lemma} 
\label{B4} Let $\psi$ be $F$-barren. 
Then there is a fragment $H\in \Lck$ 
such that whenever 
\[i:\m\rightarrow \n\] 
is $H$-elementary and $\vec b\in\n$, 
\[\n\models\psi(\vec b)\] 
implies that $F${\rm -type}$_\n(\vec b)$ appears in 
$\{F${\rm -type}$_{\m}(\vec a):\vec a\in \m\}.$ 
\end{lemma} 

\begin{proof} 
The set of $(\m, \n, i, \vec b)$ for which 
\[\m\models\psi(\vec b)\]
and $i$ is elementary with respect to first order formulas   
but  $F$-type$_\n(\vec b)$ is not realized 
over $\m$ is $\Sigma^1_1$; the assumption on 
$\psi$ then guarantees some $\alpha<\omega_1^{{\rm ck}(\m,\n)}$ 
and some $\varphi\in L_{\alpha}$ and some $\vec a\in \m$ with 
\[(\m\models \varphi(\vec a))\Leftrightarrow 
(\n\models\neg\varphi(i(\vec a))).\] 

Thus by the boundedness theorem for $\Sigma^1_1$ 
we have some single $\gamma_0< 
\omega_1^{{\rm ck}}$ such that 
whenever 
\[i: \m\rightarrow \n\] 
\[F{\rm -type}_\n(\vec b)\notin 
\{F{\rm -type}_{\m}(\vec a):\vec a\in \m\}\] 
then there exists $\alpha<\gamma_0$ and 
$\varphi\in L_{\alpha}$ with 
\[(\m\models \varphi(\vec a))\Leftrightarrow
(\n\models\neg\varphi(\vec a)).\] 

We finish with $H=\lone\cap L_{\gamma_0}$. 
\end{proof} 



For future reference it may be helpful to note that the set 
of $F$-barren $\psi(\vec x)$ is uniformly in $F$ 
$\Pi^1_1$ in the codes as is 
the set of $H$ as in \ref{B4}. Thus by Spector-Gandy we have that 
the set of 
\[(F,\psi)\in \Lck\] 
such that $F$ is a fragment for $\l$ and $\psi$ is $F$-barren 
is a $\Sigma_1^{\Lck}$ set as is the set of 
triples 
\[(F, H,\psi)\] 
fulfilling the conclusion of \ref{B4}. 

In the course of section 
\ref{case(I)} we will need the following two lemmas. 

\begin{lemma} 
\label{B5} 

Suppose $\m\models A_F(a)$ and $\omega_1^{{\rm ck}(\m)}=
\omega_1^{\rm ck}$. Then we may find $\n\in\mod$ and 
$\omega_1^{{\rm ck}(\n, \m)}$-elementary 
\[j:\n\rightarrow \m\] 
with $F${\rm -type}$_{\m}(a)$ not realized 
in $\n$. 
\end{lemma} 

\begin{proof} 
By \ref{A7} we obtain that the 
failure of the lemma would give some $\Sigma^1_1$ set $B$ 
with 
$\m\models B(a)$ and for all $\hat{\m}, \hat{a}$ with 
\[\hat{\m}\models B(\hat{a})\] 
we have that there is no 
 $\hat{\n}\in\mod$ and
$\omega_1^{{\rm ck}(\hat{\n}, \hat{\m})}$-elementary
\[\hat{j}:\hat{\n}\rightarrow \hat{\m}\]
with $F$-type$_{\hat{\m}}(\hat{a})$ not realized
in $\hat{\n}$. 
However this would be a direct contradiction to 
our assumption that $\m\models A_F(a)$. 
\end{proof} 


\begin{lemma}
\label{B6}

Suppose $\m\models A_F(a)$ and $\omega_1^{{\rm ck}(\m)}=
\omega_1^{\rm ck}$ and $B\in\Sigma^1_1$ with 
\[\m\models B(a).\] 
 
Then we may find $\n\in\mod$ and
$\omega_1^{{\rm ck}(\m, \n)}$-elementary
\[j:\m\rightarrow \n\]
and $b\in \n$ with 
\[\n\models B(b)\] 
and 
$F${\rm -type}$_{\n}(b)$ not realized
in $\m$.
\end{lemma}

\begin{proof} 
Otherwise we may again apply 
\ref{A7} to find some single 
$\Sigma^1_1$ set $C$ such that 
\[\m\models C(a)\] 
and 
for all $\hat{\m}, \hat{a}$ with
\[\hat{\m}\models C(\hat{a})\]
we have that there is no 
 $\hat{\n}\in\mod$ and
$\omega_1^{{\rm ck}(\hat{\m}, \hat{\n})}$-elementary
\[\hat{j}:\hat{\m}\rightarrow \hat{\n}\]
with some $\hat{b}\in\hat{\n}$ having 
\[\hat{\n}\models B(\hat{b})\] 
but 
$F$-type$_{\hat{\n}}(\hat{b})$ not realized
in $\hat{\m}$. 

Claim: There are no $\hat{\m}, \hat{\n}\in\mod$ 
and $\omega_1^{{\rm ck}(\hat{\m}, \hat{\n})}$-elementary
\[\hat{j}:\hat{\m}\rightarrow \hat{\n}\] 
with 
some $\hat{b}\in\hat{\n}$ having
\[\hat{\n}\models B(\hat{b})\wedge C(\hat{b})\]
but
$F$-type$_{\hat{\n}}(\hat{b})$ not realized
in $\hat{\m}$.

Proof of Claim: Otherwise fix $\hat{\m}, \hat{\n}$, $\hat{j}$, 
$\hat{b}$ as indicated. 
Then the elementarity of $\hat{j}$ along with 
\ref{**} gives that there will exist 
some $\hat{a}\in \hat{\m}$ with 
\[\hat{\m}\models B(\hat{a})\wedge C(\hat{a}).\] 
Then we have a contradiction to assumption on 
$C$. 
\hfill (Claim$\Box$) 

But then the claim implies that the set $B\cap C$ 
provides a direct contradiction to 
$\m\models A_F(a)$. 
\end{proof} 




%\begin{notation} Let $(c_i)_{i\in\omega}$ be an infinite 
%sequence of distinct 
%constants not appearing in $\l$. For $k\in \omega$ we 
%let $\l^k$ be the extension of $\l$ obtained by adding the 
%constant symbols $(c_i)_{i<k}$. 

%For $\m\in\mod$ and 
%$\vec a\in\m$ we define 
%\[\langle \m,\vec a\rangle\] 
%to be the expansion of $\m$ to $\l^{lh(\vec a)}$ obtained 
%by insisting that at each $i<lh(\vec a)$ 
%\[\langle \m,\vec a\rangle\models c_i=a_i.\] 
%\end{notation} 

\newpage 

\section{Aside: Which sentences have uncountable 
models?} 
\label{aside} 

The definition just considered leads naturally to a characterization 
of when a sentence $\varphi\in\lone$ admits an uncountable model. 
We carry a parameter $z\in 2^\o$ through the next couple of 
lemmas. 

Nothing in this section will be used again; it may indeed be safely ignored. 


\begin{definition} Let $\l$ be a recursive in $z$ language and 
$\m,\n\in\mod$. An embedding 
\[i:\m\rightarrow\n\] 
is {\it $\Sigma^1_1(z)$-elementary} if for all 
$A\in \Sigma^1_1(z)$ and $\vec a\in\m$ 
\[\m\models A(\vec a)\] 
implies 
\[\n\models A(i(\vec a)).\] 
\end{definition} 


\begin{lemma} 
\label{limit} Let $(\m_n)_{n\in\o}$ be a sequence in 
$\mod$ and suppose that at each $n$ we have a 
$\Sigma^1_1(z)$ elementary map 
\[\rho_n: \m_n\rightarrow \m_{n+1}.\]  

Then for the direct limit model 
\[{\rm Dir \: Lim}_{n\in\o} (\m_n)=\m_\infty\] 
and for the various induced direct limit maps 
\[\rho_{n,\infty}: \m_n\rightarrow \m_\infty\] 
we have that each $\rho_{n, \infty}$ is 
$\Sigma^1_1(z)$-elementary. 
\end{lemma} 

\begin{proof} It suffices to prove that for 
any $\Sigma^1_1(z)$ set $A$ we have that if 
\[\m_0\models A\] 
then 
\[\m_\infty\models A.\] 


Fix at each $n$ an enumeration 
$(a_i^n)_{i\in\o}$ of $\m_n$. 
For each $n\leq m$ let 
\[\rho_{n,m}:\m_n\rightarrow \m_m\] 
be the composition obtained from our given embeddings. 
These are all clearly 
$\Sigma^1_1(z)$ elementary. 

We may apply the definition of $\m\models A$ and 
our space $\mod$ to find a recursive in $z$ array  
\[(\varphi_{n,l}(v_0, v_1, ...., v_{n-1}))_{(n,l)\in\o\times\o}\] 
of 
quantifier free formulas such that for all $\n\in\mod$ 
we have 
\[\n\models A\] 
if and only if there is a permutation $\pi\in S_\infty$ 
and $f:\o\rightarrow \o$ 
such that at each $k\in\o$ 
\[\n\models \varphi_{k, f(k)}(\pi(0), \pi(1),...,\pi(k-1)).\] 

Claim: We may find a sequence $(m_n)_{n\in\o}$ of natural numbers and 
a sequence of 
finite sets $F_n\subset \m_n$ and corresponding 
$k_n$ equal to the size of $F_n$, 
with $\{b_i^n: i<k_n\}$ enumerating $F_n$ such that 
the following all hold: 

\leftskip 0.5in 

\noindent (i) for each $n$ and $i<k_n$ we 
\[\rho_n(b_i^n)=b_i^{n+1};\] 

\noindent (ii) at each $n$ there is a permutation $\pi_n$ 
of $\omega$ and $f:\o\rightarrow \o$ such that 

\leftskip 1in 

\noindent (a) $\pi_n(i)=b_i^n$ all $i<k_n$, and 

\noindent (b) for all $l\in\o$ 
\[\m_n\models \varphi_{l,f(l)}(\pi_n(0), \pi_n(1),...,\pi_n(l-1));\] 

\noindent (c) for all $l\leq n$ we have $f(l)=m_l$; 

\leftskip 0.5in 

\noindent (iii) for all $i, l\leq n$ there is some $j(i, l)<k_n$ such that 
\[b_n^{j(i, l)}=\rho_{l, n}( a_l^i).\] 

\leftskip 0in 

Proof of Claim: We show the existence of these things 
by induction on $n$. 
Suppose we have done this up to 
$F_n=\{b_i^n: i<k_n\}\subset \m_n$ and we wish to continue 
one more step and find $F_{n+1}$. 

Then obviously we start with $b_i^{n+1}=\rho_n(b_i^n)$ for 
each $i<k_n$. Since $\rho_n$ is a $\Sigma^1_1(z)$-elementary 
map we obtain that there is some permutation $\pi_{n+1}$ of 
$\o$ and function $f:\o\rightarrow \o$ 
such that 

\leftskip 1in
 
\noindent (a) $\pi_{n+1}(i)=b_i^{n+1}$ all $i<k_n$, and
 
\noindent (b) for all $l\in\o$
\[\m_{n+1}\models \varphi_{l, f(l)}(\pi_{n+1}(0), 
\pi_{n+1}(1),...,\pi_{n+1}(l-1));\]
 
\noindent (c) for all $l\leq \n$ we have $f(l)=m_l$. 

\leftskip 0in 

But then we can go to some large 
enough $k_{n+1}$ so that 
\[\{\rho_{l, n+1}( a_l^i): i, l\leq n+1\}\subset \{\pi_{n+1}(j): j<k_{n+1}\}.\] 
Taking $b_{n+1}^j=\pi_{n+1}(j)$ and $m_{n+1}=f(n+1)$ 
we continue to the next round. 
\hfill (Claim$\Box$) 

Now we can define $b^{\infty}_i\in\m_\infty$ to be 
\[\rho_{n,\infty}(b^n_i)\] 
for any sufficiently large $n$; this is well defined by 
part (i) of the claim. The first order elementarity 
of the various $\rho_n$ maps along with (ii) 
is sufficient to ensure that at 
every $k\in\o$ 
\[\m_\infty\models \varphi_{k,m_k}(b^\infty_0, b^\infty_1,..., b^\infty_{k-1}).\] 
Clause (iii) of the claim gives that $\{b_i^\infty: i\in\o\}$ 
enumerates $\m_\infty$. 
\end{proof} 


Thus from \ref{**} we have that $\omega_1^{{\rm ck}(\m,\n, z)}$-elementary 
embeddings are $\Sigma^1_1(z)$-elementary. With a bit of 
 shoving  and squeezing  
we could probably go through the next few steps only using this 
original notion of $\omega_1^{{\rm ck}(\m,\n,z)}$-elementarity, but the  
new definition is definitely more flexible. 


\begin{definition} A $\Sigma^1_1(z)$ set $A$ is said to be 
{\it unyielding} if whenever 
\[i:\m\rightarrow \n\] 
is $\Sigma^1_1(z)$-elementary  
and 
\[\n\models A\] 
then 
\[\forall b\in \n\exists a\in \m(i(a)=b).\] 
\end{definition}

\begin{lemma} 
\label{aside1} 
If $A$ is not unyielding then there is 
some pair $\m, \n\in\mod$ with 
\[\omega_1^{{\rm ck}(\m, \n)}=\omega_1^{{\rm ck}},\] 
\[\n\models A,\] 
and 
\[i:\m\rightarrow \n\] 
$\Sigma^1_1(z)$-elementary 
but not onto. 
\end{lemma} 

\begin{proof} A simple consequence of $A$ failing to be 
unyielding is that we may find $(\a, \b, j)$ with 
\[\b\models A,\] 
while the map  
\[j:\a\rightarrow \b\] is not onto and yet we still have 
for all $\psi\in L_{\omega_1^{{\rm ck}(z)}}[z]
\cap\lone$ and $\vec c\in \a$  
\[\a\models \psi(\vec c)\] 
if and only if 
\[\b\models \psi(j(\vec c)).\] 
Thus by \ref{low} we can find $(\m, \n, i)$ with 
\[\omega_1^{{\rm ck}(\m, \n)}=\omega_1^{{\rm ck}},\]
\[\n\models A,\] 
\[i:\m\rightarrow \n\] not onto,  
and for all $\psi\in  L_{\omega_1^{{\rm ck}(z)}}[z] 
\cap\lone$ and $\vec a\in \m$ we
have
\[\m\models \psi(\vec a)\]
if and only if
\[\n
\models 
\psi(j(\vec a)).\] 
But then it follows by \ref{*} that $j$ is $\Sigma^1_1(z)$ 
elementary. 
\end{proof} 



We then have a couple of lemmas in direct analogy with 
their counterparts in \ref{consequences}. 

\begin{lemma} \label{aside2} 
The property of being unyielding is 
$\Pi^1_1(z)$ in the indices for $\Sigma^1_1(z)$ sets. 
\end{lemma} 
\begin{proof} 
Given \ref{aside1}, this has a proof 
like \ref{B1}. 
\end{proof} 

\begin{corollary} 
\label{aside3} 
If $A\in\Sigma^1_1(z)$ is unyielding then there exists a 
$\Delta^1_1(z)$ set 
$D\supset A$ which is again unyielding. 
\end{corollary} 

\begin{proof} 
This follows \ref{aside2} as \ref{B2} followed 
\ref{B1}. 
\end{proof} 


 
\begin{definition}
A sentence $\psi$ is unyielding 
if the corresponding
set
\[D_{\psi}=\{\m: \m\models \psi\}\]
is unyielding in the above sense.
\end{definition}
 


\begin{corollary}
\label{aside4}  
If $A$ is an unyielding $\Sigma^1_1(z)$ set
then there is an unyielding sentence  
$\psi\in L_{\omega_1^{{\rm ck}(z)}}[z]$ with
\[D_{\psi}\supset A.\]
\end{corollary}

\begin{proof} By the method of 
\ref{B2.a}.
\end{proof} 

\begin{corollary}
\label{aside5}
We have a set 
$A^{{\rm u}, z}\in\Sigma^1_1(z)$ such that
\[\m\models A^{{\rm u}, z}\] if and only if 
for no $A\in\Sigma^1_1(z)$
that is unyielding do we have
\[\m\models A.\]
\end{corollary} 

\begin{proof} 
By \ref{aside5} and Spector-Gandy. 
\end{proof} 




With the definition given by \ref{aside5} we can state 
the theorem for this 
section. This is parallel to a similar result due to \cite{gao} 
in the special case that $\sigma$ is the Scott sentence of a 
countable model. 

\begin{theorem} 
\label{aside6} 
Let $\l$ be a recursive language and $\sigma\in 
L_{\omega_1^{{\rm ck}(z)}}[z]$. The following three things 
are equivalent: 

(1) $\sigma\in\lone$ has an uncountable model. 



(2) There are $\m, \n \in$ {\rm Mod}$(\sigma)$ and 
$\Sigma^1_1(z)$-elementary 
\[i:\m\rightarrow \n\] 
that is not onto. 

(3) For some $\n\in$ {\rm Mod}$(\sigma)$  
\[\n\models A^{{\rm u}, z}.\] 
 
\end{theorem} 

\begin{proof} 

First let us suppose in (1) that $\a$ is a model of $\sigma$ of size $\aleph_1$. 
Let $F$ be the fragment generated by $\sigma$ 
Then a standard Skolem hull argument enables us to find 
a chain of $F$-elementary models 
\[\m'{\Large \prec}_F \n'{\Large \prec}_F \a\] 
such that 

\leftskip 0.5in 

\noindent (i) $\m'$ is properly included in $\n'$; 

\noindent (ii) $\m'$ and $\n'$ are countable; 

\noindent (iii) for all $A\in\Sigma^1_1(z)$ and $\vec a\in \n_0$  
\[\exists \alpha<\aleph_1(\n'\models \psi_{A,\alpha}(\vec a))\] 
if and only if 
\[\exists \alpha<\aleph_1(\m'\models \psi_{A,\alpha}(\vec a)).\]

\leftskip 0in 

Thus if we choose $\m, \n\in\mod$ isomorphic to $\m', \n'$ 
respectively then we can obtain a $\Sigma^1_1(z)$-elementary map between 
$\m, \n$ that is not onto, and hence we have (2). 

The implication from (2) to (3) should be obvious. 


So this leaves us with the real work of showing that 
(3) implies (1). 

Claim: We may 
build by induction on $\alpha<\aleph_1$ a sequence of pairs of models 
$(\a_\alpha, \b_\alpha)$ and such that: 

(i) $\a_\alpha\in$ Mod$(\sigma)$ 
and  
$\omega_1^{{\rm ck}(\a_\alpha,z)}=\omega_1^{{\rm ck}(z)}$; 

(ii) $\b_\alpha$ is isomorphic to $\a_\alpha$; 

(iii) for $F$ the fragment generated 
by $\sigma$ and $\alpha<\beta<\aleph_1$ we have 
\[\b_{\alpha}{\Large \prec}_F \b_\beta\] 
and 
\[\b_\alpha\neq \b_\beta;\] 

(iv) for $\alpha_0<\alpha_1<\aleph_1$ there are 
$\Sigma^1_1(z)$ elementary maps 
\[\tau_{\alpha_0, \alpha_1}: \a_{\alpha_0}\rightarrow 
\a_{\alpha_1},\] 
and these commute, in the sense that for 
$\alpha_0<\alpha_1<\alpha_2$ we have 
\[\tau_{\alpha_0,\alpha_2}=\tau_{\alpha_1, \alpha_2}\circ
\tau_{\alpha_0, \alpha_1}.\] 


\leftskip 0in 

Proof of Claim; 
By induction on $\alpha$. 

Something does actually need to be said about the base case 
of this 
induction, so suppose that 
\[\n\models A^{{\rm u}, z}\] 
and let us assume that 
$\omega_1^{{\rm ck}(\n, z)}=\omega_1^{{\rm ck}(z)}$.  
But then it follows by 
\ref{A7} and the formulation of being unyielding 
that we may find some 
$\m\in\mod$ with 
\[\omega_1^{{\rm ck}(\m, \n,z)}=\omega_1^{{\rm ck}(z)}\] 
and an $\omega_1^{{\rm ck}(\m, \n,z)}$-elementary map 
\[i:\m\rightarrow \n\] 
which is not onto. We then start the proof of the claim with 
$\a_0=\m$ and $\a_1=\n=\b_1$ and $\b_0=i[\m]$. 

For the successor steps of the induction we imagine that we 
have some $\alpha$ and $\beta<\alpha$ 
\[\b_\beta\neq \b_\alpha\] and 
corresponding $\Sigma^1_1(z)$ elementary 
$\tau_{\beta, \alpha}:\a_\beta\rightarrow \a_\alpha$ 
which is not onto. Then since $\tau_{\beta, \alpha}$ is 
$\Sigma^1_1(z)$-elementary we may transfer any relevant 
$\Sigma^1_1(z)$ fact about $\a_\beta$ up to 
$\a_\alpha$. In particular we may find a model $\a$ with 
\[\omega_1^{{\rm ck}(\a_\alpha, \a,z)}=\omega_1^{{\rm ck}(z)}\] 
and an 
$\omega_1^{{\rm ck}(z)}$-elementary map 
\[\tau: \a_\alpha\rightarrow \a\] 
which is not onto. Taking $\a_{\alpha +1}=\a$ and 
$\b_{\alpha +1}$ an appropriate isomorphic copy of 
$\a_{\alpha +1}$ we can continue to a further round. 

For the limit stages of the construction we naturally wish to take 
\[\b_\lambda=\bigcup_{\alpha<\lambda} \b_\alpha\] 
whenever $\lambda$ is a limit, and then we are just left 
with trying to show that we can obtain an appropriate $\a_\lambda.$ 
And this is where \ref{limit} comes to our rescue. 

We find a model  $\a_\infty$ from \ref{limit} to be the 
direct limit of the $\a_{\alpha(n)}$'s for some 
\[\alpha(n)\rightarrow \lambda.\] 
The direct limit construction gives 
\[\tau_{\alpha(n), \infty}: \a_{\alpha(n)}\rightarrow \a_\infty\] 
which commute and are $\Sigma^1_1(z)$ elementary; by composing with 
suitable $\tau_{\alpha, \alpha(n)}$ we may find 
\[\tau_{\alpha, \infty}: \a_{\alpha}\rightarrow \a_\infty\] 
all $\alpha<\lambda$. 

The $\Sigma^1_1(z)$-elementarity 
of these maps ensures that we may find some 
\[\rho:\a_\lambda\cong \a_\infty\] 
with 
\[\omega_1^{{\rm ck}(\a_\lambda,z)}=\omega_1^{{\rm ck}(z)}.\] 
Choosing $\tau_{\alpha, \lambda}=\rho\circ\tau_{\alpha, \infty}$ 
we finish. 
\hfill (Claim$\Box$) 

But then the union 
\[\b_{\aleph_1}=\bigcup_{\alpha<\aleph_1}\b_\alpha\] 
is as required  

 
\end{proof} 


An immediate corollary of this theorem is a result previously proved 
by Keisler and Shelah using very different techniques. They showed  
the property of $\sigma\in\lone$ allowing an uncountable model 
to be absolute between models of set theory, 
and moreover if we restrict ourselves to 
\[\sigma\in \lone\cap V_\alpha\] 
some $\alpha<\omega_1$ then the set of such sentences is 
$\Ubf{\Sigma}^1_1$. 

However I should add to this that it would be excessive to 
claw through the several reflection lemmas above if 
our only goal was to reproduce Keisler-Shelah. Hugh Woodin has in 
any case shown that their theorem allows a short proof using 
iterations of ultrapowers of the Frechet filter at $\omega_1$. 

 
\newpage 

\section{The split in cases} 
\label{split}

We wish to prove a dichotomy theorem for the isomorphism relation on 
countable models of some countably infinitary sentence $\sigma$. After relativizing 
to a real we may assume the existence of  
some $z\in 2^\omega$ and countable language 
${\cal L}$ such that: 

\leftskip 0.5in 

\medskip 

(i) ${\cal L}$ is recursive in $z$; 

(ii) the Scott ranks of models of $\sigma$ are bounded below 
$\omega_1^{{\rm ck}(z)}$; 

(iii) $\sigma\in L_{\omega_1^{{\rm ck}(z)}}[z]$. 

\leftskip 0in 

\medskip 

\noindent The arguments depend not at all on $y$, and thus there is no harm in 
lightening our notation and assuming: 

 
\medskip 
 
\leftskip 0.5in
 
 

(i) ${\cal L}$ is a recursive language;
 
(ii) the Scott ranks of models of $\sigma$ are bounded below
$\omega_1^{{\rm ck}}$;
 
(iii) $\sigma\in L_{\omega_1^{{\rm ck}}}$; 

  
\leftskip 0in 

\medskip 

\noindent and by \ref{polish} we may as well even assume 

\medskip 

\leftskip 0.5in


(iv) Mod$(\sigma)$ is a $\Pi^0_2$ subset of Mod$({\cal L})$; 


\leftskip 0in

\medskip 

\noindent following \ref{(a1)} and \ref{(a2)} we may further insist 
that 

\leftskip 0.5in
\medskip 


(v) each tuple in $\m\in$ Mod$(\sigma)$ has its type 
first order definable 
from a single $a\in \m$; 

(vi) for all $\vec a, b\in \m$, $\m\in$ Mod$(\sigma)$, there are 
infinitely many $c\in \m$ with 
\[\langle \m; \vec a, b\rangle\cong\langle \m; \vec a, c\rangle.\] 

\leftskip 0in 

\medskip 

\no And in the usual way we may assume that there are no function 
symbols to contend with: 

\medskip 

\leftskip 0.5in 

(vii) $\l$ is relational.

\leftskip 0in 

\medskip 

\bigskip 
\bigskip 

\noindent {\bf CASE(I)} There is a fragment $F\in\Lck$ and there 
is $\m\in$ Mod$(\sigma)$ such that 
\[\forall \vec b\in \m\exists \vec a\in \m 
(\langle \m; \vec b\rangle \models A_F(\vec a)).\] 

\bigskip 

In other words, for all $\vec b$ in $\m$ there is some 
other $\vec a$ in $\m$ such that whenever 
\[\langle \m; \vec b\rangle \models A(\vec a)\] we must have 
that $A$ is not $F$-barren. 


\begin{definition} Let $X_F$ be the set of $\m$ as in case 
assumption.
\end{definition} 

Clearly $X_F\in\Sigma^1_1$. 
 
\bigskip
\bigskip

\noindent {\bf CASE(II)} Not case (I). 

Here we need some observations and 
definitions before splitting into 
two further subcases. 

%\begin{definition}  For each fragment $F\in \Lck$ 
%let $B_F$ be the $\Sigma^1_1$ set of 
%$\langle \m; \vec b\rangle$ such that 
%\[\exists \vec a\in \m 
%(\langle \m; \vec b\rangle \models A_F(\vec a)).\] 
%\end{definition} 

By \ref{*} we may 
find a transfinite sequence $\psi_{A_F,\alpha}$ 
such that 
\[\alpha\mapsto \psi_{A_F,\alpha}\] 
is uniformly $\Delta_1$ over admissible sets and the following three 
things are equivalent for all $\m\in\mod$ and $\vec a, \vec b\in\m$: 

\leftskip 0.5in 

(1) $\langle \m;\vec b\rangle\models A_F(\vec a)$; 

(2) $\forall \alpha (\langle \m;\vec b\rangle \models 
\neg \psi_{A_F,\alpha}(\vec a))$; 

(3) $\forall \alpha<\omega_1^{{\rm ck}(\m)} 
(\langle \m;\vec b\rangle \models 
\neg \psi_{A_F,\alpha}(\vec a))$; 

\leftskip 0in 


By case assumption and boundedness we can find a single 
$\gamma_0^F<\omega_1^{{\rm ck}}$ such for all $\m\in$ Mod$(\sigma)$ 
there is $\vec b\in\m$ such that 
\[\langle \m;\vec b\rangle \models\forall \vec a \bigvee_{\alpha<\gamma_0^F}
\psi_{A_F, \alpha}(\vec a).\] 

%Then by \ref{B2} and \ref{B4} 

\begin{lemma} \label{II.1} 
Under the assumptions of case(II) we may find 
for each fragment $F\in\Lck$ 
a corresponding fragment $H\in\Lck$ 
such that for all $\m,\n\in$ {\rm Mod}$(\sigma)$ and 
\[i:\m\rightarrow\n\] 
$H$-elementary map, 
we have every 
\[F{\rm -type}_\n(\vec a)\] 
is realized over $\m$. 
\end{lemma} 

\begin{proof} 
Note that if $H_{\forall \vec x\bigvee_{\alpha<\gamma_0^F}
\psi_{A_F, \alpha}(\vec x)}$ is the fragment generated by the  
formula 
$\forall\vec x \bigvee_{\alpha<\gamma_0^F}
\psi_{A_F, \alpha}(\vec x) $ then we must have that for any 
$H_{\forall \vec x \bigvee_{\alpha<\gamma_0^F}
\psi_{A_F, \alpha}(\vec x)}$-elementary map 
\[i:\m\rightarrow \n\] 
between countable models of $\sigma$ there will be some 
$\vec b\in\m$ such that 
\[\langle \n; i(\vec b)\rangle\models 
\forall \vec x\bigvee_{\alpha<\gamma_0^F}
\psi_{A_F, \alpha}(\vec x);\] 
and thus for every $\vec a\in\n$ we would by 
\ref{B2.a} have some barren $\psi$ such that 
\[\langle \n; i(\vec b)\rangle\models\psi(\vec a).\] 

Now as in the proof of \ref{B4} we may apply \ref{boundedness} 
to find a single fragment $H\supset H_{\forall \vec x
\bigvee_{\alpha<\gamma_0^F}
\psi_{A_F, \alpha}(\vec x)}$ such that for all $\m,\n\models\sigma$, 
all $\vec a\in\n$, 
and all 
\[i:\m\rightarrow \n\] which is $H$-elementary and 
for all $\vec b\in\m$ with  
\[\langle \n; i(\vec b)\rangle\models A_F(\vec a)\] 
we obtain the  
$F$-type$_{\langle \n; i(\vec b)\rangle}
(\vec a)$ appearing in $\langle \m; \vec b\rangle$, and in 
particular 
$F$-type$_{\n}
(\vec a)$ realized over $\m$. 
This $H$ suffices for the lemma. 
\end{proof} 

Note that for any fragment $F$ the set of $H$ satisfying the 
conclusion of \ref{II.1} is uniformly $\Pi^1_1$ in the codes. Thus 
by Spector-Gandy: 



\begin{corollary} 
\label{II.2} 
Under assumptions of case(II), we may find a 
$\Delta^{\Lck}_1$ function 
\[F\mapsto H_F\] 
such that 
for all $\m,\n\in$ {\rm Mod}$(\sigma)$ and
\[i:\m\rightarrow\n\]   
$H$-elementary map,
we have every
\[F{\rm -type}_\n(\vec a)\]
is realized over $\m$.
\end{corollary}


Now we may assign to each $\m\in{\rm Mod}(\sigma)$ and fragment 
$F\in\Lck$ a corresponding 
tree 
\[T^F_\m\subset \m^{<\o}\] 
such that: 

\leftskip 0.5in 

\noindent (i) there is in $\Lck$ a sequence of 
formulas 
$(\varphi_{i\in\o}^F)_{i\in\o}$ in $H_F$, depending on $F$ but not 
on $\m$, such that for each $n\in\o$ and $\vec a\in \m^n$ we have 
\[\m\models \varphi_n^F(\vec a)\] 
if and only if 
\[\vec a\in T^F_\m;\] 

\noindent (ii) a substructure $\n$ of $\m$ is an $H_F$-elementary 
substructure if and only if there is some infinite branch 
\[f\in [T^F_\m]\] with 
\[\n=\{f(n): n\in\omega\}.\] 


\leftskip 0in 

\medskip 

This is just a general fact; it does not depend at all on the specifics 
of our case assumption. 
We can tear apart all the sentences of interest 
and insist that the $(\varphi_{i\in\o}^F)_{i\in\o}$ be chosen 
so as to appropriately Skolemize the formulas appearing in $H_F$. 

However in the setting of our case assumption we must moreover obtain: 

\medskip 

\leftskip 0.5in
 
\noindent (iii) for each $\vec a\in\m$ and $f\in [T_\m^F]$ 
there will exist some $\vec c\in \{f(n):n\in\o\}$ such that 
\[F{\rm -type}_\m(\vec a)= 
F{\rm -type}_\m(\vec c);\] 

\leftskip 0in 

\medskip 

\no this in particular implies the weaker but more useful conclusion that 

\medskip 

\leftskip 0.5in


\noindent (iv) for each $\vec a\in\m$ and $f\in [T_\m^F]$
there will exist some $\vec c\in \{f(n):n\in\o\}$ such that
$F{\rm -type}_\m(\vec a)$ is $H$-definable from $\vec c$. That is to say, 
there is some formula $\psi\in H$ such that 

\leftskip 1in 

\noindent (a) $\m\models \psi(\vec c, \vec a)$; 

\noindent (b) $\m\models \forall \vec b^0, \vec b^1 
(\bigwedge_{\varphi\in F}(\psi(\vec c, \vec b^0)\wedge
\psi(\vec c, \vec b^1)\Rightarrow(\varphi(\vec b^0)\Leftrightarrow 
\varphi(\vec b^1))).$   

\leftskip 0in 


\bigskip 

\no Thus we may define for any $F\in\Lck$, $H\supset H_F$, $\m\in{\rm Mod}(\sigma)$ 
a kind of ranking function 
\[\rho^H_{F, \m}:T^F_\m\times\m^{<\o}\rightarrow \aleph_1\] 
defined by the specification that: 

\leftskip 0.5in 

\noindent $\rho^H_{F, \m}(\vec a, \vec b)=0$ if 
$F{\rm -type}_\m(\vec b)$ is $H$-definable from $\vec a$; 

\noindent $\rho^H_{F, \m}(\vec a, \vec b)=$ sup$\{ \rho^H_{F, \m}
(\vec a^\smallfrown c,\vec b)+1: \vec a^\smallfrown c\in T^F_\m\}$ whenever 
$F{\rm -type}_\m(\vec b)$ is not $H$-definable from $\vec a$. 

\leftskip 0in 

\bigskip 

\noindent{\bf CASE(IIa):} For all fragments 
$F\in \Lck$ there is some fragment 
$H\supset H_F$ in $\Lck$ such that for all $\m\in{\rm Mod}(\sigma)$ there 
is some $\vec a\in\m$ with 
\[{\rm sup}\{\rho^H_{F, \m}(\vec a, \vec b): \vec b\in\m\}<\o.\] 

\bigskip 

\noindent{\bf CASE(IIb):} There is some fragment 
$F\in \Lck$ such that for all $H\supset H_F$ in $\Lck$ there is 
$\m\in{\rm Mod}(\sigma)$ with 
\[{\rm sup}\{\rho^H_{F, \m}(\vec a, \vec b): \vec b\in\m\}\]
infinite for all $\vec a\in\m$. 

\newpage 


\section{Proof for case(I)} 
\label{case(I)} 

Fix the fragment $F$ as in case hypothesis. 
%Let us assume by \ref{(a1)} 
%and \ref{(a2)} that the type of any finite tuple in some $\m\in\mods$ 
%is encoded by the type of some single point and that for all $\vec a, b\in\m$ 
%\[\exists^\infty c\in \m (\langle m; \vec a, b\rangle 
%\cong \langle \m;\vec a, c\rangle).\] 
It will be convenient to work with models of $\sigma$ whose underlying 
set is something other than $\omega$. 

\begin{notation} Let $\Omega$ be the disjoint union of 
$(2^{<\omega})^{<\omega}$ and 
$(2^{<\omega})^{<\omega}\times\omega$. Let Mod$_\Omega(\l)$ be 
the space of $\l$-structures on $\Omega$ equipped with the 
topology of quantifier free formulas. Let $\modss$ be the subspace 
of models of $\sigma$. 
We again have that Sym$(\Omega)$, the collection of permutations of 
$\Omega$, is a Polish group in the topology of pointwise convergence 
and gives rise to the isomorphism relation on Mod$_\Omega(\l)$. 
\end{notation} 

We can continue then by analogy with section \ref{definition}. 

\begin{definition} For $A\subset$ Mod$_\Omega(\l)$ 
a $\Sigma^1_1$ set and 
$f\subset\Omega$ finite, $\m\in$ Mod$_\Omega(\l)$, 
$(a_u)_{u\in f}$ a collection  
elements of $\m$ indexed by the elements of $f$, 
let us write 
\[\m\models A((a_u)_{u\in f})\] 
if there is $\pi\in$ Sym$(\Omega)$ with 
\[\pi(a_u)=u\] 
all $u\in f$ and 
\[\pi\cdot\m\in A.\] 

For  $(a_u)_{u\in f}$ in $\m$ we 
let $\langle \m; (a_u)_{u\in f}\rangle$ 
be the expansion of $\m$ by fresh 
constants $({\bf c}_u)_{u\in f}$ with 
\[\langle \m; (a_u)_{u\in f}\rangle\models {\bf c}_u=a_u\] 
all $u\in f$. Given $f_0, f_1,..., f_n$ finite 
disjoint subsets of $\Omega$ we may naturally 
write 
\[\langle \m; (a_u)_{u\in f_0}, (a_u)_{u\in f_1},...\rangle \] 
in place of 
\[\langle \m; (a_u)_{u\in f_0\cup f_1\cup...}\rangle\] 
and 
\[\m\models A((a_u)_{u\in f_0}, (a_u)_{u\in f_1},..)\] 
in place of 
\[\m\models A((a_u)_{u\in f_0\cup f_1\cup...}).\] 
\end{definition} 

In general it is convenient to extend the model theoretic conventions 
for sequences to our present situation. We may just write 
\[(a_u)_{u\in f}\in\m\] 
to indicate that $(a_u)_{u\in f}$ is an $f$-indexed collection of 
points in $\m$. 


\begin{definition} We write 
\[\langle \m; (a_u)_{u\in f}\rangle\models A_F(b)\] if for all 
$\Sigma^1_1$ sets $A$ with 
\[\langle \m; (a_u)_{u\in f}\rangle\models A(b),\] 
we can find 
\[\n_0, \n_1\in \modss,\]  
\[(b_u)_{u\in f}\in\n_0,\] 
\[d\in\n_1,\]  
\[\tau: \n_0\rightarrow \n_1\] 
$\omega_1^{{\rm ck}(\n_0, \n_1)}$-elementary, with 
\[\langle \n_1; (\tau(b_u))_{u\in f}\rangle \models A(d),\] 
but 
\[F{\rm -type}_{ \langle \n_1; (\tau(b_u))_{u\in f}\rangle}
(d)\notin \{F{\rm -type}_{\langle \n_0; (b_u)_{u\in f}\rangle}(e): 
e\in \n_0\}.\] 
\end{definition} 



Strictly speaking we should introduce a different $A_{F, f}$ for 
each finite subset $f$ of $\Omega$. We do not go to this trouble. 

We should also distinguish these $\Sigma^1_1$ sets 
from their counterparts 
in the space $\mods$. Again we do not go to this trouble. 

\begin{definition} We let $X_F\subset\modss$ be the set of $\m$ such 
that for all $\vec b\in \m$ there is $a\in\m$ with 
\[\langle \m; \vec b\rangle\models A_F(a).\] 
\end{definition} 

Our case assumptions appropriately translated across to the space 
$\modss$ give that $X_F$ is a non-empty set; here we have used that the 
conclusion of \ref{(a1)} is assumed to hold and so we can restrict 
ourselves to $a$ a single point, instead of having to range over all 
sequences $\vec c\in\m$.  
\ref{B3} gives that 
$X_F$ is $\Sigma^1_1$. 

\begin{lemma} 
\label{C1} Let $\n_0,\n_1\in\modss$, 
\[\tau:\n_0\rightarrow\n_1\]  
$\omega_1^{{\rm ck}(\n_0, \n_1)}$-elementary, 
and let $b\in\n_1$ with 
\[F{\rm -type}_{\n_1}(b)\notin \{F{\rm -type}_{\n_0}(c):
c\in \n_0\}.\]

Then for all finite $f\subset\Omega$ and $(a_u)_{u\in f}$ in 
$\n_0$ we have 
\[\langle \n_1; (\tau(a_u))_{u\in f}\rangle \models A_F(b).\] 

\end{lemma} 
\begin{proof} 
Fix  $(a_u)_{u\in f}$ in
$\n_0$. Since 
$F{\rm -type}_{\n_1}(b)\notin \{F{\rm -type}_{\n_0}(c):
e\in \n_0\}$ we have in particular that 
\[F{\rm -type}_{\langle \n_1; (\tau(a_u))_{u\in f}\rangle}
(b)\notin \{F{\rm -type}_{\langle \n_0; (a_u)_{u\in f}\rangle}(c):
c\in \n_0\}.\] 
Thus we necessarily have that for all $A\in\Sigma^1_1$ with 
\[\langle \n_1; (\tau(a_u))_{u\in f}\rangle\models A(b)\] 
we can indeed find a pair of models and an elementary embedding 
(namely: $\langle \n_0; (a_u)_{u\in f}\rangle$, 
$\langle \n_1; (\tau(a_u))_{u\in f}\rangle$, 
$\tau$!) as in the definition of $A_F$ as 
above. 
\end{proof} 

\begin{definition} 
We let $\Q_0$ the set of sequences $\langle A, (a_{\vec s})_{\vec s\in f_0}, 
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...(b_v)_{v\in g_n}\rangle$ 
such that:- 

\leftskip 0.5in 

\no (i) $n\in\o$; each of the $a_{\vec s}$ and 
$b_v$ are in $\Omega$; 

\no (ii) there are $l_0, l_1,...,l_n\in\o$ with each $f_i=2^{l_0}\times 
2^{l_1}\times...
\times 2^{l_n}$ and each $g_i$ a finite subset of $f_i\times\o$; 

\no (iii) $A\in\Sigma^1_1$; 

\no (iv) there is some $\m\in\modss$ with 
\[\m \models A( (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,(b_v)_{v\in g_n});\] 
for all 
$\m\in\modss$
with
\[\m\models A(  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n})\]
we have
\[\m\models X_F;\] 


\no (v) for each $m\leq n$ there is a linear ordering $<^m$ on 
$f_m=2^{l_0}\times 2^{l_1}\times...
\times 2^{l_m}$ such that for all $\vec t\in f_m$ and $\m\in\modss$ 
with 
\[\m\models A(  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n})\] 
we have 
\[\langle \m;  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,(a_{\vec s})_{\vec s\in f_{m-1}},
(b_v)_{v\in g_{m-1}},
(a_{\vec s})_{\vec s<^m \vec t}
\rangle\models A_F(a_{\vec t});\] 

\no (vi) for each $\vec s\neq\vec t\in\bigcup_{m\leq n}f_m$ there is 
some $\psi_{\vec s, \vec t}\in F$ such that 
whenever \[\m\models A( (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n})\]
we have must have 
\[\m\models \psi_{\vec s, \vec t}(a_{\vec s})\wedge 
\neg \psi_{\vec s, \vec t}(a_{\vec t}).\] 

\leftskip 0in 

\end{definition} 

In fact the ordering $<^m$ in (v) can be taken to be the 
lexicographic ordering under some appropriate isomorphism 
of $2^{l_0}\times 2^{l_1}\times...\times 2^{l_m}$ with 
$2^{l_0+l_1+...+l_m}$. There is no need for us to keep count 
of this specific detail and so we ignore it. 

Note that it has been hard wired into our definitions that whenever 
$\vec s\neq \vec t$ and 
\[\langle \m;  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n}\rangle\models A\] 
for any $\Sigma^1_1$ set $A$ then it must be the case that 
\[a_{\vec s}\neq a_{\vec t},\] 
\[a_{\vec s}\neq b_{\vec t},\]
\[a_{\vec s}\neq b_{\vec s},\] 
\[b_{\vec s}\neq b_{\vec t}.\] 


Part (vi) of the definition of $\Q_0$ represents 
a minor redundancy. 
If we were to define $\Q_0^*$ to be the 
set obtained by sequences only satisfying (i)-(v), then 
we would obtain that 
in some sense 
$\Q_0$ is dense in $\Q_0^*$. 


\begin{lemma} 
\label{C2} 
Suppose $\langle A, (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...(b_v)_{v\in g_n}\rangle$ 
satisfies (i)-(v) from the definition of $\Q_0$ above. 
Then we may find a $\Sigma^1_1$ set $\hat{A}\subset A$ 
such that 
\[\langle \hat{A}, (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...
(b_v)_{v\in g_n}\rangle\in \Q_0.\] 
\end{lemma} 

\begin{proof} 
For each $m\leq n$ let $<^m$ be the indicated ordering on $f_m$ as 
in (v) of the definition of $\Q_0$. Let $\m\in\modss$ be such that 
\[\m\models A(  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n}).\] 
Then for each $m\leq n$ and 
$\vec t\in f_m$ we have 
\[\langle \m;  (a_{\vec s})_{\vec s\in f_0},  
(b_v)_{v\in g_0}, ...,(a_{\vec s})_{\vec s<^m \vec t}
\rangle\models A_F(a_{\vec t}),\] 
and thus in particular it is an outright consequence of 
the definition of $A_F$ that for any $\vec s<^m \vec t$ 
\[\m\models\neg\bigwedge_{\psi\in F}(\psi(a_{\vec s})
\Leftrightarrow \psi(a_{\vec t})).\] Thus we may choose 
some $\psi_{\vec s, \vec t}\in F$ with 
\[\m\models \psi_{\vec s, \vec t}(a_{\vec s})\wedge 
\neg \psi_{\vec s, \vec t}(a_{\vec t}).\] 

Then we can define $\hat{A}\subset A$ by the specification 
that for all $\n\in\modss$ 
\[\n\models  \hat{A}(  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n})\]
if and only if 
\[\n\models  A(  (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, ...,
(b_v)_{v\in g_n})\] 
and for all $m\leq n$ and $\vec t\in f_m$ 
\[\n\models \bigwedge_{\vec s<^m \vec t}
\neg\psi_{\vec s, \vec t}(a_{\vec t})\wedge\bigwedge_{\vec s >^m \vec t} 
\psi_{\vec t, \vec s}(a_{\vec t}).\] 
\end{proof} 

\begin{notation} Suppose $l_0, l_1,..., l_n\in \o$ and $f_i=2^{l_0}\times 
2^{l_1}\times...\times 2^{l_i}$. 
Then for each $m\leq n$ we let 
\[f_i^{(m)}=2^{l_0}\times 2^{l_1}\times...\times 2^{l_{m-1}}\times 2^{l_m+1}
\times 2^{l_{m+1}}\times...
\times 2^{l_i}.\] 
(Naturally  when $m>i$ we simply have $f_i^{(m)}=f_i$.) 

For $\vec s\in f_i$ we define $\vec s^{(m, 0)}\in f_i^{(m)}$ by 
\[(\vec s^{(m,0)})_j=(\vec s)_j\] 
for $j\leq i$, $j\neq m$, 
and 
\[(\vec s^{(m,0)})_m=(\vec s)_j^\smallfrown 0;\] 
similarly \[(\vec s^{(m,1)})_j=(\vec s)_j\]
for $j\leq i$, $j\neq m$, 
\[(\vec s^{(m,1)})_m=(\vec s)_j^\smallfrown 1.\]
Thus in particular if $\vec s\in f_i$ and 
$m>i$ then 
\[\vec s^{(m,0)}=\vec s^{(m,1)}=\vec s.\] 
We let 
\[f^{(m, 0)}_i=\{\vec s^{(m, 0)}: \vec s \in f_i\},\] 
\[f^{(m, 1)}_i=\{\vec s^{(m, 1)}: \vec s \in f_i\}.\]

In a similar fashion we extend this to $g_i\subset f_i\times\o$. 
So for any $v=(\vec s, k)\in g_i$ we let 
\[v^{(m,0)}=(\vec s^{(m, 0)}, k),\] 
\[v^{(m,1)}=(\vec s^{(m, 1)}, k).\] 
Then 
\[g_i^{(m, 0)}=\{v^{(m,0)}: v\in g_i\},\] 
\[g_i^{(m, 1)}=\{v^{(m,1)}: v\in g_i\},\]
\[g_i^{(m)}=g_i^{(m, 0)}\cup g_i^{(m, 1)}.\] 
\end{notation} 

The definitions are set up so that given any $g_i\subset \Omega$ 
finite and $m\leq i$ we have 
\[g_i^{(m, 0)}\cap g=g_i^{(m, 1)}\cap g=0.\] 
This along with our assumption that $\modss$ satisfies the 
conclusion of \ref{(a2)} is being used in the next 
lemma; together they keep a leash on  
the sets of the form $(b_v)_{v\in g_i}$. Without these assumptions 
we can move forward only by painfully enumerating when $b_v=b_w$. 

\begin{lemma} 
\label{C3} Let 
\[\langle A, (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...(b_v)_{v\in g_n}\rangle\] 
be in $\Q_0$, where 
each $f_i=2^{l_0}\times 2^{l_1}\times...\times 2^{l_i}$ and 
let $m\leq n$. 

Then there is some 
\[\langle B, (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...,(b_v)_{v\in g_{m-1}}, 
(a_{\vec s})_{\vec s\in f_m^{(m)}},
(b_v)_{v\in g_m^{(m)}}, 
%(a_{\vec s})_{\vec s\in f_{m+1}^{(m)}},...
...(b_v)_{v\in g_n^{(m)}}\rangle\] in 
$\Q_0$ 
such that for all 
\[\m\models B((a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...,(b_v)_{v\in g_{m-1}}, 
(a_{\vec s})_{\vec s\in f_m^{(m)}},
(b_v)_{v\in g_m^{(m)}},
%(a_{\vec s})_{\vec s\in f_{m+1}^{(m)}},...
(b_v)_{v\in g_n^{(m)}})\] 
we have 
\[\m\models A ((a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...,(b_v)_{v\in g_{m-1}},
(a_{\vec s^{(m,0)}})_{\vec s\in f_m},
(b_{v^{(m,0)}})_{v\in g_m},
%(a_{\vec s^{(m,0)}})_{\vec s\in f_{m+1}},...
...(b_{v^{(m,0)}})_{v\in g_n})\] 
and 
\[\m\models A ((a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...,(b_v)_{v\in g_{m-1}},
(a_{\vec s^{(m,1)}})_{\vec s\in f_m}, 
(b_{v^{(m,1)}})_{v\in g_m},
%(a_{\vec s^{(m,1)}})_{\vec s\in f_{m+1}},... 
...(b_{v^{(m,1)}})_{v\in g_n})\]
\end{lemma} 

\begin{proof} For notational simplicity let us take the case that 
$n=1$, $l_0=0$, $l_1=1$, $m=0$, $g_0=2^0\times \{5, 6\}=
\{0\}\times\{5,6\},$ 
$g_1=0$. Thus $f_0$ contains only 
the empty set and $f_1$ is the set of size  
two whose only elements are 
$\langle 0, \langle 0\rangle \rangle $ 
and $\langle 0, \langle 1\rangle \rangle$; 
$f_0^{(0, 0)}$ contains $\langle 0\rangle$ and  
$f_1^{(0,0)}$ is the set 
whose elements are $\langle \langle 0\rangle, 
\langle 0\rangle \rangle $    
and $\langle\langle  0\rangle , \langle 1\rangle \rangle$; 
$f_0^{(0, 1)}$ contains $\langle 0\rangle$ and                         
$f_1^{(0,1)}$ contains $\langle \langle 1\rangle, 
\langle 0\rangle \rangle $
and 
$\langle \langle 1\rangle, \langle 1\rangle \rangle$. 

Let us assume that 
\[\langle 0, \langle 0\rangle \rangle <^1 \langle 0, \langle 1\rangle \rangle\] 
describes the linear ordering $<^1$ on $2^0\times 2^1=f_1$. 

Now from clause (v) of the definition of $\Q_0$ we may find 
$\n_0, \n_1\in\modss$ and $\omega_1^{{\rm ck}(\n_0, \n_1)}$-elementary 
\[\tau_0: \n_0\rightarrow \n_1\] 
and 
\[a^0_{\langle 0\rangle}, 
b^0_{\langle \langle 0\rangle , \langle 5\rangle \rangle},
b^0_{\langle \langle 0\rangle , \langle 6\rangle \rangle},
a^0_{\langle \langle 0\rangle, \langle 0\rangle \rangle}, 
a^0_{\langle \langle 0\rangle , \langle 1\rangle \rangle}\in\n_0,\] 
\[a^1_{\langle 1\rangle}, 
b^1_{\langle \langle 1\rangle , \langle 5\rangle \rangle},
b^1_{\langle \langle 1\rangle , \langle 6\rangle \rangle}, 
a^1_{\langle \langle 1\rangle , \langle 0\rangle \rangle},
a^1_{\langle \langle 1\rangle , \langle 1\rangle \rangle}\in\n_1,\] 
\[\n_0\models A((a_{\vec s^{(0,0)}}^0)_{\vec s\in f_0}, (b_{v^{(0,0)}}^0)_{v\in g_0}, 
(a_{\vec s^{(0,0)}}^0)_{\vec s\in f_1}),\] 
\[\n_1\models A((a_{\vec s^{(0,1)}}^1)_{\vec s\in f_0}, (b_{v^{(0,1)}}^1)_{v\in g_0},
(a_{\vec s^{(0,1)}}^1)_{\vec s\in f_1}),\] 
\[F{\rm -type}_{\n_1}(a^1_{\langle 1\rangle})\notin\{
F{\rm -type}_{\n_0}(c): c\in \n_0\}\]
and therefore by \ref{C1} 
\[\langle \n_1; \tau_0(a^0_{\langle 0\rangle})\rangle \models 
A_F(a^1_{\langle 1\rangle}).\] 
We use the assumption that the conclusion of \ref{(a2)} holds to 
obtain 
$b^1_{\langle \langle 1\rangle , \langle 5\rangle \rangle},
b^1_{\langle \langle 1\rangle , \langle 6\rangle \rangle}$ 
distinct to 
$\tau_0(b^0_{\langle \langle 0\rangle , \langle 5\rangle \rangle}),
\tau_0(b^0_{\langle \langle 0\rangle , \langle 6\rangle \rangle})$. 

%\newpage 

%\begin{figure}

\begin{picture}(0,0)%
{\includegraphics{nC3zero.pstex}}%
%\caption{In $\n_1$ $a^1_{\langle 1\rangle}$ realizes a new $F$-type.} 
\end{picture}%
\setlength{\unitlength}{0.00083300in}%
\begin{picture}(5861,5559)(365,-4901) 
\put(5401,239){\makebox(0,0)[lb]{$\n_1$}}
\put(4726,-1411){\makebox(0,0)[lb]{{\rm New}}}
\put(4126,239){\makebox(0,0)[lb]{$a^1_{\langle 0\rangle}$}}
\put(3901,-286){\makebox(0,0)[lb]{$a^1_{\langle \langle 0\rangle,
\langle 0\rangle \rangle}$}}
\put(3676,-811){\makebox(0,0)[lb]{$a^1_{\langle \langle 0\rangle,
\langle 1\rangle \rangle}$}}
\put(1051,-661){\makebox(0,0)[lb]{$a^0_{\langle 0\rangle}$}}
\put(751,-1186){\makebox(0,0)[lb]{$a^0_{\langle \langle 0\rangle, \langle 0\rangle \rangle}$}}
\put(526,-1861){\makebox(0,0)[lb]{ $a^0_{\langle \langle 0\rangle, \langle 1\rangle \rangle}$}}
\put(751,-3286){\makebox(0,0)[lb]{$b^0_{\langle \langle 0\rangle, \langle 5\rangle \rangle}$}}
\put(976,-4036){\makebox(0,0)[lb]{$b^0_{\langle \langle 0\rangle, \langle 6\rangle \rangle}$}}
\put(1426, 14){\makebox(0,0)[lb]{$\n_0$}}
\put(4126,-2011){\makebox(0,0)[lb]{$a^1_{\langle 1\rangle}$}}
\put(3976,-2536){\makebox(0,0)[lb]{$a^1_{\langle \langle 1\rangle,
\langle 0\rangle \rangle}$}}
\put(4051,-3361){\makebox(0,0)[lb]{$a^1_{\langle \langle 1\rangle,
\langle 1\rangle \rangle}$}}
\put(6226,-136){\makebox(0,0)[lb]{$a^1_{\langle 0 \rangle}=
\tau_0(a^0_{\langle 0\rangle})$}}
\put(6226,-1186){\makebox(0,0)[lb]{$a^1_{\langle\langle 0\rangle,
\langle 0\rangle \rangle}=
\tau_0(a^0_{\langle\langle 0\rangle, \langle 0\rangle\rangle})$}}
\put(6226,-2386){\makebox(0,0)[lb]{ $a^1_{\langle\langle 0\rangle,
\langle 1\rangle \rangle}=
\tau_0(a^0_{\langle\langle 0\rangle, \langle 1\rangle\rangle})$}}
\put(2626,164){\makebox(0,0)[lb]{$\tau_0$}} 
\end{picture}







%\end{figure}



So far the only properties mentioned for the pair $(\n_0, \n_1)$ is 
that it falls inside finitely many $\Sigma^1_1$ sets. Thus we 
may assume 
from \ref{A7} 
\[\omega_1^{{\rm ck}(\n_0, \n_1)}=\omega_1^{{\rm ck}}.\] 
The elementarity of the map $\tau_0$ is 
sufficient by \ref{**} to give 
\[\n_1\models A((\tau_0(a_{\vec s^{(0,0)}}^0))_{\vec s\in f_0}, 
(\tau_0(b_{v^{(0,0)}}^0))_{v\in g_0},
(\tau_0(a_{\vec s^{(0,0)}}^0))_{\vec s\in f_1}),\] 
and hence 
\[\langle \n_1; (\tau_0(a^0_{\vec s^{(0, 0)}}))_{\vec s\in f_0}, 
(\tau_0(b^0_{v^{(0,0)}})_{v\in g_0})\rangle \models A_F
(\tau_0(a^0_{\langle \langle 0\rangle, \langle 0\rangle \rangle}))\] 
by clause (v) of the definition of $\Q_0$. 

By \ref{A7} and \ref{B6} we may find 
$\n_2\in\modss$ with 
\[\omega_1^{{\rm ck}(\n_0, \n_1, \n_2)}=
\omega_1^{{\rm ck}(\n_0, \n_1)}=
\omega_1^{{\rm ck}}\] 
and $\omega_1^{{\rm ck}}$-elementary 
\[\tau_1: \n_1\rightarrow \n_2\]
and
\[a^2_{\langle \langle 0\rangle , \langle 0\rangle \rangle},
a^2_{\langle \langle 0\rangle , \langle 1\rangle \rangle}\in\n_2,\] 
with 
\[\n_2\models A((\tau_1\circ \tau_0(a_{\vec s^{(0,0)}}^0))_{\vec s\in f_0}, 
(\tau_1\circ \tau_0(b_{v^{(0,0)}}^0))_{v\in g_0},
(a_{\vec s^{(0,0)}}^2)_{\vec s\in f_1}),\] 
and 
\[F{\rm -type}_{\n_2}(a^2_{\langle \langle 0\rangle, 
\langle 0\rangle \rangle})\notin
\{F{\rm -type}_{\n_1}(c): c\in \n_1\},\] 
and therefore in particular  
\[\langle \n_2; (\tau_1\circ \tau_0
(a^0_{\langle 0\rangle}))_{ \{\langle 0\rangle\} }, 
(\tau_1(a^1_{\langle 
1\rangle}))_{ \{\langle 1\rangle\} }, 
(\tau_1\circ\tau_0(b_{v^{(0,0) } }^0))_{v^{(0, 0)}\in g_0^{(0, 0)}}, 
(\tau_1(b_{v^{(0,1)}}^1))_{ v^{(0,1)}\in g_0^{(0,1)} } \rangle \models
A_F(a^2_{\langle \langle 0\rangle , \langle 0\rangle \rangle}).\]
 


%\begin{figure}

\begin{picture}(0,0)%
{\includegraphics{C3one.pstex}}%
\end{picture}%
\setlength{\unitlength}{0.00083300in}%  
\begin{picture}(4558,4825)(2602,-4853)
\put(6226,-736){\makebox(0,0)[lb]{$a^2_{\langle 0\rangle}$}}
\put(6301,-3061){\makebox(0,0)[lb]{$a^2_{\langle 1\rangle}$ }}
\put(6301,-3586){\makebox(0,0)[lb]{$a^2_{\langle \langle 1\rangle, \langle 0\rangle\rangle}$}}
\put(6100,-4111){\makebox(0,0)[lb]{$a^2_{\langle \langle 1\rangle, \langle 1\rangle\rangle}$}}
\put(5851,-1861){\makebox(0,0)[lb]{$a^2_{\langle \langle 0\rangle, \langle 0\rangle\rangle}$}}
\put(6301,-136){\makebox(0,0)[lb]{$\n_2$}}
\put(3376,-436){\makebox(0,0)[lb]{$\n_1$}}
\put(3076,-1111){\makebox(0,0)[lb]{$a^1_{\langle 0\rangle}$}}
\put(2926,-1711){\makebox(0,0)[lb]{$a^1_{\langle \langle 0\rangle, \langle 0\rangle\rangle}$}}
\put(2851,-2236){\makebox(0,0)[lb]{$a^1_{\langle \langle 0\rangle, \langle 1\rangle\rangle}$}}
\put(5776,-2461){\makebox(0,0)[lb]{$a^2_{\langle \langle 0\rangle, \langle 1\rangle\rangle}$}}
\put(5926,-1436){\makebox(0,0)[lb]{{\rm New}}}
\put(3076,-4036){\makebox(0,0)[lb]{$a^1_{\langle \langle 1\rangle, \langle 1\rangle\rangle}$}}
\put(3001,-3436){\makebox(0,0)[lb]{$a^1_{\langle \langle 1\rangle, \langle 0\rangle\rangle}$}}
\put(3151,-2836){\makebox(0,0)[lb]{$a^1_{\langle 1\rangle}$}}
\put(4651,-661){\makebox(0,0)[lb]{$\tau_1$}} 
\end{picture}



%\caption{We build models $\n_1$ and $\n_2$ with 
%$\omega_1^{\rm ck}$-elementary embeddings. $a^1_{\langle 1\rangle}$ realizes 
%an $F$-type not appearing in 
%$\n_0$. $a^2_{\langle \langle 0\rangle, \langle 0\rangle\rangle}$ realizes an 
%$F$-type not appearing over $\n_1$}



%\end{figure}

We can repeat and find $\n_3$, again with 
\[\omega_1^{{\rm ck}(\n_0, \n_1, \n_2, \n_3)}=\omega_1^{\rm ck},\]  
and some $a^3_{\langle \langle 0\rangle, \langle 1\rangle \rangle} \in \n_3,$ 
with 
\[\n_3\models A((\tau_2\circ\tau_1\circ \tau_0(a_{\vec s^{(0,0)}}^0))_{\vec s\in f_0},
(\tau_2\circ\tau_1\circ \tau_0(b_{v^{(0,0)}}^0))_{v\in g_0},
(\tau_2(a^2_{\langle \langle 0\rangle ,
\langle 0\rangle \rangle}))_{\{\langle \langle 0\rangle , \langle 0\rangle \rangle\} }, 
(a^3_{\langle \langle 0\rangle, \langle 1\rangle \rangle})_{ 
\{\langle \langle 0\rangle, \langle 1\rangle \rangle\}}),\] 
\[F{\rm -type}_{\n_3}(a^3_{\langle \langle 0\rangle , \langle 1\rangle 
\rangle})\not\in\{
F{\rm -type}_{\n_2}(c): c\in \n_0\}\] 
and thus 
%\[\langle \n_3; (\tau_2\circ\tau_1\circ \tau_0
%(a^0_{\langle 0\rangle}))_{\{\langle 0\rangle\}},
%(\tau_2\circ\tau_1
%(a^1_{\langle 1\rangle}))_{\{\langle 1\rangle\}},
%(\tau_2\circ\tau_1\circ\tau_0(b_{v^{(0,0)}}^0))_{v^{(0,0)}\in g_0^{(0,0)}},
%(\tau_2\circ\tau_1(b_{v^{(0,1)}}^1))_{v^{(0,1)}\in g_0^{(0,1)}},
%(\tau_2(a^2_{\langle \langle 0\rangle , 
%\langle 0\rangle \rangle})_{\{\langle \langle 0\rangle , \langle 0\rangle \rangle\} }
%\rangle \models
%A_F(a^3_{\langle \langle 0\rangle, \langle 1\rangle \rangle}).\] 
\[\langle \n_3; (\tau_2\circ\tau_1\circ \tau_0
(a^0_{\langle 0\rangle}))_{\{\langle 0\rangle\}},
\cdots, 
(\tau_2(a^2_{\langle \langle 0\rangle ,
\langle 0\rangle \rangle}))_{\{\langle \langle 0\rangle , \langle 0\rangle \rangle\} }
\rangle \models
A_F(a^3_{\langle \langle 0\rangle, \langle 1\rangle \rangle}).\]



%\begin{figure}

\begin{picture}(0,0)%
{\includegraphics{C3two.pstex}}%
\end{picture}%
\setlength{\unitlength}{0.00083300in}%
\begin{picture}(5492,5715)(1267,-6418)
\put(1726,-3511){\makebox(0,0)[lb]{$a^2_{\langle \langle 0\rangle, \langle 0\rangle\rangle}$}}
\put(1726,-4111){\makebox(0,0)[lb]{$a^2_{\langle \langle 0\rangle, \langle 1\rangle\rangle}$}}
\put(1801,-2761){\makebox(0,0)[lb]{$a^2_{\langle 0\rangle}$}}
\put(2026,-1786){\makebox(0,0)[lb]{$\n_2$}}
\put(1501,-4861){\makebox(0,0)[lb]{$a^2_{\langle 1\rangle}$ }}
\put(1576,-5386){\makebox(0,0)[lb]{ $a^2_{\langle \langle 1\rangle, \langle 0\rangle\rangle}$ }}
\put(1876,-6061){\makebox(0,0)[lb]{ $a^2_{\langle \langle 1\rangle, \langle 1\rangle\rangle}$}}
\put(5851,-1786){\makebox(0,0)[lb]{ $a^3_{\langle 0\rangle}$}}
\put(5851,-2311){\makebox(0,0)[lb]{$a^3_{\langle \langle 0\rangle, \langle 0\rangle\rangle}$}}
\put(5701,-2986){\makebox(0,0)[lb]{ $a^3_{\langle \langle 0\rangle, \langle 1\rangle\rangle}$}}
\put(5776,-3811){\makebox(0,0)[lb]{ $a^3_{\langle 1\rangle}$}}
\put(5776,-4186){\makebox(0,0)[lb]{$a^3_{\langle \langle 1\rangle, \langle 0\rangle\rangle}$}}
\put(5776,-4636){\makebox(0,0)[lb]{   $a^3_{\langle \langle 1\rangle, \langle 1\rangle\rangle}$}}
\put(5851,-811){\makebox(0,0)[lb]{$\n_3$}}
\put(6076,-3361){\makebox(0,0)[lb]{${\rm New}$}}
\end{picture}


%\caption{A new type with $a^3_{\langle \langle 0\rangle, \langle 1\rangle}$ appears in 
%$\n_3$ for the first time.} 

%\end{figure}



Now let us introduce the notations   
\[\tau_{0, 3}=\tau_{2}\circ\tau_1\circ\tau_0:\n_0\rightarrow \n_3,\] 
\[\tau_{1, 3}=\tau_{2}\circ\tau_1:\n_1\rightarrow \n_3,\] 
\[\tau_{2, 3}=\tau_2:\n_2\rightarrow \n_3.\]
We can then go on and let 
\[b^3_{v^{(0,0)}}=\tau_2\circ\tau_1\circ\tau_0(b_{v^{(0,0)}}^0)\] 
for 
$v^{(0,0)}\in g_0^{(0,0)},$ 
\[b_{v^{(0,1)}}^3=\tau_2\circ\tau_1(b_{v^{(0,1)}}^1)\] 
for $v^{(0,1)}\in g_0^{(0,1)},$
\[a^3_{\langle 0\rangle}=\tau_{0, 3}(a^0_{\langle 0\rangle} ).\] 
\[a^3_{\langle \langle 0\rangle, \langle 0\rangle \rangle} 
=\tau_{2, 3}(a^2_{\langle \langle 0\rangle, \langle 0\rangle \rangle}),\] 
\[a^3_{\langle \langle 1\rangle, \langle 0\rangle \rangle}
=\tau_{1, 3}(a^1_{\langle \langle 1\rangle, \langle 0\rangle \rangle}),\] 
\[a^3_{\langle \langle 1\rangle, \langle 1\rangle \rangle}
=\tau_{1, 3}(a^1_{\langle \langle 1\rangle, \langle 1\rangle \rangle}),\]
\[a^3_{\langle 1 \rangle}
=\tau_{1, 3}(a^1_{\langle 1\rangle}).\]

We have that each $\tau_{i, j}$ is  
$\omega_1^{{\rm ck}(\n_i, \n_j)}$-elementary, 
and hence respects $\Sigma^1_1$ truths in the sense indicated by 
\ref{**}.  
Thus we have all the following in $\n_3$:- 

\leftskip 0.5in 

\no (a) \[\n_3\models A((a_{\vec s^{(0,0)}}^3)_{\vec s\in f_0}, 
(b_{v^{(0,0)}}^3)_{v\in g_0},
(a_{\vec s^{(0,0)}}^3)_{\vec s\in f_1});\]

\no (b) \[\langle \n_3; a^3_{\langle 0\rangle}\rangle \models
A_F(a^3_{\langle 1\rangle});\] 

%\no (c) \[\langle \n_3; (a_{\vec s^{(0, 0)}})_{\vec s\in f_0},
%(b_{v^{(0,0)}}^3)_{v\in g_0}\rangle \models A_F
%(a^3_{\langle \langle 0\rangle, \langle 0\rangle \rangle});\] 

\no (c) \[\langle \n_3; 
(a^3_{\langle 0\rangle})_{\{\langle 0\rangle\}},
(a^3_{\langle 1\rangle})_{\{\langle 1\rangle\}},
(b_{v}^3)_{v\in g_0^{(0)}} 
\rangle \models
A_F(a^3_{\langle \langle 0\rangle , \langle 0\rangle \rangle});\]

\no (e) and by one last application of \ref{C1}, 
\[\langle \n_3; (a^3_{\langle 0\rangle})_{\{\langle 0\rangle\}}, 
(a^3_{\langle 1\rangle})_{\{\langle 1\rangle\}},
(b_{v}^3)_{v\in g_0^{(0)}}, 
(a^3_{\langle \langle 0\rangle , 
\langle 0\rangle \rangle})_{\{\langle \langle 0\rangle , 
\langle 0\rangle \rangle\}}\rangle\models A_F(a^3_{\langle \langle 0\rangle , 
\langle 1\rangle \rangle}).\] 

\leftskip 0in 


Now holding onto $a^3_{\langle 0\rangle}$, 
$a^3_{\langle 1\rangle}$, 
$(b_{v^{(0,0)}}^3)_{v^{(0,0)}\in g_0^{(0,0)}}$, 
$(b_{v^{(0,1)}}^3))_{v^{(0,1)}\in g_0^{(0,1)}}$, 
$a^3_{\langle \langle 0\rangle}$, 
$a^3_{\langle \langle 0\rangle ,
\langle 1\rangle \rangle}$, we can work on $a^3_{\langle 1\rangle}$ 
and obtain in perfect analogy to the construction of $\n_1$ 
given $\n_0$ above some $\omega_1^{{\rm ck}}$-elementary map 
\[\tau_3:\n_3\rightarrow \n_4\] 
and some $a^4_{\langle \langle 1\rangle, \langle 0\rangle\rangle },
a^4_{\langle \langle 1\rangle, \langle 1\rangle\rangle } \in \n_4$ with 
\[\n_4\models A((\tau_3(a_{\vec s^{(0,1)}}^4))_{\vec s\in f_0},
(\tau_3(b_{v^{(0,1)}}^4))_{v\in g_0},
(a_{\vec s^{(0,1)}}^4)_{\vec s\in f_1}),\]
\[F{\rm -type}_{\n_4}(a^4_{\langle \langle 1\rangle,
\langle 0\rangle \rangle})\not\in\{
F{\rm -type}_{\n_3}(c): c\in \n_3\}.\] 



Then 
we go again to obtain 
$\n_5$, 
\[\tau_4:\n_4\rightarrow \n_5,\] 
\[\n_2\models A((\tau_4\circ \tau_3(a_{\vec s^{(0,1)}}^0))_{\vec s\in f_0},
(\tau_4\circ \tau_3(b_{v^{(0,1)}}^3))_{v\in g_0},
(\tau_4(a_{\langle \langle 1\rangle,\langle 0\rangle 
\rangle }^4))_{\{\langle \langle 1\rangle,\langle 0\rangle \rangle \}}),
(a_{\langle \langle 1\rangle,\langle 1\rangle 
\rangle }^5)_{\{\langle \langle 1\rangle,\langle 1\rangle \rangle \}}),\] 
\[F{\rm -type}_{\n_5}(a^5_{\langle \langle 1\rangle,
\langle 1\rangle \rangle})\not\in\{   
F{\rm -type}_{\n_4}(c): c\in \n_4\}.\] 

We may again obtain that $\tau_4$ and $\tau_5$ preserve the 
satisfaction with respect to $\Sigma^1_1$ formulas. 

Let 
\[\tau_{3, 5}=\tau_{4}\circ\tau_3:\n_3\rightarrow \n_5.\]
Again 
\[b^5_{v}=\tau_{3, 5}(b_{v}^3),\]
for $v\in g_0^{(0)}$. 
And again 
\[a^5_{\langle \langle 1\rangle,\langle 0\rangle \rangle }=
\tau_4(a^5_{\langle \langle 1\rangle,\langle 0\rangle \rangle}),\]  
\[a^5_{\langle 0\rangle}=\tau_{3, 5}(a^3_0),\]
\[a^5_{\langle \langle 0\rangle, \langle 0\rangle \rangle}
=\tau_{3,5 }(a^3_{\langle \langle 0\rangle, \langle 0\rangle \rangle}),\]
\[a^5_{\langle \langle 1\rangle, \langle 0\rangle \rangle}
=\tau_{3, 5}(a^3_{\langle \langle 1\rangle, \langle 0\rangle \rangle}),\]
\[a^5_{\langle \langle 1\rangle, \langle 1\rangle \rangle}
=\tau_{3, 5}(a^3_{\langle \langle 1\rangle, \langle 1\rangle \rangle}),\]
\[a^5_{\langle 1 \rangle}
=\tau_{3, 5}(a^3_{\langle 1\rangle}).\] 

By the preservation of the relevant $\Sigma^1_1$ formulas we 
have 


\leftskip 0.5in

\no (a') \[\n_5\models A((a_{\vec s^{(0,0)}}^5)_{\vec s\in f_0},  
(b_{v^{(0,0)}}^5)_{v\in g_0},
(a_{\vec s^{(0,0)}}^5)_{\vec s\in f_1});\]

\no (b') \[\langle \n_5; a^5_{\langle 0\rangle}\rangle \models
A_F(a^5_{\langle 1\rangle});\]

%\no (c') \[\langle \n_5; (a_{\vec s^{(0, 0)}}^5)_{\vec s\in f_0},
%(b_{v^{(0,0)}}^5)_{v\in g_0}\rangle \models A_F
%(a^5_{\langle \langle 0\rangle, \langle 0\rangle \rangle});\]

\no (c') \[\langle \n_5;
(a^5_{\langle 0\rangle})_{\{\langle 0\rangle\}},
(a^5_{\langle 1\rangle})_{\{\langle 1\rangle\}},
(b_{v}^5)_{v\in g_0^{(0)}} 
\rangle \models
A_F(a^5_{\langle \langle 0\rangle , \langle 0\rangle \rangle});\]

\no (d') 
\[\langle \n_5; (a^5_{\langle 0\rangle})_{\{\langle 0\rangle\}},
(a^5_{\langle 1\rangle})_{\{\langle 1\rangle\}},
(b_{v}^5)_{v\in g_0^{(0)}}, 
(a^5_{\langle \langle 0\rangle ,
\langle 0\rangle \rangle})_{\{\langle \langle 0\rangle ,
\langle 0\rangle \rangle\}}\rangle\models A_F(a^5_{\langle \langle 0\rangle ,
\langle 1\rangle \rangle});\]

\no (e') 
\[\langle \n_5; (a^5_{\langle 0\rangle})_{\{\langle 0\rangle\}},
(a^5_{\langle 1\rangle})_{\{\langle 1\rangle\}},
(b_{v}^5)_{v\in g_0^{(0)}}, 
...,(a^5_{\langle \langle 0\rangle ,
\langle 1\rangle \rangle})_{\{\langle \langle 0\rangle ,
\langle 1\rangle \rangle\}}
\rangle\models 
A_F(a^5_{\langle \langle 1\rangle,\langle 0\rangle\rangle}) ;\]

\no (g') 
\[\langle \n_5; (a^5_{\langle 0\rangle})_{\{\langle 0\rangle\}},
(a^5_{\langle 1\rangle})_{\{\langle 1\rangle\}},...
(a^5_{\langle \langle 1\rangle,\langle 
0\rangle\rangle})_{ \{\langle \langle 1\rangle,\langle 
0\rangle\rangle\} }
\rangle 
\models A_F(a^5_{\langle \langle 1\rangle,\langle 1\rangle\rangle}).\] 



\leftskip 0in



Finally with $\n_5$ and the various points indicated above in place, we can 
return to the task of ``splitting" the indicated sequence in $\Q_0$. 
We can let 
\[\langle 0\rangle <^0 \langle 1\rangle\] 
define the ordering on $2^1$ and 
\[ \langle \langle 0\rangle,\langle 0\rangle\rangle <^1 
\langle \langle 0\rangle,\langle 1\rangle\rangle <^1
\langle \langle 1\rangle,\langle 0\rangle\rangle<^1
\langle \langle 1\rangle,\langle 1\rangle\rangle\] 
define the ordering on $2^1\times 2^1$. Taking $B$ to be 
any $\Sigma^1_1$ set describing enough about $\n_5$ 
and applying \ref{C2} we finish. 




\end{proof} 

\begin{definition} For $\vec s\in f_i=2^{l_0}\times 2^{l_1}\times...
\times 2^{l_i}$ and $\vec t\in2^{k_0}\times 2^{k_1}\times...
\times 2^{k_j}$ some $j\geq i$, we define 
\[\vec s * \vec t \in 2^{l_0+k_0}\times 2^{l_1+k_1}\times...
\times 2^{l_i+k_i}\] 
by the specification that at each $m\leq i$ 
\[(\vec s * \vec t)_m=(\vec s)_m^\smallfrown (\vec t)_m,\]
the concatenation of the sequences $(\vec s)_m$ and 
$(\vec t)_m$. 
For 
\[v=(\vec s, k)\in f_i\times \o,\] we let 
\[v*\vec t=(\vec s * \vec t, k).\] 
\end{definition} 

\begin{definition} For elements in $\Q_0$ 
\[p=\langle A, (a_{\vec s})_{\vec s\in f_0},
(b_v)_{v\in g_0}, (a_{\vec s})_{\vec s\in f_1},...(b_v)_{v\in g_n}\rangle\] 
and 
\[\bar{p}=\langle \bar{A}, (\bar{a}_{\vec s})_{\vec s\in \bar{f}_0},
(\bar{b}_v)_{v\in \bar{g}_0}, (\bar{a}_{\vec s})_{\vec s\in \bar{f}_1},...
(\bar{b}_v)_{v\in \bar{g}_{\bar{n}}}\rangle\] 
we set 
$\bar{p}\leq {p}$ if the following all take place:- 

\leftskip 0.5in 

\no (i) $n\leq \bar{n}$; 

\no (ii) there are $l_0,l_1,..., l_n$, $k_0