



% LaTeX Article Template - customizing header and footer
 \documentclass{article}
 

\usepackage{amssymb}  
 
 
\def\no{\noindent} 
\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\N{{\Bbb N}}
\def\R{{\Bbb R}}
\def\Q{{\Bbb Q}}
\def\l{{\cal L}}
\def\n{{\cal N}}
\def\m{{\cal M}}
\def\Z{{\Bbb Z}}

\begin{document} 

\title{Course at Notre Dame}         % 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 

\centerline {\huge {\bf Overview}}

\bigskip 

\noindent {\bf Main Goal:} Survey some of the recent work 
on Borel and $\Ubf{\Sigma}^1_1$ equivalence relations We will 
specifically consider the $\Ubf{\Sigma}^1_1$ equivalence relation 
which arises as the isomorphism relation on a class of 
countable structures. 

\bigskip 

\no {\bf Definition} A topological space is Polish if 
it is separable\footnote{I.e. there is a countable dense 
subset} and it allows a complete metric. 

\bigskip 

\no {Examples} 1. ${\Bbb R}, {\Bbb C}$ in their 
usual topologies. 

2. Any countable ordinal in the order topology, 
where the basic open sets are $\{\beta: 
\gamma_1<\beta< \gamma_2\}$. (This requires some 
proof of course. One way to do this is to show by 
transfinite induction on $\alpha<\omega_1$ that for 
any $a< b\in\R\cup\{+\infty\}$ we can find a 
closed homeomorphic 
copy of $\alpha$ in  
$[a, b)$ if $\alpha$ is a limit 
ordinal or in $[a, b]$ if $\alpha$ is a successor.) 

3. ${\Bbb N}^{\Bbb N}=\{f:\N\rightarrow \N\}$. Here we 
can take as our complete metric 
\[d(f, g)=2^{-\Delta(f,g)}\] 
where $\Delta(f, g)$ is the least $n$ at which 
$f(n)\neq g(n)$. 

\smallskip 

Actually for us some of the most important examples 
of Polish spaces will arise from model theory. 

\smallskip 

4. Let $\l$ be some countable language and let Mod$(\l)$ be 
the space of $\l$-structures on $\N$ with the topology whose 
basic open sets are all those of the form 
\[\{\m| \m\models \varphi(n_1, n_2, .., n_k)\}\] 
for $k, n_1, ..., n_k\in\N$ and $\varphi$ a quantifier-free 
formula. 

So as a simple case of this let us say that $\l=\{U, R\}$ 
where $U$ is a unary function and $R$ is a binary relation. 
Then we can associate to any $\m\in$ Mod$(\l)$ the 
pair 
\[(U^\m, \chi_{(R^\m)})\in \N^\N\times \{0, 1\}^\N,\] 
where $U^\m$ is $\m$'s interpretation of the unary function 
symbol and $\chi_{(R^\m)}$ is the characteristic 
function of the binary relation from the point of 
view of $\m$. 

We obtain as in example 3 that  
$\N^\N\times \{0, 1\}^\N$ is Polish\footnote{For instance, 
$d((f_1, f_2), (g_1, g_2))=2^{-\Delta(f_1,g_1)}+2^{-\Delta(f_2,g_2)}$.}. 
And our association 
\[\m\mapsto (U^\m, \chi_{(R^\m)})\] 
is a homeomorphism. 

5. Actually, as we will see later, the topology in which we 
take as basic open sets those of the form 
\[\{\m| \m\models \varphi(n_1, n_2, .., n_k)\}\]       
$\varphi$ a {\it first order 
formula} gives rise to a Polish topology. Richer than the first, 
but obviously closely connected. 

6. More generally, if $F\subset{\l    }_{\omega_1, \omega}$ 
is any countable ``fragment''\footnote{Again, the definition of 
${\l    }_{\omega_1, \omega}$ and ``fragment'' will be given 
in a couple of weeks.} then the topology generated by sets of the 
form 
\[\{\m| \m\models \varphi(n_1, n_2, .., n_k)\}\]       
for $\varphi\in F$ is Polish. 

\bigskip 

\no{\bf Definition} A subset of a Polish space is {\it Borel} 
if it can be generated from the open sets by the operations of 
complementation, countable union, and countable intersection. 
A function 
\[f: X\rightarrow Y\] 
is {\it Borel} if $f^{-1}[B]$ is Borel for any Borel 
$B\subset Y$. (Equivalently we simply have required that the 
pullbacks of open sets along $f$ are all Borel; the point is that 
the operations of complementation, intersection, and union behave 
nicely with respect to pullback.) 

An equivalence relation $E$ on a Polish space $X$ is {\it Borel} 
if it is Borel as a subset of $X\times X$ in the product topology. 

\bigskip 

With respect to this last definition, it is not hard to see that the 
product of two Polish spaces is Polish; in particular 
$X\times X$ is Polish. 

Here a theorem dating back to the early 1900's 
describes the possible structure of an 
arbitrary Borel set. 

\bigskip 



\no{\bf Theorem} (Classical) If $B$ is a Borel set then either  

\leftskip 0.5in 

\no (I) $|B|\leq \aleph_0$ ($B$ is countable), or 

\no (II) $|B|=2^{\aleph_0}$ ($B$ has cardinality continuum). 

\leftskip 0in 

{\underline{Moreover}} any two Borel sets of the same cardinality are 
Borel isomorphic. 

\bigskip 

By this last part of the theorem I mean the following. If $X_1, X_2$ are Polish 
and $B_i\subset X_i$ ($i=1, 2$) are Borel with $|B_1|=|B_2|$ then there 
is a function 
\[f: B_1\rightarrow B_2\] 
with 

\leftskip 0.5in 

\no (a) $f$ a bijection; 

\no (b) $f^{-1}[C]$ Borel all $C\subset B_2$ Borel; and 

\no (c) $f[C]$ Borel all $C\subset B_1$ Borel. 

\leftskip 0in 

(Just in passing I should add that (c) above follows from 
the conjunction of (a) and (b) -- but we probably won't need that 
particular fact.) 

The situation for Borel equivalence relations initially appears the 
same. 

\bigskip 

\no {\bf Theorem} (Silver) Let $E$ be a Borel equivalence relation 
on a Polish space $X$. Then either 

\leftskip 0.5in 

\no (I) $|X/E|\leq \aleph_0$ ($E$ has only countably many equivalence classes), or 

\no (II) $|X/E|=2^{\aleph_0}$ ($E$ has continuum many classes). 

\leftskip 0in 

\bigskip 

But there is no ``moreover''. The problem is with part (II), where there is an 
enormous range of possible types of equivalence relations with continuum 
many equivalence classes. 

\bigskip 

\no {\bf Definition} Let $E$ and $ F$ be Borel equivalence relations on Polish $X$ 
and $ Y$. 
We write 
\[E\leq_B F,\] 
and say that $E$ is {\it Borel reducible} to $F$,  
if there is a Borel function 
\[f: X\rightarrow Y\] 
such that for all $x_1, x_2\in X$ 
\[x_1 E x_2 \Leftrightarrow f(x_1)F f(x_2).\] 

$E\sim_B F$ indicates that we have both 
\[E\leq_B F\] 
and 
\[F\leq_B E.\] 

\bigskip 

\no {\bf Examples} 1. For any Polish space $X$ we have id$(X)$ as the 
identity relation on $X$: $\{(x_1, x_2)\in X\times X: x_1=x_2\}$. 

2. $E_0$, eventual agreement on 
\[2^\N=\{0,1\}^\N,\] 
the space of infinite binary sequences. So that $f_1 E_0 f_2$ if there is some 
$N\in\N$ such that 
\[\forall m>N(f_1(m)=f_2(m)).\] 

3. $E_v$, the Vitali equivalence relation consisting of cosets of $\Q$ in $\R$. 
So $r_1 E_v r_2$ if 
\[r_1-r_2\in \Q.\] 

\bigskip 

Actually it turns out that $E_0\sim_B E_v$ and for any two uncountable 
Polish spaces $X_1, X_2$ one has 
id$(X_1)\sim_B$ id$(X_2)$. 


Possibility (II) from Silver's theorem represents the start of a 
very long story. The first major result was obtained at the end 
of the 1980's: 

\bigskip 

\no {\bf Theorem}(Harrington-Kechris-Louveau) Let $E$ be a Borel 
equivalence relation. Then exactly one of the following holds: 

\leftskip 0.4in 

\no (I) $E\leq_B$ id$(2^\N)$; 

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

\leftskip 0in 

\bigskip 

It takes a non-trivial amount of descriptive set theory to 
prove this theorem. Instead I will probably try to work through 
the analogue for isomorphism relation on countable structures. 

Just as a warning, for $\l$ a countable language we do not have that 
the isomorphism relation on countable $\l$-structures is Borel 
in any of the previously mentioned Polish topologies, except when 
$\l$ is composed solely of unary predicates. Thus Harrington-Kechris-Louveau 
will not generally apply. 

However it turns out that an analogue can be proved. 

Here for $\sigma\in\l_{\omega_1, \omega}$ I will let Mod($\sigma$) 
be the subset of Mod$(\l)$ consisting of models of $\sigma$. This is 
a Borel subset of Mod$(\l)$ under any of our topologies, and a 
Polish space in its right in the topology generated by any countable 
fragment $F\subset\l_{\omega_1, \omega}$ which includes $\sigma$. 

\bigskip 

\no{\bf Theorem} (Becker; Hjorth-Kechris) For $\l$ a countable 
language and $\sigma\in \l_{\omega_1, \omega}$ we have either 

\leftskip 0.5in 

\no (I) there is a $\Ubf{\Delta}^{\rm HC}_1$ function\footnote{That is to 
say, some function which is $\Delta_1(x)$ over the hereditarily countable 
sets for some hereditarily countable $x$. The details of this definition 
are not so important; it is just that we can not use the old standby of 
Borel reduction for various technical reasons. 

One might choose to think of the complexity class $\Ubf{\Delta}^{\rm HC}_1$ as 
being the analogue to HC of recursive to HF (the hereditarily finite sets).} 
assigning elements of $2^{<\omega_1}$ as complete invariants, or 

\no (II) $E_0\leq_B\cong|_{{\rm Mod}(\sigma)}$.  

\leftskip 0in 


\bigskip 

Beyond $E_0$ the picture becomes extremely complicated, and it 
is poorly understood. If time allows, we 
might be able to work in some discussion of this still largely uncharted 
territory. Another side topic will be the theory of continuous actions of 
Polish groups and some special cases of the {\it topological Vaught conjecture}          ; 
this should fit naturally into the proof of ``Becker; Hjorth-Kechris'' above, 
since it too requires some discussion of the general actions of Polish groups. 


\newpage 

\centerline{\bf {\huge Borel sets}} 



\bigskip 

\no {\bf Definition} A topological space is {\it Polish} 
if it is separable and there exists a complete metric which 
generates its topology. 

\bigskip 

Note then that a Polish space always has a countable basis 
for its topology. 

Just to give some context, let me mention a classical 
characterization of Polish spaces. We will never use this 
result, so I mention it without proof. 

\bigskip 

\no {\bf Theorem} (Hausdorff) A topological space is Polish if 
and only if it is homeomorphic to some subset of the Hilbert 
cube, $[0,1]^\N$, and it is the image of $\N^\N$ under some 
continuous, open function. 

\bigskip 

\no {\bf Definition} The $\sigma$-algebra generated by the 
open sets forms the {\it Borel} subsets of a Polish space. 

\bigskip 

\no {\bf Example} Let $\l$ be a countable language and Mod($\l$) 
the space of $\l$-structures on $\N$; if we equip this space with 
the topology generated by quantifier free formulas then it is naturally 
homeomorphic to 
\[\prod_{{\rm no\: of\: unary\: predicates}} \{0, 1\}^\N\times 
\prod_{{\rm no\: of\: binary\:  relations}} \{0, 1\}^{\N\times\N}\times\]
\[\prod_{{\rm no\: of\: ternary\:  relations}} \{0, 1\}^{\N\times\N\times\N}\times
\cdots\] 
\[\prod_{\rm no\: of\: unary \: functions} \N^\N\times 
\prod_{\rm no\: of \: binary\: functions} \N^{\N\times\N}
\cdots.\] 
We will shortly prove that countable products of Polish spaces are 
Polish, and so this is as well. 

Then one has for any first order formula $\varphi$ and $\vec n\in \N^{<\N}$ 
that the set of 
\[\{\m| \m\models \varphi(\vec n)\}\] 
is a Borel set. This is easily proved by induction on 
the logical complexity of $\varphi$, starting with the 
quantifier free formulas as the base case, and working up through 
the addition of existential and universal quantifiers\footnote{Since 
every formula is provably equivalent to one with all the quantifiers on 
the outside and all the Boolean connectives on the inside, this is all we 
need to worry about.} by observing that 
\[\{\m: \m\models \exists x\varphi(\vec n, x)\}=
\bigcup_{m\in \N}\{\m: \m \models \varphi(\vec n, m)\}\] 
and 
\[\{\m: \m\models \forall x\varphi(\vec n, x)\}=
\bigcap_{m\in \N}\{\m: \m \models \varphi(\vec n, m)\}.\]

Thus the topology of quantifier free formulas and the topology of 
first order logic give rise to the same Borel sets. 


\def\b{\cal B}

\bigskip 

\no{\bf Definition} A set $X$ with a $\sigma$-algebra of sets $\b$ is 
said to be a {\it standard Borel space} if there is some Polish 
topology which gives rise to $\b$ as its Borel sets. 

\bigskip 

Now we can at least state the our temporary goals, just for this 
section. 

\begin{enumerate} 

\item Mod($\l$) in the topology of first order formulas is Polish. 

\item A Borel subset of a standard Borel space is again standard 
Borel. 

\item Any uncountable Borel set has size $2^{\aleph_0}$. 

\end{enumerate} 




Actually in the proof of this last point we will follow the path 
chosen in Kechris' {\bf Classical descriptive set theory,} reducing 
it to 2. and the perfect set theorem for Polish spaces. 


The arguments here are all fairly elementary. One does little 
calculations with respect to metrics, and the typical step is to 
show that we can fiddle some coordinates to produce a complete 
metric with various desirable properties. 

Ultimately we will use these little results as part of the proof the 
above mentioned dichotomy theorem for the isomorphism relation on 
classes of countable structures. The proof requires us to repeatedly 
modify a given space of structures, through transfinitely many steps, and 
at each stage it will be necessary to maintain the Polishness of 
the space. 

The study of Polish space has emerged as a central theme in descriptive 
set theory. It is generally accepted that these are the spaces 
we can work with, applicable to a wide context but sufficiently specific 
to avoid certain pathologies. 

