

% 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 $i<j\leq k$ then 
$x_1, x_2,..., x_k$ are rationally independent. 
Fix a continuous injection 
\[\varphi_C:2^\N \hookrightarrow C.\] 
\end{notation} 

To each element $y$ of $Y_2$ we wish to associate a measure preserving transformation
\[T_y:[0,1]\times ({\Bbb R}/{\Bbb Z})^{\Bbb N}\rightarrow 
[0,1]\times {\Bbb R}/{\Bbb Z}^{\Bbb N}\] 
whose ergodic components have the form
\[\{x\}\times ({\Bbb R}/{\Bbb Z})^{\Bbb N}\] 
for $x\in[0,1]$; on each such ergodic component we will
have a discrete spectrum measure preserving transformation with eigenvalues
$\{e^{2\pi i \varphi_C((y(x))(n, \cdot))}: n\in{\Bbb N}\}$.
The proof that $y_1 E^{Y_2}_{G_{\infty}}y_2$ 
if and only if $T_{y_1}$ and $T_{y_2}$ are conjugate
is then a consequence of the well known fact that two measure preserving transformations are
conjugate if and only if there is a measure one set on which their ergodic components are
individually conjugate component by component. Partly for the convenience of the reader, 
and partly because there seems no easy source listing exactly the facts we 
need in exactly the form we need them, we write out the proof 
in $\S$\ref{2} without assuming any 
familiarity with the ergodic decomposition of a measure preserving transformation.


\newpage 




\section{$E^{Y_2}_{G_\infty}\leq_B \approx^*$} 
\label{2} 


\begin{definition} Let $T:(X, {\cal B}, \mu)\rightarrow (X, {\cal B}, \mu)$ be Borel a
measure preserving map, $X$ a Polish space, $\mu$ a Borel probability measure on $X$,
${\cal B}$ the collection of Borel subsets of $X$. A non-zero
$f\in L^2(X,\mu)(=_{df}$ the Hilbert
space of all square integrable complex valued functions on $(X,\mu)$, subject to the usual
identification of functions that agree almost everywhere) is said to be an
{\it eigenfunction} for $T$ if for some $\lambda\in {\Bbb C}$ we have $f\circ T=\lambda f$ a.e; we
then also say that $\lambda$ is an {\it eigenvalue}. $T$ is said to be {\it ergodic} if
all $T$-invariant Borel sets are either null or conull with respect to $\mu$.
\end{definition} 

\begin{lemma} \label{5.1.15} 
$T:(X, {\cal B}, \mu)\rightarrow (X, {\cal B}, \mu)$ is ergodic
if and only if the space of eigenfunctions with eigenvalue 1 is one dimensional. 
\end{lemma} 

\begin{proof} If $f:X\rightarrow {\Bbb C}$ is a non-constant eigenfunction for 
the eigenvalue 1, then for some $U\subset{\Bbb C}$ the pullbacks $f^{-1}[U]$ 
and $f^{-1}[{\Bbb C}\setminus U]$ are disjoint and non-null. 
\end{proof} 







Hence if $T$ is ergodic then no eigenvalue can have corresponding eigenspace with
dimension greater than 1 -- for if $f_1, f_2:X\rightarrow {\Bbb C}$ are linearly  
independent non-zero functions with $f_1\circ T=cf_1$ and $f_2\circ T=cf_2$ then  
\[f_2/f_1:X\rightarrow {\Bbb C}\] would be a non-constant function with
eigenvalue 1.




\begin{definition}  
Let $X=[0,1]\times {\Bbb R}/{\Bbb Z}^{\Bbb N}$ with the product of
  Lebesgue  measure on $[0,1]$ and Haar measure $\nu$ on each copy of
${\Bbb R}/{\Bbb Z}$ (so that
$\nu(\{x{\Bbb Z}:a\leq x\leq b\})=b-a$ for any $0<a<b\leq 1$).
For $y\in Y_2$ we define
\[T_y:X\rightarrow X\]
by
\[T_y(x, z_0, z_1, ...)=(x, \varphi_C((y(x))(0,\cdot))\oplus z_0,
\varphi_C((y(x))(1,\cdot))\oplus z_1,...),\]
where $\oplus$ is addition modulo 1.
For $x\in[0,1]$ we let $T_y^x:({\Bbb R}/{\Bbb Z})^{\Bbb N}\rightarrow 
({\Bbb R}/{\Bbb Z})^{\Bbb N}$ be the
map resulting from restriction to the fiber  above $x$:
\[T_y^x( z_0, z_1, ...)=(\varphi_C((y(x))(0,\cdot))\oplus z_0, 
\varphi_C((y(x))(1,\cdot))\oplus z_1,...)\]
\end{definition} 

\begin{lemma} \label{5.1.17} 
For all $y\in Y_2$ and $x\in[0,1]$:

\leftskip 0.5in 

