% 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.15in}
% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
\setlength{\textwidth}{6.5in}
% Set top margin - The default is 1 inch, so the following
% command sets a 0.75-inch top margin.
\setlength{\topmargin}{-0.1in}
% Set height of the header
\setlength{\headheight}{0.3in}
% Set height of the text
\setlength{\textheight}{8.1in}
% Set vertical distance between the text and the
% bottom of footer
\setlength{\footskip}{0.8in}
% Set the beginning of a LaTeX document
\begin{document}
%\large
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{subclaim}[theorem]{Subclaim}
\newtheorem{fact}[theorem]{Fact}
\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{notation}[1][Notation]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{question}[1][Question]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\V{{\mathbb V}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\K{{\mathbb K}}
\def\B{{\mathbb B}}
\def\F{{\mathbb F}}
\def\P{{\mathbb P}}
\def\T{{\mathbb T}}
\def\o{{\omega}}
\def\oo{{\omega^{\omega}}}
\def\lo{{\omega^{<\omega}}}
\def\d{{\dot{\bigcup}}}
\def\h{{\cal H}}
\def\no{\noindent}
\def\a{{\mathcal A}}
\def\b{{\mathcal B}}
\def\c{{\mathcal C}}
\def\l{{\mathcal L}}
\def\n{{\mathcal N}}
\def\m{{\mathcal M}}
\def\p{{\mathcal P}}
\def\h{{\mathcal H}}
\def\u{{\mathcal U}}
\def\co{{\mathcal O}}
\def\t{{\mathcal T}}
\def\c{{\mathcal C}}
\def\nh{|\! |}
\def\no{\noindent}
\title{\huge A converse to Dye's theorem\footnote{{\it Key words and phrases:}
Ergodic theory, treeable equivalence relations, non-amenable groups,
property $T$ groups, free groups, Borel reducibility.
{\it AMS Subject Classification:} 03E15, 28D15, 37A15.} }
\author{Greg Hjorth\footnote{Partially supported by
NSF grant DMS 01-40503.}} % Enter your name between curly braces
\date{\empty} % Enter your date or \today between curly braces
\maketitle
\abstract{Every
non-amenable countable group induces orbit inequivalent
ergodic equivalence relations on standard Borel
probability spaces. Not every free, ergodic,
measure preserving action of
$\F_2$ on a standard Borel probability space
is orbit equivalent to an action of a countable group on an inverse
limit of finite spaces.
There is a treeable non-hyperfinite Borel equivalence
relation which is not universal for treeable in the $\leq_B$
ordering.}
%\tableofcontents
\section{Introduction}
\label{introduction}
We show a converse to a consequence of
the final strengthening of Dye's theorem
proved by Ornstein and Weiss.
\begin{definition} An equivalence relation $E$
is said to be {\it standard} if it is
defined on a standard Borel probability space $(X, \b, \mu)$, it
is Borel as a subset of $X\times X$, and all its
equivalence classes are countable. It is said to be
{\it measure preserving} if for any measurable $A, B\subset X$
and for any measurable bijection $\varphi: A\rightarrow B$ included in the
graph of $E$ ($xE \varphi(x)$ all $x$) we have $\mu(A)=\mu(B)$.
It is {\it ergodic} if any $E$-invariant set is either
null or conull.
Two such equivalence relations, $E$ on $(X, \b, \mu)$, $F$ on $(Y, \c,
\nu)$, are
said to be {\it orbit equivalent} if there is a measure preserving bijection
\[\psi: X\rightarrow Y\]
such that almost everywhere we have
\[x_1 E x_2 \Leftrightarrow \psi(x_1) F \psi(x_2).\]
An equivalence relation $E$ on
a standard Borel probability space
$(X, \b, \mu)$ is said to be {\it induced}
by a countable group $G$ if there is a Borel, measure preserving, ergodic, and
almost everywhere free action of $G$ on $X$ such that $E$ equals
the corresponding equivalence relation $E_G$. Any such $E_G$ will
necessarily be standard,
measure preserving, and ergodic.
\end{definition}
\begin{theorem} (Dye; see \cite{dye}, \cite{dye2}.) Any two ergodic,
standard, measure preserving equivalence relations
induced by $\Z$ are orbit equivalent.
\end{theorem}
\begin{theorem} (Ornstein, Weiss; see \cite{ornsteinweiss},
\cite{cofewe}.) If $G$ is a countably infinite
amenable group, then
any two ergodic, standard, measure preserving equivalence relations
induced by $G$ are orbit equivalent.
\end{theorem}
\begin{theorem} \label{asym}
(Connes, Weiss; Schmidt; see
\cite{connesweiss}, \cite{schmidt}.)
If $G$ is countable, non-amenable and without property
$T$, then there are at least two orbit inequivalent ergodic, standard, measure
preserving equivalence relations induced by actions of $G$.
\end{theorem}
Below:
\begin{theorem} If $G$ is countably infinite with property $T$, then there are
continuum many orbit inequivalent ergodic, standard, measure preserving
equivalence relations induced by actions of $G$.
\end{theorem}
\begin{corollary} A countable group is amenable if and only if it induces
only one orbit equivalence relation considered up to orbit equivalence.
\end{corollary}
The argument, which answers a question raised by Schmidt at
3.10 of \cite{schmidt2},
was inspired by certain constructions from
\cite{popa}.
We also consider another structural consequence of
Dye's work, who in the course of the proof of his theorem
provided a normal
form for the orbit equivalence relations induced by groups such as $\Z$.
Any measurable equivalence relation induced by $\Z$ can be represented as
an orbit equivalence relation arising by a kind of inverse limit of actions
of $\Z$ on finite spaces. While it is unreasonable to hope that the specifics
of Dye's construction, with $\Z$ acting by the {\it odometer map} as in
\cite{dye}, could provide a canonical model for non-amenable equivalence
relations, it does seem to have been open whether arbitrary measure preserving
standard ergodic $E$ may allow themselves to be presented as arising
from this kind of inverse limit of actions on finite spaces.
We formalize the notion of {\it modular} in section 3 to capture this
idea, and go onto show that in general $\F_2$ can induce measurable
equivalence
relations which are not modular in this sense.
It turns that the mixing properties of the Bernoulli shift of $\F_2$ on
$2^{\F_2}$, in direct contrast to the Bernoulli shifts of amenable groups,
are somehow ``remembered" at the level of orbit equivalence, and do not
allow themselves to be modeled by a modular equivalence relation.
This argument turns out to give information
in the context of Borel reducibility. In answer to a
question of Jackson, Kechris, and Louveau:
\begin{theorem} There is a countable treeable Borel equivalence relation
which is not hyperfinite and does not Borel reduce every other
countable treeable Borel equivalence relation.
\end{theorem}
Here we say that $E$ {\it Borel reduces} $F$ if there is a Borel function
between their respective fields with $x_1 E x_2$ if and only if $\theta(x_1) F
\theta (x_2)$; roughly speaking, the quotient space from
$E$ Borel injects into the quotient space from $F$.
We say that an equivalence relation is {\it hyperfinite}
if it can be written as the increasing union of Borel equivalence relations
with finite classes; equivalently, see \cite{jakelo}, that it is induced by a
Borel action of $\Z$. We say that $E$ is {\it treeable} if there is an acyclic
Borel graph on its field whose connected components form the $E$-equivalence
classes; equivalently, there is a collection of
partial Borel bijections which generate $E$ and allow no non-trivial loops.
\bigskip
\noindent{\bf Acknowledgments:} I am grateful to
John Clemens, Damien
Gaboriau, Alexander Kechris, and Simon Thomas for helpful remarks about
earlier drafts of this paper and pointing out various errors. With
kind permission many of their comments have been included in the revised
version. I am also grateful to Sergey Bezuglyi for his help with
the references.
\section{Orbit equivalence relations induced by Kazhdan groups}
\label{proof}
\begin{notation}
We generally write $U(\h)$, or $U_\infty(\h)$ when we know $\h$ to be
infinite dimensional, for the group of unitary transformations of a
Hilbert space $\h$.
\end{notation}
\begin{definition} Let
\[\pi: G\rightarrow U(\h)\]
\[g\mapsto \pi_g\]
be a unitary
representation of a group $G$.
This representation is said to have
{\it almost invariant unit vectors} if for all $\epsilon >0$
and $F\subset G$ finite there is some $\zeta\in \h$ with $\nh h\nh =1$
and $\nh \zeta - \pi_g(\zeta)\nh<\epsilon$ all $g\in F$.
\end{definition}
\begin{definition}
A discrete group $G$ is said to be
{\it Kazhdan} or to {\it have property T} if any unitary representation
$\pi: G\rightarrow U(\h)$ with almost invariant unit vectors has an
outright invariant unit vector -- that is to say, some $\zeta\in \h$ with
$\nh \zeta \nh =1$ and
\[\pi_g(\zeta)=\zeta\]
all $g\in G$.
\end{definition}
Possible references for the subject of Kazhdan groups are given
by \cite{harpevalette} and \cite{zimmer}. We mention
two apparent strengthenings of the definition which
in fact turn out to be equivalent. In both cases the proofs are
routine and can be left as exercises for the reader.
\begin{proposition} $G$ has property T if and only if there is some
finite $F\subset G$ and $\epsilon>0$ such that whenever $\pi:
G\rightarrow U(\h)$
is a unitary representation with some $\zeta\in \h$ having $\nh
\pi_g(\zeta) - \zeta\nh <\epsilon$
all $g\in F$ then $\pi$ has an invariant unit vector.
\end{proposition}
\begin{proposition} $G$ has property T if and only if for all $\delta>0$
there is some
finite $F\subset G$ and $\epsilon>0$ such that whenever $\pi:
G\rightarrow U(\h)$
is a unitary representation with some $\zeta\in \h$ having $\nh
\pi_g(\zeta) - \zeta\nh <\epsilon$
all $g\in F$ then $\pi$ has an invariant unit vector $\eta$ with $\nh
\eta -\zeta\nh<\delta$.
\end{proposition}
One natural example of a Kazhdan group is the collection of three by
three integer coefficient
matrices with determinant one. More generally, at every $n\geq 3$ the
group $SL_n(\Z)$ is
Kazhdan.
In say chapter 7 of \cite{zimmer} one can find an extended discussion of
theorems to the effect that certain kinds of discrete subgroups of certain
kinds of Lie groups will, under the appropriate conditions, be Kazhdan.
As with
Kazhdan's original proof for $SL_3(\Z)$, the proofs are analytical in flavor,
turning on the topological properties of the ambient Lie group. More recently
Andre Zuk in
\cite{zuk} has obtained purely combinatorial proofs that certain discrete
groups
have property T. Indeed he even shows that in some suitably statistical sense
most finitely generated groups in an indicated class are Kazhdan.
In this section we prove that all countably infinite Kazhdan groups have
continuum many free, ergodic, measure preserving actions on
standard Borel spaces up to orbit equivalence. This theorem was previously
known from \cite{geftergolodets} for certain special classes of property
T groups;
for instance it was known for $SL_3(\Z)$. The first proof that there is
at least
{\it some} countable group with continuum many actions can be found in
\cite{bezuglyigolodets}, which built on work by McDuff in the theory of
operator
algebras.
Our proof is more elementary than these previous arguments.
\begin{definition}
Let $E$ be a standard, measure preserving equivalence relation on
$(X, \b, \mu)$ and let $G$ be a countable group.
We then set $\c(E, G)$ to be the collection of all measurable
\[\alpha: E\rightarrow G\]
such that almost everywhere
\leftskip 0.4in
\noindent (i) if $y\in [x]_E$ then $\alpha(y, x)=1_G$ if and only if $y=x$;
\noindent (ii) if $y, z\in [x]_E$, then $\alpha(z, y)\alpha(y,x)=
\alpha(z, x)$;
\noindent (iii) for all $g\in G$ there exists $y\in [x]_E$ with
$\alpha(y, x)=g$.
\leftskip 0in
We identify $\alpha_1, \alpha_2\in \c(E, G)$ if they agree almost everywhere.
\end{definition}
\begin{remark}
We can think of $\c(E, G)$ as the space of possible ways to arrange a
free action
and measurable action of $G$ on $X$ with $E_G=E$.
In the case that $\Gamma$ induces $E$, we can identify $\c(E, G)$ with the
cocycles from $X\times \Gamma\rightarrow G$ which are appropriately
``one-to-one"
and ``onto".
\end{remark}
\begin{definition} From now on fix an enumeration $(g_n)_{n\in\N}$ of
the group $G$. For $E$ as above, and
$\alpha, \beta\in \c(E, G)$ we let
\[d_E(\alpha, \beta)=\sum_{n\in\N} 2^{-n} \mu(\{x:
\exists y(\alpha(y, x)=g_n, \beta(y, x)\neq g_n)\} \bigcup
\{x:
\exists y(\beta(y, x)=g_n, \alpha(y, x)\neq g_n)\}).\]
%The definition of $\c(E, G)$ implies that almost everywhere
%$\exists ! y \alpha(y, x)=g_n$, and hence that $d_E(\alpha,\beta)=d_E(\beta, \alpha)$.
$\c(E, G)$ equipped with this metric becomes a separable, complete
metric space. We will not need the completeness of the metric, but the
separability plays a starring role.
\begin{fact} For $E$ and $G$ as above, $\c(E, G)$ has a countable dense
subset.
\end{fact}
\begin{proof} Let us consider $\c_0(E, G)$, the set of measurable
\[\alpha: E\rightarrow G\]
with $|\{y: \alpha(y, x)=g\}|< 2$ for all $g\in G$, a.e. $x\in X$.
Since $\c(E, G)$ is included in $\c_0(E, G)$ and the metric for the first
extends to a metric for the second, it will suffice to find
a countable dense subset of $\c_0(E, G)$.
For this purpose, let $(f_n)_{n\in\N}$ be a sequence of measurable injections
with $(f_n(x))_{n\in\N}$ enumerating $[x]_E$ almost everywhere. Let
$\b_0\subset \b$ be a countable Boolean subalgebra which is dense with
respect to the measure algebra, in the sense that for all $B\in \b$,
$\epsilon > 0$, there is some $B_0\in \b_0$ with $\mu(B\Delta B_0)<\epsilon$.
Then consider the collection of all $\alpha\in \c_0(E, G)$ satisfying:
\leftskip 0.4in
\noindent (i) for each $g$, the set of $n$ with $\mu(\{x: \alpha(f_n(x),
x)=g\})\neq 0$ is
finite;
\noindent (ii) for each $g, n$, the set $\{x: \alpha(f_n(x), x)=g\}$ is
in $\b_0$;
\noindent (iii) for all sufficiently large $n$, $\{x: \alpha(f_n(x),
x)=g_n\}=X$.
\leftskip 0in
\noindent The countability and density of this collection are routinely
verified.
\end{proof}
Note that the metric $d_E$ depends on the choice of the enumeration
$(g_n)_{n\in\N}$
of $G$. In the observations which follow we will want to consider a
single countable
group
$G$ in relation to various choices of $E$. We will think of a countable group
as coming with some fixed choice of an enumeration $(g_n)_{n\in\N}$, and
in each
case use $d_E$ to refer to the metric which arises on $\c(E, G)$ for that
predetermined choice; we will not specifically mention the enumeration.
\end{definition}
\begin{definition} (Compare \cite{cofewe}.) For $E$ a standard, measure
preserving
equivalence relation on $(X, {\mathcal B}, \mu)$,
let $p_1, p_2: E\rightarrow X$
be the projections onto the first and second coordinates.
We then define a measure $m$ on $E$ by
\[m(B)=\int_X |p^{-1}_1[\{x\}]\cap B|d\mu(x).\]
Since $E$ is measure preserving, we could as well have used the projection
$p_2$ in place of $p_1$ and obtained the same measure.
We then let $\u(E)$ be the collection of all unitary operators on the Hilbert
space $L^2(E, m)$ of square integrable $f: E\rightarrow \C$.
Given $\alpha, \beta\in \c(E, G)$ we define a unitary
representation
\[\pi^{\alpha, \beta}: G\rightarrow \u(E),\]
\[g\mapsto \pi^{\alpha, \beta}_g\]
by
\[(\pi^{\alpha, \beta}_g(f))(x', y')=f(x, y)\]
where $x', y'$ are defined by the specification that
\[\alpha(x', x)=g,\]
\[\beta(y', y)=g.\]
\end{definition}
In other words, if we use $\alpha$ and $\beta$ in the obvious way to
obtain actions
\[a_\alpha: G\times X\rightarrow X,\]
\[a_\beta: G\times X\rightarrow X,\]
and we take the induced measure preserving transformation
\[a_\alpha\times a_\beta: G\times E\rightarrow E\]
given by
\[(a_\alpha\times a_\beta)(g, (x, y))=(a_\alpha(g, x), a_\beta(g, y)),\]
then in the usual manner we produce a representation of $G$ in
$\u(E)$.
\begin{notation} In what follows, $\chi_\Delta: E\rightarrow \{0, 1\}$ is the
characteristic function of the diagonal; so that $\chi_\Delta(x, y)=1$ if
$x=y$
and 0 if $x\neq y$.
\end{notation}
\begin{fact} \label{fact}
Let $G$ be a countably infinite group.
For all $\epsilon>0$ and finite $F\subset G$, there exists a
$\delta>0$ such that for all standard, measure preserving $E$, all
$\alpha, \beta
\in \c(E, G)$, if $d_E(\alpha, \beta)<\delta$, then
\[\forall g\in F(\nh \pi_g^{\alpha, \beta}
(\chi_\Delta) -\chi_\Delta\nh <\epsilon),\]
where $\nh \cdot \nh$ refers to the Hilbert space norm on $L^2(E, m)$.
\end{fact}
\hfill ($\square$)
\begin{lemma} Let $G$ be a countably infinite group with property T.
Then there is a $\delta>0$ such that for all ergodic, standard, measure
preserving $E$ on $(X, \b, \mu)$ and all $\alpha, \beta\in \c(E, G)$ with
\[d_E(\alpha, \beta)<\delta,\]
there is a measurable bijection $\varphi: X\rightarrow X,$ $\varphi\subset E$,
such that for the induced actions
\[a_\alpha: G\times X\rightarrow X,\]
\[a_\beta: G\times X\rightarrow X,\]
we have
\[a_\alpha(g, x)=\varphi^{-1}(a_\beta(g, \varphi(x)))\]
almost everywhere.
\end{lemma}
\begin{proof} Since $G$ has $T$, we may find $\epsilon>0$ and finite
$F\subset G$
such that whenever $\pi:G\rightarrow U_\infty(\h)$ is a unitary representation
and $\eta\in\h$ is a unit vector with
\[\forall g\in F (\nh \pi_g(\eta) -\eta\nh <\epsilon),\]
then there is a unit vector $\eta_0\in \h$ which is $G$-invariant and has
\[\nh \eta -\eta_0\nh <10^{-2}.\]
For this $F\subset G$ and $\epsilon>0$ we choose $\delta>0$ as \ref{fact}.
We then consider $E$ as above, $\alpha, \beta\in \c(E, G)$ with
$d_E(\alpha, \beta)<\delta$. By the assumption on $\delta, \epsilon, F$, we
may find $G$-invariant $f\in L^2(E, m)$ with
\[\nh \chi_\Delta - f\nh <10^{-2}.\]
Consider then the set
\[A_f=\{x\in X|\exists ! y\in [x]_E(|f(x, y)-1|<\frac{1}{4})\}.\]
Since $f$ is close to $\chi_\Delta$, $A_f$ is non-null. But then by ergodicity
of action $a_\alpha: G\times X\rightarrow X$ we must have $A_f$ co-null.
$G$-invariance of $f$ amounts to the assertion that for almost all
$(x, y)\in E$ and all $g\in G$
\[f(x, y)=f(a_\alpha(g, x), a_\beta(g, x)).\]
Thus if we define $\varphi: A_f\rightarrow X$ by
$\varphi(x)=y$ if and only if $|f(x, y)-1|<\frac{1}{4}$ then this equation
implies
\[\varphi(x)=y\Leftrightarrow \varphi(a_\alpha(g, x))=a_\beta(g, y),\]
which in turn gives
\[a_\alpha(g, x)=\varphi^{-1}(a_\beta(g, \varphi(x)))\]
almost everywhere.
\end{proof}
\begin{corollary} \label{2.4}
If $E$ is an ergodic,
standard, measure preserving, equivalence
relation on $(X, \b, \mu)$ and
$G$ is a property $T$ group,
then up to isomorphism\footnote{Here we say that
two actions of $G$ are {\it isomorphic} if they are simultaneously conjugate:
That is to say, $a, b: G\times X\rightarrow X$ are {\it isomorphic} actions if
there is measure preserving $\varphi: X\cong X$ with
$\varphi(a(g, \varphi^{-1}(x)))= b(g, x)$ almost everywhere.} there are
at most
$\aleph_0$ many free
actions of $G$ by measurable transformations on $X$ which induce $E$.
\end{corollary}
\begin{proof} We may identify such actions with elements of
$\c(E, G)$. The last
lemma asserts that the equivalence relation of isomorphism of
action is open in
$\c(E, G)$, and so the corollary follows from the separability of this space.
\end{proof}
\begin{corollary} If $G$ is a countably infinite property $T$ group, then it
induces $2^{\aleph_0}$ many orbit inequivalent ergodic,
standard, measure preserving,
equivalence relations.
\end{corollary}
\begin{proof} Since the group $G$ is not abelian-by-finite, and hence
not type I (see \cite{thoma}), we may find
\[\pi_\gamma: G\rightarrow U_\infty(\h_\gamma),\]
${\gamma\in 2^{\aleph_0}}$, non-conjugate infinite
dimensional irreducible unitary representations of $G$.
Following \cite{zimmer} 5.2.13, we may find corresponding ergodic
actions of $G$ on standard Borel probability spaces
$(X_\gamma, \b_\gamma, \mu_\gamma)$,
with each induced representation $\sigma_\gamma: G\rightarrow
U_\infty(L^2(X_\gamma, \mu_\gamma))$
having $\h_\gamma$ as a direct summand. The product of
an ergodic action of an infinite
group with a mixing action is still ergodic, so after
possibly taking the product of this
action with the Bernoulli shift, of $G$ acting on $\{0, 1\}^G$,
we may assume that
each action is free.
Then each induced representation
$\sigma_\gamma: G\rightarrow U_\infty(L^2(X_\gamma, \mu_\gamma))$ has only
countably many irreducible representations as direct summands, and
is therefore only
isomorphic as a unitary representation to countably many other
$\sigma_\kappa$'s; in
particular the original measure preserving action from which it derives
is only
isomorphic to countably many others.
Thus by \ref{2.4} each such $E_{\sigma_\gamma}$ is orbit equivalent to at most
countably many other such $E_{\sigma_\alpha}$'s.
\end{proof}
\section{Non-modular equivalence relations induced by $\F_2$}
In this section we formulate the notion of a modular equivalence
relation, and show that in general
the free actions of $\F_2$ may induce non modular actions.
The argument gives information in the context of Borel
reducibility, and thus in answer to question
6.4(A) from \cite{jakelo}, we obtain in the following
section a treeable countable Borel
equivalence relation which is neither universal
treeable nor hyperfinite.
Very recently Damien Gaboriau and Sorin Popa have shown that any non-abelian
free group gives rise to continuum many non-orbit equivalent free actions.
As far as can be determined, their argument does not appear to provide insight
at the level of $\leq_B$-reducibility, and it remains open whether
$\F_2$, or any $\F_n$
($n=2, 3,..., \aleph_0$) has more than two non-hyperfinite free Borel actions
up to Borel reducibility.
There is a fair amount in way of prefatory lemmas and definitions.
We need to distinguish the highly mixing actions of say the
Bernoulli shift from those actions which have generating sets
for the Borel algebra with finite orbit. We make that distinction by
assigning to each measurable set in $2^{\F_2}
=_{\rm df} \{0, 1\}^{\F_2}$ a {\it center}, cradled between those elements
of $\F_2$ which are most important for its definition. The
various prefatory lemmas are required for that
definition and to formulize the manner in which this center is
rapidly mixed by the equivalence relation.
We think of $\F_2=\langle a, b\rangle$ as having $a$ and $b$ as
generators.
\begin{definition} A {\it weight} for $\F_2$ is a function
\[w: \F_2\rightarrow \R\]
such that $w(\sigma)\geq 0$ all $\sigma\in \F_2$, $w$ is non-zero
at some point, and
$w\in \ell^1(\F_2)$.
An element $\sigma_0$ is a {\it center} for some such weight
$w$ if each
\[\sum\{w(\tau x\sigma_0): \tau \in \F_2, \tau x \mbox{ is a reduced
word}\},\]
as $x$ ranges over $\{a, a^{-1}, b, b^{-1}\}$, is less than
\[\frac{1}{2}\sum\{w(\tau): \tau\in \F_2\}.\]
$\sigma_0$ is a {\it weak center} if each such
\[\sum\{w(\tau x\sigma_0): \tau x \mbox{ is a reduced word}\}
< \frac{2}{3}\sum\{w(\tau): \tau\in \F_2\}.\]
\end{definition}
\begin{lemma} \label{I} Every weight has
at least one center.
\end{lemma}
\begin{proof} We begin with some $e\in \F_2$, and if that is
a center we are content.
Otherwise there will be some $x_0\in \{a, a^{-1}, b, b^{-1}\}$ with most
of the weight
lying on reduced words of the form $\tau x_0$ and so we shift our attention
to $x_0$. And again if $x_0$ is a center we are done, and otherwise
we pass onto some $x_1$ with most of the weight lying on
words of the form $\tau x_1 x_0$. Since the majority of the weight
lies within some definite distance from the identity, this
process must terminate after considering finitely many
$x_i$'s.
\end{proof}
\begin{notation}
We let $\F_2$ act on $\ell^1(\F_2)$ by right multiplication:
\[\tau\cdot f(\sigma) =f(\sigma\tau).\]
\end{notation}
\begin{lemma} \label{II} $\sigma_0$ is a center for
a weight $w$ if and only if $\sigma_0\tau^{-1}$ is a
center for $\tau\cdot w$;
$\sigma_0$ is a weak center for
a weight $w$ if and only if $\sigma_0\tau^{-1}$ is a
weak center for $\tau\cdot w$.
\end{lemma}
\begin{proof}
Immediate from the structure of the definitions.
\end{proof}
Note then that the centers of a
weight and the weak
centers of a weight form a finite subset of
$\F_2$ which is convex when viewed as being included
in the Cayley graph.
In fact they are not just convex but linear; this is
the key combinatorial fact.
\begin{lemma}
\label{III}
If $w$ is a weight, then its collection of weak centers is linearly
ordered; that is to say, there are $x_0, x_1,..., x_n$, with
$x_0\in \F_2$, each $x_{i+1}\in \{a, a^{-1}, b, b^{-1}\}$, such
that each $x_ix_{i-1}...x_0$ forms a reduced word and
\[\{x_ix_{i-1}...x_0: i\leq n\}\]
enumerates the weak centers.
\end{lemma}
\begin{proof}
Assume instead that there is some $\sigma_0\in \F_2$ such that
$a\sigma_0, a^{-1}\sigma_0, b\sigma_0$ are all weak centers.
(Without any real loss of generality we can assume that this
is the case; the other possibilities are entirely similar.)
Then for $c\in \{a, a^{-1}\}$ we have for $x=c^{-1}$ that
\[\sum\{w(\tau x c \sigma_0): \tau x \mbox{ is a reduced
word}\}< \frac{2}{3} \nh w \nh _{\ell^1}\]
\[\therefore \sum\{w(\tau c \sigma_0): \tau c \mbox{ is a reduced
word}\} > \frac{1}{3} \nh w \nh _{\ell^1}.\]
For $y=b^{-1}$ we have
\[\{\tau_0 y b\sigma_0: \tau_0 y \mbox{ reduced}\}
\supset \{\tau_1 a\sigma_0: \tau_1 a \mbox{ reduced}\}
\cup
\{\tau_2 a^{-1}\sigma_0: \tau_2 a^{-1} \mbox{ reduced}\}\]
\[\therefore\sum\{w(\tau y b \sigma_0): \tau y \mbox{ is a reduced
word}\}> \frac{2}{3} \nh w \nh _{\ell^1},\]
with a slur on $b\sigma_0$'s claim of weak centerhood.
\end{proof}
\def\tf{2^{\F_2}}
\begin{notation} We let $2^{\F_2}=_{\rm df}\{0,1\}^{\F_2}$ be the
collection of functions from $\F_2$ to $\{0, 1\}$; we equip this with the
product measure and let $\F_2$ act by multiplication on the right: For
$f\in 2^{\F_2}$, $\sigma, \tau\in \F_2$
\[\tau\cdot f(\sigma)=f(\sigma\tau).\]
This in turn induces an action on $L^2(\tf)$ in the usual way: Given
\[\psi: \tf\rightarrow \C\]
we define $\tau\cdot \psi$ by the formulation
\[\tau\cdot \psi(f) =\psi(\tau^{-1}\cdot f).\]
For $S\subset \F_2$ finite we define a corresponding function
\[\psi_S: \tf\rightarrow \{-1, 1\}\]
\[f\mapsto (-1)^{|\{\sigma\in S: f(\sigma)=1\}|}.\]
Thus if $f$ assumes the value 1 on an odd number of elements of $S$ then
$\psi_S(f)=-1$; otherwise it takes the value 1.
\end{notation}
It is well known that $\{\psi_S: S\subset \F_2$ is finite$\}$ forms an
orthonormal basis. One can for instance determine by hand that they are
orthogonal and then by Stone-Weierstrass check that their linear
combinations are dense, and hence that they span.
Note that $\psi_\emptyset: f\mapsto 1$ is the constant function with
value 1. $\psi\in L^2(2^{\F_2})$ will be orthogonal to the
constant functions if and only if it is in the subspace given by the
closed span of $\{\psi_S: S\neq \emptyset\}$.
\def\f{{\mathcal F}}
\begin{notation} Let $\f(\F_2)=\{S\subset \F_2: S$ is finite$\}$.
\end{notation}
$\f(\F_2)$ is a countable set, and we can thus form $\ell^2(\f(\F_2))$ in
the usual way. This Hilbert space is of course naturally isomorphic to
$L^2(\tf)$ and we introduce some notation to describe that isomorphism.
\begin{notation} Let
\[\Delta: L^2(\tf)\rightarrow \ell^2(\f(\F_2))\]
be the linear isometry induced by the association
\[\psi_S\mapsto \delta_{S},\]
where $\delta_{S}(T)=1$ if $T=S$, $=0$ if $T\neq S$.
\end{notation}
From here we wish to convert the elements of $\ell^2(\f(\F_2))$ into
weights. Of course now there is no question of a linear isomorphism;
instead we ask only for a process of conversion which is
Lipschitz on the unit sphere. We begin by mapping $\ell^2(\f(\F_2))$ into
the positive part of $\ell^1(\f(\F_2))$.
\begin{notation} We define
\[E: \ell^2(\f(\F_2))\rightarrow \ell^1(\f(\F_2))\]
by
\[E(\phi)(s)=|\phi(s)|^2.\]
\end{notation}
Note that $\nh E(\phi)\nh_{\ell^1}=\nh \phi\nh_{L^2}^2$.
\begin{lemma} \label{page3}
For $\phi_1, \phi_2\in \ell^2(\f(\F_2))$
\[\nh E(\phi_1) - E(\phi_2)\nh_{\ell^1}
\leq (\nh \phi_1\nh_{\ell^2} + \nh \phi_2\nh_{\ell^2} )
\nh \phi_1 - \phi_2\nh_{\ell^2}.\]
\end{lemma}
\begin{proof}
\[\nh E(\phi_1) - E(\phi_2)\nh_{\ell^1}=\sum_{s\in \f(\F_2)}
|E(\phi_1)(s)-E(\phi_2)(s)|\]
\[=\sum_{s\in \f(\F_2)} |\phi_1(s)^2-\phi_2(s)^2|=
\sum_{s\in \f(\F_2)} |\phi_1(s)[\phi_1(s)-\phi_2(s)]
+\phi_2(s)[\phi_1(s)-\phi_2(s)]|\]
\[\leq \sum_{s\in \f(\F_2)} |\phi_1(s)|\cdot|\phi_1(s)-\phi_2(s)|
+ \sum_{s\in \f(\F_2)} |\phi_2(s)|\cdot |\phi_1(s)-\phi_2(s)|\]
\[=\langle |\phi_1|, |\phi_1-\phi_2|\rangle +\langle |\phi_2|,
|\phi_1-\phi_2|\rangle
\leq \nh \phi_1\nh_{\ell^2} \nh \phi_1- \phi_2\nh_{\ell^2} +
\nh \phi_2\nh_{\ell^2} \nh \phi_1- \phi_2\nh_{\ell^2},\]
by Cauchy-Schwarz.
\end{proof}
\begin{notation} We define
\[\Sigma: \ell^1(\f(\F_2))\rightarrow \ell^1(\F_2)\]
by
\[\Sigma(\phi)(\sigma) = \sum_{S\in\f(\F_2), \sigma\in S} |S|^{-1}\phi(S).\]
$\Sigma$ is a linear contraction, and for $\phi$ positive, say in the range
of $E$, of unit length, and with $\phi(\emptyset)=0$,
we have that $\Sigma(\phi)$ is a weight with $\nh \Sigma(\phi)\nh_{\ell^1}
=\nh \phi\nh_{\ell^1}$.
We then let
\[\pi=\Sigma E \Delta: L^2(\tf)\rightarrow \ell^1(\F_2),\]
\[\varphi\mapsto \Sigma(E(\Delta(\varphi))).\]
\end{notation}
\begin{notation} For $S\subset \F_2$ finite and $\tau\in \F_2$ we let
\[\tau\cdot S = \{\sigma\tau^{-1}: \sigma\in S\};\]
thus
\[\sigma\in S\Leftrightarrow \sigma\tau^{-1}\in \tau\cdot S,\]
\[\therefore \sigma\tau\in S\Leftrightarrow \sigma\in \tau\cdot S.\]
Then for $f\in \ell^2(\f(\F_2))\cup \ell^1(\f(\F_2))$ and $\tau\in \F_2$
we define $\tau\cdot f\in \ell^2(\f(\F_2))\cup \ell^1(\f(\F_2))$
by
\[\tau\cdot f(S)=f(\tau^{-1}\cdot S);\]
thus if $f=\delta_{S_0}$ then
\[\tau\cdot f(S)=1 \mbox { iff } \tau^{-1}\cdot S = S_0\]
\[\mbox{ iff } S=\tau\cdot S_0;\]
and thus $\tau\cdot \delta_{S_0}= \delta_{\tau\cdot S_0}.$
\end{notation}
\begin{lemma} \label{IV} \empty
(o) For $\varphi\in L^2(2^{\F_2})$ orthogonal to the constant
functions and of norm one,
$\nh \pi(\varphi)\nh_{\ell^1} =1$.
(i) $\nh \pi(\varphi_1) -\pi(\varphi_2)\nh_{\ell^1} \leq
(\nh\varphi_1\nh_{L^2} + \nh\varphi_2\nh_{L^2})
\nh \varphi_1-\varphi_2\nh_{L^2}$.
(ii) $\pi$ is an $\F_2$-map, in the sense that for $\sigma\in \F_2$ and
$\varphi\in L^2(\tf)$
\[\pi(\sigma\cdot \varphi) = \sigma\cdot \pi(\varphi).\]
(iii) For $\varphi$ not a.e. constant, $\pi(\varphi)$ is a weight.
(iv) For such $\varphi$ and $\sigma\in \F_2$,
$\sigma_0$ is a center of $\pi(\varphi)$ if and only if
$\sigma_0\sigma^{-1}$ is a center of $\pi(\sigma\cdot \varphi)$;
$\sigma_0$ is a weak center of $\pi(\varphi)$ if and only if
$\sigma_0\sigma^{-1}$ is a weak center of $\pi(\sigma\cdot \varphi)$.
(v) For $\varphi_1, \varphi_2$ unit
vectors in $L^2(\tf)$ orthogonal to the
constant functions with
$\nh \varphi_1-\varphi_2\nh_{L^2} < \frac{1}{12}$, and
$\sigma_0$ a center of $\pi(\varphi_1)$, we will necessarily have
$\sigma_0$ a weak center of $\pi(\varphi_2)$.
\end{lemma}
\begin{proof} (o) and (i) follow from the various facts recorded above
regarding $E$, $\Delta$, and $\Sigma$.
(ii): We first observe:
\smallskip
\noindent{\bf Claim:} $\Delta: L^2(\tf)\rightarrow \ell^2(\f(\F_2))$ is an
$\F_2$-map.
\smallskip
\noindent{\bf Proof of claim:}
It suffices to check this for the basis elements, of the form $\psi_S$. So let
$\tau\in \F_2$, $S\subset\F_2$ finite, $f\in\tf$.
\[\tau\cdot \psi_S(f)=\psi_S(\tau^{-1}\cdot f)
=(-1)^{|\{\sigma\in S: \tau^{-1}\cdot f(\sigma)=1\}|}\]
\[=(-1)^{|\{\sigma\in S: f(\sigma\tau^{-1})=1\}|}
=(-1)^{|\{\sigma\tau\in S: f(\sigma)=1\}|}
=(-1)^{|\{\sigma\in \tau\cdot S: f(\sigma)=1\}|}\]
\[=\psi_{\tau\cdot S}(f).\]
Thus $\Delta(\tau\cdot \psi_S)=\Delta(\psi_{\tau\cdot S})=\delta_{\tau\cdot S}
=\tau\cdot \delta_{S} =\tau\cdot\Delta(\psi_S).$
\hfill (Claim$\square$)
\smallskip
It is immediate that $E$ is an $\F_2$-map, and as for $\Sigma$ we have
\[(\Sigma(\tau\cdot f))(\sigma) =\sum_{\sigma\in S}|S|^{-1}\tau\cdot f(S)
=\sum_{\sigma\in S} |S|^{-1}\cdot f(\tau^{-1}\cdot S)\]
\[=\sum_{\sigma\in \tau\cdot S} |S|^{-1}f(S)
=\sum_{\sigma\tau\in S}|S|^{-1}f(S) =(\Sigma(f))(\sigma\tau)
=(\tau\cdot \Sigma(f))(\sigma).\]
(iii) This is obvious from the definitions and \ref{page3}.
(iv) We have for any $x\in \{a, a^{-1}, b, b^{-1}\}$ that
\[\sum\{\pi(\sigma\cdot \varphi)(\tau x \sigma_0 \sigma^{-1}):
\tau x \mbox{ is a reduced word} \}=
\sum\{\sigma\cdot\pi(\varphi)(\tau x \sigma_0 \sigma^{-1}):
\tau x \mbox{ is a reduced word} \}\]
by (ii) above,
\[=\sum\{\pi(\varphi)(\tau x \sigma_0): \tau x \mbox { is a reduced word}\},\]
by the definition of the action.
(v) If $\nh \varphi_1\nh_{L^2}, \nh \varphi_2\nh_{L^2} =1$,
$\varphi_1, \varphi_2\perp \C 1$, and
\[\nh \varphi_1-\varphi_2\nh_{L^2} < \frac{1}{12} \]
then using (0), (i) we have
\[\nh \pi(\varphi_1)-\pi(\varphi_2)\nh_{\ell^1} <
\frac{1}{6} {\rm min}\{\nh\pi(\varphi_1)\nh_{\ell^1},
\nh\pi(\varphi_2)\nh_{\ell^1}\}=\frac{1}{6}.\]
Thus for each $\sigma_0\in \F_2$, $x\in \{a, a^{-1}, b, b^{-1}\}$
\[|\sum\{\pi(\varphi_1)(\tau x \sigma_0): \tau x \mbox { reduced }\}
-\sum\{\pi(\varphi_2)(\tau x \sigma_0): \tau x \mbox { reduced }\}|\]
is bounded by $\frac{1}{6}\nh\pi(\varphi_2)\nh_{\ell^1}$,
so that if
\[\sum\{\pi(\varphi_1)(\tau x \sigma_0): \tau x \mbox { reduced }\}
<\frac{1}{2}\nh\pi(\varphi_1)\nh_{\ell^1}=
\frac{1}{2}\nh\pi(\varphi_2)\nh_{\ell^1}\]
then
\[\sum\{\pi(\varphi_2)(\tau x \sigma_0): \tau x \mbox { reduced }\}
<\frac{1}{2}\nh\pi(\varphi_2)\nh_{\ell^1} +
\frac{1}{6}\nh\pi(\varphi_2)\nh_{\ell^1}
= \frac{4}{6} \nh\pi(\varphi_2)\nh_{\ell^1} = \frac{2}{3}
\nh\pi(\varphi_2)\nh_{\ell^1}.\]
\end{proof}
\begin{definition} An equivalence relation $E$ on a standard Borel space
$(X, \b)$ has
{\it modular type} if there is a countable
group $G$ acting by Borel automorphisms on $X$ with
$E=E_G$ and there is an increasing sequence of finite Boolean algebras
\[\b_0\subset\b_1\subset\b_2\subset...\subset\b_n\subset\b_{n+1}\subset...\b,\]
such that $G$'s action permutes each $\b_n$ and $\b$ is generated
as a $\sigma$-algebra by
\[\bigcup_{n\in\N} \b_n.\]
In particular then we have $X, \emptyset\in \b_0$ and if $A$ is an atom in
some $\b_n$ and $g\in G$, then $g\cdot A$ is still an atom in $\b_n$.
\end{definition}
\begin{example} Consider the space $2^{\N}=_{\rm df}\{f|f: \N\rightarrow
\{0, 1\}\}$,
equipped with the metric $d(f_1, f_2)=2^{-n(f_1,f_2)}$, where $n(f_1,
f_2)$ is the least
$n$ with $f_1(n)\neq f_2(n)$. Suppose, as in the examples constructed by
Ted Slaman and John Steel, \cite{slamansteel}, we have an action of $\F_2$
by isometries on this space relative to this metric: That is to say, for
all $f_1, f_2
\in 2^\N$ and $\sigma\in \F_2$ we have $d(f_1, f_2)=d(\sigma\cdot f_1,
\sigma\cdot f_2)$.
Then for each $s\in 2^{<\N}$ a finite binary sequence, we let
\[V_s=\{f\in 2^\N: f\supset s\}.\]
Taking $\b_n=\{V_s: {\rm length}(s)\leq n\}$ we have witnesses to modularity.
We will in future refer to this space with this action as $X_{ss}$.
\end{example}
Alexander Kechris has suggested a different way of thinking about these
classes of examples. If we order the atoms of the various $\b_n$'s under
inclusion,
thereby obtaining a tree structure, then we can identify the space
with a subset of the infinite branches, and view the group
as acting by isomorphisms.
In this way modular actions can be identified with actions by automorphisms of
a rooted tree.
In the next theorem we equip $2^{\F_2}=_{\rm df} \{0, 1\}^{\F_2}$
with the product measure, $\mu$, and the shift action on the
right: $(\tau\cdot f)(\sigma)=f(\sigma\tau)$. We let $E_{\F_2}$
denote this equivalence relation.
\begin{theorem}
\label{main}
Let $E$ be of modular type on $(X, \b)$ and $M\subset \tf$ of full measure.
Then there is no countable to one measurable
\[\theta: M\rightarrow X\]
such that for all $f_1, f_2\in \tf$
\[f_1 E_{\F_2} f_2\Rightarrow \theta(f_1) E \theta(f_2).\]
\end{theorem}
\begin{proof}
Note first of all that we may assume that on some positive measure set
$M_0\subset M $ we have that $\theta|_{M_0}$ is one to one. There are
various ways
to see this: One approach is to appeal to the uniformization theorem for
subsets
of the plane with countable sections, and argue that $\theta[M]$ is Borel and
admits a Borel right inverse $\rho: \theta[M]\rightarrow M$; the image of
$\rho$ has conull saturation, and hence positive measure; since
$\theta\circ \rho(y)=y$ all $y\in$ Dom$(\rho)$ we can simply take the image of
$\rho$ as our positive set.
For the time being I wish to make a drastic simplifying assumption:
$\theta$ is injective
{\it everywhere}. This will ease some of the notation, and we can return
to the further
problems faced in the general case after having seen the main ideas. In
actual fact
it will turn out that the general argument is only slightly more involved
and requires
only minor regearing.
Let $G$ be a countable group acting by Borel automorphisms with $E=E_G$,
$\b_0\subset\b_1\subset...\subset\b_n\subset\b_{n+1}\subset...\b$ with
$\bigcup\b_n$
generating $\b$ and each $\b_n$ a finite $G$-invariant algebra. We let
$A(\b_n)$
denote the atoms of the algebra $\b_n$.
For $B\in\b$ we let
\[\hat{B}=\theta^{-1}[B].\]
We can then define $\hat{\b}$ to be $\{\hat{B}: B\in \b\}$,
$\hat{\b_n}=\{\hat{B}: B\in \b_n\}$, and $A(\hat{\b_n})$ to be the
atoms of $\hat{\b_n}$. Note that off of a measure zero set we still
have $\hat{\b}$ generating the Borel algebra of $\tf$. (See 15.2 of
\cite{kechris}. This is the place where we are using $\theta$ injective.)
For $x\in\{a, a^{-1}, b, b^{-1}\}, f\in \tf$, let $g_{f, x}\in G$ be
such that
\[g_{f, x}\cdot \theta(f)=\theta(x\cdot f).\]
Note that this assignment $f\mapsto g_{f, x}$ can be
chosen to be measurable, for any such
$x$.
\smallskip
\noindent {\bf Claim(I):} $\forall x\in\{a, a^{-1}, b, b^{-1}\} \forall
\epsilon > 0 \exists M\subset \tf\exists n\in \N$ such that $\mu(M)>
1-\epsilon$
and $\forall \hat{B}\in A(\hat{\b_n})\forall f_1, f_2\in \hat{B}\cap M$
\[g_{f_1, x}=g_{f_2, x};\]
in other words, the function $f\mapsto g_{f, x}$ depends only on which
$\hat{B}\in A(\hat{\b_n})$ the point $f$ resides.
\smallskip
\noindent{\bf Proof of Claim:} One approach is to fix $F\subset G$ finite
such that off of a set of measure less than $\epsilon/ 2$ we have each
$g_{f, x}\in F$; we then go on and let $(M_g)_{g\in F}$ be such that
for all $f\in M_g$
\[g_{f, x}=g\]
and $\mu(\bigcup_{g\in F} M_g)>1-\epsilon/ 2$. Since $\bigcup\hat{\b}_n$
generates $\hat{\b}$ as a $\sigma$-algebra, we have that
$\bigcup_{n\in\N}\hat{\b}_n$
is dense in the measure algebra. Thus for each $g\in \F$ we may choose
$n_g\in\N$ and $\hat{B}_g\in\hat{\b}_{n_g}$ with
\[\mu(\hat{B}_g\Delta M_g)<\frac{\epsilon}{2|F|}.\]
Thus taking
\[n={\rm max}\{n_g: g\in F\}\]
and
\[M=(\bigcup_{g\in F} M_g)\setminus (\bigcup_{g\in F}\hat{B}_g\Delta M_g)\]
we are done.
\hfill (Claim$\square$)
\smallskip
Applying this last claim repeatedly we may produce sets
$N_2\subset N_1\subset \tf$,
$n\in \N$, and
\[g: A(\hat{\b_n})\times \{a, a^{-1}, b, b^{-1}\}\rightarrow G,\]
\[(\hat{B}, x)\mapsto g_{\hat{B}, x},\]
such that
\leftskip 0.4in
\no (i) for all $\tau\in \F_2$ with\footnote{We
write $d(\tau_0, \tau_1)$ to indicate the distance of $\tau_0$ from
$\tau_1$ in the Cayley graph; thus $d(\tau, e)\leq 3$ indicates that
$\tau$ can be written as a word in $\{a, a^{-1}, b, b^{-1},e\}$ of
length at most 3.}
$d(\tau, e)\leq 3$
and
all $f\in N_2$ we have $\tau\cdot f\in N_1$;
\no (ii) $\mu(N_2) > 1 - (10^{-9})$;
\no (iii) if $\hat{B}\in A(\hat{\b_n})$, $f\in \hat{B}\cap N_1,$
$x\in \{a, a^{-1}, b, b^{-1}\}$, then
\[g_{\hat{B}, x}=g_{f, x}.\]
\leftskip 0in
\smallskip
We may further assume that $\mu(\hat{B})<10^{-8}$ all
$\hat{B}\in A(\hat{\b}_n)$.
\smallskip
\def\ahbn{A(\hat{\b_n})}
\def\abhn{\ahbn}
\def\abn{A(\b_n)}
\no {\bf Claim(II):} If $x\in \{a, a^{-1}, b, b^{-1}\}$,
$B_1, B_2\in \abn$, and $x\cdot [\hat{B_1}\cap N_1]\cap \hat{B}_2\cap
N_1\neq 0$,
then
\leftskip 0.4in
\no (i) $x\cdot [\hat{B_1}\cap N_1]\subset \hat{B}_2$;
\no (ii) $x^{-1}\cdot [\hat{B_2}\cap N_1]\subset \hat{B_1}$;
\no (iii) $x\cdot [\hat{B_1}]\supset \hat{B_2}\cap N_1$.
\leftskip 0in
\smallskip
\no {\bf Proof of Claim:}
\smallskip
\no (i): Choose $f_0\in \hat{B}_1\cap N_1\cap x^{-1}\cdot [\hat{B_2}]$.
Then $g_{f_0, x}=g_{\hat{B_1}, x}$, and since
\[g_{\hat{B_1}, x}\cdot \theta(f_0)=\theta(x\cdot f_0)\in B_2\]
and since $G$ permutes $\abn$ we have $g_{\hat{B_1}, x}\cdot B_1=B_2$.
And thus for all $f\in \hat{B_1}\cap N_1$ we have
\[\theta(x\cdot f)=g_{f, x}\cdot \theta(f)=g_{\hat{B_1}, x}\cdot
\theta(f)\in B_2,\]
\[\therefore x\cdot f\in \hat{B_2}.\]
\smallskip
\no (ii): Choose $f_0\in \hat{B_1}\cap N_1\cap x^{-1}\cdot [\hat{B_2}\cap
N_1]$.
Letting $f_1=x\cdot f_0$ we have
\[f_1\in \hat{B_2}\cap N_1,\]
\[x^{-1}\cdot f_1\in \hat{B_1},\]
and we finish by applying (i) but with $x^{-1}$ taking the place of $x$ and
$\hat{B_1}$ and $\hat{B_2}$ exchanging roles we are done.
\smallskip
\no (iii): If $f_0\in \hat{B_2}\cap N_1$, then $x^{-1}\cdot f_0\in \hat{B_1}$
by (ii).
\hfill (Claim$\square$)
\smallskip
\begin{definition} Let us say that $\hat{B}\in \ahbn$ is {\it good} if
\[\frac{\mu(\hat{B}\setminus N_2)}{\mu(\hat{B})}< 10^{-4};\]
if it is not good then we say it is {\it bad}.
\end{definition}
\smallskip
It follows from $\mu(N_2)>1-(10^{-9})$ that
\[\mu(\bigcup \{\hat{B}\in \abhn: \hat{B} \mbox{ is bad}\}
\cup (\tf \setminus N_2)< 10^{-4}.\]
The remainder of the proof has the following overarching form.
The last claim more or less states that $\F_2$ comes close to
permuting the good elements of $\ahbn$. But then if we look at the
centers associated to the characteristic functions of the
good elements of $\abhn$ we obtain a set which is overly
$\F_2$-invariant, and a contradiction ensues.
Let
\[N_3=\{f\in \tf : \forall \tau\in \F_2(d(\tau, e)\leq 3
\Rightarrow \tau\cdot f\in N_2\setminus \bigcup\{\hat{B}\in \abhn: \hat{B}
\mbox{ bad}\})\}.\]
Note that $\mu(N_3)>1-(4\times 3\times 3\times 10^{-4})> 1- 10^{-2}.$
\smallskip
\no {\bf Claim(III):} If $f_0\in N_3\cap \hat{B_1}, \tau\in \F_2,
d(\tau, e)\leq 3, \tau\cdot f_0\in \hat{B}_2$, then
\[\frac{\mu(\hat{B_1})}{\mu(\hat{B_2})}\in
(\frac{10^4-1}{10^4}, \frac{10^4}{10^4-1})\]
and
\[ \mu(\tau\cdot\hat{B_1}\Delta \hat{B_2})< 4\cdot 10^{-4}{\rm min}
\{\mu(\hat{B_1}), \mu(\hat{B_2})\}.\]
\smallskip
\no {\bf Proof of Claim:}
Let us suppose $\tau=x_0x_1x_2$, each $x_i\in \{a, a^{-1}, b, b^{-1}\}$;
let us fix
$\hat{C_1}, \hat{C_2}\in \abhn$ containing $x_2\cdot f$ and $x_1x_2\cdot
f$. Then
by (iii) of the last claim, $x_2\cdot \hat{B_1}\supset \hat{C_1}\cap N_1$,
$x_1\cdot \hat{C_1}\supset \hat{C_2}\cap N_1$,
and $x_0\hat{C_2}\supset \hat{B_2}\cap N_1$. But for any $f'\in
\hat{B_2}\cap N_2$
we have
\[\tau^{-1}\cdot f'= x_2^{-1}x_1^{-1}x_0^{-1}\cdot f',
x_1^{-1}x_0^{-1}\cdot f', x_0^{-1}\cdot f'\in N_1;\]
tracking backwards we obtain $x_0^{-1}\cdot f'\in \hat{C_2}\cap N_1$,
$x_1^{-1}x_0^{-1}\cdot f'\in \hat{C_1}\cap N_1$, and finally
$\tau^{-1}\cdot f'\in \hat{B_1}$.
And thus, bearing in mind that $\tau\cdot f\in \hat{B}_2$
implying $\hat{B}_2$ good, we in general obtain
\[\tau\cdot[\hat{B_1}]\supset \hat{B_2}\cap N_2\]
\[\therefore(\mu(\hat{B}_2\setminus (\tau\cdot \hat{B}_1))<
10^{-4}\mu(\hat{B}_2)\]
\[\therefore \mu(\hat{B}_2)-\mu(\hat{B}_1)=
\mu(\hat{B}_2)-\mu(\tau\cdot\hat{B}_1)
<10^{-4}\mu(\hat{B_2}).\]
Similar reasoning implies $\tau^{-1}\cdot[\hat{B_2}]\supset \hat{B_1}\cap
N_2$,
\[\therefore \hat{B_2}\supset \tau\cdot [\hat{B_1}\cap N_2]\]
\[\therefore \mu((\tau\cdot\hat{B_1})\setminus \hat{B_2}) < 10^{-4}
\mu(\hat{B_1}).\]
And then as in the previous paragraph we have
\[\therefore \mu(\hat{B}_1)-\mu(\hat{B}_2)
<10^{-4}\mu(\hat{B_1}).\]
\hfill (Claim$\square$)
\smallskip
\def\hb{{\hat{B}}}
\begin{definition}
For $\hb\subset \tf$ with $\mu(\hb)\in (0, 1)$ we define
$\gamma_{\hb}\in L^2(\tf)$ by
\[\gamma_{\hb}(f)=\frac{\surd(1-\mu(\hb))}{\surd(\mu(\hb))}\]
for $f\in \hb$ and
\[\gamma_{\hb}(f)=\frac{-\surd(\mu(\hb))}{\surd(1-\mu(\hb))}\]
for $f\notin \hb$.
Note then that
\[\nh\gamma_{\hb}\nh^2_{L^2}=\int(\gamma_{\hb})^2\]
\[=\int_{\hat{B}}\frac{1-\mu(\hb)} {\mu(\hb)}+\int_{\tf\setminus \hat{B}}
\frac{\mu(\hb)}{1-\mu(\hb)} =1\]
and that
\[\langle \gamma_\hb , 1\rangle =
\int_{\hat{B}}({(1-\mu(\hb))}/{\mu(\hb)})^{\frac{1}{2}}-\int_{\tf\setminus
\hat{B}}
({\mu(\hb)}/{(1-\mu(\hb))})^{\frac{1}{2}}\]
\[=\surd(\mu(\hb))\surd(1-\mu(\hb)) - \surd(1-\mu(\hb))\surd(\mu(\hb)) = 0.\]
We therefore have a unit vector which is orthogonal to the constant
functions.
We say that $\sigma_0$ is a {\it center} (or {\it weak center})
for $f\in\tf$ if for $\hat{B}\in \abhn$ containing $f$ we have that $\sigma_0$
is a center (respectively, weak center) for $\pi(\gamma_\hb)$, the weight
associated to the element of $\abhn$ in which $f$ falls.
\end{definition}
\smallskip
\noindent{\bf Claim(IV):} If $f\in N_3, \tau\in \F_2, d(\tau, e)\leq 3,
f\in\hb_1, \tau\cdot f\in \hb_2, \hb_1, \hb_2\in \ahbn$,
then
\[\nh\tau\cdot \gamma_{\hb_1}-\gamma_{\hb_2}\nh_{L^2}
= \nh\gamma_{\tau\cdot \hb_1}-\gamma_{\hb_2}\nh_{L^2} < 3\cdot 10^{-2}.\]
\smallskip
\noindent{\bf Proof of Claim:} We may partition $\tf$ into the sets
$\tau\cdot\hb_1\Delta \hat{B}_2, \tau\cdot\hb_1\cap\hb_2,
\tf\setminus(\tau\cdot\hb_1\cup\hb_2)$
and let $\psi_1, \psi_2, \psi_3$ be the functions with support equal to those
sets respectively and such that
\[\gamma_{\tau\cdot\hb_1}-\gamma_{\hb_2}=\psi_1+\psi_2+\psi_3.\]
It suffices to find suitable bounds on $\nh\psi_1\nh_{L^2},
\nh\psi_2\nh_{L^2}, \nh\psi_3\nh_{L^3}$.
For ease of expression we assume $\mu(\hb_1)\leq \mu(\hb_2)$; this is
harmless;
the argument under the reverse inequality is symmetrical. Recall that we have
\[\mu(\hb_2)< \frac{10^4}{10^4-1}\mu(\hb_1)\]
by the last claim.
We calculate upper bounds on
$\nh\psi_1\nh_{L^2}, \nh\psi_2\nh_{L^2}, \nh\psi_3\nh_{L^2}$ in turn.
\[\nh\psi_1\nh_{L^2} =(\int_{\tau\cdot \hb_1\Delta\hb_2}\psi_1^2)^{1/2}
\leq [(4\cdot
10^{-4}\mu(\hb_1))(\frac{1}{\surd(\mu(\hb_1))})^2)^{\frac{1}{2}}
=\surd(4\cdot 10^{-4})
=2\cdot 10^{-2}.\]
\[\nh \psi_2\nh_{L^2} = (\int_{\tau\cdot \hb_1 \cap \hb_2}
\psi_2^2)^{\frac{1}{2}}
\leq \surd(\mu(\hb_2)) [ \frac{\surd(1-\mu(\hb_1))}{\surd(\mu(\hb_1))}
-\frac{\surd(1-\mu(\hb_2))}{\surd(\mu(\hb_2))} ] \]
\[\leq \surd(\mu(\hb_2)) [ \frac{\surd(1-\mu(\hb_1))}{\surd(\mu(\hb_1))}
-\frac{\surd(1-\mu(\hb_2))}{\surd(\mu(\hb_2))}]
[ \frac{\surd(1-\mu(\hb_1))}{\surd(\mu(\hb_1))}
+ \frac{\surd(1-\mu(\hb_2))}{\surd(\mu(\hb_2))}] (\surd(\hb_2)) \]
\[=\mu(\hb_2)[\frac{(1-\mu(\hb_1))}{(\mu(\hb_1))}
-\frac{(1-\mu(\hb_2))}{(\mu(\hb_2))}\]
\[= \mu(\hb_2)
(\frac{\mu(\hb_2) -\mu(\hb_1)\mu(\hb_2) -\mu(\hb_1) +\mu(\hb_1)\mu(\hb_2)}
{\mu(\hb_1)\mu(\hb_2)} \]
\[=\frac{\mu(\hb_2)-\mu(\hb_1)}{\mu(\hb_1)} <
\frac{10^{-4}\mu(\hb_1)}{\mu(\hb_1)}
=10^{-4}.\]
\[\nh\psi_3\nh_{L^2} =((\int_{\tf\setminus(\tau\cdot \hb_1\cup \hb_2)}
[\frac{\surd(\mu(\hb_1))}{\surd(1-\mu(\hb_1))} -
\frac{\surd(\mu(\hb_2))}{\surd(1-\mu(\hb_2))}]^2)^{\frac{1}{2}}\leq
[(\frac{\surd(\mu(\hb_1))}{\surd(1-\mu(\hb_1))})^2+
(\frac{\surd(\mu(\hb_2))}{\surd(1-\mu(\hb_2))})^2]^{\frac{1}{2}}\]
\[<(2\mu(\hb_1) +2\mu(\hb_2))^{\frac{1}{2}}< (2\cdot 10^{-8} + 2\cdot
10^{-8})^{\frac{1}{2}}
=2\cdot 10^{-4}.\]
%\[\leq
%\frac{1}{\surd(\mu(\hb_1)}[\frac{\surd(\mu(\hb_1))}{\surd(1-\mu(\hb_1))} -
%\frac{\surd(\mu(\hb_2))}{\surd(1-\mu(\hb_2))}]
%[\frac{\surd(\mu(\hb_1))}{\surd(1-\mu(\hb_1))} +
%\frac{\surd(\mu(\hb_2))}{\surd(1-\mu(\hb_2))}]\]
%\[=\frac{1}{\surd(\mu(\hb_1)}[\frac{\mu(\hb_1)}{1-\mu(\hb_1)} -
%\frac{\mu(\hb_2)}{1-\mu(\hb_2)}]\]
%\[=\frac{1}{\surd(\mu(\hb_1)}[\frac{\mu(\hb_1) -\mu(\hb_1)\mu(\hb_2)
%-\mu(\hb_2) %+\mu(\hb_1)\mu(\hb_2)}{(1-\mu(\hb_1))(1-\mu(\hb_2))}] \]
%\[\leq \frac{4}{\surd(\mu(\hb_1))}(\mu(\hb_1)+\mu(\hb_2))\leq
%\frac{9\cdot \mu(\hb_1)}{\surd(\mu(\hb_1))}=9\surd(\mu(\hb_1))< 9\cdot
%10^{-4}.\]
\hfill(Claim$\square$)
%\smallskip
%\noindent{\bf Claim(V):} If $f\in N_3, \tau\in \F_2, d(\tau, e)\leq 3,
%f\in\hb_1, \tau\cdot f\in \hb_2, \hb_1, \hb_2\in \ahbn$,
%then
%\[\nh\tau\cdot \gamma_{\hb_1}-\gamma_{\hb_2}\nh_{L^2}
%= \nh\gamma_{\tau\cdot \hb_1}-\gamma_{\hb_2}\nh_{L^2} < 4\cdot 10^{-2}.\]
%\smallskip
%\noindent{\bf Proof of Claim:}
%We have that
%\[\surd(1+\mu(\hb_1))\gamma_{\tau\cdot \hb_1}= \gamma_{\tau\cdot \hb_1}^*,\]
%\[\therefore \nh\gamma_{\tau\cdot \hb_1}
%-\gamma^*_{\tau\cdot\hb_1}\nh_{L^2} < 10^{-8},\]
%\[\surd(1+\mu(\hb_2))\gamma_{\hb_2}= \gamma_{\hb_2}^*,\]
%\[\therefore \nh\gamma_{ \hb_2} -\gamma^*_{\hb_2}\nh_{L^2} < 10^{-8}.\]
%Hence by the previous claim
%\[\nh\gamma_{\tau\cdot \hb_1}-\gamma_{\hb_2}\nh_{L^2}\leq
%\nh\gamma_{\tau\cdot \hb_1} -\gamma^*_{\tau\cdot\hb_1}\nh_{L^2}
%+ \nh\gamma_{\tau\cdot \hb_1}^*-\gamma_{\hb_2}^*\nh_{L^2}
%+ \nh\gamma_{ \hb_2} -\gamma^*_{\hb_2}\nh_{L^2} < 10^{-8} + 3\cdot
%10^{-2} + 10^{-8}
%< 4\cdot 10^{-2}.\]
%\hfill(Claim$\square$)
\smallskip
\noindent{\bf Claim(V):} If $f\in N_3, \tau\in \F_2,
d(\tau, e)\leq 3$, $\sigma_0$ a center for $f$, then
$\sigma_0\tau^{-1}$ is a weak center for $\tau\cdot f$.
\smallskip
\noindent{\bf Proof of Claim:} We fix $\hb_1, \hb_2\in \ahbn$ with
$f\in \hb_1$ and $\tau\cdot f\in \hb_2$. By definition we then have
$\sigma_0$ a center for $\pi(\gamma_{\hb_1})$.
By (iv) \ref{IV} we have that $\sigma_0\cdot\tau^{-1}$ is a center for
$\pi(\tau\cdot\gamma_{\hb_1})=\pi(\gamma_{\tau\cdot\hb_1})$. By claim(IV)
we have
$\nh\gamma_{\tau\cdot\hb_1}-\gamma_{\hb_2}\nh_{L^2}< \frac{1}{12}$, and
hence by (v) \ref{IV} $\sigma_0\tau^{-1}$ is a weak center for
$\pi(\gamma_{\hb_2})$ and hence by definition a weak center for
$\tau\cdot f$.
\smallskip
\begin{definition} For $x\in \{a, a^{-1}, b, b^{-1}\}$ we let $A_x$ be
the set of
$f\in N_3$ such that either the identity $e$ is a center of $f$ or
some reduced word of the form $\sigma x$ is a center of $f$.
For $\tau$ a reduced word we let $B_\tau$ be the set of $f\in \tf$ such that
some reduced $\sigma\tau$ is a weak center for $f$.
\end{definition}
Each $f\in N_3$ is a member of at least one $A_x$ by lemma \ref{I}, and hence
we may fix $A_x$ with $\mu(A_x)>\frac{1}{5}$. From the last claim we have
that if $f\in A_x\cap N_3$, and $\tau$ does {\it not} begin with $x$, and
$d(\tau, e)\leq 3$, then
\[\tau\cdot f\in B_{x\tau^{-1}}\subset B_{\tau^{-1}}.\]
There are 27 possibilities for a reduced word $\tau$ of length 3
not starting with $x$, and
for each such $\tau$ we have
\[\mu(B_{x\tau^{-1}})\geq \mu(A_x)>\frac{1}{5}.\]
Since $\frac{27}{5}> 2$ there is some $f\in\tf$ in three different
$B_{x\tau^{-1}_1}, B_{x\tau^{-1}_2}, B_{x\tau^{-1}_3}$, each $x\tau_i$
reduced, each $d(\tau_i, e)=3$. This flatly contradicts lemma \ref{III}.
\bigskip
So much for the proof of the theorem under the simplifying assumption
that $\theta$ is one to one everywhere.
In the general case we must first pass to $M_0$ of positive measure on
which $\theta$ is injective. Since the action of $\F_2$ on $\tf$ is
mixing we may find invertible mpts
\[T, S: M_0\rightarrow M_0\]
such that at each $x\in M_0$ there will be $n(x), m(x)>0$ with
\[T(x)=a^{n(x)}\cdot x, \]
\[S(x)=b^{m(x)}\cdot x,\]
and thus we have $\langle T, S\rangle\cong\F_2$.
Now we trot through the argument above, but selectively replacing
$\langle a, b\rangle$ with $\langle T, S\rangle$.
We still calculate the centers with respect to the
Cayley graph on $\F_2=\langle a, b\rangle$, but we use only
words from $\langle T, S\rangle$ to shift.
We amend the definitions from above by setting $\hat{B}=M_0\cap
\theta^{-1}[B]$
for $B\in \b$; as in claim(I) we may find an $n$ such that for all
$\hat{B}\in \abhn$, all $x\in \{T, T^{-1}, S, S^{-1}\}$,
and $f_1, f_2$ in a subset of $M_0$ with relatively
large measure, $g_{f_1, x}=g_{f_2, x}$, where $f\mapsto g_{f, x}$ has
been chosen measurably with the requirement that
$\theta(x.f)=g_{f, x}\cdot \theta(x).$
Our definitions of $N_2, N_1$ are parallel to the ones before, but now
asking that $N_2\subset N_1\subset M_0$ and $\mu(N_2)>(1-10^{-8})\mu(M_0)$
and having $x$ range over $\{T, T^{-1}, S, S^{-1}\}$. In claim(II) we have
$x$ again range over $\{T, T^{-1}, S, S^{-1}\}$ and in claim(III) we have
$\tau$ range over words of length less than
three built from $\{T, T^{-1}, S, S^{-1}\}$. The main idea here is that
if $\tau$ is an irreducible word in $\{T, T^{-1}, S, S^{-1}\}$ and $f\in M_0$,
then there will be a corresponding $\bar{\tau}_f$ built from
$\{a, a^{-1}, b, b^{-1}\}$ with $\bar{\tau}_f\cdot f=\tau\cdot f$ and various
other natural properties: $\sigma = \tau$ if and only if $\bar{\sigma}_f =
\bar{\tau}_f$; $\sigma$ and $\tau$ are incomparable (i.e. neither extends
the other) if and only if $\bar{\sigma}_f$ is incomparable with
$\bar{\tau}_f$.
With these and other natural adjustments the proof passes through as before.
\end{proof}
Kechris pointed out a more elegant approach to the last step of the argument,
which passes from one to one somewhere to the specific case of one to
one everywhere. We begin by assuming we have a homomorphism\footnote{A
Borel function $\theta$ is said to be a {\it homomorphism} from an
equivalence relation
$F$ to an equivalence relation $F'$ if $x_1 F x_2$ always implies
$\theta(x_1) F' \theta(x_2)$.}
$\theta$ from $E_{\F_2}$
as in the statement of the theorem; we are aiming for a contradiction.
We
then choose Borel
$\rho: \theta[M]\times \N \twoheadrightarrow M$ such that
$\{\rho(y, n): n\in\N\}$ enumerates the preimage of any $y\in \theta[M]$.
We let $G\times \Z$ act on $X\times 2^{\N}$ with the product of the original
action of $G$ on $X$ and the odometer action of $\Z$ on $2^\N$ (the generator
acts by adding one with carry, but in fact any modular action of
$\Z$ or any other countably infinite group will do); this action will
still be modular since
the odometer action of $\Z$ is modular.
We let $(z_n)_{n\in\N}$ enumerate some orbit in $2^\N$ under the action
of $\Z$.
We now define a new homomorphism
\[\hat{\theta}: M\rightarrow X\times 2^\N\]
given by
\[\hat{\theta}(x)=(\theta(x), z_n),\]
where $n$ is least such that $\rho(\theta(x), n)=x$.
This new homomorphism is one to one everywhere, and falls into the proof
above.
There is one obvious generalization which the argument accommodates.
\begin{definition} Let $(Z, \c, \nu)$ be a standard Borel probability space
and let $Z^{\F_2}$ be the product space consisting of all
\[f: \F_2\rightarrow Z\]
with the product measure and the action defined by
\[\sigma\cdot f(\tau)=f(\tau\sigma).\]
This space with this action and measure is said to be the
{\it Bernoulli shift} of $\F_2$ on $Z^{\F_2}$.
\end{definition}
\begin{theorem}
\label{extend}
Let $E$ be of modular type on $(X, \b)$,
$(Z, \c, \nu)$ a standard Borel probability space,
and $M\subset Z^{\F_2}$ of
full measure.
Then there is no countable to one measurable
\[\theta: M\rightarrow X\]
such that $f_1 E_{\F_2} f_2\Rightarrow \theta(f_1) E \theta(f_2).$
\end{theorem}
\begin{proof}
We let $(C_\ell)_{\ell\in \N}$ be a generating algebra of $\nu$-independent
sets in $Z$, each having measure one half. For $S\subset \N\times \F_2$
finite we define
\[\psi_S: Z^{\F_2}\rightarrow \{-1,1\}\]
\[f\mapsto (-1)^{|\{(\ell, \sigma)\in S: f(\sigma)\in C_\ell\}|}.\]
With this and other painless modifications the proof goes through as before.
\end{proof}
\section{Borel reducibility}
\begin{definition} For $E$ and $F$ equivalence relations on standard Borel
$(X, \b)$ and $(Y, \c)$, we say that $E$ {\it is Borel reducible to } $F$,
written $E\leq_B F$, if there is a Borel function $\theta: X\rightarrow
Y$ with
\[x_1 E x_2 \Leftrightarrow \theta(x_1) F \theta(x_2).\]
We write $E<_B F$ if $E\leq_B F$ holds but $F\leq_B E$ fails.
We say that $E$ is {\it treeable} if it is countable and there is an acyclic
graph on $X$, which is Borel in the sense of having its collection of
vertices Borel as a subset of $X\times X$ in the product Borel structure,
whose
connected components form the $E$ equivalence classes. $E$ is {\it
hyperfinite}
if it can be written as an increasing union of Borel equivalence
relations which
have all equivalence classes finite.
\end{definition}
Any free Borel action of $\F_2$ is treeable; one simply copies the
Cayley graph across the various components of $E_{\F_2}$.
An equivalence relation with countable classes is {hyperfinite} if and only
if it is Borel reducible to $E_0$. A group is amenable if and only if it
has a free action by measure preserving transformations on a standard
Borel probability space whose resulting orbit equivalence relation is
hyperfinite.
For these and other related facts the reader should refer to
\cite{jakelo}.
\begin{theorem} (Jackson, Kechris, Louveau; see \cite{jakelo}.)
There is a universal treeable equivalence relation; that is to say, there is a
treeable equivalence relation $E_{\t\infty}$ such that for all $F$ with
countable
classes we
have
\[F\leq_B E_{\t\infty}\]
if and only if $F$ is treeable.
\end{theorem}
Not all treeable equivalence relations are universal in their sense. $E_0$ is
treeable, but not $\leq_B$-universal. But in answer to a question raised in
\cite{jakelo}:
\begin{theorem} There is an
equivalence relation $E$ on standard Borel $(X, \b)$
with
\[E_0<_B E<_B E_{\t\infty}.\]
\end{theorem}
\begin{proof} Let $E$ be a modular equivalence relation, arising
from a free ergodic action of
$\F_2$ as in \cite{slamansteel}, as discussed following the
original definition of modular in the previous
section. Since it arises from a free Borel action of $\F_2$, it
is treeable; since there is an invariant measure and $\F_2$ is non-amenable,
it is not Borel reducible to $E_0$.
To see that it is not $\leq_B$-universal among treeable equivalence relations
we apply \ref{main}.
\end{proof}
John Clemens pointed out a further application of \ref{main}. He begins
by considering the equivalence relation $E^{X_{ss}}_{\F_2}\times E_0$, where,
as before, $\F_2$ acts in a measure preserving fashion on $X_{ss}$ with
modular type. This resulting product equivalence relation is still
modular, and hence in particular $E_{\t\infty}$ is not Borel reducible to
$E^{X_{ss}}_{\F_2}\times E_0$; on the other
hand by \cite{adams} the product equivalence relation is not treeable and thus
we also have $E^{X_{ss}}_{\F_2}\times E_0$ not Borel reducible to
$E_{\t\infty}$.
In this way we have an example of a countable Borel equivalence relation which
is not $\leq_B$-comparable with $E_{\t\infty}$. As Clemens puts it,
$E_{\t\infty}$ is not a {\it node} among the countable Borel equivalence
relations.
There is one manner in which the definition of
modular could be relaxed. Instead
of asking that each $\b_n$ be finite we ask only that it be countable and
generated as an algebra by its atoms.
\begin{definition}
An equivalence relation $E$ on a standard Borel space $(X, \b)$ is
{\it loosely modular} if there is a countable group $G$ acting by
Borel automorphisms on $X$ with $E=E_G$ and there is an increasing sequence
of countable algebras
\[\b_0\subset\b_1\subset...\subset\b_n\subset...\b\]
such that
\leftskip 0.4in
\noindent (a) each $B\in\b_n$ is a finite Booelan combination
of the atoms in $\b_n$;
\noindent (b) each $\b_n$ is permuted by the action of $G$.
\leftskip 0in
\end{definition}
However in the context of equivalence relations and actions on finite measure
spaces this generalization, although painless, buys relatively little new.
We leave the following proposition as an exercise for the reader.
%\begin{fact} Let $(\b_n)_{n\in\N}$ and $G$ witness that $E=E_G$ on $(X,\b)$
%is loosely modular,
%and at each $n$ let $(A_{n, i})_{i\in\N}$ enumerate the
%atoms of $\b_n$. Let $(Y, \c, \mu)$ be a probability space and
%\[\theta: Y\rightarrow X\]
%a measurable map.
%Then we may find a sequence $(\ell_n)_{n\in\N}$ such that on a
%non-null set
%\[{\theta}(y) \in \bigcap_{n\in\N}\bigcup_{i\leq\ell_n} A_{n, i}. \]
%\end{fact}
%\hfill ($\square$)
%If in this situation $\theta$ provides a homomorphism from
%an {\it ergodic} equivalence relation $F$ on $Y$ to $E_G$ on $X$,
%then
%a.e. $y$ has $\theta(y)$ $E_G$-equivalent to some element of
%$\bigcap_{n\in\N}\bigcup_{i\leq\ell_n} A_{n, i}$; thus
%by adjusting the homomorphism $\theta$ to some new
%$\hat{\theta}$ with $\hat{\theta}(y) E_F \theta(y)$ at
%a.e. $y$, we obtain:
\begin{proposition} Let $E$ on $(X, \b)$ be loosely modular, $F$ an
ergodic equivalence relation on a standard
Borel probability space $(Y, \c,\mu)$, and
\[\theta: Y\rightarrow X\]
a countable to one measurable map with
\[y_1 F y_2\Rightarrow \theta(y_1) E \theta(y_2).\]
Then there is a modular $\hat{E}$ on $(\hat{X}, \hat{\b})$ and a
countable to one measurable $\hat{\theta}: Y\rightarrow \hat{X}$
with $y_1 F y_2 \Rightarrow \hat{\theta}(x_1) \hat{E} \hat{\theta}(x_2)$.
\end{proposition}
Thus if $F$ refuses measurable reduction to a
modular equivalence relation
then it likewise refuses measurable reduction to any loosely modular
equivalence relation.
An example of a loosely modular equivalence relation is given by any
countable group of permutations of $\N$ acting by right composition
on the space of injections from $\N$ to some countable set. It follows then
in particular that there are countable
Borel equivalence relations which are not reducible to say the group of
recursive permutations
acting on the space of injections $\N\hookrightarrow \N$.
Since the first draft of this paper, Kechris
in \cite{kechrisnotes} has written up his
own treatment of this material which draws out the representation
theoretic connections and in which he formalizes the notion of
{\it anti-modular}.
\newpage
\begin{thebibliography}{99}
\bibitem{adams} S. Adams, {\it The indecomposability of treed equivalence
relations,} {\bf Israel Journal of Mathematics,} vol. 64(1988), pp. 362--380.
\bibitem{bezuglyigolodets} S. Bezuglyi, V. Golodets, {\it Hyperfinite
and ${\rm II}\sb{1}$
actions for nonamenable groups,}
{\bf Journal of Functional Analysis,} vol. 40(1981), pp. 30--44.
\bibitem{cofewe} A. Connes, J. Feldman, B. Weiss,
{\it An amenable equivalence relation is generated by a single
transformation,}
{\bf Ergodic Theory Dynamical Systems,}
vol. 1(1981), pp. 431--450.
\bibitem{connesweiss}
A. Connes, B. Weiss,
{\it Property ${\rm T}$ and asymptotically invariant sequences,}
{\bf Israel Journal of Mathematics,}
vol. 37(1980), pp. 209--210.
\bibitem{dye} H.A. Dye,
{\it On groups of measure preserving transformation. I,}
{\bf American Journal of Mathematics,}
vol. 81(1959) pp. 119--159.
\bibitem{dye2} H.A. Dye,
{\it On groups of measure preserving transformation. II,}
{\bf American Journal of Mathematics,}
vol. 85(1963) pp. 551--576.
\bibitem{gaboriaupopa} D. Gaboriau, S. Popa,
{\it An uncountable family of non-orbit equivalent actions
of $\F_n$,} preprint,
Ecole Normale Superieure, Lyon, UMPA, 2003.
\bibitem{geftergolodets}
S. Gefter, V. Golodets,
{\it Fundamental groups for ergodic actions and actions with unit
fundamental groups,}
{\bf Kyoto University Research Institute for Mathematical Sciences
Publications,}
vol. 24(1988), pp. 821--847.
\bibitem{harpevalette} P. de la Harpe, A. Valette,
{\bf La Propri\'{e}t\'{e} (T) de Kazhdan pour les localement compact},
Ast\'{e}rique {\bf 175}, 1989.
\bibitem{jonesschmidt} V.F.R Jones, K. Schmidt,
{\it Asymptotically invariant sequences and approximate finiteness,}
{\bf American Journal of Mathematics,} vol. 109(1987), pp. 91--114.
\bibitem{kechris} A.S. Kechris,
{\bf Classical descriptive set theory,}
Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995.
\bibitem{kechrisnotes}
A.S. Kechris,
{\it Notes on unitary representations and modular actions,}
preprint, Caltech, 2003.
\bibitem{jakelo}
S. Jackson, A.S. Kechris, A. Louveau,
{\it Countable Borel equivalence relations,}
{\bf Journal of Mathematical Logic,}
vol. 2(2002), pp. 1--80.
\bibitem{ornsteinweiss} D. Ornstein, B. Weiss,
{\it Ergodic theory of amenable group actions,}
{\bf Bulletin of the American Mathematical Society,}
vol. 2(1980), pp. 161--164.
\bibitem{popa} S. Popa,
{\it Correspondences,}
typed notes, INCREST, preprint, 1986.
\bibitem{popa2} S. Popa,
{\it On a class of type II$_1$ factors with
Betti number invariants,} typed notes, UCLA, 2002.
\bibitem{schmidt} K. Schmidt,
{\it Asymptotically invariant sequences and an
action of SL$(2, \Z)$ on the sphere,}
{\bf Israel Journal of Mathematics,}
vol. 37(1980), pp. 193--208.
\bibitem{schmidt2} K. Schmidt,
{\it Some solved and unsolved problems concerning orbit
equivalence of countable group actions,}
pp. 171--184, in
{\bf Proceedings of the Conference in
Ergodic Theory and Related Topics II,
Georgenthal (Thurinigia), GDR, April 20-25,
1986,} Heubner-Texte, Band 94, Leipzig, 1987.
\bibitem{slamansteel} T. Slaman, J.R. Steel,
{\it Definable functions on degrees} in {\bf Cabal Seminar 81--85,}
pp. 37--55, Lecture Notes in Mathematics,
1333, Springer, Berlin, 1988.
\bibitem{thoma} E. Thoma,
{\it \"{U}ber unit\"{a}re Darstellungen abz\"{a}hlbarer, diskreter Gruppen,}
{\bf Mathematische Annalen,}
vol. 153(1964), pp. 111--138.
\bibitem{zuk} A. Zuk,
{\it Property (T) and Kazhdan constants for discrete groups,}
{\bf Geometric and Functional Analysis,}
vol. 13(2003), pp. 643--670.
\bibitem{zimmer} R.J. Zimmer,
{\bf Ergodic Theory and Semisimple Groups,}
Birkh\"{a}user, Boston, 1984.
\end{thebibliography}
\leftskip 0.5in
greg@math.ucla.edu
\bigskip
MSB 6363
UCLA
CA 90095-1555
\leftskip 0in
\end{document}