% LaTeX Article Template - using defaults
\documentclass{article}[12pt]
\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.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}{7in}
% 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}
\markright{G. Hjorth}
% Set the beginning of a LaTeX document
\begin{document}
\large
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\bigskip\end{trivlist}}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\bigskip}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\bigskip}
\newenvironment{remark}[1][Remark]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\bigskip}
\newenvironment{notation}[1][Notation]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\bigskip}
\newenvironment{question}[1][Question]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\bigskip}
\newenvironment{examples}[1][Examples]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}\bigskip}
\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\Q{{\Bbb Q}}
\def\Z{{\Bbb Z}}
\def\N{{\Bbb N}}
\def\n{{\cal N}}
\def\m{{\cal M}}
\def\T{{\Bbb T}}
\def\R{{\Bbb R}}
\def\C{{\cal C}}
\def\G{{\cal G}}
\def\l{{\cal L}}
\def\p{{\mathcal P}}
\def\a{{\cal A}}
\def\b{{\cal B}}
\def\B{{\cal B}}
\def\e{\epsilon}
\def\d{\delta}
\title{On invariants for measure preserving transformations}
% Enter your title between curly braces
\author{G. Hjorth\footnote{The author gratefully acknowledges
support from NSF grants DMS 99-70403 and DMS 96-22977.}}
% Enter your name between curly braces
%\date{\today} % Enter your date or \today between curly braces
\maketitle
\abstract{The classification problem for measure preserving
transformations is strictly more complicated than that of
graph isomorphism.\footnote{AMS Subject Classification: 04A15. Key words
and phrases: Classification; measure preserving transformation; Polish
group action.}
\section{Preamble}
\label{0}
We consider the group $M_{\infty}$ of all invertible
measure preserving
transformations either on the
unit interval or any other reasonable measure space.
It seems natural to say that
two of these transformations, $\sigma_1$, $\sigma_2$, are equivalent or {\it isomorphic}
if there is a third, $\pi$, so that
\[\pi\circ \sigma_1\circ\pi^{-1}=\sigma_2\:{\rm {a.e.}}\]
To what extent can this equivalence relation be considered {\it classifiable}?
In specific cases -- for instance $\sigma_1$, $\sigma_2$ both {\it Bernoulli} or
{\it discrete spectrum} -- there are well accepted systems of complete invariants.
However in the completely general context of arbitrary measure preserving transformations
there is no known satisfactory system of complete invariants nor even a clear statement
of what this would entail.
For instance, Halmos in \cite{ha1} despairs of precisely formulating the problem but
at page 1029 suggest that its solution should fulfill the ``the vague task of finding
a complete set of invariants...'' At page 75 of \cite{ha2}
he proposes that the central problem
is to ``find usable necessary and sufficient conditions for the conjugacy of two measure
preserving transformations.'' Some time later Weiss at page 670 of \cite{we} raises
the problem of finding ``a set of invariants large enough so that if all invariants agree
for two m.p.t. one can conclude that the m.p.t. are isomorphic.''
This article considers attempts to make this precise and
ask abstractly whether the problem of classifiability
could {\it in principle} have a positive solution.
We present a clearly identifiable lower bound on the
{\it classification difficulty} of the isomorphism relation for
measure preserving transformations.
One precise formulation of the problem would be to understand a {\it classifiable
equivalence relation} on a Polish space to be one for which we may find a Borel assignment of
reals or points in some other {\it standard Borel space} as complete invariants. This is
the notion of classifiable suggested by the Glimm-Effros dichotomy of \cite{hakelo}.
Indeed Feldman in \cite{feldman} takes exactly that position. Appealing to
\cite{ornstein} he observes that the isomorphism
relation for {\it Bernoulli} shifts allows real numbers to be assigned in a
Borel manner as a complete invariant and uses
\cite{ornsteinshields} to remark that such an assignment is already
impossible for the class of measure preserving having the {\it property of K}.
A more generous notion of classification, closer to the kinds we consider
below, is already implicit in
sources \cite{ha1}, \cite{ha2}, \cite{we}. In each
case the results of \cite{hane} are accepted as providing a complete classification
for the {\it discrete spectrum} measure preserving transformations. Here the
invariants are not real numbers or single points in a standard Borel space,
but rather countable sets of complex numbers. The significance of this is
not in the
use of complex numbers as against reals -- this is immaterial since all uncountable
Polish spaces are Borel isomorphic. The significant feature of the invariants from
\cite{hane} is that they have the form of a {\it countable unordered set} of points
in a standard Borel space.\footnote{Superficially it might be thought that the ability to assign
countable sets of points in a standard
Borel space as a complete invariant is tantamount to
classifiability in the sense of \cite{feldman}. In fact this is untrue -- there is
in general no {\it canonical} way to encode or parameterize a countable set
of complex numbers by a real, or by a point in any other separable
completely metrizable
(i.e. {\it Polish}) space. Indeed this can already been seen in the
present context, as it is known that there is no Borel function that assigns
to a discrete spectrum measure preserving transformation a complex number as
a complete invariant (compare the start of $\S$5 below).
More starkly, and just to allay suspicions that this
may be a consequence of restricting to the Borel
category, the techniques of \cite{solovay} are
sufficient to demonstrate the consistency of set theory without the axiom of
choice along with the non-existence of {\it any} function assigning complex
numbers as complete invariants for discrete spectrum transformations.
It is intrinsic to the methods of \cite{hane} that we obtain countable sets
of points as complete invariants, and no amount of modification will squeeze it
into the form requested by \cite{feldman}.}
Thus we may in general ask for an
equivalence relation $E$ on a standard Borel space $X$:
\begin{question} {\bf Q1:} Does there exists a countable sequence
$(f_i)_{i\in{\Bbb N}}$ of Borel functions, each $f_i:X\rightarrow {\Bbb C}$
such that for all $x_1, x_2\in X$
\[x_1 E x_2 \Leftrightarrow
\{f_i(x_1): i\in{\Bbb N}\}=\{f_i(x_2): i\in{\Bbb N}\}?\footnote{Matt Foreman
has shown that the
procedure of \cite{hane} indeed obtains such a classification, that is to say,
in the Borel category, for discrete spectrum mpt's.} \]
\end{question}
As suggested by Matt Foreman, we might hope that
``usable and sufficient conditions'' should at least make
the relation of isomorphy Borel in $M_{\infty}\times M_{\infty}$.
\begin{question} {\bf Q2:} Let Graph$(E)\subseteq X\times X$
be the set of $(x_1, x_2)$ for which
$x_1 Ex_2$.
Is Graph$(E)$ Borel in the product Borel structure on $X\times X$?
(In future I will refer to this
conclusion simply as the statement that $E$ be Borel.)
\end{question}
These are in general distinct notions. Given an equivalence relation $E$ on a
Polish space $X$, classifiability in the sense of a single Borel function assigning points
as complete invariants implies a positive answer to Q1. A positive
answer to Q1 implies one for Q2. Neither of these implications reverse.
Below we consider these questions for the specific case of $X=M_{\infty}$ and
$E$ the equivalence relation of conjugacy, given by setting $\sigma_1 E\sigma_2$
if there exists $\pi\in M_{\infty}$ such that
\[\sigma_1(x) =\pi\circ \sigma_2\circ \pi^{-1}(x) \: {\rm a.e.}\]
We place on $M_\infty$ the customary Borel structure,
described by \cite{feldman} and recalled in section \ref{1} below.
\begin{theorem} \label{0.3}
The conjugacy equivalence relation on $M_{\infty}$ is
non-Borel.
\end{theorem}
In fact the situation is much worse than this alone would suggest. It turns out that
the classification problem for measure preserving transformations encompasses the
classification problem for arbitrary countable discrete structures -- countable groups,
countable linear orderings, graphs, and so on. For ${\cal L}$ a countable language,
Mod$({\cal L})$, the
space of all ${\cal L}$-structures
whose underlying set is ${\Bbb N}$, is naturally
a standard Borel space; the details of this definition are recalled
in section \ref{1} below, and discussed at length in many places,
such as
\cite{kechrisclassical},
\cite{hjorthkechris}, \cite{hjorth}.
A specific example of such a collection is the space of (directed) graphs
on $\N$, which by appeal to the corresponding characteristic function of
the adjacency relation can be identified with $\{0,1\}^{\N\times\N}$ and given
a natural topology.
\begin{theorem} \label{0.4} If ${\cal L}$ is a countable
language then there is a Borel function $\theta\! :{\rm Mod}({\cal L})
\rightarrow M_{\infty}$ such that for all $M, N\in$ Mod$({\cal L})$
\[M\cong N\Leftrightarrow
\exists \pi\in M_{\infty}(\pi\circ \theta(M)\circ\pi^{-1}=
\theta(N)\:{\rm {a.e.}}).\]
\end{theorem}
It is not known whether \ref{0.4} or \ref{0.3}
can be obtained for the {\it ergodic} measure
preserving transformations -- that is to say, whether we may have $\theta$ as
in \ref{0.4} but with the further requirement that it always assume a value
$\theta(M)\in M_{\infty}$ such that every Borel $\theta(M)$-invariant set
is either null or co-null.
These further and still
open questions are of interest given the ergodic decomposition theorem,
stating that every element of $M_{\infty}$ may be in some sense written as the
integral of its ergodic components (see for instance
\cite{ha2}, $\S$2.3 \cite{zimmer},
\cite{petersen}).
In this context one could compare the conjugacy
equivalence relation on the unitary representations of a discrete group: in the
case of irreducible representations this is known to be not only Borel but
actually $F_\sigma$ in an appropriate topology.
(See \cite{effros}.)
For the narrow case of ergodic transformations we only
know the following:
\begin{theorem} \label{0.6} There is a Polish group $G$ and a {``turbulent"}
Polish $G$-space $X$ and a Borel function $\theta:X\rightarrow M_{\infty}$ such that
\leftskip 0.5in
\noindent (i) $\theta(x)$ is ergodic for all $x\in X$;
\noindent (ii) $x_0E^X_G x_1$ if and only if
\[\exists \pi \in M_\infty (\pi\circ \theta(x_0)\pi^{-1} = \theta(x_1)\]
for all
$x_0, x_1\in X$.
\leftskip 0in
\end{theorem}
In other words, we may embed a {\it turbulent} orbit equivalence relation into
the isomorphism relation on ergodic measure preserving transformations.
In light of the results from \cite{hjorth}, this provides a succinct
anti-classifiability result.
In particular, the reduction in \ref{0.4} does not reverse:
The classification problem for measure preserving transformations is
{\it strictly}
more complicated than for discrete countable structures.
\begin{theorem} \label{0.7}
For ${\cal L}$ a countable language, there is no
Borel $\theta_1\! :M_{\infty}\rightarrow$ {\rm Mod}$({\cal L})$ such that for all
$\sigma_1, \sigma_2\in M_{\infty}$
\[\exists \pi\in M_{\infty}(\pi\circ \sigma_1\circ\pi^{-1}=
\sigma_2\:{\rm {a.e.}})\Leftrightarrow \theta_1(\sigma_1)\cong\theta_1(\sigma_2).\]
\end{theorem}
Indeed there is no such $\theta_1$ even with domain just the ergodic
transformations. Actually we obtain in \ref{0.6}(i) that each $\theta(x)$ is in
the class of {\it rank 2
generalized discrete spectrum} (see \cite{furstenberg}).
This is an important detail: Since the discrete spectrum measure preserving
transformations {\it do} admit classification by countable sets of complex numbers,
and hence by countable models, we might have hoped for instance that the
$\alpha$th level of the generalized discrete spectrum transformations
admit complete invariants in something like
the $\alpha$th iteration of the operation of taking all countable subsets
applied to ${\Bbb C}$.
It should not be thought that the results above are {\it fragile} to the choice
of the Borel category. We can define more generous classes of reducibility and
show that even with broader but still reasonable classes
of functions -- of the kind
that are encountered in Ulm invariants for
abelian $p$-groups and the Scott analysis
for countable structures -- there is no reduction of conjugacy
on $M_{\infty}$ to isomorphism
on countable structures, or equality on countable sets of reals, or indeed
to any Borel equivalence relation.
Finally I suppose it might be felt that the real problem is not that we are
demanding Borel functions but more generally that we are requiring
{\it any sort of definability} what so ever. In this way we might dream
of some manner of classification, only without the invariants being
produced in a ``effective'' manner.
But not even that much can be hoped for. If $\approx$ is the conjugacy
equivalence relation on $M_{\infty}$, $\cong$ isomorphism on countable
structures, then by the techniques of \cite{solovay} it is consistent
with ZF and enough of the axiom of choice to develop most classical
mathematics that there be {\it no} injection:
\[M_{\infty}/\!\!\approx\: \hookrightarrow {\rm {Mod}}({\cal L})/\!\cong.\]
In particular if ${\cal P}_{\aleph_0}(A)$ denotes the collection of all
countable subsets of a set ${A}$, then there will be no injection
\[M_{\infty}/\!\!\approx\:\hookrightarrow {\cal P}_{\aleph_0}({\Bbb C}),\]
nor
\[M_{\infty}/\!\!\approx\: \hookrightarrow {\cal P}_{\aleph_0}({\cal P}_{\aleph_0}({\Bbb C})),\]
and so on.
Similarly it is consistent with ZF and a large fragment (DC) of choice
that for any Borel equivalence relation on a Polish space $X$ there is
no injection
\[M_{\infty}/\!\!\approx\hookrightarrow X/E.\]
In $\S$\ref{1} we give some definitions and present
the outline of the proof for \ref{0.4}, which
is in turn completed in sections \ref{2} and \ref{3}.
Section \ref{4} embeds a turbulent orbit equivalence relation into the
generalized
discrete spectrum transformations. $\S$\ref{5} gives a proof of a known result to
the effect that
the natural equivalence relation on cocycles from the measure preserving
action of a countable group into a compact group is Borel; this
equivalence relation is closely related to the one needed in
$\S$\ref{4}. It is also noted that the collection of measurable
transformations conjugating a transformation $T$ to itself is compact
if and only if $T$ has discrete spectrum.
\bigskip
In terms of background material needed for reading this paper,
formally it does not assume much more than a general
knowledge of elementary analysis, of the kind which would be
found in an text such as \cite{zimmer}. However as a practical matter
it would be more than helpful to have some acquaintance with ergodic theory.
A knowledge of classical descriptive set theory in the sense of
\cite{kechrisclassical} may also make the paper easier to read.
Many of the results appeal to the modern theory of Borel equivalence relations;
for this \cite{frst} and \cite{beckerkechris} are good references.
The theory of turbulence is developed in \cite{hjorth}; the notation here largely
follows the notation there.
We indulge in all the usual sins. A measurable square summable function is
identified with its equivalence class in $L^2$. We say ``everywhere" when
we mean ``on all but a null set".
\bigskip
\noindent{\bf Acknowledgment:} I am grateful to Matthew Foreman for several
illuminating
discussions in the neighborhood of these topics and for pointing out the
relevance of \cite{hane}.
I am also very much indebted to the referee for an exceptionally thorough
and penetrating report, and in particular for finding a serious mathematical
error in the first draft. This first draft claimed that one can obtain
\ref{0.4} by proving that isomorphism on countable torsion-free
abelian groups is Borel complete in the sense of \cite{frst}; that proof
of the Borel completeness of torsion-free abelian groups was erroneous.
\newpage
\section{Outline of the proof of \ref{0.4}}
\label{1}
The concept of ``Borel reducibility" is central to the
arguments below.
\begin{definition} Let $E$ and $F$ be equivalence relations on
Polish spaces $X$ and $Y$.
We say that $E$ is {\it Borel reducible} to $F$, written $E\leq_B F{\rm ,}$
if there is a Borel function
\[\theta: X\rightarrow Y\]
such that for all $x_1, x_2\in X$ we have
\[x_1 E x_2\]
if and only if
\[\theta(x_1) F \theta(x_2).\]
Naturally we write $E<_B F$ if $E\leq_B F$ holds but
$F\leq_B E$ fails.
\end{definition}
This relation $\leq_B$ is clearly transitive and reflexive.
\begin{examples} More detail, along with proofs of the
various folklore
assertions, can be found in \cite{hjorth}.
(i) For $X$ a Polish space, id$(X)$ is the identity equivalence
relation on $X$. If $E\leq_B$ id$(X)$ for any Polish space $X$
then we say that $E$ is {\it smooth}.
(ii) $E_v$ is the Vitali equivalence relation on $\R$, given by the
cosets of $\Q$. Here it is known that $E_v$ is not smooth.
(iii) $E_0$ the equivalence relation of eventual agreement
on infinite binary sequences. It is known that
$E_0\leq_B E_v\leq_B E_0$.
(iv) Let $2^{\N\times\N}$ be the space of functions from
$\N\times\N$ to $\{0, 1\}$, with the topology of point wise
convergence.\footnote{Here and elsewhere we identify
2 with $\{0,1\}$, and thus $2^{\N\times \N}$ is the space of all
functions from $\N\times\N$ to $\{0,1\}$.}
Following \cite{frst} we define $F_2$ by
\[x_1 F_2 x_2\]
if and only if
\[\forall n\in \N \: \exists m_1, m_2\in \N (\forall k\in\N
(x_1 (n, k)=x_2(m_2, k), x_1(m_1, k)=x_2(n, k))).\]
Then ${\rm id}(\R)<_B E_0 <_B F_2.$
\end{examples}
Two important classes of Polish spaces are those consisting of all
measure preserving transformations of a Lebesgue space and those consisting
of all ${\cal L}$-structures on $\N$ for some countable language ${\cal L}$.
\begin{definition} Let $M_{\infty}$ be the group of Borel measure
preserving bijections from $[0,1]$ to $[0,1]$ with identification of
maps agreeing on a measure one set. For $(O_n)_{n\in{\Bbb N}}$ a basis
of $[0,1]$ we obtain a separable metric $d_{\lambda}$ on
$M_{\infty}$ by setting
\[d_{\lambda}(\pi_1, \pi_2)=\sum 2^{-n}
[\lambda(\pi_1(O_n)\Delta\pi_2(O_n))+\lambda(\pi_1^{-1}(O_n)\Delta\pi_2^{-1}(O_n))],\]
where $\lambda$ is Lebesgue measure and $\Delta$ is used to denote symmetric difference:
$X\Delta Y=(X\setminus Y)\cup (Y\setminus X)$.
Let $\approx^*$ denote the conjugacy equivalence relation:
\[\pi_1\approx^*\pi_2\Leftrightarrow \exists \sigma\in M_{\infty}
(\sigma\circ \pi_1\circ \sigma^{-1}=\pi_2).\]
\end{definition}
\begin{definition} For ${\cal L}$ a countable language,
let Mod$({\cal L})$ be the collection of all different ways
we may place an ${\cal L}$-structure on the natural numbers
$\N$. We then place a topology on this space by taking as subbasic open
sets those of the form
\[\{\m\in {\rm Mod}(\l)\mid (n_1,..., n_k)\in R^\m\},\]
\[\{\m\in {\rm Mod}(\l)\mid (n_1,..., n_k)\not\in R^\m\},\]
\[\{\m\in {\rm Mod}(\l)\mid f^\m(n_1,..., n_k)=m\},\]
\[\{\m\in {\rm Mod}(\l)\mid f^\m(n_1,..., n_k)\not = m\},\]
where $n_1,n_2,..., n_k, m$ range over finite sequences from
$\N$, $R$ ranges over relation symbols in $\l$,
and $f$ ranges over function symbols in $\l$.
We let $\cong\! |_{{\rm Mod}(\l)}$ denote the isomorphism relation
on these ${\cal L}$-structures. Thus $\m_1\cong\m_2$ if and only if
there is a bijection $\sigma: \N\rightarrow\N$
with
\[(n_1,..., n_k)\in R^{\m_1}\Leftrightarrow (\sigma(n_1)
,..., \sigma(n_k))\in R^{\m_2}\]
and
\[f^{\m_1}(n_1,..., n_k)=m\Leftrightarrow
f^{\m_2}(\sigma(n_1),..., \sigma(n_k))=\sigma(m)\]
all relation symbols $R$, function symbols $f$, and
$n_1,..., n_k, m\in\N$.
\end{definition}
\begin{lemma} \label{5.1.2}
$M_{\infty}$ is a Polish group; $d_\lambda$ is complete.
\end{lemma}
\begin{proof} This was shown in \cite{feldman};
a proof can also be found in chapter 2 of \cite{hjorth}.
\end{proof}
\begin{lemma}
\label{5.1.2a}
{\rm Mod}$(\l)$ is a Polish space whenever $\l$ is a countable language.
\end{lemma}
\begin{proof} This lemma should be obvious, since the space can be naturally
identified with a suitable countable product of the Polish spaces $\N^{\{0, 1\}}$
and $\N^\N$.
\end{proof}
We wish to start working towards a proof that for any countable
language $\l$ we have
\[\cong\! |_{{\rm Mod}(\l)}\leq_B \approx^*.\]
An equivalence relation $E$ on $X$
is said to be {\it Borel} if it is Borel as a subset of
$X\times X$. It is then easily seen that the
Borel equivalence relations are closed downwards under
$\leq_B$. And thus since it is well known (see \cite{frst}
or 6.16 \cite{hjorth}) that for many $\l$ one
has $\cong\! |_{{\rm Mod}(\l)}$ non-Borel, a proof of
\[\approx^*\leq_B \cong\! |_{{\rm Mod}(\l)}\]
will in particular
give that $\approx^*$ is non-Borel.
It is rather cumbersome to be continually working with the full
range of possible $\cong\! |_{{\rm Mod}(\l)}$ as $\l$ ranges over
countable languages. Instead it will be convenient to work with a
canonical example, which is already known to have maximal complexity
in the $\leq_B$-ordering.
For us a {\it graph} will be a directed graph where loops are possible
but parallel edges are not. Thus we may naturally identify a graph
on the underlying set $\N$ with a binary relation on $\N$, and this
in turn may by consideration of the characteristic function be identified
with $2^{\N\times \N}$.
\begin{definition} Let Mod(Gph) be the Polish space $2^{\N\times\N}$
equipped with the product topology.
We let the infinite symmetric group, $S_\infty$, consisting of all
permutations of the natural numbers, act on $2^{\N\times\N}$ in the following
manner: Given $\sigma\in S_\infty$ and $x\in 2^{\N\times\N}$, we
define $\sigma\cdot x$ by
\[(\sigma\cdot x)(n, m)=x(\sigma^{-1}(n), \sigma^{-1}(m)).\]
We then let
\[E^{\rm Mod(Gph)}_{S_\infty}\]
denote the resulting orbit equivalence relation:
\[x_1 E^{\rm Mod(Gph)}_{S_\infty} x_2 \]
if and only if
\[\exists \sigma\in S_\infty(\sigma\cdot x_1=x_2).\]
\end{definition}
Thus $E^{\rm Mod(Gph)}_{S_\infty}$ is the isomorphism relation for
the space of all binary relations on $\N$.
Of course as a space Mod(Gph) is nothing other than $2^{\N\times\N}$;
it will be convenient to have this separate notation, to remind ourselves
with Mod(Gph) that we are thinking of $2^{\N\times\N}$ as a Polish
$S_\infty$-space in a specific way.
\begin{lemma} \label{5.1.2b} If $\l$ is a countable language, then
\[\cong\! |_{{\rm Mod}(\l)}\leq_B E^{\rm Mod(Gph)}_{S_\infty}.\]
\end{lemma}
\begin{proof}
A proof of this well known folklore fact can be found in many places,
including \cite{frst}.
\end{proof}
Thus the task of showing $\approx^*$ non-Borel has been reduced to showing
that for any countable language $\l$ we have
\[\cong\! |_{{\rm Mod}(\l)}\leq_B \approx^*,\]
which has in turn been reduced to showing
\[ E^{\rm Mod(Gph)}_{S_\infty}\leq_B \approx^*.\]
In order to do this we will introduce one further equivalence relation,
$E^{Y_2}_{G_\infty}$ defined shortly, and show in section \ref{2} first that
\[E^{Y_2}_{G_\infty}\leq_B \approx^*,\]
and then in section \ref{3} that
\[E^{\rm Mod(Gph)}_{S_\infty} \leq_B E^{Y_2}_{G_\infty}.\]
\begin{definition} Let $M(S_{\infty})=
\{g\in(S_{\infty})^{[0,1]}: g$ Borel$\}$
be the group of
measurable functions from $[0,1]$ to $S_{\infty}$,
where
$S_{\infty}$ is the infinite symmetric group on ${\Bbb N}$;
we multiply pointwise,
\[(g_1g_2)(x)=
g_1(x)g_2(x){\rm ,}\] and identify functions that
agree $\lambda$ a.e.
\end{definition}
Observe then that if $g^{-1}$ is the
group theoretic inverse of $g\in M(S_{\infty})$ then
$g^{-1}(x)=(g(x))^{-1}$ for ($\lambda$ a.e) $x\in[0,1]$.
\begin{definition}
Define $\psi: M_{\infty}\rightarrow$ Aut$(M(S_{\infty}))$
by the requirement that for $\pi\in M_{\infty}$,
$x\in[0,1]$, $g\in M(S_{\infty})$
\[((\psi(\pi))(g))(x)=g(\pi^{-1}(x)).\]
\end{definition}
So $\psi(\pi)$ is the (group theoretic) automorphism of $M(S_{\infty})$
obtained by shift.
In fact these groups all have natural topologies
and $\psi$ is a homeomorphism from $M_\infty$ into the group of
continuous automorphisms of $M(S_{\infty})$.
\begin{definition}
Form the semi-direct product
$ M(S_{\infty}) \rtimes_\psi M_{\infty}$
in the usual way, so that
for $g_0, g_1\in M(S_{\infty})$,
$\pi_0, \pi_1\in M_{\infty}$
\[(g_0,\pi_0)(g_1, \pi_1)=
(g_0(\psi(\pi_0))(g_1), \pi_0\pi_1).\]
For short write $G_{\infty}=_{\rm df} M(S_{\infty}) \rtimes_\psi M_{\infty}$.
\end{definition}
\begin{definition} For $y\in 2^{\N\times \N}$ and $n\in\N$ we define
$y(n, \cdot)\in 2^\N$ in the obvious way, by
\[(y(n, \cdot))(m)=y(n, m).\]
Let
\[B_2=\{x\in 2^{{\Bbb N}\times{\Bbb N}}:n\not\! = m \Rightarrow
x(n, \cdot)\not\! = x(m, \cdot)\}{\rm ;}\]
$B_2$ is a $G_\delta$ subset of the Polish
space $2^{\N\times\N}$ and hence Polish (see \cite{kechrisclassical} 3C).
Let
\[Y_2=\{y\in (B_2)^{[0,1]}\mid
y \:{\rm Borel }\}\]
be the space of measurable functions from $[0,1]$ to
$B_2$ where we identify functions agreeing almost
everywhere. We give this space the topology of convergence almost every where,
so that
\[f_n\rightarrow f\]
if for almost every $x\in[0,1]$ we have $f_n(x)\rightarrow f(x)$.
\end{definition}
\begin{lemma} \label{5.1.7} $Y_2$ is a Polish space.
\end{lemma}
\begin{proof} Let $d'$ be a complete compatible metric on $B_2$.
We obtain a complete metric $d_2$ by setting
\[ d_2(y_0, y_1)=\int d'(y_0(x), y_1(x))\lambda(x)\]
for $y_0, y_1\in Y_2$.
\end{proof}
\begin{definition} Let $G_{\infty}$ act on $Y_2$ as follows: Given
$y\in Y_2$,
\[y:[0,1]\rightarrow 2^{{\Bbb N}\times{\Bbb N}}{\rm ,}\]
and
\[(g, \pi)\in G_{\infty}{\rm ,} \]
\[g:[0,1]\rightarrow S_{\infty}{\rm ,}\]
\[\pi
\in M_{\infty}{\rm ,}\]
we
define $(g, \pi)\cdot y:[0,1]\rightarrow 2^{{\Bbb N}\times{\Bbb N}}$
by
\[(((g,\pi)(y))(x))(m, n)=(y(\pi^{-1}(x)))(g^{-1}(x)(m), n).\]
(Here $g^{-1}$ is intended to be the group theoretic inverse of
$g\in M(S_{\infty})$; thus $g^{-1}(x)=(g(x))^{-1}$.)
Observing
\[([(g_0,\pi_0)((g_1, \pi_1)(y))](x))(m,n)=[((g_1,\pi_1)(y))(\pi_0^{-1}(x))]((g_0^{-1}(x))(m), n)\]
\[=(y(\pi^{-1}_1(\pi_0^{-1}(x))))(g^{-1}_1(\pi_0^{-1}(x))(g_0^{-1}(x))(m), n)\]
\[=(y(\pi^{-1}_1(\pi_0^{-1}(x))))((((\psi(\pi_0))(g_1))^{-1}g_0^{-1})(x))(m), n).\]
The last equality uses that the group operations for $M(S_{\infty})$ are calculated
pointwise, and hence
\[g_1^{-1}(\pi_0^{-1}(x))=(g_1(\pi_0^{-1}(x)))^{-1}\] and
\[[(((\psi(\pi_0))(g_1))^{-1} g_0^{-1})](x)=
[((\psi(\pi_0))(g_1^{-1}))(x)][g_0^{-1}(x)].\]
%\[=y(\pi_1^{-1}(\pi_0^{-1}(x)))((\psi(\pi_0)(g_1)^{-1}))^{-1}g_0^{-1}(x))(m),n)\]
Thus,
\[[(((g_0,\pi_0)((g_1, \pi_1)(y)))(x))](m,n)=
[y(\pi^{-1}_1(\pi_0^{-1}(x)))](((((\psi(\pi_0))(g_1))^{-1}g_0^{-1})(x))(m), n)\]
\[=[((g_0(\psi(\pi_0)(g_1)),\pi_0\pi_1)(y))(x)](m,n),\]
which establishes this to be an action.
We then let $E^{Y_2}_{G_\infty}$ be the orbit equivalence relation on
$Y_2$
resulting from this action.
\end{definition}
\begin{lemma} \label{5.1.7b} For $y_0, y_1\in Y_2$ we
have
\[y_0 E^{Y_2}_{G_\infty} y_1\]
if and only if there is some $\pi\in M_{\infty}$ such
that
\[\lambda(\{x: \{(y_0(x))(n,\cdot): n\in{\Bbb N}\}=
\{(y_1(\pi^{-1}(x)))(n,\cdot): n\in{\Bbb N}\}\})=1.\]
\end{lemma}
\begin{proof} The ``only if" part of the lemma is trivial.
The ``if" direction uses the well known fact, a proof of which
can be found in 18A \cite{kechrisclassical}, that any Borel
set in the plane may be uniformized by a Lebesgue measurable
function.
\end{proof}
\begin{notation}
Following the Kuratowski-Mycielski theorem of
19A \cite{kechrisclassical}, choose $C\subset [0,1]$ to be a perfect
set such that for any $k\in\N$ and
\[x_1,x_2, ..., x_k\in C\]
we have that if $x_i\not\! = x_j$ all $i0$ there is $g\in H_0$ of the form
\[g=\sum_{j=1}^{j=k} c_j\chi_{A_j}\]
with
\[d_0(g, f_0)<\frac{\epsilon}{3},\]
some $k\in\N$, $c_1,c_2,..., c_k\in{\Bbb C}$, of absolute value 1,
and measurable subsets
$A_1, ..., A_k$ of $\T$, each given by
\[A_n=\{e^{2\pi i x}\mid a_n\leq x0$. Following the
Kakutani-Rokhlin lemma (see page 48 \cite{petersen}) we may find
$A\subseteq \T$ so that for some $n$
\leftskip 0.5in
\noindent (i) $A$, $e^{2\pi i {\surd 2 } }A$, $e^{4\pi i {\surd 2 } }A$,...
$e^{2n\pi i {\surd 2 } }A$, are pairwise
disjoint\footnote{Here
$e^{2\pi i {\surd 2 } }A=\{e^{2\pi i {\surd 2 } }\zeta:\zeta\in A\}$.};
\noindent (ii) $\lambda(\bigcup_{l1-\epsilon$.
\leftskip 0in
To obtain the existence of this set $A$ we apply Kakutani-Rokhlin to any
$n>\frac{2}{\epsilon}$ to obtain $A$ so that
\[\lambda(\bigcup_{l\leq n} e^{2l\pi i {\surd 2 } }A)>1-\frac{\epsilon}{2}\]
and the sets
\[A, e^{2\pi i {\surd 2 } }A, e^{4\pi i {\surd 2 } }A, ..., e^{2n\pi i {\surd 2 } }A\]
are disjoint as in (i).
Then we must have $\lambda(A)<\frac{\epsilon}{2}$ and (ii) follows as well.
Now we may simply step around this sequence
$A$, $e^{2\pi i {\surd 2 } }A$, $e^{4\pi i {\surd 2 } }A$,...
$e^{2n\pi i {\surd 2 } }A$,
defining $f|_{e^{2l\pi i {\surd 2 } }A}$ by induction on $l$ so that at each
$\xi\in e^{2l\pi i {\surd 2 } }A$ we have $f(\xi) h_0(\xi) (f(\xi
e^{2\pi i {\surd 2 } }))^{-1}=h_1(\xi)$.
More formally, we let $f|_A$ just be constantly 1. Assuming inductively that
$l1/4\lambda(A)\lambda(B).\]
Since $h\mapsto T_h$ is continuous, the set of $h$ for which
$T_h$ is ergodic is again $G_{\delta}$.
However there is {\it some} $h$ for which $T_h$ is ergodic -- for instance
$h:\T\rightarrow \T$, $\zeta\mapsto \zeta$ (see here \cite{befo} or
\cite{furstenberg}). Thus by \ref{4.12}, the set of $h$ for which $T_h$ ergodic
is a
dense $G_{\delta}$.
\end{proof}
\begin{notation} Let $X_0=\{h\in X: T_h$ is ergodic $\}$.
\end{notation}
By \ref{4.14} we have that $X_0$ is $G$-invariant; since it is $G_\delta$
we have that it is a Polish $G$-space in its own right.
For the convenience of the reader,
we give the next definition only in the narrow context that is
directly relevant.
The more general definitions can be found in \cite{zimmer2} or
\cite{petersen} $\S$2.4.
\begin{definition} Let
\[\rho:\T^2\rightarrow \T^2\]
be an invertible measure preserving transformation of the
form
\[(\zeta, \xi) \mapsto (\zeta e^{2\pi i \surd{2}} ,
\hat{\rho}(\zeta, \xi))\]
where $\hat{\rho}:\T^2\rightarrow \T$.
Then a non-zero function $f\in L^2(\T^2)$ is said to be a
{\it generalized eigenfunction} for $\rho$ if there is some
$g\in L^2(\T)$, called a {\it generalized eigenvalue}, with
the property that for all $(\zeta, \xi)\in \T^2$ we have
\[f\circ \rho(\zeta, \xi)=g(\zeta)(f(\zeta, \xi));\]
in other words, $f\circ \rho =\hat{g}f$ for $\hat{g}$ defined
by
\[\hat{g}(\zeta, \xi)=g(\zeta).\]
\end{definition}
The next couple of lemmas are standard; more general results, along with
related facts, can be found in \cite{zimmer2}.
\begin{lemma} \label{4.15a} Let $h\in X_0$ and let $f_1, f_2\in L^2(\T^2)$ be
generalized eigenfunctions for $T_h$ with
a common generalized eigenvalue. Then $f_1$ is a linear multiple of $f_2$.
\end{lemma}
\begin{proof} $f_1^{-1}f_2$ is invariant under $T_h$, and hence must be a
constant function by ergodicity.
\end{proof}
\begin{lemma}
\label{4.15b} Let $h\in X_0$. Then the only generalized eigenfunctions
are
\[(\zeta, \xi)\mapsto \xi^n k(\zeta)\]
for some measurable function
\[k: \T \rightarrow {\Bbb C}.\]
\end{lemma}
\begin{proof}
Note that by Stone-Weierstrass, every function $f\in L^2(\T^2)$
can be written as
\[f:(\zeta, \xi)\mapsto \sum_{n\in \Z}\xi^n k_n(\zeta)\]
for some $k_n\in L^2(\T)$. Moreover decomposition is unique, since
\[(\zeta, \xi)\mapsto \xi^nk_n(\zeta)\]
and
\[(\zeta, \xi)\mapsto \xi^m k_m(\zeta)\]
are orthogonal for $n\not = m$.
Now let us suppose that
\[f:(\zeta, \xi)\mapsto \sum_{n\in \Z}\xi^n k_n(\zeta)\]
has $g$ as its generalized eigenfunction. Then
\[f\circ T_h :(\zeta, \xi)\mapsto \sum_{n\in \Z}\xi^n
h(\zeta)^n k_n(\zeta e^{2\pi i \surd 2}).\]
Then the uniqueness of the decomposition of $f\circ T_h$ gives
for a.e. $\zeta\in\T$ that
\[\xi^n h(\zeta)^n k_n(\zeta e^{2 \pi i \surd{2}})=g(\zeta) \xi^n k_n(\zeta).\]
This means that any $k_n$ not identically zero gives rise
to
\[(\zeta, \xi)\mapsto \xi^n k_n(\zeta)\]
as a function with generalized eigenfunction $g$; thus by
\ref{4.15a} we have $k_n\equiv 0$ for all but a single $n$.
\end{proof}
\begin{lemma} \label{4.17}
For all $h_0, h_1\in X_0$
\[T_{h_0}\approx T_{h_1}\Rightarrow h_0 E^X_G h_1.\]
\end{lemma}
\begin{proof}
Fix $h_0, h_1$ with $T_{h_0}\approx T_{h_1}$, and
let $\pi\in M_{\infty}$ witness this -- in that
$\pi T_{h_0} \pi^{-1}=T_{h_1}$ $\lambda^2$ a.e.
By ergodicity
\[(\zeta, \xi)\mapsto \zeta\]
is up to scalar multiples the only eigenfunction with
eigenvalue $e^{2\pi i {\surd 2 } }$ for
both $T_{h_0}$ and $T_{h_1}$.
Thus
\[\pi(\zeta, \xi)=(\zeta_0\zeta, \hat{\rho}(\zeta, \xi))\]
for some fixed $\zeta_0\in\T$ and suitable $\hat{\rho}$.
By replacing $h_0$ by
$((\zeta_0)^{-1}, \bar{0}, 1)\cdot h_0$ we may assume that
$\zeta_0=1$ and thus
\[\pi(\zeta, \xi)=(\zeta, \hat{\rho}(\zeta, \xi)).\]
By \ref{4.15b} we have that the only generalized
eigenfunctions for $T_{h_i}$ ($i$ equal to either 0 or 1) are of the
form
\[(\zeta,\xi)\mapsto \xi^n k(\zeta)\]
for some $n\in\Z$ and measurable $k:\T\rightarrow {\mathbb C}$.
Thus we see that the generalized eigenfunctions of the form
\[(\zeta,\xi)\mapsto \xi k(\zeta)\]
\[(\zeta,\xi)\mapsto \xi^{-1} k(\zeta)\]
have a privileged status, as the only generalized eigenfunctions which
are able to generated the space $L^2(\T^2, \lambda^2)$ by the operations
of multiplication, addition, and multiplication by linear combinations of
the eigenfunctions $(\zeta, \xi)\mapsto \zeta^m$ some $m\in \Z$
(here by generate, I mean that they are dense in the sense of the
Hilbert space norm on $L^2$).
Note then that $(\zeta, \xi)\mapsto \xi$
must be sent to a generalized eigenfunction for $T_{h_1}$ of the
form
\[(\zeta,\xi)\mapsto \xi^{j} k(\zeta)\]
where $j$ is either $1$ or $-1$.
Thus
we may assume
\[\pi(\zeta, \xi)=(\zeta, \xi^{(-1)^i} k(\zeta))\]
for some measurable $k:\T\rightarrow\T$,
and so
\[\pi^{-1}(\zeta, \xi)=(\zeta, \xi^{(-1)^i} (k(\zeta))^{(-1)^{i+1}}).\]
Thus
\[( e^{2\pi i {\surd 2 } }\zeta, h_0(\zeta)\xi)=\pi^{-1} T_{h_1}
\pi(\zeta, \xi)=\pi^{-1} T_{h_1}(\zeta, k(\zeta)(\xi)^{(-1)^i})\]
\[=\pi^{-1}(\zeta e^{2\pi i {\surd 2 }} , k(\zeta) h_1(\zeta)(\xi)^{(-1)^i})
=(\zeta e^{2\pi i {\surd 2 } },
(k(\zeta e^{2\pi i {\surd 2 } }))^{(-1)^{i+1}}
(h_1(\zeta))^{(-1)^i}k(\zeta)^{(-1)^i}\xi).\]
Thus for a.e. $(\zeta, \xi)$ we have
\[ [(k(\zeta e^{2\pi i {\surd 2 } })^{-1}h_1(\zeta) k(\zeta)]^{(-1)^i}
=h_0(\zeta),\]
and so $h_0 E^X_G h_1$ as required.
\end{proof}
\begin{lemma} \label{4.18}
Every orbit in $X$ is meager.
\end{lemma}
\begin{proof}
Let
\[A_0=\T\times \{e^{2 \pi i x}\mid \frac{1}{4}\leq x
\leq \frac{3}{4}\}.\]
\medskip
\noindent{\bf Claim:} For any $O_1, O_2\subset X$ open, non-empty and
$A$ measurable, there exist $h_1\in O_1$, $h_2\in O_2$,
$k\in\N$, $k>0$. with
\[\lambda^2(A\Delta T^k_{h_1}(A))<\frac{1}{13},\]
\[\lambda^2(A_0\Delta T^k_{h_2}(A_0))>\frac{1}{4}.\]
\noindent{\bf Proof of Claim:} Let $\hat{h}_1$ be the function
on $\T$
\[\hat{h}_1: \zeta\mapsto 1,\]
and let $\hat{h}_{\surd{3}}$ be the function
\[\hat{h}_{\surd{3}}: \zeta\mapsto e^{2\pi i \surd{3}}.\]
Then by \ref{4.12} we may find
$(1, \bar{0}, f_1), (1, \bar{0}, f_2)\in G$
with
\[h_1=_{\rm df} (1, \bar{0}, f_1)\cdot \hat{h}_1\in O_1,\]
\[h_2=_{\rm df} (1, \bar{0}, f_2)\cdot \hat{h}_{\surd{3}}\in O_2.\]
Since the continuous functions are dense in $L^1$ we may
actually assume that $f_1$ and $f_2$ are continuous. Then
\[h_1(e^{2\pi i x})=f_1(e^{2\pi i x})\hat{h}_1
(e^{2\pi i x})(f_1(e^{2\pi i (x+\surd{2})}))^{-1}\]
\[=f_1(e^{2\pi i x})(f_1(e^{2\pi i (x+\surd{2})}))^{-1}\]
and thus
\[T_{h_1}: (e^{2\pi i x}, \xi)\mapsto
(e^{2\pi i (x+\surd{2})},
f_1(e^{2\pi i x})(f_1(e^{2\pi i (x+\surd{2})}))^{-1}\xi)\]
and
\[(T_{h_1})^k: (e^{2\pi i x}, \xi)\mapsto
(e^{2\pi i (x+k\surd{2})},
f_1(e^{2\pi i x})(f_1(e^{2\pi i (x+k\surd{2})}))^{-1}\xi).\]
An exactly similar calculation gives
\[(T_{h_2})^k: (e^{2\pi i x}, \xi)\mapsto
(e^{2\pi i (x+k\surd{2})},
f_2(e^{2\pi i x}) e^{2k\pi i\surd{3}}
(f_2(e^{2\pi i (x+k\surd{2})}))^{-1}\xi).\]
The continuity of $f_1, f_2$ guarantees for each $\delta$ some
corresponding
$\hat{\delta}>0$ such that whenever
\[|e^{2k\pi i \surd{2}} -1|<\hat{\delta}\]
then
for all $x\in [0, 1]$
\[|f_1(e^{2\pi i x})-f_1(e^{2\pi i (x+k\surd{2})})|,
|f_2(e^{2\pi i x})-f_2(e^{2\pi i (x+k\surd{2})})|<\delta.\]
Since $\surd{2}$ and $\surd{3}$ are rationally independent, we
can therefore apply Kronecker's lemma (theorem 28 of \cite{morris}) and
find $k$ with
\[|f_1(e^{2\pi i x})-f_1(e^{2\pi i (x+k\surd{2})})|,\]
\[|f_2(e^{2\pi i x})-f_2(e^{2\pi i (x+k\surd{2})})|\]
both arbitrarily small for all $x\in [0,1]$ and $e^{2k\pi i \surd{3}}$
arbitrarily close to $e^{\pi i}$. Such $k$ clearly suffices.
\hfill (Claim$\square$)
\medskip
Now let us choose a sequence of measurable sets $(B_i)_i$ such that
for all $\pi\in M_\infty$ there is some $i\in\N$ with
\[\lambda^2(\pi(A_0)\Delta B_i)<\frac{1}{13}.\]
Let $V_i$ be
\[\{\pi\in M_\infty\mid \lambda^2(\pi(A_0)\Delta B_i)<\frac{1}{13}\}.\]
By \ref{4.14} suffices to show that for each $i$ the set
\[\{(h_1, h_2)\in X\times X\mid \exists \pi \in V_i
(\pi^{-1} \circ T_{h_1}\circ \pi =T_{h_2})\}\]
is nowhere dense.
But given any non-empty open $O_1, O_2\subset X\times X$ we can
by the above claim find some non-empty open $U_1\subset O_1,
U_2\subset O_2$ and $k\in\N$
such that for all $h_1\in U_1$, $h_2\in U_2$
\[\lambda^2(B_i\Delta T^k_{h_1}(B_i))<\frac{1}{13},\]
\[\lambda^2(A_0\Delta T^k_{h_2}(A_0))>\frac{1}{4}.\]
Fixing such $h_1, h_2$ and $\pi\in V_i$ we need to show
\[\pi^{-1} \circ T_{h_1}\circ \pi\not = T_{h_2}.\]
But since $\pi$ is measure preserving we have
\[\lambda^2(A_0\Delta (\pi^{-1}T_{h_1}\pi)^k(A_0))
=\lambda^2(A_0\Delta \pi^{-1} (T^k_{h_1}(\pi (A_0))))\]
\[=\lambda^2(\pi(A_0)\Delta T^k_{h_1}(\pi (A_0))),\]
which by the triangle inequality is bounded by
\[\lambda^2(\pi(A_0), B_i)+ \lambda^2(B_i, T^k_{h_1}(B_i))
+\lambda^2(T^k_{h_1}(B_i), T^k_{h_1}(\pi(A_0)))\]
\[=\lambda^2(\pi(A_0), B_i)+ \lambda^2(B_i, T^k_{h_1}(B_i))
+\lambda^2(B_i, \pi(A_0))\]
since $T_{h_1}^k$ is measure preserving, which in turn is bounded by
\[\frac{1}{13}+\frac{1}{13}+\frac{1}{13}<\frac{1}{4}\]
by assumption of $h_1\in U_1$ and $\pi\in V_i$.
This is as required to show
\[\lambda^2(A_0\Delta \pi^{-1} (T^k_{h_1}(\pi (A_0))))
\not =
\lambda^2(A_0\Delta T^k_{h_2} (A_0)).\]
\end{proof}
\begin{definition} Let $H$ be a Polish group and $Y$ a Polish
$H$-space. The action of $H$ on $Y$ is said to be {\it turbulent} if
\leftskip 0.5in
\noindent (i) every orbit is dense;
\noindent (ii) every orbit is meager;
\noindent (iii) for all $x, y\in Y$, $U\subseteq Y$, $V\subseteq H$ open with
$x\in U$, $1\in V$, there exists $y_0\in [y]_H$ (the orbit of $y$) and
such that for all open $U_0$ containing $y_0$ there is $k\in\N$,
$(h_i)_{i< k}\subseteq V$, $(x_i)_{i\leq k}\subseteq U$ with
\[x_0=x,\]
\[x_{i+1}=h_i\cdot x_i,\]
and
\[x_k\in U_0.\]
\leftskip 0in
\end{definition}
The usefulness of this concept is that it gives a sufficient condition for
a degree of
non-classifiability: As in \cite{hjorth} no
turbulent action allows a Borel -- or even
Baire measurable --
function reducing its orbit equivalence relation to isomorphism on
countable structures. More generally, any equivalence relation into which
we can embed a turbulent orbit equivalence relation will similarly
be unclassifiable by countable structures considered up to isomorphism.
\begin{lemma} \label{4.20} The action of $G$ on $X_0$ is turbulent.
\end{lemma}
\begin{proof} We already established
that every orbit is dense and meager, so we are only left to show the
``local density" condition at (iii) from the definition of turbulence.
For this purpose, fix $h_0, h_1\in X$ and $\epsilon>0$. It suffices
to show there is some $n\in\N$ and there are some $g_0, g_1,...,g_{n-1}\in G$
such that
\[h_{0,0}=h_0,\]
\[h_{0,l+1}=g_l\cdot h_{0,l},\]
we have
\leftskip 0.5in
\noindent (i) $d_G(g_l, 1_G)<\epsilon$ each $l3/\epsilon$. Appealing to
Kakutani-Rokhlin we find $A\subseteq \T$ with
\leftskip 0.5in
\noindent (iv) $A$, $e^{2\pi i {\surd 2 } }A$, $ e^{4\pi i {\surd 2 } }A$,...
$ e^{2n\pi i {\surd 2 } }A$ all disjoint;
\noindent (v) $\therefore \lambda(A)<\epsilon/3$;
\noindent (vi) $\lambda(\bigcup_{l\leq n} e^{2l\pi i {\surd 2 } }A)
>1-\epsilon/3$.
\leftskip 0in
We now define $f_l:\T\rightarrow \T$ by induction on $l k, l