Contemporary Mathematics

A dichotomy theorem for being essentially countable

Greg Hjorth

Abstract. We introduce a definition to characterize when an orbit equivalence relation is Borel reducible to a countable equivalence relation. As a corollary we obtain a kind of low basis theorem – an orbit equivalence relation which arises from an effective action of a recursively presented Polish group on a recursive Polish space is Borel reducible to a countable Borel equivalence relation if and only if it is reducible to a Δ_{1}^{1} countable equivalence relation using a Δ_{1}^{1} function. We make some effort to draw out the consequences of the theorem for the model theoretic context, which in turn raises an open problem regarding first order logic.

1. Introduction

Definition We say that one equivalence relation, E, is Borel reducible to another, F, written E ≤_{B} F, if there is a Borel function θ such that

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

Definition An equivalence relation is Borel if it is Borel as a subset of the product of the space on which it is defined; it is countable if all its equivalence classes are countable. An equivalence relation on a standard Borel space X is essentially countable if there is a countable Borel equivalence relation E to which it is Borel reducible. Example It is trivially seen that if E arises from the Borel action of a countable group then necessarily it is Borel and each equivalence class is countable. More surprisingly Kechris has shown in [13] that the orbit equivalence relations arising from Borel actions of locally compact Polish groups are necessarily essentially countable. In very general terms the essentially countable equivalence relations might be thought of as those where there is some kind of notion of “finite rank”. Example Let σ be the sentence in L_{ω_{1},ω} whose models are exactly the finite rank torsion free abelian groups – that is to say, those abelian, torsion free groups which have some finite sequence g_{1}, g_{2}, ..., g_{n} such that for every h ≠ 0 there is some k such that k · h is in the subgroup generated by g_{1}, g_{2}, ..., g_{n}. Let Mod(σ) be the collection of models for σ with underlying set ℕ and the usual Borel structure (as described in [10]); let ≅_{Mod(σ)} be the equivalence relation of isomorphism on

\begin{matrix}c \\ ◯ \end{matrix}0000 (copyright holder)

1991 Mathematics Subject Classification. Primary 03E15, 04A15, 28A05, 54H05, 54H10; Secondary 03C15, 03C75.

Mod(σ). Then ≅_{Mod(σ)} is essentially countable. In fact, at each n we can let σ_{n} be the sentence whose models are exactly the rank n torsion free abelian groups, and we obtain ≅_{n}(=_{df} ≅_{Mod(σ_{n})}) Borel reducible to the action of ℚ^{n} by multiplication on the collection of all subgroups of (ℚ^{n}, +). Indeed recent years have witnessed an outpouring of papers on these equivalence relations – culminating in Simon Thomas’ [15], where it was shown that at every n one has

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

On the other hand it is known the isomorphism relation on countable torsion free abelian groups of infnite rank is not essentially countable in any of its customary Borel structures. (See e.g. [9], §5 [11]). Indeed a natural example of an equivalence relation which is not essentially countable is given by considering the coding of countable sets of reals; that is to say, for f_{1}, f_{2} ∈ ℝ^{ℕ} set

f_{1}F_{2}f_{2}

if for all n ∈ ℕ there exists m_{1}, m_{2} ∈ ℕ with

f_{1}(n) = f_{2}(m_{1}),
f_{2}(n) = f_{1}(m_{2}).

One certainly finds in [11] a proof that this equivalence relation is not essentially countable and in [9] a proof that isomorphism on general countable torsion free abelian groups Borel reduces F_{2} – though in both cases the results are folklore and invoking theorems of these papers would represent a degree of overkill. Example In the natural Borel structure, induced by looking at group operations placed on some fixed countable set, the isomorphism relation on finitely generated groups is essentially countable. (See [10].) This cannot be extended to general countable groups, since, as noted above, the isomorphism relation on countable abelian groups is already ≤_{B} above F_{2}. A special kind of essentially countable equivalence relation is formed by those which are smooth. Definition An equivalence relation E is smooth if there is a Borel function θ from the space on which E lives to ℝ (or, equivalently, any uncountable Polish space) with

x_{1}Ex_{2} ⇔ θ(x_{1}) = θ(x_{2}).

Not all essentially countable equivalence relations, even among those given by the isomorphism relation on some natural class of structures, are smooth. For instance, §3.1 of [6] gives a gentle proof that ≅_{1}, isomorphism of rank one torsion free abelian groups, is not smooth. In [10] a model theoretic analysis of smoothness and essential countability is presented.

Theorem 1.1. (Hjorth, Kechris) Let L be a countable language, with the usual Borel structure generated by first order logic.^{1} Let σ ∈ L_{ω_{1},ω}.

(I) The following are equivalent:

1So that for any ψ and a⃗ a finite sequence from ℕ, the set of M which satisfy ψ(a⃗) is Borel; this is indeed a standard Borel structure – see [4].

(a) ≅_{Mod(σ)} is smooth; (b) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ∈ Mod(σ) we have that

Th_{F} M,

the F -theory of M, is ℵ_{0}-categorical; (c) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ∈ Mod(σ) we have that

Th_{F} M,

the F -theory of M, is atomic. (II) The following are equivalent:

(a) ≅_{Mod(σ)} is essentially countable; (b) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ∈ Mod(σ) we have some a⃗ ∈ M such that

Th_{F} ⟨M, a⃗⟩,

the F -theory of the expansion of M obtained by adding names for all the elements of the a⃗ sequence, is ℵ_{0}-categorical; (c) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ∈ Mod(σ) we have some a⃗ ∈ M such that

⟨M, a⃗⟩,

is F -atomic.

Question Does there exist a first order theory T with ≅_{Mod(T)} essentially countable but not smooth? In light of 1.1 the question of whether smoothness and essential countability coincide for first order structures has a purely model theoretic reading. We are asking for a countable first order theory T for which there exists a countable fragment F over which every M ⊧ T has some a⃗ with

⟨M, a⃗⟩

F -atomic, but for which there is no fragment F′ for which every model M ⊧ T is F′-atomic; notice that this purely model theoretic formulation makes no explicit reference to countable models. In practically all the standard cases, say for instance the kinds of first order theories one finds in [2], it is easily determined that Mod(T) is either smooth or not essentially countable.

