When is an Equivalence Relation Classifiable?

Greg Hjorth

Abstract. One finds in certain branches of analysis the idea that a classifiable equivalence relation is one for which we can assign points in a very concrete space as a complete invariant. Results by Effros, Glimm, and Mackey, and then later Harrington, Kechris, and Louveau, have given a thorough analysis of when such a classification is possible. In the last few years a similar analysis has been undertaken by descriptive set theorists regarding when an equivalence relation is classifiable by countable structures considered up to isomorphism. There is a kind of parallel theory of which equivalence relations can be assigned countable structures as complete invariants.

1991 Mathematics Subject Classification: 04A15 Keywords and Phrases: Equivalence relations, effective cardinality, classification, Polish group actions.

§0 One answer The question posed in the title of this talk is admittedly a vague one. Not only is the question itself vague, but moreover any answer to this question will necessarily be subjective, since a classification theorem will only be satisfactory if it is judged as such for some specific purposes.

Nevertheless, in certain branches of mathematics, especially those influenced by the works of George Mackey, one finds the idea that a classifiable equivalence relation is one for which points in some very concrete spaces – such as ℝ, ℂ, 𝕋, C([0, 1]) – can be assigned in some reasonably ‘nice’, preferably Borel, manner. Ultimately I will discuss some alternative notions of classifiable and present motivating examples for this line of research. Before continuing we should understand the following definition.

0.1 Definition Let E be an equivalence relation on a Polish space X. E is smooth or tame if there is Polish space Y and a Borel function

θ : X → Y

such that for all x, y ∈ X

xEy ⇔ θ(x) = θ(y).

Just so there are no confusions about the definitions, a Polish space is a separable topological space that admits a complete compatible metric – and so the class of Polish spaces includes objects like the reals, the complex numbers, Hilbert space, and so on. A function between Polish spaces is said to Borel if the pullback of any open set is Borel.

It is also customary in this context to refer to a Polish space stripped down to its Borel structure as a standard Borel space; that is to say, (Y, B) is a standard Borel space if there is a Polish topology τ on Y with respect to which B is the σ-algebra generated by the τ-open sets.

In definition 0.1 we could just as well insist that Y be ℝ, since any Polish space allows a Borel injection into the reals.

It may then be helpful to think of the function

θ : X → ℝ

from 0.1 as lifting to an injection

θ̂: X/E → ℝ,

and that in this sense the Borel cardinality of X/E is less than or equal to the Borel cardinality of ℝ. Indeed this is an important theme in this branch of descriptive set theory: Determine the effective cardinality of quotients of the form X/E.

An another equivalent formulation of smoothness is that the space of equivalence classes, X/E = {[x]_{E} : x ∈ X}, be a subspace of a standard Borel space in the quotient Borel structure – that is to say, if we let B_{E} be the collection of subsets of X/E of the form {[x]_{E} : x ∈ A} for A ⊂ X an E-invariant (any x ∈ A has [x]_{E} ⊂ A) Borel set, then there is some standard Borel space (Y, B) with Y ⊃ X/E and B_{E} = {A ∩ X/E : A ∈ B}. Finally, E is smooth if and only if there is a countable sequence (A_{n})_{n∈ℕ} of E-invariant such that for all x, y ∈ X

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

I suppose that for a mathematician approaching this from another area the restriction to the Borel category may seem rather arbitrary. It turns out that many mathematically objects can be naturally realized as either points in some Polish space or as equivalence classes in some Polish space, and in fact the context of these problems is far wider than it may initially appear. The theorems stated below in §4 for Borel functions all pass to much more general classes of reasonably definable functions.

Historically the notion of smoothness as classifiability is extremely important. Not only does one find the notion in papers such as [2], [3], and [5], and perhaps [15]. These papers suggest a wider project to determine which equivalence relations are smooth and which classification problems are no harder than that of the equality relation on ℝ.

§1 Examples: Smooth 1.1 Example: Compact Riemann surfaces A very natural classification problem is that of compact Riemann surfaces considered up conformal equivalence. In this case there exists a reduction to the equality relation on the reals. The classical theory, as at say [11], obtains points in some standard Borel space as a complete invariant.

Of course one can ask how this sits with the original definition at 0.1. Here it is routine (but see [13] for details) to obtain a standard Borel space parameterizing (separable) complex manifolds in some natural manner. In this context one has that the set of points parameterizing the compact complex surfaces is Borel and the equivalence relation of conformal equivalence restricted to this Borel set is indeed smooth in exactly the sense of 0.1.

