Handbook of Set Theory

Foreman, Kanamori, and Magidor (eds.) September 11, 2006

2

Contents

I Borel equivalence relations 5 by Greg Hjorth 1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 A survey of structure theorems . . . . . . . . . . . . . . . . . . . 14

2.1 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Anti-structure . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Beyond good and evil . . . . . . . . . . . . . . . . . . . . 18

3 Countable Borel equivalence relations . . . . . . . . . . . . . . . 21 3.1 The global structure . . . . . . . . . . . . . . . . . . . . . 21 3.2 Treeable equivalence relations . . . . . . . . . . . . . . . 29 3.3 Hyperfiniteness . . . . . . . . . . . . . . . . . . . . . . . 29

4 Effective cardinality . . . . . . . . . . . . . . . . . . . . . . . . . 30 5 Classification problems . . . . . . . . . . . . . . . . . . . . . . . 32

5.1 Smooth versus non-smooth . . . . . . . . . . . . . . . . . 32 5.2 Universal for Polish group actions . . . . . . . . . . . . . 33 5.3 Universal for S_{∞} . . . . . . . . . . . . . . . . . . . . . . . 34 5.4 E_{∞} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.5 E_{0} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4 CONTENTS

I. Borel equivalence relations

Greg Hjorth

This chapter is setting out to achieve an impossibility, namely to survey the rapidly exploding field of Borel equivalence relations as found in descriptive set theory and the connections with areas entirely outside logic. The choice of content and emphasis is inevitably molded by this author’s own prejudices and research history; others may have a radically different vision of the subject. For instance I have somewhat arbitrarily chosen to say nothing about the study of equivalence relations arising in Borel ideals, as found in papers such as [63], [50], [11], or the parallel theory of Borel linear orderings as found in say [48], [29], or the still unpublished work of Hugh Woodin’s and of Richard Ketchersid’s on the cardinality of certain Borel equivalence relations under strong determinacy assumptions, the work on general Σ ∼_{1}^{1} equivalence relations as found in [4], or the topological Vaught conjecture as discussed in [59], [45], [5], [34]. Moreoever the discussion of Borel equivalence relations is organized around the Borel reducibility order, ≤_{B}, rather than notions such as orbit equivalence, as found in say [21], [19], [22], [58], [37], or notions of isomorphism, as discussed in [9]. Without a super-human effort to the contrary, it is easy to slip in to discussing what I know best, which, regretfully perhaps, are the papers I have written. Finally I should admit to being much more conversant with the mathematics of the subject than the history, and since my main concern is to communicate the most vibrant ideas with a certain immediacy undoubtedly some important citations have been overlooked.

Thus I stand impeached with prejudice, ignorance, arbitrariness, arrogance, and discourtesy.

But as unfortunate as these failings may be, they are inevitable, and I say all of this simply so the reader will understand that this is a project doomed to at least partial failure and nevertheless worth pursuing in the hope of partial success. A similar but rather different point of view can be found [51]. The reader might also look at [6] for a closer examination of some of the issues surrounding actions induced by Polish group actions, or at [34] for a discussion of the Vaught conjecture, or [57] for orbit equivalence. Another survey is given in [36], but in fact I am unable to even point to any small set of papers which would be fully adequate.

1. Definitions

Before moving on to the theory of Borel equivalence relations it would be helpful to discuss Borel sets in general. A thorough and more complete account can be found in [49].

1.1 Definition. A Polish space is a separable topological space which admits a compatible complete metric. The Borel subsets of a Polish space are those appearing in the σ-algebra generated by the open sets – that is to say, if we begin with the open sets and continue applying the operations of countable union, countable intersection, and complementation, then the Borel sets are those appearing in the collection which thereby arises.

Inside the Borel sets we make further distinctions. Thus a set is Σ ∼_{1}^{0} if it is open, and after that we define recursively a set to be Π ∼_{α}^{0} if its complement is Σ ∼_{α}^{0}, and to be Σ ∼_{α}^{0} if it is a countable union of Borel sets each of which are Π ∼_{β}^{0} for some β < α. It is easily shown that Π ∼_{α}^{0} ⊆ Σ ∼_{α+1}^{0} and every Borel set will be Σ ∼_{α}^{0} for some α < ω_{1}. At the bottom level of this hierarchy there are alternate notations used by analysts – for instance a Π ∼_{2}^{0} set is also called G_{δ} and a Σ ∼_{2}^{0} set is also called F_{σ}.

For much of the time we are unconcerned with the topological structure of a Polish space, focusing instead on its Borel structure. Accordingly a set X equippped with a σ-algebra B is a standard Borel space if there is some Polish topology on X which gives rise to B as the collection of Borel sets.

1.2 Example. 1 ℝ and ℂ are Polish. Any compact metric space is Polish.

2 There is a natural way to think of the collection of all subsets of the natural numbers as a Polish space. By associating with each set its characteristic function, or indicator function, we can identify the power set of ℕ, denoted by P(ℕ), with

{0, 1}^{ℕ} =_{df} 2^{ℕ},

which is a compact space in the product topology. Similarly P(ℕ × ℕ) or P(S) any countable set S.

3 Any Borel subset of a Polish space is a standard Borel space in the inherited Borel structure (see [54], 13.4 [49]).

4 The Borel probability measures on a standard Borel space themselves again form a standard Borel space (this ultimately follows from the Riesz representation theorem; compare 17.23 [49]).

5 Consider the collection of subsets of ℕ × ℕ × ℕ which form the graph of a function

• : ℕ × ℕ → ℕ

providing a finite rank torsion free abelian group structure on ℕ. This collection in the natural Borel structure is a standard Borel space, since it is a Borel subset of the Polish space ℕ × ℕ × ℕ.

6 Given a countable language we can form two possible Polish topologies on the space of L-structures on ℕ. For simplicity assume the language is relational, though the more general case of L having function symbols is only slightly more complicated. We let Mod(L) be the set of all L-structures with the natural numbers as their underlying set.

The first of the topologies is τ_{qf}. For ψ(x⃗) a formula in L and a⃗ = (a_{1}, ..., a_{n}) a sequence in ℕ, we let U(ψ(x⃗), a⃗) be the collection of all N ∈ Mod(L) with

N ⊧ ψ(a⃗),

and then τ_{qf} is the collection the topology with basis consisting of all the sets of the form U(ψ(x⃗), a⃗), as ψ ranges over the quantifier free formulas. If L consists of relations R_{1}, R_{2}, ..., each R_{i} and n(i)-ary relation, then it is easily seen that (Mod(L), τ_{qf}) is isomorphic to ∏_{i∈ℕ} ℕ^{2^{n(i)}} in the product topology. Since the class of Polish spaces is closed under product (see §2.1 [33]) we have that (Mod(L), τ_{qf}) is Polish.

The more subtle topology is τ_{fo}, with basis consisting of all U(ψ(x⃗), a⃗) as ψ ranges over first order formulas. This is a again a Polish topology, though the proof of this, say as found at 2.42 [33], is less obvious.

While these are divergent choices in topology, there is really one reasonable choice of Borel structure on this space. Since τ_{fo} ⊃ τ_{qf} and both are Polish topologies, they give rise to the same Borel structure. (This follows from 18.10, 18.14 [49]).

1.3 Definition. Given a Polish space X, we let F(X) be the collection of all closed subsets of X, equipped with the σ-algebra generated by sets of the form {F ∈ F(X) : U ∩ F ≠ ∅} for U open.

This is known as the Effros Borel structure on the closed subsets of X. It is not hard to show that F(X) equipped with this Borel structure is indeed a standard Borel space – see for instance §2 [33] or [49].

The reader should definitely consult [49] for a more reasonable introduction to the theory of Borel sets. This is the smallest sketch.

1.4 Definition. A function

f : X → Y

is said to be Borel if f^{−1}[B] is Borel for any Borel set B ⊆ Y.

An equivalence relation E on X is said to be Borel if it is Borel as subset of X × X. We then use [x]_{E} to denote the equivalence class of x for any x ∈ X – that is to say, the set {y ∈ X : xEy}.

1.5 Definition. Given E and F Borel equivalence relations on standard Borel X and Y, we write

E ≤_{B} F,

E is Borel reducible to F, if there is a Borel f : X → Y such that for all x_{1}, x_{2} ∈ X

x_{1}Ex_{2} ⇔ f(x_{1})F f(x_{2});

in other words, f pushes down to injective map

f̄: X/E → Y/F

between the quotient spaces.

After this we naturally set E <_{B} F if there is a Borel reduction from E to F but not F to E. We set E ∼_{B} F if each is Borel reducible to the other.

Note that the order ≤_{B} is transitive, since the composition of two Borel functions is again Borel.

Remark This definition is only for Borel f, but one can of course consider more general classes of functions if this seems too stingy – for instance, Cmeasurable functions, projective functions, L(ℝ) functions. In virtually all cases this makes no difference – the failures of reducibility for Borel functions persist to these wider classes. Indeed, appropriately understood most of the theorems about Borel equivalence relations turn into theorems about cardinality in L(ℝ). See §4 below.

It should also be admitted that there are other ways in which we can compare Borel equivalence relations, for instance asking that there be isomorphisms of the underlying spaces that conjugate the relations, or in the presence of a measure we can ask for measure preserving isomorphisms between the spaces which conjugate the equivalence relations almost everywhere; indeed this second notion is the subject of extensive study in areas such as operator algebras (for instance [58]), geometric group theory (for instance [21], [61]), and the rigidity theory in the sense of Zimmer ([69]). For the purposes of descriptive set theory, I incline to the view that ≤_{B} is the central notion. Indeed some kind of defense of the philosophical significance of ≤_{B} is given in §4.

1.6 Example. 1 For X a Polish space, we let id(X) be the identity relation on the space X. Since any two uncountable standard Borel spaces are isomorphic (15.6 [49]), it follows that for any uncountable X we have

id(X) ≤_{B} id(ℝ).

2 We let E_{0} be the equivalence relation of eventual agreement on infinite binary sequences. Thus for x⃗ = (x_{0}, x_{1}, ...), y⃗ = (y_{0}, y_{1}, ...) ∈ 2^{ℕ}, we set

x⃗E_{0}y⃗

if and only if there exists some N ∈ ℕ with

