\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 $k<n$
\[\hat{\varphi}_0|_{B_{n, k}}: B_{n, k}\rightarrow B_{n, k+1}\] 
is a bijection. 
We also want to do this in such a way as we can obtain 
a new graphing containing $\hat{\varphi}_0$, for which the cost 
has not increased, and such that all the parts of morphisms 
which have been lost from the older graphing can be easily 
recovered as powers of $\hat{\varphi}_0$. 


\begin{lemma}
\label{1}
Let $E$ be as above, $\Phi$ a graphing of $E$.
Then there is 
a graphing $\hat{\Phi}_0$ of $E$, 
$\hat{\varphi}_0\in\hat{\Phi}_0$,
$(B_{n, k})_{n\geq 1, k\leq n}$ a partition of $X$, such that:

\leftskip 0.4in

\noindent (1) $C_\mu(\hat{\Phi}_0)\leq C_\mu(\Phi)$ (the cost has not 
increased);

\no (2) $\hat{\p}_0[B_{n, k}]=B_{n, k+1}$ all $k<n$ (the new morphism 
moves the elements of the partition in the prescribed manner);

\no (3) {\rm Dom}$(\hat{\varphi}_0)=
\bigcup_{k<n, n\in \N} B_{n, k}$ (the new morphism has the indicated 
domain);

\no (4) for each $\varphi\in \hat{\Phi}_0$ with 
$\varphi\neq\hat{\varphi}_0$ we have
\[\varphi=\psi|_C,\] some $C\subset X$, $\psi\in \Phi$ (the new 
graph consists just of the new morphism and restrictions of the old 
morphisms);

\no (5) for each $\psi\in \Phi$ there is a partition $(C_i)_{i\in\N}$ of 
$X$ such that

\leftskip 0.6in

\no (i) $\psi|_{C_0}\in \hat{\Phi}_0$;

\no (ii) and at $i>0$, $\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 $k<n$;

\no (3) Dom$(\hat{\varphi}^*)=\bigcup_{k<n, n\in \N} C_{n, k}$;

\no (4) for each $\varphi\in \hat{\Phi}^*$ with 
$\varphi\neq\hat{\varphi}^*, \hp_0$ we have
\[\varphi=\psi|_C,\] some $C\subset X$, $\psi\in \hat{\Phi}_0$;

\no (5) for each $\psi\in \hat{\Phi}_0$ there is a partition 
$(D_i)_{i\in\N}$ of $X$ such that

\leftskip 0.6in

\no (i) $\psi|_{D_0}\in \hat{\Phi}^*$;

\no (ii) and at $i>0$, $\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, k<n} B_{n,k}\cup\{x| \exists n(x\in B_{n, n}, 
\hp_0^{-n}(x)\in
\bigcup_{m\in\N, k<m} C_{m, k})\}.\]
This morphism $\hp_1$ will extend the old $\hp_0$, and so we simply set 
$\hp_1(x)=\hp_0(x)$
for $x\in \bigcup_{n\in\N, k<n} B_{n,k}$. For $x\in B_{n, n}$ and 
$\hp_0^{-n}(x)\in
\bigcup_{m\in\N, k<m} C_{m, k}$ we let
\[\hp_1(x)=\hp^*\circ\hp_0^{-n}(x).\]
 From this we obtain a new graphing $\hP_1$ of $E$ with
\[\hP_1=(\hP^*\setminus\{\hp_0, \hp^*\})\cup\{\hp_1\}.\]

Comparing $\hP_1$ with $\hP_0$ and $\hp_1$ with $\hp_0$ we discover the 
following:

\leftskip 0.4in

\no $C_\mu(\hP_1)\leq C_\mu(\hP_0)$;

\no $\hP_1$ is still a graphing of $E$;

\no $\hp_1$ extends $\hp_0$ and $\mu(X\setminus{\rm
Dom}(\hp_1))\leq\frac{1}{2}
\mu(X\setminus{\rm Dom}(\hp_0))$;

\no for any $\psi\in \hP_0$ we can partition Dom$(\psi)$ into 
$(D_i)_{i\in\N}$ such that

\leftskip 0.6in

\no (a) $\psi|_{D_0}\in \hP_1$;

\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

\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 $k<n$;

\no (3) {\rm Dom}$(\hat{\theta}_0)=\bigcup_{k<n, n\in \N} D_{n, k}$;

\no (4) for each $\varphi\in \hat{\Theta}_0$ with
$\varphi\neq\hat{\varphi}_\infty, 
\hat{\theta}_0$ we have
\[\varphi=\psi|_C,\] some $C\subset X$, $\psi\in \hP_\infty$;

\no (5) for each $\psi\in \hP_\infty$ there is a partition $(C_i)_{i\in\N}$ 
of $X$ such that

\leftskip 0.6in

\no (i) $\psi|_{C_0}\in \hat{\Theta}_0$;