Recently a few people -- notably Becker and Kechris - have made some 
use of the more general ``strong Choquet'' spaces. But it is not clear 
that this is likely to ever unseat the current prejudice in favor of 
Polish. 











\bigskip 


\no {\bf Lemma} Let $X$ be a Polish space. Then it has as a compatible 
complete metric bounded by 1. 

\smallskip 

\no {\bf Proof} Let $d'$ be some complete metric. Let 
\[d(x_1, x_2)=\frac{d'(x_1, x_2)}{1+d'(x_1, x_2)}.\] 
The transformation 
\[r\mapsto \frac{r}{1+r}\] 
provides an order preserving transformation of $[0,\infty)$ onto 
$[0,1)$. Thus, jumping ahead to the end of the argument, once we establish 
that $d$ {\it is} a metric then we have the same Cauchy sequences for 
the two metrics, and from this completeness follows for free. Similarly the 
two metrics have the same open balls, and hence give rise to the same topologies. 

We are therefore only left with proving it to be a metric. And here the main 
issue is showing that the triangle inequality holds. 

Let $x_1, x_2, x_3\in X$. We want to show 
\[d(x_1,x_3)\leq d(x_1, x_2)+d(x_2, x_3).\] 
We may assume that 
\[d'(x_1, x_3)\geq d'(x_1, x_2), d'(x_2, x_3);\] 
since if for  instance  $d'(x_1, x_3)\leq d'(x_1, x_2)$ then 
\[d(x_1,x_3)\leq d(x_1, x_2),\]
since our change in coordinates is order preserving, and we are done. 

But now we have 
\[d(x_1, x_2)+d(x_2, x_3)=\frac{d'(x_1, x_2)}{1+d'(x_1, x_2)}+
\frac{d'(x_2, x_3)}{1+d'(x_2, x_3)}\]
\[\geq \frac{d'(x_1, x_2)+d'(x_2, x_3)}{1+d'(x_1, x_3)},\] 
by our assumption above, 
which in turn, by the triangle inequality for $d'$, is at least 
as large as $\frac{d'(x_1, x_3)}{1+d'(x_1, x_3)}$. 
\hfill $\square$ 


\bigskip 

\no{\bf Corollary} Let $(X_i)_i$ be a sequence of Polish spaces. 
Then 
\[\prod_{i\in\N} X_i\] 
is Polish. 

\smallskip 

\no {\bf Proof} Let $d_i$ be a complete metric on $X_i$, $i\in\N$. 
By the lemma we may assume the metric bounded by one. Then for 
\[\vec x=(x_0, x_1, x_2,...), \vec y=(y_0, y_1, y_2,...)\in \prod_{i\in\N} X_i\] 
we can let 
\[d(\vec x, \vec y)=\sum_{i\in\N} 2^{-i}d_i(x_i, y_i).\] 
\hfill $\square$ 

\bigskip 

\no {\bf Lemma} An open subset of a Polish space is Polish in the 
subspace topology. 

\smallskip 

\no {\bf Proof} Let $X$ be a Polish space, $d$ a complete metric, $O\subset X$ 
open. 

Let us fix a continuous 
\[\pi : O\rightarrow \R\] 
which has the property 
\[\pi(x)\rightarrow +\infty\] 
as $x\rightarrow X\setminus O$. For instance we can take 
\[\pi(x)=\frac{1}{{\rm inf}\{d(x, y)| y\notin O\}}.\] 
Then let 
\[d_O(x_1, x_2)=d(x_1, x_2)+|\pi(x_1)+\pi(x_2)|.\] 

Since $\pi$ is continuous we do not add to the topology of 
$O$ by taking this metric. For instance, if $V\subset O$ is open, 
$x\in V$, then we can find some $\epsilon$ such that for all 
$y$ with $d(x, y)<\epsilon$ we have $y\in V$; but then from the 
definition of $d_O$ we have every $y$ with $d_O(x, y)<\epsilon$ 
in $V$, which is just what we need to show $V$ is open with 
respect to $d_O$. Conversely if $V\subset O$ is $d_O$-open, 
$x\in V$, then we can choose some $\epsilon$ with the open ball of 
radius $\epsilon$ with respect to $d_O$ included in $V$; and then the 
continuity of $\pi$ enables us to find some $\delta<\frac{\epsilon}{2}$ 
such that for all $y\in O$ with $d(x, y)<\delta$ we have 
\[|\pi(x)-\pi(y)|<\frac{\epsilon}{2},\] 
and thus the ball of radius $\delta$ with respect to $d$ is included 
in $V$. 


And the various facts required 
for $d_O$ to be a metric are trivial to verify. The main issue 
is completeness. 

But if $(x_i)_i$ is a Cauchy sequence in $(O, d_O)$ then it will 
necessarily be $d$-Cauchy, and so it will have a limit $x_\infty\in X$. 
We need to check $x_\infty\in O$. 

But otherwise we obtain 
\[\pi(x_i)\rightarrow+\infty\] 
and hence for all $x_N$ on our sequence 
\[|\pi(x_N)-\pi(x_i)|\rightarrow +\infty\] 
as $i\rightarrow \infty$, contradicting our assumption on 
the sequence $(x_i)_i$. 
\hfill $\square$ 

\bigskip 

\no {\bf Definition} A subset of a Polish space is $G_\delta$ 
if it is given by a countable intersection of open sets. 

\bigskip 

Some people use $\Ubf{\Pi}^0_2$ instead of $G_\delta$. And in fact 
this is a better notation, since it forms part of a general scheme to 
refer to the entire Borel hierarchy, while 
the 
\[G_\delta, F_\sigma, G_{\delta\sigma} , F_{\sigma\delta},...\] 
method only extends to the finite levels. 

Note that every closed set is $G_\delta$. If $C\subset X$ is closed, then 
it equals 
\[\bigcap_{n\in\N}\{x: \exists y\in C(d(x, y)\leq\frac{1}{n})\}.\] 

\bigskip 

\no {\bf Corollary} Any $G_\delta$ subset of a Polish space is 
Polish in the subspace topology. 

\smallskip 

\no {\bf Proof} Let $X$ be Polish, 
\[B=\bigcap_{i\in\N} O_i \] 
a $G_\delta$ subset, 
where each $O_i$ is open, and 
let $d_i$ be a complete metric on $O_i$ for $i\in\N$. 

We may assume each $d_i$ is bounded by $1$, and then let 
\[d_B(x, y)=\sum_{i\in\N}2^{-i}d_i(x, y).\] 
\hfill $\square$ 


\bigskip 

\no {\bf Lemma} For $\l$ a countable language, the space 
Mod($\l$) equipped with the topology of first order formulas 
is a Polish space. 

\smallskip 

\no {\bf Proof} Let $\{c_n| n\in\N\}$ be fresh constants 
and let $\hat{\l}=\l\cup\{c_n| n\in\N\}$ be the language 
obtained by adding them to $\l$. Let $S$ be the collection of 
sentences in $\hat{\l}$. Then 
\[\{0,1\}^S\] 
in the product topology is naturally homeomorphic to 
$\{0,1\}^\N$, and thus Polish. 

Let $B$ be the set of $f\in\{0,1\}^S$ such that 

\leftskip 0.4in 

\no (a) $\{\varphi| f(\varphi)=1\}$ is consistent, and 

\no (b) for all $\varphi$ we have 
\[f(\varphi)=0\Leftrightarrow f(\neg\varphi)=1,\] 
and 

\no (c) for all $\varphi$ we have 
\[f(\exists x \varphi(x))\Leftrightarrow \exists n\in\N(f(\varphi(c_n))=1).\] 

\leftskip 0in 

\medskip 

Claim: $B$ is a $G_\delta$ subset of $\{0,1\}^S$. 

Proof of Claim: Since countable intersections of 
$G_\delta$ sets are $G_\delta$, it 
suffices to show that the conditions (a), (b), and (c) 
all correspond to $G_\delta$ sets. This is almost trivially true 
for (a), since a first order theory is inconsistent if and only if 
it includes a finite set of set of sentences which are inconsistent; 
thus if ${\cal I}\subset [S]^{<\N}$ is the set of finite inconsistent 
subset of $S$ then (a) corresponds to the $G_\delta$ set 
\[\bigcap_{F\in {\cal I}}\bigcup_{\psi\in F}\{f| f(\psi)=0\}.\] 

Similarly (b) is $G_\delta$ (and as with (a), it is actually closed). 

Finally, (c) corresponds to the conjunction of the sets 
\[\bigcap_{\varphi\in S}\bigcap_{n\in\N}\{f| f(\varphi(c_n))=1\Rightarrow 
f(\exists x \varphi(x))=1\}\] 
and 
\[\bigcap_{\varphi\in S}(\{f| f(\exists x\varphi(x))=0\}\cup
\bigcup_{n\in\N} \{f| f(\varphi(c_n))=1\}),\] 
and is thus $G_\delta$. \hfill (Claim$\square$) 

\medskip 

To each $\m\in{\rm Mod}(\l)$ let $T_\m\in \{0,1\}^S$ 
be given by 
\[T_\m(\varphi(c_{n_1}, c_{n_2},...))=1\Leftrightarrow \m\models 
\varphi(n_1, n_2,...).\] 
It is more or less immediate from the definitions that each 
such $T_\m$ is in $B$. 

\medskip 


Claim: The map 
\[{\rm Mod}(\l)\rightarrow B\] 
\[\m\mapsto T_\m\] 
is a bijection of ${\rm Mod}(\l)$ onto $B$. 

Proof of Claim: The map is obviously one-to-one, since 
for any $\m_1\neq\m_2$ there will be some atomic $\psi(\vec x)$ 
and $n_1, n_2,...$ on which they disagree, whence 
$T_{\m_1}$ and $T_{\m_2}$ disagree on 
$\psi(c_{n_1}, c_{n_2},...)$. 


As for showing it onto, fix $T\in B$. We define $\m$ by the requirements 
that for any relation $R\in\l$ 
\[\m\models R(n_1, n_2,...)\] 
if and only if $T(R(c_{n_1}, c_{n_2},...))=1$, and 
for any function symbol $F\in\l$ 
\[F^\m(n_1, n_2,...)=\ell\] 
if and only if $T(F(c_{n_1}, c_{n_2},...)=c_\ell)=1$. 
(This {\it is} well defined. By (a) and (b) we have 
$T(\exists x(F(c_{n_1}, c_{n_2},...)=x))=1$, and then 
by (c) we have some witness $c_\ell$.)  
Then an easy induction on logical complexity shows that 
for any first order $\psi$ 
\[\m\models \psi(n_1, n_2,...)\Leftrightarrow 
T(\psi(c_{n_1}, c_{n_2},...))=1.\] 
\hfill (Claim$\square$) 

\medskip 

But this basically finishes the lemma. It follows from the 
definitions of the topologies that 
\[\m\mapsto T_\m\] 
is a homeomorphism. 
Thus Mod$(\l)$ in the topology generated by first 
order formulas 
is homeomorphic to $B$; and we know $B$ must be Polish 
since it is a $G_\delta$ subset of a Polish space. 
\hfill $\square$ 

\bigskip 


\def\o{{\cal O}}

Up to now I have done the usually sloppy, convenient, but not 
quite correct thing, and simply identified a topological space with 
its underlying set. Over the next couple of lemmas we need to be 
more precise. Thus let us agree to write $(X, \tau)$ for a Polish space 
with underlying set $X$ and topology $\tau$. 

\bigskip 


\no {\bf Lemma} Let $(X, \tau)$ be a Polish space and ${\cal O}\subset X$ 
open. Then there is  a new topology $\hat{\tau}$ such that:  

\leftskip 0.4in 

\no (a) $\hat{\tau}\supset \tau$; 

\no (b) every $\hat{\tau}$-open set is $\tau$-Borel (and hence the two 
topologies give rise to the same standard Borel structure); 

\no (c) $\o$ is $\hat{\tau}$-clopen. 

\leftskip 0in 

\no {\bf Proof: } 
Let $d_X$ be a compatible complete metric on $(X,\tau)$. 
Since $\o$ is open we can find a complete metric 
$d_\o$ on $\o$ which is compatible with 
its subspace topology from $\tau$. By earlier lemmas we can assume both to be 
bounded by 1. 

Now we can define $d$ on $X$ by cases. 

\leftskip 0.4in 

\no (i) If $x, y\in \o$ then $d(x, y)=d_\o(x, y)$. 

\no (ii) If $x, y\notin \o$ then $d(x, y)=d_X(x, y)$. 

\no (iii) If $x\in \o, y\notin\o$ then $d(x, y)=2$. 

\no (iii) If $x\notin \o, y\in\o$ then $d(x, y)=2$. 

\leftskip 0in 

It is as if we have split the space up into two halves, $\o$ and $X\setminus \o$, 
each a distance of 2 away from the other. 
Any $d$-Cauchy sequence must eventually 
decide to stay in one of these two halves, and hence will be either 
$d_X$ or $d_\o$ Cauchy. 
\hfill $\square$ 

\bigskip 


Really this proof is using the fact that the disjoint union of 
two Polish spaces is again Polish. 


The next lemma appears to be a folklore result. I am going to 
give a proof I saw presented by Ramez Sami. 

\def\c{\cal C}

\bigskip 

\no {\bf Lemma}  Let $(X, \tau)$ be a Polish space and $B\subset X$ 
Borel. Then there is a richer topology $\hat{\tau}\supset \tau$ such that:  

\leftskip 0.4in 

\no (a) $\hat{\tau}\supset \tau$; 

\no (b) every $\hat{\tau}$-open set is $\tau$-Borel; 

\no (c) $B$ is $\hat{\tau}$-open. 

\leftskip 0in 

\no {\bf Proof: } Let $\c$ be the collection of all $B\subset X$ for 
which we can find $\hat{\tau}$ satisfying the lemma. We have previously 
seen that this include all open sets. Then by the structure of the 
definition we have that it must be closed under complementation -- that is 
to say, if $B\in\c$ then $(X\setminus B)\in \c$. 

Therefore to show it forms a $\sigma$-algebra we need only show it 
is closed under countable intersections. For this the following observation 
suffices. 

\medskip 

Claim: Suppose for each $i$ we have a Polish topology $\tau_i\supset \tau$. 
Then the union of these topologies generates a Polish topology. 

Proof of Claim: 
Consider the space 
\[\prod_{i\in\N} (X, \tau_i).\] 
This is a product of Polish spaces, and hence Polish. As is the closed subset 
\[\{\vec x| \forall i, j\in\N(x_i=x_j)\}\] 
consisting of all constant sequences. 

If we associate to each $x\in X$ the sequence with constant value $x$ then 
we obtain a homeomorphism of $X$ under the topology generated by 
$\bigcup_{i\in\N}\tau_i$ and  $\{\vec x| \forall i, j\in\N(x_i=x_j)\}$ 
with the subspace topology. 
\hfill (Claim$\square$) 
 
\hfill $\square$ 

\bigskip 

\no {\bf Definition} A subset $P$ of a Polish space $X$ is {\it perfect} 
if it is 

\leftskip 0.4in 

\no (a) non-empty, 

\no (b) closed, and 

\no (c) it has no isolated points -- that is to say, if 
$U\subset X$ is open with $|U\cap P|\geq 1$ then we actually have 
$|U\cap P|\geq 2$. 

\leftskip 0in 

\bigskip 


\def\b{{\cal B}}





\no {\bf Lemma} If $X$ is an uncountable Polish space, then 
it contains a perfect set. 

\no {\bf Proof} Let $\b=\{U_n| n\in\N\}$ be a countable basis for $X$. 
Then define $\b_0\subset\b$ to be the set of 
$\{U_n| U_n\cap P$ is countable $\}$ and define $P$ to be the elements 
of $X$ not contained in any element of $\b_0$: 
\[P=X\setminus(\bigcup\b_0).\] 
Since $\bigcup\b_0$ is a union of open sets, we certainly have 
that $P$ is closed. 

If $P$ is empty, then $X$ is a countable union of countable sets 
and we have a contradiction. 

So instead assume $P\neq \emptyset$, $x\in P$, and we try to show $x$ not 
isolated. 

For this purpose fix open $U$ containing $x$. After possibly shrinking 
$U$ we can assume $U\in\b$. But then if $|U\cap P|=1$ we would have 
\[|U\setminus(\bigcup \b_0)|=1\] 
and hence 
\[|U|\leq |\bigcup \b_0|+1\leq \aleph_0+1 =\aleph_0,\] 
which would place $U$ into $\b_0$, contradicting $x\in P$. 
\hfil $\square$ 

\bigskip 

It is implicit in this proof that any Polish 
space without isolated points must contain a perfect subset. 

\bigskip 

\no {\bf Lemma} If $P$ is a perfect subset of a Polish space, then 
$P=|2^{\aleph_0}|$, and in fact contains a homeomorphic copy of 
\[\{0,1\}^\N\] 
as a closed subset. 

\no {\bf Proof} We first need an observation about the 
structure of open sets in our perfect set. 

\smallskip 

Claim: If $U$ is open with $U\cap P\neq\emptyset$ and $\epsilon > 0$ 
then there are open $V_0, V_1$ with: 

\begin{enumerate} 

\item $V_0\cap P, V_1\cap P \neq\emptyset$; 

\item $\overline{V_0}, \overline{V_1}\subset U$;\footnote{$\overline{A}$ indicates the closure of a set 
$A$.}  

\item $V_0\cap V_1=\emptyset$; 

\item $d(V_0), d(V_1) <\epsilon$.\footnote{Here and elsewhere 
I use $d(V)$ to denote the {\it diameter} of $V$, 
sup$\{d(x, y): x, y\in V\}$, where $d$ is some complete metric 
on our Polish space.} 

\end{enumerate} 

Proof of Claim: Since $P$ has no isolated points we 
may choose $x_0, x_1\in U\cap P$ with 
$x_0\neq x_1$. Then we may choose sufficiently small open 
neighborhoods $B_{2\delta}(x_0), B_{2\delta}(x_1)$ with:\footnote{In general 
$B_r(x)$ denotes the open ball of radius $r$ around $x$: $\{y: 
d(x, y)<r\}$.}

\begin{enumerate} 

\item $B_{2\delta}(x_0), B_{2\delta}(x_1)\subset V$; 

\item $B_{2\delta}(x_0)\cap B_{2\delta}(x_1)=\emptyset$; 

\item $\delta<\epsilon$. 

\end{enumerate} 

Then the sets $B_\delta(x_0)=V_0$ and $B_\delta(x_1)=V_1$ are 
as in the claim. 
\hfill (Claim $\square$) 

\smallskip 

Claim: There is a collection of open sets 
indexed by {\it finite} binary sequences, 
$(U_s)_{s\in \{0,1\}^{<\N}}$, such that: 

\begin{enumerate} 

\item $U_s\cap P\neq\emptyset$ all $s\in \{0,1\}^{<\N}$; 

\item $\overline{U_{s^\smallfrown 0}}, 
\overline{U_{s^\smallfrown 1}}\subset U_s$ all  
$s\in \{0,1\}^{<\N}$;\footnote{For $s:\{0,1,...,n-1\}\rightarrow \{0,1\}$ 
we use $s^\smallfrown i$ to indicate the sequence of length $n+1$ obtained 
by concatenating $s$ with the sequence $\langle i \rangle$; that is to say, 
$s^\smallfrown i$ extends $s$, has length equal to length$(s)+1$, and assumes 
$i$ as its final value.} 

\item $d(U_s)< \frac{1}{n}$ all $s\in \{0,1\}^n$; 

\item $U_{s^\smallfrown 0}\cap U_{s^\smallfrown 1}=\emptyset$ 
all $s\in\{0,1\}^{<\N}$. 


\end{enumerate}

Proof of Claim: We build $(U_s)_{s\in \{0,1\}^{\leq n}}$ by 
induction on $n$. We can just begin with $U_\emptyset$ any sufficiently 
small open set meeting $P$. 

Given the collection $(U_s)_{s\in\{0,1\}^n}$ we can choose for 
each $s$ 
\[U_{s^\smallfrown 0}, U_{s^\smallfrown 1}\subset U_s\] 
as in the last claim 
for $\epsilon =\frac{1}{n+1}$. 
\hfill (Claim $\square$) 

\smallskip 

In this way we have obtained a nested collection of open sets whose 
structure resembles the canonical basis of open sets in the 
space $\{0,1\}^\N$ of infinite binary sequences. 
For each $f:\N\rightarrow \{0,1\}$ and $n\in\N$ we let 
$f|_n$ be the binary sequence of length $n$ obtained by restricting 
$f$ to its first $n$ many values. 

\smallskip 

Claim: For each $f:\N\rightarrow \{0,1\}$ there is $x_f\in P$ with 
\[x_f\in\bigcap_{n\in\N} U_{f|_n}.\] 

Proof of Claim: We may choose $z_n\in U_{f|_n}\cap P$ for 
each $n$ by assumption on our nested collection of open sets. 
Then we obtain that $d(z_n, z_m)< \frac{1}{n}$ all $m\geq n$ 
since both points are in $U_{f|_n}$ and this open set has diameter 
less than $\frac{1}{n}$. Thus $(z_n)$ must be a Cauchy sequence, 
which will necessarily converge to some point 
\[z_\infty\in P\cap \bigcap_{n\in\N}\overline{U_{f|_n}}.\] 
Since $\overline{U_{f|_{n+1}}}\subset U_{f|_n}$ we 
obtain $x_f=z_\infty$ is as required. 
\hfill (Claim $\square$) 

\smallskip 

For each such $f$ there will be exactly one $x_f$ as 
in the claim, for any other 
\[x_f'\in\bigcap_{n\in\N} U_{f|_n}\] 
would have to have $d(x_f, x_f')<1/n$ all $n$. 

Thus $f\mapsto x_f$ provides some kind of map from 
the space of infinite binary sequences to $P$. It is obviously 
one to one, since if $f\neq f'$ then we may let $s=f\cap f'$ be 
the longest initial segment contained in both, and obtain 
that one of $x_f, x_{f'}$ is in $U_{s^\smallfrown 0}$ and 
the other is in $U_{s^\smallfrown 1}$. 
The main issue is continuity. 

\smallskip 

Claim: $f\mapsto x_f$ is continuous. 

Proof of Claim: Let $V$ be an open neighborhood of $x_f$. 
(We need an open $W$ containing $f$ with $\{x_h: h\in W\}
\subset V$.) Choose $n$ with $B_{1/n}(x_f)\subset V$. Then since 
any two points $y_0, y_1$ 
of $U_{f|_n}$ have $d(y_0, y_1)<1/n$ we obtain $U_{f|_n}\subset V$, 
and thus for $W$ the open set $\{h: \N\rightarrow \{0,1\}| h\supset f|_n\}$ 
we have $x_h\in V$ all $h\in W$. 
\hfill (Claim $\square$) 

Thus 
\[\{0,1\}^\N\rightarrow P\] 
\[f\mapsto x_f\] 
is a continuous  
function. Since $\{0,1\}^\N$ is compact the map 
sends closed sets to closed sets. Since it is injective 
we then have that it sends open sets to sets which 
are relatively open in its image, and thus it is a 
homeomorphism onto a closed subset of $P$. 


$P$ is at least as big as the number of subset of $\N$; thus $|P|\geq 
2^{\aleph_0}$. But 
conversely, $P$ is a Polish space in its own right, and so it has a countable 
dense subset, ${\cal D}$ say; and then $P$ is no bigger than the number of 
Cauchy sequences from ${\cal D}$, which gives us the bound 
\[|P|\leq |{\cal D}|^{\N} \leq |{\cal P}({\cal D}\times \N)|=
|2^{{\cal D}\times\N}|=2^{\aleph_0}.\] 
\hfill $\square$ 

\bigskip 

\no {\bf Corollary} Any uncountable Borel set has size $2^{\aleph_0}$. 

\no {\bf Proof} Since we have previously seen that any Borel set allows a 
Polish topology and any uncountable Polish space contains a perfect subset 
and hence has cardinality continuum. 
\hfill $\square$ 

\bigskip 

\no {\bf Corollary} Any Polish space without isolated points has size 
$2^{\aleph_0}$. 

\no {\bf Proof} As remarked above, a Polish space without isolated points 
must contain a perfect set. 
\hfill $\square$ 

\bigskip 

Thus in particular $\Q$ in the subspace topology it inherits from $\R$ is not 
a Polish space. 

\bigskip 



We are yet to see that any two Borel sets of the same cardinality are 
Borel isomorphic. In light of our lemmas on changing topologies we need 
only see that any two Polish spaces of the same cardinality are 
isomorphic as standard Borel spaces. The proof of this is sketched in the 
exercises below. 

\bigskip 
\bigskip 

\no {\bf Exercises} 

\smallskip 

1. Show that $\N^\N$ is homeomorphic to a $G_\delta$ subset of 
$\{0,1\}^\N$. (Namely, the set of binary sequences with infinitely 
many 1's). 

\smallskip 

2.(a) Show that if $X$ is Polish then we may find a nested collection of 
sets $(V_s)_{s\in\N^{<\N}}$ such that 

\begin{enumerate} 

\item each $V_s$ is non-empty and open,

\item $\overline{V_s}\subset V_t$ whenever $s$ strictly extends $t$, 

\item $V_\emptyset =X$,  

\item $d(V_s)<\frac{1}{n}$ whenever $s:\{0,1,...,n-1\}\rightarrow \N$, 
$n>0$,  

\item each $V_s$ equals $\bigcup_{k\in\N} V_{s^\smallfrown k}$. 

\end{enumerate} 

(b) Conclude that any Polish space is the continuous, open image of $\N^\N$. 

(c) Show that if $X$ is Polish then there is a Borel $B\subset \N^\N$ 
which is Borel isomorphic to $X$. 


\smallskip 

3. Let $X_1, X_2$ be Polish spaces, $B_1\subset X_1, B_2\subset X_2$ 
Borel sets, $\pi_1: X_1\rightarrow B_2, \pi_2: X_2\rightarrow B_1$ 
Borel isomorphisms. 

Show that $X_1$ and $X_2$ are Borel isomorphic. (Hint: This is close 
to the proof of Schroeder-Bernstein which does {\it not} use choice. You can 
find {\it that} proof in Tom Jech's {\bf Set Theory}.) 

\smallskip 

4. Conclude from 1-3 above and the earlier results about perfect 
sets that any two uncountable Borel sets are Borel isomorphic. 

\smallskip 

5. Show that if $X$ is a countable Polish space then any subset is 
Borel. Thus any function between countable Polish spaces is Borel. 


\newpage 


\centerline{\bf {\huge Borel equivalence relation}} 

\bigskip 

\no {\bf Definition} An equivalence relation $E$ on a 
Polish space $X$ is {\it Borel} if it is Borel as a subset 
of $X\times X$ in the product topological structure. A 
function 
\[\theta: X\rightarrow Y\] 
between Polish spaces is {\it Borel} if $\theta^{-1}[U]$ is 
Borel for any open set $U\subset Y$. (Actually this is equivalent 
to the graph of $\theta$ being Borel as a subset of $X\times Y$, but 
we are unlikely to need that particular result.) 

For $E, F$ equivalence relations on $X,Y$ we write 
\[E\leq_B F,\] 
$E$ {\it Borel reducible to} $F$, 
if there is a Borel $\theta: X\rightarrow Y$ such that 
for all $x_1, x_2\in X$ 
\[x_1 E x_2 \Leftrightarrow \theta(x_1) F \theta(x_2).\] 
We can then go ahead and set $E<_B F$ if there is a Borel reduction 
of $E$ to $F$ but not the other way around, and $E\sim_B F$ if there 
is a Borel reduction in both directions. 

\bigskip 

Of course there are other notions of comparison we might use for 
Borel equivalence relations. We might ask that the reduction be 
one-to-one. Or that it provide a bijection with some invariant Borel 
subset of the target space. And so on. 

Although certainly not the only notion worth investigating, 
$\leq_B$ is the main one studied by descriptive set theorists. 
It, and its variant, which allow classes of functions more general than 
Borel, also provides the most generous notion of reduction, and thus 
the non-reducibility below have the most force if we phrase them 
for $\leq_B$. 

\bigskip  

\no {\bf Notation} For $X$ a Polish space we let id$(X)$ be the identity 
relation on $X$. (Some people use $\Delta(X)$ for this relation, which is 
suggested by it being the diagonal in $X \times X$.) 

$E_0$ is the equivalence relation of agreement mod 
finite on $\{0,1\}^\N$: $f_1E_0 f_2$ if 
\[\exists N\forall m> N (f_1(m)=f_2(m)).\] 

\bigskip 

>From now on let me just write $2^\N$ for the space $\{0,1\}^\N$. It is 
a little less cumbersome and formal. 

\bigskip 

\no {\bf Lemma} id$(2^\N)\leq_B E_0$. 

\no {\bf Proof} Let $(s_n)_{n\in\N}$ enumerate the set 
$\{0,1\}^{<\N}$ of all finite binary sequences. For each $f\in 2^\N$ we 
define $\theta(f)$ by 
\[(\theta(f))(n)=1\Leftrightarrow s_n\subset f.\] 
That is to say, $(\theta(f))(n)=1$ if $s_n$ is a substring of $f$.  

This is continuous, since if $s_n:\{0,1,...,k-1\}\rightarrow \{0,1\}$ 
and $(\theta(f_0))(n)=i$ ($i\in\{0,1\}$), then for any other $f$ in the 
open set $\{h: \forall j< k(h(j) =f_0(j))\}$ we have $(\theta(f))(n)=i$. 

And obviously if $f_1$ id$(2^\N) f_2$ then by definition $f_1=f_2$ and 
so $\theta(f_1) =\theta(f_2)$ and they are certainly $E_0$ equivalent. 

Conversely if $f_1(k)\neq f_2(k)$ then for all $s_n$ with $s_n\subset f_1$ 
of length greater than $k$ we have $(\theta(f_1))(n)=1$ while 
$(\theta(f_2))(n)=0$. 
\hfill $\square$ 

\bigskip 

To show failure of reducibility in the other direction I will use 
Baire category techniques. 
The idea here is to approximate Borel functions on some suitably 
``large'' set by continuous functions. 

\bigskip 

\no {\bf Definition} A subset of a space $X$ is 
{\it nowhere dense} if its intersection with any non-empty 
open subset of $X$ is not dense. A subset is {\it meager} if 
it is included in the countable union of sets which are each 
closed and nowhere dense. 
The complement of a meager set is said to be {\it comeager}. 

\bigskip 

\no {\bf Fact} The countable unions of meager sets are meager; 
countable intersections of comeager sets are comeager.  
The meager sets form a $\sigma$-ideal; the comeager sets form a 
$\sigma$-filter. 


\bigskip 

Some books only state the Baire category theorem for a few specific spaces 
like the unit interval. The usual proof extends to Polish spaces. 

\bigskip 

\no {\bf Baire category theorem} 
Any comeager subset of a Polish space is non-empty. 

\bigskip 

\no {\bf Corollary} 
If $X$ is a Polish space without isolated points then 
any comeager set is uncountable. 

\bigskip 

\no {\bf Definition} A set $A$ has {\it the Baire property} if for some 
open $\o$ 
the symmetric difference 
\[A\Delta \o= (A\setminus \o)\cup (\o\setminus A)\] 
is meager. 

\bigskip 


\no {\bf Lemma} Every Borel set has the Baire property. 

\no {\bf Proof} Clearly the open sets have Baire property. 

If $C$ is closed then for 
\[C^o=\bigcup \{U: U\subset C, U {\rm \: open}\}\] 
we have that $C^o$ is the largest open set included in $C$ and 
$C\Delta C^o=C\setminus C^o$ is nowhere dense. Thus in general 
the complement of a set with Baire property has Baire property, since 
if $B\Delta \o$ is included in a meager set $M$, and $C$ is the 
complement of the open set $\o$, then 
\[(X\setminus B)\Delta C^o\subset M\cup (C\setminus C^o).\] 

Finally if $(B_i)_i$ is a sequence of Borel sets, $(\o_i)_i$ a 
sequence of open sets with $B_i\Delta \o_i$ always meager, 
then 
\[(\bigcup_{i\in\N} B_i)\Delta (\bigcup_{i\in\N} \o_i)\] 
is included  in the countable union of meager sets, and is 
hence meager in its own right. 
\hfill $\square$ 

\bigskip 

\no {\bf Corollary} Any Borel function between Polish spaces is 
continuous on a comeager set. 


That is to say, if $\theta: X\rightarrow Y$ is Borel, then there is a 
comeager $C\subset X$ having $\theta|_C$ continuous. 

\no{\bf Proof} Let $\{U_n| n\in\N\}$ be a countable basis of $Y$. For 
each $n$ choose open $\o_n\subset X$ with 
\[(\theta^{-1}[U_n])\Delta \o_n\subset M_n\] 
for some meager set $M_n$. Let 
\[C=X\setminus (\bigcup_{n\in\N} M_n).\] 
Then we have that 
$\theta|_C$  pulls basic open sets back to relatively open subsets of 
$C$, and thus is continuous. 
\hfill $\square$ 

\bigskip 

\no {\bf Lemma} $E_0$ is not Borel reducible to id$(2^\N)$. 

\no {\bf Proof} Instead let $\theta: 2^\N\rightarrow 2^\N$ be a 
Borel reduction. Let $C$ be a comeager set on which $\theta$ is 
continuous. 

For each finite binary sequence $s\in \{0,1\}^{<\N}$ define 
\[\psi_s: 2^\N\rightarrow 2^\N\] 
by 
\[(\psi_s(f))(n)=s(n) +f(n) \:\: {\rm mod}\: 2\] 
if $n$ is less than the length of $s$, and equal to 
$f(n)$ otherwise.\footnote{A way to think of this. Identify 
$\{0,1\}^\N$ with the product group $\Z_2^\N$ and consider 
the subgroup $G$ consisting of elements which have finite support. 
To each finite binary sequence $s$ we can associate a corresponding 
$g_s\in G$ and let $\psi_s$ be translation by $g_s$.} 
Each $\psi_s$ is a homeomorphism, and thus $\psi_s(C)$ is again 
comeager. 

Thus we can let 
\[\hat{C}=\bigcup_{s\in 2^{<\N}}\psi_s[C]\] 
and obtain a comeager set which is invariant under $E_0$, in the sense 
that it includes any equivalence class it meets, and on which $\theta$ 
is continuous. Now choose $f\in \hat{C}$. The $E_0$-equivalence class 
\[[f]_{E_0}\] 
of $f$ is dense in $2^\N$ and included in $\hat{C}$; hence it is 
dense in $\hat{C}$. $\theta$ is constant on $[f]_{E_0}$ by the 
assumption it perform a reduction. 

$\theta|_{\hat{C}}$ is continuous and constant on a dense 
subset, and therefore it is constant on $\hat{C}$. But this really does give us a 
contradiction, since $\hat{C}$ must be uncountable, and we can choose some 
\[h\in \hat{C}\setminus[f]_{E_0}\] 
with $\theta(h)=\theta(f)$. 
\hfill $\square$ 

\bigskip 
\bigskip 

\no {\bf Exercises} 

1. Show that for any two uncountable Polish spaces $X$ and $Y$ we have 
id$(X)\leq_B$ id$(Y)$. 

\smallskip 

2. Let $\l$ be a language consisting of just countably many unary predicates and 
let $F_2$ be the isomorphism relation on Mod$(\l)$.  
Show that $E_0\leq_B F_2$. 

Hence that id$(\R)<_B F_2$. 

\bigskip 
\bigskip 

The non-reducibility of $F_2$ to the identity relation on a Polish space even 
works for notions of reducibility which allow broader classes of functions. 
Consistently with ZFC $F_2$ is non-reducible to id$(\R)$ using ``set recursive'' 
or even ``$\R$-ordinal definable'' functions.\footnote{I only say 
``consistently with ZFC'' since we need to avoid, for instance, certain 
things which can happen in G\"{o}del's $L$ as a result of the simply definable 
well order of $\R$. Certainly with a little bit of forcing one can 
guarantee all $\Ubf{\Delta}^1_2$ sets have Baire property and with quite 
a lot of forcing one obtains the same for 
the $\R$-ordinal definable sets.}  
So although this isomorphism relation for countably many unary predicates 
might seem to be almost trivial from the point of view of model theory, there 
is already a substantial 
restriction on the kinds of objects one can hope to assign as 
complete invariants. 

If you want a considerably harder exercise you might try showing that 
$E_0<_B F_2$. And at 
the end of the course perhaps we will have time to 
discuss the general result that $F_2$ is not 
Borel reducible to any equivalence 
relation all of whose equivalence classes are countable. 


\newpage 








\centerline{\bf {\huge Infinitary logic}}

\bigskip 

\no {\bf Definition} Let $\l$ be a language. $\l_{\omega_1, \omega}$ 
is obtained by closing the atomic formulas of 
$\l$ under the usual first order operations 

\leftskip 0.4in 

\no (a) $\psi\mapsto \exists x \psi$, $\psi\mapsto \forall x \psi$, 

\no (b) $(\psi, \phi)\mapsto \psi\vee \phi$,  $(\psi, \phi)\mapsto \psi\wedge \phi$, 

\no (c) $\psi\mapsto \neg \psi$, 

\leftskip 0in 

\no as well as infinitary conjunction and disjunction, 

\leftskip 0.4in 

\no (d) whenever $\{\psi_i| i\in\N\}$ is a countable set of formulas in 
$\l_{\omega_1, \omega}$ we have 
\[\bigvee_{i\in\N}\psi_i\in \l_{\omega_1, \omega},\] 
\[\bigwedge_{i\in\N}\psi_i\in \l_{\omega_1, \omega}.\] 

\leftskip 0in 

\bigskip 


\no {\bf Definition} If $\m$ is an $\l$-structure, and $\varphi(x_1,x_2,..., x_k)$ 
is a formula of $\l_{\omega_1, \omega}$ with just finitely many free variables, then we 
can define 
\[\m\models \varphi(a_1, ..., a_k)\] 
by induction on the complexity of $\varphi$ in the usual way. The only clauses 
which differ from first order logic and the ones corresponding to infinite 
conjunction and disjunction, and here we stipulate that 
\[\m\models \bigwedge_{i\in\N}\psi_i\] 
\[\Leftrightarrow (\forall i\in\N(\m\models \psi_i)),\] 
and 
\[\m\models \bigvee_{i\in\N}\psi_i\]
\[\Leftrightarrow (\exists i\in\N(\m\models \psi_i)).\]

\bigskip 

\no {\bf Technical remarks} 

(i) The infinite conjunction 
$\bigvee_{i\in\N}\psi_i\in \l_{\omega_1, \omega}$ and infinite 
disjunction 
$\bigwedge_{i\in\N}\psi_i\in \l_{\omega_1, \omega}$ depend solely on the 
{\it set} $\{\psi_i| i\in\N\}$, and not the particular enumeration 
$(\psi_i)_{i\in\N}$. 

(ii) I have allowed formulas with infinitely many free variables, but 
not given any role to them in the satisfaction relation. There seems to be 
some variation in the literature on this point. 

(iii) Later we will need to perform a range of 
computations with languages and formulas, and 
for these purposes it will be helpful to adopt some conventions. Firstly that 
we assume $\l$ consists solely of symbols which are themselves hereditarily 
countable\footnote{A set $A$ is {\it hereditarily countable} if it is countable, 
all its elements are countable, all their elements are countable, and so on. More 
precisely, HC, the {\it collection of hereditarily countable sets},  is the 
smallest set containing all its countable subsets.} sets; all our languages 
will be countable, so this is not overly restrictive. After that we can assume 
that $\l_{\omega_1, \omega}$ is a subset of the hereditarily countable sets; 
for instance we can have as our convention that $\bigvee$ is some fixed hereditarily 
countable set, such as the number 17, and that 
\[\bigvee_{i\in\N}\psi_i=\{\{\psi_i, \bigvee\}: i\in\N\}.\] 

(iv) I will only use countably many variable symbols. Keisler handles this 
point somewhat differently. 


\bigskip 

\def\lo{\l_{\omega_1, \omega}}

\no {\bf Definition} $F\subset\lo$ is a {\it fragment} if: 

\leftskip 0.4in 


\no (a) it contains the atomic formulas; 

\no (b) it is closed under the first order operations 
\[\psi\mapsto \exists x\psi,\]  
\[\psi\mapsto \forall x \psi,\] 
\[(\psi, \phi)\mapsto \psi\vee \phi,\]   
\[(\psi, \phi)\mapsto \psi\wedge \phi,\] 
\[\psi\mapsto \neg \psi;\] 


\no (c) it is closed under subformulas, in the sense that 
\[\exists x \psi\in F\Rightarrow \psi\in F,\]
\[\forall x \psi\in F\Rightarrow \psi\in F,\] 
\[\psi\wedge \phi \in F\Rightarrow \psi, \phi\in F,\]
\[\psi\vee \phi \in F\Rightarrow \psi, \phi\in F,\] 
\[\neg\psi\in F\Rightarrow \psi\in F,\] 
\[\bigwedge_{i\in\N} \psi\in F\Rightarrow \{\psi_i: i\in\N\}\subset F,\]
\[\bigvee_{i\in\N} \psi\in F\Rightarrow \{\psi_i: i\in\N\}\subset F;\]  

\no (d) if $\varphi(x_1, x_2,x_3 ...)\in F$ and $t$ is a term, then 
\[\varphi(t, x_2, x_3,...)\in F.\] 

\leftskip 0in 

\bigskip 

In this definition of fragment (d) is important for what it 
{\it does not} do. It does not license 
substitutions which replace infinitely many variables with terms. 
Otherwise all our fragments would be uncountable. 

In Ramez Sami's {\it Polish group actions and the topological 
Vaught conjecture} he uses a somewhat weaker notion of 
fragment. As it turns out this weaker notion is still sufficient 
to prove that countable fragments generate Polish topologies, but 
not quite sufficient for us to obtain a nice characterization of 
{\it atomic model relative to a given fragment}. 

\bigskip 


\no {\bf Definition} For $F\subset\lo$ a fragment we let 
$\tau_F$ be the topology on Mod$(\l)$ whose basis consists of 
open sets of the form 
\[\{\m\in {\rm Mod}(\l): \m\models \varphi(n_1, n_2, ..., n_k)\},\] 
where $n_1, n_2, ..., n_k\in\N$ and $\varphi(\vec x)\in F$. 

\bigskip 

\no {\bf Lemma} If $F$ is a countable fragment then (Mod$(\l), \tau_F$) 
is a Polish space. 

\no {\bf Proof} This follows our proof for the topology generated by 
first order logic. 
We let $\hat{\l}$ be the language obtained by adding fresh constants 
$(c_n)_{n\in\N}$ to $\l$; and then we obtain $\hat{F}$ as the fragment 
generated by $F$ in $\hat{\l}_{\omega_1, \omega}$. And parallel to the 
proof from before we let $\hat{S}$ be the set of sentences in $\hat{F}$. 
\[2^{\hat{S}}=_{\rm df} \{0,1\}^{\hat{S}}\] 
gives us a Polish space, and we can let $A_{\hat{S}}$ be the set of 
$f\in 2^{\hat{S}}$ satisfying: 

\leftskip 0.4in 

\no (a) any finite subset of $\{\psi: f(\psi)=1\}$ is {\it consistent}, in 
the sense that it has some model; 

\no (b) $f(\psi)=1$ if and only if $f(\neg\psi)=0$; 

\no (c) $f(\exists x\psi(x))=1$ if and only if there is some $n$ 
with $f(\psi(c_n))=1$; 

\no (d) $f(\bigvee_{i\in\N} \psi_i)=1$ if and only if there is some 
$i\in\N$ with $f(\psi_i)=1$. 

\leftskip 0in 

We had to modify (a) a bit, so that it still corresponds to a 
closed condition. We also had to add a condition (d), which is $G_\delta$ 
by the same calculation we previously used for (c). 
With these modifications one can show that if we assign to 
each $\m\in{\rm Mod}(\l)$ the characteristic function of 
$F$-theory of its canonical expansion to a model of $\hat{\l}$, $T_\m$ where 
\[T_\m(\psi(c_{n_1}, c_{n_2},.., c_{n_k}))=1\Leftrightarrow \m\models 
\psi(n_1, n_2,..., n_k),\] 
then 
\[({\rm Mod}(\l), \tau_F)\rightarrow A_{\hat{F}}\] 
\[\m\mapsto T_\m\] 
provides a homeomorphism. 
\hfill $\Box$ 

\bigskip 

\no {\bf Definition} If $\sigma\in \lo$ is a sentence 
then we let Mod$(\sigma)$ be the collection of $\m\in {\rm Mod}(\l)$ 
satisfying $\sigma$; we let $F(\sigma)$ be the fragment generated 
by $\sigma$, and obtain from the last lemma that ${\rm Mod}(\sigma)$ 
is a Polish space in the subspace topology bequeathed by  
$\tau_{F(\sigma)}$. 

If $F$ is a countable fragment and $T\subset F$ a theory, then we let 
Mod$(T)$ be the models of $T$. This is a closed subset of $({\rm Mod}(\l), 
\tau_F)$, and hence a Polish space in the subspace topology. 

\bigskip 

\no {\bf Definition} Given a countable fragment $F$ 
we can define an 
{\it $n$-type  over $F$} to be some subset of the $F$-formulas in 
free variables $x_1, x_2,..., x_n$, and more generally we 
can define an {\it $F$-type} to be an $n$-type over $F$ for some 
for $n$. A type is {\it $F$-complete} if any $\psi(\vec x)\in F$ in the 
appropriate variables is either in the type or has its negation in $F$. 
We then say that a complete type is {\it principal} 
over a complete theory $T\subset F$ 
if it contains some $\varphi(\vec x)$ such that for all other 
and for all $\psi(\vec x)\in F$ we 
have either 
\[\forall \vec x(\varphi(\vec x)\rightarrow \psi(\vec x))\] 
or 
\[\forall \vec x(\varphi(\vec x)\rightarrow \neg \psi(\vec x)).\] 


Given a model $\m$ and $\vec a\in \m$ 
we let the {\it $F$-type over $\m$} be the set of $\psi(\vec x): 
\m\models \psi(\vec a)$. $\m$ {\it omits} an $F$-type if there is 
no $\vec a$ which has that type as its $F$-type over $\m$. 
For $F$ a fragment Th$_F(\m)$ is the set of sentences in $F$ satisfied 
by $\m$. 
We say that a model $\m$ is {\it $F$-atomic} if it realizes no non-principal 
types over Th$_F(\m)$. 

\bigskip 

These definitions out of the way, all the usual facts for first 
order logic generalize easily. 

\bigskip 

\no {\bf Lemma} Let $F$ be a countable fragment, $T\subset F$ a complete theory. 
Any two countable $F$-atomic models of $T$ are isomorphic. 


\bigskip 

\no {\bf Lemma} Let $F$ be a countable fragment. Let $\Sigma(x_1, x_2,..., x_n)$ 
be a complete non-principal type over $F$ 
and let $k_1, k_2,..., k_n\in\N$. 
Let $T\subset F$ be a complete theory.  
Then the set of 
$\m\in {\rm Mod}(T)$ 
with 
\[\m\models \Sigma(k_1, k_2,..., k_n)\] 
is closed nowhere dense (with respect to $\tau_F$). 

\bigskip 

\no {\bf Corollary} (Omitting types theorem) 
$F, T$, $\Sigma(\vec x)$ as above. The set of $\m$ 
in $({\rm Mod}(T), F)$ omitting $\Sigma(\vec x)$ is comeager 
(in $({\rm Mod}(T), F)$).  

\bigskip 

\no {\bf Lemma} Let $F$ be a countable fragment, $T\subset F$ a complete 
theory, $\m_0\in {\rm Mod}(T)$. The set of $\n\in ({\rm Mod}(T), F)$ 
isomorphic to $\m_0$ is comeager if and only if $\m_0$ is atomic. 

\no {\bf Proof} 
First suppose that $\m_0$ is atomic. Then: 

Claim: For each $\vec n\in \N^{<\N}$ 
the set of $\n \in ({\rm Mod}(T), F)$ with $\vec n$ realizing a principal type 
is open dense. 

Proof of Claim: The set is immediately open by the definition of the 
topology. To see density, let us consider some non-empty 
basic open set of the 
form 
\[V=\{\n: \n\models \psi(\vec n, \vec m)\}\] 
where $\vec m\in \N^{<\N}$ has been chosen to be disjoint from $\vec n$ 
and $\psi(\vec x, \vec y)\in F$. Then we can consider the formula 
\[\exists \vec y\psi(\vec x, \vec y)\wedge\bigwedge_{i<lh(\vec x)}\bigwedge_{j<lh(\vec y)}x_i\neq y_j.\] 
Since this is realized by some tuple in some model in our space, and since 
$\m_0$ satisfies the complete theory $T$, we may find some $\vec a\in \m_0$ 
with 
\[\m_0\models \exists \vec y\psi(\vec a, \vec y)
\wedge\bigwedge_{i<lh(\vec x)}\bigwedge_{j<lh(\vec y)}a_i\neq y_j.\] 
We then find some $\varphi(\vec x)$ with 
\[\m_0\models \varphi(\vec a)\] 
witnessing that $\vec a$ realizes some principal type. But then the set 
\[U=\{\n: \n\models \psi(\vec n, \vec m)\wedge \varphi(\vec n)\wedge\bigwedge_{i<lh(\vec x)}
\bigwedge_{j<lh(\vec y)}n_i\neq m_j\}\] 
is an open subset of $V$ all of whose elements have $\vec n$ realizing a 
principal type; to see that this set is non-empty we choose some $\vec b\in \m_0$ 
disjoint from $\vec a$ 
with $\m_0\models \varphi(\vec a, \vec b)$ and some isomorphic copy of 
$\m_0$ where $\vec n$ goes to $\vec a$ and $\vec m$ goes to $\vec b$. 
\hfill (Claim$\Box$) 

Thus we have that the set of atomic models is comeager, and since any two 
comeager models are isomorphic we are done. 

Conversely, if $\m_0$ is {\it not} atomic, then we can consider some 
principal complete type $\Sigma(\vec x)$ realized by $\m_0$. By the omitting types 
theorem the collection of models omitting   $\Sigma(\vec x)$ is comeager. 
By the 
Baire category theorem we have that this set intersects any comeager 
set. 
\hfill $\Box$ 


\bigskip 

\no {\bf Lemma}  Let $F$ be a countable fragment, $T\subset F$ a complete 
theory, $\m_0\in {\rm Mod}(T)$. 
If there is no $F$-atomic model of $T$ then the isomorphism relation is 
meager as a subset of 
\[({\rm Mod}(T), \tau_F)\times ({\rm Mod}(T), \tau_F).\] 

\no {\bf Proof} It is easily seen that the non-existence of an atomic 
model is equivalent to the principal types not being dense in the space 
of $n$-types for some $n$. So let us choose some $\psi(\vec x)$ which 
extends to no principal type. Then we have that for any $\vec n, \vec m$ 
the collection $U_{\vec m \vec n}$ 
of $(\m, \n)$ with 
\[\m\models \psi(\vec m), \] 
\[\n\models\psi(\vec n), \] 
is relatively clopen in the product space; but the subset $C_{\vec m, \vec n}$ 
consisting of 
$(\m, \n)$ over which $\vec m$ and $\vec n$ respectively realize 
the same type is a closed nowhere dense subset of $U_{\vec m, \vec n}$. 

But then we have for any $(\m, \n)$ in the comeager set 
\[\bigcap_{\vec m, \vec n}(X\setminus C_{\vec m, \vec n})\] 
there must, by completeness of $T$, be {\it some} $\vec k, \vec \ell$ 
with 
\[\m\models \psi(\vec k), \] 
\[\n\models\psi(\vec \ell). \] 
\hfill $\square$ 

\bigskip 


The above lemma is the main fact we will need about infinitary logic. There is 
one other result worth mentioning just for comparison. This further result requires 
another definition. 

\bigskip 

\no {\bf Definition} $S_\infty$ is the group of all permutations of the natural 
numbers with topology of pointwise convergence. Thus a basic open set consists 
of all bijections $\pi: \N\rightarrow \N$ with 
\[\forall i< k(\pi(i)=n_i),\] 
for some $k, n_1, n_2,..., n_k\in\N$. 

\bigskip 

$S_\infty$ is a topological group, since the group operations are all 
continuous; it is also $G_\delta$ as a subset of $\N^\N$, and hence 
Polish as a space. 

Note that $S_\infty$ acts continuously and in a canonical fashion 
on any $({\rm Mod(\l)},\l)$; and moreover its orbit equivalence relation 
is the isomorphism relation. 

\bigskip 

\no {\bf Theorem} (Becker-Kechris) Let $X$ be a standard Borel space on which 
$S_\infty$ acts in a Borel manner\footnote{I.e. the map 
\[(\pi, x)\mapsto \pi\cdot x,\] 
\[S_\infty\times X\rightarrow X\] 
is Borel}. Then there is some countable $\l$ and 
sentence $\sigma\in \lo$ and Borel isomorphism 
\[\theta: X\rightarrow {\rm Mod(\sigma)}\] 
intertwining the actions -- that is to say, for all $\pi\in S_\infty$ 
and $x\in X$ 
\[\pi\cdot\theta(x)=\theta(\pi\cdot x).\] 

\bigskip 

\no {\bf Exercises} 

\medskip 

1. Show that if $T$ is a complete theory for the countable 
fragment $F$ then 
every isomorphism type in Mod$(T)$ is dense. That is to say, if 
$\m\in$ Mod$(T)$, then the set of $\n\in$ Mod$(T)$ with 
\[\m\cong\n\] 
is dense relative to $\tau_F$. 

\medskip 



2. $T$, $F$ as above. 
Show that if the isomorphism type of $\m$ is $G_\delta$, then it is 
comeager; and moreover if $\m$ is atomic then its isomorphism type is 
$G_\delta$. 

\medskip 

3. $T$, $F$ as above. 
Show that canonical action of $S_\infty$ on $({\rm Mod}(T), \tau_F)$ 
is continuous. 

\medskip 

4. $T$, $F$ as above. 
For $\m\in ({\rm Mod}(T), \tau_F)$ we have that the induced map 
\[S_\infty\rightarrow \{\n\in {\rm Mod}(T): \n\cong\m\}\] 
\[\pi\mapsto \pi\cdot \m\]  
is open if and only if $\m$ is $F$-atomic. 

\medskip 

5. Conclude that for $T$, $F$ as above 
the following are equivalent for $\m\in ({\rm Mod}(T), \tau_F)$:  

\leftskip 0.4in 

\no (a) $\m$ is atomic; 

\no (b) the isomorphism type of $\m$ is comeager; 

\no (c) the isomorphism type of $\m$ is $G_\delta$; 

\no (d) the map $\pi\mapsto \pi\cdot \m$ is open as a map 
to the isomorphism type of $\m$. 

\leftskip 0in 


\bigskip 

For an arbitrary continuous action of a Polish group 
$G$ on a Polish space 
Ed Effros has 
shown that an orbit $[x]$ is $G_\delta$ if and only if it is comeager in its 
closure, if and only if the natural map $g\mapsto g\cdot x$ is open. 




\newpage 



\centerline{\bf {\huge Scott's analysis}}  

\bigskip 


\noindent{\bf  Definition} For $\m$ a model and $\vec a$ a finite sequence from 
$\m$ we define 
\[\varphi^{\vec a, \m}_{\alpha}\]
by induction on the ordinal $\alpha$. 
\[\varphi^{\vec a, \m}_0=\bigwedge\{\psi(\vec x): \psi(\vec x) 
\:{\rm quantifier \: free}, \: \m\models \psi(\vec a)\}\]
\[\varphi^{\vec a, \m}_{\alpha+1}= \varphi^{\vec a, \m}_{\alpha} \bigwedge\{\exists \vec y
\varphi^{\vec a\vec b, \m}_{\alpha}(\vec x, \vec y):\vec b\in\m^{<\N}\}\wedge\]
\[\bigwedge_{n\in\N}\forall y_0, y_1, ..., y_n\bigvee\{
\varphi^{\vec a\vec b, \m}_{\alpha}(\vec x, \vec y):\vec b\in\m^{n+1}\}.\]
For $\lambda$ a limit we set 
\[\varphi^{\vec a, \m}_{\lambda}=\bigwedge_{\alpha<\lambda}
\varphi^{\vec a, \m}_{\alpha}.\] 

\bigskip 

Note then that if $\m$ is a countable model of a countable 
language $\l$ then we have for each $\alpha<\omega_1$ and $\vec a\in \m$ 
\[\varphi^{\vec a, \m}_\alpha\in\lo.\] 

For $\alpha<\beta$ 
\[\m\models \varphi^{\vec a, \m}_{\beta}=\varphi^{\vec b, \m}_{\beta}\Rightarrow 
\varphi^{\vec a, \m}_{\alpha}=\varphi^{\vec b, \m}_{\alpha}.\]
Thus: 

\bigskip 

\no {\bf Lemma:} For $\m, \l$ countable there will be an ordinal 
$\delta<\omega_1$ such that for all 
$\vec a, \vec b\in\m$ 
\[\exists \gamma<\omega_1(\varphi^{\vec a, \m}_{\gamma}\neq\varphi^{\vec b, \m}_{\gamma})
\Leftrightarrow 
\varphi^{\vec a, \m}_{\delta}\neq\varphi^{\vec b, \m}_{\delta}.\] 

\bigskip 

In general such an ordinal $\delta$ with the property that 
\[\forall \vec a, \vec b\in\m(\exists \gamma (\varphi_\gamma^{\vec a, \m}\neq 
\varphi_\gamma^{\vec b, \m})\Leftrightarrow (\varphi_\delta^{\vec a, \m}\neq 
\varphi_\delta^{\vec b, \m}))\] 
will be guaranteed to exist by replacement, as we may 
take the supremum over $\vec a, \vec b\in\m$ of the least $\alpha$ (when it exists) 
with 
\[\varphi_\alpha^{\vec a, \m}\neq \varphi_\alpha^{\vec b,\m}.\] 
However it may be uncountable. For instance 
taking the usual ordering on ordinals, the Scott height of the structure 
\[(\omega_1, <)\] 
is itself $\omega_1$. 

\bigskip 


\no {\bf Definition} For $\m$ a countable model the 
least $\delta$ as in the last lemma is the {\it Scott height of} $\m$, and  
will be 
denoted by $\alpha(\m)$. 
\[\varphi_{\alpha(\m)+2}^{\emptyset, \m}=_{\rm df}\varphi^{\m}\] 
is the (canonical) {\it Scott sentence of 
$\m$}; 
\[\varphi_{\alpha(\m)+2}^{\vec a, \m}=_{\rm df}\varphi^{\vec a,\m}\] 
(or just 
$\varphi^{\vec a}$ when context indicates $\m$) 
is the {\it Scott sentence of 
$\vec a$} (in $\m$); each 
$\varphi^{\vec a, \m}_{\alpha}$ is the {\it $\alpha$th approximation of the Scott 
sentence for $\vec a$} or {\it the canonical $\alpha$-type of $\vec a$}. 

\bigskip 

Note that if $\vec a, \vec b\in \m$ with 
\[\varphi_{\alpha(\m)}^{\vec a, \m}=\varphi_{\alpha(\m)}^{\vec b, \m}\] 
then it follows from the definition of $\alpha(\m)$ that in particular 
we must have 
\[\varphi_{\alpha(\m)+1}^{\vec a, \m}=\varphi_{\alpha(\m)+1}^{\vec b, \m}.\] 


\bigskip 
\no {\bf Lemma} 
If $\varphi_{\beta}^{\vec a, \m}\neq \varphi_{\beta}^{\vec b, \m}$  
then in any other model $\n$ 
\[\n\models\forall \vec x(\varphi_\beta^{\vec a,\m} (\vec x) 
\Rightarrow \neg \varphi_\beta^{\vec b, \m}(\vec x)).\] 

\no {\bf Proof} We prove this by induction on $\beta$. It is 
obvious for $\beta=0$ and the passage through limits 
follows trivially from the structure of the definition. 

For the inductive step, assume the lemma is true at $\beta$ 
and 
without loss that 
\[\n\models \varphi_{\beta +1}^{\vec a, \m}(\vec c)\] 
and that there is some $\vec d\in\m$ with 
\[\forall \vec e \in\m(\varphi_{\beta}^{\vec a \vec d, \m}\neq 
\varphi_{\beta}^{\vec b \vec e, \m}).\] 
Then we may find some $\vec f\in\n$ with 
\[\n\models \varphi_\beta^{\vec a \vec d}(\vec c, \vec f),\] 
and hence for all $\vec e\in\m$ we have 
\[\n\models \neg\varphi_\beta^{\vec b\vec e, \m}(\vec c, \vec f).\] 
\hfill $\Box$ 




\bigskip 

\no {\bf Theorem} (Scott) Any two countable 
models satisfying the same Scott sentence 
are isomorphic. 

\no {\bf Proof} Let $\m,\n$ be countable models with 
\[\n\models\varphi^\m.\] 
Fix some ordinal $\alpha=\alpha(\m)$ as the Scott height of $\m$. 

\smallskip 

Claim: For all $\vec a \in\n$, $\vec b\in\m$ 
\[\n\models \varphi_\alpha^{\vec b, \m}(\vec a)\] 
implies that 
\[\n\models \varphi_{\alpha+1}^{\vec b, \m}(\vec a).\] 

Proof of Claim: Otherwise from the assumption that $\n$ satisfies the  
Scott sentence of $\m$ we have 
\[\n\models\forall \vec x\bigvee_{\vec c\in\m}\varphi_{\alpha+1}^{\vec c,\m}(\vec x)\] 
we may find some $\vec c\in\m$ with 
\[\n\models \varphi_{\alpha+1}^{\vec c, \m}(\vec a)\] 
\[\therefore \n\models\varphi_\alpha^{\vec c, \m}(\vec a)\] 
and so by the last lemma we must have  
\[\varphi_\alpha^{\vec c, m}=\varphi_\alpha^{\vec b, \m}\] 
\[\therefore \m\models \varphi_{\alpha}^{\vec c, \m}(\vec b)\] 
but by the assumption the claim fails 
\[\m\models\neg\varphi_{\alpha+1}^{\vec c, \m}(\vec b),\] 
with a contradiction to $\alpha$ being 
the Scott height of $\m$. 
\hfill (Claim$\square$) 

\smallskip 


But now we can just go ahead the usual back and forth kind of 
argument. We can define a sequence 
\[a_0, a_1, a_2,...\in\m,\] 
\[b_0, b_1, b_2,...\in\n,\] 
with at each $k$ 
\[\n\models\varphi_{\alpha}^{\langle a_0, a_1, ..., a_k\rangle, \m}(b_0, b_1,..., b_k)\] 
and under some fixed enumerations of the two models we have that the {\it i}$^{\rm th}$ element 
of $\m$ appears among $\{a_0,a_1,..., a_{2i}\}$ and the 
{\it i}$^{\rm th}$ element of $\n$ appears among the 
$\{b_0, b_1,..., b_{2i+1}\}$. We are able to propagate this construction 
since the claim above 
in particular implies that if 
$\m\models \varphi_\alpha^{\vec b, \n}(\vec a)$ and $d\in\n$ then 
\[\m\models \exists y \varphi_\alpha^{\vec b^\smallfrown d, \n} (\vec a, y),\] 
which is the same as saying there is some $d'\in\m$ with 
\[\m\models \varphi_\alpha^{\vec b^\smallfrown d,\n}(\vec a, d').\] 
\hfill $\square$ 

\bigskip 

This was all proved because Dana Scott wanted to show: 

\bigskip 

\no {\bf Corollary} The isomorphism type of any countable model is 
Borel in Mod$(\l)$. 

\bigskip 

It has previously been shown that the isomomorphism type of any 
{\it countable ordinal} is Borel in Mod$(\{<\})$; indeed it is a nice exercise 
to prove this by induction on the ordinal, without any appeal to 
the Scott analysis. With this result in mind Kuratowski had asked 
whether the isomorphism type of any countable structure was Borel, 
which in turn was explicitly answered as above. 

\bigskip 

\no {\bf Exercises} 

\medskip 

1. $F$ a countable fragment and $T$ an $F$-complete theory. 
The  isomorphism type of any $\m\in ({\rm Mod}(T), \tau_F)$ has Baire 
property and is non-meager if and only if it is comeager. 

\medskip 

2. Let $\l$ be a countable 
language and  $(F_\alpha)_{\alpha\in\omega_1}$ 
be an increasing sequence of countable fragments in $\lo$. 
Suppose $\m\in$ Mod$(\l)$ is fortunate enough 
that for each $\alpha$ and $\vec a\in\m$ there is some $\psi(\vec x)\in F_{\alpha+1}$ 
such that  
\[\m\models \psi(\vec a)\] 
\[\m\models \forall \vec x \forall \vec y\bigwedge_{\varphi\in F_\alpha} 
(\psi(\vec x)\wedge \psi(\vec y)\Rightarrow (\varphi(\vec x)\Leftrightarrow \varphi(\vec y)));\] 
in other words, for each $\vec a$ 
there is some formula in $F_{\alpha+1}$ satisfied by $\vec a$ which ``isolates its 
type over $F_\alpha$''. 

Then show that there is some countable $\gamma<\omega_1$ with $\m$ atomic relative to 
the fragment $F_\gamma$ and the theory Th$_{F_\gamma}(\m)$. 

\medskip 

3. Show that if $\delta$ is the Scott height of a countable model then 
we have {\it for all} ordinals $\gamma$ 
\[\varphi_\gamma^{\vec a, \m}\neq 
\varphi_\gamma^{\vec b, \m}\Rightarrow \varphi_\delta^{\vec a, \m}\neq 
\varphi_\delta^{\vec b, \m}.\] 

\medskip 

4. (a) Show that if $T\subset F$ is a complete theory then 
\[\{\varphi_0^{\vec a, \m}: \m\models T, \vec a\in\m\}\] 
is a Borel set in some standard Borel structure; and hence has 
size continuum or $\leq\aleph_0$. 

(b)  Show that if $\sigma$ is sentence appearing in some fragment $F$ then 
the collection of countable complete ``consistent''\footnote{Of course I 
have been trying to avoid use of this word in the context of infinitary 
model theory. Here I mean that the theory has some model.} 
$T\subset F$ containing $\sigma$ 
is a Borel set. 



(c) Conclude that for any $\sigma\in\lo$ 
\[\{\varphi_0^{\vec a, \m}: \m\models \sigma, \vec a\in\m\}\]
is either countable or has cardinality $2^{\aleph_0}$.  


(d) Iterating the argument of (a)-(c) show that for any 
$\sigma\in\lo$ and $\alpha<\omega_1$ 
\[\{\varphi_\alpha^{\vec a, \m}: \m\models \sigma, \vec a\in\m\}\]
is either countable or has cardinality $2^{\aleph_0}$.  

(e) (``Morley's lemma'') Show that 
if $\sigma$  has less than continuum many non-isomorphic 
countable models then it has $\leq\aleph_1$ many non-isomorphic 
countable models. 

\bigskip 

Actually the proof of the main theorem we are heading towards 
parallels the above argument due to Morley. 
There again is a kind of transfinite induction, where the failure at 
each level for their being ``lots of models'' gives us the ability 
to perform one further step of the analysis. 

In Morley's lemma ``lots of models'' corresponds to $2^{\aleph_0}$ many 
countable models; and the technical tool used at each step is the 
perfect set theorem for Borel sets. In our setting the ``lots of models'' 
case will correspond to an embedding of $E_0$ and the central technical 
device is a version of Glimm-Effros due to Becker and Kechris. 




\newpage 

\centerline{\bf {\huge Glimm-Effros}} 

\bigskip 

\no {\bf Theorem} (Becker-Kechris) Let $E$ be an equivalence relation on a 
Polish space $X$ and  
let $G$ be a group acting by homeomorphisms on $X$. Then assuming 

\leftskip 0.4in 

\no (a) $E$ is meager as a subset of $X\times X$, and 

\no (b) for all $g\in G, x\in X$ we 
have 
\[g\cdot x E x\] 
(that is to say, the orbit equivalence relation induced by $G$ is included 
in $E$), and 

\no (c) there is some $x_0\in X$ with $[x_0]_G=_{\rm df}
\{g\cdot x_0| g\in G\}$ dense, 

\leftskip 0in 

\no then 
\[E_0\leq_B E.\] 

\no {\bf Proof} Fix a complete metric $d$ on $X$ and a point 
$x_0\in X$ whose orbit under the action of $G$ is dense.  
Let $(F_n)_{n\in\N}$ be a countable sequence of closed nowhere 
dense subsets of $X\times X$ with 
\[E\subset \bigcup_{n\in\N} F_n.\] 


The theorem is proved by a construction. We build a sequence 
of non-empty 
open sets $(V_s)_{s\in 2^{<\N}}$ in $X$ and an array of 
group elements $\{(g_{s, t})_{s, t\in \{0,1\}^n}: n\in\N\}$ 
such that: 

\medskip 

\leftskip 0.4in 

\no (i) for $s:\{0,1...,n-1\}\rightarrow \{0,1\}$ we have 
\[d(V_s)<\frac{1}{n};\] 

\smallskip 

\no (ii) 
\[V_s\subset V_t\] 
for $s\supset t$ and moreover 
\[\overline{V_s}\subset V_t\] 
if $t\subsetneq s$; 

\smallskip 

\no (iiia) for $s, t\in 2^n$ and $u\in 2^{<\N}$ 
we have 
\[g_{s, t}\cdot V_{s^\smallfrown u}=V_{t^\smallfrown u};\] 

\no (iiib) and in fact if $\vec 0$ is the sequence of all zeroes of length 
$n$ and $s, t\in 2^n$ then we have 
$g_{s, t}=g_{\vec 0, t}\circ g_{\vec 0, s}^{-1}$; 

\no (iiic) for $s, t\in 2^n$ and $u\in 2^{<\N}$ 
we have 
\[g_{s, t}=g_{s^\smallfrown u, t^\smallfrown u};\] 


\smallskip 

\no (iv) for $s, t\in 2^n$ with $s\neq t$ we 
have 
\[V_s\times V_t\cap (\bigcup_{m\leq n}F_m)=\emptyset.\] 

\leftskip 0in 

\smallskip 

If we succeed in doing all this, then the theorem 
follows quickly. We define for each $f\in 2^\N$ a 
corresponding 
\[x_f\in \bigcup_{n\in\N} V_{f|_n}.\] 
There will be a unique such point $x_f$ in the infinite intersection 
by (i) and (ii); and then by the nature of the construction we 
have 
\[f\mapsto x_f\] 
as a Borel, in fact continuous, map. 
>From (iiia) we have that if $N\in\N$ is the largest integer with 
$f_1(N-1)\neq f_2(N-1)$ then 
\[g_{f_1|_N, f_2|_N}\cdot x_{f_1}=x_{f_2}\] 
and thus 
\[x_{f_1} E_0 x_{f_2}.\] 
(iv) moreover yields that if there are infinitely many 
$n$ with $f_1(n)\neq f_2(n)$ then there are infinitely many 
$n$ with 
\[(x_{f_1}, x_{f_2})\notin \bigcup_{m\leq n} F_n,\] 
and so 
\[(x_{f_1}, x_{f_2})\notin E\subset \bigcup_{n\in\N}F_n.\] 

So let us now concentrate on showing that some such sequence of open 
sets and array of group elements has been produced. We do it by 
induction on $lh(s)$, and for this purpose assume that 
$(V_s)_{s\in 2^{\leq n}}$  
and $\{(g_{s, t})_{s, t\in \{0,1\}^m}: m\leq n\}$ 
have the properties indicated above. 
We will begin by refining the open set $V_{\vec 0}$, where $\vec 0$ is 
the sequence of length $n$ which takes zero as its value on each 
coordinate. 

Remember that the group $G$ is acting by homeomorphisms, and so 
\[\{(x, y): (g\cdot x, h\cdot y)\in F\}\] 
is closed nowhere dense for any $g,h\in G$ and closed nowhere 
dense $F\subset X\times X$. 
Moreover the finite union of closed nowhere dense sets is 
again closed nowhere dense. 

Thus we may chose some open non-empty $W, W'\subset V_{\vec 0}$ such that 
for all $g, h\in \{(g_{s, t})_{s, t \in\{0,1\}^m}: m\leq n\}$ 
\[g\cdot W\times h\cdot W'\cap (\bigcup_{m\leq n+1}F_m)=\emptyset.\] 
After further refinement we may assume that 
\[d(g\cdot W), d(g\cdot W')<\frac{1}{n+1}\] 
and 
\[\overline{g_{\vec 0, s}\cdot W}, \overline{g_{\vec 0, s}\cdot W'}\subset V_s\] 
all $s\in 2^n$. 

Then since $[x_0]_G$ is dense we may choose 
\[x\in W\cap [x_0]_G,\]
\[x'\in W'\cap [x_0]_G.\] 
In particular there will be some $h_0\in G$ with 
\[h_0\cdot x=x'.\] 
Since $G$ acts by homeomorphisms we may find $V_{\vec 0^\smallfrown 0}\subset W$,  
$V_{\vec 0^\smallfrown 1}\subset W'$ with 
\[h_0\cdot V_{\vec 0^\smallfrown 0}=V_{\vec 0^\smallfrown 1}.\] 

At this stage we can finish up with 
\[V_{s^\smallfrown 0}=
g_{\vec 0, s}\cdot V_{\vec 0^\smallfrown 0},\] 
\[V_{s^\smallfrown 1}=g_{\vec 0, s}h_0\cdot V_{\vec 0^\smallfrown 0}=g_{\vec 0, s}\cdot V_{\vec 0^\smallfrown 1},\] 
\[g_{\vec 0^\smallfrown 0, s^\smallfrown 1}=g_{\vec 0, s}\circ h_0,\] 
for $s\in 2^n$.  
The decisions 
\[g_{\vec 0^\smallfrown 0, s^\smallfrown 0}=g_{\vec 0, s}\] 
\[g_{s^\smallfrown i, t^\smallfrown i}=g_{s, t}\] 
all $s, t\in 2^n$, $i\in\{0, 1\}$ are forced on us by (iiib) 
and (iiic). 
Taking 
\[g_{s^\smallfrown 0, t^\smallfrown 1}=g_{\vec 0, t}\circ h_0 \circ g_{\vec 0, s}^{-1}\] 
and 
\[g_{s^\smallfrown 1, t^\smallfrown 0}=g_{t^\smallfrown 0, s^\smallfrown 1}^{-1}\] 
provides us with the full armory of group elements to go up to $n+1$. 
\hfill $\square$ 

\bigskip 

\no {\bf Corollary} Let $F\subset\lo$ be a countable fragment, $T\subset F$ a 
complete theory. Then either 
\[E_0\leq_B \cong\:|_{{\rm Mod}(T)}\] 
or there is an $F$-atomic model. 

\no {\bf Proof} Completeness of the theory gives that every 
isomorphism type is dense in (Mod$(T), \tau_F)$. The orbit equivalence 
relation is induced by a continuous action of the infinite symmetric 
group, $S_\infty$, and so we can use the previous lemma to conclude that 
either 
\[E_0\leq_B \cong\:|_{{\rm Mod}(T)}\] 
or the orbit equivalence relation is not meager; and in this later case 
we saw two sections ago that we must have an atomic model. 
\hfill $\square$

\bigskip 

\no {\bf Definition} A topological group\footnote{That is to say, a group 
equipped with a topology under which the group operations of multiplication 
and inversion are continuous.} is a {\it Polish group} if it is Polish as a 
topological space. 

\bigskip 

\no{\bf Exercises}  

\medskip 

1. Let $G$ be a Polish group acting continuously on a Polish space $X$. 
Show that there is a Borel function 
\[\theta: X\rightarrow\R\] 
such that $\theta(x_1)=\theta(x_2)$ if and only if the orbits 
of $x_1$ and $x_2$ have the same closure. 

\medskip 

2. Let $G$ be a locally compact Polish group acting 
continuously on a Polish space $X$ with orbit equivalence relation 
$E_G$. 

(a) Show that $E_G$ is $F_\sigma$ as a subset of $X\times X$. 

(b) Show that if there is dense orbit then it must contain an open 
set. 

(c) Show that in general, even without a dense orbit, we have either 
\[E_G\leq {\rm id}(\R)\] 
or 
\[E_0\leq_B E_G.\] 


\bigskip 




\newpage 


\centerline{\bf {\huge Final theorem}}

\bigskip 

\no {\bf Definition} HC denotes the collection of hereditarily 
countable sets. A formula $\psi(\vec x)$ in the language of set theory 
is $\Sigma_0$ if the only quantifiers appearing are the bounded 
quantifiers 
\[\forall x\in y\] 
\[\exists x\in y.\] 

A subset $A\subset$ HC is said to be $\Ubf{\Sigma}_1^{\rm HC}$ 
if there is some $\Sigma_0$ formula $\psi$ and parameter $a\in $ HC such 
that $A$ equals the set of $b\in $ HC for which 
\[(HC, \in)\models\exists x \psi(a, b, x).\] 
$D\subset$ HC is $\Ubf{\Delta}_1^{\rm HC}$ if both it and its 
complement are $\Ubf{\Sigma}_1^{\rm HC}$. 
I will say that a function is $\Ubf{\Delta}_1^{\rm HC}$ if its 
graph and domain are both 
$\Ubf{\Delta}_1^{\rm HC}$. 

\bigskip 

It will be convenient to phrase the next result in terms of 
$\Ubf{\Delta}_1^{\rm HC}$ reductions; but I will skip over 
any detailed verifications about certain functions and sets 
appearing in the definition being $\Ubf{\Delta}_1^{\rm HC}$. 
Instead here are some facts without proof. 
For many of these facts there are 
similar facts with similar proofs 
holding for the recursive 
functions. 

\bigskip 

\no {\bf Facts} 

1. Ordinal addition, multiplication, and exponentiation are 
$\Ubf{\Delta}_1^{\rm HC}$. 

2. If 
\[G: \omega_1\times {\rm HC}\rightarrow {\rm HC}\] 
\[H: {\rm HC}\rightarrow {\rm HC}\]  
$\Ubf{\Delta}_1^{\rm HC}$, then so is the function defined 
recursively by 
\[F(\alpha +1)=H(G(\alpha, F(\alpha)))\] 
and 
\[F(\lambda)=\bigcup \{F(\alpha): \alpha<\lambda\}\] 
when $\lambda$ a limit. 

3. For $a\in$ HC 
\[\alpha\mapsto L_\alpha(a)\] 
is $\Ubf{\Delta}_1^{\rm HC}$, where we here use $L_{\alpha}(a)$ to 
denote the $\alpha^{\rm th}$ level of the constructible hierarchy 
built over $a$. 

4. The $\Ubf{\Delta}_1^{\rm HC}$ recursive functions are closed under 
$\mu$-recursion with respect to the ordinals. Thus if for each 
$z\in $ HC there exists $\alpha<\omega_1$ with 
\[L_{\alpha}(z, a)\models \psi(a, z),\] 
then the function assigning to each $z$ the least such $\alpha$ is 
$\Ubf{\Delta}_1^{\rm HC}$. 

5. Given $\l$ a countable language, there is a 
$\Ubf{\Delta}_1^{\rm HC}$ function assigning to each 
$\m\in {\rm Mod}(T)$ and countable fragment $F\subset \lo$ 
the theory of $\m$ in that fragment. 

6. Every {\it set recursive function} (in the sense of Garvin Melles) 
is $\Ubf{\Delta}_1^{\rm HC}$; and in fact the theorem below could 
equally be phrased in terms of set recursive functions instead of 
$\Ubf{\Delta}_1^{\rm HC}$. 

\bigskip 

\no {\bf Theorem} Let $\l$ be a countable language and $\sigma\in\lo$. 
Then either 

\leftskip 0.4in 

\no (I) $E_0\leq_B\cong\!|_{{\rm Mod}(\sigma)}$; or 

\no (II) there is a $\Ubf{\Delta}_1^{\rm HC}$ function 
\[\theta: {\rm Mod}(\sigma)\rightarrow 2^{<\omega_1}\] 
such that for all $\m,\n\in{\rm Mod}(\sigma)$ 
\[\m\cong\n\Leftrightarrow \theta(\m)=\theta(\n).\] 

\leftskip 0in 

In other words, $\cong\!|_{{\rm Mod}(\sigma)}$ is either as 
complicated as $E_0$ or allows a $\Ubf{\Delta}_1^{\rm HC}$ 
assignment of bounded subset of 
$\aleph_1$ as complete invariants. 

\no {\bf Proof} 
Assume $E_0$ is not Borel reducible to $\cong\!|_{{\rm Mod}(\sigma)}$; 
by the corollary to Becker-Kechris this will ensure that we have 
many atomic models, no matter which fragment we choose to consider. 

First fix a fragment $F_0$ containing $\sigma$. For each $\alpha<\omega_1$ 
and positive integer $n$ let $P_{\alpha, n}$ be a new $n$-ary relation; we can 
do this so that 
\[(\alpha, n)\mapsto P_{\alpha, n}\] 
is a $\Ubf{\Delta}_1^{\rm HC}$ function. We let $\l^\alpha$ be the language generated 
by $\l$ and $\{P_{\beta, n}: n>0, \beta<\alpha\}$ and we let $F_\alpha\subset 
\l^\alpha_{\omega_1, \omega}$ be the fragment generated by $F_0$ and all formulas 
of the form 
\[\bigvee_{\{\beta: \gamma\leq \beta <\gamma'\}}P_{\beta, n}(\vec x)\] 
for $\gamma<\gamma'\leq \alpha$. 
We may simultaneously fix a $\Ubf{\Delta}_1^{\rm HC}$ 
increasing sequence of ordinals, 
\[(\gamma_\alpha)_{\alpha\in\omega_1}\] 
and bijections 
\[\pi_\alpha: \gamma_\alpha \rightarrow F_\alpha\] 
which are uniformly $\Ubf{\Delta}_1^{\rm HC}$, 
in the sense that 
\[(\alpha, \beta)\mapsto \pi_\alpha(\beta)\] 
is a $\Ubf{\Delta}_1^{\rm HC}$ function. 

Fix $\m\in {\rm Mod}(\sigma)$. We describe a a sequence of expansions 
\[\m_0=\m, \m_1,\cdots, \m_\alpha\cdots\] 
out through the ordinals, the isomorphism type of each $\m_\alpha$ depending 
only on the isomorphism type of $\m$ and 
each $\m_\alpha$ an $\l^\alpha$-structure; at 
each $\alpha$ we let $T^\m_\alpha$ be the theory of $\m_\alpha$ with 
respect to the fragment $F_\alpha$. 

Thus in particular we begin with 
\[T^\m_0={\rm Th}_F(\m),\] 
the theory of $\m$ with respect to $F$. 

\medskip 

Claim: $T_0^\m$ has an atomic model. 

Proof of Claim: Or else Becker-Kechris gives 
\[E_0\leq_B \cong\!|_{{\rm Mod}(T^\m_0)},\] 
\[\therefore E_0\leq_B \cong\!|_{{\rm Mod}(\sigma)}.\]
\hfill ($\Box$Claim) 

\medskip 

We then define $\m_1$ to be the expansion of $\m$ to $\l^1$ 
as follows. For each $a_1, a_2, ..., a_n\in\m$ we let 
\[\m_1\models P_{0,n}(\vec a)\] 
if and only if $\vec a$ realizes a principal type relative 
to the theory $T^0_\m$. Then we let $T^\m_1$ be the theory of 
$\m_1$ relative to the fragment $F_1$. 

And we can keep going in the obvious way. We let 
\[T_\alpha^\m={\rm Th}_{F_\alpha}(\m_\alpha);\] 
$\m_{\alpha+1}$ is the expansion to $\l^{\alpha+1}$ obtained 
by letting 
\[\m_{\alpha+1}\models P_{\alpha, n}(\vec a)\] 
if $lh(\vec a)=n$ and $\vec a$ realizes a principal type over 
the theory $T_\alpha^\m$. At limit stages we can let 
$\m_\lambda$ be the unique model in the language 
\[\l^\lambda=\bigcup_{\alpha<\lambda}\l^\alpha\] 
which expands the all the preceding 
\[\{\m_\alpha: \alpha<\lambda\}.\] 

One possibility is that regardless of our particular choice of 
$\m$ we always arrive at some $F_\kappa$ with $\m_\kappa$ the 
$T^{\m}_\kappa$-atomic model for $F_\kappa$. Then we are done. We 
can just let $\kappa(\m)$ be the first such $\kappa$ for $\m$ and 
let 
\[\theta(\m)=\{\beta<\gamma_{\kappa(\m)}: \m_{\kappa(\m)}\models \pi_{\kappa(\m)}(\beta)\}
\cup\{\gamma_{\kappa(\m)}\}\] 
to obtain an invariant which indicates to us $\gamma_{\kappa(\m)}$, and hence $\kappa(\m)$, 
and hence 
the 
fragment $F_{\kappa(\m)}$, as well as the theory $T^\m_{\kappa(\m)}$ and the fact that 
$\m_{\kappa(\m)}$ is atomic with respect to this theory; since each complete countable 
theory has at most one atomic model up to isomorphism, the invariant 
indicates the isomorphism type of $\m_{\kappa(\m)}$; since $\m_{\kappa(\m)}$ 
is up to isomorphism an invariant of $\m$, we obtain that $\theta(\m)$ is a 
complete invariant for the isomorphism type of $\m$. And finally in this 
case it would be routine to establish that the association 
\[\m\mapsto \theta(\m)\] 
is $\Ubf{\Delta}^{\rm HC}_1$. 

So instead let us try to show that some such ordinal $\kappa(\m)$ 
always exists. And for this let us assume that $\m$ is a counterexample 
and try to derive a contradiction. 

  

\medskip 

Claim: For each $n>0$ and $\delta<\omega_1$ there is a larger countable ordinal 
$\delta'>\delta$ 
such that for each $a_1, a_2,..., a_n\in \m$ 
\[\m_{\delta'}\models\bigvee_{\alpha\in[\delta, \delta')}P_{\alpha, n}(\vec a).\] 

Proof of Claim: Instead we obtain that each $\delta'$ 
\[\m_{\delta'}\models\exists 
\vec x \bigwedge_{\alpha\in[\delta, \delta')}\neg P_{\alpha, n}(\vec x).\]
Since $T^\m_\delta$ has an atomic model, by Becker-Kechris, we obtain some 
principal type refining the type 
\[\bigwedge_{\alpha\in[\delta, \delta')}\neg P_{\alpha, n}(\vec x),\] 
and thus by the nature of our construction 
some $\vec a^{\:\delta'}$ with 
\[\m_{\delta'+1}\models P_{\delta'}(\vec a^{\: \delta'})
\bigwedge_{\alpha\in[\delta, 
\delta ')}\neg P_{\alpha, n}(\vec a^{\:\delta'});\] 
but then 
\[\delta'\mapsto \vec a^{\: \delta'}\] 
gives us $\aleph_1$ distinct $n$-tuples in $\m$, with an obvious 
contradiction to its countability. 
\hfill (Claim$\Box$) 

\medskip 

Thus by repeated application of this claim we can find an 
increasing sequence of ordinals, 
\[(\delta_\alpha)_{\alpha<\omega_1},\] 
such that for each $\alpha\in\omega_1$, $n>0$, $\vec a\in\m^n$ there is 
some 
\[\beta>\bigcup_{\alpha'<\alpha}\delta_{\alpha'}\] 
with 
\[\beta\leq \delta_\alpha\] 
and 
\[\m_{\delta_\alpha}\models P_{\beta, n}(\vec a).\] 

We may also fix for each $\beta<\omega_1$ and $n>0$ a 
sequence of formulas $(\psi^m_{\beta, n})_m$ such that 
\[\m_{\beta+1}\models\forall x_1, x_2, ..., x_n 
(P_{\beta, n}(\vec x)\Leftrightarrow \bigvee_{m\in\N}\psi^m_{\beta, n}(\vec x))\] 
and each $\psi^m_{\beta, n}(\vec x)\in F_\beta$ defines a principal 
type over $T^\m_\beta$. Unfortunately the disjunction 
$\bigvee_{m\in\N}\psi^m_{\beta, n}(\vec x)$ has not been placed in any of our 
fragments, so we need to observe that the equivalence 
\[\n\models\forall x_1, x_2, ..., x_n 
(P_{\beta, n}(\vec x)\Leftrightarrow \bigvee_{m\in\N}\psi^m_{\beta, n}(\vec x))\]
holds for any sufficiently ``generic'' $\n$ 
in the space of $T^\m_\beta$ models, 
for any $\alpha>\beta$. 
 
\medskip 

Claim: For each $n>0$, $\vec a\in\N^n$ and $\beta<\alpha$, the set of 
\[\n\in ({\rm Mod}(T^\m_\alpha), \tau_{F^\m_\alpha})\] 
with 
\[\n\models P_{\beta, n}(\vec a)\Leftrightarrow 
\bigvee_{m\in\N}\psi^m_{\beta, n}(\vec a)\] 
is open dense. 

Proof of Claim: It is a straight calculation to determine that the 
set of such $\n$ is open. 
For density we use 
that the isomorphism type of $\m_\alpha$ is dense in 
$({\rm Mod}(T^\m_\alpha, \tau_{F^\m_\alpha})$ and 
\[\m_{\beta}\models\forall x_1, x_2, ..., x_n 
(P_{\beta, n}(\vec x)\Leftrightarrow \bigvee_{m\in\N}\psi^m_{\beta, n}(\vec x)).\]  
\hfill (Claim$\Box$) 

\medskip 

Thus for each $\alpha$ there is a comeager set 
\[C_\alpha\subset ({\rm Mod}(T^\m_\alpha), \tau_{F^\m_\alpha})\] 
such that for all $\beta<\alpha, n>0, \n\in C_\alpha$ 
\[\n\models\forall x_1, x_2, ..., x_n 
(P_{\beta, n}(\vec x)\Leftrightarrow \bigvee_{m\in\N}\psi^m_{\beta, n}(\vec x)).\] 


In the next claim I will use $\n\!|_\l$ to indicate the reduction of some $\l^\alpha$ model 
to our base language $\l$. As usual, 
\[\varphi^{\vec \ell, \n\!|_\l}_\kappa\] 
will indicate the $\kappa^{\rm th}$ approximation to the Scott sentence of 
$\vec \ell$ over $\n\!|_\l$. 

\medskip 

Claim: For each $\n\in C_\alpha$, 
$\delta_\kappa\leq\beta<\alpha<\omega_1$, $n>0$, $m\in\N$, $\vec \ell, 
\vec k\in\N^n$ we have 
that if 
\[\m_\alpha\models\psi^m_{\beta, n}(\vec k)\] 
and 
\[\n\models\psi^m_{\beta, n}(\vec \ell)\]
then 
\[\varphi^{\vec \ell, \n\!|_\l}_\kappa =
\varphi^{\vec k, \m}_\kappa.\] 

Proof of Claim: We prove this by induction on $\kappa$. It should be clear 
for $\kappa=0$, since $\psi^m_{\beta, n}\in F_0$ defines a principal type 
over $F_0$, and thus is sufficient to decide the quantifier free type, even 
if $\n$ does not belong to our comeager set $C_\alpha$. The limit steps 
follow almost vacuously from the structure of the Scott analysis and its 
requirement that we take conjunctions at limit stages. 

For successor steps, let us suppose 
$\delta_{\kappa+1}\leq\beta<\alpha<\omega_1$, 
\[\m_\alpha\models\psi^m_{\beta, n}(\vec k),\] 
and 
\[\n\models\psi^m_{\beta, n}(\vec \ell).\] 

Choose some $\vec a\in\n$; we need to show that there is some 
other $\vec b\in\m$ with 
\[\varphi^{\vec \ell\vec a, \n\!|_\l}_\kappa =
\varphi^{\vec k\vec b, \m}_\kappa.\] 
But since $\n$ and $\m_\beta$ realize the same the theory it must be 
the case that there 
\[\n\models \forall x_1, ..., x_n \bigvee_{\{\beta': \gamma_\kappa\leq\beta'<  
\gamma_{\kappa+1}\}}P_{\beta', n}(\vec x),\]
and thus in particular for some 
$\beta'\in [\gamma_\kappa, \gamma_{\kappa +1})$ and $n'=lh(\vec \ell)+lh(\vec a)$ 
we have 
\[\n\models P_{\beta', n'}(\vec \ell, \vec a);\] 
then by assumption on $\n\in C_\alpha$ 
we have some $m'$ with 
\[\n\models\psi^{m'}_{\beta', n'}(\vec \ell, \vec a);\] 
then since $\psi^m_{\beta, n}$ decides the type of 
$\vec k$ over the fragment $F_{\beta'}$ we have 
\[\m_\alpha\models\exists \vec y\psi^{m'}_{\beta', n'}(\vec k,\vec y);\]  
and so for some 
$\vec b$ 
\[\m_\alpha\models\exists \vec y\psi^{m'}_{\beta', n'}(\vec k,\vec k)\] 
and so by the inductive assumption 
\[\varphi^{\vec \ell\vec a, \n\!|_\l}_\kappa =
\varphi^{\vec k\vec b, \m}_\kappa.\] 

The converse direction is that for all $\vec b\in\m$ there is 
$\vec a\in\n$ with 
$\varphi^{\vec \ell\vec a, \n\!|_\l}_\kappa =
\varphi^{\vec k\vec b, \m}_\kappa.$ This is similar, but only 
easier. 
\hfill (Claim$\Box$) 

\medskip 

Thus we obtain in particular that 
for any $\alpha> \alpha(\m)+2$ and $\n\in C_\alpha$  
\[\varphi^{\emptyset, \n\!|_\l}_{\alpha(\m)+2} =
\varphi^{\emptyset, \m}_{\alpha(\m)+2},\] 
and thus by Scott's theorem
\[\n\!|_\l\cong\m;\] 
but then it follows from the definition of the various 
$\m_\beta$'s that the isomorphism from 
$\n\!|_\l$ to $\m$ lifts to one from $\n$ to $\m_\beta$ for 
each $\beta<\alpha$. 

Thus the isomorphism type of $\m_\alpha$ {\it will} be 
comeager in some 
\[({\rm Mod}(T^\m_\alpha), \tau_{F^\m_\alpha});\]
and thus $\m_\alpha$ {\it will} be atomic, and so the 
process must have terminated at some stage after all. 
\hfill $\Box$. 

\bigskip 

In general this theorem can be improved by slightly sharpening the 
reduction to one that is {\it provably} or 
{\it absolutely} $\Ubf{\Delta}^{\rm HC}_1$; these complexity classes 
are a little technical to define\footnote{See e.g. {\bf Classification and 
orbit equivalence relations}, G. Hjorth, AMS, Rhode Island, 2000 for the 
precise definitions}, but have the advantage of 
being just inside the region for which ZFC alone can prove regularity 
properties, such as any {\it absolutely} $\Ubf{\Delta}^{\rm HC}_1$ 
function between Polish spaces is continuous on a comeager set. 
In this sharper form the theorem would then become a dichotomy 
theorem: (I) and a suitably amended version of (II) would be 
incompatible. 

A respect in which the theorem cannot be sharpened is with regards to 
the {\it kinds of} invariants we obtain in (II). For instance we 
cannot ask that we have say elements of $2^\N$ being assigned as 
complete invariants. The isomorphism relation on abelian $p$-groups 
provides a counterexample under suitable set theoretical assumptions for 
general $\Ubf{\Delta}^{\rm HC}_1$ functions and outright in ZFC for 
the  absolutely $\Ubf{\Delta}^{\rm HC}_1$. 

However this class is not first order definable, so I don't know whether 
one might hope to prove that for any first order theory $T$ we have either 
have 

\medskip 

\leftskip 0.4in 

\no (I) $E_0\leq_B \cong\!|_{{\rm Mod}(T)}$, or 
 
\no (II') $\cong\!|_{{\rm Mod}(T)}\leq_B$ id$(2^\N)$. 

\leftskip 0in 

\medskip 

\no Even showing this with (II') replaced by 

\medskip 

\leftskip 0.4in 

\no (II'') there is a $\Ubf{\Delta}_1^{\rm HC}$ assignment of 
elements of $2^\N$ as complete invariants. 

\leftskip 0in 

\medskip 

\no would be extremely interesting, and sufficient to prove Vaught's 
conjecture under large cardinal assumptions, or even prove Vaught's conjecture 
outright in ZFC if, as most likely, one could obtain 


\medskip 

\leftskip 0.4in 

\no (II$^*$) there is an absolutely $\Ubf{\Delta}_1^{\rm HC}$ assignment of 
elements of $2^\N$ as complete invariants. 

\leftskip 0in


\medskip 

\newpage 

\centerline{\bf {\huge More reading}}

\bigskip 

There is always more to read, but in this case especially there 
are a number of issues we only touched on which could have been 
discussed at length. 

\bigskip 

The canonical references for the descriptive set theory of group actions 
connections with the isomorphism relation on countable models  are 

\medskip

\leftskip 0.4in 

\no H. Becker, A.S. Kechris, {\bf The descriptive set theory of 
Polish group actions}, London Mathematical Society Lecture Notes Series, 
232, Cambridge University Press, Cambridge, 1996 

\medskip

\leftskip 0in 

\no and 

\leftskip 0.4in 

\medskip

\no R. Sami, {\it The topological Vaught conjecture}, 
{\bf Transactions of the 
American Mathematical Society}, vol. 341(1994), pp. 335-353. 


\medskip

\leftskip 0in  

The serious mathematical discussion of dichotomy theorems for Borel equivalence 
relations was initiated in 

\leftskip 0.4in 
 
\medskip

\no  L.A. Harrington, A.S. Kechris, 
A. Louveau, {\it A Glimm-Effros dichotomy for 
Borel equivalence relations,} {\bf Journal 
of the American Mathematical Society,} 
vol. 3(1990), pp. 903-928.  

\medskip

\leftskip 0.4in 

\no A more recent survey is given by 

\medskip

\leftskip 0.4in 

\no  G. Hjorth, 
A.S. Kechris, {\it New dichotomies for 
Borel equivalence relations}, {\bf Bulletin of Symbolic Logic}, vol. 3(1997), 
pp. 329--346. 

\leftskip 0in 

\medskip


A continued discussion of some of the material above, in much the same  
elementary style, is given by 


\leftskip 0.4in 

\medskip

\no G. Hjorth, 
{\bf Classification and orbit equivalence relations,} Mathematical Surveys
and Monographs, 75,  American Mathematical Society, Providence, RI, 2000. 

\leftskip 0in 

\medskip

\no This includes some easy proofs of some things we didn't quite get to, such 
as $F_2$ not being Borel reducible to any of the countable Borel equivalence 
relations, such as $E_0$. 

The main theorem, which we finished with, was first presented in 

\medskip

\leftskip 0.4in 

\no  G. Hjorth, A.S. Kechris, {\it 
Analytic equivalence relations 
and Ulm-type classifications,} 
{\bf Journal of Symbolic Logic,} vol. 60(1995), pp. 1273-1300, 

\leftskip 0in

\medskip

\no and is also independently due to Howard Becker. 
The proof given there is rather different, in that it is derived as a 
corollary of Harrington-Kechris-Louveau; and indeed in this paper the 
main battle was to extend the result to general 
$\Ubf{\Sigma}^1_1$ equivalence relations, while above we have been 
primarily concerned with developing an argument that uses no 
non-trivial descriptive set theory. 

If there had been more time we might have discusses special versions of 
this dichotomy theorem which can be proved for specific classes of 
Polish groups. Then one often can hope to replace (II) by 

\medskip

\leftskip 0.4in  

\no (II') $\cong\!|_{{\rm Mod}(T)}\leq_B$ id$(2^\N)$.

\leftskip 0in 

\medskip

In 

\leftskip 0.4in 

\medskip

\no G. Hjorth, S. Solecki, 
{\it Vaught's conjecture and the Glimm-Effros property for 
Polish transformation groups,} 
{\bf Transactions of the American Mathematical Society,} vol. 351(1999), 
pp. 2623-2641

\leftskip 0in 

\medskip

\no this was done for the orbit equivalence relations induced by 
continuous actions of nilpotent and invariantly metrizable Polish 
groups, while 

\leftskip 0.4in 

\medskip

\no H. Becker, 
{\it The topological Vaught's conjecture and minimal counterexamples,} 
{\bf Journal of Symbolic Logic,} vol. 59(1994), pp. 757-784  

\medskip

\leftskip 0in 

\no obtained more general results for solvable or under the assumption of a 
complete left invariant metric. 

A rather different approach to some of these questions can be found 
in 

\leftskip 0.4in 

\medskip

\no G. Melles, {\it One cannot show from ZFC that there is an 
Ulm-type classification of the torsion-free abelian groups,} 
pp. 293-309, {\bf MSRI Publication 26,} Springer-Verlag, 11992, New-York. 

\medskip

\leftskip 0in 












\end{document} 