∀n > N(x_{n} = y_{n}).

Here we have

id(2^{ℕ}) <_{B} E_{0}.

To see that there is a Borel reduction from id(2^{ℕ}) to E_{0} is routine. It follows simply because there is perfect set in Cantor space consisting of mutually generic reals.

The failure of reducibility in the other direction is more subtle. First one observes that E_{0} is given by the continuous action of the countable group

⨁_{ℕ} ℤ/2ℤ

with (g_{0}, g_{2}, ...) · (x_{0}, x_{1}, ...) = (g_{0} + x_{0}mod2, g_{1} + x_{1}mod2, ...). Then given a supposed Borel reduction f of E_{0} to the identity relation on 2^{ℕ} we can find a comeager set C on which f is continuous. Then we can take

⋂ ; g⃗∈⨁ ℤ/2ℤ g⃗ · C,

which will still be comeager and now invariant. Taking any x⃗ in this set we obtain that f will be constant on [x⃗]_{E_{0}}. Since this equivalence class is dense, f will constant on the entire set ⋂g⃗ g⃗ · C. Since this set is uncountable, it contains many equivalence classes with a contradiction. (For a more detailed and general argument, see 3.2 [33]).

3 We let E_{1} be the equivalence relation of eventual agreement on infinite sequences of reals. Here one has

E_{0} <_{B} E_{1}.

(See [52], or even [33]).

4 Given a countable group Γ, we let 2^{Γ} be the collection of all functions

f : Γ → {0, 1}

with the product topology. We let Γ act on 2^{Γ} with

γ · f(δ) = f(γ^{−1}δ),

the left shift action. We then let E_{G} be the resulting equivalence relation.

In the case that we start with G = 𝔽_{2}, the free group on two generators, one has

E_{0} <_{B} E_{𝔽_{2}}.

(See for instance appendix A of [43] for a survey of stronger and more general results one can prove in this direction.)

5 An example of historical importance is the Vitali equivalence relation, E_{v}. For r, s ∈ ℝ set

rE_{v}s

if and only if

r − s ∈ ℚ.

The classical argument that this equivalence relation has no measurable selector can be modified to show that id(ℝ) <_{B} E_{v}; alternatively one may appeal to a variation of the Baire category argument at example 2 just above.

On the other hand, at the level of Borel reducibility there is no distinction between E_{0} and E_{v}. (See for instance the argument after 1.5 [32] for a short proof that E_{0} ∼_{B} E_{v}.)

6 Let X_{2} be the space of all h ∈ 2^{ℕ×ℕ}, where at each n ≠ m there exists a k with h(n, k) ≠ h(m, k). In other words, if we set h_{n} ∈ 2^{ℕ} to be given by h_{n}(k) = h(n, k) then for n ≠ m we have h_{n} ≠ h_{m}.

Then define T_{2} on X_{2} by h^{1}T_{2}h^{2} if and only if the corresponding countable sets in 2^{ℕ} are equal – that is to say,

{h_{n}^{1} : n ∈ ℕ} = {h_{n}^{2} : n ∈ ℕ}.

Thus if we let S_{∞} be the group all permutations of ℕ, acting on X_{2} by

σ · h(n, k) = h(σ^{−1}(n), k),

then T_{2} is the resulting equivalence relation.

It is well known that for any E_{G} as above, arising from a countable group G acting on 2^{G}, one has

E_{G} <_{B} T_{2}.

(See for instance 2.64 [33].)

1.7 Definition. An equivalence relation E on standard Borel X is said to be smooth or tame if E ≤_{B} id(ℝ).

Smoothness amounts to asserting the existence of a countable algebra {B_{n} : n ∈ ℕ} of E-invariant Borel sets which separates points – which is to say

xEy ⇔ ∀n(x ∈ B_{n} ⇔ y ∈ B_{n}).

This in turn is equivalent to saying that X/E = {[x]_{E} : x ∈ X} in the quotient Borel structure consisting of all E-invariant Borel sets is a subset of a standard Borel space. (See [28], [47].)

1.8 Definition. A Borel equivalence relation E on a standard Borel space X is said to be countable if every equivalence class is countable. It is essentially countable if there is some other countable Borel equivalence relation F with E ≤_{B} F.

1.9 Example. Let 𝔽_{2} be the free group on two generators and let E_{∞} arise from action of 𝔽_{2} on 2^{𝔽_{2}}. Then this is countable, since the responsible group is countable.

It is known from [47] that this equivalence relation is universal among the countable equivalence relations, in the sense that for every countable Borel equivalence relation E one has

E ≤_{B} E_{∞}.

We will not get ensnarled in the details of this argument here, but it might be helpful to point out that the proof depends on the Feldman-Moore theorem, which in some sense reduces to the study of countable Borel equivalence relations to the study of the orbit equivalence relations induced by countable groups.

1.10 Theorem (Feldman, Moore, [15]). If E is a countable Borel equivalence relation on X, then there is a Borel group of automorphisms whose orbits equal the E-equivalence classes.

Proof. Following the Lusin-Novikov uniformization theorem (18.10, 18.15 [49]) we can find a sequence of Borel functions (f_{n})_{n∈ℕ} such that [x]_{E} always equals {f_{n}(x) : n ∈ ℕ}. We can find Borel sets B_{n} consisting of exactly the points on which f_{n}(x) ≠ x. We can then find a partition of B_{n} into Borel sets {C_{n,i} : i ∈ ℕ} with f_{n}[C_{n,i}] disjoint from C_{n,i} and f|_{C_{n,i}} one-to-one. We then let g_{n,i} be the function which is the identity off of f_{n}[C_{n,i}] ∩ C_{n,i}, equal to f_{n} on C_{n,i}, and to f_{n}^{−1} on f[C_{n,i}]. It follows by Lusin-Novikov again that each g_{n,i} is Borel.

Letting G be the countable group of automorphisms generated by {g_{n,i} : i, n ∈ ℕ} we obtain E = E_{G}, the orbit equivalence relation induced by G. ⊣

1.11 Lemma. A countable Borel equivalence relation is smooth if and only if it has a Borel selector – that it so say, a Borel set which meets every equivalence class in exactly one point.

Proof. This follows rapidly from the Lusin-Novikov uniformization theorem. See for instance [47], or [7] for far more general results. ⊣

This lemma fails for general equivalence relations. For instance if we take C ⊆ ℕ^{ℕ} × ℕ^{ℕ} with the projection {x : ∃y((x, y) ∈ C)} non-Borel, and set (x, y)E(x′, y′) on C exactly when x = x′, then a Borel selector would result in the projection being Borel, since the one-to-one image of any Borel set under a Borel function is Borel.

1.12 Definition. An equivalence relation E is hyperfinite if there is a sequence of Borel equivalence relations, (F_{n})_{n∈ℕ}, with each F_{n} having all its equivalence classes finite, each F_{n} ⊆ F_{n+1}, and E = ⋃_{n∈ℕ} F_{n}.

1.13 Lemma ([47]). A countable Borel equivalence relation E on X is hyperfinite if and only if E ≤_{B} E_{0}.

1.14 Definition. An equivalence relation E on a standard Borel space X is treeable if its classes form the components of a Borel treeing on X – that is to say, there is T ⊆ X × X which is Borel with respect to the product Borel structure, is symmetric, acyclic, loopless, and for which we have xEy if and only if there is a finite chain x_{0} = x, x_{1}, x_{2}, ..., x_{n} = y, each (x_{i}, x_{i+1}) ∈ T . (So here one has in mind the notion of tree prevelant in certain branches of combinatorics or computer science, rather than descriptive set theory – an acyclic graph, with no distinguished root in the various connected components).

1.15 Definition. Let 𝔽_{2} be the free group on two generators. Let F (2^{𝔽_{2}}) be the free part of the shift action of 𝔽_{2} on 2^{𝔽_{2}} – that is to say, the set of h : 𝔽_{2} → {0, 1} such that for all σ ∈ 𝔽_{2} there exists τ with h(σ^{−1}τ) ≠ h(τ), equipped with the action (σ · h)(γ) = h(σ^{−1}γ). We then let E_{T ∞} be the orbit equivalence arising from this action of 𝔽_{2} on F (2^{𝔽_{2}}).

In most cases treeable equivalence relations have been studied simply in the case that E is already countable. Here one has an analogue of 1.13.

1.16 Lemma (See [47] or [40]). A countable equivalence relation is treeable if and only if it is Borel reducible to E_{T ∞}.

Although this survey is primarily concerned with Borel equivalence relations, one must naturally connect this study with the analysis of those lying just outside this class.

1.17 Definition. A subset of a standard Borel space is analytic or Σ ∼_{1}^{1} if it is the image under a Borel function of a Borel set.

1.18 Definition. A Polish group is a topological group which is Polish as a space. Given a Polish group G, a Polish G-space is a Polish space equipped with a continuous action of G; a standard Borel G-space is a standard Borel space equipped with a Borel action by G.

In either case, if X is the space we use E_{G}^{X}, or even just E_{G} when there is no doubt to X, to denote the resulting orbit equivalence relation, and [x]_{G} to denote the orbit of a point x.

The equivalence relations arising from the Borel action of a Polish group are always Σ ∼_{1}^{1}, but frequently non-Borel. As noted in [6], for any such E_{G}^{X} we can write X as an ℵ_{1} union of invariant Borel sets,

X = ⋃_{α<ω_{1}} X_{α},

and E_{G}^{X} restricted to each X_{α} Borel.

1.19 Example. 1 Let S_{∞} be the group of all infinite permutations of the natural numbers equipped with the topology of pointwise convergence – that is to say, a basic open set has the form {σ ∈ S_{∞} : σ(n_{0}) = k_{0}, ..., σ(n_{ℓ}) = k_{ℓ}}. or L a countable language we let S_{∞} act on Mod(L) in the natural way –

(σ · M) ⊧ R(n_{0}, ..., n_{ℓ})

if and only if