While I would conjecture that an example of a countable first order theory with ≅_{Mod(T)} essentially countable but non-smooth should exist, but simply be very hard to conceive, it does pay to seriously consider the possibility that there may be a structure theorem which denies this. This would represent some kind of basic obstruction or dichotomy theorem for L_{ω,ω} equivalence relations which is entirely missing for L_{ω_{1},ω}. Here it is worth pointing out that any such dichotomy theorem could not be proved using purely Baire category methods. Example Let G be a countable infinite group and L the language which contains function symbols F_{g} for each g ∈ G along with unary predicates (U_{n})_{n∈ℕ}. Let T be the first order theory which asserts that the composition of the functions exactly mimics the group (so for each g_{1}, g_{2} we have an axiom asserting F_{g_{1}} ∘ F_{g_{2}} = F_{g_{1}g_{2}}), the identity element acts trivially (∀a(F_{1}(a) = a)), and that otherwise the action of G is free (for each g ≠ 1 we have ∀a(F_{g}(a) ≠ a)). We can equip with Mod(T), the space of T -structures with underlying set ℕ, the usual topological structure, under which for every quantifier free ψ(·) and a⃗ we have

{M : M ⊧ ψ(a⃗)}

becomes clopen. In this topology it is a Polish space, and it follows easily from the usual kinds of arguments that on no comeager set C is

≅ |_{C}

smooth. (Compare the arguments from say §3.1[6].) A failure to be essentially countable is not yet detectable at the level of Baire category. If we take C to be the comeager set of models on which the group action is transitive, that is to say, the structure satisfies the L_{ω_{1},ω} sentence

∀a, b ⋁_{g∈G}(F_{g}(a) = b),

then we have that

≅ |_{C}

is essentially countable. This can be observed by (II)(c) 1.1 since on this set we have that any M ∈ C is the functional closure of any a ∈ M. However the isomorphism relation of the theory is not essentially countable. One way to see this is actually to use forcing, starting with a fragment F in the ground model and showing its failure to achieve (II)(c) in a suitable generic extension. We begin with an action of G on ℕ which is free but has infinitely many orbits and interpret the function symbols (F_{g})_{g∈G} accordingly. Then we force to obtain mutually Cohen generic (x_{a})_{a∈ℕ} elements of 2^{ℕ}; for each x_{a} we define the indicated pattern of unary predicates at a, with

U_{n}(a) ⇔ x_{a}(n) = 1.

It is a routine exercise in forcing to see that if a_{0}, a_{1}..., a_{ℓ} = a⃗ is a finite sequence from ℕ then

Th_{F} ⟨M, a⃗⟩

can be uniformly defined in

V^{[(x_{Fg (a_{i})})_{i≤ℓ,g∈G}]}

from F and (x_{F_{g}(a_{i})})_{i≤ℓ,g∈G}; then considering some b ∉ {F_{g}(a_{i}) : i ≤ ℓ, g ∈ G} we have that the F -type of x_{b} will not be in V^{[(x_{Fg (a_{i})})_{i≤ℓ,g∈G}]}, and hence certainly not F -atomic over Th_{F} ⟨M, a⃗⟩.

In this note we introduce a new definition to analyze essential countability. Definition Let G be a Polish group acting continuously on a Polish space X. We then say that X is a stormy G-space if for every non-empty, open V ⊂ G and x ∈ X we have that the natural map

g ↦ g · x

from V to V · x is not an open function. For future reference note that this definition has a kind of stability and upward persistence.

Lemma 1.2. If X is a stormy Polish G-space with respect to the topology τ, then for any stronger Polish G-space topology τ_{0} ⊃ τ we can find a G_{δ}(X, τ) subspace X_{0} ⊂ X such that (X_{0}, τ_{0}) is still a stormy Polish G-space.

Proof. It is an entirely classical fact that we can find an X_{1} which is a G_{δ} subspace of (X, τ) such that the induced inclusion map

(X_{1}, τ) ↪ (X, τ_{0})

is continuous; this follows since any Borel map is continuous on a dense G_{δ} (see [12]). Then we let

X_{0} = {x ∈ X : ∀^{∗}g ∈ G(g · x ∈ X_{1})},

the set of points for which a comeager collection of group elements place us in X_{1}. Using the continuity of the action of G on (X, τ_{0}) we still have that the induced map

(X_{0}, τ) ↪ (X, τ_{0})

continuous; so the topology τ on X_{0} equals τ_{0} on X_{0}. So then the structure of the definition of stormy, with its insistence that something happens at every orbit, guarantees that

(X_{0}, τ_{0})

is still stormy. □

An especially important instance of this definition is provided by model theory. Here let us consider that S_{∞} acts in the usual manner on the space of all models of some infinitary sentence σ ∈ L_{ω_{1},ω}; cofinally many of the Polish topologies are of the form τ_{F} for some countable fragment F – that is to say, they have a basis consisting of sets of the form

{M : M ⊧ φ(a⃗)}

for some φ ∈ F, a⃗ ∈ ℕ^{<ω}. (Again, see [10]). Here we may assume without loss of generality that we restrict ourselves to open sets V of the form

{π ∈ S_{∞} : ∀i ≤ ℓ(π(a_{i}) = a_{i})}

for some chosen a⃗ = a_{0}, a_{1}, ...a_{ℓ} in ℕ. Then the action of S_{∞} on ⟨ Mod(σ), τ_{F} ⟩ is stormy if and only if for every M ⊧ σ there is no a⃗ ∈ M with ⟨M, a⃗⟩ being F -atomic. Building on the methods of [8]:

Theorem 1.3. Let G be a Polish group and X a Polish G-space with the induced orbit equivalence relation E_{G}^{X} Borel. Then exactly one of the following holds:

(I) E_{G}^{X} is essentially countable;

(II) there is a stormy Polish G-space Y and a continuous G-embedding

ρ : Y → X.

Note in (II) that since ρ is one to one, the image ρ[Y] is Borel in X. Thus we may without loss of generality assume that Y is a Borel invariant subset of X and that we have found a Polish topology on Y which refines the original Xtopology under which the action remains continuous and becomes stormy. I have no concrete instances of an equivalence relation whose essential countability can only be affirmed or refuted by appeal to 1.3. However it can be said that the argument is effective; it uses the “geometry” of Σ_{1}^{1} sets in the now usual way. In particular the following represents a corollary of the method, which would presumably have not been obvious hitherto.

Theorem 1.4. Let G be a recursive Polish group and X a recursive Polish G-space with the induced orbit equivalence relation E_{G}^{X} ∈ Δ_{1}^{1}. If E_{G}^{X} is essentially countable, then there is a countable Δ_{1}^{1} equivalence relation on an effective Polish space to which E_{G}^{X} is reducible by a Δ_{1}^{1} function.

