\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