\noindent (i) the set of eigenvalues of $T^x_y$ is the subgroup of the complex unit circle
generated by $\{e^{2\pi i \varphi_C((y(x))(n,\cdot)}: n\in{\Bbb N}\}$;

\noindent (ii) $T_y^x: ({\Bbb R}/{\Bbb Z})^{\Bbb N}
\rightarrow ({\Bbb R}/{\Bbb Z})^{\Bbb N}$ is ergodic.

\leftskip 0in 

\end{lemma} 

\begin{proof} 
For $x$ such that $\{(y(x))(n,\cdot): n\in{\Bbb N}\}$ is a rationally independent set
we can use the Stone-Weierstrass theorem 
to see that the sums of the {\it finite} multiples of the projection functions 
and their inverses  
\[Pr_k: ({\Bbb R}/{\Bbb Z})^{\Bbb N}\rightarrow {\Bbb C},\]            
\[\vec z\mapsto e^{2\pi iz_k}\]
are dense in 
$L^2({\Bbb R}/{\Bbb Z}^{\Bbb N},\mu^{\Bbb N})$. Hence the functions of the 
form 
\[(Pr_{k_1})^{n_1}\cdot (Pr_{k_2})^{n_2}...(Pr_{k_p})^{n_p},\] 
as $\langle n_1, n_2,..., n_p \rangle$ and $\langle k_1,..., k_p\rangle$ 
range over finite sequences from $\Z$ and $\N$,  
form a Hilbert basis for $L^2({\Bbb R}/{\Bbb Z}^{\Bbb N},\mu^{\Bbb N})$. 
The rational independence 
property assumed for $C$ implies 
\[(Pr_{k_1})^{n_1}\cdot (Pr_{k_2})^{n_2}...(Pr_{k_p})^{n_p}\] 
and 
\[(Pr_{l_1})^{m_1}\cdot (Pr_{l_2})^{m_2}...(Pr_{l_q})^{m_q}\] 
have distinct eigenvalues whenever these functions are distinct, 
any eigenfunctions must be a
finite multiple of these coordinate functions
\[Pr_k: ({\Bbb R}/{\Bbb Z})^{\Bbb N}\rightarrow {\Bbb C},\]
\[\vec z\mapsto e^{2\pi iz_k}.\]
Thus up to scalar multiplication the only
eigenfunctions are 1 and the finite
multiples of the coordinate projections, $\{Pr_k:k\in{\Bbb N}\}$. 
\end{proof} 


\begin{lemma} \label{5.1.18} 
If $y\in Y_2$ and $A\subset X$ is Borel and
$T_y$-invariant then there is
a Borel $B\subset X$ so that $A=B\times 
({\Bbb R}/{\Bbb Z})^{\Bbb N}$ modulo some null set.
\end{lemma} 


\begin{proof} 
For each $x\in [0,1]$ we have that 
\[A^x=\{\vec z: (x, \vec z)\in A\}\] 
is $T_y^x$-invariant. 
Thus by \ref{5.1.17} 
\[\nu^{\Bbb N}(A^x)\in\{0,1\}\]
(where $\nu^{\Bbb N}$ is the
$\N$-fold product of
Haar measure $\nu$ on ${\Bbb R}/{\Bbb Z}$). Thus for
$B=\{x\in[0,1]: \nu^{\Bbb N}(A^x)=1\}$ we have
$A=B\times ({\Bbb R}/{\Bbb Z})^{\Bbb N}$ off of a null set by Fubini. 
\end{proof} 


\begin{lemma} \label{5.1.19} 
If $y_1, y_2\in Y_2$, $x_1, x_2 \in [0,1]$, then 
the transformations $T_{y_1}^{x_1}$
and $T_{y_2}^{x_2}$ are conjugate
if and only if 
\[\{(y_1(x_1))(n,\cdot): n\in{\Bbb N}\}=
\{(y_2(x_2))(n,\cdot): n\in{\Bbb N}\}.\] 
\end{lemma} 


\begin{proof} 
By \ref{5.1.17}, the
transformations $T_{y_1}^{x_1}$ and $T_{y_2}^{x_2}$ are conjugate only if
the set of eigenvalues are equal, which is to say that the multiplicative
subgroup of the complex unit circle
generated by
$\{e^{2\pi i\varphi_C((y_1(x_1)(n, \cdot))}: n\in{\Bbb N}\}$ and
$\{e^{2\pi i\varphi_C((y_2(x_2)(n, \cdot))}: n\in{\Bbb N}\}$ are equal;
and this in turn, by the assumptions on $C$, holds only if
\[\{e^{2\pi i\varphi_C((y_1(x_1)(n, \cdot))}: n\in{\Bbb N}\}=
\{e^{2\pi i\varphi_C((y_2(x_2)(n, \cdot))}: n\in{\Bbb N}\}.\]

The converse direction is trivial. 
\end{proof} 

\begin{lemma} \label{5.1.20} 
If $y_1, y_2\in Y_2$ with $T_{y_1}, T_{y_2}$ conjugate
then we may find $g\in G_{\infty}$ with $g\cdot y_1=y_2$.
\end{lemma} 

\begin{proof} If $\pi:X\rightarrow X$ is measure preserving and conjugates
$T_{y_1}$ and $T_{y_2}$ then we use 
\ref{5.1.18} to find some measure one set $M$ such that
for all basic open $O\subset [0,1]$ there is $B_{O}, D_{O}\subset [0,1]$ so that
\[\pi[(O\times({\Bbb R}/{\Bbb Z})^{\Bbb N})\cap M]=
(B_O\times ({\Bbb R}/{\Bbb Z})^{\Bbb N})\cap M,\]
\[\pi^{-1}[(O\times({\Bbb R}/{\Bbb Z})^{\Bbb N})\cap M]=
(D_O\times ({\Bbb R}/{\Bbb Z})^{\Bbb N})\cap M.\]
We may also assume that $M$ is invariant under $\pi$, $T_{y_1}$, $T_{y_2}$.
Thus we have that on the measure one set $M$ for all $(x,\vec z)\in M$ there is
some $\hat{\pi}(x)\in[0,1]$ so that $\pi|_{(\{x\}\times {\Bbb R}/{\Bbb Z}^{\Bbb N})}$
conjugates 
\[T_{y_1}|_{(\{x\}\times {\Bbb R}/{\Bbb Z}^{\Bbb N}\cap M)}\] 
and 
\[T_{y_2}|_{(\{\hat{\pi}(x)\}\times {\Bbb R}/{\Bbb Z}^{\Bbb N}\cap M)}.\]   
This $\hat{\pi}:[0,1]\rightarrow [0,1]$
is measure preserving since for a.e.  $(x, \vec z)\in [0,1]\times 
\T^\N$ we have 
\[\pi(x, \vec z)=(\hat{\pi}(x), \vec z'),\] 
some $\vec z'\in \T^\N$. 
Thus we are finished by \ref{5.1.7b}. 
\end{proof} 









\begin{lemma} \label{5.1.21} 
If $g\in G_{\infty}$ with $g\cdot y_1=y_2$ then
$T_{y_1}$ and $T_{y_2}$ are conjugate.
\end{lemma} 


\begin{proof} This is simply unpacking the definitions.
   
First consider the case that $g=(1, \hat{\pi})$, some $\hat{\pi}\in M_{\infty}$.
Then
\[(y_2(x))(n, \cdot)= ((g\cdot y_1)(x))(n,\cdot)=_{df}(y_1(\hat{\pi}^{-1}(x)))(n,\cdot)\]
for a.e. $x\in[0,1]$ and all $n\in{\Bbb N}$. Thus we can define ${\pi}:X\rightarrow X$
by ${\pi}(x, \vec z)=(\hat{\pi}(x), \vec z)$ to obtain
\[T_{y_2}={\pi}\circ T_{y_1}\circ{\pi}^{-1}.\]

Similarly if $\sigma\in M(S_{\infty})$ with $(\sigma, 1)\cdot y_1=y_2$ then we
can define $\pi: X\rightarrow X$ by
\[(x, z_0, z_1, z_2,...)\mapsto (x, z_{(\sigma(x))(0)}, z_{(\sigma(x))(1)},...).\]

The above terminates the proof, since any
$g\in G_{\infty}$ can be written in the form $g=(\sigma, 1)(1, \hat{\pi})$.
\end{proof} 

\begin{definition} Following earlier notation, 
let $M_{\infty}(X)$ be the group of Borel measure
preserving bijections from $X$ to $X$, again identifying two
maps that agree a.e with respect to the measure $\lambda\times\nu^{\Bbb N}$.
For $(O_n)_{n\in{\Bbb N}}$ a basis
of $X$ we obtain a complete separable metric $d_{X}$ on
$M_{\infty}(X)$ by setting
\[d_{X}(\pi_1, \pi_2)=\sum 2^{-n}
[\lambda\times\nu^{\Bbb N}(\pi_1(O_n)\Delta\pi_2(O_n))
+\lambda\times\nu^{\Bbb N}(\pi_1^{-1}(O_n)\Delta\pi_2^{-1}(O_n))].\]
Note then that $M_{\infty}(X)$ is
a Polish group under composition. It is in fact isomorphic to $M_{\infty}$,
since we can find a measure isomorphism
$\Phi:(X,\lambda\times\nu^{\Bbb N})\rightarrow ([0,1],\lambda)$ and then
take the induced isomorphism
\[\hat{\Phi}: M_{\infty}(X)\rightarrow M_{\infty},\]
\[\pi\mapsto{\Phi}^{-1}\circ \pi \circ {\Phi}.\] 

Let $\approx^{**}$ denote the conjugacy
equivalence relation on $M_{\infty}(X)$.

\end{definition} 

\begin{lemma} \label{5.1.23} 
The map
\[Y_2\rightarrow M_{\infty}(X),\]   
\[y\mapsto T_y,\]
is continuous.
\end{lemma} 

\begin{proof} Let $M(\lambda\times \nu^\N)$ be the algebra of 
measurable subsets of $(X, \lambda\times \nu^\N)$ subject to the 
usual identification of sets which agree off of a null set; 
this a Polish space in the metric 
$d(A, B)=\lambda\times \nu^\N(A\Delta B)$ (see 
for instance 2.2 \cite{hjorth}). 
First note almost immediately from the definitions
that if $A\subset [0,1]\times({\Bbb R}/{\Bbb Z})^{\Bbb N}$ is a basic open set
of the form $\{\vec x: x(i)\in J\}$ for some open interval $J$ included in either
$[0,1]$ or ${\Bbb R}/{\Bbb Z}$, then the resulting map into the measure algebra
\[Y_2\rightarrow M(\lambda\times\nu^{\Bbb N}),\]
\[y\mapsto T_y(A)\]
is continuous.
Since the subalgebra of the Boolean algebra of  
measurable sets in $(X, \lambda\times\nu^{\Bbb N})$
generated by the cylinders is dense, we obtain that $y\mapsto T_y$ is continuous.
\end{proof} 

\begin{proposition} 
\label{5.1.23b} $E^{Y_2}_{G_\infty}\leq_B \approx^{*}.$ 
\end{proposition} 

\begin{proof} 
$X$ and $[0,1]$ are two non-atomic, standard Borel probability spaces, and 
hence\footnote{See for instance 17.41 of \cite{kechrisclassical}} 
they are isomorphic 
as measure spaces. 
Thus it suffices to show 
\[E^{Y_2}_{G_\infty}\leq_B \approx^{**},\] 
which is exactly the content of the last three lemmas. 
\end{proof} 


There are some details here which were not needed in developing a proof of 
\ref{5.1.23b} but which might have independent interest. Namely, the 
group $G_\infty$ is a Polish group, and its action on $Y_2$ is not only 
continuous but also turbulent in the sense of 
\cite{hjorth}. 

\newpage 










\section{$E^{{\rm Mod(Gph)}}_{S_\infty}\leq_B E^{Y_2}_{G_\infty}$} 
\label{3} 

\begin{notation} From now until the end of the section fix 
continuous one-to-one 
\[f_0:2^\N\hookrightarrow 2^\N\] 
\[f_1: 2^\N\times 2^\N\hookrightarrow 2^\N\] 
with 
\[f_0[2^\N]\cap f_1[2^\N\times 2^\N]=\emptyset.\] 
\end{notation} 

It is easily seen that such a pair $f_0$, $f_1$ exists. 
For instance 
\[(f_0(y))(n+1)=y(n),\] 
\[(f_0(y))(0)=0,\] 
\[(f_1(y_1, y_2))(2n+1)=y_1(n),\] 
\[(f_1(y_1, y_2))(2n+2)=y_2(n),\]
\[(f_1(y_1, y_2))(0)=1.\]

\begin{notation} 
For $\vec z=(z_i)_{i\in\N}\in (2^\N)^\N$ and 
$x\in$ Mod(Gph) we let 
\[\p(2^\N, x, \vec z)=\{y\in 2^\N\mid \exists n (y=f_0(z_n))\}
\cup \{y\in 2^\N\mid \exists n, m (y=f_1(z_n, z_m), x(n, m)=1)\}.\] 

\end{notation} 



We have previously defined $B_2$ to be the set of $w\in 2^{\N\times\N}$ 
such that for all $n_1\not\! =n_2$ we have $w(n_1,\cdot)\not\! = 
w(n_2, \cdot)$. 

\begin{lemma} 
\label{3.1} There is a Borel function 
\[\varphi_{\rm eva}: {\rm Mod(Gph)}\times (2^\N)^\N\rightarrow B_2\] 
such that for all $x\in {\rm Mod(Gph)}$ and $\vec z\in (2^\N)^\N$ with 
$z_i\neq z_j$ all $i\neq j$ 
we have 
\[\{(\varphi_{\rm eva}(x, \vec z))(n, \cdot)\mid n\in\N\} 
=\p(2^\N, x, \vec z).\] 
\end{lemma} 

\begin{proof} 

We may partition Mod(Gph) into Borel sets 
\[A_0, A_1, A_2, ..., A_{\aleph_0}\] 
such that for each $\kappa\in \{0, 1, 2,..., \aleph_0\}$ and 
each $x\in A_\kappa$ there are exactly $\kappa$ many pairs $(n, m)$ 
with $x(n, m)=1$. It suffices then to show 
$\varphi_{\rm eva}\!|_{A_\kappa\times 
(2^\N)^\N}$ is Borel for each $\kappa$. 

Fixing $\kappa$, we divide $\N$ into sets 
$\{a_i: i\in\N\},$ $\{b_j: j<\kappa\}.$ 
Then for a given $x\in A_\kappa$ we can let $(m_j, n_j)_{j<\kappa}$ 
enumerate, in the ordering obtained by comparing maximums and then 
adjudicating ties lexicographically, the pairs $(m, n)$ with $x(m, n)=1$. 
We can then let 
\[\varphi_{\rm eva}(x, \vec z)\in 2^{\N\times\N}\] 
be defined by 
\[(\varphi_{\rm eva}(x, \vec z))(a_i,m)=(f_0(z_i))(m),\] 
\[(\varphi_{\rm eva}(x, \vec z))(b_j,m)=(f_1(z_{m_j}, z_{n_j}))(m).\] 

The verification that the resulting function is Borel is routine. 
\end{proof} 

\begin{notation} Let $\mu$ be the usual product measure on 
$2^\N$, so that for each $n$ we have 
\[\mu(\{x\in 2^\N\mid x(n)=1\})
=\frac{1}{2}{\rm .}\]  
Let $\mu^\N$ be {\it its} corresponding product measure on 
$(2^\N)^\N$. Let $N_2=\{\vec z\in (2^\N)^\N\mid \forall 
i\neq j(z_i\neq z_j)\}$, and note that $\mu^\N(N_2)=1$. 

Since $((2^\N)^\N, \mu^\N)$ and $([0,1],$ Lebesgue measure$)$ are 
both non-atomic and both have standard Borel structures, 
we can find a Borel measure preserving bijection 
\[\varphi_{{\rm iso}}: N_2\rightarrow [0,1].\] 
\end{notation} 

\begin{notation} 
For $x\in {\rm Mod(Gph)}$ define 
\[\psi_x:[0, 1]\rightarrow 2^{\N\times\N}\] 
by 
\[\psi_x(\alpha)=\varphi_{\rm eva}(x, 
\varphi_{\rm iso}^{-1}(\alpha)).\] 
\end{notation} 

\begin{lemma} 
The function 
\[x\mapsto \psi_x\] 
is a Borel function from {\rm Mod(Gph)} to $Y_2$. 
\end{lemma} 

\begin{proof} The key point is that we can apply  \ref{3.1} to see that if 
\[f(\cdot, \cdot)=\varphi_{\rm eva}(\cdot,
\varphi_{\rm iso}^{-1}(\cdot))\] 
then for each $x$ the set 
\[\{\psi_x\}=\{\psi\in Y_2\mid \psi(\beta)=f(x, \beta) {\rm \: a.e.}\beta\}\] 
is a uniformly in $x$ Borel singleton; thus the assignment of $\psi_x$ to 
$x$ is Borel by the uniformization theorem for Borel subsets of the plane 
with countable sections.  
\end{proof} 


\begin{lemma} 
If $x_1, x_2\in {\rm Mod(Gph)}$ with 
\[x_1 E_{S_\infty}^{\rm Mod(Gph)} x_2,\] 
then 
\[\psi_{x_1} E^{Y_2}_{G_\infty} \psi_{x_2}.\] 
\end{lemma} 

\begin{proof} Fix $\sigma\in S_\infty$ with 
\[\sigma\cdot x_1=x_2.\] 
Thus for all $(n, m)\in \N\times \N$ we have 
\[x_1(n, m)=x_2(\sigma(n), \sigma(m)).\] 
And so if we define 
\[\hat{\sigma}: (2^\N)^\N\rightarrow (2^\N)^\N\] 
by 
\[(\hat{\sigma}(\vec z))_n=\vec z_{\sigma(n)}\] 
then $\hat{\sigma}$ is an invertible measure preserving transformation 
such that at each $\vec z$ 
\[\p(2^\N, x_1, \vec z)=\p(2^\N, x_2, \hat{\sigma}(\vec z)).\] 
From this we obtain $\psi_{x_1} E^{Y_2}_{S_\infty} \psi_{x_2}$ 
by \ref{5.1.7b}. 
\end{proof} 
 


\begin{lemma}
If $x_1, x_2\in {\rm Mod(Gph)}$ with
\[\psi_{x_1} E^{Y_2}_{G_\infty} \psi_{x_2},\]
then 
\[x_1 E_{G_\infty}^{\rm Mod(Gph)} x_2.\] 
\end{lemma}

\begin{proof} The assumption that 
$\psi_{x_1} E^{Y_2}_{G_\infty} \psi_{x_2}$ 
in particular implies the existence of some $\vec z^{\: 1}$ and 
$\vec z^{\: 2}$ with 
\[\p(2^\N, x_1, \vec z^{\: 1})=\p(2^\N, x_2, \vec z^{\: 2})\] 
and for all $n\neq m$ 
\[(\vec z^{\: 1})_n\neq (\vec z^{\: 1})_m{\rm ,}\]
\[(\vec z^{\: 2})_n\neq (\vec z^{\: 2})_m .\]
This implies 
\[\{f_0((\vec z^{\: 1})_i): i\in\N\}= 
\{f_0((\vec z^{\: 2})_i): i\in\N\},\] 
and so we can find some $\sigma\in S_\infty$ with 
\[(\vec z^{\: 1})_n=(\vec z^{\: 2})_{\sigma(n)}\] 
all $n\in\N$. 
At this point the assumptions on $f_0$ and $f_1$ give that for all 
$n, m$ 
\[x_1(n, m)= x_2(\sigma(n), \sigma(m)),\] 
and so 
\[\sigma\cdot x_1=x_2.\] 
\end{proof} 

\begin{proposition} 
$E^{{\rm Mod(Gph)}}_{S_\infty}\leq_B E^{Y_2}_{G_\infty}$ 
\end{proposition} 

\begin{proof} 
This is exactly what the last three lemmas show. 
\end{proof} 




\newpage 



\section{Turbulence for the generalized discrete spectrum 
transformations} 
\label{4}



Below we consider the isomorphism relation for generalized discrete spectrum 
transformations, or what \cite{befo} calls the ``measure-distal" 
actions. The results below show non-classifiability by countable 
structures, but perhaps raise more questions than they answer. For instance it 
is not known if there is a way to embed isomorphism of countable models into 
the  generalized discrete spectrum 
transformations, or more modestly just embed the equivalence relation 
\[F_{\alpha},\]  arising from the $\alpha$th iteration of 
the operation ``countable subset of" applied to some standard 
Borel space\footnote{See \cite{frst}.} into some appropriate level 
of the generalized discrete spectrum hierarchy. 

Just by way of comparison, I should mention that for the very simple  
subclass consisting of the transformations having  
completely {\it discrete} spectrum the situation is totally understood. 
Here \cite{hane} shows that we may assign countable subsets of 
${\Bbb C}$ as complete invariants. Indeed Foreman and Louveau have 
observed that even in the Borel context 
this precisely encapsulates the classification difficulty 
of the discrete spectrum maps.  

\begin{theorem} (Foreman, Louveau) \label{foremanlouveau} 
Let $D\subset M_\infty$ be the class 
of discrete spectrum measure preserving transformations. Then: 

\leftskip 0.5in 

\noindent (i) The set $D$ is a Borel subset of $M_\infty$. 

\noindent (ii) There is a sequence of Borel functions 
\[f_n: D\rightarrow \R\] 
such that for all $\pi_1, \pi_2\in D$ 
\[\pi_1\approx^* \pi_2\] 
if and only if 
\[\{f_n(\pi_1): n\in\N\}=\{f_n(\pi_2): n\in\N\}{\rm ;}\] 
thus there is a Borel 
\[\theta_1: D\rightarrow 2^{\N\times \N}\] 
such that for all $\pi_1, \pi_2\in D$
\[\pi_1\approx^* \pi_2 \leftrightarrow 
\{(\theta_1(\pi_1))(n, \cdot): n\in\N\}=
\{(\theta_1(\pi_2))(n, \cdot): n\in\N\}{\rm ,}\]
so in other words we have 
\[\approx^*\! |_D\leq_B F_2.\] 

\noindent (iii) And conversely, 
\[F_2 \leq_B \approx^*\! |_D\] 
in the sense that there is a Borel function 
\[\theta_2: 2^{\N\times \N} \rightarrow D\] 
such that for all $x_1, x_2\in 2^{\N\times \N}$ 
\[\{ x_1(n, \cdot): n\in\N\}=
\{x_2(n, \cdot): n\in\N\}
\Leftrightarrow 
\theta_2(x_1)\approx^*\theta_2(x_2).\] 
\end{theorem} 

In particular the isomorphism relation on the 
discrete spectrum transformations is {\it non-smooth}. 


\begin{notation} Let $\T=\{e^{2\pi i x}:x\in[0,1]\}$, the 
complex unit circle, be viewed as a group under multiplication. 
For the remainder of this section let 
$\lambda$ be the usual Lebesgue measure on $\T$ normalized so that 
$\lambda(\T)=1$. 

Let $H_0=\{f:\T\rightarrow \T\mid $ $f$ is Lebesgue measurable$\}$, 
where we identify $f_0,f_1\in H_0$ if they agree $\lambda$ a.e. 
For $f_0, f_1\in H_0$ the product $f_0f_1\in H_0$ is defined by 
pointwise multiplication: 
\[(f_0f_1)(\zeta)=(f_0(\zeta))(f_1(\zeta)).\] 
We give this group the topology of a.e. pointwise convergence; which is to 
say the topology induced by the metric 

\[d_0(f_0, f_1)=1/2\int |f_0(\xi)-f_1(\xi)|d\lambda,\] 
where $|\cdot|$ is the usual Euclidean distance in ${\Bbb C}$. 
The technical advantage of just this choice for $d_0$ is that whenever  
$f_0$ and $f_1$ differ on a set of measure less than $\epsilon$ we must have 
\[d_G((1, \bar{0},  f_0), (1, \bar{0} , f_1))<\epsilon{\rm .}\] 
\end{notation} 

In future I will use 1 to denote the function in $H_0$ which  
constantly takes the value 1 for all $\zeta\in\T$. This is the 
group identity, which of course creates some notational conflict with 
$H_0$ being commutative. 


\begin{lemma} \label{4.2} 
$H_0$ is an abelian Polish group. 
\end{lemma}

\begin{proof} 
The metric $d_0$ is easily checked to be complete, 
continuous with respect to the group action, 
and separable since 
$L^1(\T,\lambda)$ is separable. 
\end{proof} 



\begin{notation} Let $H_1=\T\times \Z_2$ be the 
direct product of the groups $\T$ and $\Z_2$. We define 
\[\varphi:H_1\rightarrow {\rm Aut} (H_0)\] by the requirement 
that 
\[((\varphi(\zeta,\bar{1}))(f))(\xi)=(f(\xi \zeta))^{-1}\] 
\[((\varphi(\zeta,\bar{0}))(f))(\xi)=(f(\xi \zeta)).\]
\end{notation} 


Note that $H_1$ is a compact Polish group and $\varphi$ is a 
group homomorphism. 

I will write  $\varphi_{(\zeta, \bar{k})}$ for the 
homomorphism 
$\varphi(\zeta, \bar{k}):H_0\rightarrow H_0$. 
The map $\varphi$ is continuous in the following sense: 

\begin{lemma} \label{4.3(a)} The function 
\[H_1\times H_0\rightarrow H_0\] 
\[((\zeta, \bar{i}), f)\mapsto \varphi_{(\zeta, \bar{i})}(f)\] 
is continuous as a map from $H_1\times H_0$ to $H_0$. 
\end{lemma} 

\begin{proof} 
Recall that the step functions consisting of finite linear 
combinations of the characteristic functions of intervals 
are dense in $L^1(\T, \lambda)$. This rapidly implies that for 
$f_0\in H_0$ and $\epsilon>0$ 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 x<a_{n+1}\}.\] 

For continuity it is enough to check that for 
\[(\zeta , \bar{j})=(e^{2\pi i y}, \bar{j})\] 
sufficiently close to the identity and $f\in H_0$ sufficiently close 
to $f_0$ we have 
\[d_0(\varphi_{(e^{2\pi i y}, \bar{j})}(f), f_0)<\epsilon.\] 

But if $\bar{j}=\bar{0}$ and $y$ is close enough to $0$ that 
\[|c_n y|=|y|<\frac{\epsilon}{3k},\] 
$n=1, 2, ..., k$, 
then 
\[d_0(\varphi_{(e^{2\pi i y}, \bar{0})}(g), g)<\frac{\epsilon}{3}{\rm ,}\] 
since at each $n\leq k$ 
\[ \lambda (A_n\Delta \{e^{2\pi y}\zeta | \zeta \in A_n\}) \leq |y|. \]  
$\varphi_{(e^{2\pi i y}, \bar{0})}$ is an isometry, so we have for $f$ close to $f_0$ 
that 
\[d_0(\varphi_{(e^{2\pi i y}, \bar{0})}(g), 
\varphi_{(e^{2\pi i y}, \bar{0})}(f))<\frac{\epsilon}{3},\] 
and thus by the triangle inequality 
\[d_0(\varphi_{(e^{2\pi i y}, \bar{j})}(f), f_0) \leq 
d_0(\varphi_{(e^{2\pi i y}, \bar{j})}(f), \varphi_{(e^{2\pi i y}, \bar{0})}(g))+ 
d_0(\varphi_{(e^{2\pi i y}, \bar{0})}(g), g) + 
d_0(g, f_0)\]
\[<\frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{\epsilon}{3}=\epsilon.\] 
\end{proof} 



\begin{notation} Let $G=H_1\rtimes_{\varphi} H_0$ be the 
semi-direct product of $H_1$ and $H_0$ along $\varphi$. 
Thus for $(\zeta_0, \bar{i}_0,  f_0), (\zeta_1, \bar{i}_1 , f_1)\in G$ 
\[(\zeta_0, \bar{i}_0,  f_0)(\zeta_1, \bar{i}_1 , f_1)=
(\zeta_0\zeta_1, \bar{i}_0+\bar{i}_1, (\varphi(\zeta_1, \bar{i}_1))(f_0)f_1).\] 
\end{notation} 

This order of taking the semi-direct product does give us a group since 
$H_1$ is abelian. 

Here and elsewhere I simply write $(\zeta, \bar{i}, f)$ for an arbitrary 
element of $G$, instead of the more cumbersome but perhaps more formally 
correct $((\zeta, \bar{i}), f)$. 


%All abelian Polish groups have invariant
%metrics; therefore we may 
Fix 
complete metrics 
$d_0$ and $d_1$ 
on $H_0$ and
$H_1$. 







\begin{lemma} \label{4.5} 
$G$ is a Polish group. 
\end{lemma} 


\begin{proof} We obtain a complete and compatible 
metric $d_G$ on $G$ by 
\[d_G((\zeta_0, \bar{i}_0,  f_0), (\zeta_1, \bar{i}_1 , f_1))= 
d_1((\zeta_0, \bar{i}_0), (\zeta_1, \bar{i}_1))+ d_0(f_0, f_1).\] 

It follows from \ref{4.3(a)} and $H_0$ and $H_1$ being topological 
groups that the group operation of  multiplication  is continuous on 
$G$. Since $G$ is Polish as a space it follows from say 
\cite{sosr} that 
\[g\mapsto g^{-1}\] 
is continuous as well. 
\end{proof} 












\begin{notation} Let $X=\{h:\T\rightarrow \T\mid  h$ is 
Lebesgue measurable$\}$, where we identity functions agreeing a.e. 
For future reference we let $d_X$ be a metric given 
on $X$ by $d_X(h_0, h_1)=1/2(\int |h_0(\xi)-h_1(\xi)|d\lambda)$. 

We let $G$ act on $X$ as follows: 

\[((\zeta, {\bar{i}}, f)\cdot h)(\xi)=
[f(\xi/\zeta)h(\xi/\zeta)(f(e^{2\pi i {\surd 2 } } \xi/\zeta))^{-1}]^{(-1)^i}.\] 
(Of course literally as a space $X$ is the same as $H_0$. But here we are thinking of 
$X$ as coming equipped with a $G$-action, while we think of $H_0$ as presented 
with a {\it group structure}.) 
\end{notation}  

\begin{lemma} \label{4.7} This {\rm is} an action. 
\end{lemma} 

\begin{proof} It is trivial to confirm that 
\[(1, \bar{0}, 1)\cdot h =h\] 
all $h\in X$; the main task is to show that the associativity 
properties of the action. 

Let $\hat{H}_0$ be subgroup of $G$ consisting of elements of 
the form 
\[(1, \bar{0}, f)\] 
and let $\hat{H}_1$ consist of those of the form 
\[(\zeta, \bar{i}, 1).\] 
Every element $g$ of $G$ can be written in the form 
\[g=h_0 h_1=h_1^*h_0^*\] 
for suitable $h_0, h_0^*\in \hat{H}_0$ and $h_1, h_1^*\in \hat{H}_1$. 
Hence it suffices to show purely for $k_1, k_2\in \hat{H}_0\cup \hat{H}_1$ 
that we have for all $x\in X$ that 
\[k_1\cdot (k_2\cdot x)=(k_1k_2)\cdot x{\rm ;}\] 
the point is that given arbitrary $g_1, g_2\in G$ we can write 
\[g_1=h_{0, 1}h_{1, 1}\] 
\[g_2=h_{1, 2}h_{0, 2}\] 
(for suitable $h_{0, i}\in \hat{H}_0, h_{1, i}\in \hat{H}_1$) 
and then steadily multiply through to get 
\[g_1\cdot (g_2\cdot x)= h_{0, 1}
\cdot h_{1, 1}\cdot h_{1, 2} 
\cdot h_{0, 2}\cdot x\]
\[=h_{0,1}\cdot (h_{1,1}h_{1, 2})\cdot h_{0, 2}\cdot x\]
\[=(h_{0,1}h_{1,1}h_{1, 2})\cdot h_{0, 2}\cdot x
=h_1^*h_0^*\cdot h_{0, 2}\cdot x\]
(suitable $h_0^*\in \hat{H}_0, h_1^*\in \hat{H}_1$) 
\[ h_1^*\cdot (h_0^*h_{0, 2})\cdot x =(h_1^*h_0^*h_{0, 2})\cdot x.\] 





So we are left only with checking the associativity of the 
action for $k_1, k_2\in \hat{H}_0\cup \hat{H}_1$. There are four 
possibilities, but only the case $k_2\in \hat{H}_1$, 
$k_1\in \hat{H}_0$ requires close inspection. 

Here however we see that for any $h\in X$, $(\zeta, \bar{i})\in H_1$, 
$f\in H_0$, 
\[(((1, \bar{0}, f)(\zeta, \bar{i}, 1))\cdot h)(\xi)=
((\zeta, \bar{i}, \varphi_{(\zeta, \bar{i})}(f))\cdot h)(\xi)\] 
\[ =[(\varphi_{(\zeta, \bar{i})}(f))(\xi/\zeta))
h(\xi/\zeta) 
((\varphi_{({\zeta, \bar{i}})}(f)) 
(\xi e^{2\pi i {\surd 2 } }/\zeta))^{-1}]^{(-1)^i}\]
\[=[(f(\zeta \xi/\zeta))^{(-1)^i}h(\xi/\zeta)(f(\zeta e^{2\pi i {\surd 2 } }
\xi/\zeta ))^{(-1)^{i+1}}]^{(-1)^i}\]
\[=(f(\xi))^{(-1)^{2i}}(h(\xi/\zeta))^{(-1)^i}(f(\xi 
e^{2\pi i {\surd 2 } }))^{(-1)^{2i+1}}\] 
\[= f(\xi)(h(\xi/\zeta))^{(-1)^{i}}(f(\xi e^{2\pi i {\surd 2 } } ))^{-1}\]
\[=f(\xi)(((\zeta, \bar{i}, 0)\cdot h)(\xi))(f(e^{2\pi i {\surd 2 } } \xi))^{-1} 
=((1, \bar{0}, f)\cdot (\zeta, \bar{i}, 1)\cdot h)(\xi)\] 
as required. 
\end{proof} 

The action is clearly continuous, and so $X$ is a Polish $G$-space. 



\begin{notation} 
Let $E^X_G$ denote the orbit equivalence relation 
induced by this action. 
\end{notation}

\begin{notation} From now until the end of the section 
$M_{\infty}$ is used to 
denote $M_{\infty}(\T^2,\lambda^2)$, the 
group of invertible $\lambda^2$ measure preserving functions $\pi:\T^2\rightarrow 
\T^2$, subject to the usual identification in the event of agreement 
almost everywhere. 
\end{notation} 


Thus we are using $M_{\infty}$ to denote a different Polish group to the 
one from section \ref{1}, but since these two are naturally isomorphic the 
identification would seem harmless. 



\begin{notation} For $h\in X$, let $T_h:\T^2\rightarrow \T^2$ be 
given by 
\[(\zeta, \xi)\mapsto (\zeta  e^{2\pi i {\surd 2 } }, \xi h(\zeta)).\] 
\end{notation} 




\begin{lemma} \label{4.11} 
The function $h\mapsto T_h$ is a continuous 
function from $X$ to $M_{\infty}$. 
\end{lemma} 

\begin{proof} In general ``skew products" of this form give rise to measure 
preserving transformations (compare $\S$2 \cite{befo} or chapter 1 of 
\cite{petersen}). The further facts that $T_h$ is invertible and that the 
assignment $h\mapsto T_h$ is continuous follow almost immediately from 
the definitions. 
\end{proof} 




\begin{lemma} \label{4.12} 
Every $G$-orbit in $X$ is dense; in fact, for any $h\in X$ 
\[\{(1, \bar{0}, f)\cdot h| f\in H_0\}\] 
is dense in $X$. 
\end{lemma} 


\begin{proof} Fix $h_0, h_1\in X$ and $\epsilon>0$. 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_{l<n} e^{2l\pi i {\surd 2 } }A)>1-\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 
$l<n$ and $f|_{e^{2l\pi i {\surd 2 } }A}$ has been defined, we let 
\[f(\xi e^{2\pi i {\surd 2 } })=f(\xi) h_0(\xi)(h_1(\xi))^{-1}\] 
for any $\xi\in  e^{2l\pi i {\surd 2 } }A$. 

Finally we have that for all $\xi\in \bigcup_{l<n} e^{2l\pi i {\surd 2 } }A$ 
\[f(\xi)h_0(\xi)(f(\xi e^{2\pi i {\surd 2 } }))^{-1}=h_1(\xi),\] 
and thus 
\[d_X((1, \bar{0}, f)\cdot h_0, h_1)<\epsilon.\] 
\end{proof} 





\begin{notation} Let $\approx$ denote the conjugacy 
equivalence relation on $M_{\infty}$ -- so that for 
$\sigma_1, \sigma_2\in M_{\infty}$ we write $\sigma_1\approx 
\sigma_2$ if there is a $\pi\in M_{\infty}$ such that for a.e. 
$(\zeta, \xi)\in\T^2$ 
\[\pi\circ \sigma_1\circ \pi^{-1}=\sigma_2.\] 
\end{notation}  

\begin{lemma} \label{4.14} 
For all $h_0, h_1\in X$ 
\[h_0 E^X_G h_1 \Rightarrow T_{h_0}\approx T_{h_1}.\] 
\end{lemma} 

\begin{proof} We may break this down into three cases. 

(i) $(\zeta_0, \bar{0}, 1)\cdot h_0=h_1$, so that 
$h_1(\xi)=h_0(\xi/\zeta_0)$ for $\lambda$ a.e. $\xi$. 
Then we may define $\pi:\T^2\rightarrow \T^2$ by 
\[\pi:(\zeta, \xi)\mapsto (\zeta\zeta_0, \xi).\] 
We then have for a.e. $(\zeta, \xi)$ 
\[(\pi \circ T_{h_0}\circ \pi^{-1})(\zeta, \xi)= 
(\pi \circ T_{h_0})(\zeta/\zeta_0, \xi)=(\pi(e^{2\pi i {\surd 2 } }
\zeta/\zeta_0), h_0(\zeta/\zeta_0)\xi)\] 
\[=(e^{2\pi i {\surd 2 } }\zeta, \xi h_1(\zeta))=T_{h_1}(\zeta, \xi).\] 

(ii) $(1, \bar{1}, 1)\cdot h_0=h_1$, so that $h_1(\xi)=(h_0(\xi))^{-1}$ 
a.e. Then define $\pi:\T^2\rightarrow \T^2$ by 
\[(\zeta, \xi)\mapsto (\zeta, \xi^{-1})\] 
and note that 
\[\pi T_{h_0}\pi^{-1}(\zeta, \xi)= \pi(e^{2\pi i {\surd 2 } }
\zeta, h_0(\zeta)/\xi)=(e^{2\pi i {\surd 2 } }
\zeta, (h_0(\zeta))^{-1}\xi)=(e^{2\pi i {\surd 2 } }
\zeta, h_1(\zeta)\xi).\] 

(iii) $(1, \bar{0}, f)\cdot h_0=h_1$, so that 
$f(\zeta)h_0(\zeta)(f(\zeta e^{2\pi i {\surd 2 } }))^{-1}=h_1(\zeta)$ a.e. 
Define  $\pi:\T^2\rightarrow \T^2$ by
\[(\zeta, \xi)\mapsto (\zeta, f(\zeta)\xi).\] 
Note then that 
\[\pi^{-1} T_{h_0}\pi(\zeta, \xi)= 
\pi^{-1}( e^{2\pi i {\surd 2 } }\zeta, h_0(\zeta)f(\zeta) \xi)\]
\[=( e^{2\pi i {\surd 2 } }\zeta, (f(\zeta e^{2\pi i {\surd 2 } }))^{-1}
h_0(\zeta)f(\zeta) \xi)=T_{h_1}(\zeta, \xi).\]  
\end{proof} 
 
\begin{lemma} \label{4.15} The set of $h\in X$ 
for which $T_h$ is ergodic is a dense $G_\delta$. 
\end{lemma} 

\begin{proof} 
Recall (compare $\S2$ \cite{befo}) that ergodicity is a $G_{\delta}$ condition 
on an element of $M_{\infty}$: $\pi\in M_{\infty}$ is ergodic if and only 
if for all 
open $A, B\subseteq \T^2$ arising as finite unions of basic open sets 
there is $m$ with 
\[\lambda(\pi^m(A)\cap B)>1/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 $l<n$; 

\noindent (ii) $d_X(h_{0,l}, h_0)<d_X(h_0, h_1)+\epsilon$ each 
$l\leq n$; 

\noindent (iii) $d_X(h_{0,n}, h_1)<\epsilon$. 

\leftskip 0in 

\noindent We will do this in a manner resembling the proof of \ref{4.12}. 


Choose $n\in\N$ such that $n>3/\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<n$. 
$f_0$ is constantly $1$. Given the definition of $f_l$ we let 
\[f_{l+1}(e^{2\pi i {\surd 2 } }\xi)=f_l(\xi)h_0(\xi) (h_1(\xi))^{-1}\] 
for $\xi\in e^{2l\pi i {\surd 2 } } A$, and 
\[f_{l+1}(e^{2\pi i {\surd 2 } }\xi)=1\] 
otherwise. 
We then let $g_i=(1, \bar{0}, f_i)$. 
We then let $h_{0,0}=h_0$ and $h_{0,l+1}=g_l 
h_{0,l}$ as indicated 
above. 

At once we have (i), since each $f_i$ is not equal to 1 only on a 
set of measure $<\epsilon$. For (ii), note that if $k<n$ then 
$\forall \xi\in\bigcup_{l<k}e^{2l\pi i {\surd 2 } }A$ 
\[h_{0,k}(\xi)=h_1(\xi),\] 
$\forall \xi\in\bigcup_{l> k, l<n}e^{2l\pi i {\surd 2 } }A$ 
\[h_{0,k}(\xi)=h_0(\xi).\]
Thus 
\[d_X(h_{0,k}, h_0)=\int 1/2 |h_{0,k}(\xi)- h_0(\xi)|d\lambda\]
\[<\lambda(e^{2k \pi i \surd{2}}A)+ \lambda(e^{2n \pi i \surd{2}}A) 
+\epsilon/3+\int 1/2 |h_{1}(\xi)- h_0(\xi)|d\lambda\]
\[<\epsilon+d_X(h_0, h_1).\]
Finally for (iii) note that $h_{0,n}$ and $h_1$ agree except on the 
set 
\[\T\setminus \bigcup_{l< n}  e^{2l\pi i {\surd 2 } }A,\] 
which has measure less than $\epsilon$. 
\end{proof} 

Summarizing what has been proved: 


\begin{theorem} \label{4.21} There is a Polish group $G$ and a  
Polish $G$-space $X_0$ and a Borel function $\theta:X_0\rightarrow M_{\infty}$ such 
that: 

\leftskip 0.5in 

\noindent (i) the action of $G$ on $X_0$ is turbulent (\ref{4.20}); 

\noindent (ii) for each $h\in X_0$ the transformation $\theta(h)\in M_{\infty}$ 
is ergodic (\ref{4.15}, \ref{4.17}); 

\noindent (iii) in fact each $\theta(h)$ is ``measure-distal" (in the sense of 
\cite{befo}), and in fact it is rank 2 generalized discrete spectrum (granting (ii), this is an 
immediate consequence of the definition of the assignment $h\mapsto T_h$); 

\noindent (iv) for all $h_0, h_1\in X_0$ 
\[h_0 E^X_G h_1\] 
if and only if 
\[\theta(h_0)\approx \theta(h_1),\] 
where $\approx$ is the equivalence relation of conjugacy (\ref{4.14}, 
\ref{4.17}). 

\leftskip 0in 
\end{theorem} 



\begin{corollary} \label{4.22} 
(a) There is no 
countable language ${\cal L}$ and 
Borel 
\[\rho:M_{\infty}
\rightarrow {\rm   Mod}({\cal L})\] 
such that for all $\sigma_1$, 
$\sigma_2\in M_{\infty}$ 
\[\sigma_1\approx \sigma_2\Leftrightarrow \rho(\sigma_1)
\cong \rho(\sigma_2).\] 

(b) In fact, if $B\subseteq  M_{\infty}$ is the subclass 
consisting of rank 2 generalized 
discrete spectrum ergodic transformations 
then 
there is no Borel  
\[\rho: B
\rightarrow {\rm  Mod}({\cal L})\] 
such that for all $\sigma_1$,
$\sigma_2\in M_{\infty}$
\[\sigma_1\approx \sigma_2\Leftrightarrow \rho(\sigma_1)
\cong \rho(\sigma_2).\]
\end{corollary} 

\begin{proof} At once by the results of $\S$3.2, \cite{hjorth}. 
\end{proof} 





In actual fact there is no compulsion to restrict ourselves so 
carefully to the Borel category. The methods of \cite{hjorth} are 
sufficient to obtain non-reducibility to isomorphism on 
countable structures even using very broad classes of functions, 
such as $C$-measurable, absolutely $\Ubf{\Delta}^1_2$, 
and universally Baire measurable. As mentioned in the introduction, 
we may even obtain the consistency of ZF+DC along with the 
non-existence of {\it any} injection 
\[i:P/\!\approx\:\:\hookrightarrow \: {\rm Mod}({\cal L}).\] 

\newpage 





\section{Remarks on the equivalence of cocycles} 

\label{5} 


There is obviously a close relation between the arguments of 
$\S$\ref{4} and the isomorphism relation on cocycles. It might be worth 
pausing before the finish of this paper to consider what can be drawn 
out in this fashion. 


\begin{definition} Let $(\Omega, \B, \mu)$ be a probability  
space and $H$ a countable group 
acting by measure preserving transformations on $\Omega$. 
For later purposes assume that $\Omega$ is a Lebesgue space 
(that is to say measurably isomorphic to $([0,1],$ Borel$, 
\lambda)$). 
Let $K$ be a 
compact metric group. 
A map measurable 
\[\alpha:H\times \Omega\rightarrow K\] 
is a {\it cocycle} if for all $h, h'\in H$ and $s\in \Omega$ 
\[\alpha(hh', s)=\alpha(h, h's)\alpha(h',s).\] 
(Here the measurability requirement is that 
for all $h\in H$ we have $s\mapsto \alpha(s, h)$ measurable.) 
\end{definition} 



In the case that $H=\Z$ the cocycle condition becomes especially 
transparent, since we can exactly specify a cocyle by its value 
on a generator of $\Z$. 
Hence we can naturally identify a cocycle for $\Z$ with a measurable 
function from the space $\Omega$ to $K$. 


The perspective of \cite{zimmer2} is to only consider the 
case that $K$ is a compact metric group; the remarks below persist in some 
form    
even in the more general context that $K$ is a locally 
compact Polish 
group with an invariant two sided metric. 
If $d_K$ is a compatible complete metric on a compact metric group 
$K$ then we obtain an invariant metric with 
$d_{K,{\rm{inv}}}(g_0,g_1)$ set equal to 
\[\int_{K\times K} d_K(h_0g_0 h_1, h_0g_1h_1)   
\mu_K\times\mu_K.\] 


\begin{definition} 
Let $(\Omega, \B, \mu)$, $K$, $H$ be as above. 
Two cocycles \[\alpha,\beta:H\times \Omega\rightarrow K\] 
are said to be {\it equivalent} if there is a measurable function  
\[\varphi:\Omega\rightarrow K\]  
such that for every $h\in H$ and a.e. every $s\in \Omega$ 
\[\varphi(h\cdot s)^{-1} \alpha(h,s) \varphi(s)=\beta(h, s).\] 
\end{definition} 


Note -- as exploited in $\S$\ref{4} -- this equivalence relation is induced by 
a Polish group action. 



\begin{notation} Let $(\Omega, \B, \mu)$, $K$, $H$, be as above. 
Let $d_K$  be an invariant metric on $K$;  
by possibly replacing it with $d_K/(1+d_K)$ we may 
assume it is bounded by 1. 
Let $X(\Omega, K,H,\mu)$ be the space of all cocycles from $H\times\Omega$ to 
$K$. Let $G(\Omega, K, H,\mu)$ be the group of all measurable 
\[\varphi:\Omega\rightarrow K\] 
under the operation of pointwise multiplication. 
We let  $G(\Omega, K, H,\mu)$ act on $X(\Omega, K,H,\mu)$ by the specification 
that 
\[(\varphi\cdot\alpha)(h,s)= \varphi(h\cdot s)^{-1}\alpha(h,s)\varphi(s).\] 
For $\alpha\in  X(\Omega, K,H,\mu)$ use  $G(\Omega, K, H,\mu)_{\alpha}$ to denote 
the {\it stabilizer of $\alpha$} -- that is to say the set of 
$\varphi$ for which 
\[\varphi\cdot \alpha=\alpha.\] 
\end{notation} 


The action of  $G(\Omega, K, H,\mu)$ on  $X(\Omega, K,H,\mu)$ is exactly chosen 
so that the resulting orbit equivalence relation is the cocycle equivalence 
relation.  $G(\Omega, K, H,\mu)$ and  $X(\Omega, K,H,\mu)$ are Polish spaces, 
and $X(\Omega, K,H,\mu)$ is a Polish  $G(\Omega, K, H,\mu)$-space.  
For the group we obtain a complete and in fact invariant metric by 
\[d_{G(\Omega, K, H,\mu)}(\varphi_0,\varphi_1)=\int_{\Omega} d_K(\varphi_0(s), 
\varphi_1(s))d\mu.\] 
For the cocycles we can choose an enumeration $(h_i)_{i\in\N}$ of $H$ and let 
\[d_{X(\Omega, K,H,\mu)}(\alpha, \beta)=\sum_{i\in\N}2^{-i}\int_{\Omega} 
d_K(\alpha(h_i, s), \beta(h_i,s))d\mu.\] 

A special case of the above is when $H=\Z$, $\Omega=\T$, 
$K=\T$, 
and the action of $\Z$ on $\T$ is given by 
\[l\cdot \zeta=e^{2l\pi i {\surd 2 } } \zeta.\] 
Clearly the arguments of $\S$\ref{4} are sufficient to obtain that in this 
case -- and in many others -- the action of 
$G(\Omega, K, H,\mu)$ on  $X(\Omega, K,H,\mu)$ is turbulent. In showing 
conditions (i) and (iii) from the definitions of turbulence for 
$G$ we only used the $G(\Omega, K, H,\mu)$ part in \ref{4.12} and \ref{4.20}. 
Clearly the property of every orbit being meager goes down to this 
sub-action by $G(\Omega, K, H,\mu)$. 
Thus in general the cocycle equivalence relation 
refuses classification by countable models. 

In the presence of ergodicity, the 
stabilizers are all compact. 


\begin{lemma}\label{5.4} Let $(\Omega, \B, \mu)$, $K$, $H$ be as 
above. Suppose that the action of $H$ on $\Omega$ is ergodic. 

Then for every $\alpha\in X(\Omega, K,H,\mu)$ we have that 
$G(\Omega, K, H,\mu)_{\alpha}$ is compact. 
\end{lemma} 

\begin{proof} $G(\Omega, K, H,\mu)_\alpha$ is a 
complete metric space, so we just 
need to show that it is $\epsilon$-bounded for each $\epsilon$. 

Let $(\varphi_i)_{i\in\N}$ be a countable dense subset 
of $G(\Omega, K, H,\mu)_{\alpha}$. 
Using the fact that $K$ is a compact metric space we may find 
a finite sequence of balls $B_0,B_1,...B_n$ of radius $<\epsilon/3$ 
covering $K$. For each $i_0, i_1\in\N, j\leq n$ let $A_{i_0, i_1,j}
=\{s\in\Omega: 
\varphi_{i_0}(s), \varphi_{i_1}(s)\in B_j\}$.  
Let $\a$ be the {\it countable}  collection 
$\{A_{i_0,i_1, j}: i_0, i_1\in \N, j\leq n\}$. 
We may clearly find 
$s_0\in \Omega$ such that for all $A\in \a$, if $s_0\in A$ 
then $A$ is not null. 


Now we may choose a finite collection $\varphi_{l_0}, \varphi_{l_1},...,
\varphi_{l_k}$ from our sequence  $(\varphi_i)_{i\in\N}$ such that 
for any $j\leq n$, if there exists $i\in\N$ with 
$\varphi_i(s_0)\in B_j$ then there is some $i'\leq k$ with 
$\varphi_{l_{i'}}(s_0)\in B_j$. 

Claim. If $\varphi_i(s_0)\in B_j$ and $\varphi_{l_{i'}}(s_0)\in B_j$ 
then for a.e. $s\in\Omega$, 
\[d_K(\varphi_i(s), \varphi_{l_{i'}}(s))\leq 2\epsilon/3.\] 

Proof of claim: Let $A=\{s\in \Omega: d_K(\varphi_i(s), 
\varphi_{l_{i'}}(s))\leq 2\epsilon/3\}$. 
By assumption on $s_0$ this set $A$ has non-zero measure. 
By ergodicity it suffices to show $A$ is $H$-invariant. 

But for any $h\in H$ and $s\in A$  
\[\alpha (h, s) 
= (\varphi_i \cdot 
\alpha )(h,s)
= \varphi_i(h\cdot s)^{-1} \alpha(h, s)\varphi_i(s)\] 
\[\therefore 
\varphi_i(h\cdot s)=\alpha(h, s)\varphi_i(s) 
\alpha(h, s)^{-1} ,\] 
and similarly 
\[\varphi_{l_{i'}}(h\cdot s)=\alpha(h, s)\varphi_{l_{i'}}(s)
\alpha(h, s)^{-1}.\]  
Thus by the invariance of the metric 
$d_K(\varphi_i(h\cdot s),
\varphi_{l_{i'}}(h\cdot s))\leq 2\epsilon/3$. \hfill (Claim$\Box$) 

But then it is immediate from the definition of the complete  
metric on $G(\Omega, K, H,\mu)$ and the density of the 
set $(\varphi_i)_{i\in\N}$ that every element in 
$G(\Omega, K, H,\mu)_{\alpha}$ is within $\epsilon$ of some 
$\varphi_{l_{i'}}$. 
\end{proof} 



Thus for any two cocycles $\alpha$ and $\beta$ the 
set of $\varphi\in G(\Omega, K, H,\mu)$ with 
\[\varphi\cdot \alpha=\beta\] 
is either empty or compact. Therefore the set 
\[\{(\alpha, \beta)\in X(\Omega, K,H,\mu)^2:\exists 
\varphi\in G(\Omega, K, H,\mu)(\varphi\cdot \alpha=\beta)\}\] 
is the projection of a Borel set 
all of whose sections are 
compact, and is, by the Arsenin-Kunugui theorem 
(see $\S$18 \cite{kechrisclassical} and
$\S$4F \cite{moschovakis}), itself Borel. 

We consequently have a short proof of the equivalence 
relation being Borel for ergodic actions. I believe a much deeper proof 
of this 
fact  
has been previously extracted by Foreman and Weiss from the results of 
\cite{zimmer2}. 

Lemma \ref{5.4} should {\it not} be thought of as implying that the measure 
preserving transformations considered in $\S$\ref{4} themselves have 
compact stabilizers in the natural action of $M_\infty$ (= group of 
invertible measure preserving transformations on the unit interval) on $M_\infty$. 
In fact the ergodic transformations having compact stabilizer in $M_\infty$ are 
exactly the discrete spectrum transformations. 

\begin{lemma} 
\label{5.5} Let $ T\in M_\infty$ be ergodic. Then the set 
\[\{\pi\in M_\infty: \pi\circ T \circ \pi^{-1}= T\}\] 
is compact if and only if $T$ is a discrete spectrum transformation. 
\end{lemma} 

\begin{proof} 
First let us take the case that $T$ is discrete spectrum. Then 
by \cite{hane} we can assume that there is a compact abelian  
metric group $G$ with a Haar measure $\mu$ and corresponding $g\in G$ 
with 
\[\{n\cdot g: n\in\Z\}\] 
dense in $G$ and $T$ as a measure preserving transformation on 
$[0,1]$ isomorphic to translation of $(G, \mu)$ by $g$. 
For each $k\in G$ let  
\[T_k:G\rightarrow G\] 
\[h\mapsto kh\] 
be the transformation given by $k$-translation. 
Let 
$M_\infty(G)$ be the group of invertible measure preserving 
transformation on $(G, \mu)$. Since the assignment 
\[G\rightarrow M_\infty(G)\] 
\[k\mapsto T_k\]
is continuous we 
need only show 
\[\{\pi\in M_\infty(G): \pi\circ T_g \circ \pi^{-1}=T_g\}\]
equals $\{T_k: k\in G\}$. 

It is clear that 
the compact group of measure preserving transformations 
\[\{T_k: k\in G\}\] 
is included in $\{\pi\in M_\infty(G): 
\pi\circ T_g \circ \pi^{-1}=T_g\}$, so let us fix $\pi$ with 
$\pi\circ T_g \circ \pi^{-1}=T_g$ a.e. 
To each $x\in G$ let $h_x\in G$ be such that 
\[h_x x=\pi(x).\] 
We then  have 
\[h_{x}(T_gx)=h_x(gx)\] 
by definition of $T_g$, which in turn equals 
\[gh_x x\] 
by $G$ abelian, which now equals 
\[g\pi(x)=T_g\pi(x)=(T_g\circ \pi)(x),\] 
which by assumption on $\pi$ equals 
\[(\pi\circ T_g)(x)=\pi(T_g(x))\] 
on a measure one set; and 
thus the function 
\[x\mapsto h_x\] 
is a $T_g$-invariant function 
on a measure one set, and 
hence by ergodicity constant 
almost everywhere. Hence $\pi=T_{h_x}$ for some 
$x\in G$ on a measure one set, and we are done. 

\smallskip 

Conversely, if 
\[\{\pi\in M_\infty: \pi\circ T \circ \pi^{-1}= T\}\] 
is compact, then we have that $T$ is an element of a 
compact subgroup of $M_\infty$. Thus by the 
Peter-Weyl theorem, as for instance found in \cite{zimmer}, 
we may find a sequence of finite 
dimensional subspaces 
\[H_0, \:\: H_1, \:\: H_2, \cdots\] 
of $L^2([0,1], \lambda)$ which are invariant under the 
unitary operator $f\mapsto f\circ T$ 
and which jointly sum up to give 
\[L^2([0,1], \lambda =\bigoplus_n H_n.\] 
Then diagonalizing this unitary on each of these finite 
dimensional subspaces we finish. 
\end{proof} 






\bigskip 






\newpage 

\begin{thebibliography}{99}

\bibitem{beckerkechris} H. Becker and A.S. Kechris, {\bf The descriptive set theory of 
Polish group actions}, London Mathematical Society Lecture Notes Series, Cambridge, 1996. 

\bibitem{befo} F. Beleznay, M. Foreman, {\it The complexity of the collection of 
measure distal transformations,} {\bf The Journal of Ergodic Theory and 
Dynamical Systems,} 
vol. 16(1996), pp. 929-962.

\bibitem{effros} E. Effros, {\it Transformation groups and $C^*$-algebras,}
{\bf Annals of Mathematics,} ser 2, vol. 81(1975), pp. 38-55.

%\bibitem{frst} H. Friedman, L. Stanley, {\it A Borel reducibility theory for %classes %of 
%countable structures}, {\bf Journal of Symbolic Logic,} vol. 54(1989), pp, 894-914.  

\bibitem{feldman} J. Feldman, {\it Borel structure and invariants for 
measurable transformations,} {\bf Proceedings of the American Mathematical 
Society,} vol. 46(1974), pp. 383-394. 

\bibitem{frst} H. Friedman, L. Stanley, {\it A Borel reducibility theory for classes of 
structures, } {\bf Journal of Symbolic Logic,} vol. 54(1989), pp. 894-914. 

\bibitem{furstenberg} H. Furstenberg, {\bf Recurrence in ergodic theory and 
combinatorial number theory,} Princeton University Press, Princeton, 1981. 

\bibitem{ha1} P.R. Halmos, {\it Measurable transformations,} {\bf Bulletin of the 
American Mathematical Society,} vol. 55(1949), pp. 1015-34. 

\bibitem{ha2} P.R. Halmos, {\it Recent progress of ergodic theory,} {\bf Bulletin of the 
American Mathematical Society,} vol. 67(1961), pp. 70-80. 


\bibitem{hane} P.R. Halmos, J. von Neumann, {\it Operator methods in classical 
mechanics II,} {\bf Annals of Mathematics,} vol. 43(1942), pp. 332-50. 

\bibitem{hakelo} L.A. Harrington, A.S. Kechris, A. Louveau, {\it A Glimm-Effros dichotomy for 
Borel equivalence relations,} {\bf Journal of the American Mathematical Society,} 
vol. 3(1990), pp. 903-928. 

\bibitem{hewittross} E. Hewitt, K.A. Ross, {\bf Abstract harmonic analysis,} 
Grundlehren der mathematischen wissenschaft 115, Springer-Verlag, New York, 1979. 

\bibitem{hjorth} G. Hjorth, {\bf Classification 
and orbit equivalence relations,} Mathematical 
Surveys and Monographs, volume 75,  
American Mathematical Society, Providence, RI, 2000. 


\bibitem{hjorthkechris} G. Hjorth, A.S. Kechris, {\it Borel equivalence relations and
classifications by countable models}, {\bf Annals of Pure and Applied Logic,}
vol. 82(1996), pp. 221-272.


%\bibitem{hjso} G. Hjorth, S. Solecki, {\it The Glimm-Effros property and 
%Vaught's conjecture,} to appear in the {\bf Transactions of the American Mathematical 
%Society.} 

\bibitem{hodges} W. Hodges, {\bf Model theory,} Cambridge University Press, 
Cambridges, 1993. 


%\bibitem{kechris3} A.S. Kechris, {\it The structure of Borel equivalence relations in 
%Polish spaces,}, {\bf Set theory of the continuum,} (eds, H. Judah, W. Just, 
%W.H. Woodin) MSRI Publication 26, Springer-Verlag, 
%New-York, 1990, pp. 75-84.

%\bibitem{kechriscountable} A.S. Kechris, {\it Countable sections for locally compact %group actions,} 
%{\bf Journal of Egrodic Theory and Dynamical Systems,} vol. 12(1992), pp. 283-95. 

\bibitem{kechrisclassical} A.S. Kechris, {\bf Classical descriptive set theory}, 
Springer-Verlag Graduate Texts in Mathematics, Berlin, 1995. 

%\bibitem{kechrisdefinable} A.S. Kechris, {\bf Definable equivalence relations and %Polish group 
%actions}, unpublished manuscript. 

%\bibitem{kechrislouveau} A.S. Kechris, A. Louveau, {\it The classification of 
%hypersmooth Borel equivalence relations,} to appear in the {\bf Journal of the American 
%Mathematical Society}. 

\bibitem{morris} S.A. Morris, {\bf Pontryagin duality and the structure 
of  locally compact abelian groups,} 
LMS Lecture Notes Series, 29, Cambridge University Press, Cambrdige, 1977. 

\bibitem{moschovakis} Y.N. Moschovakis, {\bf Descriptive set theory,} 
North-Holland Press, Amsterdam, 1980. 


\bibitem{ornstein} D.S. Ornstein, {\it Two Bernoulli shifts with the same 
entropy are isomorphic,} {\bf Advances in Mathematics,} vol. 4(1970), pp. 337-352. 

\bibitem{ornsteinshields} D.S. Ornstein, P.C. Shields, {\it An uncountable family 
of $K$-automorphisms,} {\bf Advances in Mathematics,} vol. 10(1973), pp. 63-88. 

\bibitem{petersen} K. Petersen, {\bf Ergodic theory,} Cambridge University 
Press, Cambridge, 1983. 

\bibitem{sosr} S. Solecki, S.M. Srivastava, {\it Automatic continuity of group
operations,} {\bf Topology and its Applications} vol. 77(1997), pp. 65-75. 

\bibitem{solovay} R.M. Solovay, {\it A model of set theory in which every set of 
reals is Lebesgue measurable,} {\bf Annals of Mathematics,} vol. 71(1970). pp. 1-56. 

\bibitem{we} B. Weiss, {\it The isomorphism problem in ergodic theory,} 
{\bf Bulletin of the American Mathematical Society,} vol. 78(1972), pp. 668-84. 

\bibitem{zimmer2} R.J. Zimmer, {\it Ergodic actions with 
generalized discrete spectrum,} {\bf Illinois Journal of Mathematics,} 
vol. 20(1976), pp. 373-409. 

\bibitem{zimmer} R.J. Zimmer, {\bf Essential results of functional analysis}, 
University of Chicago Press, 1990, Chicago.



\end{thebibliography}

6363 MSB

Mathematics

UCLA

CA90095-1555

greg@math.ucla.edu

www.math.ucla.edu/\~{}greg 


\end{document}


