% THIS MUST be processed using the command "latex2e" on a UCLA math dpt machine \documentclass{report} \usepackage{amsmath, amssymb} %\usepackage{graphicx} \usepackage{psfig} \usepackage{amssymb} \usepackage{amsfonts} %\usepackage[all]{xy} %\input{amsfonts.dtx} %\input{amssymb.def} %\input{amssymb.tex} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newenvironment{proof}[1][Proof]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}{\hfill{\huge $\square$}}} \newenvironment{definition}[1][Definition]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{example}[1][Example]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{remark}[1][Remark]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{examples}[1][Examples]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{notation}[1][Notation]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} % Set left margin - The default is 1 inch, so the following % command sets a 1.25-inch left margin. \setlength{\oddsidemargin}{-0.25in} % Set width of the text - What is left will be the right margin. % In this case, right margin is 8.5in - 1.25in - 6in = 1.25in. \setlength{\textwidth}{6.25in} % Set top margin - The default is 1 inch, so the following % command sets a 0.75-inch top margin. \setlength{\topmargin}{-0.1in} % Set height of the header \setlength{\headheight}{0.7in} % Set vertical distance between the header and the text \setlength{\headsep}{0.4in} % Set height of the text \setlength{\textheight}{8in} % Set vertical distance between the text and the % bottom of footer \setlength{\footskip}{0.4in} \pagestyle{myheadings} \markboth {Hjorth}{Hjorth} % \markright{G. Hjorth} \begin{document} \def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}} \def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}} \def\R{{\mathbb R}} \def\N{{\mathbb N}} \def\Q{{\mathbb Q}} \def\Z{{\mathbb Z}} \def\C{{\mathbb C}} \def\P{{\mathbb P}} \def\no{\noindent} \def\Box{\square} \def\forces{\Vdash} %\frontmatter \title{\Huge {\bf Group Actions and Countable Models}} % Information for first author \author{\huge Greg Hjorth \bigskip \\ \huge Department of Mathematics \\\huge University of California at Los Angeles\\ \huge Los Angeles, California \\\huge 90095-1555} \date{\huge August, 1999} \maketitle \huge \tableofcontents \chapter*{Introduction} The field of Polish group actions has emerged in the last couple of years as a kind of sub-sub-discipline in its own right. To some extent one can think of the study of countable models as being a special case of a Polish group action -- since the infinite symmetric group, consisting of all permutations of the natural numbers, is a Polish group whose action on countable models gives rise to the isomorphism relation as its orbit equivalence relation. In these talks I will try to emphasize the connections between recent work on Polish groups and some basic concepts one might see in a first course in logic or model theory. %\endgroup \newpage %\begin{figure} %\begin{picture}(0,0)% %{\includegraphics{people.pstex}}% %\caption{Turbulence} %\end{picture}% %\setlength{\unitlength}{0.00041700in}% %\begin{picture}(8574,11649)(964,-11623) %\put(6976,-361){\makebox(0,0)[lb]{ {\huge Mackey}}} %\put(6976,-2761){\makebox(0,0)[lb]{\huge (Glimm)}} %\put(6976,-3061){\makebox(0,0)[lb]{{\huge Effros [1965,1982]}}} %\put(1576,-2911){\makebox(0,0)[lb]{{\huge (Ryll-Nardzewski [1964])}}} %\put(1501,-4411){\makebox(0,0)[lb]{{\huge Vaught [1973, 1974] }}} %\put(1426,-6661){\makebox(0,0)[lb]{{\huge Sami [1994]}}} %\put(1351,-8836){\makebox(0,0)[lb]{{\huge Becker-Kechris [1996]}}} %\put(2101,-10486){\makebox(0,0)[lb]{{\huge Lots of recent stuff }}} %\put(2101,-11086){\makebox(0,0)[lb]{{\huge Becker, %Farah, Gao, Kechris}}} %\put(2101, -11686){\makebox(0,0)[lb]{{\huge Louveau, %Solecki, and others}}} %\end{picture} %\end{figure} \begin{figure}[ht] {\psfig{figure=people.ps}} \end{figure} \chapter{\Huge Dynamic changes in topologies} %The main issue here is to discuss some of the tricks that %enable us to change topologies and remain in the category %of Polish spaces. \section{\huge Polish spaces and Polish groups [definitions; the statement of the topological Vaught conjecture]} \bigskip \begin{definition} A topological space is said to be {\it Polish} if it is separable and there is some complete metric which generates its topology. \end{definition} \no{\bf Examples} (i) $\R$, the reals equipped with the topology generated by the open intervals. %(The usual %euclidean distance gives a complete metric.) (ii) $C([0, 1])$, the continuous functions from the unit interval to $\R$ with the topology generated by the sup norm, $d(f_1, f_2)=$ sup$_{0\leq x\leq 1}|f_1(x)-f_2(x)|.$ (iii) $\N$ in the discrete topology. As a metric, $d(x_1, x_2)=1$ if $x_1\neq x_2$, $=0$ if $x_1=x_2$. (iv) $\N^{\N}$ in the product topology. \newpage (v) More generally if $(X_i)_{i\in\N}$ is a sequence of Polish spaces, then their infinite product \[\prod_\N X_i\] is a Polish space in the product topology. \bigskip \bigskip \no{\bf Proof:} After possibly replacing each metric $d_i$ with \[\hat{d}_i(x, y)=\frac{d_i(x, y)}{d_i(x, y)+1}\] we may assume that each $d_i$ is bounded by 1. Then we can obtain a compatible complete metric on the product given by \[d(\vec x, \vec y)=\sum_{i\in \N}2^{-i}d_i(x_i, y_i)\] where \[\vec x=(x_0, x_1, x_2, \ldots, x_i, \ldots)\] \[\vec y= (y_0, y_1, y_2, \ldots, y_i, \ldots)\] are both in $\prod_\N X_i$. \hfill $\Box$ \newpage \begin{lemma} \label{G_d} Let $X$ be a Polish space and $A\subset X$ a $G_{\delta}$ subset -- that is to say, defined by the countable intersection of open sets. Then $A$ in the subspace topology is again a Polish space. \end{lemma} \begin{proof} First for open ${\cal O}\subset X$. Let $d$ be complete metric for $X$, and find continuous \[f: {\cal O}\rightarrow \R\] with $f(x)\rightarrow \infty$ as $x\rightarrow X\setminus {\cal O}$. (For instance, $f(x)=$ inf$\{\frac{1}{d(x, c)}: c\notin {\cal O} \}$.) Then define $d_{\cal O}$ on ${\cal O}$ by \[d_{\cal O}(x, y)=d(x, y)+|f(x)-f(y)|.\] Suppose $(x_i)$ is a sequence in ${\cal O}$ that is $d_{\cal O}$-Cauchy. From the definition of $d_{\cal O}$ it must be $d$-Cauchy, and hence by assumption that $d$ witnesses $X$ Polish, there is a limit $x_\infty$. But we must also have that $(f(x_i))_{i\in\N}$ will be Cauchy in $\R$, and thus $x_\infty\in {\cal O}$. For the general case \[A=\bigcap_{i\in\N}{\cal O}_i\] we stitch together the complete metrics $d_{{\cal O}_i}$ on ${\cal O}_i$ as in last proof to obtain a complete metric on $A$. \end{proof} \newpage \begin{definition} A topological group is said to be {\it Polish} if it is Polish as a space. \end{definition} \begin{examples} (i) $(\R, +)$, the reals equipped with its usual additive structure. (ii) Any discrete group. Countable products of discrete groups, and more generally the class of Polish groups is closed under countable products. (iii) $S_\infty$ the group of all permutations of $\N$, equipped with the topology of pointwise convergence. So as a basis we may take all sets of the form \[\{\pi\in S_\infty: \pi(k_1)=l_1, ..., \pi(l_n)=k_n\}.\] (iv) $U_\infty$ the unitary group of $\ell^2$, infinite dimensional (separable) Hilbert space. Thus $U_\infty$ is the group of all bijective linear operators \[T:\ell^2\rightarrow \ell^2\] such that for all $\xi, \zeta\in \ell^2$ \[\langle \xi, \zeta\rangle=\langle T(\xi), T(\zeta)\rangle.\] We give this the topology generated by the subbasis consisting of sets of the form \[\{T\in U_\infty: |\langle T(\xi), \zeta\rangle - \langle T_0(\xi), \zeta\rangle|<\epsilon\}.\] \end{examples} \newpage \begin{definition} Let $G$ be a Polish group. We say that a Polish space $X$ is a {\it Polish $G$-space} if it is a Polish space which is equipped with a continuous action by $G$. We then let $E_G$ denote the orbit equivalence relation: $x_1 E_G x_2$ if \[\exists g\in G(g\cdot x_1=x_2).\] For $x\in X$ let $[x]_G$ indicate the orbit of $x$: \[\{y\in X: \exists g\in G(g\cdot x=y)\}.\] $X/G$ indicates the set of orbits. \end{definition} \bigskip \bigskip {\bf TOPOLOGICAL VAUGHT CONJECTURE}\footnote{\large This conjecture is very much still open}: Whenever $G$ is a Polish group and $X$ a Polish $G$-space, then either \begin{enumerate} \item $X/G\leq \aleph_0$ (at most countably many orbits), or \item $X/G=2^{\aleph_0}$ (continuum many orbits). \end{enumerate} \bigskip As stated here, the topological Vaught conjecture is trivially true under CH (the continuum hypothesis). Frequently people use a reformulation of this conjecture that is equivalent under CH. \newpage One can pose similar kinds of questions for other classes of equivalence relations, and in almost every case the answer is known. \begin{theorem} (Silver) Let $E$ be a Borel (or even $\Ubf{\Pi}^1_1$) equivalence relation on a Polish space $X$. Then either \begin{enumerate} \item $X/E\leq \aleph_0$ (at most countably many orbits), or \item $X/E=2^{\aleph_0}$ (continuum many orbits), and in fact in this case there is a perfect set of $E$-inequivalent points in $X$. \end{enumerate} \end{theorem} \bigskip \begin{theorem} (Burgess, see \cite{burgess78}) \label{burgess} Let $E$ be a $\Ubf{\Sigma}^1_1$ equivalence relation on a Polish space $X$. That is to say, there is some Polish space $Y$, Borel function $f: Y\rightarrow X\times X$, and Borel set $B\subset Y$ with $E=\{f(z): z\in B\}$. Then either \begin{enumerate} \item $X/E\leq \aleph_1$, or \item $X/E=2^{\aleph_0}$ (continuum many orbits), and in fact in this case there is a perfect set of $E$-inequivalent points in $X$. \end{enumerate} \end{theorem} \bigskip Burgess' theorem optimal. If one considers the space $2^\N$ and sets $x_1Ex_2$ if $\omega_1^{{\rm ck}(x_1)}=\omega_1^{{\rm ck}(x_2)}$ (the least $x_1$-admissible ordinal equals the least $x_2$-admissible) then we obtain an equivalence relation which has exactly $\aleph_1$ many classes, where each orbit is Borel, and the equivalence relation itself is $\Ubf{\Sigma}^1_1$. The equivalence relations which arise from Polish group actions are $\Ubf{\Sigma}^1_1$ and have every orbit Borel. This counterexample shows that we should certainly be using more than just these properties if we are to ever prove the conjecture. \newpage \section{\huge The space of countable models [isomorphism of countable models viewed as a kind of Polish group action; different Polish topologies we may place on spaces of countable models]} \begin{definition} Let ${\cal L}$ be a countable language, and for notational simplicity assume that ${\cal L}$ is generated by a single binary relation $R$. We then let Mod$({\cal L})$ be the space of all ${\cal L}$-structures whose underlying set is $\N$, equipped with the topology generated by sets of the form \[\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models \varphi(k_1, \ldots, k_n)\}\] where $\varphi$ is quantifier free and $k_1, \dots, k_n$ are in $\N$. There is then a natural homeomorphism \[{\rm Mod}({\cal L})\rightarrow \{0, 1\}^{\N\times \N}\] \[{\cal M}\mapsto \chi_{R^{\cal M}}\] associating to each ${\cal M}$ the characteristic function of its interpretation of $R$. \bigskip Thus Mod$({\cal L})$ is a Polish space. \newpage We let $S_\infty$ act on Mod$({\cal L})$ by \[\pi\cdot {\cal M}\models R(k_1, k_2)\] if and only if \[{\cal M}\models R(\pi^{-1}(k_1), \pi^{-1}(k_2)).\] Then Mod$({\cal L})$ is a Polish $S_\infty$ space and the orbit equivalence relation is just the usual isomorphism relation. \end{definition} \bigskip Our next goal is to see that the topological Vaught conjecture really does generalize the model theoretic versions of the Vaught conjecture. To do this we need to consider alternative Polish topologies we may place on the space of countable models. \newpage \begin{definition} (i) Let $\tau_{\rm FO}$ be the topology on ${\rm Mod}({\cal L})$ whose basic open sets have the form \[\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models \varphi(k_1, \ldots, k_n)\}\] where $\varphi$ is first order and $k_1, \dots, k_n$ are in $\N$. (ii) For $F\subset {\cal L}_{\omega_1, \omega}$ a countable fragment (closed under subformulas, instantiations, and first order operations), let $\tau_F$ be the topology on ${\rm Mod}({\cal L})$ whose basic open sets have the form \[\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models \varphi(k_1, \ldots, k_n)\}\] where $\varphi\in F$. \end{definition} Both provide Polish topologies on ${\rm Mod}({\cal L})$. (Proof for (i) below). Thus for any theory $T$ the set \[\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models T\}\] is a closed $S_\infty$-invariant subspace of $({\rm Mod}({\cal L}), \tau_{\rm FO})$, and hence a Polish $S_\infty$ space in its own right. Sets of the form $\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models T\}$ correspond exactly to the closed invariant subspaces; the subspace is minimal iff $T$ complete. \bigskip A key step in the proof of Becker's theorem (next talk) is to pass from a not so good topology (like the quantifier free topology) to a better topology (like $\tau_{\rm FO}$). \newpage \begin{lemma} (Gregorczyk, Mostowski, Ryll-Nardzewski) $({\rm Mod}({\cal L}), \tau_{\rm FO})$ is a Polish space. \end{lemma} \begin{proof} Let $B$ be the set of substitutions of the form $\varphi(k_1, \ldots, k_n)$ where $\varphi$ is a first order ${\cal L}$ formula. Let $X=\{0, 1\}^B$, the space of all functions from $B$ to $\{0, 1\}$. We may naturally identify $({\rm Mod}({\cal L}), \tau_{\rm FO})$ with the functions in $f\in X$ which preserve the ``inductive unraveling of truth" -- for instance, $f(\varphi_1(k)\wedge \varphi_2(k))=1$ if and only if $f(\varphi_1(k))=f(\varphi_2(k))=1$. Most of these requirements correspond to closed conditions in $X$, except for the rule governing existential quantifiers, \[f(\exists x\varphi(k, x))=1\Leftrightarrow\exists l\in \N f(\varphi(k, l))=1{\rm ,}\] which is still no worse than $G_\delta$. Thus $({\rm Mod}({\cal L}), \tau_{\rm FO})$ is homeomorphic to a $G_\delta$ subspace of a Polish space, and thus Polish. \end{proof} \bigskip In many respects $\tau_{\rm FO}$ would seem to be a nicer topology than the topology generated by quantifier free formulas. This becomes more apparent after we introduce the notion of {\it Vaught transform} and to note that $\tau_{\rm FO}$ has a basis that is closed under the Vaught transforms. %Here there is an important theorem due to Becker and Kechris which states that %among other things that for any Polish $G$-space there are ``cofinally" many %Polish topologies in which that action is still continuous and that are %closed under the Vaught transforms. \newpage \section{\huge Becker-Kechris theorem [Vaught transforms; adding to the topology of a Polish $G$-space and keeping the action continuous]} \begin{definition} Let $G$ be a Polish group and $X$ a Polish $G$-space. For $V\subset G$ open and $B\subset X$ (preferably Borel), we let \[B^{\Delta V}\] be the set of $x\in X$ for which there is a non-meager\footnote{\large A set is meager if it is included in a countable union of closed sets each of which contain no non-trivial open subset} set of $g\in V$ for which $g\cdot x\in B$. We symmetrically define $B^{* V}$ to be the set of $x\in X$ for which there is a relatively comeager set of $g\in V$ with $g\cdot x\in V$. \end{definition} \bigskip \bigskip \begin{lemma} (Vaught) For $\varphi\in{\cal L}_{\omega_1, \omega}$, $B$ the set of ${\cal M}\in {\rm Mod}({\cal L})$ with $ {\cal M}\models \varphi(k_1, \ldots, k_n, a_1, \ldots, a_m)\}{\rm ,}$ and $V=\{\pi\in S_\infty: \pi(a_1)=b_1,\ldots, \pi(a_m)=b_m\}$, \[B^{\Delta V}=\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models \exists x_1\ldots\exists x_n \varphi(\vec x,\vec b)\}{\rm ,}\] \[B^{* V}=\{{\cal M}\in {\rm Mod}({\cal L}): {\cal M}\models \forall x_1\ldots \forall x_n \varphi(\vec x, \vec b)\}{\rm .}\] \end{lemma} \newpage \begin{theorem} (Becker-Kechris) \label{change} Let $G$ be a Polish group and $X$ a Polish $G$-space. Let $B\subset X$ be Borel. Let ${\cal B}$ be a countable basis for $G$. Then there is a Polish topology $\tau$ on $X$ such that: \begin{enumerate} \item $\tau$ is richer than the original topology on $X$; \item for any $V\in {\cal B}$ \[B^{\Delta V}\in \tau{\rm ;}\] \item $\tau$ has a countable basis ${\cal C}$ such that for all $U_1, U_2\in {\cal C}$ and $V_1, V_2\in {\cal B}$, \[(U_1\cap (X\setminus U_2)^{*V_1})^{\Delta V_2}\in {\cal C}{\rm ;}\] \item the action of $G$ on $X$ is still continuous with respect to $\tau$ (and thus $(X, \tau)$ is still a Polish $G$-space). \end{enumerate} \end{theorem} In the case that $B$ is invariant under the action of $G$ we obtain that $B^{\Delta G}=B^{*G}=B$, and thus $B$ is an invariant clopen subset of $(X,\tau)$. In particular Vaught's conjecture for ${\cal L}_{\omega_1, \omega}$ is implied by the topological Vaught conjecture for $S_\infty$. \newpage \begin{lemma} $X$ a Polish $G$-space, $V\subset G$ open and $C\subset X$ closed. Then there is a richer Polish topology on $X$ for which the action is still continuous and $C^{\Delta V}$ is now open. \end{lemma} \begin{proof} By Birkhoff-Kakutani we may find a compatible right invariant metric $d$ on $G$ that is bounded by 1. Let ${\cal L}(G)$ be the space of $f: G\rightarrow [0, 1]$ such that for all $g_1, g_2 \in G$ \[|f(g_1)-f(g_2)|\leq d(g_1, g_2){\rm .}\] Then ${\cal L}(G)$ is a Polish $G$-space under the natural action $(g\cdot f)(h)= f(hg).$ For $x\in X$ let $f_x\in {\cal L}(G)$ be given by \[f_x(g)={\rm \: inf}\{d(g, h): h\cdot x\notin C\}{\rm .}\] $X_C=\{(x, f_x): x\in X\}$ is an invariant subset of $X\times {\cal L}(G)$ and $\pi_C:X\rightarrow X_C$ \[x\mapsto (x, f_x)\] is a bijection which respects the $G$-action. One then verifies that $X_C$ is a $G_\delta$ subset of $X\times {\cal L}(G)$ and thus a Polish $G$-space. The pullback of the topology on $X_C$ to $X$ is as required. \end{proof} \chapter{\Huge Smoothness and the Glimm-Effros dichotomy} \section{\huge Smoothness [Effros lemma; $G_\delta$ orbits as the analogue of atomic models]} \begin{definition} An orbit equivalence relation $E_G$ on Polish space $X$ is said to be {\it smooth} if there is a Borel function\footnote{\large that is to say, for any open $O\subset \R$ the set $f^{-1}(O)$ appears in the $\sigma$-algebra on $X$ generated by the open sets} $f: X\rightarrow \R$ such that for all $x_1, x_2\in X$ \[x_1 E_G x_2 \Leftrightarrow f(x_1)=f(x_2).\] \end{definition} \bigskip Burgess (\cite{burgess79}) showed that for $E_G$ given by the continuous action of a Polish group action we have $E_G$ smooth if and only if there is a Borel set meeting every orbit in exactly one point. \newpage \begin{example} Let $\Z_2^{<\N}$ be the infinite binary sequences which are eventually constantly 0. This is a countable set, and we give it the discrete topological structure. We further introduce the group structure obtained by pointwise addition mod 2; thus for $\vec g, \vec h\in \Z_2^{<\N}$ and $n\in\N$ we have $(\vec g +\vec h)(n)=0$ if $\vec h(n)= \vec g(n)$ and $=1$ otherwise. We then let it act on $2^\N$ in the natural manner: For $\vec x\in 2^\N=_{df}{\{0, 1\}}^\N$, $\vec g\in \Z_2^{<\N}$, $n\in\N$, we again have $(\vec g\cdot \vec x)(n)=0$ if and only if $\vec x(n)=\vec g(n)$. \end{example} \begin{lemma} \label{non-smooth} The above orbit equivalence relation $E_{\Z_2^{<\N}}$ is non-smooth. \end{lemma} \begin{proof} Suppose instead (by Burgess) $B$ is a Borel selector. Let $\mu$ be the product (``coin flipping") measure on $2^\N$. Note that $(2^\N, \mu)$ is a probability space and ${\Z_2^{<\N}}$ acts by measure preserving transformations on $(2^\N, \mu)$. Since countably many translates of $B$ cover $2^\N$ we must have $\mu(B)>0$. But then there are $\aleph_0$ many {\it disjoint} translates of $B$, each having the same measure, and hence a contradiction to $\mu(2^\N)=1$. \end{proof} \newpage There are many theorems giving necessary conditions for non-smoothness in terms of being able to {\it embed} this orbit equivalence relation $E_{\Z_2^{<\N}}$. For a wide variety of groups (but not $S_\infty$!) one can show that $E_G$ is smooth if and only if we cannot so embed this canonical example of a non-smooth equivalence relation. For instance: \begin{theorem} (Becker-Kechris) \label{E_0} Let $G$ be a Polish group and $X$ a Polish $G$-space, $x\in X$. Suppose that no orbit $[y]_G$ with the same closure as $[x]_G$ is comeager in \[\overline{[x]_G}{\rm ,}\] the closure of the orbit. Then \begin{enumerate} \item $E_G$ is not smooth and \item there is a continuous injection \[\rho: 2^\N\rightarrow X\] such that for all $\vec x, \vec y\in 2^\N$ \[\vec x E_{\Z_2^{<\N}} \vec y\Leftrightarrow (\rho(\vec x) E_G \rho(\vec y)).\] \end{enumerate} \end{theorem} \bigskip In fact 2. implies 1. in the statement of the theorem. \newpage After this Becker-Kechris theorem one might conclude that it would be nice to understand when an orbit is comeager in its own closure. Here a theorem was proved some 30 years earlier by Effros: \begin{theorem} (Effros) Let $G$ be a Polish group and $X$ a Polish $G$-space. Then for $x\in X$ the following are equivalent: \begin{enumerate} \item $[x]_G$ is comeager in $\overline{[x]_G}$; \item $[x]_G$ is $G_\delta$; \item the map \[G\rightarrow [x]_G\] \[g\mapsto g\cdot x\] is open. \end{enumerate} \end{theorem} In the case of the logic action of $S_{\infty}$ on $({\rm Mod}({\cal L}), \tau_{\rm FO})$ -- the ${\cal L}$-structures on $\N$ with the topology generated by first order logic -- one has that the $G_\delta$ orbits correspond to atomic models, see \cite{miller}. (The omitting types theorem shows that the realization of any non-principal type is meager.) \newpage \section{\huge Examples [algebraic characterization of discrete groups with smooth dual (Thoma); Bernoulli shifts up to isomorphism are smooth (Ornstein); but not general mpt's (Feldman)]} \begin{example} As before let $U_\infty$ be the infinite dimensional unitary group, consisting of all isomorphisms of Hilbert space. For $H$ a countable (discrete) group we define Rep$(H)$ to be the space of all homomorphism \[\rho: H\rightarrow U_\infty.\] This may naturally be identified with a closed subspace of the $H$-fold product of $U_\infty$, \[\prod_H U_\infty{\rm ,}\] and thus is a Polish space. We let $U_\infty$ act on Rep$(H)$ by ``pointwise conjugation", \[(T\cdot \rho)(h)=T\circ\rho (h) \circ T^{-1}.\] \newpage We then let Irr$(H)$ be the {\it irreducible} representations in Rep$(H)$ -- that is to say those $\rho$ for which there are no non-trivial closed subspaces of Hilbert space closed under the operators $\{\rho(h): h\in H\}$. It turns out that Irr$(H)$ is a $G_\delta$ subset of Rep$(H)$, and thus a Polish $U_\infty$-space in its own right. \end{example} \bigskip \bigskip \begin{theorem} (Thoma) \label{thoma} The orbit equivalence $E_{U_\infty}$ on {\rm Irr}$(H)$ is smooth if and only if $H$ is abelian-by-finite. \end{theorem} \newpage %One can extend the definition of Rep$(H)$ and Irr$(H)$ to %general locally compact group. Here one demands that the %representations all be continuous, and we give these spaces %the ``compact-open" topology, generated by sets of the %form %\[\{\rho: \rho[C]\subset O\}{\rm ,}\] %where $C\subset H$ is compact and $O\subset U_\infty$ is open. %Again we obtain that Rep$(H)$ and Irr$(H)$ are $U_\infty$ %Polish spaces. %\bigskip %\bigskip %\bigskip %\begin{theorem} (Harish-Chandra, more or less\footnote{\large %I lie terribly. In fact he proved that the representations of %semi-simple connected Lie groups are all type I. While at the time it %was felt that this should turn into a proof of the smoothness %of $E_{U_\infty}|_{{\rm Irr}(H)}$, this does not seem to have been %confirmed until the proof of the ``Mackey conjecture" a few years %later by Glimm}) If $H$ is a semi-simple %connected Lie group, then the %orbit equivalence $E_{U_\infty}$ on {\rm Irr}$(H)$ is smooth. %\end{theorem} %\newpage \begin{example} Let $M_\infty$ be the group of measure preserving transformations of the unit interval, subject to identification of transformations agreeing almost everywhere. We give this the topology generated by sets of the form \[\{\pi\in M_\infty: \mu(\pi(A)\Delta \pi_0(A))<\epsilon\}{\rm ,}\] for $\pi_0\in M_\infty$, $A\subset [0,1]$ measurable, $\epsilon>0$. In this topology and the operation of composition it becomes a Polish group. It seems natural to think of measure preserving transformations as really being ``isomorphic" if they are the same up to some isomorphism of the underlying measure space. Thus we are led to the orbit equivalence relation of $M_\infty$ acting on itself by conjugation: \[\pi\cdot \rho=\pi\circ \rho\circ \pi^{-1}.\] \end{example} \begin{theorem} (Feldman\footnote{\large Something stronger and more specific is shown in \cite{feldman} }) The orbit equivalence relation $E_{M_\infty}$ obtained above is not smooth. \end{theorem} For some special classes of measure preserving transformations one obtains smoothness of the restriction of $E_{M_\infty}$. For instance Ornstein showed that the isomorphism relation on {\it Bernoulli shifts} is smooth and that {\it entropy} provides a complete invariant. \newpage \section{\huge Becker's theorem [Glimm-Effros dichotomy, and hence Vaught's conjecture, for solvable groups]} \begin{definition} (Becker) A Polish group $G$ satisfies the {\it Glimm-Effros dichotomy} if whenever $G$ acts continuously on a Polish space $X$ either: \begin{enumerate} \item $E_G$ is smooth; or \item there is a continuous injection \[\rho: 2^\N\rightarrow X\] such that for all $\vec x, \vec y\in 2^\N$ \[\vec x E_{\Z_2^{<\N}} \vec y\Leftrightarrow (\rho(\vec x) E_G \rho(\vec y)).\] \end{enumerate} \end{definition} Ever expanding classes of groups have been shown to satisfy the Glimm-Effros dichotomy: \begin{enumerate} \item Locally compact Polish groups (Effros, after Glimm). \item Abelian Polish groups (Solecki). \item Nilpotent (Hjorth). \item Solvable (Becker). \end{enumerate} Notably $S_\infty$ fails this dichotomy. \newpage \begin{lemma} Any Polish group satisfying the Glimm-Effros dichotomy satisfies the topological Vaught conjecture. \end{lemma} \begin{proof} Let $X$ be a Polish $G$-space. We wish to show that either there are $2^{\aleph_0}$ many orbits or at most countably many orbits. Apply the definition of the Glimm-Effros dichotomy. Suppose first we are in case 2, and so we have a continuous embedding $\rho$ of $E_{\Z_2^{<\N}}$ into $E_G$. Then we may find $2^{\aleph_0}$ infinite almost disjoint subsets $(A_{\alpha})_{\alpha<2^{\aleph_0}}$ of $\N$. For each $\alpha$ let $\vec x_{\alpha}\in 2^{\N}$ be the characteristic function of $A_{\alpha}$, and thus for $\alpha\neq \beta$ we have that $\vec x_{\alpha}$ and $\vec x_{\beta}$ differ on infinitely many coordinates, and thus $\rho(\vec x_\alpha)$ and $\rho(\vec x_\beta)$ are $E_G$ inequivalent by assumption on $\rho$. (Here we have just used that ${\cal P}(\N)/$Finite has cardinality $2^{\aleph_0}$.) Alternatively suppose we are in case 1. Then there is Borel $G$-invariant \[f: X\rightarrow \R{\rm ,}\] such that for all $x_1, x_2 \in X$ \[x_1E_G x_2 \Leftrightarrow f(x_1)=f(x_2).\] Thus there is a bijection between $X/G$ and $\{f(x): x\in X\}$. But $\{f(x): x\in X\}$ is a $\Ubf{\Sigma}^1_1$ or {\it analytic} set, and so we finish by the following classical theorem: \begin{theorem} (Souslin) Let $Y$ be a Polish space and $C\subset Y$ an analytic set -- that is to say, suppose there is some other Polish space $Z$ and Borel set $B\subset Z$ and Borel function $h: Z\rightarrow Y$ with $C$ equal to the image of $B$ under $h$. Then either $C$ is countable or it has size $2^{\aleph_0}$. \end{theorem} \end{proof} \newpage \begin{theorem} (Becker) Solvable Polish groups satisfy the Glimm-Effros dichotomy. \end{theorem} \begin{proof} Let $G$ be a solvable Polish group and $X$ a Polish $G$-space. Assume that 2. fails, that is to say, we are unable to continuously inject $E_{\Z_2^{<\N}}$ into $E_G$. Since $G$ is solvable it has a {\it complete} compatible right invariant metric (Gao, Hjorth-Solecki), call it $d_G$. Following \ref{change} we may assume that we have a basis ${\cal C}$ for the topology on $X$ and ${\cal B}$ on $G$ such that: \begin{enumerate} \item for all $U_1, U_2\in {\cal C}$ and $V_1, V_2\in {\cal B}$, \[(U_1\cap (X\setminus U_2)^{*V_1})^{\Delta V_2}\in {\cal C}{\rm ;}\] \item the action of $G$ on $X$ is still continuous with respect to $\tau$ (and thus $(X, \tau)$ is still a Polish $G$-space). \end{enumerate} It is not hard to show that there is a Borel function \[\theta: X\rightarrow \R\] such that for all $x_1, x_2 \in X$ \[\theta(x_1)=\theta(x_2)\Leftrightarrow \overline{[x_1]_G}= \overline{[x_2]_G}.\] (We may code the closure of an orbit by a real number, and the coding can be completed in a Borel manner.) Thus it suffices to show that $\overline{[x]_G}$ is a complete invariant of $[x]_G$. Fix $x\in X$. Now by \ref{E_0}, the Becker-Kechris theorem on embedding $E_{\Z_2^{<\N}}$, we know that there must a $G_\delta$ orbit $[y]_G$ with the same closure as $[x]_G$. Using the Effros lemma, we can obtain for each open \[V_n=\{g\in G: d_G(1_G, g)<2^{-n}\}\] some open $U_n\in{\cal C}$ containing $y$ with diameter less than $2^{-n}$ such that \[V_n\cdot y\supset U_n\cap [y]_G.\] Then using assumption 2. on the topology and a short calculation we can argue that whenever $U\in {\cal C}$ and \[U\cap U_n\cap [y]_G\neq\emptyset\] \[\hat{x}\in U_n\cap [x]_G\] then there are $g$ arbitrarily close to the identity with \[g\cdot \hat{x}\in U^{\Delta V_n^2},\] and thus in particular we may find $g,h\in V_n^2$ with $hg\cdot \hat{x}\in U$. Repeating this observation infinitely often we may find a sequence $(h_n)_{n\in\N}$ in $G$ and $(x_n)_{n\in\N}$ in $[x]_G$ with: \begin{enumerate} \item $x_n\in U_n$; \item $h_n\in V_n^4$, and thus $d_G(h_n, 1_G)<2^{-n+2}$; \item $x_{n+1}=h_n\cdot x_n$. \end{enumerate} We find $h_{n+1}$ by applying the preceding observation with $U_{n+1}$ taking the place of the set $U$. Thus if we let $g_n=h_nh_{n-1}\ldots h_1h_0$ then we have $x_n=g_n\cdot x_0\in [x]_G$ and by 1. we have \[x_n\rightarrow y.\] On the other hand 2. and right invariance of the metric gives \[d_G(g_n, g_{n-1})< 2^{-n+2}\] and thus $(g_n)$ is Cauchy. But for $g_\infty$ the limit we obtain from continuity of the action, \[g_\infty\cdot x_0=y.\] \end{proof} \newpage \begin{example} $S_\infty$ does not satisfy the Glimm-Effros dichotomy. Let ${\cal L}$ be generated by binary function $+$, unary function $-(\:)$, and constant symbol $0$. Let AG be the subset of Mod$({\cal L})$ consisting of ${\cal G}$ in which $(+^{\cal G}, -(\:)^{\cal G}, 0^{\cal G})$ defines an abelian group structure on $\N$. Certainly this corresponds to a first order definable property on ${\cal G}$, and so AG is a closed invariant subspace of Mod$({\cal L})$. Then for $p$ a prime let TAG$_p$ be the set of all $p$-groups -- that is to say, ${\cal G}$ such that for all $g\in {\cal G}$ there exists $n>0$ with \[{\cal G}\models p^n\cdot g=0.\] TAG$_p$ is an invariant $G_\delta$ set, and hence a Polish $S_\infty$-space in its own right. \bigskip The Ulm analysis of abelian $p$-groups shows that we may find a {\it reasonably nice} (e.g. provably $\Delta^1_2$ in the codes) function $U:{\rm TAG}_p\rightarrow 2^{<\omega_1}$ assigning bounded subsets of $\aleph_1$ as complete invariants. \bigskip {\bf Claim:} ${\rm TAG}_p/S_\infty$ is not smooth. Roughly this follows because in general there can be no {\it reasonably simply definable} (e.g. absolutely $\Delta^1_2$!) $\omega_1$ sequence of reals. \bigskip {\bf Claim:} We cannot embed $E_{\Z_2^{<\N}}$ into ${\rm TAG}_p/S_\infty$. Otherwise by postcomposing with $U$ we would obtain an assignment $\hat{U}$ of bounded subsets of $\aleph_1$ as complete invariants for $2^\N/{\Z_2^{<\N}}$. Then we would obtain some fixed $\alpha<\omega_1$ and $\mu$-measure\footnote{\large $\mu$ the ``coin flipping" measure from before} one set on which the reduction $\hat{U}$ takes values inside $2^\alpha$. (To see this, we can take $(M; \in)$ some countable transitive model containing the real parameter used in the embedding of $E_{\Z_2^{<\N}}$; then there will be a $\mu$-measure 1 set of $x\in 2^\N$ that are ``random" generic for $M$ -- and for any such $x$ there will be some $\alpha< \omega_1^M=\omega_1^{M[x]}<\omega_1^V$ with $\hat{U}(x)\in 2^\alpha$). But then since $2^\alpha$ is naturally isomorphic to $2^\N$, and hence Borel isomorphic to $\R$, we obtain a contradiction to our proof before that $2^\N/{\Z_2^{<\N}}$ is non-smooth on any $\mu$-measure one set. (Here we have skipped over technicalities relating to the fact that $\hat{U}$ is not necessarily Borel. The issue here however is that it can be chosen to be absolutely measurable in the codes; hence on a measure one set it will equal a Borel function, or alternatively the proof of \ref{non-smooth} can be seen to work in the more general context of $\mu$-measurable functions.) \end{example} \chapter{\Huge Vaught's conjecture on analytic sets} \section{\huge Variations on the conjecture} \begin{definition} A subset $P$ of Polish space $X$ is {\it perfect} if it is closed, non-empty, and has no isolated points. \end{definition} Any perfect set contains a homeomorphic copy of $2^\N$, and hence has size $2^{\aleph_0}$. \begin{notation} For $H$ a Polish group let WVC$(H)$ be the statement that whenever $X$ is a Polish $H$-space either there are at most $\aleph_0$ many orbits or there are $2^{\aleph_0}$ many orbits. Let TVC$(H)$ be the statement that whenever $X$ is a Polish $H$-space then either there are only countably many orbits or there is a perfect set $P\subset X$ of orbit inequivalent points: \[\forall x_1, x_2 \in P(x_1\neq x_2 \Rightarrow [x_1]_H\neq [x_2]_H).\] \end{notation} \newpage \begin{lemma} (Sami) \label{borel} If $H$ is a Polish group and $X$ is a Polish $H$-space witnessing the failure of TVC$(H)$, then $X$ continues to witness the failure of TVC$(H)$ through all generic extensions. \end{lemma} \begin{proof} \empty \bigskip {\bf Claim:} In no generic extension can $X$ contain a perfect set of orbits. \bigskip Proof of Claim: The statement that there are perfectly many orbits may be expressed as: \[\exists P\subset X(P {\rm \: perfect\:} \wedge\] \[\forall x_1, x_2 \in P\forall g\in G(x_1\neq x_2\Rightarrow g\cdot x_1\neq x_2)).\] This is $\Ubf{\Sigma}^1_2$, and hence absolute by Shoenfield. \hfill (Claim$\square$)\footnote{\large This proof also works to show that if a $\Ubf{\Sigma}^1_1$ $A$ does not contain a perfect set of orbit then in no generic extension it will contain a perfect set of orbits. The point here is that if $P$ is a perfect subset of $A$ then by say an appeal to the Baire category theorem and the Jankov-von Neumann uniformization we may find a perfect $P_0\subset P$ and a continuous function $f$ on $P_0$ such that for all $x\in P_0$ we that $f(x)$ witnesses $x\in A$.} \bigskip {\bf Claim:} In every generic extension $X/H$ is uncountable. \bigskip Proof of Claim: For conceptual simplicity let us do the case that $X=\{{\cal M}\in$ Mod$({\cal L}): {\cal M}\models T\}$ and $H=S_\infty$. Then for any ${\cal M}\in$ Mod$({\cal L})$ we have that $[{\cal M}]_{S_\infty}$ is uniformly Borel in (any code for) the Scott sentence of ${\cal M}$. Moreover, in some natural parameter space $Y$ we have that \[{\cal S}=\{({\cal M}, y): y {\rm \: codes \: the \: Scott \: sentence \: of \: }{\cal M}\}\] is $\Ubf{\Pi}^1_1.$ Then the statement that the models of $T$ has uncountably many isomorphism types becomes the statement that for all sequences $({\cal M}_i), (y_i)$, either: \begin{enumerate} \item there exists $i$ with $({\cal M}_i, y_i)\notin {\cal S}$; or \item there exists ${\cal N}\models T$ with ${\cal N}$ not satisfying any of the sentences coded by the $\{y_i: i\in\N\}$. \end{enumerate} Thus it is $\Ubf{\Pi}^1_2$ and subject to Shoenfield absoluteness. The general case follows by working not with the Scott sentence, but the {\it stabilizer} of the points in question; again $[x]_H$ is uniformly Borel in (any code for) the stabilizer of $x$. \hfill (Claim$\square$) \end{proof} \newpage \begin{corollary} It is provable in ZFC that every Polish group $H$ satisfies WVC$(H)$ (i.e. the original topological Vaught conjecture) if and only it is provable that every Polish group satisfies TVC$(H)$. \end{corollary} \begin{proof} $\Leftarrow$ since any perfect set has size $2^{\aleph_0}$. \bigskip $\Rightarrow$ since if we have a group $H$ and a Polish $H$-space $X$ showing the failure of TVC$(H)$ then we may go to a forcing extension in which $2^{\aleph_0}=\aleph_2$. In the forcing extension Sami's lemma and Burgess' theorem from \ref{burgess} on analytic equivalence relations imply that we must have $|X/H|=\aleph_1$. \end{proof} \bigskip In view of this fact many people take the ``topological Vaught conjecture" to mean the stronger statement -- that for every Polish group $H$ a Polish $H$-space $X$ we have either $\leq\aleph_0$ many orbits or perfectly many. \newpage \begin{definition} A subset $A$ of a Polish space $X$ is said to be {\it analytic}, or $\Ubf{\Sigma}^1_1$, if there is some Polish space $Y$, Borel set $B\subset Y$, Borel function $f: Y\rightarrow X$, with \[A=\{f(y): y\in B\}.\] \end{definition} \bigskip \begin{notation} For $H$ a Polish group let TVC$(H, \Ubf{\Sigma}^1_1)$ be the statement that whenever $X$ is a Polish $H$-space and $A\subset X$ is $\Ubf{\Sigma}^1_1$ then either \[A/H\leq \aleph_0\] or there is perfect $P\subset A$ such that for all $x_1, x_2\in P$ \[x_1\neq x_2\Rightarrow [x_1]_H\neq [x_2]_H.\] \end{notation} \bigskip Sami's argument also shows absoluteness of TVC$(H, \Ubf{\Sigma}^1_1)$. \bigskip \begin{lemma} (H. Friedman, see \cite{friedman}) Up to isomorphism there are exactly $\aleph_1$ many possible order types for the ordinals in countable $\omega$-models of Kripke-Platek set theory. \end{lemma} \bigskip \begin{corollary} TVC$(S_\infty, \Ubf{\Sigma}^1_1)$ fails. \end{corollary} \newpage \section{\huge ``Proofs" [some sketches around the proof of the characterization of TVC$(G, \Ubf{\Sigma}^1_1)$]} \begin{definition} Let us say that $S_\infty$ {\it divides} a Polish group $H$ if there is a closed subgroup $K