M ⊧ R(σ^{−1}(n_{0}), ..., σ^{−1}(n_{ℓ}).

The resulting equivalence relation is nothing other than isomorphism on this class of structure, and for any reasonably rich one has E_{S_{∞}} is Σ ∼_{1}^{1} but non-Borel.

2 Given L as above, and φ ∈ L_{ω_{1},ω}, a countably infinitary formula, we let Mod(φ) be the structures in Mod(L) which satisfy φ. Since this is a Borel subset of a Polish space, it is a standard Borel space in its own right, and in the induced action a standard Borel S_{∞}-space.

Here one should see [6] for further details. The first paper to consider these examples seriously from the point of the view of the ≤_{B} ordering is [17].

3 Given a Polish group G we can let it act on itself by conjugation –

σ · ρ = σ^{−1}ρσ.

In many cases this corresponds naturally to some kind of classification problem. For instance, if M_{∞} is the group of all measure preserving transformations of the unit interval considered up to agreement almost everywhere, then this group is indeed Polish in the natural topology and the equivalence relation arising from its conjugation action is the equivalence relation of isomorphism of measure preserving transformations. Or if we let U_{∞} be the unitary group on infinite dimensional Hilbert space, we are find ourselves confronted with the classification up to unitary equivalence of unitary operators. Or one may consider Hom([0, 1]), the homeomorphism group of the unit interval, for the classification problem for homeomorphisms of the unit interval up to topological similarity. All these examples are discussed at length in [33].

2. A survey of structure theorems

2.1. Structure

At the base level of the ≤_{B} there is a sharp structure. The first of these results is due to Jack Silver. Although it was proved sometime prior to the general study of Borel equivalence relations, it may be paraphrased in modern terminology as follows.

2.1 Theorem (Silver, [62]). If E is a Borel equivalence relation, then exactly one of:

(I) E ≤_{B} id(ℕ);

(II) id(ℝ) ≤_{B} E.

In some ways this belongs to the prehistory of the subject. Momentum only began in ernest following the seminal dichotomy theorem of Leo Harrington, Alexander Kechris, and Alain Louveau. This is sometimes known as the Glimm-Effros dichotomy, since the forerunners of this theorem were proved by Glimm and then later Effros, who had the result in the case that E is an F_{σ} equivalence relation induced by the continuous action of a Polish group.

2.2 Theorem (Harrington-Kechris-Louveau, [28]). If E is a Borel equivalence relation, then exactly one of:

(I) E ≤_{B} id(ℝ);

(II) E_{0} ≤_{B} E.

Proof. (Sketch only) We describe some of the combinatorics under the drastic assumption that E is a countable Borel equivalence relation. This is misleading as to the difficulty of the proof, since then the vast majority of the mathematical issues simply evaporate. It should also be pointed out that the theorem in this case was already known to Glimm and Effros, [27], [10].

First we can appeal to 1.10 to obtain a countable group G acting by Borel transformations on the Polish space X with E_{G} = E. Applying a change of topology argument, as found in say §13 [49], we may assume G acts by homeomorphisms.

Now there are two possibilities.

First of all we may have that for any x ≠ y ∈ X we have the closures of their orbits, \overline{[x]_{G}}, \overline{[y]_{G}}, distinct. In that case one defines a map

X → F(X),
x ↦ \overline{[x]_{G}},

from X to the space of all closed subsets of X with the standard Borel structure. It is easily seen that this map is Borel, and so we obtain a reduction of E to id(F(X)). Since any two uncountable Borel spaces are Borel isomorphic, this is as good as a reduction to id(ℝ).

The other case is that there are distinct orbits with the same closure. We will now work entirely inside some X_{0} ⊆ X consisting of all y with \overline{[y]_{G}} = C for some closed C. X_{0} is a G_{δ} subset of X, and hence Polish in its own right. (See for instance §2.1 [33].) At this stage we are assuming that X_{0} contains more than one orbit for the purpose of deriving a contradiction. We let {g_{n} : n ∈ ℕ} enumerate the group G. Now note that E_{G} is F_{σ}, and our assumptions on X_{0} imply that both it and its complement are dense in X_{0} × X_{0}.

We then construct non-empty open neighborhoods (U_{s})_{s∈2^{<ℕ}} in X_{0} and (g_{s})_{s∈2^{<ℕ}}

(i) \overline{U_{s}} ⊆ U_{t} for s a strict extension of t;

(ii) with respect to a compatible complete metric on X_{0}, the diameter of each U_{s} is less than 2^{−n} for s ∈ 2^{n}; (iii) g_{s^{⌢}0} = g_{s}; g_{s^{⌢}1} = g_{s}g_{⟨0,0,...0⟩^{⌢}1}; g_{⟨0,0,...0⟩} = e, the identity of the group; (iv) g_{s} · U_{⟨0,0,..0⟩} = U_{s}, where ⟨0, 0, ..., 0⟩ is the constantly zero sequence of the same length as s;

(v) if s, t ∈ 2^{n+1} and s(n) ≠ t(n), then for all i ≤ n we have g_{i} · U_{s} ∩ U_{t} = ∅.

Assuming we can effect this elaborate arrangement, the conclusion is brief. (iv) will guarantee that for each s, t ∈ 2^{n} we have

g_{t}g_{s}^{−1} · U_{s} = U_{t},

and then repeated applications of (iii) ensures for any w ∈ 2^{<ℕ}

g_{t}g_{s}^{−1} · U_{s^{⌢}w} = U_{t^{⌢}w}.

Thus for any x ∈ 2^{ℕ} there will be a unique point

θ(x) ∈ ⋂ U_{x|_{n}},

and if x(n) = y(n) all n ≥ N, then

g_{x|_{n}}g_{y|_{n}}^{−1}(θ(y)) = θ(x),

whilst if x(n) ≠ y(n) for infinitely many n then (v) guarentees E_{G}-inequivalence.

So suppose we have done this up to some level. We have (U_{s})_{s∈2^{n}}, (g_{s})_{s∈2^{n}}. By the density of the complement of E_{G} we can find some x, y ∈ U_{⟨0,0,...0⟩} which are inequivalent. We can then let x_{s} = g_{s} · x, y_{s} = g_{s} · y. We form small enough open sets W, V around x, y so that if W_{s} = g_{s} ·W, V_{s} = g_{s} ·V, then g_{i} · V_{s} ∩ W_{t} = ∅, g_{i}^{−1} · V_{s} ∩ W_{t} = ∅.

We then find a point x′ ∈ [x]_{G} ∩ V_{⟨0,0,...0⟩} by the density of the orbits. We let g_{⟨0,0,...0⟩^{⌢}1} be a group element moving x to x′. We let g_{s^{⌢}1} be g_{s}g_{⟨0,0,...0⟩^{⌢}1}. We then build a sufficiently small set U^{∗} ⊆ W so that if we let U_{t} = g_{t} · U^{∗} for each t ∈ 2^{n+1} then for i ≤ n we have ensured (i), (ii), and (v). ⊣

The argument for general Borel E is far harder, and uses the Gandy-Harrington topology. There is no known proof of 2.2 which does not use ideas from logic.

Therefore at the base of the picture one obtains the Borel equivalence relations with finitely many classes, followed by any Borel equivalence relation with exactly ℵ_{0} many classes, then the identity relation on the reals, and then E_{0}, or, equivalently when considered up to Borel reducibility, the Vitali equivalence relation.

It should be mentioned that Harrington-Kechris-Louveau implies Silver’s theorem. If f : 2^{ℕ} → X witnesses E_{0} ≤_{B} E then we can find a comeager set on which this function is continuous, and then inside this comeager we can find a compact perfect set of E_{0}-inequivalent reals. On the other hand if E ≤ id(ℝ) then the equivalence classes of E can be identified with a Σ ∼_{1}^{1} subset of a Polish space, whereapon Silver’s theorem reduces to the perfect set theorem for Σ ∼_{1}^{1} sets.

Immediately after this one obtains a splintering. It is known from [52] that there are no other Borel equivalence relations E such that for any other Borel F one has either E ≤_{B} F or F ≤_{B} E. Instead we have:

2.3 Theorem (Kechris-Louveau; [52]). Let E be a Borel equivalence relation with E ≤_{B} E_{1}. Then exactly one of the following holds:

(I) E ≤_{B} E_{0}; or,

(II) E_{1} ≤_{B} E.

2.4 Definition. Let E_{0}^{ℕ} be the equivalence relation on (2^{ℕ})^{ℕ} given by

x⃗E_{0}^{ℕ}y⃗

if and only if

∀n(x_{n}E_{0}y_{n});

that is to say, we have E_{0}-equivalence at every coordinate.

2.5 Theorem (Hjorth-Kechris; [42]). Let E be a Borel equivalence relation with E ≤_{B} E_{0}^{ℕ}. Then exactly one of the following holds:

(I) E ≤_{B} E_{0};

(II) E_{0}^{ℕ} ≤_{B} E.

There are no other known immediate successors to E_{0}, but Ilijas Farah in [12] has proposed a continuum of plausible examples which are inspired by ideas in Banach space theory. What he does show is that these examples are incomparable, and that any equivalence relation strictly below any of them is essentially countable. The gnawing technical difficulty at the end of his argument is our inability to determine which countable equivalence relations are hyperfinite. Very recently, in a spectacular and unpublished piece of work, Su Gao and Steve Jackson showed all equivalence relations arising from the Borel actions of countable abelian groups are hyperfinite, and on this basis we might hope for further clarification in the coming years.

Although we are at a loss to provide further global dichotomy theorems, there is something more that can be said if we restrict ourselves to the region of equivalence relations which are below isomorphism of countable structures.

2.6 Definition. For L a countable language, we let ≅_{mod(L)} be isomorphism on the standard Borel space of L-structures with underlying set ℕ. For ψ ∈ L_{ω_{1},ω} we let ≅_{mod(ψ)} be the restriction of this equivalence relation to models of ψ.

2.7 Lemma (Becker-Kechris; [6]). Let E be Borel. Then the following are equivalent:

(I) E ≤_{B}≅_{mod(L)} for some countable language L

(II) E ≤_{B} E_{S_{∞}}, where E_{S_{∞}} arises from the continuous action of a S_{∞} on a Polish space.

2.8 Definition. If either of these equivalent conditions hold, then we say that E admits classification by countable structures.

In the still unpublished [38] a dichotomy theorem was recently announced for equivalence relations admitting classification by countable structures. It should be emphasised that this proof is long and has not been refereed, and accordingly the result has a provisional status.

2.9 Theorem (Hjorth; [38]). Let E be a Borel equivalence relation admitting classification by countable structures. Then exactly one of

(I) E ≤ E_{∞}, that is to say, E is essentially countable; (II) E_{0}^{ℕ} ≤_{B} E.

2.2. Anti-structure

The last section represented the good news. Now for the evil.

Refining an earlier result of Hugh Woodin’s, Alain Louveau and Boban Velickovic embedded P(ℕ)/Fin into the Borel equivalence relations considered up to Borel reducibility.

2.10 Theorem (Louveau-Velickovic, [55]). There is an assignment

A ↦ E_{A}

of Π ∼_{3}^{0} equivalence relations to subset of ℕ such that

E_{A_{1}} ≤_{B} E_{A_{2}}

if and only if A_{2} \ A_{1} is finite.

Therefore there is no global structure theorem for the ≤_{B} ordering.

Given the dichotomy theorems of [52] and [42] we might at least hope for some kind of basis of immediate successors to E_{0}, but even this seems unlikely. In [13] Farah obtains an infinite descending chain in ≤_{B} which is unlikely to be above an immediate successor to E_{0}. I say unlikely, though it is hard to make a fast guess at this point. Literally Farah obtains the existence of a sequence (F_{n})_{n∈ℕ} with each F_{n+1} <_{B} F_{n}, none of them essentially countable, and with the further property that any equivalence relation E ≤_{B} F_{n} at every n must be essentially countable. Since the F_{n}’s arise in a very simple form, in particular the continuous action of an abelian Polish group, there is some grounds for thinking the only countable equivalence relations reducible to one of these will be reducible to E_{0}.

Farah’s work also disproves the existence of a dichotomy theorem for being classifiable by countable structures in many dramatic ways. For instance he obtains an uncountable sequence of Borel equivalence relations, (E_{x})_{x∈2^{ℕ}}, which are not classifiable by countable structures, and such that for any x ≠ y and Borel E with

E ≤_{B} E_{x}, E_{y}

we have E classifiable by countable structures.

2.3. Beyond good and evil

There are slender few candidates for outright Borel dichotomy theorems in the style of 2.2, and 2.10 and the later results of Farah would seem to rush hopes for a global analysis of the ≤_{B} ordering. On the other hand there still seems that there are results which would help us understand when equivalence relations fall on some side of a key divide.

A distinction of philosophical interest is when we can classify by countable structures, which has clear parallels in broader mathematical practise. Here one has in mind for instance certain branches of topology, where one seeks complete algebraic invariants, and in effect one is trying to classify a certain equivalence relation by a countable algebraic structure considered up to isomorphism. The introduction of [33] surveys several examples along these lines from a variety of different mathematical areas.

2.11 Definition. Let G be a Polish group and X a Polish G-space. For U ⊆ G an open neighborhood of the identity, V ⊆ X an open neighborhood of a point x, the local U-V -orbit of x, written O(x, U, V), is the set of all y such that there exists a finite sequence of points x_{0} = x, x_{1}, x_{2}, ..., x_{n} = y in U with each x_{i+1} ∈ V · x_{i} – that is to say, we can move from x_{i} to x_{i+1} using some group element in V.

Then we say that the action of G on X is turbulent if the following three things hold:

(I) every orbit [x]_{G} is dense in X; (II) every orbit [x]_{G} is meager in X; (III) given x, y ∈ X, U an open neighborhood of y, V an open neighborhood of the identity in G, there is some x′ ∈ [x]_{G} ∩ U with y in the closure of the local orbit O(x′, U, V).

2.12 Theorem (Hjorth; [33]). If E_{G} arises from a turbulent action of G on the Polish G-space X and L is a countable language, then E_{G} is not Borel reducible to ≅_{mod(L)}.

Proof. (Sketch) We present the argument in a simple case with a number of simplifying assumptions. Consider the example of an S_{∞} action given before, where the space is X_{2}, consisting of all h ∈ 2^{ℕ×ℕ}, where at each n ≠ m there exists a k with h(n, k) ≠ h(m, k). Then define T_{2} on X_{2} by h^{1}T_{2}h^{2} if and only if the corresponding countable sets in 2^{ℕ} are equal. This is the orbit equivalence relation arising from the S_{∞} action

(σ · h)(m, n) = h(σ^{−1}(m), n).

We assume for a contradiction θ : X → X_{2} witnesses E_{G} ≤_{B} T_{2}.

Every Borel function is continuous on a comeager set, so let us actually make the simplifying assumption that θ is continuous everywhere.

Claim: For any n there is a comeager collection of x ∈ X which have some basic open neighborhood V_{x,n} of the identity in S_{∞} for which there is a comeager collection of σ ∈ V_{x,n} having

(θ(x))(n, ·) = (θ(σ · x))(n, ·).

Proof of Claim: For each individual point x and m we consider the Borel function

f_{x}^{m} : G → ℕ

which assigns to g ∈ G the natural number f(g) with θ(x)(m, ·) = θ(g · x)(f(g), ·). Each Borel set has the property of Baire, hence we can find open sets (O_{n}^{m})_{n∈ℕ} with dense union in G such that O_{n}Δf^{−1}(n) is meager at every n. Then for any

g ∈ ⋂_{m} ⋃_{n} O_{n}^{m}

we have at each ℓ some basic open V ⊂ G such that for a comeager collection of h ∈ V

θ(g · x)(ℓ, ·) = θ(hg · x)(ℓ, ·).

Thus we have show that inside each orbit the collection of g ∈ G for which g · x has the required property is comeager. Now the conclusion of the claim follows by Kuratowski-Ulam.

Let us make the additional and rather radical assumption that

x ↦ V_{x,n}

is defined everywhere, and “continuous” in the sense that given any basic open V and n the collection of x with V_{x,n} = V is open.

Let x, y ∈ X. Consider some n. It suffices to show that there is a representative of the orbit of x,

x′ ∈ [x]_{G},

which has θ(x′)(n, ·) = θ(y)(n, ·). By the above simplifying assumptions we can find a basic open neighborhood of U of y and V a basic open neighborhood of the identity in the group which has

(θ(z))(n, ·) = (θ(σ · z))(n, ·)

all z ∈ U, σ ∈ V.

Now if we take x′ ∈ [x]_{G} with

y ∈ \overline{O(x′, U, V)}

then we can find a sequence of points (z_{i})_{i∈ℕ}, each z_{i} ∈ O(x′, U, V) with

z_{i} → y.

By the assumptions on U and V we have θ(z_{i})(n, ·) = θ(x′)(n, ·) at all n, and hence θ(x′)(n, ·) = θ(y)(n, ·), as required. ⊣

As a practical matter [33] suggests turbulence to be the key phenomena in determining whether an equivalence relation is classifiable by countable structures. This has been supported in various examples and practical investigations, such as [25], [53], as well as some partial results given in [33]. The correct theorem was not established until a few years later.

2.13 Theorem (Hjorth; [35]). Let G be a Polish group and X a Polish G-space. Suppose E_{G}^{X} is Borel. Then exactly one of the following hold:

(I) E_{G}^{X} admits classification by countable structures; or (II) there is a turbulent Polish G-space Y with E_{G}^{Y} ≤ E_{G}^{X}.

3. Countable Borel equivalence relations

The subject of countable Borel equivalence relations is notable for its interactions with such diverse fields as geometric group theory, the ergodic theory of non-amenable groups, operator algebras, and superrigidity in the sense of Zimmer. There is a sense in which this interaction has been largely one way, since one finds logicians borrowing from these other fields rather than these areas being serviced by logic.

In the course of this period it is perhaps unsurprising that logicians have made a few notable contributions to the benefit of the other fields. However in almost every case the applications do not consist in applying deep ideas from logic, as found in say the work of Hrushovski, [46], but rather the natural result of mathematicians from one field rethinking the problems from another and approaching with a different point of view.

3.1. The global structure

In some form or another almost every argument which distinguishes countable Borel equivalence relations in the ≤_{B} ordering uses measure theory. At the very base level we can use Baire category arguments to show id(ℝ) <_{B} E_{0} but beyond this there is a fundamental obstruction.

3.1 Theorem (Sullivan, Weiss, Wright; [64]). Let E be a countable Borel equivalence relation on a Polish space X. Then there is a comeager set on which E is hyperfinite.

Proof. (Sketch; this draws from Segal’s thesis, [60]; see also [57].) E is induced by a countable group G acting by Borel automorphisms. Let us make the simplifying assumptions that G acts by homeomorphisms and the space is zero-dimensional – these assumptions are harmless, but we will skip over this point in the interest of keeping the argument short.

Let B be a countable basis for X consisting of clopen sets. Let (g_{n})_{n∈ℕ} enumerate the countable group G.

At each n let Y_{n} be the collection of sequences

A⃗ = (A_{0}, A_{1}, ..., A_{n}),

where each A_{i} is a finite subset of B. Given such a sequence we let RA⃗ be the graph on X given by

xRA⃗x′

if there is some i ≤ n, V, V′ ∈ A_{i}, with x ∈ V, x′ ∈ V′ and

g_{i} · x = x′.

We let EA⃗ be the equivalence relation arising from the connected components of RA⃗.

We then let Y_{n}^{∗} be the subset of Y_{n} for which the induced equivalence relation EA⃗ has all its equivalence classes finite. Given A⃗ = (A_{0}, ..., A_{n}) ∈ Y_{n}^{∗}, B⃗ = (B_{0}, ..., B_{m}) ∈ Y_{n}^{∗} where m ≥ n, we say that B⃗ extends A⃗ if every at every i ≤ n

A_{i} ⊆ B_{i}.

Claim: Given any x, y = g_{i} · x, n ≥ i and

A⃗ ∈ Y_{n}^{∗}

we can find an extension B⃗ ∈ Y_{n}^{∗} with

xRB⃗y.

Proof of Claim: The point is that we can add to A_{i} a small enough open set W around x that will specify x with sufficient exactness to ensure that for any x′ ∈ W, the EA⃗ equivalence class of x consists of {h_{i} · x′ : i ≤ ℓ} for some finite sequence h_{0}, ..., h_{ℓ−1} of group elements. (This is where we use zero-dimensionality.) Then we can find V ∈ B that specifies x with sufficient precision to ensure that for any x′ ∈ V and zEA⃗x′ we have either z = x′ or z ∉ V. Similarly we can do the same for y with some V′. Then if we were to take the simple extension B⃗ which has B_{i} = A_{i} ∪ {V, V′} but B_{j} = A_{j} at j ≠ i, then EA⃗ has index at most two in EB⃗. (Claim□)

We then let Y be the space of all infinite sequences

(A⃗^{n})_{n∈ℕ} ∈ ∏_{n∈ℕ} Y_{n}^{∗}

where each A⃗^{n+1} extends A_{n}. Any such (A⃗^{n})_{n∈ℕ} ∈ Y gives rise to an increasing sequence of Borel equivalence relations with finite classes, taking F_{n}^{(A⃗^{n})_{n∈ℕ}} to be EA⃗^{n}. ∏_{n∈ℕ} Y_{n}^{∗} comes with a natural product topology, under which it is Polish. Y is a closed subset of this product space, and hence Polish in its own right. The above claim shows that for all x ∈ X there is a comeager collection of (A⃗^{n})_{n∈ℕ} ∈ Y with

[x]_{E} = ⋃_{n∈ℕ}[x]_{F_{n}^{(A⃗^{n})_{n∈ℕ}}} .

Thus by Kuratowski-Ulam (see [49]), there is a comeager collection of (A⃗^{n})_{n∈ℕ} ∈ Y for which there is a comeager collection of x with [x]_{E} = ⋃_{n∈ℕ}[x]_{F_{n}^{(A⃗^{n})_{n∈ℕ}}}.

Taking any such (A⃗^{n})_{n∈ℕ} ∈ Y and corresponding comeager set, we are done. ⊣

On the other hand the subject of countable Borel equivalence relations considered up to Borel reducibility might collapse into a kind of death by heat dispersal if all these examples were hyperfinite. It turns that in the presence of an invariant probability measure, non-amenable groups give rise to equivalence relations which are not hyperfinite.

3.2 Definition. A countable group Γ is amenable if for any finite F ⊆ Γ and ϵ > 0 there is a finite, non-empty A ⊆ Γ such that for all σ ∈ F

\frac{|AΔσA|}{|A|} < ϵ.

As a word on the notation, we use |B| to denote the cardinality of the set B and BΔC to denote the symmetric difference of the sets B and C. Thus amenability amounts to the existence of something like “almost invariant” subsets of the group – given any finite collection of group elements, any tolerance (ϵ > 0), we can find a finite set which when translated by any of the group elements differs from its original position on a relatively small number of elements.

3.3 Example. 1 ℤ is amenable. Given F = {k_{1}, ..., k_{ℓ}} in the group and ϵ > 0, we let k = max(|k_{1}|, ..., |k_{ℓ}|), the max of the absolute values, and then let

N > \frac{2(k + 1)}{ϵ}.

The set A = {−N, −N + 1, −N + 2, ..., 0, 1, ..., N − 1, N} is as required.

2 On the other hand, 𝔽_{2} = ⟨a, b⟩, the free group on two generators, is most famously non-amenable. Just take ϵ = 1/10, F = {a, b, a^{−1}, b^{−1}}. We can see this by dividing the non-identity elements of 𝔽_{2} into four regions, C_{a}, C_{b}, C_{a^{−1}}, C_{b^{−1}}, where a (reduced) word is in the region C_{u} if it begins with u.

Consider some putative set A that is trying to witness amenability for 1/10 and {a, b, a^{−1}, b^{−1}}. For u = a, b, a^{−1}, or b^{−1}, n ∈ ℕ, if at least n of A’s elements are not in C_{a^{−1}}, C_{b^{−1}}, C_{a}, or C_{b}, respectively, then at least n of u · A’s elements are in C_{a}, C_{b}, C_{a^{−1}}, or C_{b^{−1}} respectively. Therefore we can clearly find two distinct u_{1}, u_{2} with at least three fifths of u_{i} · A’s elements in C_{u_{i}}. One of these sets must differ from A by at least \frac{1}{10}|A|.

Note that there is nothing special here about the use of almost invariant sets in 𝔽_{2}. We would obtain a similar contradiction if we considered almost invariant functions in ℓ^{1}(𝔽_{2}). G iven f ∈ ℓ^{1}(𝔽_{2}) and u ∈ {a, b, a^{−1}, b^{−1}} we could look at the norm of the corresponding f_{u} defined by f_{u}(σ) = f(σ) if σ ∈ C_{u}, f_{u}(σ) = 0 otherwise.

3.4 Definition. A standard Borel probability space is a standard Borel space X equipped with an atomless σ-additive probability measure μ on its Borel sets.

3.5 Theorem. Let Γ be a countable non-amenable group. Suppose Γ acts freely and by measure preserving transformations on a standard Borel probability space (X, μ). Then E_{Γ} is not hyperfinite.

Proof. We sketch the argument just in the case that G = 𝔽_{2}.

For a contradiction suppose E_{𝔽_{2}} = ⋃_{n∈ℕ} F_{n}, where each F_{n} is finite, Borel, and has F_{n} ⊆ F_{n+1}. At each x ∈ X we define

f_{n,x} : 𝔽_{2} → ℝ

with

f_{n,x}(σ) = \frac{1}{|[x]_{F_{n}}|}

if σ^{−1} · xF_{n}x,

f_{n,x}(σ) = 0

otherwise. Let

f_{n}(σ) = ∫_{X} f_{n,x}(σ)dμ.

For any x we have ||f_{n,x}||_{ℓ^{1}} = 1, and so certainly ||f_{n}||_{ℓ^{1}} = 1, and in fact for any measurable set A ⊆ X

∑_{σ} ∫_{A} f_{n,x}(σ)dμ ≤ μ(A).

Claim: For any γ ∈ 𝔽_{2}, as n → ∞

||f_{n} − γ · f_{n}||_{ℓ^{1}} → 0.

Proof of Claim: Note that if xF_{n}γ · x then

γ · f_{n,x} = f_{n,γ·x},

since for any σ we have

γ · f_{n,x}(σ) = f_{n,x}(γ^{−1}σ) = \frac{1}{|[x]_{F_{n}}|}(= \frac{1}{|[γ · x]_{F_{n}}|})

if and only if σ^{−1}γ · xF_{n}x, which, by the assumption xF_{n}γ · x, amounts to saying if and only if

f_{n,γ·x}(σ) = \frac{1}{|[γ · x]_{F_{n}}|}.

Thus if we let A_{n,γ} = {x ∈ X : xF_{n}γ · x}, then

∫_{A_{n,γ}} γ · f_{n,x}(σ)dμ = ∫_{γ·A_{n,γ}} f_{n,x}(σ)dμ,

and hence

||f_{n} − γ · f_{n}||_{ℓ^{1}} ≤ 2 ∑_{σ} ∫_{X\A_{n,γ}} f_{n,x}(σ)

= 2 ∫_{X\A_{n,γ}} ∑_{σ} f_{n,x}(σ) = 2μ(X \ A_{n,γ}).

Since μ(A_{n,γ}) → 1 as n → ∞, we are done. (Claim□)

Now we have established the existence of almost invariant functions in ℓ^{1}(𝔽_{2}), and this can be refuted by the same kind of argument as used to show the non-amenability of 𝔽_{2}. ⊣

For the longest while there was only a small finite number of countable Borel equivalence relations known to be distinct in the ≤_{B} ordering. It was a notorious open problem to establish even the existence of ≤_{B}-incomparable examples. This was finally settled by:

3.6 Theorem (Adams, Kechris, [2]). There exists an assignment of countable Borel equivalence relations to Borel subsets of ℝ,

B ↦ E_{B},

such that E_{B} ≤_{B} E_{C} if and only if B ⊆ C.

Formally their result relied on the superrigidity theory of Zimmer for lattices in higher rank lie groups, [69], and thus in turn had connections with earlier work of Margulis and Mostow. I will say nothing about Zimmer’s work as such, but instead try to describe some of the engine which drives the theory.

3.7 Definition. For a compact metric space K we let M(K) denote the probability measures on K. By the Riesz representation theorem this can be identified with a closed subset of a the dual of C(K), and thus is a Polish space in its own right. Note that the homeomorphism group of K acts on M(K) in a natural way:

(ψ · μ)(f) = μ(ψ^{−1} · f),

where ψ^{−1} · f is defined by (ψ^{−1} · f)(x) = f(ψ(x)).

3.8 Definition. Given a group Γ acting on a space X and another group H we say that

α : Γ × X → H

is a cocycle if for all γ_{1}, γ_{2} ∈ Γ, x ∈ X

α(γ_{2}, γ_{1} · x)α(γ_{1}, x) = α(γ_{1}γ_{2}, x).

Here is a typical situation in which a cocycle arises. Given Γ a group of Borel automorphisms of standard Borel space X, H a countable group acting freely and in a Borel manner on a standard Borel space Y, if

θ : X → Y

witnesses E_{Γ}^{X} ≤_{B} E_{H}^{Y}, then we obtain a Borel cocycle by letting α(γ, x) be the unique h ∈ H with

h · θ(x) = θ(γ · x).

3.9 Lemma (Furstenberg, Zimmer, [20], [69]). If Δ is a countable amenable group acting in a Borel manner on a standard Borel probability space (X, μ) and

α : Δ × X → Hom(K)

is a cocyle into the homeomorphism group of a compact metric space K, then we can find a measurable assignment of measures

x ↦ ν_{x},
X → M(K),

which is almost everywhere equivariant; that it is to say

∀^{μ}x∀γ(α(γ, x) · ν_{x} = ν_{γ·x}.

The applications of this lemma and its forerunners are much too involved to be discussed here. Some understanding of what is going on can be given by the following simple lemma. In fact, the hypotheses of the lemma can never be realized, and indeed the real theorem is that equivalence relations of the form E_{Γ×ℤ}^{X} are never treeable, but I simply want to give a short illustration of some key ideas.

3.10 Lemma. Suppose Γ is a non-amenable countable group. Let X = {0, 1}^{Γ×ℤ} and let μ be the product measure on this space. Let Γ × ℤ act in the natural way on this space:

σ · f(τ) = f(σ^{−1}τ)

for any f ∈ X, σ, τ ∈ Γ × ℤ.

Suppose 𝔽_{2} acts freely and by Borel automorphisms on standard Borel probability space Y. Suppose

θ : X → Y

witnesss E_{Γ×ℤ}^{X} ≤_{B} E_{𝔽_{2}}^{Y}.

Then there is homomorphism ρ : Γ → 𝔽_{2} and an alternative reduction

θ̂: X → Y,

which is equivalent in the sense that

θ̂(x)E_{𝔽_{2}}^{Y}θ(x)

all x ∈ X and whose resulting cocycle accords with ρ almost everywhere, in the sense that

∀^{μ}x∀γ(ρ(γ) · θ̂(x) = θ̂(γ · x).

Proof. (Sketch) Let

α : (Γ × ℤ) × X → 𝔽_{2}

be the induced cocycle.

Let ∂(𝔽_{2}) denote the infinite reduced words from {a, b, a^{−1}, b^{−1}}. This is a compact metric space on which 𝔽_{2} acts by homeomorphisms. (See Appendix C [43].) Following 3.9 we can find a measurable assignment

X → M(∂(𝔽_{2})),
x ↦ μ_{x},

with

α(e, ℓ) · μ_{x} = μ_{(e,ℓ)·x}

for all ℓ ∈ ℤ and a.e. x ∈ X. (We will use e for the identity in Γ and 0 for the identity in ℤ.)

Claim: We can choose this assignment so that the measures μ_{x} concentrate almost everywhere on more than two points.

Proof of Claim: (Sketch only; see Appendix C of [43] for a completely precise argument for a more general claim.) Suppose instead that every such ℤ-equivariant assignment of measures concentrates on at most two points.

The key observation here is that if

x ↦ μ_{x}

is such an assignment of measures then for any γ ∈ Γ so is

x ↦ α(γ, 0)^{−1} · μ_{(γ,0)·x}.

Thus to prevent a situation in which we could simply pile on more and more of these measures, passing from say x ↦ μ_{x} to

x ↦ \frac{μ_{x} + α(γ, 0)^{−1} · μ_{(γ,0)·x}}{2}

we must be able to obtain an assignment which is actually Γ-equivariant.

Using certain strong ergodicity properties of the shift action of Γ on X (see Appendix A [43]) and the hyperfiniteness of the action of 𝔽_{2} on ∂(𝔽_{2})

(see Appendix C [43]) we obtain that there is a single measure ν_{0} such that for almost all x we have some σ_{x} ∈ 𝔽_{2} with

σ_{x} · μ_{x} = ν_{0}.

Thus replacing θ with the reduction

θ̂: x ↦ σ_{x} · θ(x)

we obtain a reduction of E_{Γ×ℤ}^{X} to E_{H}^{X} where H is the subgroup of 𝔽_{2} corresponding which stabilizes the measure ν_{0}. This subgroup will be amenable (see Appendix C [43]), which in turn provides a contradiction to the nonamenability of Γ × ℤ (see Appendix A [43] again). (Claim□)

So now we obtain an assignment of measures that concentrates on at least three points almost everywhere. Here an observation of Russ Lyons (the rough idea is that a measure on ∂(𝔽_{2}) concentrating on more than three points can be assigned a center in an 𝔽_{2}-equivariant manner – again, see Appendix C [43]) gives us a measurable map

η : X → 𝔽_{2}

such that

η((e, ℓ) · x) = α((e, ℓ), x) · η(x)

almost everywhere. Replacing θ : X → Y by

θ̂: X → Y,
x ↦ η(x)^{−1} · θ(x)

we obtain a reduction with an induced cocycle

α̂ : (Γ × ℤ) × X → 𝔽_{2}

with α̂((e, ℓ), x) = e almost everwhere.

Then, as at the proof of 2.2 [43], the ergodicity of the action of ℤ on X gives that for any γ ∈ Γ,

x ↦ α̂((γ, 0), x)

is a.e. invariant. From this it is easily seen that we obtain the required homomorphism into 𝔽_{2}. ⊣

Arguments of this form can be found very clearly in papers by Scot Adams such as [1], though in truth the ideas trace back to Margulis and Mostow by the way of Zimmer’s [69].

[43] gives a self contained proof of the existence of many ≤_{B}-incomparable countable Borel equivalence relations using arguments along these lines, but something similar is implicit in the superrigidity results of [69] to which Adams and Kechris appeal in the course of proving 3.6. In that case one is dealing not with the compact space ∂(𝔽_{2}) but certain compact quotients of an algebraic group (see for instance page 88 [69]) or the measures on projective space over a locally compact field (see 3.2.1 [69]). The appearance of product group actions is more subtle, but present; superrigidity typically on works for groups of matrices of rank greater than two, when we can hope to find a subgroup which indeed has the form Γ × ℤ for Γ non-amenable.

In passing it should also be mentioned that there are applications of Furstenberg lemma to the theory of the homeomorpism group of the circle. In [26] the combinatorial properties of M(S^{1}) play a role in understanding what kinds of homomorphisms are possible into Homeo(S^{1}).

3.2. Treeable equivalence relations

The situation with the countable Borel equivalence relations can in some sense be viewed as resolved. It is a giant mess, with many incomparable examples, but we know it to be the ghastly mess that it is.

The situation with treeable countable Borel equivalence relations is far different.

It is well known that not all treeable equivalence relations are hyperfinite. If one take the free part of the shift action of 𝔽_{2} on 2^{𝔽_{2}} then the resulting equivalence relation, E_{T ∞}, is treeable – we define a Borel treeing by xT x′ if there is a generator of 𝔽_{2} which moves x to x′. The equivalence relation is not hyperfinite, as shown for instance in [43], since the product measure concentrates on the free part and is 𝔽_{2}-invariant.

It is also known that there is a maximal countable treeable equivalence relation. [47] shows that for any treeable countable Borel equivalence relation E one has E ≤_{B} E_{T ∞}.

After that precious little is known. [37] gives the existence of a treeable equivalence relation E with E_{0} <_{B} E <_{B} E_{T ∞}, but at the time of writing it is still open whether there are exactly two non-hyperfinite treeable countable Borel equivalence relations up to Borel reducibility.

3.3. Hyperfiniteness

One of the enduring problems in this field is to determine which countable Borel equivalence relations are hyperfinite. Nowadays this is almost always asked in the Borel context, since the measure theoretic setting is completely understood.

3.11 Theorem (Connes-Feldman-Weiss; [8]). Let G be a countable amenable group acting by measure preserving transformations on a standard Borel probability space (X, μ). Then there is a conull set on which the orbit equivalence relation is hyperfinite.

Equivalently, we can find a measurable reduction of E_{G} to E_{0}.

Even this result for very simple groups remains inscrutiatingly difficult in the Borel setting.

3.12 Theorem (Jackson-Kechris-Louveau, [47]). Let G be a finitely generated group with a nilpotent subgroup H with [G : H], the index of H in G, finite. If G acts by Borel automorphisms on a standard Borel space X, then the resulting equivalence relation E_{G} is hyperfinite.

There was a considerable pause until quite recently it was shown:

3.13 Theorem (Gao-Jackson, [24]). Let G be a countable abelian group. If G acts by Borel automorphisms on a standard Borel space X, then the resulting equivalence relation E_{G} is hyperfinite.

To give an idea of how difficult these problems have proved, it was not until 3.13, despite considerable efforts, we even knew that the commensurability equivalence relation on ℝ \ {0},

rE_{c}s ⇔ r/s ∈ ℚ

was hyperfinite.

It would be natural to conjecture all E_{G}’s arising from the Borel action of an countable amenable group on a standard Borel space are hyperfinite. This conjecture is presently far out of reach, and actually has little in the way of supporting evidence.

4. Effective cardinality

One way in which to look at the theory of Borel reducibility is as a kind of theory of Borel cardinality, and in this sense there are definitely roots in papers by Harvey Friedman such as [16]. If we were to truly embrace a mathematical ontology consisting solely of Borel objects, then we would also be naturally led to consider certain kinds of quotients arising from Borel equivalence relations and to make any comparison along the lines of cardinality it seems we would use something like Borel reducibility.

In this sense I am more inclined to consider the theory of ≤_{B} as something like a theory of cardinality, as opposed to a theory of reducibility of information, as one finds in the theory of Turing reducibility. In fact there are close parallels between the structure of the ≤_{B}-ordering on Borel equivalence relations and the cardinality theory of L(ℝ) under suitable determinacy assumptions.

4.1 Definition. For A, B ∈ L(ℝ) write

|A|_{L(ℝ)} ≤ |B|_{L(ℝ)},

the L(ℝ) cardinality of A does not exceed that of B, if there is an injection

i : A ↪ B

in L(ℝ).

4.2 Lemma (Folklore, but see [39].). Assume AD^{L(ℝ)}. Let E, F be Borel equivalence relations on ℝ. If

|ℝ/E|_{L(ℝ)} ≤ |ℝ/F |_{L(ℝ)}

then there is a function

f : ℝ → ℝ

in L(ℝ) with for all x_{1}, x_{2} ∈ ℝ

x_{1}Ex_{2} ⇔ f(x_{1})F f(x_{2}).

Then in parallel to Silver’s theorem Woodin has shown:

4.3 Theorem (Woodin). Let A ∈ L(ℝ). Then exactly one of:

(I) There is an ordinal α with |A|_{L(ℝ)} ≤ |α|_{L(ℝ)} – in other words, A is well orderable; or (II) |ℝ|_{L(ℝ)} ≤ |A|_{L(ℝ)}.

And for Harrington-Kechris-Louveau:

4.4 Theorem (Hjorth, [30]). Assume AD^{L(ℝ)}. Let A ∈ L(ℝ). Then exactly one of:

(I) There is an ordinal α with |A|_{L(ℝ)} ≤ |2^{α}|_{L(ℝ)} – in other words, A has a well orderable separating family; or (II) |ℝ/E_{v}|_{L(ℝ)} ≤ |A|_{L(ℝ)}.

In (II) we can equivalently say that P(ω)/Fin embeds into A.

The theory of effective cardinality, whether we choose to explicate it using Borel functions and objects or the more joyously playful world of L(ℝ), can also be compared with the idea of classification difficulty. If the effective cardinality of A is below that of B, then any objects which suceed as complete invariants for B do as well for A. Here one could even begin certain kinds of wild speculations, to the effect that subconsciously part of the mathematical activity of vaguely searching for some kind of ill defined classification theorem for a class of objects is in fact a query as to its effective cardinality.

Even if circumspection draws us back from grand fantasies along these lines, calculations of Borel cardinality undoubtedly say something about classification difficulty. A non-reduction result, saying E not Borel reducible to F, will inform as to which kinds of objects would be insufficient, in the Borel category at least, to act as complete invariants for E.

Finally, in the context of L(ℝ) there is a curious refinement of the usual Borel hierarchy theorem.

4.5 Theorem (Hjorth, [31]). Assume AD^{L(ℝ)}. Then for every α < β < ω_{1}

|Π ∼_{α}^{0}|_{L(ℝ)} < |Π ∼_{β}^{0}|_{L(ℝ)}.

Thus, not only is Π ∼_{α}^{0} strictly included in Π ∼_{β}^{0}, it is also smaller in effective cardinality. Sharper results are possible here. [3] determines the exact levels of the Wadge degrees which provide new cardinals in L(ℝ).

5. Classification problems

Until this point our discussion has largely been concerned with the structural properties of the ≤_{B} ordering. However in the sum total of papers on the subject, the majority deal not with the abstract issues of this partial order, but instead with the specific problems of placing certain natural occurring equivalence relations in this hierarchy.

Here one pictures specific levels of classification difficulty, and for an example “from the wild” we ask whether it is smooth, or classifiable by countable structures, or universal for countable Borel equivalence relations, and so on.

5.1. Smooth versus non-smooth

At the very base, we have the distinction between smooth and non-smooth. If E ≤_{B} id(ℝ) then we can classify the E-classes by points in a concrete space.

The very first writings dealing at all with attempting to understand the classification difficulty of mathematical problems as a kind of science in and of itself are due to George W. Mackey, for instance in [56]. Very specifically he was concerned with understanding which groups have smooth duals. Here given U(H), the unitary group of a separable Hilbert space, and irreducible representations

σ_{1}, σ_{2} : Γ → U(H),

we set σ_{1} ∼ σ_{2} if there is some unitary T ∈ U(H) with

T^{−1} ∘ σ_{1}(γ) ∘ T = σ_{2}(γ)

all γ ∈ Γ. For Γ countable, the space of unitary representations is a Polish space, since it is a closed subset of

U(H)^{Γ},

and then the irreducible representations are a G_{δ} subset of those, and hence again Polish in the subspace topology (see for instance [10]). We say that the group Γ has smooth dual if the equivalence relation ∼ on the irreducibles is smooth. Ultimately it was determined in [65] that the countable groups with smooth duals are exactly the abelian by finite.

Another example is the equivalence relation of matrices over ℂ considered up to similarity. As remarked in [28], this equivalence relation is smooth, since we can assign to a matrix its canonical Jordan form as a complete invariant.

Some authors following on from this have drawn out from Mackey’s writings the entirely general view that in all branches of mathematics the dividing line between classifiable and non-classifiable is given by the smooth versus non-smooth distinction. Indeed the author of [10] appears to flirt with such a opinion. For a rather different take one might look at the introduction of [33]; indeed this work cites many apparent classification theorems – Baer’s analysis of rank one torsion free abelian groups, the von Neumann-Halmos analysis of discrete spectrum transformations, the spectral theorem for infinite dimensional unitary operators – for equivalence relations which are non-smooth.

5.2. Universal for Polish group actions

It is well known – probably first due to Leo Harrington, but for a proof see [44] – that there is no universal Borel equivalence relation: For every Borel equivalence relation E there is another Borel equivalence relation F which does not Borel reduce to E. On the other hand there is a universal Σ ∼_{1}^{1} equivalence relation, which we might in some sense think of as sitting on the throne above all our examples.

As a practical matter almost all the equivalence relations which seem to have independent interest arise as, or are reducible to, orbit equivalence relations induced by the continuous action of a Polish group on a Polish space. Among these there is an upermost example: E_{G_{∞}}^{X_{∞}}, induced by the continuous action of a Polish group G_{∞} on a Polish space X_{∞}. Although we are stepping slightly outside the subject of Borel equivalence relations as such, E_{G_{∞}}^{X_{∞}} can be viewed as a kind of extreme, at the opposite end to id(ℝ), of an equivalence relation with maximal complexity.

In unpublished work Alexander Kechris and Slawek Solecki showed that in the natural Borel structure compact metric spaces considered up to homeomorphism are ∼_{B} with, bi-Borel reducible with, E_{G_{∞}}^{X_{∞}}. A recent and published example is given by [25], where they show that complete separable metric spaces considered up to isometry is ∼_{B} to E_{G_{∞}}^{X_{∞}}, as are closed subsets of the Uyrsohn space under the orbit equivalence relation induced by the isometry group of this space.

5.3. Universal for S_{∞}

As shown in [6], for each Polish group G there is a corresponding Polish Gspace X with E_{G}^{X} universal for orbit equivalence relations of G, moreover in the case of G = S_{∞} we can take X to be Mod(L) for any L which contains at least one relation of arity two or higher. For future reference let us fix some such universal space for S_{∞} orbit equivalence relations and denote the corresponding equivalence relation by E_{∞S_{∞}}. Again this is Σ ∼_{1}^{1} but not Borel.

The study of which equivalence relations lie at the level of E_{∞S_{∞}} go right back to the first work of logicians on the ≤_{B} ordering.^{1} One finds ≤_{B} defined independently, quite by accident with the exact same notation and terminology, in [28] and [17]. The first of these papers deals with the structural result of 2.2, and the second almost entirely with specific issues of which classes of isomorphism are ∼_{B} with E_{∞S_{∞}}. More generally, given any E which admits classification by countable structures, we automatically have E ≤_{B} E_{∞S_{∞}} and we can go on to ask when in fact the reverse ≥_{B} holds as well.

[17] demonstrate, among other examples, that isomorphism of countable groups, countable fields, and countable linear orderings, are all ∼_{B} E_{∞S_{∞}}. (In general, given any ψ ∈ L_{ω_{1},ω}, the set of M ∈ Mod(L) satisfying ψ is Borel, and hence forms a standard Borel space in its own right.) More recently [23] show countable boolean algebras up to isomorphism are universal in this class.

In general most of the questions in this area which can be reasonably posed have been answered. However one wound remains with us from [17]:

Question (Friedman-Stanley) Is isomorphism on countable torsion free abelian groups ∼_{B} to E_{∞S_{∞}}?

This question remains open despite several efforts to give it closure.

5.4. E_{∞}

If E is a countable equivalence relation then 1.10 shows E is induced by the Borel action of a countable group, G. Any countable group is realizable as a closed subgroup of S_{∞}, and so by [6] we have that E admits classification by countable structures.

Thus the countable Borel equivalence relations form a subclass of the equivalence relations admitting classification by countable structures, with a top most example E_{∞}. The subclass is proper, since T_{2} from our earlier examples, corresponding to equality on countable sets of reals, is <_{B} above E_{∞}. In fact, the lesson we take away from say [44] is that the countable Borel equivalence relations are only a tiny part of the totality of equivalence relations admitting classification by countable structures.

1I choose these words warily. Although the notion of ≤_{B} does not appear explicitly in the writings of Mackey, and was first formally isolated in the late 80’s, in some form the idea is already implicit, both in Mackey and in other authors such as [14].

Nevertheless many important examples lie in the class of countable Borel equivalence relations, and on the whole this has proved to be one of the hardest and most exciting parts of the discipline. In general terms a class of countable structures tends to be ≤_{B} E_{∞}, that is to say, essentially countable, if there is some notion of finite rank.

Simon Thomas and Boban Velickovic, [68], in answer to questions raised in [41], show that isomorphism on finitely generated groups and fields of finite transcendence degree are ∼_{B} E_{∞}.

5.5. E_{0}

If the diagram has a well described bottom, id(ℝ), then it equally has a well defined second rung, that of E_{0}. Implicitly in the classical literature on this subject there is a classification theorem in terms of hyperfiniteness.

5.1 Theorem (Baer, in effect; see [18]). Isomorphism on rank one torsion free abelian groups is hyperfinite.

In fact, Baer’s original result dates back to the 1920’s and is not stated in this form. Rather he explicitly associates to each rank one torsion free group a kind of type, consisting of a description of orders considered up to finite difference, and goes on to show that the type is a complete invariant. This has generally been considered a satisfactory classification of the rank one torsion free groups, and Fuchs in [18] asks the vague but earnest question whether the rank two torsion free abelian groups can be “classified”.

5.2 Definition. For each n let S_{n} be the subgroups of (ℚ^{n}, +). Let ≅_{n} be the isomorphism relation on these groups.

Every rank n torsion free abelian group appears as a subgroup of ℚ^{n}, and in turn these subgroups all have rank ≤ n. Moreover two subgroups of ℚ^{n} are isomorphic if and only if there is a linear transformation over the rationals which sends one to the other, and thus the equivalence relation ≅_{n} has countable classes – and thus ≤_{B} E_{∞}.

The authors of [41] observe that Baer had implicitly shown ≅_{1}≤_{B} E_{0} and went on to suggest as a possible explication of Fuchs’ question whether ≅_{2}≤_{B} E_{0}. With absolutely no evidence, and armed only with the arrogance of ignorance, [41] conjectured that ≅_{2}∼_{B} E_{∞}.

This conjecture was refuted by Thomas in a spectacular sequence of papers. There have several papers around the subject of isomorphism on finite rank torsion free abelian groups, most of which are surveyed in [66] 36 I. Borel equivalence relations 5.3 Theorem (Thomas; [67]). At every n

≅_{n}<_{B}≅_{n+1} .

Bibliography

[1] Scot Adams. Indecomposability of treed equivalence relations. The Israel Journal of Mathematics, 112:271–287, 1990.

[2] Scot Adams and Alexander Kechris. Linear algebraic groups and countable Borel equivalence relations. The Journal of the American Mathematical Society, 13:909–943, 2000.

[3] Alex Andretta, Greg Hjorth, and Itay Neeman. Effective cardinals in bold faced point classes. preprint, ∞.

[4] Howard Becker. The number of path-components of a compact subset of ℝ^{n}. In Logic Colloquim ’95, volume 11 of Lecture Notes in Logic, pages 1–16. Springer, Berlin, 1998.

[5] Howard Becker. Polish group actions: dichotomies and generalized embeddings. The Journal of the American Mathematical Society, 11:397– 449, 1998.

[6] Howard Becker and Alexander Kechris. The descriptive set theory of Polish group actions. London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1996.

[7] John Burgess. A selection theorem for group actions. The Pacific Journal of Mathematics, 80:333–336, 1979.

[8] Alain Connes, Jacob Feldman, and Benjamin Weiss. An amenable equivalence relation is generated by a single transformation. The Journal of Ergodic Theory and Dynamical Systems, 1:431–450, 1981.

[9] Randall Dougherty, Steve Jackson, and Alexander Kechris. The structure of hyperfinite Borel equivalence relations. The Transactions of the American Mathematical Society, 341:193–225, 1994.

[10] Edward Effros. Transformation groups and C^{∗}-algebras. The Annals of Mathematics, 81:38–55, 1965.

[11] Ilijas Farah. Ideals induced by Tsirelson submeasures. Fundamenta Mathematicae, 159:243–259, 1999.

[12] Ilijas Farah. The basis problem for turbulent actions I. The Annals of Pure and Applied Logic, 108:189–203, 2001.

[13] Ilijas Farah. The basis problem for turbulent actions II. The Proceedings of the London Mathematical Society, 82:169–177, 2001.

[14] Jacob Feldman. Borel structures and invariants for measurable transformations. The Proceedings of the American Mathematical Society, 46:383–394, 1974.

[15] Jacob Feldman and Calvin Moore. Ergodic equivalence relations, cohomology, and von Neumann algebras i, ii. The Transactions of the American Mathematical Society, 234:289–324, 325–359, 1977.

[16] Harvey Friedman. On the necessary use of abstract set theory. Advances in Mathematics, 41:209–280, 1981.

[17] Harvey Friedman and Lee Stanley. A Borel reducibility theory for classes of countable structures. The Journal of Symbolic Logic, 54:894– 914, 1989.

[18] Lazlo Fuchs. Infinite Abelian Groups, volume 36 of Pure and Applied Mathematics. Academic Press, Cambridge, 1970.

[19] Alexander Furman. Orbit equivalence rigidity. The Annals of Mathematics, 150:1083–1108, 1999.

[20] Hillel Furstenberg. Boundary theory and stochastic processes in homogeneous spaces. The Proceedings of Symposium in Pure Mathematics, 26:193–229, 1973.

[21] Damien Gaboriau. Cox ut des relations d’equivalence et des groupes. Inventiones Mathematica, 139:41–98, 2000.

[22] Damien Gaboriau and Sorin Popa. An uncountable family of nonorbit equivalent actions of 𝔽_{n}. The Journal of the American Mathematical Society, 18:547–559, 2005.

[23] Su Gao and Riccardo Camerlo. The completeness of the isomorphism relation for countable boolean algebras. The Transactions of the American Mathematical Society, 353:491–518, 2001.

[24] Su Gao and Steve Jackson. Hyperfiniteness of abelian group actions. To appear, ∞.

[25] Su Gao and Alexander Kechris. On the classification of Polish spaces up to isometry. The Memoirs of the American Mathematical Society, 161, 2003.

[26] Eitienne Ghys. Groups acting on the circle. Enseignement Mathematique, 47:329–407, 2001.

[27] John Glimm. Type i C^{∗}-algebras. The Annals of Mathematics, 73:572– 612, 1961.

[28] Leo Harrington, Alexander Kechris, and Alain Louveau. A Glimm-Effros dichotomy for Borel equivalence relations. The Journal of the American Mathematical Society, 3:903–928, 1990.

[29] Leo Harrington, David Marker, and Saharon Shelah. Borel orderings. The Transactions of the American Mathematical Society, 310:293–302, 1988.

[30] Greg Hjorth. A dichotomy for the definable universe. The Journal of Symbolic Logic, 60:1199–1207, 1995.

[31] Greg Hjorth. An absoluteness principle for borel sets. The Journal of Symbolic Logic, 63:663–693, 1998.

[32] Greg Hjorth. Orbit cardinals: on the effective cardinalities arising as quotient spaces of the form X/G where G acts on a Polish space X. The Israel Journal of Mathematics, 111:193–229, 1999.

[33] Greg Hjorth. Classification and orbit equivalence relations. Mathematical Surveys and Monographs. American Mathematical Society, Providence, 2000.

[34] Greg Hjorth. Vaught’s conjecture on analytic sets. The Journal of the American Mathematical Society, 14:125–143, 2001.

[35] Greg Hjorth. A dichotomy theorem for turbulence. The Journal of Symbolic Logic, 67:1520–1540, 2002.

[36] Greg Hjorth. Group actions and countable models. In Logic Colloquium ’99, pages 3–29. Association for Symbolic Logic, 2004.

[37] Greg Hjorth. A converse to Dye’s theorem. The Transactions of the American Mathematical Society, 357:3083–3103, 2005.

[38] Greg Hjorth. A dichotomy theorem for isomorphism. preprint, ∞.

[39] Greg Hjorth. Effective cardinals. preprint, to appear.

[40] Greg Hjorth. Non-treeability for product group actions. The Israel Journal of Mathematics, to appear.

[41] Greg Hjorth and Alexander Kechris. Borel equivalence relations and classifications of countable models. The Annals of Pure and Applied Logic, 82:221–272, 1996.

[42] Greg Hjorth and Alexander Kechris. Recent developments in the theory of Borel reducibility. Fundamenta Mathematicae, 170:21–52, 2001.

[43] Greg Hjorth and Alexander Kechris. Rigidity theorems for actions of product groups and countable Borel equivalence relations. The Memoirs of the American Mathematical Society. American Mathematical Society, Providence, 2005.

[44] Greg Hjorth, Alexander Kechris, and Alain Louveau. Borel equivalence relations induced by actions of the symmetric group. The Annals of Pure and Applied Logic, 92:63–112, 1998.

[45] Greg Hjorth and Slawomir Solecki. Vaught’s conjecture and the Glimm-Effros property for Polish transformation groups. The Transactions of the American Mathematical Society, 351:2623–2641, 1999.

[46] Ehud Hrushovski. The Manin-Mumford conjecture and the model theory of difference fields. The Annals of Pure and Applied Logic, 112:43– 115, 2001.

[47] Steve Jackson, Alexander Kechris, and Alain Louveau. Countable Borel equivalence relations. The Journal of Mathematical Logic, 2:1–80, 2002.

[48] Vladimir Kanovei. When is a partial order linearizable. Fundamenta Mathematicae, 155:301–309, 1998.

[49] Alexander Kechris. Classical descriptive set theory. Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1995.

[50] Alexander Kechris. Rigidity properties of Borel ideals on the integers. Topology and its Applications, 85:195–205, 1998.

[51] Alexander Kechris. New directions in descriptive set theory. The Bulletin of Symbolic Logic, 5:161–174, 1999.

[52] Alexander Kechris and Alain Louveau. The classification of hypersmooth Borel equivalence relations. The Journal of the American Mathematical Society, 10:215–242, 1997.

[53] Alexander Kechris and Nikolaus Sofronidis. A strong generic ergodicity property of unitary and self-adjoint operators. The Journal of Ergodic Theory of Dynamical Systems, 21:193–229, 2001.

[54] Cristoff Kuratowski. Espaces Metrisables, Espaces Complets 2d ed. Monografie Matematyczne. Polish Mathematical Society, Warszawa-Wroclaw, 1948. French.

[55] Alain Louveau and Boban Velickovic. A note on Borel equivalence relations. The Proceedings of the American Mathematical Society, 120:255– 259, 1994.

[56] George Mackey. Imprimitivity for represenations of locally cmpact groups. The Proceedings of the National Academy of Sciences, 35:537– 545, 1949.

[57] Benjamin Miller and Alexander Kechris. Topics in orbit equivalence. Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2004.

[58] Sorin Popa. Some rigidity results for non-commutative Bernoulli shifts. The Journal of Functional Analysis, 230:273–328, 2006.

[59] Ramez Sami. Polish group actions and the Vaught conjecture. The Transactions of the American Mathematical Society, 341:335–353, 1994.

[60] Miri Segal. Hyperfinitess. Hebrew University of Jerusalem, Jerusalem, 1997. PhD. Thesis.

[61] Nicolas Shalom and Yehuda Shalom. Orbit equivalence rigidity and bounded cohomolgy. Preprint, to appear.

[62] Jack Silver. Counting the number of equivalence classes of Borel and coanalytic equivalence relations. The Annals of Mathematical Logic, 18:1–28, 1980.

[63] Slawomir Solecki. Analytic ideals. The Bulletin in Symbolic Logic, 2:339–348, 1996.

[64] Dennis Sullivan, Benjamin Weiss, and Mikhail Wright. Generic dynamics and monotone complete c^{∗}-algebras. The Transactions of the American Mathematical Society, 295:795–809, 1986.

[65] Enver Thoma. Eine charakterisierung diskreter gruppen vom type i. Inventiones mathematique, 6:190–196, 1968.

[66] Simon Thomas. On the complexity of the classification problem for torsion-free abelian groups of finite rank. The Bulletin of Symbolic Logic, 7:329–344, 2001.

[67] Simon Thomas. The classification problem for torsion-free groups of finite rank. The Journal of the American Mathematical Society, 16:233– 258, 2003.

[68] Simon Thomas and Boban Velickovic. On the complexity of the isomorphism relation for finitely generated groups. The Journal of Algebra, 217:352–373, 1999.

[69] Robert Zimmer. Ergodic theory and semisimple groups. Monographs in Mathematics. Birkh user Verlag, Basel, 1984.

Index

E_{0}, 9 E_{1}, 9 G_{δ}, 6 ≤_{B}, 8 T_{2}, 10 amenable group, 23 Borel reducible, 8 classification of torsion free abelian

groups, 35 Effros Borel structure, 7 Glimm-Effros dichotomy, 14 hyperfinite equivalence relation, 12 local orbit, 19 Mod(L), 7 Polish G-space, 12 Polish group, 12 Polish space, 6 smooth equivalence relation, 10 standard Borel G-space, 12 standard Borel space, 6 treeable equivalence relation, 12 turbulence, 19