A lemma for cost attained^{∗}

Greg Hjorth^{†}

May 28, 2005

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.

1 Introduction

Given an equivalence relation E one can consider the 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 [6] 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 [5] to obtain a kind of dichotomy theorem for amenability and [7] in an application to von Neumann algebras. The authors of [5] wrote up a proof of 1.1, though their organization is very different to the one below.

Proposition 1.1 Let E be an ergodic measure preserving equivalence relation on a standard Borel probability space (X, μ); assume that every equivalence class is countable. Let Φ be a graphing for E with C_{μ}(Φ) ≥ n.

Then there is an alternate graphing Φ′ for E which has no greater cost and contains n morphisms which are total that is to say –

(a) C_{μ}(Φ′) ≤ C_{μ}(Φ);

(b) and there are distinct bijections φ_{1}, ..., φ_{n} in Φ′ with φ_{i} : X → X.

One obtains additionally that if C_{μ}(Φ) ≤ n + 1 then we may further conclude Φ′ = {φ_{1}, φ_{2}, ..., φ_{n}, θ}, where θ : A → B is a bijection, some A, B ⊂ X.

Recall that a measurable equivalence relation is 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 [4] 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.

∗Key words and phrases: Ergodic theory, treeable equivalence relations, free groups, measure equivalence of groups AMS Subject Classification: 04A15, 28D15, 37A15.

†Partially supported by NSF grants DMS 99-70403, DMS 01-40503.

Corollary 1.2 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, 𝔽_{n}, which is free μ-a.e. and has E as its orbit equivalence relation.

We also show that in the case that E is treeable with infinite cost one may find a free action of 𝔽_{∞} giving rise to E. Appealing to the connections made in [3] 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.

Corollary 1.3 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 μ-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.

Furman in [3] 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.

2 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 everywhere when we only mean almost everywhere. ℕ begins with the number 0.

Definition A standard Borel space is a set X equipped with a σ-algebra B, such that B is the σ-algebra generated by some choice of a Polish topology on X. A standard Borel probability space is a standard Borel space equipped with a probability measure on its Borel sets.

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].

Definition If E is an equivalence relation on a standard Borel probability space (X, μ), and A, B ⊂ X measurable, then we say that a function

f : A → B

is a morphism (for E) if it is a bijection and

xEf(x)

all x ∈ A. We say that E is measure preserving if every morphism is a measure preserving function. We say that E is ergodic if every E-invariant set is either null or conull.

From [2], 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, [3] has shown that in general we may not be able to choose this group so that it acts freely on the space. Below we will prove that the additional assumption of treeability does ensure that we can choose the countable group so that it acts freely.

Definition Given a set Ψ of morphisms, a word built from Ψ is a morphism of the form

x ↦ ψ_{1}^{ϵ(1)} ∘ ψ_{2}^{ϵ(2)}... ∘ ψ_{n}^{ϵ(n)}(x),

where each ψ_{i} ∈ Ψ, each ϵ(i) ∈ {−1, 1}, and x ranges over a set on which these compositions make sense. The word is reduced if at no i do we have ϵ(i) = −ϵ(i + 1) along with ψ_{i} = ψ_{i+1}. A set of morphisms Ψ is said to be a graphing of E if for any xEy there is a word mapping x to y; the graphing is said to be a treeing if there is always a unique reduced word. Equivalently, Φ is a treeing if the adjacency relation xRy if there exists φ ∈ Φ with φ^{±1}(x) = y provides a tree structure on each equivalence class.

For Ψ a collection of morphisms we let Ψ^{−1} = {ϕ^{−1} : ϕ ∈ Ψ}.

3 Proof