It might also be worth thinking about the model theoretic consequences of this theorem. Again, for a logician the isomorphism relations on classes of countable structures, while not quite Borel, comprise the central examples to which all others should be compared.

In the next corollary we bear in mind that ≅ _{Mod(σ)} is Borel if and only if there is some countable ordinal which bounds the Scott heights of models of σ. This result from [1] makes possible to state the following corollary in largely model theoretic terminology.

Corollary 1.5. Let σ ∈ L_{ω_{1},ω} for some countable language L. Assume that there is some countable ordinal which bounds the Scott heights of the models of σ. Then exactly one of the following holds.

(I) there is a countable fragment F ⊂ L_{ω_{1},ω} such that for every M ∈ Mod(σ) we have some a⃗ ∈ M such that

⟨M, a⃗⟩,

is F -atomic;

(II) there is a countable fragment F and some φ ∈ L_{ω_{1},ω} for which there exists a model of φ ∧ ψ, such that for every

M ⊧ φ

there is no a⃗ ∈ M with

⟨M, a⃗⟩

F -atomic.

To see that the corollary indeed follows from the theorem we observe first of all that (I) 1.5 is a direct restatement of (I) 1.3 in light of 1.1. This leaves (II). Note at this point we actually obtain in applying 1.3 a Borel S_{∞}-invariant Borel subspace Y and a Polish topology τ_{Y} on Y under which the action becomes stormy. We may find a countable fragment F such that τ_{F} ⊃ τ_{Y} by [14], and then by 1.2 find a Y_{0} ⊂ Y so that (Y_{0}, τ_{F}) is a stormy Polish S_{∞}-space; membership in Y_{0}, by [14] again, is given by some sentence φ ∈ L_{ω_{1},ω}.

2. Setting Sail

In all the lemmas below we assume that G is a Polish group and X is a Polish Gspace. E_{G}^{X} is the orbit equivalence relation. We assume there are fixed countable bases for X and G and that the basis for G contains a neighborhood basis of symmetric sets around 1_{G}.

Lemma 2.1. Suppose for every x ∈ X there is a non-empty open V ⊂ G with

V → V · x
g ↦ g · x

an open mapping. Then E_{G}^{X} is essentially countable.

Proof. Let us say that a non-empty basic open set V ⊂ G is x-safe if for all W ⊂ V open, non-empty, \overline{W · x} includes a non-empty relatively open subset of \overline{V · x}. Our assumption in the lemma yields that for each x ∈ X there is such an x-safe point. Note moreover that any non-empty open subset of an x-safe set is again x-safe. If V is x-safe and U ⊂ X is a non-empty basic open set, then we say that U is a V -x-harbor if there is some symmetric basic open neighborhood W of 1_{G} such that

∀h ∈ W ∀y ∈ U ∩ \overline{V h · x}(y ∈ \overline{V · x}).

Claim(I): For each x there are U and V as above.

Proof of claim: Choose open V̂ with

V̂ ↦ V̂ · x

an open map. Let g_{0} ∈ V̂. Appealing to the continuity of the group operations we may choose V ⊂ V̂ an open neighborhood of g_{0} and W a symmetric open neighborhood of 1_{G} such that

V W ⊂ V̂ .

V is clearly x-safe, since the mapping

V → V · x

is open. Let us choose U basic open with

\overline{V · x} ⊃ U ∩ \overline{V̂ · x}.

Then we have for all h ∈ W and y ∈ U ∩ \overline{V h · x}

y ∈ U ∩ \overline{V̂ · x}
∴ y ∈ \overline{V · x},

just as required. (Claim(I)□)

For each x, the collection of such (U, V) as above is uniformly Π ∼_{1}^{1} in x. The bases from which they are chosen are countable. Hence we may assign

x ↦ (U_{x}, V_{x})

in a Borel manner so that each V_{x} is x-safe and each U_{x} is a V_{x}-x-harbor. We can then define a Borel function

X → F(X),

from X to the standard Borel space of closed subsets of X, given by

x ↦ \overline{U_{x} ∩ V_{x} · x}.

By Kechris’ criterion for being essential countable, as presented at §5 of [7], it is enough to show that this map has countable image on each equivalence class (claim(II)) and that images of distinct equivalence classes are disjoint (claim(III)).

Claim(II): For each x, the set \{\overline{U_{y} ∩ V_{y} · y} : y ∈ [x]_{G}\} is countable.

Proof of claim: Otherwise we could find an uncountable set (y_{α})_{α∈ℵ_{1}} of elements of [x]_{G} with each y_{α} having the same U_{y_{α}} = U, V_{y_{α}} = V and the same W witnessing that U is a V -y_{α}-harbor, and yet

U ∩ \overline{V · y_{α}} ≠ U ∩ \overline{V · y_{β}}

for α ≠ β. Considering the separability of the group G we can find two y, y′ in this uncountable set with y ∈ W y′ and y′ ∈ W y. Then for all z ∈ U ∩\overline{V · y} ⊂ U ∩\overline{V W · y′} we must have by assumptions on U and V that z ∈ U ∩\overline{V · y′}, and conversely. Thus

U ∩ \overline{V · y} = U ∩ \overline{V · y′}

after all. (Claim(II)□)

Claim(III): If V is x-safe, then V · x is comeager in \overline{V · x}.

Proof of claim: Suppose not. Then there is some open U ⊂ X with V · x meager in U ∩ \overline{V · x}. And then we can find some open V_{0} ⊂ V and open U_{0} ⊂ U with V_{0} · x dense in U_{0} ∩ \overline{V · x}; which would place us in the situation that V_{0} is now our x-safe set and V_{0}· is meager in U_{0} ∩ \overline{V_{0} · x}. But then if we cover V_{0} · x by countably many closed sets, F_{0}, F_{1}, ...F_{n}, ..., each of which is nowhere dense in U_{0} ∩\overline{V_{0} · x}, then there must be some open non-empty W ⊂ V_{0} with W · x ⊂ F_{n}, at some n ∈ ℕ. And so W ⊂ V_{0} ⊂ V contradicts the definition of safety. (Claim(III)□)

□

This lemma has as an immediate corollary a result previously proved by Alexander Kechris by other means:

Corollary 2.2. (Kechris) If G is a locally compact Polish group and X is a Polish G-space, then E_{G}^{X} is essentially countable.

