% 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)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_{iFrom (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}