1.2 Example: Bernoulli shifts Let S = {s_{1}, ..., s_{n}} be a finite alphabet, σ : S^{ℤ} → S^{ℤ} be the shift map, and for p_{1}, p_{2}, ..., p_{n} a finite sequence of positive numbers summing to 1 let μ the product measure resulting from giving s_{i} the weight p_{i}. We may choose to think of two such systems as being equivalent if there is an invertible measure preserving map that conjugates them: that is, set (S_{1}, σ_{1}, μ_{1}) ∼ (S_{2}, σ_{2}, μ_{2}) if there is a measurable preserving bijection

π : (S_{1})^{ℤ} → (S_{2})^{ℤ}

such that

σ_{1} = π^{−1} ∘ σ_{2} ∘ π
∀A ⊂ (S_{2})^{ℤ}(μ_{2}(A) = μ_{1}(π^{−1}(A))).

Ornstein in [16] shows a single real number, the entropy of the system (S, σ, μ), provides a complete invariant. Moreover in a suitable standard Borel structure, this invariant can be calculated in a Borel fashion. Here as a suitable Borel structure one may represent the shift by the sequence p_{1}, p_{2}, ..., p_{n} ∈ ℝ^{n} for various n; the point is that a countable union of standard Borel spaces, such as ⋃_{n} ℝ^{n} is again standard Borel.

1.3 Example: Group representations Consider the irreducible representations of the group ℤ. Given a complex Hilbert space H with associated unitary group U of all inner product respecting transformations, we can let Irr(ℤ, H) be the space of homomorphisms

τ : ℤ → U

where U has no non-trivial invariant subspaces under τ[ℤ]. It is natural to think of τ_{1} and τ_{2} as somehow presenting equivalent representations if there is some T ∈ U with

τ_{1}(g) = T ∘ τ_{2}(g) ∘ T^{−1}

for all g ∈ ℤ.

The space of all representations may be naturally identified with a closed subspace of H^{ℤ}, and hence it is a Polish space. Furthermore the equivalence relation of interest here is induced by the continuous action of the group H.

Here Irr(ℤ, H) is non-empty if and only if H is one dimensional. Moreover we may identify the elements of Irr(ℤ, H) with characters, and thus a complete classification of these objects may be given by points in 𝕋, and hence ℝ.

On the other hand if G is finite the space Irr(G, H) will be non-empty only when H is finite dimensional. Then the above equivalence relation will be induced by the a continuous action of the now compact group U on the Polish space Irr(G, H). In general such orbit equivalence relations are always classifiable by points in ℝ.

§2 Examples: Non-smooth 2.1 Example: General Complex Domains One can view Becker, Henson, and Rubel in [1] as obtaining non-classifiability by a process tantamount to embedding the equivalence relation E_{0} of eventual agreement on infinite sequences of 0’s and 1’s into conformal equivalence on complex domains – so that for f, g : ℕ → {0, 1} we have fE_{0}g if there is some N ∈ ℕ such that

∀n > N(f(n) = g(n)).

Here E_{0} is an F_{σ} equivalence relation on {0, 1}^{ℕ}, the space of all infinite binary sequences in the product topology, and is in some ways (compare [9]) the canonical example of a non-smooth equivalence relation.

In fact if we assign D, the space of open subsets of ℂ, with the Effros standard Borel structure – under which it does have a natural Borel structure – then their argument can be seen as showing that there is a Borel function

θ : {0, 1}^{ℕ} → D

such that fE_{0}g if and only if θ(f) and θ(g) are biholomorphic. Since E_{0} is nonsmooth we obtain non-smoothness of conformal equivalence on arbitrary complex surfaces, even with respect to the Borel structure articulated in [13].

2.2 Example: Arbitrary measure preserving transformations Consider M_{∞} the group of all invertible measure preserving transformations of the unit interval . In the topology it inherits from its action on L^{2}([0, 1]) this is a topological group that is Polish as a space – that is to say, it is a Polish group. For instance, if (U_{n}) enumerates the basic open subsets of [0, 1] we obtain a complete metric with

d(π_{1}, π_{2}) = ∑_{n∈ℕ} 2^{−n}λ(π_{1}(U_{n})Δπ_{2}(U_{n})) + λ(π_{1}^{−1}(U_{n})Δπ_{2}^{−1}(U_{n})).