Proof. Fix x ∈ X and consider some non-empty precompact V ⊂ G. \overline{V} /G_{x} is compact^{2}, and hence the natural map

\overline{V} /G_{x} ↠ \overline{V} · x

maps closed sets to closed sets and is one-to-one and onto, thus it is open. In particular

V/G_{x} ↠ V · x

and

V ↠ V · x

are both open, and we fall under the case assumptions of 2.1. □

Lemma 2.3. If E_{G}^{X} is essentially countable, then for a comeager collection of x ∈ X there exists V ⊂ G open and non-empty with

V → V · x
g ↦ g · x

open.

2Here as elsewhere we follow the notation of [1]; so G_{x} is the stabilizer of the point x: that is to say, the subgroup {g ∈ G : g · x = x}.

Proof. Let

θ : X → Z

be a Borel function reducing E_{G}^{X} to some countable equivalence relation on a Polish space Z. Following 4.1 [3] (or see §18 of [12], along with references tracing back to earlier work by Burgess) we have that the range of θ is Borel and there is a Borel function

ρ : Ran(θ) → X

such that for all z ∈ Ran(θ) we have θ(ρ(z)) = z. For each x ∈ X let

p_{x} = ρ(θ(x));

thus this x ↦ p_{x} is a Borel function which in effect “selects” a countable set from each orbit. Following 7.1.2 of [1] (the orbit equivalence relation is Borel, and thus too is the stabilizer function x ↦ G_{x} from X to F(X)) we may in a Borel manner choose for each x a group element g_{x} with

g_{x} · x = p_{x}.

For the moment let us say that a point y ∈ X is good if there is some basic open neighborhood W of 1_{G} such that ∀^{∗}h ∈ W (p_{y} = p_{h·y}).

Claim: The set of good points is comeager.

Proof of claim: Otherwise use Kuratowski-Ulam to find some y ∈ X and open non-empty V ⊂ G such that ∀^{∗}g ∈ V (g · y is not good). Then since {p_{y′} : y′E_{G}^{X}y} is countable, we may find some single y_{0} and non-empty open W ⊂ V such that

∀^{∗}g ∈ W (p_{g·y} = y_{0}).

Then we find some basic open neighborhood Ŵ of 1_{G} and g_{0} ∈ G with Ŵ g_{0} ⊂ W; after possibly nudging g_{0} slightly, we may assume it falls into the relatively comeager sets {g ∈ W : g · y not good } and {g ∈ W : p_{g·y} = y_{0}}. But this gives

∀^{∗}g ∈ Ŵ (p_{g·(g_{0}·y)} = y_{0} = p_{g_{0}·y}),

and hence g_{0} · y must be good after all. (Claim□)

Let (W_{ℓ})_{ℓ∈ℕ} be a neighborhood basis at 1_{G}. We may apply the above claim to choose a Borel function

γ : X → ℕ

such that

∀^{∗}y ∈ X∀^{∗}h ∈ W_{γ(y)}(p_{y} = p_{h·y}).

Finally choose a comeager set C ⊂ X such that (a) γ|_{C} is continuous on C; (b) x ↦ g_{x} and x ↦ p_{x} are continuous on C; (c) for all x ∈ C we have ∀^{∗}g ∈ W_{γ(x)}(p_{x} = p_{g·x}).

Let x ∈ X be such that ∀^{∗}g ∈ G(g · x ∈ C). We can then find some non-empty open set V̂ ⊂ G and a point x_{0} ∈ [x]_{G} such that

∀^{∗}g ∈ V̂ (p_{g·x} = x_{0}).

We then find open U_{0} having non-empty intersection with V̂ · x such that for some single ℓ_{0}

∀y ∈ U_{0} ∩ C(γ(y) = ℓ_{0}).

Finally we pass to V = {g ∈ V̂ : g · x ∈ U_{0}}. I now want to show that g ↦ g · x is open from V to V ·x. So consider some y ∈ V ·x and V_{0} an open neighborhood of 1_{G}; I want to show that there is an open U_{1} containing y such that for all y_{1} ∈ V ·x∩U_{1} we have y_{1} ∈ V_{0} · y. First choose V_{1} an open neighborhood of 1_{G} with

(V_{1})^{−1} = V_{1},
(V_{1})^{4} ⊂ V_{0},
V_{1} · y ⊂ V · x,
V_{1} ⊂ W_{ℓ_{0}}.

And then take g_{0} ∈ V_{1} with

y′ = g_{0} · y ∈ C

and

p_{y′} = x_{0}.

And then let U′ ⊂ U_{0} be a basic neighborhood of y′ such that for all ŷ ∈ U′ ∩ C we have

gŷ ∈ g_{y′}V_{1}.

I claim that U_{1} = U_{0} ∩ (U′)^{ΔV_{1}} succeeds. For this purpose, let us suppose y_{1} ∈ V · x ∩ U_{1}; we can choose g_{1} ∈ V_{1} with

y_{2} =_{df} g_{1} · y_{1} ∈ V · x ∩ U_{1} ∩ C

and p_{y_{2}} = x_{0}. We may then appeal to the definition of U_{1} to find g_{2} ∈ V_{1} with

y′_{2} =_{df} g_{2} · y_{2} ∈ U′ ∩ C.

Since y_{2} ∈ U_{0} ∩C and g_{2} ∈ V_{1} ⊂ W_{ℓ_{0}} we can appeal to the assumption on U_{0} to find a sequence of group elements (ϵ_{n})_{n∈ℕ} which approach 1_{G} and have the property that

p_{ϵ_{n}·y′_{2}} = p_{y_{2}} = x_{0}

and each ϵ_{n} · y′_{2} ∈ C; since the function ŷ ↦ pŷ is continuous on C we must have p_{y′_{2}} equals x_{0} as well. By assumption on U′ we may find some h ∈ V_{1} with

g_{y′_{2}} = g_{y′} · h.

But this gives

g_{y′_{2}} · y′_{2} = x_{0} = g_{y′} · y′
∴ g_{y′}h · y′_{2} = g_{y′} · y′
∴ h · y′_{2} = y′
∴ hg_{2}g_{1} · y_{1} = y′ = g_{0} · y
∴ y_{1} = g_{1}^{−1}g_{2}^{−2}h^{−1}g_{0} · y ∈ (V_{1})^{4} · y ⊂ V_{0} · y

thereby concluding the proof. □ Definition Let G be a Polish group and X a Polish G-space. We say that X is a stormy G-space if

V → V · x
g ↦ g · x,