\no (ii) and at $i>0$, $\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 $k<n$, $n\in\N$;

\no (3) {\rm Dom}$(\psi^*)=\bigcup_{n\in\N, k<n} Y_{n, k}$; and 
$\psi^*\supset \bar{\psi}$;

\no (4) for each $\p\in \Theta^*\setminus\{\psi_1, ...,\psi_n, \psi^*\}$ we 
have
$\p=\psi|_C$ some $C\subset Y$, $\psi\in\Theta$;

\no (5) 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}

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 $k<n$;

\no (3) Dom$(\hat{\theta}^*)=\bigcup_{k<n, n\in \N} H_{n, k}$;

\no (4) for each $\varphi\in \hat{\Theta}^*$ with $\varphi\neq\hat{\theta}^*,
\hat{\theta}_0, \hp_\infty$ we have
\[\varphi=\psi|_C,\] some $C\subset X$, $\psi\in \hat{\Theta}_0$;

\no (5) for each $\psi\in \hat{\Theta}_0$ there is a partition 
$(D_i)_{i\in\N}$ of $X$ such that

\leftskip 0.6in

\no (i) $\psi|_{D_0}\in \hat{\Theta}_0$;

\no (ii) and at $i>0$, $\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})_{m<n\in\N}$
such that

\leftskip 0.4in

\no (a) each $\Theta_m=\{\psi_1,...\psi_m, \p_{m+1}|_{A_{m+1, m}},
\p_{m+2}|_{A_{m+2, m}},...\}$;

\no (b) each $\psi_i: X\rightarrow X$ is total;

\no (c) each $\p_m$ can be written as a word in $\{\psi_1, ..., \psi_m\}$;

\no (d) for $n>m$ 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<k_i$, and treeings $\Theta_n$ for $E$ such that:

\leftskip 0.4in

\no (a) $\Theta_n=\{\p_i:i\in\N\}\cup\{\psi_{i, j}: i\leq n, j < k_i\}\cup
\{\theta|_{B_{\theta, n}}: \theta\in \Theta\},$
each $B_{\theta, n}$ some subset of Dom$(\theta)$;

\no (b) $C_\mu(\{\p_i: i\in\N\}\cup \{\psi_{i, j}: i\leq n, j < k_i\})\geq
C_\mu(\Theta)-2^{-n-1}=C_\mu(E)-2^{-n-1}$;

\no (c) for each $\theta\in\Theta$ we may partition $X$ into 
$(C_i)_{i\in\N}$ such that

\leftskip 0.6in

\no (i) $\theta|_{C_0}\in \Theta_n$;

\no (ii) each $\theta|_{C_{i+1}}$ equals some word in
$\{\p_i: i\in\N\}\cup \{\psi_{i, j}: i\leq n, j < k_i\}$.

\leftskip 0in

It follows from lemma \ref{3.4} that we may indeed construct such a
sequence. Given the graphing
$\hat{\Theta}_n=\{\p_i: i\in\N\}\cup \{\psi_{i, j}: i\leq n, j < k_i\}$,
or the
morally equivalent graphing
$\bar{\Theta}_n =\{\p \}\cup \{\psi_{i, j}: i\leq n, j < k_i\}$,
we can consider whether $C_\mu(E)\geq C_\mu(\hat{\Theta}_n)+ 2^{-n-1}$.
If no, we
just pass on with $k_{n+1}=0$; if yes, then we apply \ref{3.4} to obtain
some
\[\psi_{n+1,0}: A_{n+1}\rightarrow A_{n+1}\]
and graphing
\[\Theta_{n+1}=\{\p_i:i\in\N\}\cup\{\psi_{i, j}: i\leq n+1, j < k_i\}\cup
\{\theta|_{B_{\theta, n+1}}: \theta\in \Theta\},\]
and take the process to the next round.

This construction granted it follows from (c) that
\[\Theta_\infty=\{\p_i:i\in\N\}\cup\{\psi_{i, j}: i\in\N, j < k_i\}\]
graphs $E$. Since each $\Theta_n$ is a treeing it follows that $\Theta_\infty$
is a treeing. We will use it define a group action in some natural way.

We let $G$ be the group with generators $\{a_i: i\in\N\}$, $\{b_{i, j}: 
i\in\N,
j<k_i\}$. We will ask that this group be free subject to the relations
\[a_\ell b_{i, j}=b_{i, j} a_\ell\]
for $i>\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<k_i$
\[S_{i, j}(x)=\p_{0}^{-m_{0}^x}\circ 
\p_{1}^{-m_{1}^x}\circ...\p_{i-1}^{-m^x_{i-1}}\circ
\psi_{i, j}(y_x).\]

We want to show that if we let each $a_\ell$ act on $X$ via $T_\ell$ and
each $b_{i, j}$ act via $S_{i, j}$ then firstly it is well defined as an 
action of
$G$ and secondly that it is free a.e.