The obvious classification problem is for the conjugacy equivalence relation – it is natural to say that π_{1}, π_{2} : [0, 1] → [0, 1] are equivalent if they are conjugate, in the sense of their being some σ ∈ M_{∞} such that

σ ∘ π_{1} = π_{2} ∘ σ a.e.

This equivalence relation was observed by Feldman [5] to be non-smooth. As with 2.1 the proof rested on embedding E_{0}.

2.3 Example: Group representations again Let G be a countable discrete group that it not abelian-by-finite. Let H_{∞} be a separable infinite dimensional Hilbert space and U_{∞} the unitary group on H_{∞}. Again take Irr(G, H_{∞}) to be space of irreducible representations τ : G → U_{∞} with the equivalence relation of conjugacy –

τ_{1} ≈ τ_{2} ⇔ ∃A ∈ U_{∞}∀g ∈ G(τ_{1}(g) = A^{−1} ∘ τ_{2}(g) ∘ A).

It is known from [17] and [8] that Irr(G, H_{∞}) is non-empty and ≈ is not smooth: there is no Borel assignment of reals as complete invariants to Irr(G, H_{∞})/ ≈.

§3 More Examples: Puzzling cases The above were deliberately chosen with the view to supporting the intuition that classifiable means smooth. In the cases where there is a proof of smoothness, it is generally accepted as a classification theorem. In the cases where the equivalence relation does not admit points in ℝ as a complete invariant, the authors seemed to take that as a proof of at least some manner of non-classifiability. Consequently I hope the position that takes classifiable to mean smooth will seem an initially attractive one.

This much said, let us consider some examples where there is a more generous notion of classifiability implicit; these in turn have motivated the search for new tools in the study of Borel and analytic equivalence relations.

3.1 Question: Complex surfaces Becker, Henson, and Rubel in [1] explicitly ask: is there some reasonably non-pathological way to assign to every domain D ⊂ ℂ some countable set of complex numbers S_{D} such that

D ≅ D′

if and only if

S_{D} = S_{D′}?

3.2 Example: Discrete spectrum mpt’s Halmos and von Neumann in [10] showed that for discrete spectrum elements of M_{∞}, we may assign a countable collection {c_{i}(π) : i ∈ ℕ} of complex numbers that completely describe the equivalence class of π. While conjugacy on discrete measure preserving transformations is not smooth, the Halmos-von Neumann theorem would seem to constitute some sort of weaker notion of classification, and it certainly appears to be accepted as such.

3.3 Example: C^{∗}-algebras and topological dynamics (This is not quite analogous to examples 1.3 and 2.3, but derives from roughly the same area.) Giordano, Putnam, and Skau in [6] consider the problem of classifying minimal Cantor systems up to orbit equivalence. Two continuous

φ_{1} : X_{1} → X_{1},
φ_{2} : X_{2} → X_{2}

which are minimal in the sense of having no non-trivial closed invariant sets and are Cantor in the sense of X_{1}, X_{2} being compact, uncountable and completely disconnected metric spaces, are said to be orbit equivalent if there is a homeomorphism F : X_{1} → X_{2} which respects the orbit structure set wise, in that for all x

{φ_{2}^{i}(F (x)) : i ∈ ℤ} = F [{φ_{1}^{i}(x) : i ∈ ℤ}].

This problem is in turn equivalent to classifying a certain class of C^{∗}-algebras.

Here they produce countable ordered abelian groups as complete invariants. One similarly finds discussion of the classification of certain C^{∗} by countable discrete structures considered up to isomorphism in papers such as [4].

It is important to note a link between the kind of classification one finds in 3.1-2 and 3.3: Any equivalence relation that can be classified by a countable set of reals can be classified by countable structures considered up to isomorphism. For instance, if we let (q_{n}) enumerate the rationals, then to a countable unordered set A ⊂ ℝ we can associate the model M_{A} = {x_{a} : a ∈ A} with unary predicates (P_{n}) governed by the rule that

M_{A} ⊧ P_{n}(x_{a})

if and only if q_{n} < a. Trivially then reduction to the equality relation on ℝ implies classification by countable sets of reals, and hence classification by countable structures.

Thus we may be led to formulate a more generous notion of classifiability.

3.4 Question For which E can we provide some kind of countable structure considered up to isomorphism as a complete invariant?

Letting L be a countable language, we form Mod(L), the space of all Lstructures on ℕ with the topology generated by quantifier free formulas. This is a Polish space, and therefore there is a precise version of the question.