as V ranges over non-empty open subsets of the group and x ranges over points in X, is never an open mapping.

Proposition 2.4. If E_{G}^{X} ≤_{B} E, and X is a stormy Polish G-space, then E is not essentially countable.

Proof. This is a corollary of 2.3. □ In the remainder of the note we wish to start working towards a kind of converse

to this proposition. If E is induced by continuous action of a Polish group G, then E is essentially countable if and only if there is no stormy Polish G-space Y and continuous G-embedding from Y to X. It might be worthwhile first to pause in order to point out a couple of facts in the neighborhood of this definition. Example It is not hard to see that if the canonical map from V to V ·x is open, then V · x is comeager in its closure. This was implicitly proved at claim(III) of 2.1. The reverse implication fails. For instance let G = S_{∞}, the infinite symmetric group, and consider the space B_{2}, consisting of all one-to-one sequences x⃗ = (x_{0}, x_{1}, ...) ∈ ([0, 1])^{ℕ}. The responsible group acts by permutation of the indices in the obvious manner:

(π · x⃗)_{n} = x_{π^{−1}(n)}.

Consider the point y⃗ = (y_{0}, y_{1}, ...) defined by

y_{0} = 0,

but

y_{n} = \frac{1}{n}

for n > 0. We can then let

V_{0} = {π ∈ S_{∞} : π(0) = 0},

and for k > 0 we let

V_{k} = {π ∈ S_{∞} : π(k) = 0, π(0) = k}.

It is not hard to see that at each k > 0 we have V_{k} · y⃗ comeager in its closure; and thus for

V = ⋃_{k≥0} V_{k}

we have that V · y⃗ comeager in \overline{V · y⃗}. In fact the set V · y⃗ is a G_{δ}. A point x⃗ is in V · y⃗ if and only if

(i) ∀n, m∃ℓ(|x_{ℓ} − 1/n| < 1/m);

(ii) ∀n, ℓ_{1}, ℓ_{2}(ℓ_{1} ≠ ℓ_{2} ⇒ (|x_{ℓ_{1}} − 1/n)| ≥ (n + 1)^{−2} ∨ |x_{ℓ_{2}} − 1/n)| ≥ (n + 1)^{−2});

(ii) ∀ℓ, m∃n(|x_{ℓ} − 1/n| < 1/m);

(iv) ∀m∃k ≠ 0((|x_{0}| < 1/m)∨(|x_{k}| < (k+1)^{−2} ∧|x_{0} −1/k| < (m(k+1))^{−2})).

However the map

V → V · y⃗
π ↦ π · y⃗

is not open, since V_{0} · y⃗ is contained in a closed nowhere dense subset of \overline{V · y⃗}. Question Suppose that for every x ∈ X there is some V such that V · x is nonmeager in \overline{V · x}. Must E_{G}^{X} be essentially countable? (must the hypotheses of 2.1 hold?)

Proposition 2.5. Let G be a Polish group acting continuously on a Polish space X. Let B be a countable basis for G. Suppose

∀^{∗}x ∈ X∀W ∈ B(W ≠ 0 ⇒ W · x is meager in \overline{W · x}).

Then E_{G}^{X} is not essentially countable.

Proof. First of all we can take a dense G_{δ} set C ⊂ X such that for all x ∈ C and all W ∈ B, W ≠ 0 we have W · x is meager in \overline{W · x}. Then we can let

X_{0} = C^{∗G},

the Vaught transform of C. This is then an invariant G_{δ} set, and it suffices to show E_{G}^{X_{0}} is not essentially countable. For this it suffices to observe the following claim: Claim: X_{0} is a stormy Polish G-space. Proof of Claim: Fix x ∈ X_{0} and V ⊂ G open. We may then choose ϵ ∈ G with ϵ · x ∈ C. Then we may choose some non-empty W ∈ B with W ϵ ⊂ V. W · (ϵ · x) is meager in \overline{W · (ϵ · x)}, and thus the map

W → W · (ϵ · x)
g ↦ gϵ · x

is not open, and hence

W ϵ → W ϵ · x
gϵ ↦ gϵ · x

is not open, and thus, since W ϵ ⊂ V,

V → V · x
g ↦ g · x

is also not an open mapping. (Claim□)

□

Example There is a canonical example of a Polish group giving rise to an orbit equivalence relation which is not essentially countable. The orbit equivalence relation, F_{2}, corresponds in some rough sense to countable sets of reals. It arises on the B_{2}, the space of one-to-one sequences of reals in the unit interval, as a result of the natural action of S_{∞} permuting the indices, as introduced in the previous example. There are several ways to prove that this equivalence relation is not essentially countable. One can even use forcing and give a metamathematical proof. However the most direct method, as sketched in the exercises from chapter 2 of [6], is in fact to show that for B the canonical basis of S_{∞}, we have for each W ∈ B non-empty

∀^{∗}x⃗ ∈ B_{2}(W · x⃗ is meager in \overline{W · x⃗}),

and then to combinatorially verify that no function continuous on a comeager set can reduce F_{2} to a countable equivalence relation. The interest of 2.5 is to show that this “standard proof” fits naturally into a more general context.

3. Organizing the Cases

We from now on assume that G is a Polish group, which is recursive as a Polish space, with the group operations of multiplication and inversion both recursive and continuous. We assume that X is a recursive Polish space, equipped with an action of G on X which is recursive and continuous as a function

G × X → X.

We further assume E_{G}^{X} ∈ Δ_{1}^{1}. We wish to work towards showing that either E_{G}^{X} may be reduced in to a countable Borel equivalence relation or we may continuously and in an action respectful manner embed into X a stormy Polish G-space. In the first case one can in fact obtain that X is reducible to a countable Borel equivalence relation which is actually Δ_{1}^{1} using a function which is actually Δ_{1}^{1}; for clarity of exposition we will not stress the various small calculations which must be checked to obtain this extra effectivity, but instead push on with the proof of the main result at 1.3. At the very end we make a few remarks about how it may be refined. In general of course the Polish group, the Polish space, and the action of the group on the space might only be recursive in z, for some parameter z ∈ ℕ^{ℕ}. The proof of this more general case is a relativized version of the specific one we consider below. We assume that G and X come equipped with some suitably recursive countable bases in the sense of [8]. At some point it will be helpful to make some simplifying assumptions: We ask that the basis for G be closed under finite intersection and inversion; that the basic open sets in X and G be closed under translation by elements from the subgroup G_{0} consisting of recursive elements of G. Definition For A ⊂ X be Σ_{1}^{1}, W_{0}, V_{0} ⊂ G basic open with 1_{G} ∈ V_{0}, V_{0}^{−1} = V_{0}, we say that (A, W_{0}) is V_{0}-damming if for all V_{1} ⊂ G with 1_{G} ∈ V_{1}, V_{1}^{−1} = V_{1}, all x ∈ A^{ΔW_{0}}, and y_{0} ∈ V_{0} · x, there is B ∈ Δ_{1}^{1} and there is W_{1} ⊂ G basic open, with

