% THIS MUST be processed using the command "latex2e" \documentclass{report} \usepackage{amsmath, amssymb} \input{amssymb.def} \input{amssymb.tex} % Set left margin - The default is 1 inch, so the following % command sets a 1.25-inch left margin. \setlength{\oddsidemargin}{-0.5in} % 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.75in} % Set top margin - The default is 1 inch, so the following % command sets a 0.75-inch top margin. \setlength{\topmargin}{-0.25in} % Set height of the header \setlength{\headheight}{0.5in} % Set vertical distance between the header and the text \setlength{\headsep}{0.2in} % Set height of the text \setlength{\textheight}{8.5in} % 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\n{{\cal N}} \def\m{{\cal M}} \title{\Huge The Vaught conjecture on analytic sets } % Enter your title between curly braces \author{\LARGE Greg Hjorth\\ \LARGE Department of Mathematics\\ \LARGE UCLA CA90095-1555\\\LARGE USA\\\LARGE greg@math.ucla.edu} \date{\LARGE August 1998\\Prague, Logic Colloquium} % Enter your date or \today between curly braces \maketitle \Huge \noindent{\bf $\S$ 0 Preview of main theorem} \bigskip \bigskip \noindent {\bf 0.1 Theorem} Let $G$ be a Polish group. \bigskip \noindent { {\bf Then either}:} \bigskip \leftskip 0.5in \noindent (I) There is a closed subgroup $H$ of $G$ and continuous homomorphism \[H \rightarrow S_{\infty}\] from $H$ onto the group of all permutations of $\N$; \bigskip \leftskip 0in \noindent {{\bf or}} \leftskip 0.4in \bigskip \noindent (II) TVC$(G, \Ubf{\Sigma}^1_1)$ -- whenever $G$ acts continously on a Polish space $X$ and $A\subset X$ is {\it analytic} then either \leftskip 0.6in \medskip \noindent $|A/G|\leq {\aleph_0}$, or \medskip \noindent there is a perfect set $P\subset A$ such that \noindent and for $x\neq y\in P$ and $g\in G$ \[g\cdot x\neq y.\] \[{\pmb \therefore} |P/G|=2^{\aleph_0}.\] \leftskip 0in \newpage \noindent {\bf $\S$1 The space of countable models} \bigskip \bigskip \noindent{\bf 1.1 Definition} ${\cal L}$ -- some countable language. For notational convenience, assume ${\cal L}=\langle R\rangle$, where $R$ is a single binary relation. Mod$({\cal L})$ -- the space of all ${\cal L}$-models whose underlying set is $\N$. \bigskip \bigskip \noindent{\bf 1.2 Two topologies} \bigskip \bigskip $\tau_{\rm qf}$ -- take as subbasic open sets \[\{\m\in {\rm Mod}({\cal L}): \m\models R(n, m)\}\] \[\{\m\in {\rm Mod}({\cal L}): \m\models \neg R(n, m)\}\] where $n,m$ range over $\N$. \bigskip $\tau_{\rm FO}$ -- take as basic open sets \[\{\m\in {\rm Mod}({\cal L}): \m\models \varphi(\vec n)\}\] where $\vec n\in\N^{<\N}$, $\varphi$ first order. \bigskip \bigskip \newpage \noindent{\bf 1.3 Definition} A {\it Polish space} is a separable topological space which allows a complete metric. \noindent E.g: \leftskip 0.4in \noindent $\R$; \noindent $\N^{\N}$ (infinite sequences of natural numbers in the product topology/topology of pointwise convergence); \noindent any separable Banach space -- $\ell^1, c_0, C([0,1])...$; \noindent any compact metric space. \leftskip 0in \bigskip \bigskip \noindent{\bf 1.4 Lemma} (i) $({\rm Mod}({\cal L}), \tau_{\rm qf})$ is a Polish space. (ii) $({\rm Mod}({\cal L}), \tau_{\rm FO})$ is a Polish space. \bigskip For (i): note homeomorphic with $\{f:{\N\times\N}\rightarrow \{0,1\}\}$; then $d(f, g)=$ \[\frac{1}{{\rm inf}\{n+m:f(n,m)\neq g(n,m)\}}.\] (ii) uses $G_{\delta}$ subsets of a Polish space are again Polish.\footnote{\large A. Gregorczyk, A. Mostowski, C. Ryall-Nardzewski, {\it Definability of sets of models of axiomatic theories,} {\bf Bulletin of the Polish Academy of Sciences, (series Mathematics, Astronomy, Physics)}, vol. 9(1961), pp. 163-7.} \newpage \noindent{\bf 1.5 Definition} Let $\cong$ denote the equivalence relation of isomorphism on models in ${\rm Mod}({\cal L})$. A subset $A$ of Mod$({\cal L})$ is {\it invariant} if whenever \leftskip 0.4in \noindent $\m\in A$ and $\n\cong \m$ \leftskip 0in \noindent then \leftskip 0.4in $\n\in A$. \leftskip0in \bigskip \noindent A closed subset $C\subset ({\rm Mod}({\cal L}), \tau_{\rm FO})$ is a {\it minimal closed invariant set} if it is closed, invariant, and whenever \leftskip 0.4in \noindent $A\subset C$ is invariant \leftskip 0in \noindent we must have either: \leftskip 0.4in \noindent $A$ empty, or \noindent $A$ not closed, or \noindent $A=C$. \leftskip 0in \bigskip \bigskip \noindent{ \bf 1.6 Fact} $C\subset ({\rm Mod}({\cal L}), \tau_{\rm FO})$ is a {minimal closed invariant set} if and only if there is a complete ${\cal L}$-theory $T$ with \[C=\{\m\in {\rm Mod}({\cal L}): \m\models T\}.\] \newpage \noindent {\bf 1.7 The Vaught conjecture} (i) If $T$ is a complete consistent ${\cal L}$-theory then {{\bf either}}: \leftskip 0.4in \noindent $\{\m\in {\rm Mod}({\cal L}): \m\models T\}$ has at most countably ($\leq \aleph_0$) many models considered up to isomorphism; \leftskip 0in \noindent { {\bf or}} \leftskip 0.4in \noindent $\{\m\in {\rm Mod}({\cal L}): \m\models T\}$ has continuum ($2^{\aleph_0}$) many models considered up to isomorphism. \leftskip 0in \bigskip \bigskip \bigskip (ii) Equivalently given 1.6: If $C\subset {\rm Mod}({\cal L})$ is minimal closed invariant set, then { {\bf either}}: \leftskip 0.4in \noindent $|C/\cong| \leq \aleph_0$; \leftskip 0in \noindent {{\bf or}} \leftskip 0.4in \noindent $|C/\cong| =2^{\aleph_0}$. \leftskip 0in \bigskip \bigskip \bigskip (iii) Equivalently (using some descriptive set theory): In (ii) can just require that $C\subset {\rm Mod}({\cal L})$ is closed and invariant. \newpage \noindent{\bf 1.8 Definition} Let $S_{\infty}$ be the group of all permutations of $\N$. Basic open sets are of the form \[\{\pi\in S_{\infty}: \pi(n_0)=k_0, \pi(n_1)=k_1, ..., \pi(n_l)=k_l\}.\] \bigskip \bigskip \bigskip We say that a Polish space is a Polish {\it $S_{\infty}$-space} if it comes equipped with a continuous action by $S_{\infty}$. \bigskip \bigskip \bigskip If $X$ is a Polish $S_{\infty}$-space then use $E_{S_{\infty}}$ to denote the orbit equivalence relation: $x_1 E_{S_{\infty}} x_2$ iff \[\exists \pi\in S_{\infty}(\pi\cdot x_1 =x_2).\] The {\it orbit} of $x$: $\:\{\pi\cdot x| \pi\in S_{\infty}\}$. \bigskip \bigskip \bigskip \bigskip \noindent E.g. \leftskip 0.4in \noindent ${\rm Mod}({\cal L})$ with the action \[(\pi\cdot\m)\models R(n, m)\Leftrightarrow \m\models R(\pi^{-1}(n), \pi^{-1}(m)).\] \noindent Any closed invariant $C\subset {\rm Mod}({\cal L})$. \leftskip 0in \bigskip \bigskip \newpage Note that for the above indicated action of $S_{\infty}$ on ${\rm Mod}({\cal L})$ we have $\m\cong\n$ if and only if \[\m E_{S_{\infty}} \n.\] \bigskip \bigskip \bigskip \bigskip \bigskip Thus the Vaught conjecture for first order logic is equivalent to saying that for the family of Polish $S_{\infty}$-spaces of the form \[\{C\subset {\rm Mod}({\cal L}): C\:{\rm closed, invariant} \:\}\] we always have either \[|C/S_{\infty}|\leq \aleph_0,\] \hfill $C$ has only countably many orbits, \noindent or \[|C/S_{\infty}|= 2^{\aleph_0},\] \hfill $C$ has continuum many orbits. \bigskip \bigskip \bigskip \newpage The obvious generalization is also equivalent to a well known problem. \bigskip \bigskip \bigskip \bigskip \noindent {\bf 1.9 Theorem} (Becker-Kechris\footnote{\large {\bf The descriptive set theory of Polish group actions}, London Mathematical Society Lecture Notes Series, 232, Cambridge University Press, Cambridge, 1996.}) Vaught's conjecture holds for ${\cal L}_{\omega_1\omega}$ if and only if for all Polish $S_{\infty}$-spaces $X$ \bigskip \bigskip \bigskip we always have either \bigskip \bigskip \[|X/S_{\infty}|\leq \aleph_0,\] \noindent or \[|X/S_{\infty}|= 2^{\aleph_0}.\] \bigskip \bigskip \bigskip \bigskip \bigskip These {\it are} both still open, as is the original Vaught conjecture. \newpage \noindent{\bf 1.10 Fact:}\footnote{\large J.R. Steel, {\it On Vaught's conjecture}, {\bf Cabal Seminar 76-77,} Lecture Notes in Logic 689, Springer-Verlag, Berlin, 1978.} The following two forms of the Vaught conjecture are {\it equiprovable}: \bigskip \noindent (I) For all Polish $S_{\infty}$-spaces $X$ \bigskip we always have either \[|X/S_{\infty}|\leq \aleph_0,\] \noindent or \[|X/S_{\infty}|= 2^{\aleph_0}.\] \bigskip \bigskip \noindent (II) For all Polish $S_{\infty}$-spaces $X$ \noindent we always have either \[|X/S_{\infty}|\leq \aleph_0,\] \noindent or there is a perfect set $P\subset X$ (that is to say, $P$ closed, non-empty, and without isolated points) such that for all $x_1, x_2\in P$ \[x_1\neq x_2 \Rightarrow \neg(x_1 E_{S_{\infty}} x_2). \] %(II) implies (I), since any perfect set has size $2^{\aleph_0}$, but %{\it as far as we know} (I) does not imply (I). \newpage \noindent{\bf $\S$ 2 Generalizing the group} \bigskip We are left to consider the further step of generalizing the group -- a direction that has been active since Sami's proof of the {\it topological Vaught conjecture for abelian groups} in the early 1980's. \bigskip \bigskip \bigskip \noindent{\bf 2.1 Definition} A {\it Polish group} is a topological group (i.e. the group operations are continuous) that is Polish as a space. \bigskip \bigskip \bigskip \bigskip \noindent E.g: \leftskip 0.4in \noindent $\R$ \noindent $S_{\infty}$ \noindent Aut$(\m)$ -- the automorphism group of a countable structure $\m$ \noindent Hom$([0,1])$ -- the homeomorphism group of the unit interval. \leftskip 0in \newpage If a Polish group $G$ acts continuously on a Polish space $X$ we say that $X$ is a {\it Polish $G$-space}. We write $E_G$ for the orbit equivalence relation. \bigskip \bigskip \bigskip \bigskip \bigskip For $G$ a Polish group, let TVC($G$) -- the {\it topological Vaught conjecture for $G$} -- be the statement that whenever $G$ acts continuously on a Polish space $X$ \bigskip \bigskip \noindent we always have either \[|X/G|\leq \aleph_0,\] \noindent or there is a perfect set $P\subset X$ such that for all $x_1, x_2\in P$ \[x_1\neq x_2 \Rightarrow \neg(x_1 E_{G} x_2). \] \bigskip \bigskip \centerline{*****************************************} Becker-Kechris: TVC($S_{\infty})\Leftrightarrow$ VC$({\cal L}_{\omega_1\omega})$. \bigskip Burgess:\footnote{\large {\it Effective enumeration of classes in a $\Sigma_{1}^{1}$ equivalence relation}, {\bf Indiana University Mathematics Journal}, vol. 28(1979), 353-364} TVC($G)\Leftrightarrow \forall X(|X/G|\neq \aleph_1)$. \newpage \noindent {\bf 2.2 Theorems} In rough historical order: \bigskip \bigskip \noindent Sami: TVC(Abelian) -- \bigskip -- that is to say, if $G$ abelian, then TVC($G$). \bigskip \bigskip \noindent Solecki: TVC(Complete 2-sided invariantly metrizable). \bigskip \bigskip \noindent Hjorth: TVC(Nilpotent). \bigskip \bigskip \noindent Becker: TVC(Complete left-translation invariantly metrizable). \bigskip \noindent {\Huge ${\pmb { \therefore}}$} TVC(Solvable). \bigskip \bigskip \bigskip \centerline{*****************************************} In all the above cases, the classes in question do not include $S_{\infty}$; in some sense the groups mentioned are simpler. For instance Gao has shown that if class of groups with a complete left invariant metric is closed under continuous homomorphic image. \newpage \bigskip \bigskip \bigskip \bigskip \noindent {\bf 2.3 Definition} If $X$ is Polish then $A\subset X$ is $\Ubf{\Sigma}^1_1$, or {\it analytic}, if there is a continuous map from \[\pi:\N^\N\rightarrow X\] with $A$ equal to the image of $\pi$. \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \noindent E.g. \leftskip 0.4in If ${\cal L}_0\subset {\cal L}_1$ are two countable languages, and $T$ is an ${\cal L}_1$ theory, then the set of $\m\in$ Mod$({\cal L}_0)$ for which there is some $\hat{\n}\models T$ with \[\hat{\n}|_{{\cal L}_0}\cong\m\] is a $\Ubf{\Sigma}^1_1$ set. \bigskip \bigskip That is to say, all {\it pseudo-elementary} classes are $\Ubf{\Sigma}^1_1$. \leftskip 0in \newpage \noindent {\bf 2.4 Definition} Let TVC$(G, \Ubf{\Sigma}^1_1)$ be the statement that whenever $G$ acts continuously on a Polish space $X$ and $A\subset X$ is $\Ubf{\Sigma}^1_1$ then either \[|A/G|\leq \aleph_0,\] \noindent or there is a perfect set $P\subset A$ such that for all $x_1, x_2\in P$ \[x_1\neq x_2 \Rightarrow \neg(x_1 E_{G} x_2). \] \bigskip \bigskip \bigskip \bigskip \bigskip \centerline{*****************************************} \centerline{TVC$(G, \Ubf{\Sigma}^1_1)\Rightarrow$ TVC$(G)$} -- since any Polish space is $\Ubf{\Sigma}^1_1$. \bigskip TVC(Abelian, $\Ubf{\Sigma}^1_1$), TVC(Nilpotent, $\Ubf{\Sigma}^1_1$),...etc. \bigskip \bigskip \centerline{TVC$(S_{\infty}, \Ubf{\Sigma}^1_1)$ fails!} \newpage $\:$ \bigskip \bigskip \bigskip \bigskip \noindent{\bf 2.5 Theorem} For $G$ a Polish group, \bigskip \bigskip \centerline{TVC$(G, \Ubf{\Sigma}^1_1)$ } \bigskip \bigskip \centerline{ {\bf iff}} \bigskip \bigskip \noindent there is no closed subgroup $H