For which equivalence relations E on Polish X can we find a Borel θ : X → Mod(L) such that for all x, y ∈ X

xEy ⇔ θ(x) ≅ θ(y)?

In very general terms these examples may illustrate the kinds of concerns driving the descriptive set theory of equivalence relations, as well as the particular problem of classification by countable structures. I should add to these general remarks that the isomorphism relation on countable structures is historically important in logic, and that for someone in my area it seems intriguing to ask which classification problems may be simply reduced to that of countable models considered up to isomorphism.

§4 Some theorems I will begin with two sufficient conditions for classifiability, the first of which is trivial.

4.1 Theorem(folklore) Let G be a compact metrizable group acting continuously on a Polish space X with induced orbit equivalence relation E_{G}. Then E_{G} is smooth.

4.2 Theorem (Kechris [14]) Let G be a locally compact Polish group acting continuously on a Polish space X. Then there is a countable sequence of Borel functions (f_{i})_{i∈ℕ} such that for all x, y ∈ X

xE_{G}y ⇔ {f_{i}(x) : i ∈ ℕ} = {f_{i}(y) : i ∈ ℕ}.

In other words, we may classify by countable unordered sets of reals.

And two sufficient conditions for non-classifiability:

4.3 Theorem (folklore) Let G be a Polish group and X a Polish space. Suppose that

(i) some orbit is dense;

(ii) every orbit is meager (its complement includes the intersection of countably many open dense sets). Then E_{G} is not smooth.

4.4 Theorem (Hjorth [12]) Let G be a Polish group and X a Polish space. Suppose that

(i) some orbit is dense;

(ii) every orbit is meager (its complement includes the intersection of countably many open dense sets);

(iii) for some x ∈ X, the local orbits of x are all somewhere dense; that is to say, if V is an open neighborhood of 1_{G}, U is an open set containing x, and if O(x, U, V) is the set of all x̂ ∈ [x]_{G} such that there is a finite sequence (x_{i})_{i≤k} ⊂ U such that x_{0} = x, x_{k} = x̂, and each x_{i+1} ∈ V · x_{i}, then the closure of O(x, U, V) contains an open set.

Then there is no Borel (or even Baire measurable) θ : X → Mod(L) such that for all x, y ∈ X

xE_{G}y ⇔ θ(x) ≅ θ(y).

Consequently there is no sequence (f_{i})_{i∈ℕ} of Borel (or even reasonably definable) functions

f_{i} : X → ℝ

such that

xE_{G}y ⇔ {f_{i}(x) : i ∈ ℕ} = {f_{i}(y) : i ∈ ℕ}.

A Polish group action satisfying 4.4(i)-(iii) is called generically turbulent. Again I will return to the motivation and examples in the next and final

section. These examples on their own may suggest that 4.4 is the right theorem for showing this kind of non-classifiability.

However there are also results in [12] reinforcing this view. The presence of a generically turbulent action is necessary for non-classifiability in the sense that if E_{G} arises from the continuous action of Polish G on Polish X then either E_{G} is reducible to isomorphism on countable structures (using say universally Baire measurable functions) or there is a generically turbulent Polish G-space Y which admits a continuous G-embedding into X. (Here a function θ is said to be universally Baire measurable if for any Borel function ρ we have that θ ∘ ρ is Baire measurable – in the sense of pulling back open sets to sets with the Baire property.)

§5 Examples again 5.1 Example: Complex manifolds again By the uniformization theorem, conformal equivalence on complex surfaces may be reduced to an appropriately chosen locally compact group action.

Theorem (Hjorth-Kechris [13]) Let D be the space of all complex domains. Then there is a definable assignment

M ↦ S_{M}

of countable sets of reals to domains such that for all M, N ∈ D

M ≅ N ⇔ S_{M} = S_{N}.

Moreover it is Borel in the sense of there existing a countable sequence (f_{n}) of Borel functions from D to ℝ such that S_{M} always equals the (unordered) set {f_{n}(M) : n ∈ ℕ}.

But in higher dimensions one may embed a generically turbulent orbit equivalence relation and obtain:

Theorem (Hjorth-Kechris [13]) Let M^{2} be the space of two dimensional complex manifolds. Then there is no Borel assignment of countable structures up to isomorphism as complete invariants. Consistently with ZFC there is no definable assignment.

5.2 Example: Measure preserving transformations again Theorem (Hjorth) Let M_{∞} be the space of invertible measure preserving transformations on the unit interval. Consider the conjugacy equivalence relation ∼: π_{1} ∼ π_{2} if there is σ ∈ M_{∞} such that