y_{0} ∈ B^{ΔW_{1}}

such that

∀y_{1}, y_{2} ∈ V_{0} · x ∩ B^{ΔW_{1}}(y_{1} ∈ V_{1} · y_{2}).

The property of being V_{0}-damming is Π_{1}^{1} in the indices. The point is that if E_{G}^{X} is Δ_{1}^{1} then it follows from [1] §7.1 that the stabilizer function x ↦ G_{x} is Δ_{1}^{1}, in some appropriately understood effective presentation of the collection of closed subsets of G. From this we obtain that the set of (y_{1}, y_{2}, V_{1}) such that

y_{1} ∈ V_{1} · y_{2}

is Δ_{1}^{1}. This granted, it all routinely unravels to the level of Π_{1}^{1}. Thus by Π_{1}^{1}- reflection^{3}, if (A, W_{0}) is V_{0}-damming then we may find some Δ_{1}^{1} set D ⊃ A with (D, W_{0}) again V_{0}-damming. We are here confronted with a split in cases.

3See [5].

Definition We let X_{bad} be the set of all x ∈ X such that for all A ∈ Σ_{1}^{1}, all basic open W_{0}, V_{0} ⊂ G with 1_{G} ∈ V_{0}, V_{0}^{−1} = V_{0}, if x ∈ A^{ΔW_{0}} then (A, W_{0}) is not V_{0}-damming.

The set X_{bad} is Σ_{1}^{1} by the reflection argument indicated above. From the structure of the definitions one can see that X_{bad} is invariant under the action of G_{0}: if g_{0}·x ∈ A^{ΔW_{0}} for some g_{0} ∈ G_{0}, some V_{0}-damming (A, W_{0}), then x ∈ A^{ΔW_{0}g_{0}} and (A, W_{0}g) is g_{0}^{−1}V_{0}g_{0}-damming. But then we see that it must be invariant under the entire action of G, since if g_{0} · x ∈ A^{ΔW_{0}} then for any g sufficiently close to g_{0} we have g · x ∈ A^{ΔW_{0}}. Thus X_{bad} is invariant under the action of the entire group G. Whether this set X_{bad} is empty provides the split in cases. Notation From now on let us understand that

V_{0}, V_{1}, V_{2}, ..., V, V̂ , V′, W, ..., W_{0}, W_{1}, W_{2}...

and such like always refer to basic open subsets of the group G.

4. Case(1): X_{bad} is Empty

Claim 4.1. For x ∈ X there exists V_{0} non-empty such that for all y ∈ V_{0} · x and V_{1} symmetric containing 1_{G}, we have some B ∈ Δ_{1}^{1} and W ⊂ G such that

y ∈ B^{ΔW} ,
∀y_{1}, y_{2} ∈ B^{ΔW} ∩ V_{0} · x(y_{1} ∈ V_{1} · y_{2}).

Proof. The case assumption implies that every such x will be included in some A^{ΔW_{0}} which necessitates some V_{0} to succeed. □

But then we may find a countable algebra B of Δ_{1}^{1} subsets of X with the following properties:

(i) B is closed under finite boolean operations; (ii) B is closed under translation by elements in G; (iii) for any B ∈ B and V basic open we have

C^{ΔV} , C^{∗V} ∈ B;

(iv) ∀x ∈ X∃V_{0} ≠ 0∀y ∈ V_{0} · x∀V_{1}, if V_{1} is a symmetric neighborhood of 1_{G} then there exists B ∈ B and W ⊂ G such that

y ∈ B^{ΔW} ∧ ∀y_{1}, y_{2} ∈ B^{ΔW} ∩ V_{0} · x(y_{1} ∈ V_{1} · y_{2});

(v) we may decompose B into some directed union

B = ⋃_{α∈δ} B_{α},

some δ ≤ ω_{1}^{ck}, such that each element of B_{0} is either closed or open, and for γ > 0 we have that each element in B_{γ} is either the countable union or intersection of elements in

⋃_{α<γ} B_{α}.

Definition We let τ_{∗,B} be the topology generated by taking as a basis all sets of the form B^{ΔW} where B ∈ B and V ⊂ G basic open.

Claim 4.2. (X, τ_{∗,B}) is a Polish G-space giving rise to the same Borel structure as the original topology on X.

Proof. (v) implies by an appeal to transfinite induction on δ that there is a Polish topology having B as its basis. This granted, the claim follows from the Becker-Kechris theorem on changing topologies from chapter 5 of [1]. □

Claim 4.3. For each x ∈ X there is some V ⊂ G non-empty such that

g ↦ g · x

is an open mapping from V to (V · x, τ_{∗,B}).

Proof. For any x we appeal to the listed properties of B; V = V_{0} from (iv) succeeds by the definition of the topology τ_{∗,B}. □

But then by 2.1 we have that E_{G}^{X} is essentially countable.

5. Case(2): X_{bad} is Non-Empty

Following [8], we let

X_{∗low} = {x ∈ X : ∀^{∗}g ∈ G(ω_{1}^{ck(g·x)} = ω_{1}^{ck})}

and consider the topology τ_{∞}^{∗} whose basis consists of all sets of the form

X_{∗low} ∩ A^{ΔW} ,

A ∈ Σ_{1}^{1} in X, W basic open in G. As shown there, this is a Polish topology, and in fact (X_{∗low}, τ_{∞}^{∗}) is a Polish G-space in the action inherited from X. As at [8], we will use the following characterization of when ω_{1}^{ck(x)} = ω_{1}^{ck}: x is low exactly when for every Σ_{1}^{1} set A, either x ∈ A or there is a Σ_{1}^{1} set B with x ∈ B and A ∩ B = 0. Definition We let X_{∗bad} = X_{∗low} ∩ X_{bad}, equipped with the subspace topology induced by τ_{∞}^{∗}.