\medskip

\no {\bf Claim(1):}
\[S_{i, j}\circ T_\ell =T_\ell \circ S_{i, j}\]
all $\ell <i$,
\[T_\ell = T_\ell^{-1}\]
\[T_\ell \circ T_k =T_k \circ T_\ell\]
all $\ell, k$.

\medskip

\no {\bf Proof of claim:} This follows quickly from the definitions.
\hfill ($\square$Claim)

\medskip

Thus this assignment $a_\ell \mapsto T_\ell$, $b_{i, j}\mapsto S_{i,j}$ 
extends to
a homomorphism
\[G\rightarrow M_\infty(X),\]
\[g\mapsto \varphi_g,\]
where $M_\infty(X)$ is the group of invertible mpts on $X$ and gives
us a measure preserving action of $G$ on $X$.

\medskip

\no {\bf Claim(2):} If $\varphi_g(x)=x$ for a non-null collection of $x\in X$
then $g=1$.

\medskip

\no {\bf Proof of claim:}
Suppose $g$ is as above and for a non-null set of $x$ we have 
$\varphi_g(x)=x$.
We attempt to reduce $g$ down to 1 using the relations imposed as part of the
definition of $G$.

We may write the group element in the form
\[g=c_0c_1...c_M\]
where each $c_k$ equals either $a_{i(k)}$, $b_{i(k), j(k)}$, or
$b_{i(k), j(k)}^{-1}$. After possibly replacing each $c_k$ by a suitable
\[a_0^{-m_0}a_1^{-m_1}...a^{-m_{i(k)-1}}_{i(k)-1}c_k 
a^{m_{i(k)-1}}_{i(k)-1}...a_0^{m_0}\]
we may assume that there is a positive measure set $A\subset X$ such that 
for all
$x\in A$
\[\varphi_g(x)=x\]
{\it and} at each $k\leq M$ we have
\[U_{k+1}\circ U_{k+2}\circ...\circ U_M(x)\in A_{k(i)},\]
where each $U_\ell$ is respectively $T_{i(\ell)}, S_{i(\ell), j(\ell)},
S_{i(\ell), j(\ell)}^{-1}$, depending on whether
$c_\ell$ equals either $a_{i(\ell)}$, $b_{i(\ell), j(\ell)}$, or
$b_{i(\ell), j(\ell)}^{-1};$  the key point is that in $G$ the element 
$c_k$ equals $a_0^{-m_0}a_1^{-m_1}...a^{-m_{i(k)-1}}_{i(k)-1}c_k 
a^{m_{i(k)-1}}_{i(k)-1}...a_0^{m_0}$ as a consequence of the relations 
imposed in the definition of the group $G$. 
It then follows from $\Theta_\infty$ being a treeing that we may reduce the 
word
\[U_0\circ U_1\circ...U_M|_A\]
down to the identity by the operations of canceling various $U_\ell\circ 
U_{\ell +1}$
when $U_{\ell +1}=U_\ell^{-1}$. Thus in particular it follows that 
$c_0c_1...c_M$ will
easily reduce to the identity in $G$ and we are done.
\hfill ($\square$Claim)

\end{proof}











































\begin{thebibliography}{99}

\bibitem{dye} H. Dye, {\it On groups of measure preserving
transformations,}
{\bf American Journal of Mathematics,}
vol. 85(1963), pp. 551-576.



\bibitem{feldmanmoore} J. Feldman, C.C. Moore, {\it Ergodic
equivalence relations and von Neumann algebras,}
{\bf Transactions of the American Mathematical Society,}
vol. 234(1977), pp. 289-324.


\bibitem{furman} A. Furman,
{\it Orbit equivalence rigidity,}
{\bf Annals of Mathematics,}
vol. 150(1999), pp. 1083-1108.

\bibitem{gaboriau} D. Gaboriau, {\it Cout des relations d'equivalence et 
des groupes},
vol. 139(2000), pp. 41-98.
{\bf Inventiones Mathematicae}. 

%\bibitem{kechris} A.S. Kechris,
%{\it Lectures on costs of equivalence relations and groups,} available at
%http://www.caltech.edu/\~{}kechris

\bibitem{kechrismiller} A.S. Kechris, B. Miller,
{\bf Topics in Orbit Equivalence,} vol. 1852, Lecture 
Notes in Mathematics, Springer, Berlin, 2004. 

\bibitem{levitt} G. Levitt, {\it On the cost of generating an equivalence 
relation,}
{\bf Ergodic theory and dynamical systems,} vol. 15(1995), pp. 1173-1181.

\bibitem{popa} S. Popa, {\it A class of cross-product factors by free
groups, having trivial fundamental group}, preprint UCLA 2001.



\end{thebibliography}

\leftskip 0.5in







greg@math.ucla.edu

\bigskip



MSB 6363

UCLA

CA 90095-1555

\leftskip 0in

\end{document}