σ ∘ π_{1} = π_{2} ∘ σ a.e.

Then there is no sequence (f_{i})_{i∈ℕ} of Borel functions

f_{i} : M_{∞} → ℝ

such that

π_{1} ∼ π_{2} ⇔ {f_{i}(π_{1}) : i ∈ ℕ} = {f_{i}(π_{2}) : i ∈ ℕ}.

In fact, ∼ is strictly more complicated than isomorphism on countable models: there is a Borel θ : Mod(L) → M_{∞} such that for all M, N ∈ Mod

M ≅ N ⇔ θ(M) ∼ θ(N),

but (for any choice of L) there is no Borel (or even universally Baire measurable) ρ : M_{∞} → Mod(L) such that for all π_{1}, π_{2} ∈ M_{∞}

π_{1} ∼ π_{2} ⇔ ρ(π_{1}) ≅ ρ(π_{2}).

5.3 Example: Discrete group representations again Theorem (Hjorth) Let G be a countable group that is not abelian-by-finite. Let H_{∞} be an separable infinite dimensional Hilbert space, let Irr(G, H_{∞}) be the space of irreducible representations of G in H_{∞}. Then there is no sequence (f_{i})_{i∈ℕ} of Borel functions

f_{i} : Irr(G, H_{∞}) → ℝ

such that

τ_{1} ≈ τ_{2} ⇔ {f_{i}(τ_{1}) : i ∈ ℕ} = {f_{i}(τ_{2}) : i ∈ ℕ}.

In fact there is no reasonably definable assignment of countable models considered up to isomorphism as complete invariants.

References

[1] J. Becker, C.W. Henson, L. Rubel, First order conformal invariants, Annals of Mathematics, vol. 102(1980), pp. 124-178.

[2] E. Effros, Transformation groups and C^{∗}-algebras, Annals of Mathematics, ser 2, vol. 81(1975), pp. 38-55.

[3] E. Effros, Polish transformation groups and classification problems, General topology and modern analysis (Proc. Conf., Univ. California, Riverside, Calif., 1980), pp.217-227, Academic Press, New York-London, 1981.

[4] G.A. Elliott, On the classification of inductive limits of sequences of semisimple finite-dimensional algebras, Journal of Algebra, vol. 38(1976), pp. 29-44.

[5] J. Feldman, Borel structure and invariants for measurable transformations, Proceedings of the American Mathematical Society, vol. 46(1974), pp. 383-394.

[6] T. Giordano, I.F. Putnam, C.F. Skau, Topological orbit equivalence and C^{∗}- crossed products, Journal Reine und Angewandt Mathematische, vol. 469(1995), pp. 51-111.

[7] J. Glimm, Locally compact transformations groups, Transactions of the American Mathematical Society, vol. 101(1961), pp. 124-138.

[8] J. Glimm, Type I C^{∗}-algebras, Annals of Mathematics, 1961, pp. 572-612.

[9] L.A. Harrington, A.S. Kechris, A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, Journal of the American Mathematical Society, vol. 3(1990), pp. 903-928.

[10] P.R. Halmos, J. von Neumann, Operator methods in classical mechanics, II, Annals of Mathematics, vol. 43(1942), pp. 332-50.

[11] Y. Imayoshi, M. Taniguchi, An introduction to Teichmüller spaces, Springer-Verlag, Berlin, 1992.

[12] G. Hjorth, Classification and orbit equivalence relations, manuscript (available at www.math.ucla.edu/˜ greg/research.html).

[13] G. Hjorth, A.S. Kechris, The complexity of the classification of Riemann surfaces by complex manifolds, preprint, UCLA, 1998.

[14] A.S. Kechris, Countable sections for locally compact group actions, Journal of ergodic theory and dynamical systems, vol. 12(1992), pp. 283-295.

[15] G.W. Mackey, Infinite-dimensional group representations, Bulletin of the American Mathematical Society, vol. 69(1963), pp.628-686.

[16] D.S. Ornstein, Bernoulli shifts with the same entropy are isomorphic, Advances in Mathematics, vol. 4(1970), pp. 337-52.

[17] E. Thoma, Eine Charakterisierung diskreter Gruppen vom type I, Inventiones Mathematique, vol. 6(1968), pp. 190-196.

Greg Hjorth Mathematics UCLA CA90095-1555 USA greg@math.ucla.edu