This X_{∗bad} is the intersection of two invariant sets, and hence G-invariant. It is relatively open in X_{∗low}, and hence again a Polish G-space. We want to show that it is in fact a stormy Polish G-space. So fix any x ∈ X_{∗bad}. If one point in the orbit of x fails to have the natural map V → V · x open for all V ⊂ G then so does every point in the orbit of x. Thus after possibly nudging x by a sufficiently generic group element g ∈ G we may assume first of all that

ω_{1}^{ck(x)} = ω_{1}^{ck}

and secondly that for all A ∈ Σ_{1}^{1}, if x ∈ A then there is a basic open neighborhood W of 1_{G} such that

x ∈ A^{∗W} .

The assumption that x ∈ X_{bad} implies that for any A_{0} ∈ Σ_{1}^{1},W_{0}, V_{0} ⊂ G, with 1_{G} ∈ V_{0}, V_{0}^{−1} = V_{0}, x ∈ A_{0}^{ΔW_{0}} there exists V_{1} with 1_{G} ∈ V_{1}, V_{1}^{−1} = V_{1}, and there exist x′ ∈ A_{0}^{ΔW_{0}}, y′ ∈ V_{0} · x′ such that for all B ∈ Δ_{1}^{1}, W_{1} ⊂ G,

y′ ∈ B^{ΔW_{1}} ⇒ (∃y′_{1}, y′_{2} ∈ B^{ΔW_{1}} ∩ V_{0} · x′(y′_{1} ∉ V_{1} · y′_{2})).

Claim 5.1. For all V ⊂ G with 1_{G} ∈ V, V^{−1} = V, there exist V_{1}, with 1_{G} ∈ V_{1}, and y ∈ V · x such that for all B ∈ Δ_{1}^{1}, W_{1} ⊂ G,

y ∈ B^{ΔW_{1}} ⇒ (∃y_{1}, y_{2} ∈ B^{ΔW_{1}} ∩ V · x(y_{1} ∉ V_{1} · y_{2})).

Proof. Otherwise the characteristic property of low reals implies that there is a Σ_{1}^{1} set A containing x such that for all x′ ∈ A , for all y′ ∈ V · x′, for all V_{1} containing 1_{G}, there exists B ∈ Δ_{1}^{1}, W_{1} ⊂ G such that

y′ ∈ B^{ΔW_{1}},
∀y′_{1}, y′_{2} ∈ V · x′ ∩ B^{ΔW_{1}}(y′_{1} ∈ V_{1} · y′_{2}).

Choose V_{0} containing 1_{G} with V_{0}^{2} ⊂ V, V_{0}^{−1} = V_{0}. Choose W_{0} ⊂ V_{0} ∩ W such that

x ∈ A^{∗W_{0}} ⊂ A^{ΔW_{0}}.

Then for any x̂ ∈ A^{ΔW_{0}} and any y′ ∈ V_{0} · x̂ and V_{1} with 1_{G} ∈ V_{1}, V_{1}^{−1} = V_{1}, we may choose

x′ ∈ W_{0} · x̂ ∩ A ⊂ V_{0} · x̂ ∩ A.

We have y′ ∈ V_{0}V_{0}^{−1} · x′ ⊂ V · x′, and so assumption on A yields some B^{ΔW_{1}} containing y′ such that

∀y′_{1}, y′_{2} ∈ V · x′ ∩ B^{ΔW_{1}}(y′_{1} ∈ V_{1} · y′_{2}).

But now note that for all y′_{1}, y′_{2} ∈ B^{ΔW_{1}} ∩ V_{0} · x̂ we have

y′_{1}, y′_{2} ∈ V_{0}V_{0}^{−1} · x′ ⊂ V · x′
∴ y′_{1} ∈ V_{1} · y′_{2}.

Thus A_{0} and W_{1} as given here contradict the assumption on x. □

The next claim states that we can obtain the same result even for B ∈ Σ_{1}^{1}. Since our topology is based around the Σ_{1}^{1} sets, not just the Δ_{1}^{1}, this is critical.

Claim 5.2. For all V ⊂ G with 1_{G} ∈ V, V^{−1} = V, there exist V_{1}, with 1_{G} ∈ V_{1}, and y ∈ V_{1} · x such that for all B ∈ Σ_{1}^{1}, W_{1} ⊂ G,

y ∈ B^{ΔW_{1}} ⇒ (∃y_{1}, y_{2} ∈ B^{ΔW_{1}} ∩ V · x(y_{1} ∉ V_{1} · y_{2})).

Proof. Fix V. Choose y and V_{1} as in the last claim. Since the property indicated for y is Σ_{1}^{1}(x), we may assume

ω_{1}^{ck(x,y)} = ω_{1}^{ck(x)} = ω_{1}^{ck}

by the Gandy low basis theorem. With this extra assumption on y we will prove that y satisfies the conclusion of the stronger claim presently before us. For this purpose consider some B ∈ Σ_{1}^{1} and W_{1} ⊂ G. Let

f_{B} : X → LO

be a rank, assigning to each z ∈ X a linear ordering f_{B}(z) ⊂ ℕ×ℕ in a Δ_{1}^{1} manner, such that f_{B}(z) is a well ordering if and only if z ∉ B. For each

α < ω_{1}^{ck}(= ω_{1}^{ck(x,y)})

we let B_{(α)} be the set of z ∈ X such that (α, ∈) allows an order preserving injection into (ℕ, f_{B}(z)). These sets are all Δ_{1}^{1}. One possibility is that for some α < ω_{1}^{ck} we have y ∉ (B_{(α)})^{ΔW_{1}}. But then if we let B̂ be the set of z ∈ B such that (ℕ, f_{B}(z)) does not contain α in its wellfounded part, then we have that B̂ is a Δ_{1}^{1} set included in B and y ∈ B̂^{ΔW_{1}}; and then we are immediately done by the assumptions on y. The other possibility is that for each α < ω_{1}^{ck} we have y ∈ (B_{(α)})^{ΔW_{1}}, and hence appealing to assumptions on y we may find y_{1}^{α}, y_{2}^{α} ∈ (B_{(α)})^{ΔW_{1}} with y_{1}^{α} ∉ V_{1} · y_{2}^{α}.

But then appealing to boundedness we can find an illfounded linear ordering (ℕ, <^{∗}) such that there exists y_{1}^{∞}, y_{2}^{∞} with

∃^{∗}g ∈ W_{1}((ℕ, <^{∗}) embeds intof_{B}(g · y_{1}^{∞})),
∃^{∗}g ∈ W_{1}((ℕ, <^{∗}) embeds intof_{B}(g · y_{2}^{∞})),
y_{1}^{∞} ∉ V_{2} · y_{2}^{∞}.

