% LaTeX Article Template - using defaults
\documentclass{conm-p-l}
%\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{latexsym}
%\pagestyle{myheadings}
%\markright{G. Hjorth}
\usepackage{amssymb}
\usepackage{latexsym}
% Set left margin - The default is 1 inch, so the following
% command sets a 1.25-inch left margin.
%\setlength{\oddsidemargin}{-0.15in}
% 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.5in}
% 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.3in}
% Set height of the text
%\setlength{\textheight}{8.1in}
% Set vertical distance between the text and the
% bottom of footer
%\setlength{\footskip}{0.8in}
% Set the beginning of a LaTeX document
\begin{document}
%\font\fib=CMDUNH10
%\fib
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
%\newenvironment{proof}[1][Proof]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}}
\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{notation}[1][Notation]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{question}[1][Question]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\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\C{{\mathbb C}}
\def\V{{\mathbb V}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\K{{\mathbb K}}
\def\B{{\mathbb B}}
\def\Q{{\mathbb Q}}
\def\o{{\omega}}
\def\oo{{\omega^{\omega}}}
\def\lo{{\omega^{<\omega}}}
\def\d{{\dot{\bigcup}}}
\def\h{{\cal H}}
\def\no{\noindent}
\def\cal{\mathcal}
\def\a{{\mathcal A}}
\def\b{{\mathcal B}}
\def\l{{\mathcal L}}
\def\n{{\mathcal N}}
\def\m{{\mathcal M}}
\def\p{{\mathcal P}}
\def\h{{\mathcal H}}
\def\co{{\mathcal O}}
\def\t{{\mathcal T}}
\def\c{{\mathcal C}}
\title{A dichotomy theorem for being essentially countable}
\author{\sc Greg Hjorth} % Enter your name between curly braces
\date{\today} % Enter your date or \today between curly braces
\subjclass{Primary 03E15, 04A15, 28A05, 54H05, 54H10;\\Secondary 03C15, 03C75}
\begin{abstract}
We introduce a definition to characterize when an orbit
equivalence relation is Borel reducible to a countable
equivalence relation. As a corollary we obtain a kind of
low basis theorem -- an orbit equivalence relation which arises
from an {\it effective} action of a recursively presented Polish
group on a recursive Polish space is Borel reducible to a countable
Borel equivalence relation if and
only if it is reducible to a $\Delta^1_1$ countable equivalence
relation using a $\Delta^1_1$ function.
We make some effort to draw out the consequences of the theorem
for the model theoretic context, which in turn raises an open
problem regarding first order logic.
\end{abstract}
\maketitle
%\tableofcontents
\section{\sc Introduction}
\label{introduction}
\begin{definition} We say that one equivalence relation, $E$, is
Borel reducible to another, $F$, written $E\leq_B F$,
if there is a Borel function $\theta$ such that
\[x_1 E x_2 \Leftrightarrow \theta(x_1) F \theta (x_2).\]
\end{definition}
\begin{definition}
An equivalence relation is {\it Borel} if it is Borel as a subset of
the product of the
space on which it is defined; it is {\it countable}
if all its equivalence classes are countable.
An equivalence relation on a standard
Borel space $X$ is
{\it essentially countable} if there is a countable Borel equivalence
relation $E$ to which it is Borel reducible.
\end{definition}
\begin{example}
It is trivially seen that if $E$ arises from the Borel
action of a {\it countable} group then necessarily it
is Borel and each equivalence class is countable.
More surprisingly Kechris has shown in
\cite{kechris2} that the orbit equivalence relations
arising from Borel actions of
locally compact Polish groups are necessarily
essentially countable.
\end{example}
In very general terms the essentially countable equivalence
relations might be thought of as those where there is some kind
of notion of ``finite rank".
\begin{example}
Let $\sigma$ be the sentence in ${\cal L}_{\omega_1, \omega}$
whose models are exactly the {\it finite rank}
torsion free abelian
groups -- that is to say, those abelian, torsion free groups
which have some finite sequence $g_1, g_2,...,g_n$ such that
for every $h\neq 0$ there is some $k$ such that $k\cdot h$ is
in the subgroup generated by $g_1, g_2,...,g_n$.
Let Mod($\sigma$) be the collection of
models for $\sigma$ with underlying set $\N$ and the
usual Borel structure (as described in
\cite{hjorthkechris}); let $\cong\!_{{\rm Mod}(\sigma)}$ be the
equivalence relation of isomorphism on Mod($\sigma$).
Then $\cong\!_{{\rm Mod}(\sigma)}$ is essentially countable.
In fact, at each $n$ we can let $\sigma_n$
be the sentence whose models are exactly the rank
$n$ torsion free abelian groups, and we obtain
$\cong\!_n(=_{\rm df}\cong\!_{{\rm Mod}(\sigma_n)})$
Borel reducible to the action of
$\Q^n$ by multiplication on the collection of all
subgroups of $(\Q^n, +)$.
Indeed recent years have witnessed an outpouring of papers
on these equivalence relations -- culminating
in Simon Thomas' \cite{thomas}, where it was
shown that at every $n$ one has
\[\cong_n<_B \cong_{n+1}.\]
On the other hand it is known the isomorphism relation
on countable torsion free abelian groups of infnite
rank is not essentially countable in any of its customary
Borel structures. (See e.g. \cite{hjorthtfa}, $\S$5 \cite{hjkelo}).
Indeed a natural example of an equivalence relation which
is not essentially
countable is given by considering the coding of countable
sets of reals; that is to say, for $f_1, f_2\in \R^\N$ set
\[f_1 F_2 f_2\]
if for all $n\in \N$ there exists $m_1, m_2\in \N$ with
\[f_1(n)=f_2(m_1),\]
\[f_2(n)=f_1(m_2).\]
One certainly finds in \cite{hjkelo} a proof that this equivalence
relation is not essentially countable and in
\cite{hjorthtfa} a proof that isomorphism on general
countable torsion free abelian groups Borel reduces $F_2$ --
though in both cases the results are folklore and invoking
theorems of these papers would represent a degree of overkill.
\end{example}
\begin{example} In the natural Borel structure, induced by
looking at group operations placed on some fixed countable
set, the isomorphism relation on finitely generated groups
is essentially countable. (See \cite{hjorthkechris}.)
This cannot be extended to general
countable groups, since, as noted above, the isomorphism
relation on countable abelian groups is already $\leq_B$ above
$F_2$.
\end{example}
A special kind of essentially countable equivalence relation
is formed by those which are smooth.
\begin{definition} An equivalence relation $E$ is {\it smooth}
if there is a Borel function $\theta$
from the space on which $E$ lives to $\R$ (or, equivalently,
any uncountable Polish space) with
\[x_1 E x_2 \Leftrightarrow \theta(x_1) = \theta(x_2).\]
\end{definition}
Not all essentially countable equivalence relations, even
among those given by the isomorphism relation on some natural
class of structures, are smooth. For instance, $\S$3.1 of
\cite{hjorthclassification} gives a gentle proof that
$\cong_1$, isomorphism of rank one torsion free abelian groups,
is not smooth.
In \cite{hjorthkechris} a model theoretic
analysis of smoothness and essential
countability is presented.
\begin{theorem} \label{hjorthkechris}
(Hjorth, Kechris)
Let $L$ be a countable language, with the
usual Borel structure generated by first order logic.\footnote{So that
for any $\psi$ and $\vec a$ a finite
sequence from $\N$, the set of $M$ which satisfy
$\psi(\vec a)$ is Borel; this is indeed a standard Borel
structure -- see \cite{grmory}.}
Let $\sigma\in {\cal L}_{\omega_1, \omega}$.
(I) The following are equivalent:
\leftskip 0.4in
\noindent (a) $\cong_{{\rm Mod}(\sigma)}$ is smooth;
\noindent (b)
there
is a countable fragment $F\subset {\cal L}_{\omega_1, \omega}$
such that for every ${M}\in$ {\rm Mod}($\sigma$) we have that
\[{\rm Th}_F{M},\]
the $F$-theory of ${M}$, is $\aleph_0$-categorical;
\noindent (c)
there
is a countable fragment $F\subset {\cal L}_{\omega_1, \omega}$
such that for every ${M}\in$ {\rm Mod}($\sigma$) we have that
\[{\rm Th}_F{M},\]
the $F$-theory of ${M}$, is atomic.
\leftskip 0in
(II) The following are equivalent:
\leftskip 0.4in
\noindent (a)
$\cong_{{\rm Mod}(\sigma)}$ is essentially countable;
\noindent (b) there
is a countable fragment $F\subset {\cal L}_{\omega_1, \omega}$
such that for every ${M}\in$ {\rm Mod}($\sigma$) we have some
$\vec a\in {M}$ such that
\[{\rm Th}_F\langle {M}, \vec a\rangle,\]
the $F$-theory of the expansion of
${M}$ obtained by adding names for all the elements
of the $\vec a$ sequence, is $\aleph_0$-categorical;
\noindent (c) there
is a countable fragment $F\subset {\cal L}_{\omega_1, \omega}$
such that for every ${M}\in$ {\rm Mod}($\sigma$) we have some
$\vec a\in {M}$ such that
\[\langle {M}, \vec a\rangle,\]
is $F$-atomic.
\leftskip 0in
\end{theorem}
\begin{question}
Does there exist a first order theory $T$ with
$\cong\!_{{\rm Mod(}T{\rm )}}$ essentially countable
but not smooth?
\end{question}
In light of \ref{hjorthkechris} the
question of whether smoothness and essential
countability coincide for
first order structures has a purely model theoretic
reading. We are asking for a
countable first order theory $T$
for which
there exists a countable fragment $F$ over which every
$M\models T$ has some $\vec a$ with
\[\langle M, \vec a\rangle\]
$F$-atomic, but for which there is no fragment $F'$ for
which every model $M\models T$ is $F'$-atomic; notice
that this purely model theoretic formulation makes
no explicit reference to countable models.
In practically all the standard cases, say for instance the
kinds of first order theories one finds in
\cite{changkiesler}, it is easily determined that
Mod($T$) is either smooth or not essentially countable.
While I would conjecture that an example of a countable
first order theory with $\cong_{{\rm Mod(}T{\rm )}}$
essentially countable but non-smooth should exist, but simply be
very hard to conceive, it does pay to seriously consider the
possibility that there may be a structure theorem which
denies this. This would represent some kind of basic obstruction
or dichotomy theorem for $L_{\omega, \omega}$ equivalence relations
which is entirely missing for $L_{\omega_1, \omega}$.
Here it is worth pointing out that any such dichotomy theorem
could not be proved using purely Baire category methods.
\begin{example} Let $G$ be a countable infinite group and
$L$ the language which contains function symbols $F_g$ for each
$g\in G$ along with unary predicates $(U_n)_{n\in\N}$.
Let $T$ be the first order theory which asserts that the composition
of the functions exactly mimics the group (so for each $g_1, g_2$ we
have an axiom asserting $F_{g_1}\circ F_{g_2}=F_{g_1g_2}$),
the identity element acts trivially ($\forall a (F_1(a)=a)$), and that
otherwise the action of $G$ is free (for each $g\neq 1$ we have
$\forall a(F_g(a)\neq a)$).
We can equip with Mod($T$), the space of $T$-structures with underlying
set $\N$, the usual topological structure, under which for every quantifier
free $\psi(\cdot)$ and $\vec a$ we have
\[\{M: M\models \psi(\vec a)\}\]
becomes clopen. In this topology it is a Polish space, and it follows
easily from the usual kinds of arguments that on no comeager set $C$
is
\[\cong|_C\]
smooth.
(Compare the arguments from say $\S$3.1\cite{hjorthclassification}.)
A failure to be essentially countable is not yet detectable
at the level of Baire category.
If we take $C$ to be the comeager set of models on which the group action is
transitive, that is to say, the structure satisfies
the $L_{\omega_1, \omega}$
sentence
\[\forall a, b\bigvee_{g\in G}(F_g(a)=b),\]
then we have that
\[\cong|_C\]
{\it is} essentially countable.
This can be observed by (II)(c) \ref{hjorthkechris} since
on this set we have that any $M\in C$ is the functional
closure of {\it any} $a\in M$.
However the isomorphism relation of the theory is not
essentially countable. One way to see this is actually to use
forcing, starting with a fragment $F$ in the ground model and
showing its failure to achieve (II)(c) in a suitable generic
extension.
We begin with an action of $G$ on $\N$ which is free but has
infinitely many orbits and interpret the function symbols
$(F_g)_{g\in G}$ accordingly.
Then we force to obtain mutually Cohen generic $(x_a)_{a\in \N}$
elements of $2^\N$; for each $x_a$ we define the
indicated pattern of unary predicates at $a$, with
\[ U_n(a)\Leftrightarrow x_a(n)=1.\]
It is a routine exercise in forcing to
see that if $a_0,a_1..., a_\ell=\vec a$ is a {\it finite} sequence
from $\N$ then
\[{\rm Th}_F\langle M, \vec a\rangle\]
can be uniformly defined in
\[V^{[(x_{F_g(a_i)})_{i\leq \ell, g\in G}]}\]
from $F$ and ${(x_{F_g(a_i)})_{i\leq \ell, g\in G}}$;
then considering some $b\notin
\{F_g(a_i):{i\leq \ell, g\in G}\}$ we have that
the $F$-type of $x_b$ will not be in
$V^{[(x_{F_g(a_i)})_{i\leq \ell, g\in G}]}$, and hence
certainly not $F$-atomic over
${\rm Th}_F\langle M, \vec a\rangle$.
\end{example}
In this note we introduce a new definition to analyze
essential countability.
\begin{definition} Let $G$ be a Polish group acting continuously on a
Polish space $X$. We then say that $X$ is a {\it stormy}
$G$-space if for every non-empty, open
$V\subset G$ and $x\in X$ we have that
the natural map
\[g\mapsto g\cdot x\]
from $V$ to $V\cdot x$ is not an open function.
\end{definition}
For future reference note that this definition has a
kind of stability and upward persistence.
\begin{lemma}
\label{change}
If $X$ is a stormy
Polish $G$-space with respect to the topology $\tau$, then
for any stronger Polish $G$-space topology $\tau_0\supset \tau$ we
can find a $G_\delta(X, \tau)$ subspace $X_0\subset X$ such that
$(X_0, \tau_0)$ is still a stormy Polish $G$-space.
\end{lemma}
\medskip
Proof.
It is an entirely classical fact that we can find an $X_1$ which
is a $G_\delta$ subspace of $(X, \tau)$ such that the induced inclusion
map
\[(X_1, \tau)\hookrightarrow (X, \tau_0)\]
is continuous; this follows since any Borel map is continuous
on a dense $G_\delta$ (see \cite{kechris}).
Then we let
\[X_0=\{x\in X: \forall^*g\in G(g\cdot x\in X_1)\},\]
the set of points for which a comeager collection of
group elements place us in $X_1$.
Using the continuity of the action of $G$ on $(X, \tau_0)$
we still have that the induced map
\[(X_0, \tau)\hookrightarrow (X, \tau_0)\]
continuous; so the topology $\tau$ on $X_0$ equals
$\tau_0$ on $X_0$.
So then the structure of the definition of stormy, with its insistence
that something happens at {\it every} orbit, guarantees that
\[(X_0, \tau_0)\]
is still stormy.
\hfill $\Box$
\bigskip
An especially important instance of this definition is
provided by model theory. Here let us consider that $S_\infty$
acts in the usual manner
on the space of all models of some infinitary sentence
$\sigma\in L_{\omega_1, \omega}$; cofinally many of the Polish
topologies are of the form $\tau_F$ for some countable fragment
$F$ -- that is to say, they have a basis consisting of sets of
the form
\[\{M: M\models \varphi(\vec a)\}\]
for some $\varphi\in F$, $\vec a\in \N^{<\omega}$.
(Again, see \cite{hjorthkechris}).
Here we may assume without loss of generality that we restrict ourselves
to open sets $V$ of the form
\[\{\pi\in S_\infty: \forall i\leq \ell (\pi(a_i)=a_i)\}\]
for some chosen $\vec a=a_0, a_1,...a_\ell$ in $\N$.
Then the action of $S_\infty$ on $\langle$ Mod($\sigma$), $\tau_F\rangle$
is stormy
if and only if for every $M\models \sigma$ there is {\it no}
$\vec a\in M$ with $\langle M, \vec a\rangle$ being $F$-atomic.
Building on the methods of \cite{hjorth}:
\begin{theorem}
\label{dichotomy}
Let $G$ be a Polish group and $X$ a Polish $G$-space with the
induced orbit equivalence relation $E_G^X$ Borel. Then
exactly one of the following holds:
(I) $E^X_G$ is essentially countable;
(II) there is a stormy Polish $G$-space $Y$ and a continuous $G$-embedding
\[\rho: Y\rightarrow X.\]
\end{theorem}
Note in (II) that since $\rho$ is one to one, the image $\rho[Y]$
is Borel in $X$. Thus we may without loss of generality assume that
$Y$ is a Borel invariant subset of $X$ and that we have found a Polish
topology on $Y$ which refines the original $X$-topology under which
the action remains continuous and becomes stormy.
I have no concrete instances of an equivalence relation
whose essential countability can only be affirmed or refuted
by appeal to \ref{dichotomy}.
However it can be said that the argument is effective;
it uses the ``geometry" of $\Sigma^1_1$ sets in the now usual way.
In particular the following represents a
corollary of the method, which would presumably have not been obvious hitherto.
\begin{theorem} Let $G$ be a recursive Polish group and $X$ a recursive
Polish $G$-space with the
induced orbit equivalence relation $E_G^X\in \Delta^1_1$.
If $E^X_G$ is essentially countable, then there is a countable
$\Delta^1_1$ equivalence
relation on an effective Polish space to which $E^X_G$ is reducible by a
$\Delta^1_1$ function.
\end{theorem}
It might also be worth thinking about the model
theoretic consequences of this theorem. Again, for a
logician the isomorphism relations on classes of countable
structures, while not quite Borel, comprise the central
examples to which all others should be compared.
In the next corollary we bear in mind that $\cong\!_{{\rm Mod}(\sigma)}$
is Borel if and only if there is some countable ordinal which bounds the
Scott heights of models of $\sigma$. This result from
\cite{beckerkechris} makes possible to state the following
corollary in largely model theoretic terminology.
\begin{corollary}
\label{model}
Let $\sigma\in L_{\omega_1, \omega}$ for some countable
language $L$.
Assume that there is some countable ordinal
which bounds the Scott heights of the models of $\sigma$.
Then exactly one of the following holds.
(I) there
is a countable fragment $F\subset {\cal L}_{\omega_1, \omega}$
such that for every ${M}\in$ {\rm Mod}($\sigma$) we have some
$\vec a\in {M}$ such that
\[\langle {M}, \vec a\rangle,\]
is $F$-atomic;
(II) there is a countable fragment $F$
and some $\varphi\in L_{\omega_1, \omega}$
for which there exists a model of $\varphi\wedge \psi$,
such that for every
\[M\models \varphi\]
there is no $\vec a\in M$ with
\[\langle M, \vec a\rangle\]
$F$-atomic.
\end{corollary}
To see that the corollary indeed follows from the
theorem we observe first of all that
(I) \ref{model} is a direct restatement of
(I) \ref{dichotomy} in light of
\ref{hjorthkechris}. This leaves (II).
Note at this point we actually obtain in applying
\ref{dichotomy} a
Borel $S_\infty$-invariant Borel
subspace $Y$ and a Polish topology $\tau_Y$ on $Y$ under
which the action becomes stormy.
We may
find a countable
fragment $F$ such that $\tau_F\supset \tau_Y$
by \cite{lopez}, and then by \ref{change} find a $Y_0\subset Y$
so that $(Y_0, \tau_F)$ is a stormy Polish $S_\infty$-space;
membership in $Y_0$, by \cite{lopez} again, is given by
some sentence $\varphi\in L_{\omega_1, \omega}$.
\section{\sc Setting Sail}
In all the lemmas below we assume that $G$ is a Polish group and
$X$ is a Polish $G$-space. $E^X_G$ is the orbit equivalence relation.
We assume there are fixed countable bases for $X$ and $G$ and that
the basis for $G$ contains a neighborhood basis of symmetric sets
around $1_G$.
\begin{lemma} \label{1}
Suppose for every $x\in X$ there is a non-empty open $V\subset G$ with
\[V\rightarrow V\cdot x\]
\[g\mapsto g\cdot x\]
an open mapping.
Then $E^X_G$ is essentially countable.
\end{lemma}
Proof.
Let us say that a non-empty basic open set $V\subset G$ is {\it $x$-safe} if for
all $W\subset V$ open, non-empty, $\overline{W\cdot x}$ includes a
non-empty relatively
open subset of $\overline{V\cdot x}$. Our assumption in the lemma yields that for
each $x\in X$ there is such an $x$-safe point. Note moreover that any
non-empty open subset of an $x$-safe set is again $x$-safe.
If $V$ is $x$-safe and $U\subset X$ is a non-empty basic
open set, then we
say that $U$ is a {\it $V$-$x$-harbor} if there is some
symmetric basic open neighborhood
$W$ of $1_G$ such that
\[\forall h\in W\forall y\in U\cap \overline{Vh\cdot x}
( y\in \overline{V\cdot x}).\]
\bigskip
\no{\bf Claim(I):} For each $x$ there are $U$ and $V$ as above.
\bigskip
\no{\bf Proof of claim:} Choose open
$\hat{V}$ with
\[\hat{V}\mapsto \hat{V}\cdot x\]
an open map. Let $g_0\in \hat{V}$. Appealing to the continuity of
the group operations we may choose $V\subset \hat{V}$ an open
neighborhood of $g_0$ and $W$ a symmetric
open
neighborhood of $1_G$ such that
\[VW\subset \hat{V}.\]
$V$ is clearly $x$-safe, since the mapping
\[V\rightarrow V\cdot x\]
is open. Let us choose $U$ basic open with
\[\overline{V\cdot x}\supset U\cap \overline{\hat{V}\cdot x}.\]
Then we have for all $h\in W$ and $y\in U\cap \overline{Vh\cdot x}$
\[y\in U\cap \overline{\hat{V}\cdot x}\]
\[\therefore y\in \overline{V\cdot x},\]
just as required.
\hfill (Claim(I)$\Box$)
\bigskip
For each $x$, the collection of such $(U, V)$ as above is uniformly
$\Ubf{\Pi}^1_1$ in $x$. The bases from which they are chosen
are countable. Hence we may assign
\[x\mapsto (U_x, V_x)\]
in a Borel manner so that each $V_x$ is $x$-safe and each $U_x$ is
a $V_x$-$x$-harbor.
We can then define a Borel function
\[X\rightarrow {\cal F}(X),\]
from $X$ to the standard Borel space of closed subsets of $X$,
given by
\[x\mapsto \overline{U_x\cap V_x\cdot x}.\]
By Kechris' criterion for being essential countable, as presented at
$\S$5 of \cite{hjorthbanach}, it is enough to show
that this map has countable image on each equivalence class (claim(II))
and that images of distinct equivalence classes are disjoint (claim(III)).
\bigskip
\no{\bf Claim(II):} For each $x$, the set $\{\overline{U_y\cap V_y\cdot y}:
y\in [x]_G\}$ is countable.
\bigskip
\no{\bf Proof of claim:} Otherwise we could find an uncountable set $(y_\alpha)_{\alpha
\in\aleph_1}$ of
elements of $[x]_G$
with each $y_\alpha$ having the same $U_{y_\alpha}=U, V_{y_\alpha}=V$
and the same $W$ witnessing that $U$ is a $V$-$y_\alpha$-harbor, and
yet
\[U\cap \overline{V\cdot y_\alpha}\neq U\cap\overline{V\cdot y_\beta}\]
for $\alpha\neq \beta$.
Considering the separability of the group $G$ we can find two $y, y'$ in this
uncountable set with $y\in {W}y'$ and $y'\in {W}y$.
Then for all $z\in U\cap \overline{V\cdot y}\subset
U\cap \overline{VW\cdot y'}$ we must have by assumptions on $U$ and $V$ that
$z\in U\cap \overline{V\cdot y'}$, and conversely. Thus
\[U\cap \overline{V\cdot y}= U\cap \overline{V\cdot y'}\]
after all.
\hfill(Claim(II)$\Box$)
\bigskip
\no{\bf Claim(III):} If $V$ is $x$-safe, then $V\cdot x$ is comeager in
$\overline{V\cdot x}$.
\bigskip
\no {\bf Proof of claim:} Suppose not. Then there is some open $U\subset X$
with $V\cdot x$ meager in $U\cap \overline{V\cdot x}$. And then we can find
some open $V_0\subset V$ and open $U_0\subset U$ with $V_0\cdot x$ dense in
$U_0\cap\overline{V\cdot x}$; which would place us in the situation that $V_0$
is now our $x$-safe set and $V_0\cdot $ is meager in $U_0\cap\overline{V_0\cdot x}$.
But then if we cover $V_0\cdot x$ by countably many closed
sets, $F_0, F_1,...F_n,...$,
each of which is nowhere dense in $U_0\cap\overline{V_0\cdot x}$, then there must be
some open non-empty $W\subset V_0$ with $W\cdot x\subset F_n$, at some $n\in\N$.
And so $W\subset V_0\subset V$ contradicts the definition of safety.
\hfill (Claim(III)$\Box$)
\hfill $\Box$
%In fact one can show that if $V$ is $x$-safe, then the induced map
%$V\rightarrow V\cdot x$ is open. The argument of claim(III) will show that
%each $W\subset V$ open will have $W\cdot x$ containing a relatively
%non-meager set in $V\cdot x$, and then some further calculations show that
%it must include some relatively open set in which it is comeager.
This lemma has as an immediate corollary a result previously proved by
Alexander Kechris by other means:
\begin{corollary}(Kechris) If $G$ is a locally compact Polish group and
$X$ is a Polish $G$-space, then $E_G^X$ is essentially countable.
\end{corollary}
Proof.
Fix $x\in X$ and consider some non-empty precompact $V\subset G$.
$\overline{V}/G_x$ is compact\footnote{Here as elsewhere we follow the
notation of \cite{beckerkechris}; so $G_x$ is the {\it stabilizer}
of the point $x$: that is to say, the subgroup $\{g\in G: g\cdot x=x\}$.}, and
hence the natural map
\[\overline{V}/G_x\twoheadrightarrow \overline{V}\cdot x\]
maps closed sets to closed sets and is one-to-one and onto, thus it
is open. In particular
\[V/G_x\twoheadrightarrow V\cdot x\]
and
\[V\twoheadrightarrow V\cdot x\]
are both open, and we fall under the case assumptions of \ref{1}.
\hfill $\Box$
\begin{lemma}
\label{2}
If $E^X_G$ is essentially countable, then for a comeager collection of
$x\in X$
there exists $V\subset G$ open and
non-empty with
\[V\rightarrow V\cdot x\]
\[g\mapsto g\cdot x\]
open.
\end{lemma}
Proof.
Let
\[\theta: X\rightarrow Z\]
be a Borel function reducing $E^X_G$ to some countable equivalence relation
on a Polish space $Z$. Following 4.1 \cite{gao} (or see $\S$18 of \cite{kechris}, along with references
tracing back to earlier work by Burgess) we have that the range of
$\theta$ is Borel and there is a Borel function
\[\rho: {\rm Ran}(\theta)\rightarrow X\]
such that for all $z\in {\rm Ran}(\theta)$ we have $\theta(\rho(z))=z$.
For each $x\in X$ let
\[p_x=\rho(\theta(x));\]
thus this $x\mapsto p_x$ is a Borel function which in effect ``selects" a
countable set from each orbit.
Following 7.1.2 of \cite{beckerkechris}
(the orbit equivalence relation is Borel, and thus too is the stabilizer
function $x\mapsto G_x$ from $X$ to ${\cal F}(X)$) we may in a Borel manner
choose for each $x$ a group element $g_x$ with
\[g_x\cdot x= p_x.\]
For the moment let us say that a point $y\in X$ is {\it good} if there is some basic
open neighborhood $W$ of $1_G$ such that $\forall^*h\in W(p_y=p_{h\cdot y})$.
\bigskip
\no {\bf Claim:} The set of good points is comeager.
\bigskip
\no{\bf Proof of claim:}
Otherwise use Kuratowski-Ulam to find some $y\in X$ and open
non-empty $V\subset G$ such that $\forall^*g\in V(g\cdot y$ is not good$)$.
Then since $\{p_{y'}: y'E_G^X y\}$ is countable, we may find some single
$y_0$ and non-empty open $W\subset V$ such that
\[\forall^*g\in W(p_{g\cdot y}=y_0).\]
Then we find some basic open neighborhood $\hat{W}$ of $1_G$ and $g_0\in G$
with $\hat{W}g_0\subset W$; after possibly nudging $g_0$ slightly, we may assume
it falls into the
relatively comeager sets $\{g\in W: g\cdot y$ not good $\}$ and
$\{g\in W: p_{g\cdot y}=y_0\}$.
But this gives
\[\forall^*g\in \hat{W} (p_{g\cdot(g_0\cdot y)}=y_0=p_{g_0\cdot y}),\]
and hence $g_0\cdot y$ must be good after all.
\hfill (Claim$\Box$)
\bigskip
Let $(W_\ell)_{\ell\in\N}$ be a neighborhood basis at $1_G$. We may apply the above claim
to choose a Borel function
\[\gamma: X\rightarrow \N\]
such that
\[\forall^*y\in X\forall^*h\in W_{\gamma(y)}(p_y=p_{h\cdot y}).\]
Finally choose a comeager set $C\subset X$ such that
\leftskip 0.4in
\no (a) $\gamma|_C$ is continuous on $C$;
\no (b) $x\mapsto g_x$ and $x\mapsto p_x$ are continuous on $C$;
\no (c) for all $x\in C$ we have $\forall^*g\in W_{\gamma(x)}(p_x=p_{g\cdot x})$.
\leftskip 0in
Let $x\in X$ be such that $\forall^*g\in G(g\cdot x\in C)$. We can then find some
non-empty
open set $\hat{V}\subset G$ and a point $x_0\in [x]_G$
such that
\[\forall^*g\in\hat{V}(p_{g\cdot x} =x_0).\]
We then find open $U_0$ having non-empty intersection with $\hat{V}\cdot x$ such that for
some single $\ell_0$
\[\forall y\in U_0\cap C(\gamma(y)=\ell_0).\]
Finally we pass to $V=\{g\in \hat{V}: g\cdot x\in U_0\}$. I now want to show that
$g\mapsto g\cdot x$ is open from $V$ to $V\cdot x$.
So consider some $y\in V\cdot x$ and $V_0$ an open neighborhood of $1_G$; I want to
show that there is an open $U_1$ containing $y$ such that for all $y_1\in V\cdot x\cap U_1$
we have $y_1\in V_0\cdot y$.
First choose $V_1$ an open neighborhood of $1_G$ with
\[(V_1)^{-1}=V_1,\]
\[(V_1)^4\subset V_0,\]
\[V_1\cdot y\subset V\cdot x,\]
\[V_1\subset W_{\ell_0}.\]
And then take $g_0\in V_1$ with
\[y'=g_0\cdot y\in C\]
and
\[p_{y'}=x_0.\]
And then let $U'\subset U_0$ be a basic neighborhood of $y'$ such that for all
$\hat{y}\in U'\cap C$ we have
\[g_{\hat{y}}\in g_{y'}V_1.\]
I claim that $U_1=U_0\cap (U')^{\Delta V_1}$ succeeds.
For this purpose, let us suppose $y_1\in V\cdot x\cap U_1$; we can choose
$g_1\in V_1$ with
\[y_2=_{\rm df} g_1\cdot y_1 \in V\cdot x\cap U_1\cap C\]
and $p_{y_2}=x_0$. We may then appeal to the definition of $U_1$ to find
$g_2\in V_1$ with
\[y_2'=_{\rm df} g_2\cdot y_2\in U'\cap C.\]
Since $y_2\in U_0\cap C$ and $g_2\in V_1\subset W_{\ell_0}$ we can appeal to the
assumption on $U_0$ to find a sequence of group elements $(\epsilon_n)_{n\in\N}$
which approach $1_G$ and have the property that
\[p_{\epsilon_n\cdot y'_2}=p_{y_2}=x_0\]
and each $\epsilon_n\cdot y'_2\in C$; since the function $\hat{y}\mapsto p_{\hat{y}}$
is continuous on $C$ we must have $p_{y'_2}$ equals $x_0$ as well.
By assumption on $U'$ we may find some $h\in V_1$ with
\[g_{y'_2}=g_{y'}\cdot h.\]
But this gives
\[g_{y'_2}\cdot y_2'=x_0=g_{y'}\cdot y'\]
\[\therefore g_{y'}h\cdot y_2'=g_{y'}\cdot y'\]
\[\therefore h\cdot {y'_2}=y'\]
\[\therefore hg_2g_1\cdot y_1=y'=g_0\cdot y\]
\[\therefore y_1=g_1^{-1}g_2^{-2}h^{-1}g_0\cdot y\in (V_1)^4\cdot y\subset V_0\cdot y\]
thereby concluding the proof.
\hfill $\Box$
\begin{definition} Let $G$ be a Polish group and
$X$ a Polish $G$-space. We say that $X$ is a {\it stormy}
$G$-space if
\[V\rightarrow V\cdot x\]
\[g\mapsto g\cdot x,\]
as $V$ ranges over non-empty open subsets of the group and $x$ ranges
over points in $X$, is never an open mapping.
\end{definition}
\begin{proposition}
\label{proposition}
If $E^X_G\leq_B E$, and $X$ is a stormy Polish $G$-space, then
$E$ is not essentially countable.
\end{proposition}
Proof.
This is a corollary of \ref{2}.
\hfill $\Box$
In the remainder of the note we wish to start working towards a
kind of converse to this proposition. If $E$ is induced by continuous action
of a Polish group $G$, then $E$ is essentially countable if and only
if there is no stormy Polish $G$-space $Y$ and continuous $G$-embedding
from $Y$ to $X$. It might be worthwhile first to pause in order to
point out a couple of
facts in the neighborhood of this definition.
\begin{example} It is not hard to see that if the canonical map from
$V$ to $V\cdot x$ is open, then $V\cdot x$ is comeager in its closure.
%Something like this was implicit in \ref{1}, and in any case we can
%apply the usual Effros argument to see that $V\cdot x$ will homeomorphic
%to $V/G_x$,
%and hence it will be a Polish space in its own right, and
%hence a dense $G_\delta$ in $\overline{V\cdot x}$.
This was implicitly proved at claim(III) of \ref{1}.
The reverse implication fails.
For instance let $G=S_\infty$, the infinite symmetric group, and consider the
space $B_2$, consisting of all
one-to-one sequences $\vec x=(x_0, x_1,...)\in ([0,1])^\N$. The responsible
group acts by permutation of the indices
in the obvious manner:
\[(\pi\cdot \vec x)_n=x_{\pi^{-1}(n)}.\]
Consider the point $\vec y=(y_0, y_1,...)$ defined by
\[y_0=0,\]
but
\[y_n=\frac{1}{n}\]
for $n>0$. We can then let
\[V_0=\{\pi\in S_\infty: \pi(0)=0\},\]
and for $k>0$ we let
\[V_k=\{\pi\in S_\infty: \pi(k)=0, \pi(0)=k\}.\]
It is not hard to see that at each $k>0$ we have
$V_k\cdot \vec y$ comeager in its closure; and thus for
\[V=\bigcup_{k\geq 0}V_k\]
we have that $V\cdot \vec y$ comeager in $\overline{V\cdot \vec y}$.
In fact the set $V\cdot \vec{y}$ is a $G_\delta$.
A point $\vec x$ is in $V\cdot \vec y$ if and only if
\leftskip 0.4in
\noindent (i) $\forall n, m\exists \ell (|x_\ell-1/n|<1/m)$;
\noindent (ii) $\forall n, \ell_1, \ell_2(\ell_1\neq \ell_2
\Rightarrow (|x_{\ell_1}-1/n)|\geq (n+1)^{-2} \vee
|x_{\ell_2}-1/n)|\geq (n+1)^{-2})$;
\noindent (ii) $\forall \ell, m\exists n (|x_\ell -1/n|<1/m)$;
\noindent (iv) $\forall m \exists k\neq 0 ((|x_0|<1/m)\vee
(|x_k|<(k+1)^{-2}\wedge |x_0-1/k|<(m(k+1))^{-2})).$
\leftskip 0in
\noindent However the map
\[V\rightarrow V\cdot \vec y\]
\[\pi\mapsto \pi\cdot \vec y\]
is not open, since $V_0\cdot \vec y$ is contained in a closed nowhere
dense subset of $\overline{V\cdot \vec y}$.
\end{example}
\begin{question}
Suppose that for every $x\in X$ there is {\it some} $V$ such that
$V\cdot x$ is non-meager in $\overline{V\cdot x}$. Must $E_G^X$ be essentially
countable? (must the hypotheses of \ref{1} hold?)
\end{question}
\begin{proposition}
\label{standard}
Let $G$ be a Polish group acting continuously on a Polish space $X$. Let
${\cal B}$ be a countable basis for $G$. Suppose
\[\forall^*x\in X\forall W\in {\cal B}(W\neq 0\Rightarrow
W\cdot x{\rm \: is \:
meager \: in\: } \overline{W\cdot x}).\]
Then $E_G^X$ is not essentially countable.
\end{proposition}
Proof.
First of all we can take a dense $G_\delta$ set $C\subset X$
such that for all $x\in C$ and all $W\in {\cal B}, W\neq 0$ we have
$W\cdot x{\rm \: is \:
meager \: in\: } \overline{W\cdot x}$. Then we can let
\[X_0=C^{*G},\]
the Vaught transform of $C$. This is then an invariant $G_\delta$ set,
and it suffices to show $E_G^{X_0}$ is not essentially countable. For this
it suffices to observe the following claim:
\smallskip
\no {\bf Claim:} $X_0$ is a stormy Polish $G$-space.
\smallskip
\no {\bf Proof of Claim:} Fix $x\in X_0$ and $V\subset G$ open. We may then
choose $\epsilon\in G$ with $\epsilon\cdot x\in C$. Then we may choose
some non-empty $W\in{\cal B}$
with $W\epsilon \subset V$.
$W\cdot (\epsilon\cdot x)$ is meager in $\overline{W\cdot (\epsilon\cdot x)}$,
and thus the map
\[W\rightarrow W\cdot (\epsilon\cdot x)\]
\[g\mapsto g\epsilon\cdot x\]
is not open, and hence
\[W\epsilon\rightarrow W\epsilon\cdot x\]
\[g\epsilon\mapsto g\epsilon\cdot x\]
is not open, and thus, since $W\epsilon\subset V$,
\[V\rightarrow V\cdot x\]
\[g\mapsto g\cdot x\]
is also not an open mapping. \hfill (Claim$\Box$)
\hfill $\Box$
\begin{example} There is a canonical example of a Polish group giving
rise to an orbit equivalence relation which is not essentially countable.
The orbit equivalence relation, $F_2$, corresponds in some rough sense to
countable sets of reals. It arises on the $B_2$, the space of one-to-one
sequences of reals in the unit interval, as a result of the natural action of
$S_\infty$ permuting the indices, as introduced in the previous example.
There are several ways to prove that this equivalence relation is not
essentially countable. One can even use forcing and give a metamathematical
proof. However the most direct method, as sketched in the exercises from
chapter 2 of \cite{hjorthclassification}, is in fact to show that for ${\cal B}$ the
canonical basis of $S_\infty$, we have for each $W\in {\cal B}$ non-empty
\[\forall^*\vec x\in B_2(W\cdot \vec x{\rm \: is \:
meager \: in\: } \overline{W\cdot \vec x}),\]
and then to combinatorially verify that no function continuous on a comeager set
can reduce $F_2$ to a countable equivalence relation.
The interest of \ref{standard} is to show that this ``standard proof" fits
naturally into a more general context.
\end{example}
\section{\sc Organizing the Cases}
We from now on assume that $G$ is a Polish group, which is recursive
as a Polish space, with the group operations of multiplication and inversion
both recursive and continuous. We assume that $X$ is a recursive Polish space,
equipped with an action of $G$ on $X$ which is recursive and continuous
as a function
\[G\times X \rightarrow X.\]
We further assume $E^X_G\in \Delta^1_1$.
We wish to work towards showing that either $E^X_G$ may be reduced in
to a countable Borel equivalence relation or we may
continuously and in an action respectful manner embed into $X$ a stormy
Polish $G$-space. In the first case one can in fact obtain that $X$ is
reducible to a countable Borel equivalence relation which is actually
$\Delta^1_1$ using a function which is actually $\Delta^1_1$; for clarity of
exposition we will not stress the various small calculations which must be
checked to obtain this extra effectivity, but instead push on with the proof of
the main result at \ref{dichotomy}. At the very end we make a few remarks about
how it may be refined.
In general of course the Polish group, the Polish space, and the
action of the group on the space might only be recursive in $z$, for some
parameter $z\in \N^\N$. The proof of this
more general case is a relativized version of the specific one we consider below.
We assume that $G$ and $X$ come equipped with some suitably recursive countable bases in
the sense of \cite{hjorth}.
At some point it will be helpful to make some simplifying assumptions: We ask that the
basis for $G$ be closed under finite intersection and inversion;
that the basic open sets in $X$ and $G$
be closed under translation by elements from the subgroup $G_0$ consisting of
recursive elements of $G$.
%\begin{definition} For $A_0,B\subset X$ two $\Sigma^1_1$ sets,
%$W_0, W_1, V_0, V_1$ basic open
%subsets of $G$, with $1_G\in V_0, V_1$, $V_0^{-1}=V_0$, $V_1^{-1}=V_1$,
%we say that {\it $(B, W_1)$ is $V_1$-local for
%$(A_0, W_0, V_0)$} if
%\[\forall x\in A_0^{\Delta W_0}\forall y_1, y_2\in
%V_0\cdot x \cap B^{\Delta W_1}(y_1\in V_1\cdot y_2).\]
%\end{definition}
%So the idea of the definition is that if $(B, W_1)$ is $V_1$-local for
%$(A_0, W_0, V_0)$, then in some ways it describes some piece
%of $V_0\cdot x$ (for any suitable $x$, that to say any $x\in A_0^{\Delta W_0}$),
%which is small in the sense that any two $y_1, y_2 \in V_0\cdot x\cap B^{\Delta W_1}$
%we must have that they are just separated by a group element in $V_1$. Of course
%for a given $V_0$ we can always find many
%$V_1, W_0,W_1, B_0, A_0, B$ to complete the definition:
%We let $V_0=V_1$ and then choose the remaining objects without concern.
%The important question, on which the dichotomy theorem rests, is whether given $V_0, V_1$
%and some possible restrictions on $A_0$ and $W_0$, can we find $B$ and $W_1$.
%It is important to note that this definition is $\Pi^1_1$ in the
%parameters.\footnote{Throughout
%we assume some reasonably effective enumeration of the bases; we
%will not explicitly spell out
%the details of how this can be done or what it would mean.} The
%point is that if $E^X_G$ is $\Delta^1_1$
%then it follows from Becker-Kechris that the stabilizer function $x\mapsto G_x$ is
%$\Delta^1_1$, in some appropriately understood effective presentation of the collection of
%closed subsets of $G$. From this we obtain that the set of $(y_1, y_2, V_1)$ such that
%\[y_1\in V_1\cdot y_2\]
%is $\Delta^1_1$. This granted, the definition is clearly $\Pi^1_1$.
%Therefore by $\Pi^1_1$ reflection,\footnote{See \cite{hamash}.}
%if $(B, W_1)$ is $V_1$-local for
%$(A_0, W_0, V_0)$, then there are $\Delta^1_1$
%sets $D_B\supset B$, $D_{A_0}\supset A_0$ with
%$D_B$ $V_1$-local for $(D_{A_0}, W_0, V_0)$.
\begin{definition} For $A\subset X$ be $\Sigma^1_1$, $W_0, V_0\subset G$ basic open
with $1_G\in V_0$, $V_0^{-1}=V_0$, we say that $(A, W_0)$ is
{\it $V_0$-damming} if for all $V_1\subset G$ with $1_G\in V_1$, $V^{-1}_1=V_1$,
all
$x\in A^{\Delta W_0}$,
and $y_0\in V_0\cdot x$, there is
$B\in \Delta^1_1$ and there is
$W_1\subset G$ basic open, with
\[y_0\in B^{\Delta W_1}\]
such that
\[\forall y_1, y_2 \in V_0\cdot x\cap B^{\Delta W_1}(y_1\in V_1\cdot y_2).\]
\end{definition}
The property of being $V_0$-damming is $\Pi^1_1$ in the
indices. The
point is that if $E^X_G$ is $\Delta^1_1$
then it follows from \cite{beckerkechris} $\S$7.1
that the stabilizer function $x\mapsto G_x$ is
$\Delta^1_1$, in some appropriately understood effective presentation of the collection of
closed subsets of $G$. From this we obtain that the set of $(y_1, y_2, V_1)$ such that
\[y_1\in V_1\cdot y_2\]
is $\Delta^1_1$. This granted, it all routinely unravels to
the level of $\Pi^1_1$.
Thus by $\Pi^1_1$-reflection\footnote{See \cite{hamash}.}, if
$(A, W_0)$ is $V_0$-damming then we may find some $\Delta^1_1$ set $D\supset A$
with $(D, W_0)$ again $V_0$-damming.
We are here confronted with a split in cases.
\def\Xb{X_{\rm bad}}
\def\X*{X_{\rm * bad}}
\begin{definition} We let $\Xb$ be the set of all $x\in X$ such that for all
$A\in\Sigma^1_1$, all basic open $W_0, V_0\subset G$ with $1_G\in V_0$,
$V_0^{-1}=V_0$, if $x\in A^{\Delta W_0}$ then $(A, W_0)$ is not
$V_0$-damming.
\end{definition}
The set $\Xb$ is $\Sigma^1_1$ by the reflection argument indicated above.
From the structure of the definitions
one can see that $\Xb$ is invariant under the action of $G_0$:
if $g_0\cdot x\in A^{\Delta W_0}$ for some $g_0\in G_0$, some $V_0$-damming $(A, W_0)$,
then $x\in A^{\Delta W_0g_0}$ and $(A, W_0g)$ is $g_0^{-1}V_0g_0$-damming.
But then we see that it must be invariant under the entire action of $G$,
since if $g_0\cdot x\in A^{\Delta W_0}$ then for any $g$ sufficiently close to $g_0$
we have $g\cdot x\in A^{\Delta W_0}$. Thus
$\Xb$ is invariant under the action of the entire group $G$.
Whether this set $\Xb$ is empty provides the split in cases.
\begin{notation}
From now on let us understand that
\[V_0, V_1, V_2,..., V,\hat{V}, V',W, ...,
W_0, W_1, W_2...\]
and such like always refer to basic
open subsets of the group $G$.
\end{notation}
\section{\sc Case(1): $\Xb$ is Empty}
\begin{claim} \label{update}
For $x\in X$ there exists $V_0$ non-empty such that for all
$y\in V_0\cdot x$ and $V_1$ symmetric containing $1_G$,
we have some $B\in \Delta^1_1$ and $W\subset G$ such that
\[y\in B^{\Delta W},\]
\[\forall y_1, y_2\in B^{\Delta W}\cap V_0\cdot x(y_1\in V_1\cdot y_2).\]
\end{claim}
Proof.
The case assumption implies that
every such $x$ will be included in some $A^{\Delta W_0}$
which necessitates some $V_0$ to succeed.
\hfill $\Box$
But then we
may find a countable algebra ${\cal B}$ of $\Delta_1^1$ subsets of $X$
with the
following properties:
\leftskip 0.4in
\noindent (i) ${\cal B}$ is closed under finite boolean operations;
\noindent (ii) ${\cal B}$ is closed under translation by elements in $G$;
\noindent (iii) for any $B\in {\cal B}$ and $V$ basic open we have
\[C^{\Delta V}, C^{*V}\in {\cal B};\]
\noindent (iv) $\forall x\in X\exists V_0\neq 0\forall
y\in V_0\cdot x\forall
V_1$, if $V_1$ is a symmetric neighborhood of $1_G$ then there exists $B\in {\cal B}$
and $W\subset G$ such that
\[y\in B^{\Delta W}\wedge \forall y_1, y_2\in B^{\Delta W}\cap
V_0\cdot x(y_1\in V_1\cdot y_2);\]
\noindent (v) we may decompose ${\cal B}$ into some directed union
\[{\cal B}=\bigcup_{\alpha\in \delta}{\cal B}_\alpha,\]
some $\delta\leq \omega_1^{\rm ck}$,
such that each element of ${\cal B}_0$ is either closed or open,
and for $\gamma>0$ we have that each element in ${\cal B}_\gamma$
is either the countable union or intersection of elements
in
\[\bigcup_{\alpha<\gamma} {\cal B}_\alpha.\]
\leftskip 0in
\def\tb{\tau_{*, {\cal B}}}
\begin{definition} We let $\tau_{*, {\cal B}}$ be the topology generated
by taking as a basis all sets of the form $B^{\Delta W}$ where $B\in {\cal B}$
and $V\subset G$ basic open.
\end{definition}
\begin{claim}
$(X, \tb)$ is a Polish $G$-space giving rise to the same Borel structure
as the original topology on $X$.
\end{claim}
Proof.
(v) implies by an appeal to transfinite induction on
$\delta$ that there is a Polish topology having ${\cal B}$
as its basis. This granted, the claim follows from
the Becker-Kechris theorem on changing topologies from
chapter 5 of \cite{beckerkechris}.
\hfill $\square$
\begin{claim}
For each $x\in X$ there is some $V\subset G$ non-empty such that
\[g\mapsto g\cdot x\]
is an open mapping from $V$ to $(V\cdot x, \tb)$.
\end{claim}
Proof.
For any $x$ we appeal to the listed properties of ${\cal B}$;
$V=V_0$ from (iv) succeeds by the definition of the topology $\tb$.
\hfill $\square$
But then by \ref{1} we have that $E_G^X$ is essentially countable.
\section{\sc Case(2): $\Xb$ is Non-Empty}
\def\Xl{X_{*{\rm low}}}
\def\tl{\tau^*_\infty}
Following \cite{hjorth}, we let
\[\Xl =\{x\in X: \forall^*g\in
G(\omega_1^{{\rm ck}(g\cdot x)}=\omega_1^{\rm ck})\}\]
and consider the topology
$\tl$ whose basis consists of all sets of the form
\[\Xl\cap A^{\Delta W},\]
$A\in\Sigma^1_1$ in $X$, $W$ basic open in $G$.
As shown there, this is a Polish topology, and in fact
$(\Xl, \tl)$ is a Polish $G$-space in the action inherited from
$X$.
As at \cite{hjorth}, we will use the following characterization of
when $\omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}$: $x$ is low exactly when for every
$\Sigma^1_1$ set $A$, either $x\in A$ or there is a $\Sigma^1_1$ set $B$ with
$x\in B$ and $A\cap B=0$.
\begin{definition} We let $\X*=\Xl\cap \Xb$, equipped with the
subspace topology induced by $\tl$.
\end{definition}
This $\X*$ is the intersection of two
invariant sets, and hence $G$-invariant.
It is relatively open in $\Xl$, and hence again a Polish
$G$-space. We want to show that it is in fact a stormy Polish
$G$-space.
So fix any $x\in \X*$. If one point in the orbit of $x$ fails to have the
natural map $V\rightarrow V\cdot x$ open for all $V\subset G$ then so
does every point in the orbit of $x$. Thus after possibly nudging $x$ by
a sufficiently generic group element $g\in G$ we may assume first of all
that
\[\omega_1^{{\rm ck}(x)}=\omega_1^{\rm ck}\]
and secondly that for all $A\in \Sigma^1_1$, if $x\in A$ then there is a basic
open neighborhood $W$ of $1_G$ such that
\[x\in A^{*W}.\]
The assumption that $x\in \Xb$ implies
that for any $A_0\in \Sigma^1_1$,$W_0, V_0\subset G$, with $1_G\in V_0$,
$V_0^{-1}=V_0$, $x\in A_0^{\Delta W_0}$ there exists $V_1$ with $1_G\in V_1$,
$V_1^{-1}=V_1$, and there exist $x'\in A_0^{\Delta W_0}, y'\in V_0\cdot x'$
such that for all $B\in \Delta^1_1$, $W_1\subset G$,
\[y'\in B^{\Delta W_1}\Rightarrow (\exists y_1', y_2'\in
B^{\Delta W_1}\cap V_0\cdot x'(y_1'\notin
V_1\cdot y_2')).\]
\begin{claim} For all $V\subset G$ with $1_G\in V$, $V^{-1}=V$,
there exist $V_1$, with $1_G\in V_1$, and $y\in V\cdot x$
such that for all $B\in \Delta^1_1$, $W_1\subset G$,
\[y\in B^{\Delta W_1}\Rightarrow (\exists y_1, y_2\in B^{\Delta W_1}
\cap V\cdot x(y_1\notin
V_1\cdot y_2)).\]
\end{claim}
Proof.
Otherwise the characteristic property of low reals implies
that there is a $\Sigma^1_1$ set $A$ containing $x$ such that for all $x'\in A$ , for all
$y'\in V\cdot x'$, for all $V_1$ containing $1_G$, there exists $B\in\Delta^1_1$,
$W_1\subset G$ such that
\[y'\in B^{\Delta W_1},\]
\[\forall y_1', y_2' \in V\cdot x'\cap B^{\Delta W_1}(y'_1\in V_1\cdot y'_2).\]
Choose $V_0$
containing $1_G$ with $V_0^2\subset V$, $V_0^{-1}=V_0$.
Choose $W_0\subset V_0\cap W$ such that
\[x\in A^{*W_0}\subset A^{\Delta W_0}.\]
Then for any $\hat{x}\in A^{\Delta W_0}$
and any $y'\in V_0\cdot \hat{x}$ and $V_1$ with $1_G\in V_1$, $V_1^{-1}=V_1$,
we may choose
\[x'\in W_0\cdot \hat{x}\cap A\subset V_0\cdot \hat{x}\cap A.\]
We have $y'\in V_0V_0^{-1}\cdot x'\subset V\cdot x'$, and so
assumption on $A$ yields some $B^{\Delta W_1}$ containing $y'$ such that
\[\forall y_1', y_2' \in V\cdot x'\cap B^{\Delta W_1}(y'_1\in V_1\cdot y'_2).\]
But now note that for all $y'_1, y'_2 \in B^{\Delta W_1}\cap V_0\cdot \hat{x}$
we have
\[y_1', y_2'\in V_0V_0^{-1}\cdot x'\subset V\cdot x'\]
\[\therefore y_1'\in V_1\cdot y_2'.\]
Thus $A_0$ and $W_1$ as given here contradict the assumption on $x$.
\hfill $\square$
The next claim states that we can obtain the same result even for $B\in\Sigma^1_1$.
Since our topology is based around the $\Sigma^1_1$ sets, not just the $\Delta^1_1$,
this is critical.
\begin{claim} For all $V\subset G$ with $1_G\in V$, $V^{-1}=V$,
there exist $V_1$, with $1_G\in V_1$, and $y\in V_1\cdot x$
such that for all $B\in \Sigma^1_1$, $W_1\subset G$,
\[y\in B^{\Delta W_1}\Rightarrow (\exists y_1, y_2\in B^{\Delta W_1}
\cap V\cdot x(y_1\notin
V_1\cdot y_2)).\]
\end{claim}
Proof.
Fix $V$. Choose $y$ and $V_1$ as in the last claim. Since the property
indicated for $y$ is $\Sigma^1_1(x)$, we may assume
\[\omega_1^{{\rm ck}(x,y)}=\omega_1^{{\rm ck}(x)}=\omega_1^{{\rm ck}}\]
by the Gandy low basis theorem.
With this extra assumption on $y$ we will prove that $y$ satisfies the conclusion
of the stronger claim presently before us. For this purpose consider some $B\in\Sigma^1_1$
and $W_1\subset G$.
Let
\[f_B: X\rightarrow {\rm LO}\]
be a rank, assigning to each $z\in X$ a linear ordering $f_B(z)\subset \N\times\N$
in a $\Delta^1_1$ manner, such that $f_B(z)$ is a well ordering if and only if
$z\notin B$.
For each
\[\alpha<\omega_1^{\rm ck}(=\omega_1^{{\rm ck}(x,y)})\]
we let $B_{(\alpha)}$ be the set of $z\in X$ such that $(\alpha, \in)$
allows an order preserving injection into $(\N, f_B(z))$. These sets are all
$\Delta^1_1$.
One possibility is that for some $\alpha<\omega_1^{\rm ck}$ we have
$y\notin (B_{(\alpha)})^{\Delta W_1}$. But then if we let $\hat{B}$
be the set of $z\in B$ such that $(\N, f_B(z))$ does not contain $\alpha$ in its wellfounded
part, then we have that $\hat{B}$ is a $\Delta^1_1$ set included in $B$ and
$y\in \hat{B}^{\Delta W_1}$; and then we are immediately done by the
assumptions on $y$.
The other possibility is that for each $\alpha< \omega_1^{\rm ck}$
we have $y\in (B_{(\alpha)})^{\Delta W_1}$, and
hence appealing to assumptions on
$y$ we may find $y_1^\alpha, y_2^\alpha\in (B_{(\alpha)})^{\Delta W_1}$ with
$y_1^\alpha\notin V_1\cdot y_2^\alpha$.
But then appealing to boundedness we can find an illfounded
linear ordering $(\N, <^*)$ such that there exists $y_1^\infty, y_2^\infty$
with
\[\exists^*g\in W_1((\N, <^*){\rm \: embeds \: into} f_B(g\cdot y_1^\infty)),\]
\[\exists^*g\in W_1((\N, <^*){\rm \: embeds \: into} f_B(g\cdot y_2^\infty)),\]
\[y_1^\infty\notin V_2\cdot y_2^\infty.\]
But if $(\N, <^*)$ embeds into $f_B(g\cdot y_i^\infty)$ then $f_B(g\cdot y_i^\infty)$
is illfounded and so $g\cdot y_i^\infty\in B$.
Thus we are done.
\hfill $\Box$
But since this last claim holds for any $x\in \X*$, we have that the action
of $G$ on $\X*$ is indeed stormy.
\section{\sc Remarks on Effectivity}
Little effort was made in case(1) to indicate how we can produce a lightfaced
reduction to a lightfaced $\Delta^1_1$ equivalence relation. On the surface,
\ref{1} is phrased so that it only looks like a bold faced result and
even the statement of Kechris' criterion at 5.2 of
\cite{hjorthbanach} is only as a boldfaced result.
First of all, inspecting the proof of Kechris' criterion one actually
obtains:
\begin{proposition} (Kechris)
\label{kechris}
Let $E$ be a $\Delta^1_1$ equivalence relation on a recursive Polish space
${\cal X}$ and
\[\theta :{\cal X}\rightarrow \{0,1\}^\N\]
a $\Delta^1_1$ function such that:
\leftskip 0.4in
\no (i) $\theta $ has countable image on each equivalence class;
\no (ii) $\theta $ maps distinct equivalence classes to disjoint sets.
\leftskip 0in
\noindent
Then there is a $\Delta^1_1$ equivalence relation $F$ on $\{0,1\}^\N$
all of whose equivalence classes are countable such that $\theta $ witnesses
$E\leq_B F$.
\end{proposition}
We are still faced with the brutishness of ${\cal B}$ and boldfacedness of \ref{1}.
These problems are both dealt with in the same way.
The main claim is this:
\begin{claim}
In the proof from case(1), we may assume that there is a $D\subset X\times \N$
in $\Delta^1_1$ such that each $B\in{\cal B}$ has the form
\[B=D_k=\{x: (x, k)\in D\}\]
for some suitable $k$.
\end{claim}
This claim is proved by the boundedness theorem for $\Sigma^1_1$ subsets of
$\omega_1^{\rm ck}$; in some sense, we can ``bound" all of the needed $\Delta^1_1$
sets in some manageable object.
To see this recall that every $\Delta^1_1$ set has the form
\[\{y: L_\alpha[y]\models \varphi(y)\}\]
for some $\alpha<\omega_1^{\rm ck}$ and formula $\varphi(\cdot)$ of set theory.
If $V_x\subset G$ satisfies the statement of \ref{update}, then this is a
$\Pi^1_1$ property on the basic open set $V$.
If $x\in X, y\in V_x\cdot x$, then the statement that $W_0\subset G$ and
\[B=\{y: L_\alpha[y]\models \varphi(y)\}\]
satisfy the assumption of
\ref{update} is $\Pi^1_1(x, y)$. Thus we have in effect a
$\Pi^1_1$ function from $X$ to the basic open sets in $G$, and then
composing a $\Pi^1_1$ function from $X\times X$ to
\[\omega_1^{\rm ck}\times{\cal L}(\in).\]
$\Pi^1_1$ functions into the natural numbers are always $\Delta^1_1$.
Thus by boundedness we can assume that there is a single $\delta<\omega_1^{\rm ck}$
such that we can always choose $\alpha\leq\delta$.
In this way, granting certain routine technical details about effectivizing the
enumeration, we can prove the claim.
But then if $(\hat{V}_\ell)_{\ell\in\N}$ is a
basis for $G$, we have a $\Pi^1_1$, and hence $\Delta^1_1$,
function
\[X\rightarrow\N\]
\[x\mapsto n_x\]
assigning to each $x$ some $n_x$ such that $\hat{V}_{n_x}$ fulfills
\ref{update}. Then we can let $(m_x, k_x)$ be chosen in a
$\Delta^1_1$ way so that
\[U_x=(D_{k_x})^{\Delta \hat{V}_{m_x}}\]
along with $V_x=\hat{V}_{n_x}$ completes the construction of \ref{1}.
We can then finish by letting $\theta (x)$ be the characteristic function
of the following set of natural numbers:
\[\{2^k3^n: V_x\cdot x\cap U_x\cap (D_k)^{\Delta \hat{V}_n}\neq 0\};\]
in this manner we have assigned to $x$ in a $\Delta^1_1$ way an element
$\theta (x)$ such that
\[\theta (x_1)=\theta (x_2)\]
if and only if
\[\overline{U_{x_1}\cap V_{x_1}\cdot x} =\overline{U_{x_2}\cap V_{x_2}\cdot x_2}.\]
By the proof of \ref{1}, this function satisfies Kechris' criterion.
\begin{thebibliography}{99}
\bibitem{beckerkechris} {\sc H. \ Becker} and
{\sc A.\ S. \ Kechris}, {\em The descriptive set theory
of Polish group actions},
London Mathematical Society Lecture
Note Series, 232, Cambridge University Press, Cambridge, 1996.
\bibitem{changkiesler} {\sc C. \ C. \ Chang} and
{\sc H. \ J. \ Keisler},
{\em Model theory,}
second edition, North-Holland,
Amsterdam, 1977.
\bibitem{gao} {\sc S. \ Gao, }
Some dichotomy theorems for isomorphism relations of countable models,
{\em Journal of Symbolic Logic,}
vol. 66 (2001), pp. 902--922.
\bibitem{grmory} {\sc A. \ Gregorczyk,}
{\sc A. \ Mostowski,}
{\sc C. \ Ryll-Nardzewski,}
{ Definability of sets of models of axiomatic theories,}
{\em Bulletin of the Polish Academy of Sciences,} (series Mathematics,
Astronomy, Physics), vol. 9 (1961), pp. 163--7.
\bibitem{hamash} {\sc L. \ A. \ Harrington,}
{\sc D. \ Marker}, and {\sc S. \ Shelah,}
Borel orderings,
{\em Transactions of the American Mathematical Society,}
{\bf vol. 310} (1988), pp. 293--302.
\bibitem{hjorthclassification}
{\sc G. \ Hjorth},
{\em Classification and orbit equivalence relations,}
American Mathematical Society, Rhode Island, 2000.
\bibitem{hjorthbanach} {\sc G.\ Hjorth},
{ Actions of the classical Banach spaces,}
{\em The Journal of Symbolic Logic,}
{\bf vol. 65} (2000), pp. 392--420.
\bibitem{hjorth} {\sc G. \ Hjorth},
{A dichotomy theorem for turbulence,}
{\em The Journal of Symbolic Logic,}
{\bf vol. 67} (2002), pp. 1520--1540.
\bibitem{hjorthtfa} {\sc G. \ Hjorth},
{The isomorphism relation for countable
torsion free abelian groups, }
{\em Fundamenta Mathematicae},
{\bf vol. 175} (2002), pp. 241--257.
\bibitem{hjorthkechris} {\sc G.\ Hjorth} and {\sc A.\ S.\ Kechris},
Borel equivalence relations and classifications
of countable models,
{\em The Annals of Pure and Applied Logic},
{\bf vol. 82} (1996), pp. 221--272.
\bibitem{hjkelo} {\sc G.\ Hjorth},
{\sc A.\ S.\ Kechris}, and {\sc A. \ Louveau},
Borel equivalence relations induced by actions of the symmetric group,
{\em The Annals of Pure and Applied Logic,}
{\bf vol. 92} (1998), pp. 63--112
\bibitem{kechris} {\sc A. \ S. \ Kechris},
{\em Classical Descriptive Set Theory,}
Springer-Verlag, New York, 1995.
\bibitem{kechris2} {\sc A. \ S. \ Kechris},
Countable sections for locally compact group
actions,
{\em Ergodic Theory and Dynamical Systems},
{\bf vol. 12} (1992),
pp. 283--295.
\bibitem{lopez}{\sc \ E.\ G. \ Lopez-Escobar},
An interpolation theorem for denumerably long formulas,
{\it Fundamenta Mathematicae,} vol. {\bf 57} (1965),
pp. 253--272.
\bibitem{thomas} {\sc S. Thomas},
The classification problem for torsion-free abelian
groups of finite rank,
{\em Journal of the American Mathematical Society,}
{\bf vol. 16} (2003),
pp. 233-258.
\end{thebibliography}
\leftskip 0.5in
greg@math.ucla.edu
\bigskip
MSB 6363
UCLA
CA 90095-1555
\leftskip 0in
\end{document}