\documentclass{article}
%\usepackage{graphicx}
\usepackage{amssymb}
%\usepackage{psfig}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{counterexample}[theorem]{Counterexample}
\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}}
\newenvironment{pcounterexample}[1][Counterexample]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
% 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}{6in}
\setlength{\topmargin}{-0.25in}
% Set height of the text - What is left will be the bottom margin.
% In this case, bottom margin is 11in - 0.75in - 9.5in = 0.75in
\setlength{\textheight}{8in}
% Set the beginning of a LaTeX document
\renewcommand{\topfraction}{1}
\renewcommand{\textfraction}{0}
\begin{document}
\title{\huge A lemma for cost attained\footnote{{\it Key words and phrases:}
Ergodic theory, treeable equivalence relations, free groups, measure
equivalence
of groups {\it AMS Subject Classification:} 04A15, 28D15, 37A15.} }
\author{Greg Hjorth\footnote{Partially supported by
NSF grants DMS 99-70403, DMS 01-40503.}} % Enter your name
%\date{\empty} % Enter your date or \today between curly braces
%\maketitle
\maketitle
\abstract{A treeable ergodic
equivalence relation of integer cost is generated by a
free action of the free group on the corresponding number of generators.
Every countable treeable ergodic
equivalence relation is induced by the free action of some countable group.}
%\begin{abstract}
%This paper is a sample prepared to illustrate the use of the American
%Mathematical Society's \LaTeX{} document class \texttt{amsbook} and
%publication-specific variants of that class for AMS-\LaTeX{} version 1.2.
%\end{abstract}
\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\o{{\omega}}
\def\oo{{\omega^{\omega}}}
\def\lo{{\omega^{<\omega}}}
\def\d{{\dot{\bigcup}}}
%\def\h{{\mathcal H}}
\def\no{\noindent}
\def\a{{\mathcal A}}
\def\b{{\mathcal B}}
\def\l{{\mathcal L}}
\def\n{{\mathcal N}}
\def\m{{\mathcal M}}
\def\h{{\mathcal H}}
\def\co{{\mathcal O}}
\def\t{{\mathcal T}}
\def\c{{\mathcal C}}
\def\F{{\mathbb F}}
\def\Varphi{\Phi}
\def\p{\varphi}
\def\P{\Phi}
\def\hP{\hat{\Phi}}
\def\hp{\hat{\varphi}}
%\def\ht{\hat{\theta}}
%\def\hT{\hat{\Theta}}
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{Introduction}
\label{introduction}
Given an equivalence relation $E$ one can consider the
{\it graphings} of $E$, consisting of partial functions included in the
graph of $E$ whose
various compositions enable us to trace out a path between any two
equivalent points.
Levitt in \cite{levitt} defines the cost of a measure preserving
equivalence relation to be the infimum among graphings of the sums
of the measures of the domains of the relevant partial
functions.
Here we present a result, which in an unpublished form has
been previously
cited by \cite{kechrismiller}
to obtain a kind of dichotomy theorem for amenability and \cite{popa}
in an application to von Neumann algebras.
The authors of \cite{kechrismiller} wrote up a proof of
\ref{mainlemma}, though their organization is very different to
the one below.
\begin{proposition}
\label{mainlemma}
Let $E$ be an ergodic measure preserving equivalence relation
on a standard Borel probability space $(X,\mu)$;
assume that every equivalence class is countable.
Let $\Varphi$ be a graphing for $E$ with
$C_\mu(\Varphi)\geq n$.
Then there is an alternate graphing $\Varphi'$ for $E$ which has
no greater cost and contains $n$ morphisms which are {\it total}
that is to say --
\leftskip 0.4in
(a) $C_\mu(\Varphi')\leq C_\mu(\Varphi)$;
(b) and there are distinct bijections
$\varphi_1,..., \varphi_n$ in $\Varphi'$ with
$\varphi_i: X\rightarrow X$.
\end{proposition}
One obtains additionally that if $C_\mu(\Phi)\leq n+1$
then we
may further conclude
$\Varphi'=\{\varphi_1, \varphi_2, ..., \varphi_n, \theta\}$,
where $\theta:A\rightarrow B$ is a bijection, some $A, B\subset X$.
Recall that a measurable equivalence relation is {\it treeable} if there is a
measurable way of assigning the structure of a tree
to each equivalence class.
In the next corollary one should bear in mind that Damien Gaboriau has shown
in \cite{gaboriau} that
an $E$ as above with finite cost
is {treeable} if and only if it admits a graphing which actually
attains its cost, and in this case any treeing will in fact realize the
infimum.
\begin{corollary} For $E$ treeable and as above, the cost of $E$ equals $n$
if and only if
there is a measure preserving action of the free group on $n$ generators,
$\F_n$, which is
free $\mu$-a.e. and has $E$ as its orbit equivalence relation.
\end{corollary}
We also show that in the case that $E$ is treeable with
infinite cost one may
find a free action of $\F_\infty$ giving rise to $E$.
Appealing to the connections made in \cite{furman} between
orbit equivalence in the ergodic setting and measure equivalence,
this implies that a countable non-amenable group is measure equivalent to
a non-abelian
free group if and only if it has a free measure preserving
action on some standard Borel probability space which gives
rise to a treeable equivalence relation.
This paper finishes
with a comment on a deep theorem of Alex Furman's.
\begin{corollary} If $E$ is
a treeable ergodic measure preserving equivalence relation on a standard
Borel probability space with countable classes,
then
there is a countable group
$G$ acting $\mu$-a.e. freely giving rise to $E$ as its orbit equivalence
relation.
Moreover, the group $G$ can be chosen solely as a function of the cost
of $E$.
\end{corollary}
Furman in \cite{furman}
had previously obtained ergodic $E$ which are not
induced by an a.e. free action of a countable group.
His examples arose by the restriction of a non-treeable
equivalence relation to a non-null set, and were therefore known
to be non-treeable.
\section{Notation and Definitions}
We take all the usual notational shortcuts. All sets considered are
measurable.
All functions are measurable. All group actions are by measure preserving
transformations.
We identify functions agreeing a.e.
Unless otherwise warned, the reader should assume that all non-empty
sets are non-null.
We tend to say
{\it everywhere} when we only mean {\it almost everywhere}.
$\N$ begins with the number 0.
\begin{definition} A {\it standard Borel space} is a set $X$ equipped with a
$\sigma$-algebra ${\mathcal B}$, such that ${\mathcal B}$ is the
$\sigma$-algebra
generated by some
choice of a
Polish topology on $X$.
A {\it standard Borel probability space} is a standard Borel space
equipped with a probability measure on its Borel sets.
\end{definition}
In general we will only be considering uncountable standard Borel spaces,
and these are
all isomorphic to the unit interval in its usual Borel structure. Thus one
might
reasonably think of a standard Borel probability space as just being some
choice
of a Borel probability measure on [0,1].
\begin{definition} If $E$ is an equivalence relation on a standard Borel
probability space $(X, \mu)$, and $A, B\subset X$ measurable, then we say
that a
function
\[f: A\rightarrow B\]
is a {\it morphism} (for $E$) if it is a bijection and
\[x E f(x)\] all $x\in A$.
We say that $E$ is {\it measure preserving} if every morphism is a measure
preserving
function. We say that $E$ is {\it ergodic} if every $E$-invariant set is
either null or
conull.
\end{definition}
From \cite{feldmanmoore}, the measure preserving equivalence relations
with countable classes are exactly those
induced by a countable group of measure preserving transformations. Even in
the case that
$E$ is ergodic, \cite{furman} has shown that in general we may not be able
to choose this
group so that it acts {\it freely} on the space. Below we will prove that
the additional
assumption of {\it treeability} does ensure that we can choose the
countable group so that
it acts freely.
\begin{definition} Given a set $\Psi$ of morphisms, a {\it word} built from
$\Psi$ is a morphism of the form
\[x\mapsto
\psi_1^{\epsilon(1)}\circ\psi_2^{\epsilon(2)}...\circ\psi_n^{\epsilon(n)}(x)
,\]
where each $\psi_i\in \Psi$, each $\epsilon(i)\in \{-1, 1\}$, and $x$
ranges over
a set on which these compositions make sense.
The word is {\it reduced} if at no $i$ do we have
$\epsilon(i)=-\epsilon(i+1)$ along
with $\psi_i=\psi_{i+1}$.
A set of morphisms $\Psi$ is said to be a {\it graphing of $E$} if for any
$xEy$
there is a word mapping $x$ to $y$; the graphing is said to be a {\it
treeing} if there is
always a {\it unique} reduced word.
Equivalently, $\Phi$ is a treeing if the adjacency relation $xRy$ if there
exists $\varphi\in\Phi$
with $\varphi^{\pm 1}(x)=y$ provides a tree structure on each equivalence
class.
For $\Psi$ a collection of morphisms we let
$\Psi^{-1}=\{\phi^{-1}: \phi\in \Psi\}$.
\end{definition}
\section{Proof}
\label{proof}
We set about proving \ref{mainlemma} for $n=2$. It should be more or less
clear
how to extend it to larger $n$.
We organize this into a series of small technical
lemmas, omitting proofs when they
resemble earlier argument.
The first of these lemmas, at \ref{1}, states that we may
find a new morphism $\hat{\varphi}_0$ included in $E$ and a
corresponding partition of the
space up into an infinite array of measurable sets,
\[B_{1, 0}, B_{1, 1},\]
\[B_{2, 0}, B_{2, 1}, B_{2,2},\]
\[...\]
\[B_{n, 0}, B_{n,1}, B_{n, 2},..., B_{n, n},\]
\[...,\]
such that at each $n\geq 1$ and $k0$, $\psi|_{C_i}=(\hat{\varphi}_0)^{\ell_i}|_{C_i}$,
some $\ell_i\in\Z$ (we can recover the missing pieces of the old
morphisms as powers of the new morphism).
\leftskip 0in
\end{lemma}
\begin{proof}
We assume that for distinct $\p, \p'\in \P$ we always have $\p (x)\neq
\p'(x)$ when
both are defined. We may also assume there is some $\hat{\psi}\in \Phi$ with
Ran$(\hat{\psi})\cap$ Dom$(\hat{\psi})$ empty.
We build transfinite sequences of graphings
\[(\Psi_\alpha)_{\alpha< \delta}, (\P_\alpha)_{\alpha < \delta},\]
along with a choice of morphisms $\p_\alpha\in\P_\alpha$,
by induction on $\alpha$ so that:
\leftskip 0.4in
\no (a) $\Psi_0$ is empty; $\P_0=\P$;
\no (b) $\Psi_1$ consists in a single morphism $\bar{\theta}_0$
with Ran$(\bar{\theta}_0)\cap$Dom$(\bar{\theta}_0)=\emptyset$,
$\bar{\theta}_0\in \Phi$, $\mu($Dom$(\bar{\theta}_0))\neq 0$; we set
$\varphi_0=\bar{\theta}_0$,
and for all $\alpha$ and $\theta\in \Psi_\alpha$ we
have
Ran$(\theta)\cap$ Dom$(\theta)$ empty;
\no (c) if $\alpha+1< \delta$, $\alpha>0$,
and $\theta\in \Psi_{\alpha +1}$, then
Dom$(\theta)\subset$ Ran$(\theta')$ some $\theta'\in \Psi_\alpha$;
\no (d) for $\alpha\leq \beta$ we have $\Psi_\alpha\subset \Psi_\beta$ and at
$\lambda$ a limit ordinal we have
$\Psi_\lambda=\bigcup_{\alpha<\lambda}\Psi_\alpha$;
\no (e) if $\p, \p'\in \Psi_\alpha$ are distinct, then their ranges are
disjoint
and their domain are disjoint;
\no (f) each $\Psi_\alpha\cup\Phi_\alpha$ graphs $E$;
\no (g) $\varphi_\alpha\in \Phi_\alpha$ is the only morphism not appearing in
$\Phi_{\alpha +1}$ and for this $\p_\alpha$ there is a partition of
Dom$(\p_\alpha)$ into $A_0^\alpha, A_1^\alpha$ such that
\leftskip 0.6in
\no $\mu(A_1^\alpha)\neq 0$;
\no $\varphi_\alpha|_{A_1^\alpha}\in\Phi_{\alpha+1}$;
\no there are $\psi_1, ..., \psi_\ell, \hat{\psi}_1, ..., \hat{\psi}_k\in
\Psi_\alpha\cup\Psi_\alpha^{-1}$, and $\bar{\theta}_\alpha\in
\Psi_{\alpha+1}$, with
\[{\rm
Dom}(\bar{\theta}_\alpha)=\hat{\psi}_1\circ...\hat{\psi}_k[A_0^\alpha]\]
and we have either
\[\varphi_\alpha|_{A^\alpha_0}=\psi_1\circ\psi_2\circ...\psi_\ell\circ
\bar{\theta}_\alpha\circ\hat{\psi}_1\circ...\circ\hat{\psi}_k|_{A_0^\alpha}\]
or
\[(\varphi_\alpha|_{A^\alpha_0})^{-1}=\psi_1\circ\psi_2\circ...\psi_\ell\circ
\bar{\theta}_\alpha\circ\hat{\psi}_1\circ...\circ\hat{\psi}_k|_{A_0^\alpha}\]
\leftskip 0.4in
\no (h) if $\lambda$ is a limit then for $\alpha<\lambda$ and $\p\in\P_\alpha$,
we have
$\p\in \P_\lambda$ if $\varphi$ is in every earlier
$\Phi_\alpha$, or otherwise we have $\p|_{A^\lambda_{\infty, \p}}\in
\P_\lambda$,
where
\[A_{\infty, \p}^\lambda=\bigcap\{A^\beta_1: \beta\geq\alpha,
\p_\beta\subset \p\}.\]
\leftskip 0in
\bigskip
In rough terms, we begin the construction by taking some
$\bar{\theta}_0$ in our original graphing which can be assumed to
have disjoint range and image and simply adding it to
$\Psi_1$ and subtracting it from $\Phi_0$ to obtain $\Phi_1$.
We just describe the first few steps, without giving
much in the way of proofs yet.
%\psfig{file=costone.ps}
\begin{figure}[h]
\begin{picture}(200,200)
\put(25,125){\framebox(50,50){}}
\put(125, 125){\framebox(50, 50){}}
\put(75, 150){\vector(1, 0){50}}
\put(100, 165){\makebox(0, 0){$\bar{\theta}_0$}}
\put(0, 0){\framebox(200, 200){}}
\end{picture}
\caption{We need to add again, and we find some
$\phi_1\in \Phi_1$ such that some restriction
$\phi_1|_{A}$ or its inverse $\phi_1|_{A}^{-1}$ has image
disjoint to both the domain and image of
$\bar{\theta}_0$. Then, as indicated later, we
can find $\hat{\theta}_1$ either of the form
$\phi_1|_A^{\pm}$ or $\phi_1|_A^{\pm}\circ
\bar{\theta}_1^{-1}$ whose domain is disjoint from
the domain of $\hat{\theta}_0$ and whose range is
disjoint to both its domain and range. We add $\bar{\theta}_1$ to
$\Psi_1$ to obtain $\Psi_2$ and subtract off
$\phi_1|_A$.}
\end{figure}
\begin{figure}[h]
\begin{picture}(200, 200)(0, 0)
\put(25, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(25, 25){}}
\put(80, 80){\framebox(25, 25){}}
\put(125, 125){\vector(-1, -1){28}}
\put(75, 150){\vector(1, 0){50}}
\put(110, 125){\makebox(0, 0){$\bar{\theta}_1$}}
\put(100, 165){\makebox(0, 0){$\bar{\theta}_0$}}
\put(0, 0){\framebox(200, 200){}}
\end{picture}
\caption{We insist that $\bar{\theta}_0, \bar{\theta}_1$ have disjoint domains and
that the range of $\bar{\theta}_1$ is entirely new.
After this we keep going, finding some $\bar{\theta_2}$ whose domain
is disjoint from the domains of $\bar{\theta}_0$ and
$\bar{\theta}_1$ and is, relative to these two morphisms,
interdefinable with some element of $\Phi_2$. We do insist that
it pick up some more of the space in its image, though we do not
object if its domain is included in the {\it range} of one of the
earlier functions.}
\end{figure}
\begin{figure}[h]
\begin{picture}(200, 200)(0, 0)
\put(25, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(25, 25){}}
\put(80, 80){\framebox(25, 25){}}
\put(125, 125){\vector(-1, -1){28}}
\put(75, 150){\vector(1, 0){50}}
\put(110, 125){\makebox(0, 0){$\bar{\theta}_1$}}
\put(100, 165){\makebox(0, 0){$\bar{\theta}_0$}}
\put(0, 0){\framebox(200, 200){}}
\put(80, 80){\framebox(10, 10){}}
\put(80, 40){\framebox(10, 10){}}
\put(85, 80){\vector(0, -1){30}}
\put(75, 70){\makebox(0, 0){$\bar{\theta}_2$}}
\end{picture}
\caption{The domain of $\bar{\theta}_2$ is included in the image of the earlier functions, but its
image is new.
After this we keep going to add $\bar{\theta}_3$,
spreading out to new domain.
And so on.}
\end{figure}
\begin{figure}[h]
\begin{picture}(200, 200)(0, 0)
\put(25, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(25, 25){}}
\put(80, 80){\framebox(25, 25){}}
\put(125, 125){\vector(-1, -1){28}}
\put(75, 150){\vector(1, 0){50}}
\put(110, 125){\makebox(0, 0){$\bar{\theta}_1$}}
\put(100, 165){\makebox(0, 0){$\bar{\theta}_0$}}
\put(0, 0){\framebox(200, 200){}}
\put(80, 80){\framebox(10, 10){}}
\put(80, 40){\framebox(10, 10){}}
\put(85, 80){\vector(0, -1){30}}
\put(75, 70){\makebox(0, 0){$\bar{\theta}_2$}}
\put(160,125){\framebox(10, 10){}}
\put(165, 125){\vector(0, -1){80}}
\put(170, 85){\makebox(0, 0){$\bar{\theta}_3$}}
\put(160,35){\framebox(10, 10){}}
\end{picture}
\caption{The next morphism $\bar{\theta}_3$ takes its domain from the image of
$\bar{\theta}_0$. We do not rule out
returning to the images of much earlier morphisms.}
\end{figure}
\begin{figure}[h]
\begin{picture}(200, 200)(0, 0)
\put(25, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(50, 50){}}
\put(125, 125){\framebox(25, 25){}}
\put(80, 80){\framebox(25, 25){}}
\put(125, 125){\vector(-1, -1){28}}
\put(75, 150){\vector(1, 0){50}}
\put(110, 125){\makebox(0, 0){$\bar{\theta}_1$}}
\put(100, 165){\makebox(0, 0){$\bar{\theta}_0$}}
\put(0, 0){\framebox(200, 200){}}
\put(80, 80){\framebox(10, 10){}}
\put(80, 40){\framebox(10, 10){}}
\put(85, 80){\vector(0, -1){30}}
\put(75, 70){\makebox(0, 0){$\bar{\theta}_2$}}
\put(160,125){\framebox(10, 10){}}
\put(165, 125){\vector(0, -1){80}}
\put(170, 85){\makebox(0, 0){$\bar{\theta}_3$}}
\put(160,35){\framebox(10, 10){}}
\put(95,80){\framebox(10, 10){}}
\put(105, 80){\vector(1, -1){20}}
\put(125,50){\framebox(10, 10){}}
\put(120,90){\makebox(0, 0){$\bar{\theta}_4$}}
\end{picture}
\caption{In this way we eventually ensure that all the space except for
dom$(\bar{\theta}_0)$ is in the range of some $\bar{\theta}_\alpha$.}
\end{figure}
\newpage
Thus the general
idea of this construction is to steadily transfer across pieces of
the $\P_\alpha$'s to the $\Psi_\alpha$'s, so that $\P_\alpha\cup\Psi_\alpha$
continues to graph $E$. The crucial part of this is (g). It tells us that when
we remove a single piece $\p_\alpha|_{A^\alpha_0}$ of a morphism
$\p_\alpha\in \P_\alpha$ then we are compensating be placing
into $\Psi_{\alpha+1}$
a morphism, $\bar{\theta}_\alpha$,
which can reconstruct $\p_\alpha|_{A^\alpha_0}$ using only
{\it pre-existing morphisms} already placed into $\Psi_\alpha$.
As we continue through the construction, and survey the construction at
ever larger ordinals $\beta$, the $\Psi_\beta$ sets only get bigger,
and our ability to write $\p_\alpha|_{A^\alpha_0}$ as a word from
$\Psi_\beta$ is never endangered.
The other parts of this construction are less vital. (a) and (d) are
bookkeeping requirements, describing how we add to the $\Psi_\alpha$'s and
remove from the $\Phi_\alpha$'s. (f) actually follows from the other clauses.
(e) ensures that partial morphisms in the $\Psi_\alpha$'s will
eventually have some morphism as their union, which in turn will give us
$\hat\p_0$ described in the statement of \ref{1}. (b) and (c) will enable
us to obtain the $(B_{n, k})$ sets with the structure indicated above.
(h) and (d) state that at limit ordinals we take an appropriate limit of the
process so far, with a union on the $\Psi_\alpha$ side and a kind of
``intersection" along the $\P_\alpha$'s.
\bigskip
We continue with this construction for as long as possible, eventually
arriving at some $(\Psi_\alpha)_{\alpha<\delta}, (\P_\alpha)_{\alpha<\delta}$
admitting no further extension. We will argue that this final ordinal $\delta$
is a successor ordinal, $\delta=\beta+1$, and that in some natural way
$\Psi_\beta\cup \P_\beta$ will yield $\hp_0$ and $\hP_0$ as required.
\bigskip
\no {\bf Claim(1):} $\delta$ is not a limit ordinal.
\medskip
\no{\bf Proof of claim:} Otherwise we could simply let
$\Psi_\delta=\bigcup_{\alpha<\delta}\Psi_\alpha$, and let $\P_\delta$
consist of
all $\p|_{A^\delta_{\infty,\p}}$ where $\p\in\P_\alpha$ some
$\alpha<\delta$ and
as in (h) above $A^\delta_{\infty, \p}=\bigcap\{A_1^\beta: \beta\geq
\alpha, \beta<\delta,
\p_\beta\subset\p\}$.
\hfill ($\square$Claim)
\bigskip
So from now on let us fix $\alpha$ with $\alpha + 1=\delta$. For each
$\beta\leq\alpha$ let
$B^\beta_0=$Dom$(\bar{\theta}_0)$, and for each $n\in\N$
let $B^\beta_{n+1}=\bigcup\{\theta[B_n^\beta]|
\theta\in\Psi_\beta\}$.
\bigskip
\no {\bf Claim(2):} For $\beta\leq\alpha$ and $n\neq m$ we have $B^\beta_n,
B^\beta_m$ disjoint.
\medskip
\no {\bf Proof of claim:} By clause (e) in our construction and transfinite
induction on
$\beta$.
\hfill ($\square$Claim)
\bigskip
\no {\bf Claim(3):} For $\beta\leq\alpha$ and $\theta \in \Psi_\beta$ we have
Dom$(\theta)\subset \bigcup_{n\in\N}B^\beta_n$; and thus
\[\bigcup_{n\in\N}B^\beta_n=\bigcup_{\theta\in\Psi_\beta}
{\rm Dom}(\theta)\cup{\rm Ran}(\theta).\]
\medskip
\no {\bf Proof of claim:} By clause (c) in our construction and induction
on $\beta$.
\hfill ($\square$Claim)
\bigskip
\no {\bf Claim(4):} For $\beta\leq \alpha$ and a.e. $x\in
\bigcup_{n\in\N}B^\beta_n$
either:
\leftskip 0.4in
\no (1) $x\notin$ Dom$(\theta)$ all $\theta\in\Psi_\beta$; or
\no (2) there exists $k$ and $\theta_0, \theta_1,..., \theta_k\in\Psi_\beta$
such that $\theta_k\circ\theta_{k-1}\circ...\circ\theta_0(x)$ is well defined
and not a member of Dom$(\theta)$ any $\theta\in\Psi_\beta$.
\leftskip 0in
\medskip
\no{\bf Proof of claim:} Otherwise suppose not; we define $B^\beta_{n,
\infty}$ to be the set of
$x\in B^\beta_n$ such that for every $k$ there exists $\theta_0,
\theta_1,...\theta_k\in \Psi_\beta$
with $\theta_k\circ\theta_{k-1}\circ...\circ\theta_0(x)$ well defined, and
observe that this set
will
have positive measure.
It then follows by
clause (c) of our construction that we may at each $m$ define a morphism
from $B^\beta_{m, \infty}$
to $B^\beta_{m+1, \infty}$ and thus for $m\leq m'$ we have $\mu(B^\beta_{m,
\infty})\leq
\mu(B^\beta_{m',\infty})$, and thus $(B^\beta_{m, \infty})_{m\geq n}$
provides
a sequence of disjoint sets with measure bounded away from zero, and a
contradiction to
$\mu(X)=1$.
\hfill($\square$Claim)
\bigskip
The next claim uses ergodicity for the first time.
\bigskip
\no {\bf Claim(5):} $X$ equals the union of the
Dom$(\theta)$, Ran$(\theta)$ for $\theta\in\Psi_\alpha$.
\medskip
\no {\bf Proof of claim:} Otherwise by ergodicity of $E$ and claims (3)
and (4)
we may find some
$\p\in \P_\alpha^{\pm 1}$, $m\in\N$, and non-null
$A$ such that
\[\p[A]\cap \bigcup_{n\in\N} B^\alpha_n =\emptyset,\]
\[A\subset{\rm Dom}(\p)\cap B^\alpha_m\]
and either
\leftskip 0.4in
\no (1) Dom$(\theta)\cap A=\emptyset$ all $\theta\in\Psi_\alpha$; or
\no (2) there exists $k$ and $\theta_0, \theta_1,..., \theta_k\in\Psi_\alpha$
such that $\theta_k\circ\theta_{k-1}\circ...\circ\theta_0(x)$ is well
defined all
$x\in A$
and $\theta_k\circ\theta_{k-1}\circ...\circ\theta_0[A]$ and
Dom$(\theta)$ are disjoint for any $\theta\in\Psi_\alpha$.
\leftskip 0in
\no We assume that (2) holds and
that $\p\in \P_\alpha$; the other cases are exactly similar.
\begin{figure}[h]
\begin{picture}(200, 200)
\put(27, 7){\makebox(0, 0){$\bigcup_{n\in\N} B_n^\alpha$}}
\put(0, 17){\framebox(200, 183){}}
\put(0,17){\framebox(170,83){}}
\put(27, 24){\makebox(0, 0){$B_n^\alpha$}}
\put(0,100){\framebox(170,50){}}
\put(27, 107){\makebox(0, 0){$B_{n+1}^\alpha$}}
\put(0, 150){\framebox(170,25){}}
\put(27, 157){\makebox(0, 0){$B_{n+2}^\alpha$}}
\put(0, 175){\framebox(170,25){}}
\put(27, 182){\makebox(0, 0){$B_{n+3}^\alpha$}}
\put(50, 50){\framebox(10,10){}}
\put(180, 50){\framebox(10,10){}}
\put(60, 55){\vector(1, 0){120}}
\put(90,60){\makebox(0, 0){$\varphi$}}
\put(50,65){\makebox(0, 0){$A$}}
\put(55, 60){\vector(0,1){60}}
\put(60, 85){\makebox(0, 0){$\theta_0$}}
\put(50, 120){\framebox(10,10){}}
\put(50, 160){\framebox(10,10){}}
\put(55, 130){\vector(0,1){30}}
\put(60, 140){\makebox(0, 0){$\theta_1$}}
\put(50, 180){\framebox(10,10){}}
\put(55, 170){\vector(0,1){10}}
\put(65, 171){\makebox(0, 0){$\theta_2$}}
\put(55, 185){\vector(1,-1){130}}
\put(130, 120){\makebox(0, 0){$\bar{\theta}_\alpha$}}
\end{picture}
\caption{A typical case: The image of $\varphi$ is what we want, but the domain intersects the
domain of morphisms already in $\Psi_\alpha$.}
\end{figure}
We can then let $\bar{\theta}_\alpha$ have domain
$\theta_k\circ\theta_{k-1}\circ...\circ\theta_0[A]$ and set
\[\bar{\theta}_\alpha(x)=\p\circ\theta_0^{-1}\circ
\theta_1^{-1}\circ...\theta_k^{-1}(x).\]
We let $A^\alpha_0=A$, $A^\alpha_1=$Dom$(\p)\setminus A^\alpha_0$,
$\Psi_{\alpha + 1}=\Psi_\alpha\cup\{\bar{\theta}_\alpha\}$,
$\P_{\alpha+1}=(\P_\alpha\setminus\{\p\})\cup\{\p|_{A^\alpha_1}\}$.
In this way we are able to contest another round, contradicting the
assumption that
the construction ground to a halt at $\delta$.
\hfill ($\square$Claim)
We can then finish up the proof of the lemma by letting $B_{n, k}$ be the
set of
$x\in B_k^\alpha$ such that there are $\theta_1, \theta_2,...\theta_{n-k}\in
\Psi_\alpha$
with $\theta_1\circ...\circ\theta_{n-k}(x)$ well defined and $n$
is the largest
such integer.
(In other words,
$\bigcup_{k\leq n} B_{n, k}$ is the set of elements whose orbit
under $\Psi_\alpha$ has size exactly $n+1$.)
We use the disjointness
of the morphisms in $\Psi_\alpha$ to define the longed for
$\hat{\p}_0$: For $x\in B_{n, k}$ we consider the unique $\theta\in
\Psi_\alpha$
with $x\in$Dom$(\theta)$ and let $\hat{\p}_0(x)=\theta(x).$
\end{proof}
We now let $B=\bigcup_{n\in\N}B_{n, 0}$. We are going to repeat the previous
step, relativizing the process to $B$.
\bigskip
\begin{lemma}
There is a graphing $\hat{\Phi}^*$ of $E$, containing $\hp_0$ along with a new
morphism $\hp^*$, with
$(C_{n, k})_{n\in\N, k\leq n}$ a partition of $B$, such that:
\noindent (1) $C_\mu(\hat{\Phi}^*)\leq C_\mu(\hat{\Phi}_0)$;
\no (2) $\hat{\p}^*[C_{n, k}]=C_{n, k+1}$ all $k0$, $\psi|_{C_i}$ equals some word built up from $\hp^*,
\hp_0$ restricted
to $C_i$.
\leftskip 0in
\end{lemma}
\begin{proof}
We may first of all assume without any loss of generality that
for each $\psi\in \hP_0\setminus\{\hp_0\}$ there are $k, \ell$ with
\[{\rm Dom}((\hp_0)^k\circ \psi\circ(\hp_0)^\ell),
{\rm Ran}((\hp_0)^k\circ \psi\circ(\hp_0)^\ell)\subset B.\]
\begin{figure}[h]
\begin{picture}(200,200)
\put(20, 0){\framebox(200, 200){}}
\put(10, 10){\makebox(0, 0){$B$}}
\put(20, 0){\framebox(200, 70){}}
\put(40, 10){\framebox(10,10){}}
\put(160, 10){\framebox(10,10){}}
\put(50, 15){\vector(1, 0){110}}
\put(40, 110){\framebox(10,10){}}
\put(160, 110){\framebox(10,10){}}
\put(165, 110){\vector(0,-1){90}}
\put(172, 90){\makebox(0, 0){$\hat{\varphi}^k$}}
\put(52, 90){\makebox(0, 0){$\hat{\varphi}^\ell$}}
\put(45, 20){\vector(0,1){90}}
\put(50, 115){\vector(1, 0){110}}
\put(100, 125){\makebox(0, 0){$\psi$}}
\end{picture}
\end{figure}
We may then consider the graphing $\hP^{\sharp}$ which for each
$\psi\in\hP_0,$
$\psi\neq\hp_0$, has the appropriate morphism
$(\hp_0)^k\circ \psi\circ(\hp_0)^\ell$ for $E|_B$.
With this granted it is straightforward to check that \ref{1}
applied to $E|_B$, $\mu_B=\frac{\mu|_B}{\mu(B)}$, $\hP^{\sharp}$,
produces the requisite $\hp^*$.
\end{proof}
Now we can define a new morphism $\hp_1$ with domain
\[\bigcup_{n\in\N, k0$ there is $\ell_i\in\Z$ such that
$\psi|_{D_i}=(\hp_1)^{\ell_i}|_{D_i}$.
\leftskip 0in
\no Plainly we can continue this indefinitely, obtaining a sequence
$(\hP_n, \hp_n)_{n\in\N}$
where at each $n$
\leftskip 0.4in
\no $C_\mu(\hP_n)\leq C_\mu(\hP)$;
\no $\hP_n$ is a graphing of $E$;
\no $\hp_{n}$ extends $\hp_{n-1}$ and $\mu({\rm Dom}(\hp_n))\geq 1-2^{-n}$;
\no for any $\psi\in \hP_{n-1}$ we can partition Dom$(\psi)$ into
$(D_i)_{i\in\N}$ such that
\leftskip 0.6in
\no (a) $\psi|_{D_0}\in \hP_n$;
\no (b) for each $i>0$ there is $\ell_i\in\Z$ such that
$\psi|_{D_i}=(\hp_n)^{\ell_\infty}|_{D_i}$.
\leftskip 0in
In the end we let
\[\hp_\infty=\bigcup_{n\in\N}\hp_n\] and for each $\psi\in\hP_1$ we place into
$\hP_\infty$ the morphism
\[\psi|_{A_{\infty, \psi}},\]
where $A_{\infty, \psi}$ equals
\[\bigcap \{D: \exists n\exists \psi'\in \hP_n (\psi'\subset\psi, D={\rm
Dom}(\psi'))\}.\]
By considering the measure of the domain we actually have
\[\hp_\infty:X\rightarrow X\]
(almost everywhere defined). By the nature of the definition of
$\hP_\infty$ and
the assumptions on the various $\hP_n$ we have that
for any $\psi\in \hP_n$ we can partition Dom$(\psi)$ into $(D_i)_{i\in\N}$
such that
\leftskip 0.4in
\no (a) $\psi|_{D_0}\in \hP_\infty$;
\no (b) for each $i>0$ there is $\ell_i\in\Z$ such that
$\psi|_{D_i}=(\hp_1)^{\ell_i}|_{D_i}$.
\leftskip 0in
This gives us a new graphing $\hP_\infty$ of $E$
containing a morphism $\hp_\infty:X\rightarrow X$ with
$C_\mu(\hP_\infty)\leq C_\mu(\P)$.
We are now going to take that whole step over again, adding in a new
morphism but
keeping hold of $\hp_\infty$ and not allowing it to be changed.
This requires relativizing \ref{1} to $\hp_\infty$.
\begin{lemma}
\label{2}
Let $E$, $\hP_\infty$, $\hp_\infty$, be as above.
Then there is a graphing $\hat{\Theta}_0$ of $E$ which still contains
$\hp_\infty$, and a morphism $\hat{\theta}_0\in\hat{\Theta}_0$, and
$(D_{n, k})_{n\in\N, k\leq n}$ a partition of $X$, such that:
\leftskip 0.4in
\noindent (1) $C_\mu(\hat{\Theta}_0)\leq C_\mu(\hP_\infty)$;
\no (2) $\hat{\theta}_0[D_{n, k}]=D_{n, k+1}$ all $k0$, $\psi|_{C_i}$ equals some word in
$\hat{\theta}_0, \hp_\infty$ restricted to $C_i$.
\leftskip 0in
\end{lemma}
\begin{proof}
This closely parallels the proof of \ref{1}. There is a difference
in how we show we can continue at inductive steps.
We build graphings
\[(\Theta_\alpha)_{\alpha< \delta}, (\Gamma_\alpha)_{\alpha < \delta},\]
and morphisms $\theta_\alpha\in\Gamma_\alpha$:
\leftskip 0.4in
\no (a) $\Theta_0$ is empty; $\Gamma_0=\hP_\infty\setminus \{\hp_\infty\}$;
\no (b) $\Theta_1$ consists in a single morphism $\hat{\rho}$, where for some
$k, \ell$, and $A=\hp_\infty^{-k}[{\rm Dom}(\rho)]$, we have
\[\hp_\infty^\ell\circ\hat{\rho}\circ\hp_\infty^k|_A\in \hP_\infty;\]
for all $\alpha<\delta$ and $\theta\in \Theta_\alpha$ we
have
Ran$(\theta)\cap$ Dom$(\theta)$ empty;
\no (c) if $\alpha+1< \delta$, $\alpha>0$,
and $\theta\in \Theta_{\alpha +1}$, then
Dom$(\theta)\subset$ Ran$(\theta')$ some $\theta'\in \Theta_\alpha$;
\no (d) for $\alpha\leq \beta$ we have $\Theta_\alpha\subset \Theta_\beta$
and at
$\lambda$ a limit ordinal we have
$\Theta_\lambda=\bigcup_{\alpha<\lambda}\Theta_\alpha$;
\no (e) if $\p, \p'\in \Theta_\alpha$ are distinct, then their ranges are
disjoint
and their domains are disjoint;
\no (f) each $\Theta_\alpha\cup\Gamma_\alpha\cup\{\hp_\infty\}$ graphs $E$;
\no (g) $\theta_\alpha\in \Gamma_\alpha$ is the only morphism not appearing in
$\Gamma_{\alpha +1}$ and for this $\theta_\alpha$ there is a partition of
Dom$(\theta_\alpha)$ into $A_0^\alpha, A_1^\alpha$ such that
\leftskip 0.6in
\no $\theta_\alpha|_{A_1^\alpha}\in\Gamma_{\alpha+1}$;
\no there are $\psi_1, ..., \psi_\ell, \hat{\psi}_1, ..., \hat{\psi}_k\in
(\Theta_\alpha\cup\{\hp_\infty\})^\pm$, and $\bar{\theta}_\alpha\in
\Theta_{\alpha+1}$, with
\[{\rm
Dom}(\bar{\theta}_\alpha)=\hat{\psi}_1\circ...\hat{\psi}_k[A_0^\alpha]\]
and we have either
\[\theta_\alpha|_{A^\alpha_0}=\psi_1\circ\psi_2\circ...\psi_\ell\circ
\bar{\theta}_\alpha\circ\hat{\psi}_1\circ...\circ\hat{\psi}_k|_{A_0^\alpha}\]
or
\[(\theta_\alpha|_{A^\alpha_0})^{-1}=\psi_1\circ\psi_2\circ...\psi_\ell\circ
\bar{\theta}_\alpha\circ\hat{\psi}_1\circ...\circ\hat{\psi}_k|_{A_0^\alpha}\]
\leftskip 0.4in
\no (h) if $\lambda$ is a limit then for $\alpha<\lambda$ and
$\p\in\Gamma_\alpha$,
we either have
$\p\in \Gamma_\lambda$ or we have $\p|_{A^\lambda_{\infty, \p}}\in
\Gamma_\lambda$,
where
\[A_{\infty, \p}^\lambda=\bigcap\{A^\beta_1: \beta\geq\alpha,
\theta_\beta\subset \p\}.\]
\leftskip 0in
\bigskip
Again this construction stops at some successor ordinal $\delta=\alpha+1$, and
as before at each $\beta\leq\alpha$ and $n\in\N$ we can let
\[D^\beta_0={\rm Dom}(\hat{\rho}),\]
\[D^\beta_{n+1}=\{\theta[D_n^\beta] : \theta\in \Theta_\beta, n\in\N\}.\]
Again $n\neq m$ implies $D^\beta_n$ and $D^\beta_m$ are disjoint. And again
$\bigcup\{{\rm Dom}(\theta)\cup{\rm Ran}(\theta): \theta\in\Theta_\beta\}$
equals $\bigcup_{n\in\N}D^\beta_n$. And again the real battle is to show
that $\bigcup_{n\in\N}D^\alpha_n=X$, and for this time around we have some
more
work. Suppose $\bigcup_{n\in\N}D^\alpha_n \neq X$, and we try
to show that after all we could have continued to define $\Theta_{\alpha+1}$,
$\Gamma_{\alpha+1}$, $\theta_{\alpha}$, $\bar{\theta}_\alpha$.
\bigskip
\no{\bf Definition} Let $F$ be the equivalence
relation on $X$ induced by the graphing
$\Theta_\alpha\cup\{\hp_\infty\}$.
\bigskip
\no{\bf Case 1} $F$ is ergodic.
\bigskip
Then we can choose some $\theta_\alpha\in \Gamma_\alpha$, words
$\psi, \hat{\psi}$ built up from $\Theta_\alpha\cup\{\hp_\infty\}$,
$A^\alpha_0\cup A_1^\alpha$ partitioning Dom$(\theta_\alpha)$, with
\[\hat{\psi}^{-1}[A_0^\alpha]\subset\bigcup_{n\in\N}D^\alpha_n\setminus
\bigcup\{{\rm Dom}(\theta)| \theta\in\Theta_\alpha\}\]
\[{\psi}\circ\theta_\alpha
[A_0^\alpha]\subset X\setminus\bigcup_{n\in\N}D^\alpha_n.\]
After shrinking we may assume $A^\alpha_0\subset$ Ran$(\theta)$ some
single $\theta\in \Theta_\alpha$, and then we can let
$\bar{\theta}_\alpha=\psi\circ\theta_\alpha\circ\hat{\psi}|_{\hat{\psi}^{-1}
[A^\alpha_0]}$.
\begin{figure}[h]
\begin{picture}(300,200)
\put(20, 0){\framebox(200, 200){}}
\put(95, 60){\makebox(0, 0){$\bigcup D^\alpha_n\setminus\bigcup{\rm Dom}(\theta)$}}
\put(20, 0){\framebox(200, 70){}}
\put(40, 10){\framebox(10,10){}}
\put(160, 10){\framebox(10,10){}}
\put(50, 15){\vector(1, 0){110}}
\put(40, 110){\framebox(10,10){}}
\put(160, 110){\framebox(10,10){}}
\put(165, 110){\vector(0,-1){90}}
\put(172, 90){\makebox(0, 0){$\psi$}}
\put(52, 90){\makebox(0, 0){$\hat{\psi}$}}
\put(45, 129){\makebox(0, 0){$A_0^\alpha$}}
\put(45, 20){\vector(0,1){90}}
\put(50, 115){\vector(1, 0){110}}
\put(100, 125){\makebox(0, 0){$\theta_\alpha$}}
\put(140, 0){\framebox(80,70){}}
\put(195, 60){\makebox(0, 0){$X\setminus\bigcup_n D^\alpha_n$}}
\end{picture}
\caption{$\empty$}
\end{figure}
\bigskip
\no{\bf Case 2} $F$ is not ergodic.
\bigskip
Then it follows that we may find $Y_1\subset \bigcup_{n\in\N} D^\alpha_n$,
$Y_2\subset X\setminus (\bigcup_{n\in\N} D^\alpha_n)$,
\[0<\mu(Y_1),\mu(Y_2),\]
and for all $y\in Y_1$ the equivalence class
$[y]_F$ is disjoint from $Y_2$.
However $E$ is ergodic and graphed by
$\Theta_\alpha\cup\Gamma_\alpha\cup\{\hp_\infty\}$, and so we may find
words $\psi_1, \psi_2, ..., \psi_\ell$ from
$\Theta_\alpha\cup\{\hp_\infty\}$ and
$\tau_1, \tau_2,..., \tau_{\ell-1}\in\Gamma_\alpha$ with
\[\psi_\ell\circ\tau_{\ell -1}\circ\psi_{\ell -1}\circ\tau_{\ell
-2}...\circ \psi_1[Y_1]
\subset X\setminus \bigcup_{n\in\N}D^\alpha_n,\]
\[\psi_{\ell -1}\circ\tau_{\ell -2}...\circ \psi_1[Y_1]
\subset \bigcup_{n\in\N}D^\alpha_n.\]
\begin{figure}[h]
\begin{picture}(300,200)
\put(20, 0){\framebox(200, 200){}}
\put(95, 60){\makebox(0, 0){$\bigcup D^\alpha_n\setminus\bigcup{\rm Dom}(\theta)$}}
\put(20, 0){\framebox(200, 70){}}
\put(40, 10){\framebox(10,10){}}
\put(160, 10){\framebox(10,10){}}
\put(50, 15){\vector(1, 0){110}}
\put(40, 110){\framebox(10,10){}}
\put(160, 110){\framebox(10,10){}}
\put(165, 110){\vector(0,-1){90}}
\put(172, 90){\makebox(0, 0){$\psi_\ell$}}
\put(55, 90){\makebox(0, 0){$\hat{\psi}^{-1}$}}
\put(35, 10){\makebox(0, 0){$Z_1$}}
\put(45, 20){\vector(0,1){90}}
\put(50, 115){\vector(1, 0){110}}
\put(100, 125){\makebox(0, 0){$\tau_{\ell -1}$}}
\put(140, 0){\framebox(80,70){}}
\put(195, 60){\makebox(0, 0){$X\setminus\bigcup_n D^\alpha_n$}}
\end{picture}
\caption{$\empty$}
\end{figure}
Again after possibly refining $Y_1$ we may assume there is some word
$\hat{\psi}$ from $\Theta_\alpha$ such that
\[\hat{\psi}\circ\psi_{\ell-1}\circ\tau_{\ell-2}\circ\psi_{\ell-2}...\circ
\psi_1[Y_1]\subset
\bigcup_{n\in\N}D^\alpha_n\setminus\bigcup\{{\rm Dom}(\theta)|
\theta\in\Theta_\alpha\}.\]
And we go onto another round with
\[\bar{\theta}_\alpha=\psi_\ell\circ\tau_{\ell-1}\circ
\hat{\psi}^{-1}|_{Z_1},\]
\[\theta_\alpha=\tau_{\ell-1},\]
where $Z_1=\hat{\psi}\circ\tau_{\ell-2}\circ...\psi_1[Y_1]$.
\end{proof}
We then let $D=\bigcup_{n\in\N}D_{n, 0}$.
\bigskip
Here is probably a good point to pause and formulate the general result.
The proof of
this general technical lemma clearly follows from the above argument.
\begin{lemma}
\label{3.3} Let $F$ be an ergodic measure preserving equivalence relation on
standard Borel space $(Y, \nu)$, with all classes countable, $\nu$ a finite
Borel measure.
Let
$\Theta$ be a graphing of $F$ containing morphisms $\{\psi_1, \psi_2, ...,
\psi_n\}$.
Let $A\subset Y$ be a set whose saturation under $\{\psi_1, \psi_2, ...,
\psi_n\}$ is
conull -- that is to say, for almost all $x\in Y$ there is some $y\in A$
and word
$\varphi_w$ from $\{\psi_1, \psi_2, ..., \psi_n\}$ with $\varphi_w(y)=x$.
Suppose further
more that $C_\nu(\Theta)\geq C_\nu(\{\psi_1, \psi_2, ..., \psi_n\})+\mu(A)$
and there is
some $\bar{\psi}\in \Theta\setminus\{\psi_1, \psi_2, ..., \psi_n\}$ having
{\rm Dom}$(\bar{\psi})$,
{\rm Ran}$(\bar{\psi})$ disjoint subsets of $A$.
Then there is a graphing $\Theta^*$ of $F$ and a morphism $\psi^*$ for $F$
such that:
\leftskip 0.4in
\no (1) $C_\nu(\Theta^*)\leq C_\nu(\Theta)$; and if $\Theta$ is a treeing
then so too
$\Theta^*$;
\no (2) for some partition $(Y_{n, k})_{n\in\N, k\leq n}$ of $A$ we have
\[\psi^*[Y_{n,k}]=Y_{n, k+1}\]
all $k0$, $\psi|_{C_i}$ equals some word in $\{\psi_1, \psi_2,
..., \psi_n, \psi^*\}$
restricted to $C_i$.
\leftskip 0in
\end{lemma}
With this general formulation observed and set to one side, let us continue
with the
proof for the specific case in front of us.
\bigskip
\begin{lemma}
There is a graphing $\hat{\Theta}^*_0$ of $E$, containing $\hp_\infty$,
$\hat{\theta}_0$,
along with a new morphism $\hat{\theta}^*$, and there is
$(H_{n, k})_{n\in\N, k\leq n}$, a partition of $D$, such that:
\leftskip 0.4in
\noindent (1) $C_\mu(\hat{\Theta}^*_0)\leq C_\mu(\hat{\Theta}_0)$;
\no (2) $\hat{\theta}^*[H_{n, k}]=H_{n, k+1}$ all $k0$, $\psi|_{C_i}$ equals some word built up from
$\hat{\theta}^*,
\hat{\theta}_0,
\hp_\infty$ restricted
to $C_i$.
\leftskip 0in
\end{lemma}
\medskip
\begin{proof}
We apply the lemma to $\hat{\Theta}_0$ for $\Theta$,
$D$ for $A$, $\{\hat{\varphi}_\infty, \hat{\theta}_0\}$
for $\{\psi_1, ..., \psi_n \}$ to obtain
$(H_{n, k})_{n\in\N, k\leq n}$ partitioning $A$ and
$\hat{\theta}^*$ as required. \end{proof}
%
%
%Note that by subdividing $\hat{\psi}_\infty$ to
%various measurable
%sets and conjugating by appropriate powers of $\hat{\theta}_0$,
%we may find some sequence of morphisms
%$\{\psi_1, \psi_2, ..., \psi_n\}$ such that
%$\{\psi_1, \psi_2, ..., \psi_n, \hat{\theta}_0\}$ and
%$\{\hat{\theta}_0, \hat{\theta}_0\}$ have the same cost and give rise to the
%same equivalence relation. Each $\psi_i$ will have the form
%\[\psi_i=\hat{\theta}_0^\ell\circ
%\hat{\varphi}_\infty\circ\hat{\theta}^k_0|_B\] for some
%suitable $\ell, k\in\Z$ and $B\subset X$.
%
%We may in a similar manner obtain a graphing $\Theta$ for $E|_D$ such that
%$\mu(X-D)+C_\mu(\Theta)=C_\mu(\hat{\Theta}_0)$,
%\[\{\psi_1, \psi_2, ..., \psi_n\}\subset \Theta,\]
%and for each $\psi\in \Theta$ there is $\hat{\psi}\in\hat{\Theta}_0$
%such that
%\[\psi=\hat{\theta}_0^\ell\circ
%\hat{\psi}\circ\hat{\theta}^k_0|_B\] for some
%suitable $\ell, k, B$.
%Applying lemma \ref{3.3} to this graphing $\Theta$ of $E|_D$ we obtain
%$\Theta^*$ as indicated there, and it is easily seen that
%$\hat{\Theta}^*_0=(\Theta^*\setminus\{\psi_1, \psi_2, ..., \psi_n\})
%\cup\{\hat{\theta}_0,\hp_\infty\}$ is as required.
% \hfill ($\square$Claim)
With this claim granted, we can mimic earlier arguments and
choose $\hat{\theta}_0^*\supset \hat{\theta}^*$
with $\mu({\rm Dom}(\hat{\theta}_0^*))=\mu({\rm Dom}(\hat{\theta}^*)) +
\mu({\rm Dom}(\hat{\theta}^*))$, and $\{\hat{\theta}^*\}$ graphing the
same equivalence relation as $\{\hat{\theta}^*, \hat{\theta}_0\}$.
And then we may clearly continue with this over and over, obtaining at
each $n$
$\hat{\Theta}^*_n$ and $\hat{\theta}^*_n$ such that:
\leftskip 0.4in
\no $C_\mu(\hat{\Theta}^*_n)\leq C_\mu(\hat{\Theta}_0)$;
\no $\hat{\Theta}_n^*$ is a graphing of $E$
containing $\hat{\theta}^*_n, \hp_\infty$;
\no $\hat{\theta}_{n}^*$ extends
$\hat{\theta}_{n-1}^*$ and $\mu({\rm Dom}(\hat{\theta}_n^*))\geq
1-2^{-n}$;
\no for any $\psi\in \hat{\Theta}_0$ we can partition Dom$(\psi)$ into
$(D_i)_{i\in\N}$ such that
\leftskip 0.6in
\no (a) $\psi|_{D_0}\in \hat{\Theta}_n^*$;
\no (b) for each $i>0$ $\psi|_{D_i}$ can be written
in a word in $\hat{\theta}_n^*$, $\hp_\infty$.
\leftskip 0in
Continuing in this fashion we obtain some
\[\hat{\theta}_\infty=\bigcup_n\hat{\theta}^*_n,\]
and as before we may define $\Phi'$ to be the appropriate limit of the
$\hat{\Theta}_n^*$, thereby completing the proof of
\ref{mainlemma} in the case that $C_\mu(\Phi)\geq 2$.
The general case of cost greater than some arbitrary integer is clearly
exactly similar. We may also observe that the last step from this argument
suggests the following modification:
\begin{lemma}
\label{3.4} Let $F$ be an ergodic measure preserving equivalence relation on
standard Borel space $(Y, \nu)$, with all classes countable, $\nu$ a finite
Borel measure.
Let
$\Theta$ be a graphing of $F$ containing morphisms $\{\psi_1, \psi_2, ...,
\psi_n\}$.
Let $A\subset Y$ be a set whose saturation under $\{\psi_1, \psi_2, ...,
\psi_n\}$ is
conull -- that is to say, for almost all $x\in Y$ there is some $y\in A$
and word
$\varphi_w$ from $\{\psi_1, \psi_2, ..., \psi_n\}$ with $\varphi_w(y)=x$.
Suppose further
more that $C_\nu(\Theta)\geq C_\nu(\{\psi_1, \psi_2, ..., \psi_n\})+\mu(A)$
and there is
some $\bar{\psi}\in \Theta\setminus\{\psi_1, \psi_2, ..., \psi_n\}$ having
{\rm Dom}$(\bar{\psi})$,
{\rm Ran}$(\bar{\psi})$ disjoint subsets of $A$.
Then there is a graphing $\Theta^*$ of $F$ and a morphism $\psi^*$ for $F$
such that:
\leftskip 0.4in
\no (1) $C_\nu(\Theta^*)\leq C_\nu(\Theta)$; and if $\Theta$ is a treeing
then so too
$\Theta^*$;
\no (2) $\psi^*: A\rightarrow A$; $\psi^*\supset\bar{\psi}$;
\no (3) for each $\p\in \Theta^*\setminus\{\psi_1, ...,\psi_n, \psi^*\}$ we
have
$\p=\psi|_C$ some $C\subset Y$, $\psi\in\Theta$;
\no (4) for $\psi\in \Theta$ there is a partition $(C_i)_{i\in\N}$ such that
\leftskip 0.6in
\no (i) $\psi|_{C_0}\in \Theta^*$;
\no (ii) at $i>0$, $\psi|_{C_i}$ equals some word in $\{\psi_1, \psi_2,
..., \psi_n, \psi^*\}$
restricted to $C_i$.
\leftskip 0in
\end{lemma}
\section{Corollaries}
\begin{lemma}
A treeable ergodic measure preserving equivalence relation $E$ with
countable classes on a
standard Borel probability space has cost $n$ if and only if it is induced by
some free action of $\F_n$.
\end{lemma}
\begin{proof} The {\it if} direction is known from \cite{gaboriau}, so we
concentrate on the
converse.
We begin with a treeing $\Phi$ of $E$; by \cite{gaboriau}, $C_\mu(\Phi)=n$.
Applying the
argument of the last section we can find an alternative graphing $\Theta$
containing
$\theta_1, ...,\theta_n$, each
\[\theta_i: X\rightarrow X,\]
and with
\[C_\mu(\Theta)\leq C_\mu(\Phi).\]
Since $n=C_\mu(E)\leq C_\mu(\Theta)\leq C_\mu(\Phi)=n,$ we have equality
throughout and
hence $\Theta=\{\theta_1, ..., \theta_n\}$.
\end{proof}
\begin{lemma} Let $E$ be an ergodic measure preserving equivalence relation
with
countable classes on a standard Borel probability space $(X, \mu)$. If $E$
has infinite
cost and is treeable, then there is a free
action of $\F_\infty$ giving rise to $E$ as its
orbit equivalence relation.
\end{lemma}
\begin{proof} Let $\Theta=\{\p_1, ...,\p_n,...\}$ be a treeing of $E$ with
infinite
cost. Without loss we may assume that each Dom$(\p_n)$ is disjoint from
Ran$(\p_n)$.
Then iterating lemma \ref{3.4} we may find successive treeings
\[\Theta_1, \Theta_2, ...., \Theta_m,...\] and morphism $\psi_1,...,
\psi_m,...$ and
measurable sets $(A_{n, m})_{mm$ we may partition Dom$(\p_m)$ up into $(B_i)_{i\in\N}$
such that
\leftskip 0.6in
\no (i) $B_0=A_{n, m}$, and so $\varphi_n|_{B_0}\in \Theta_m$;
\no (ii) each $\varphi_n|_{B_i}$ can be written as the restriction of a
word in
$\{\psi_1, ..., \psi_m\}$.
\leftskip 0in
We finish with $\{\psi_i: i\in\N\}$ as a graphing of $E$. Since each
$\Theta_m$ is a treeing so too is the limit, $\{\psi_i: i\in\N\}$.
Since each $\psi_i$ is total and since they jointly give rise to a treeing,
we thus obtain the free action of $\F_\infty$.
\end{proof}
\begin{lemma} Let $E$ be an ergodic measure preserving equivalence relation
with
countable classes on a standard Borel probability space $(X, \mu)$.
If $E$ is treeable, then there is a free
action of a countable group $G$ giving rise to $E$ as its
orbit equivalence relation.
\end{lemma}
\begin{proof} We at once can assume the cost is finite, or else the result
follows
with $G=\F_\infty$ from the last lemma.
By earlier results we may assume there is a treeing $\Theta$ and some
$\p\in\Theta$ which is total.
By Dye's theorem on the orbit equivalence of ergodic $\Z$-actions,
we can assume that there is a sequence of subsets of $X$,
$(A_i)_{i\in\N}$, such that each
\[\mu(A_i)=2^{-i},\]
\[ A_{i+1}\subset A_i,\]
\[\p^{2^i}: A_{i+1}\rightarrow A_i,\]
and $\{A_{i+1}, \p^{2^i}[A_{i+1}]\}$ partitioning $A_i$.
At each $i$ we let $\p_i:A_{i+1}\rightarrow A_i$ be given by
\[\p_i=\p^{2^i}|_{A_{i+1}};\]
note that $\{\p_i:i\in\N\}$ graphs the same equivalence relation as $\{\p\}$.
We then build $(k_i)_{i\in\N}$, $k_0\in\N$, each $k_{i+1}\in\{0, 1\}$,
and morphisms
\[\psi_{i, j}: A_i\rightarrow A_i\]
for $j\ell$,
\[(a_\ell)^2=1,\]
\[a_\ell a_k=a_ka_\ell\]
all $k, \ell$.
For each $i\in\N$ we define a total function
$T_i: X\rightarrow X$ by first choosing for a.e. $x$ the unique
$m_0^x, m_1^x,..., m_{i-1}^x\in \{-1, 0\}$ such that
\[y_x=\p_{i-1}^{m_{i-1}^x}\circ \p_{i-2}^{m_{i-2}^x}\circ...\p_0^{m^x_0}(x)
\in A_i\]
and then letting
\[T_i(x)=\p_{0}^{-m_{0}^x}\circ
\p_{1}^{-m_{1}^x}\circ...\p_{i-1}^{-m^x_{i-1}}\circ
\p_i(y_x)\]
if $y_x\in A_{i+1}$,
\[T_i(x)=\p_{0}^{-m_{0}^x}\circ
\p_{1}^{-m_{1}^x}\circ...\p_{i-1}^{-m^x_{i-1}}\circ
\p_i^{-1}(y_x)\]
if $y_x\in A_i\setminus A_{i+1}$.
(In other words we recursively define each $T_i$ to be the unique $T_i:
X\rightarrow X$
of order 2 which extends $\p_i$ and commutes with $T_j$ all $j< i$.)
Similarly we define
for $j