But if (ℕ, <^{∗}) embeds into f_{B}(g·y_{i}^{∞}) then f_{B}(g·y_{i}^{∞}) is illfounded and so g·y_{i}^{∞} ∈ B. Thus we are done. □

But since this last claim holds for any x ∈ X_{∗bad}, we have that the action of G on X_{∗bad} is indeed stormy.

6. Remarks on Effectivity

Little effort was made in case(1) to indicate how we can produce a lightfaced reduction to a lightfaced Δ_{1}^{1} equivalence relation. On the surface, 2.1 is phrased so that it only looks like a bold faced result and even the statement of Kechris’ criterion at 5.2 of [7] is only as a boldfaced result. First of all, inspecting the proof of Kechris’ criterion one actually obtains:

Proposition 6.1. (Kechris) Let E be a Δ_{1}^{1} equivalence relation on a recursive Polish space X and

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

a Δ_{1}^{1} function such that:

(i) θ has countable image on each equivalence class; (ii) θ maps distinct equivalence classes to disjoint sets.

Then there is a Δ_{1}^{1} equivalence relation F on {0, 1}^{ℕ} all of whose equivalence classes are countable such that θ witnesses E ≤_{B} F.

We are still faced with the brutishness of B and boldfacedness of 2.1. These problems are both dealt with in the same way. The main claim is this:

Claim 6.2. In the proof from case(1), we may assume that there is a D ⊂ X×ℕ in Δ_{1}^{1} such that each B ∈ B has the form

B = D_{k} = {x : (x, k) ∈ D}

for some suitable k.

This claim is proved by the boundedness theorem for Σ_{1}^{1} subsets of ω_{1}^{ck}; in some sense, we can “bound” all of the needed Δ_{1}^{1} sets in some manageable object. To see this recall that every Δ_{1}^{1} set has the form

{y : L_{α}[y] ⊧ φ(y)}

for some α < ω_{1}^{ck} and formula φ(·) of set theory. If V_{x} ⊂ G satisfies the statement of 4.1, then this is a Π_{1}^{1} property on the basic open set V. If x ∈ X, y ∈ V_{x} · x, then the statement that W_{0} ⊂ G and

B = {y : L_{α}[y] ⊧ φ(y)}

satisfy the assumption of 4.1 is Π_{1}^{1}(x, y). Thus we have in effect a Π_{1}^{1} function from X to the basic open sets in G, and then composing a Π_{1}^{1} function from X × X to

ω_{1}^{ck} × L(∈).

Π_{1}^{1} functions into the natural numbers are always Δ_{1}^{1}. Thus by boundedness we can assume that there is a single δ < ω_{1}^{ck} such that we can always choose α ≤ δ. In this way, granting certain routine technical details about effectivizing the enumeration, we can prove the claim. But then if (V̂_{ℓ})_{ℓ∈ℕ} is a basis for G, we have a Π_{1}^{1}, and hence Δ_{1}^{1}, function

X → ℕ
x ↦ n_{x}

assigning to each x some n_{x} such that V̂_{n_{x}} fulfills 4.1. Then we can let (m_{x}, k_{x}) be chosen in a Δ_{1}^{1} way so that

U_{x} = (D_{k_{x}})^{ΔV̂_{mx}}

along with V_{x} = V̂_{n_{x}} completes the construction of 2.1. We can then finish by letting θ(x) be the characteristic function of the following set of natural numbers:

{2^{k}3^{n} : V_{x} · x ∩ U_{x} ∩ (D_{k})^{ΔV̂_{n}} ≠ 0};

in this manner we have assigned to x in a Δ_{1}^{1} way an element θ(x) such that

θ(x_{1}) = θ(x_{2})

if and only if

\overline{U_{x_{1}} ∩ V_{x_{1}} · x} = \overline{U_{x_{2}} ∩ V_{x_{2}} · x_{2}}.

By the proof of 2.1, this function satisfies Kechris’ criterion.

References

[1] H. Becker and A. S. Kechris, The descriptive set theory of Polish group actions, London Mathematical Society Lecture Note Series, 232, Cambridge University Press, Cambridge, 1996.

[2] C. C. Chang and H. J. Keisler, Model theory, second edition, North-Holland, Amsterdam, 1977.

[3] S. Gao, Some dichotomy theorems for isomorphism relations of countable models, Journal of Symbolic Logic, vol. 66 (2001), pp. 902–922.

[4] A. Gregorczyk, A. Mostowski, C. Ryll-Nardzewski, Definability of sets of models of axiomatic theories, Bulletin of the Polish Academy of Sciences, (series Mathematics, Astronomy, Physics), vol. 9 (1961), pp. 163–7.

[5] L. A. Harrington, D. Marker, and S. Shelah, Borel orderings, Transactions of the American Mathematical Society, vol. 310 (1988), pp. 293–302.

[6] G. Hjorth, Classification and orbit equivalence relations, American Mathematical Society, Rhode Island, 2000.

[7] G. Hjorth, Actions of the classical Banach spaces, The Journal of Symbolic Logic, vol. 65 (2000), pp. 392–420.

[8] G. Hjorth, A dichotomy theorem for turbulence, The Journal of Symbolic Logic, vol. 67 (2002), pp. 1520–1540.

[9] G. Hjorth, The isomorphism relation for countable torsion free abelian groups, Fundamenta Mathematicae, vol. 175 (2002), pp. 241–257.

[10] G. Hjorth and A. S. Kechris, Borel equivalence relations and classifications of countable models, The Annals of Pure and Applied Logic, vol. 82 (1996), pp. 221–272.

[11] G. Hjorth, A. S. Kechris, and A. Louveau, Borel equivalence relations induced by actions of the symmetric group, The Annals of Pure and Applied Logic, vol. 92 (1998), pp. 63–112

[12] A. S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, New York, 1995.

[13] A. S. Kechris, Countable sections for locally compact group actions, Ergodic Theory and Dynamical Systems, vol. 12 (1992), pp. 283–295.

[14] E. G. Lopez-Escobar, An interpolation theorem for denumerably long formulas, Fundamenta Mathematicae, vol. 57 (1965), pp. 253–272.

[15] S. Thomas, The classification problem for torsion-free abelian groups of finite rank, Journal of the American Mathematical Society, vol. 16 (2003), pp. 233-258.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555