We set about proving 1.1 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 3.1, states that we may find a new morphism φ̂_{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 ≥ 1 and k < n

φ̂_{0}|_{B_{n,k}} : B_{n,k} → 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 φ̂_{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 φ̂_{0}.

Lemma 3.1 Let E be as above, Φ a graphing of E. Then there is a graphing Φ̂_{0} of E, φ̂_{0} ∈ Φ̂_{0}, (B_{n,k})_{n≥1,k≤n} a partition of X, such that:

(1) C_{μ}(Φ̂_{0}) ≤ C_{μ}(Φ) (the cost has not increased);

(2) φ̂_{0}[B_{n,k}] = B_{n,k+1} all k < n (the new morphism moves the elements of the partition in the prescribed manner);

(3) Dom(φ̂_{0}) = ⋃_{k<n,n∈ℕ} B_{n,k} (the new morphism has the indicated domain);

(4) for each φ ∈ Φ̂_{0} with φ ≠ φ̂_{0} we have

φ = ψ|_{C},

some C ⊂ X, ψ ∈ Φ (the new graph consists just of the new morphism and restrictions of the old morphisms);

(5) for each ψ ∈ Φ there is a partition (C_{i})_{i∈ℕ} of X such that (i) ψ|_{C_{0}} ∈ Φ̂_{0}; (ii) and at i > 0, ψ|_{C_{i}} = (φ̂_{0})^{ℓ_{i}}|_{C_{i}}, some ℓ_{i} ∈ ℤ (we can recover the missing pieces of the old morphisms as powers of the new morphism).

Proof We assume that for distinct φ, φ′ ∈ Φ we always have φ(x) ≠ φ′(x) when both are defined. We may also assume there is some ψ̂ ∈ Φ with Ran(ψ̂)∩ Dom(ψ̂) empty.

We build transfinite sequences of graphings

(Ψ_{α})_{α<δ}, (Φ_{α})_{α<δ},

along with a choice of morphisms φ_{α} ∈ Φ_{α}, by induction on α so that:

(a) Ψ_{0} is empty; Φ_{0} = Φ;

(b) Ψ_{1} consists in a single morphism θ̄_{0} with Ran(θ̄_{0})∩Dom(θ̄_{0}) = ∅, θ̄_{0} ∈ Φ, μ(Dom(θ̄_{0})) ≠ 0; we set φ_{0} = θ̄_{0}, and for all α and θ ∈ Ψ_{α} we have Ran(θ)∩ Dom(θ) empty;

(c) if α + 1 < δ, α > 0, and θ ∈ Ψ_{α+1}, then Dom(θ) ⊂ Ran(θ′) some θ′ ∈ Ψ_{α};

(d) for α ≤ β we have Ψ_{α} ⊂ Ψ_{β} and at λ a limit ordinal we have Ψ_{λ} = ⋃_{α<λ} Ψ_{α};

(e) if φ, φ′ ∈ Ψ_{α} are distinct, then their ranges are disjoint and their domain are disjoint;

(f) each Ψ_{α} ∪ Φ_{α} graphs E;

(g) φ_{α} ∈ Φ_{α} is the only morphism not appearing in Φ_{α+1} and for this φ_{α} there is a partition of Dom(φ_{α}) into A_{0}^{α}, A_{1}^{α} such that

μ(A_{1}^{α}) ≠ 0; φ_{α}|_{A_{1}^{α}} ∈ Φ_{α+1}; there are ψ_{1}, ..., ψ_{ℓ}, ψ̂_{1}, ..., ψ̂_{k} ∈ Ψ_{α} ∪ Ψ_{α}^{−1}, and θ̄_{α} ∈ Ψ_{α+1}, with

Dom(θ̄_{α}) = ψ̂_{1} ∘ ...ψ̂_{k}[A_{0}^{α}]

and we have either

φ_{α}|_{A_{0}^{α}} = ψ_{1} ∘ ψ_{2} ∘ ...ψ_{ℓ} ∘ θ̄_{α} ∘ ψ̂_{1} ∘ ... ∘ ψ̂_{k}|_{A_{0}^{α}}

or

(φ_{α}|_{A_{0}^{α}})^{−1} = ψ_{1} ∘ ψ_{2} ∘ ...ψ_{ℓ} ∘ θ̄_{α} ∘ ψ̂_{1} ∘ ... ∘ ψ̂_{k}|_{A_{0}^{α}}

(h) if λ is a limit then for α < λ and φ ∈ Φ_{α}, we have φ ∈ Φ_{λ} if φ is in every earlier Φ_{α}, or otherwise we have φ|_{A_{∞,φ}^{λ}} ∈ Φ_{λ}, where

A_{∞,φ}^{λ} = ⋂{A_{1}^{β} : β ≥ α, φ_{β} ⊂ φ}.

In rough terms, we begin the construction by taking some θ̄_{0} in our original graphing which can be assumed to have disjoint range and image and simply adding it to Ψ_{1} and subtracting it from Φ_{0} to obtain Φ_{1}. We just describe the first few steps, without giving much in the way of proofs yet.

\overline{}θ̄_{0}

Figure 1: We need to add again, and we find some ϕ_{1} ∈ Φ_{1} such that some restriction ϕ_{1}|_{A} or its inverse ϕ_{1}|_{A}^{−1} has image disjoint to both the domain and image of θ̄_{0}. Then, as indicated later, we can find θ̂_{1} either of the form ϕ_{1}|_{A}^{±} or ϕ_{1}|_{A}^{±} ∘ θ̄_{1}^{−1} whose domain is disjoint from the domain of θ̂_{0} and whose range is disjoint to both its domain and range. We add θ̄_{1} to Ψ_{1} to obtain Ψ_{2} and subtract off ϕ_{1}|_{A}.

[figure: θ̄_{1}; θ̄_{0}]

Figure 2: We insist that θ̄_{0}, θ̄_{1} have disjoint domains and that the range of θ̄_{1} is entirely new. After this we keep going, finding some θ̄_{2} whose domain is disjoint from the domains of θ̄_{0} and θ̄_{1} and is, relative to these two morphisms, interdefinable with some element of Φ_{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 range of one of the earlier functions.

[figure: θ̄_{1}; θ̄_{0}; θ̄_{2}]

Figure 3: The domain of θ̄_{2} is included in the image of the earlier functions, but its image is new. After this we keep going to add θ̄_{3}, spreading out to new domain. And so on.

[figure: θ̄_{1}; θ̄_{0}; θ̄_{2}; θ̄_{3}]

Figure 4: The next morphism θ̄_{3} takes its domain from the image of θ̄_{0}. We do not rule out returning to the images of much earlier morphisms.

Thus the general idea of this construction is to steadily transfer across pieces of the Φ_{α}’s to the Ψ_{α}’s, so that Φ_{α} ∪ Ψ_{α} continues to graph E. The crucial part of this is (g). It tells us that when we remove a single piece φ_{α}|_{A_{0}^{α}} of a morphism φ_{α} ∈ Φ_{α} then we are compensating be placing into Ψ_{α+1} a morphism, θ̄_{α}, which can reconstruct φ_{α}|_{A_{0}^{α}} using only pre-existing morphisms already placed into Ψ_{α}. As we continue through the construction, and survey the construction at ever larger ordinals β, the Ψ_{β} sets only get bigger, and our ability to write

[figure: θ̄_{1}; θ̄_{0}; θ̄_{2}; θ̄_{3}; θ̄_{4}]

Figure 5: In this way we eventually ensure that all the space except for dom(θ̄_{0}) is in the range of some θ̄_{α}.

φ_{α}|_{A_{0}^{α}} as a word from Ψ_{β} is never endangered.

The other parts of this construction are less vital. (a) and (d) are bookkeeping requirements, describing how we add to the Ψ_{α}’s and remove from the Φ_{α}’s. (f) actually follows from the other clauses. (e) ensures that partial morphisms in the Ψ_{α}’s will eventually have some morphism as their union, which in turn will give us φ̂_{0} described in the statement of 3.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 Ψ_{α} side and a kind of “intersection” along the Φ_{α}’s.

We continue with this construction for as long as possible, eventually arriving at some (Ψ_{α})_{α<δ}, (Φ_{α})_{α<δ} admitting no further extension. We will argue that this final ordinal δ is a successor ordinal, δ = β + 1, and that in some natural way Ψ_{β} ∪ Φ_{β} will yield φ̂_{0} and Φ̂_{0} as required.

Claim(1): δ is not a limit ordinal.

Proof of claim: Otherwise we could simply let Ψ_{δ} = ⋃_{α<δ} Ψ_{α}, and let Φ_{δ} consist of all φ|_{A_{∞,φ}^{δ}}

where φ ∈ Φ_{α} some α < δ and as in (h) above A_{∞,φ}^{δ} = ⋂{A_{1}^{β} : β ≥ α, β < δ, φ_{β} ⊂ φ}. (□Claim)

So from now on let us fix α with α + 1 = δ. For each β ≤ α let B_{0}^{β} =Dom(θ̄_{0}), and for each n ∈ ℕ let B_{n+1}^{β} = ⋃{θ[B_{n}^{β}]|θ ∈ Ψ_{β}}.

Claim(2): For β ≤ α and n ≠ m we have B_{n}^{β}, B_{m}^{β} disjoint.

Proof of claim: By clause (e) in our construction and transfinite induction on β. (□Claim)

Claim(3): For β ≤ α and θ ∈ Ψ_{β} we have Dom(θ) ⊂ ⋃_{n∈ℕ} B_{n}^{β}; and thus

⋃_{n∈ℕ}B_{n}^{β} = ⋃_{θ∈Ψ_{β}} Dom(θ) ∪ Ran(θ).

Proof of claim: By clause (c) in our construction and induction on β. (□Claim)

Claim(4): For β ≤ α and a.e. x ∈ ⋃_{n∈ℕ} B_{n}^{β} either:

(1) x ∉ Dom(θ) all θ ∈ Ψ_{β}; or

(2) there exists k and θ_{0}, θ_{1}, ..., θ_{k} ∈ Ψ_{β} such that θ_{k} ∘ θ_{k−1} ∘ ... ∘ θ_{0}(x) is well defined and not a member of Dom(θ) any θ ∈ Ψ_{β}.

Proof of claim: Otherwise suppose not; we define B_{n,∞}^{β} to be the set of x ∈ B_{n}^{β} such that for every k there exists θ_{0}, θ_{1}, ...θ_{k} ∈ Ψ_{β} with θ_{k} ∘ θ_{k−1} ∘ ... ∘ θ_{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_{m,∞}^{β} to B_{m+1,∞}^{β} and thus for m ≤ m′ we have μ(B_{m,∞}^{β}) ≤ μ(B_{m′,∞}^{β}), and thus (B_{m,∞}^{β})_{m≥n} provides a sequence of disjoint sets with measure bounded away from zero, and a contradiction to μ(X) = 1. (□Claim)

The next claim uses ergodicity for the first time.

Claim(5): X equals the union of the Dom(θ), Ran(θ) for θ ∈ Ψ_{α}.

Proof of claim: Otherwise by ergodicity of E and claims (3) and (4) we may find some φ ∈ Φ_{α}^{±1}, m ∈ ℕ, and non-null A such that

φ[A] ∩ ⋃_{n∈ℕ}B_{n}^{α} = ∅,

A ⊂ Dom(φ) ∩ B_{m}^{α}

and either (1) Dom(θ) ∩ A = ∅ all θ ∈ Ψ_{α}; or

(2) there exists k and θ_{0}, θ_{1}, ..., θ_{k} ∈ Ψ_{α} such that θ_{k} ∘ θ_{k−1} ∘ ... ∘ θ_{0}(x) is well defined all

x ∈ A and θ_{k} ∘ θ_{k−1} ∘ ... ∘ θ_{0}[A] and Dom(θ) are disjoint for any θ ∈ Ψ_{α}.

We assume that (2) holds and that φ ∈ Φ_{α}; the other cases are exactly similar.

[figure: ⋃_{n∈ℕ} B_{n}^{α}; B_{n}^{α}; B_{n+1}^{α}; B_{n+2}^{α}; B_{n+3}^{α}; φ; A; θ_{0}; θ_{1}; θ_{2}; θ̄_{α}]

Figure 6: A typical case: The image of φ is what we want, but the domain intersects the domain of morphisms already in Ψ_{α}.

We can then let θ̄_{α} have domain θ_{k} ∘ θ_{k−1} ∘ ... ∘ θ_{0}[A] and set

θ̄_{α}(x) = φ ∘ θ_{0}^{−1} ∘ θ_{1}^{−1} ∘ ...θ_{k}^{−1}(x).

We let A_{0}^{α} = A, A_{1}^{α} =Dom(φ) \ A_{0}^{α}, Ψ_{α+1} = Ψ_{α} ∪ {θ̄_{α}}, Φ_{α+1} = (Φ_{α} \ {φ}) ∪ {φ|_{A_{1}^{α}}}. In this way we are able to contest another round, contradicting the assumption that the construction ground to a halt at δ. (□Claim)

We can then finish up the proof of the lemma by letting B_{n,k} be the set of x ∈ B_{k}^{α} such that there are θ_{1}, θ_{2}, ...θ_{n−k} ∈ Ψ_{α} with θ_{1} ∘ ... ∘ θ_{n−k}(x) well defined and n is the largest such integer. (In other words, ⋃_{k≤n} B_{n,k} is the set of elements whose orbit under Ψ_{α} has size exactly n + 1.) We use the disjointness of the morphisms in Ψ_{α} to define the longed for φ̂_{0}: For x ∈ B_{n,k} we consider the unique θ ∈ Ψ_{α} with x ∈Dom(θ) and let φ̂_{0}(x) = θ(x). □

We now let B = ⋃_{n∈ℕ} B_{n,0}. We are going to repeat the previous step, relativizing the process to B.

Lemma 3.2 There is a graphing Φ̂^{∗} of E, containing φ̂_{0} along with a new morphism φ̂^{∗}, with (C_{n,k})_{n∈ℕ,k≤n} a partition of B, such that:

(1) C_{μ}(Φ̂^{∗}) ≤ C_{μ}(Φ̂_{0});

(2) φ̂^{∗}[C_{n,k}] = C_{n,k+1} all k < n;

(3) Dom(φ̂^{∗}) = ⋃_{k<n,n∈ℕ} C_{n,k};

(4) for each φ ∈ Φ̂^{∗} with φ ≠ φ̂^{∗}, φ̂_{0} we have

φ = ψ|_{C},

some C ⊂ X, ψ ∈ Φ̂_{0};

(5) for each ψ ∈ Φ̂_{0} there is a partition (D_{i})_{i∈ℕ} of X such that (i) ψ|_{D_{0}} ∈ Φ̂^{∗};

(ii) and at i > 0, ψ|_{C_{i}} equals some word built up from φ̂^{∗}, φ̂_{0} restricted to C_{i}.

Proof We may first of all assume without any loss of generality that for each ψ ∈ Φ̂_{0} \ {φ̂_{0}} there are k, ℓ with

Dom((φ̂_{0})^{k} ∘ ψ ∘ (φ̂_{0})^{ℓ}), Ran((φ̂_{0})^{k} ∘ ψ ∘ (φ̂_{0})^{ℓ}) ⊂ B.

We may then consider the graphing Φ̂^{♯} which for each ψ ∈ Φ̂_{0}, ψ ≠ φ̂_{0}, has the appropriate morphism (φ̂_{0})^{k} ∘ ψ ∘ (φ̂_{0})^{ℓ} for E|_{B}.

With this granted it is straightforward to check that 3.1 applied to E|_{B}, μ_{B} = \frac{μ|_{B}}{μ(B)} , Φ̂^{♯}, produces the requisite φ̂^{∗}. □

Now we can define a new morphism φ̂_{1} with domain

⋃_{n∈ℕ,k<n}B_{n,k} ∪ {x|∃n(x ∈ B_{n,n}, φ̂_{0}^{−n}(x) ∈ ⋃_{m∈ℕ,k<m}C_{m,k})}.

This morphism φ̂_{1} will extend the old φ̂_{0}, and so we simply set φ̂_{1}(x) = φ̂_{0}(x) for x ∈ ⋃_{n∈ℕ,k<n} B_{n,k}. For x ∈ B_{n,n} and φ̂_{0}^{−n}(x) ∈ ⋃_{m∈ℕ,k<m} C_{m,k} we let

φ̂_{1}(x) = φ̂^{∗} ∘ φ̂_{0}^{−n}(x).

From this we obtain a new graphing Φ̂_{1} of E with

Φ̂_{1} = (Φ̂^{∗} \ {φ̂_{0}, φ̂^{∗}}) ∪ {φ̂_{1}}.

Comparing Φ̂_{1} with Φ̂_{0} and φ̂_{1} with φ̂_{0} we discover the following:

C_{μ}(Φ̂_{1}) ≤ C_{μ}(Φ̂_{0});

[figure: B; φ̂^{k}; φ̂^{ℓ}; ψ]

Φ̂_{1} is still a graphing of E; φ̂_{1} extends φ̂_{0} and μ(X \ Dom(φ̂_{1})) ≤ \frac{1}{2} μ(X \ Dom(φ̂_{0})); for any ψ ∈ Φ̂_{0} we can partition Dom(ψ) into (D_{i})_{i∈ℕ} such that

(a) ψ|_{D_{0}} ∈ Φ̂_{1};

(b) for each i > 0 there is ℓ_{i} ∈ ℤ such that ψ|_{D_{i}} = (φ̂_{1})^{ℓ_{i}}|_{D_{i}}.

Plainly we can continue this indefinitely, obtaining a sequence (Φ̂_{n}, φ̂_{n})_{n∈ℕ} where at each n C_{μ}(Φ̂_{n}) ≤ C_{μ}(Φ̂); Φ̂_{n} is a graphing of E; φ̂_{n} extends φ̂_{n−1} and μ(Dom(φ̂_{n})) ≥ 1 − 2^{−n}; for any ψ ∈ Φ̂_{n−1} we can partition Dom(ψ) into (D_{i})_{i∈ℕ} such that

(a) ψ|_{D_{0}} ∈ Φ̂_{n};

(b) for each i > 0 there is ℓ_{i} ∈ ℤ such that ψ|_{D_{i}} = (φ̂_{n})^{ℓ_{∞}}|_{D_{i}}.

In the end we let

φ̂_{∞} = ⋃_{n∈ℕ} φ̂_{n}

and for each ψ ∈ Φ̂_{1} we place into Φ̂_{∞} the morphism

ψ|_{A_{∞,ψ}} ,

where A_{∞,ψ} equals

⋂{D : ∃n∃ψ′ ∈ Φ̂_{n}(ψ′ ⊂ ψ, D = Dom(ψ′))}.

By considering the measure of the domain we actually have

φ̂_{∞} : X → X

(almost everywhere defined). By the nature of the definition of Φ̂_{∞} and the assumptions on the various Φ̂_{n} we have that for any ψ ∈ Φ̂_{n} we can partition Dom(ψ) into (D_{i})_{i∈ℕ} such that

(a) ψ|_{D_{0}} ∈ Φ̂_{∞};

(b) for each i > 0 there is ℓ_{i} ∈ ℤ such that ψ|_{D_{i}} = (φ̂_{1})^{ℓ_{i}}|_{D_{i}}. This gives us a new graphing Φ̂_{∞} of E containing a morphism φ̂_{∞} : X → X with C_{μ}(Φ̂_{∞}) ≤

C_{μ}(Φ). We are now going to take that whole step over again, adding in a new morphism but keeping hold of φ̂_{∞} and not allowing it to be changed. This requires relativizing 3.1 to φ̂_{∞}.

Lemma 3.3 Let E, Φ̂_{∞}, φ̂_{∞}, be as above. Then there is a graphing Θ̂_{0} of E which still contains φ̂_{∞}, and a morphism θ̂_{0} ∈ Θ̂_{0}, and (D_{n,k})_{n∈ℕ,k≤n} a partition of X, such that:

(1) C_{μ}(Θ̂_{0}) ≤ C_{μ}(Φ̂_{∞});

(2) θ̂_{0}[D_{n,k}] = D_{n,k+1} all k < n;

(3) Dom(θ̂_{0}) = ⋃_{k<n,n∈ℕ} D_{n,k};

(4) for each φ ∈ Θ̂_{0} with φ ≠ φ̂_{∞}, θ̂_{0} we have

φ = ψ|_{C},

some C ⊂ X, ψ ∈ Φ̂_{∞};

(5) for each ψ ∈ Φ̂_{∞} there is a partition (C_{i})_{i∈ℕ} of X such that (i) ψ|_{C_{0}} ∈ Θ̂_{0}; (ii) and at i > 0, ψ|_{C_{i}} equals some word in θ̂_{0}, φ̂_{∞} restricted to C_{i}.

Proof This closely parallels the proof of 3.1. There is a difference in how we show we can continue at inductive steps.

We build graphings

(Θ_{α})_{α<δ}, (Γ_{α})_{α<δ},

and morphisms θ_{α} ∈ Γ_{α}:

(a) Θ_{0} is empty; Γ_{0} = Φ̂_{∞} \ {φ̂_{∞}};

(b) Θ_{1} consists in a single morphism ρ̂, where for some k, ℓ, and A = φ̂_{∞}^{−k}[Dom(ρ)], we have

φ̂_{∞}^{ℓ} ∘ ρ̂ ∘ φ̂_{∞}^{k}|_{A} ∈ Φ̂_{∞};

for all α < δ and θ ∈ Θ_{α} we have Ran(θ)∩ Dom(θ) empty;

(c) if α + 1 < δ, α > 0, and θ ∈ Θ_{α+1}, then Dom(θ) ⊂ Ran(θ′) some θ′ ∈ Θ_{α};

(d) for α ≤ β we have Θ_{α} ⊂ Θ_{β} and at λ a limit ordinal we have Θ_{λ} = ⋃_{α<λ} Θ_{α};

(e) if φ, φ′ ∈ Θ_{α} are distinct, then their ranges are disjoint and their domains are disjoint;

(f) each Θ_{α} ∪ Γ_{α} ∪ {φ̂_{∞}} graphs E;

(g) θ_{α} ∈ Γ_{α} is the only morphism not appearing in Γ_{α+1} and for this θ_{α} there is a partition of Dom(θ_{α}) into A_{0}^{α}, A_{1}^{α} such that

θ_{α}|_{A_{1}^{α}} ∈ Γ_{α+1};

there are ψ_{1}, ..., ψ_{ℓ}, ψ̂_{1}, ..., ψ̂_{k} ∈ (Θ_{α} ∪ {φ̂_{∞}})^{±}, and θ̄_{α} ∈ Θ_{α+1}, with

Dom(θ̄_{α}) = ψ̂_{1} ∘ ...ψ̂_{k}[A_{0}^{α}]

and we have either

θ_{α}|_{A_{0}^{α}} = ψ_{1} ∘ ψ_{2} ∘ ...ψ_{ℓ} ∘ θ̄_{α} ∘ ψ̂_{1} ∘ ... ∘ ψ̂_{k}|_{A_{0}^{α}}

or

(θ_{α}|_{A_{0}^{α}})^{−1} = ψ_{1} ∘ ψ_{2} ∘ ...ψ_{ℓ} ∘ θ̄_{α} ∘ ψ̂_{1} ∘ ... ∘ ψ̂_{k}|_{A_{0}^{α}}

(h) if λ is a limit then for α < λ and φ ∈ Γ_{α}, we either have φ ∈ Γ_{λ} or we have φ|_{A_{∞,φ}^{λ}} ∈ Γ_{λ}, where

A_{∞,φ}^{λ} = ⋂{A_{1}^{β} : β ≥ α, θ_{β} ⊂ φ}.

Again this construction stops at some successor ordinal δ = α + 1, and as before at each β ≤ α and n ∈ ℕ we can let

D_{0}^{β} = Dom(ρ̂),
D_{n+1}^{β} = {θ[D_{n}^{β}] : θ ∈ Θ_{β}, n ∈ ℕ}.

Again n ≠ m implies D_{n}^{β} and D_{m}^{β} are disjoint. And again ⋃{Dom(θ) ∪ Ran(θ) : θ ∈ Θ_{β}} equals ⋃_{n∈ℕ} D_{n}^{β}. And again the real battle is to show that ⋃_{n∈ℕ} D_{n}^{α} = X, and for this time around we have some more work. Suppose ⋃_{n∈ℕ} D_{n}^{α} ≠ X, and we try to show that after all we could have continued to define Θ_{α+1}, Γ_{α+1}, θ_{α}, θ̄_{α}.

Definition Let F be the equivalence relation on X induced by the graphing Θ_{α} ∪ {φ̂_{∞}}.

Case 1 F is ergodic.

Then we can choose some θ_{α} ∈ Γ_{α}, words ψ, ψ̂ built up from Θ_{α}∪{φ̂_{∞}}, A_{0}^{α}∪A_{1}^{α} partitioning Dom(θ_{α}), with

ψ̂^{−1}[A_{0}^{α}] ⊂ ⋃_{n∈ℕ}D_{n}^{α} \ ⋃{Dom(θ)|θ ∈ Θ_{α}}

ψ ∘ θ_{α}[A_{0}^{α}] ⊂ X \ ⋃_{n∈ℕ}D_{n}^{α}.

After shrinking we may assume A_{0}^{α} ⊂ Ran(θ) some single θ ∈ Θ_{α}, and then we can let θ̄_{α} = ψ ∘ θ_{α} ∘ ψ̂|_{ψ̂^{−1}[A_{0}^{α}]}.

[figure: ⋃ D_{n}^{α} \ ⋃ Dom(θ); ψ; ψ̂; A_{0}^{α}; θ_{α}; X \ ⋃_{n} D_{n}^{α}]

Figure 7:

Case 2 F is not ergodic.

Then it follows that we may find Y_{1} ⊂ ⋃_{n∈ℕ} D_{n}^{α}, Y_{2} ⊂ X \ (⋃_{n∈ℕ} D_{n}^{α}),

0 < μ(Y_{1}), μ(Y_{2}),

and for all y ∈ Y_{1} the equivalence class [y]_{F} is disjoint from Y_{2}.

However E is ergodic and graphed by Θ_{α}∪Γ_{α}∪{φ̂_{∞}}, and so we may find words ψ_{1}, ψ_{2}, ..., ψ_{ℓ} from Θ_{α} ∪ {φ̂_{∞}} and τ_{1}, τ_{2}, ..., τ_{ℓ−1} ∈ Γ_{α} with

ψ_{ℓ} ∘ τ_{ℓ−1} ∘ ψ_{ℓ−1} ∘ τ_{ℓ−2}... ∘ ψ_{1}[Y_{1}] ⊂ X \ ⋃_{n∈ℕ}D_{n}^{α},

ψ_{ℓ−1} ∘ τ_{ℓ−2}... ∘ ψ_{1}[Y_{1}] ⊂ ⋃_{n∈ℕ}D_{n}^{α}.

[figure: ⋃ D_{n}^{α} \ ⋃ Dom(θ); ψ_{ℓ}; ψ̂^{−1}; Z_{1}; τ_{ℓ−1}; X \ ⋃_{n} D_{n}^{α}]

Figure 8:

Again after possibly refining Y_{1} we may assume there is some word ψ̂ from Θ_{α} such that

ψ̂ ∘ ψ_{ℓ−1} ∘ τ_{ℓ−2} ∘ ψ_{ℓ−2}... ∘ ψ_{1}[Y_{1}] ⊂ ⋃_{n∈ℕ}D_{n}^{α} \ ⋃{Dom(θ)|θ ∈ Θ_{α}}.

And we go onto another round with

θ̄_{α} = ψ_{ℓ} ∘ τ_{ℓ−1} ∘ ψ̂^{−1}|_{Z_{1}},
θ_{α} = τ_{ℓ−1},

where Z_{1} = ψ̂ ∘ τ_{ℓ−2} ∘ ...ψ_{1}[Y_{1}]. □

We then let D = ⋃_{n∈ℕ} D_{n,0}.

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.

Lemma 3.4 Let F be an ergodic measure preserving equivalence relation on standard Borel space (Y, ν), with all classes countable, ν a finite Borel measure. Let Θ be a graphing of F containing morphisms {ψ_{1}, ψ_{2}, ..., ψ_{n}}. Let A ⊂ Y be a set whose saturation under {ψ_{1}, ψ_{2}, ..., ψ_{n}} is conull – that is to say, for almost all x ∈ Y there is some y ∈ A and word φ_{w} from {ψ_{1}, ψ_{2}, ..., ψ_{n}} with φ_{w}(y) = x. Suppose further more that C_{ν}(Θ) ≥ C_{ν}({ψ_{1}, ψ_{2}, ..., ψ_{n}}) + μ(A) and there is some ψ̄ ∈ Θ \ {ψ_{1}, ψ_{2}, ..., ψ_{n}} having Dom(ψ̄), Ran(ψ̄) disjoint subsets of A.

Then there is a graphing Θ^{∗} of F and a morphism ψ^{∗} for F such that:

(1) C_{ν}(Θ^{∗}) ≤ C_{ν}(Θ); and if Θ is a treeing then so too Θ^{∗};

(2) for some partition (Y_{n,k})_{n∈ℕ,k≤n} of A we have

ψ^{∗}[Y_{n,k}] = Y_{n,k+1}

all k < n, n ∈ ℕ;

(3) Dom(ψ^{∗}) = ⋃_{n∈ℕ,k<n} Y_{n,k}; and ψ^{∗} ⊃ ψ̄;

(4) for each φ ∈ Θ^{∗} \ {ψ_{1}, ..., ψ_{n}, ψ^{∗}} we have φ = ψ|_{C} some C ⊂ Y, ψ ∈ Θ;

(5) for ψ ∈ Θ there is a partition (C_{i})_{i∈ℕ} such that (i) ψ|_{C_{0}} ∈ Θ^{∗}; (ii) at i > 0, ψ|_{C_{i}} equals some word in {ψ_{1}, ψ_{2}, ..., ψ_{n}, ψ^{∗}} restricted to C_{i}.

With this general formulation observed and set to one side, let us continue with the proof for the specific case in front of us.

Lemma 3.5 There is a graphing Θ̂_{0}^{∗} of E, containing φ̂_{∞}, θ̂_{0}, along with a new morphism θ̂^{∗}, and there is (H_{n,k})_{n∈ℕ,k≤n}, a partition of D, such that:

(1) C_{μ}(Θ̂_{0}^{∗}) ≤ C_{μ}(Θ̂_{0});

(2) θ̂^{∗}[H_{n,k}] = H_{n,k+1} all k < n;
(3) Dom(θ̂^{∗}) = ⋃_{k<n,n∈ℕ} H_{n,k};
(4) for each φ ∈ Θ̂^{∗} with φ ≠ θ̂^{∗}, θ̂_{0}, φ̂_{∞} we have
φ = ψ|_{C},
some C ⊂ X, ψ ∈ Θ̂_{0};
(5) for each ψ ∈ Θ̂_{0} there is a partition (D_{i})_{i∈ℕ} of X such that
(i) ψ|_{D_{0}} ∈ Θ̂_{0};
(ii) and at i > 0, ψ|_{C_{i}} equals some word built up from θ̂^{∗}, θ̂_{0}, φ̂_{∞} restricted to C_{i}.

Proof We apply the lemma to Θ̂_{0} for Θ, D for A, {φ̂_{∞}, θ̂_{0}} for {ψ_{1}, ..., ψ_{n}} to obtain (H_{n,k})_{n∈ℕ,k≤n} partitioning A and θ̂^{∗} as required. □

With this claim granted, we can mimic earlier arguments and choose θ̂_{0}^{∗} ⊃ θ̂^{∗} with μ(Dom(θ̂_{0}^{∗})) = μ(Dom(θ̂^{∗})) + μ(Dom(θ̂^{∗})), and {θ̂^{∗}} graphing the same equivalence relation as {θ̂^{∗}, θ̂_{0}}. And then we may clearly continue with this over and over, obtaining at each n Θ̂_{n}^{∗} and θ̂_{n}^{∗} such that:

C_{μ}(Θ̂_{n}^{∗}) ≤ C_{μ}(Θ̂_{0});

Θ̂_{n}^{∗} is a graphing of E containing θ̂_{n}^{∗}, φ̂_{∞}; θ̂_{n}^{∗} extends θ̂_{n−1}^{∗} and μ(Dom(θ̂_{n}^{∗})) ≥ 1 − 2^{−n}; for any ψ ∈ Θ̂_{0} we can partition Dom(ψ) into (D_{i})_{i∈ℕ} such that

(a) ψ|_{D_{0}} ∈ Θ̂_{n}^{∗};

(b) for each i > 0 ψ|_{D_{i}} can be written in a word in θ̂_{n}^{∗}, φ̂_{∞}.

Continuing in this fashion we obtain some

θ̂_{∞} = ⋃_{n} θ̂_{n}^{∗},

and as before we may define Φ′ to be the appropriate limit of the Θ̂_{n}^{∗}, thereby completing the proof of 1.1 in the case that C_{μ}(Φ) ≥ 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:

Lemma 3.6 Let F be an ergodic measure preserving equivalence relation on standard Borel space (Y, ν), with all classes countable, ν a finite Borel measure. Let Θ be a graphing of F containing morphisms {ψ_{1}, ψ_{2}, ..., ψ_{n}}. Let A ⊂ Y be a set whose saturation under {ψ_{1}, ψ_{2}, ..., ψ_{n}} is conull – that is to say, for almost all x ∈ Y there is some y ∈ A and word φ_{w} from {ψ_{1}, ψ_{2}, ..., ψ_{n}} with φ_{w}(y) = x. Suppose further more that C_{ν}(Θ) ≥ C_{ν}({ψ_{1}, ψ_{2}, ..., ψ_{n}}) + μ(A) and there is some ψ̄ ∈ Θ \ {ψ_{1}, ψ_{2}, ..., ψ_{n}} having Dom(ψ̄), Ran(ψ̄) disjoint subsets of A.

Then there is a graphing Θ^{∗} of F and a morphism ψ^{∗} for F such that:

(1) C_{ν}(Θ^{∗}) ≤ C_{ν}(Θ); and if Θ is a treeing then so too Θ^{∗};

(2) ψ^{∗} : A → A; ψ^{∗} ⊃ ψ̄;

(3) for each φ ∈ Θ^{∗} \ {ψ_{1}, ..., ψ_{n}, ψ^{∗}} we have φ = ψ|_{C} some C ⊂ Y, ψ ∈ Θ;

(4) for ψ ∈ Θ there is a partition (C_{i})_{i∈ℕ} such that (i) ψ|_{C_{0}} ∈ Θ^{∗}; (ii) at i > 0, ψ|_{C_{i}} equals some word in {ψ_{1}, ψ_{2}, ..., ψ_{n}, ψ^{∗}} restricted to C_{i}.

4 Corollaries

Lemma 4.1 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 𝔽_{n}.

Proof The if direction is known from [4], so we concentrate on the converse.

We begin with a treeing Φ of E; by [4], C_{μ}(Φ) = n. Applying the argument of the last section we can find an alternative graphing Θ containing θ_{1}, ..., θ_{n}, each

θ_{i} : X → X,

and with

C_{μ}(Θ) ≤ C_{μ}(Φ).

Since n = C_{μ}(E) ≤ C_{μ}(Θ) ≤ C_{μ}(Φ) = n, we have equality throughout and hence Θ = {θ_{1}, ..., θ_{n}}. □

Lemma 4.2 Let E be an ergodic measure preserving equivalence relation with countable classes on a standard Borel probability space (X, μ). If E has infinite cost and is treeable, then there is a free action of 𝔽_{∞} giving rise to E as its orbit equivalence relation.

Proof Let Θ = {φ_{1}, ..., φ_{n}, ...} be a treeing of E with infinite cost. Without loss we may assume that each Dom(φ_{n}) is disjoint from Ran(φ_{n}).

Then iterating lemma 3.6 we may find successive treeings

Θ_{1}, Θ_{2}, ...., Θ_{m}, ...

and morphism ψ_{1}, ..., ψ_{m}, ... and measurable sets (A_{n,m})_{m<n∈ℕ} such that (a) each Θ_{m} = {ψ_{1}, ...ψ_{m}, φ_{m+1}|_{A_{m+1,m}}, φ_{m+2}|_{A_{m+2,m}}, ...};

(b) each ψ_{i} : X → X is total;
(c) each φ_{m} can be written as a word in {ψ_{1}, ..., ψ_{m}};
(d) for n > m we may partition Dom(φ_{m}) up into (B_{i})_{i∈ℕ} such that
(i) B_{0} = A_{n,m}, and so φ_{n}|_{B_{0}} ∈ Θ_{m};
(ii) each φ_{n}|_{B_{i}} can be written as the restriction of a word in {ψ_{1}, ..., ψ_{m}}.

We finish with {ψ_{i} : i ∈ ℕ} as a graphing of E. Since each Θ_{m} is a treeing so too is the limit, {ψ_{i} : i ∈ ℕ}. Since each ψ_{i} is total and since they jointly give rise to a treeing, we thus obtain the free action of 𝔽_{∞}. □

Lemma 4.3 Let E be an ergodic measure preserving equivalence relation with countable classes on a standard Borel probability space (X, μ). If E is treeable, then there is a free action of a countable group G giving rise to E as its orbit equivalence relation.

Proof We at once can assume the cost is finite, or else the result follows with G = 𝔽_{∞} from the last lemma. By earlier results we may assume there is a treeing Θ and some φ ∈ Θ which is total. By Dye’s theorem on the orbit equivalence of ergodic ℤ-actions, we can assume that there is a sequence of subsets of X, (A_{i})_{i∈ℕ}, such that each

μ(A_{i}) = 2^{−i},
A_{i+1} ⊂ A_{i},
φ^{2^{i}} : A_{i+1} → A_{i},

and {A_{i+1}, φ^{2^{i}}[A_{i+1}]} partitioning A_{i}. At each i we let φ_{i} : A_{i+1} → A_{i} be given by

φ_{i} = φ^{2^{i}}|_{A_{i+1}};

note that {φ_{i} : i ∈ ℕ} graphs the same equivalence relation as {φ}.

We then build (k_{i})_{i∈ℕ}, k_{0} ∈ ℕ, each k_{i+1} ∈ {0, 1}, and morphisms

ψ_{i,j} : A_{i} → A_{i}

for j < k_{i}, and treeings Θ_{n} for E such that:

(a) Θ_{n} = {φ_{i} : i ∈ ℕ} ∪ {ψ_{i,j} : i ≤ n, j < k_{i}} ∪ {θ|_{B_{θ,n}} : θ ∈ Θ}, each B_{θ,n} some subset of Dom(θ);

(b) C_{μ}({φ_{i} : i ∈ ℕ} ∪ {ψ_{i,j} : i ≤ n, j < k_{i}}) ≥ C_{μ}(Θ) − 2^{−n−1} = C_{μ}(E) − 2^{−n−1};

(c) for each θ ∈ Θ we may partition X into (C_{i})_{i∈ℕ} such that (i) θ|_{C_{0}} ∈ Θ_{n}; (ii) each θ|_{C_{i+1}} equals some word in {φ_{i} : i ∈ ℕ} ∪ {ψ_{i,j} : i ≤ n, j < k_{i}}.

It follows from lemma 3.6 that we may indeed construct such a sequence. Given the graphing Θ̂_{n} = {φ_{i} : i ∈ ℕ} ∪ {ψ_{i,j} : i ≤ n, j < k_{i}}, or the morally equivalent graphing Θ̄_{n} = {φ} ∪ {ψ_{i,j} : i ≤ n, j < k_{i}}, we can consider whether C_{μ}(E) ≥ C_{μ}(Θ̂_{n}) + 2^{−n−1}. If no, we just pass on with k_{n+1} = 0; if yes, then we apply 3.6 to obtain some

ψ_{n+1,0} : A_{n+1} → A_{n+1}

and graphing

Θ_{n+1} = {φ_{i} : i ∈ ℕ} ∪ {ψ_{i,j} : i ≤ n + 1, j < k_{i}} ∪ {θ|_{B_{θ,n+1}} : θ ∈ Θ},

and take the process to the next round.

This construction granted it follows from (c) that

Θ_{∞} = {φ_{i} : i ∈ ℕ} ∪ {ψ_{i,j} : i ∈ ℕ, j < k_{i}}

graphs E. Since each Θ_{n} is a treeing it follows that Θ_{∞} 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 ∈ ℕ}, {b_{i,j} : i ∈ ℕ, j < k_{i}}. We will ask that this group be free subject to the relations

a_{ℓ}b_{i,j} = b_{i,j}a_{ℓ}

for i > ℓ,

(a_{ℓ})^{2} = 1,
a_{ℓ}a_{k} = a_{k}a_{ℓ}

all k, ℓ. For each i ∈ ℕ we define a total function T_{i} : X → X by first choosing for a.e. x the unique m_{0}^{x}, m_{1}^{x}, ..., m_{i−1}^{x} ∈ {−1, 0} such that

y_{x} = φ_{i−1}^{m_{i−1}^{x}} ∘ φ_{i−2}^{m_{i−2}^{x}} ∘ ...φ_{0}^{m_{0}^{x}}(x) ∈ A_{i}

and then letting

T_{i}(x) = φ_{0}^{−m_{0}^{x}} ∘ φ_{1}^{−m_{1}^{x}} ∘ ...φ_{i−1}^{−m_{i−1}^{x}} ∘ φ_{i}(y_{x})

if y_{x} ∈ A_{i+1},

T_{i}(x) = φ_{0}^{−m_{0}^{x}} ∘ φ_{1}^{−m_{1}^{x}} ∘ ...φ_{i−1}^{−m_{i−1}^{x}} ∘ φ_{i}^{−1}(y_{x})

if y_{x} ∈ A_{i} \ A_{i+1}. (In other words we recursively define each T_{i} to be the unique T_{i} : X → X of order 2 which extends φ_{i} and commutes with T_{j} all j < i.) Similarly we define for j < k_{i}

S_{i,j}(x) = φ_{0}^{−m_{0}^{x}} ∘ φ_{1}^{−m_{1}^{x}} ∘ ...φ_{i−1}^{−m_{i−1}^{x}} ∘ ψ_{i,j}(y_{x}).

We want to show that if we let each a_{ℓ} act on X via T_{ℓ} 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.

Claim(1):

S_{i,j} ∘ T_{ℓ} = T_{ℓ} ∘ S_{i,j}

all ℓ < i,

T_{ℓ} = T_{ℓ}^{−1}
T_{ℓ} ∘ T_{k} = T_{k} ∘ T_{ℓ}

all ℓ, k.

Proof of claim: This follows quickly from the definitions. (□Claim)

Thus this assignment a_{ℓ} ↦ T_{ℓ}, b_{i,j} ↦ S_{i,j} extends to a homomorphism

G → M_{∞}(X),
g ↦ φ_{g},

where M_{∞}(X) is the group of invertible mpts on X and gives us a measure preserving action of G on X.

Claim(2): If φ_{g}(x) = x for a non-null collection of x ∈ X then g = 1.

Proof of claim: Suppose g is as above and for a non-null set of x we have φ_{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_{0}c_{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_{i(k)−1}^{−m_{i(k)−1}}c_{k}a_{i(k)−1}^{m_{i(k)−1}}...a_{0}^{m_{0}}

we may assume that there is a positive measure set A ⊂ X such that for all x ∈ A

φ_{g}(x) = x

and at each k ≤ M we have

U_{k+1} ∘ U_{k+2} ∘ ... ∘ U_{M}(x) ∈ A_{k(i)},

where each U_{ℓ} is respectively T_{i(ℓ)}, S_{i(ℓ),j(ℓ)}, S_{i(ℓ),j(ℓ)}^{−1}, depending on whether c_{ℓ} equals either a_{i(ℓ)},

b_{i(ℓ),j(ℓ)}, or b_{i(ℓ),j(ℓ)}^{−1}; the key point is that in G the element c_{k} equals a_{0}^{−m_{0}}a_{1}^{−m_{1}}...a_{i(k)−1}^{−m_{i(k)−1}}c_{k}a_{i(k)−1}^{m_{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 Θ_{∞} being a treeing that we may reduce the word

U_{0} ∘ U_{1} ∘ ...U_{M}|_{A}

down to the identity by the operations of canceling various U_{ℓ} ∘ U_{ℓ+1} when U_{ℓ+1} = U_{ℓ}^{−1}. Thus in particular it follows that c_{0}c_{1}...c_{M} will easily reduce to the identity in G and we are done. (□Claim)

□

References

[1] H. Dye, On groups of measure preserving transformations, American Journal of Mathematics, vol. 85(1963), pp. 551-576.

[2] J. Feldman, C.C. Moore, Ergodic equivalence relations and von Neumann algebras, Transactions of the American Mathematical Society, vol. 234(1977), pp. 289-324.

[3] A. Furman, Orbit equivalence rigidity, Annals of Mathematics, vol. 150(1999), pp. 1083-1108.

[4] D. Gaboriau, Cout des relations d’equivalence et des groupes, vol. 139(2000), pp. 41-98. Inventiones Mathematicae.

[5] A.S. Kechris, B. Miller, Topics in Orbit Equivalence, vol. 1852, Lecture Notes in Mathematics, Springer, Berlin, 2004.

[6] G. Levitt, On the cost of generating an equivalence relation, Ergodic theory and dynamical systems, vol. 15(1995), pp. 1173-1181.

[7] S. Popa, A class of cross-product factors by free groups, having trivial fundamental group, preprint UCLA 2001.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555