% 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}