CONJUGACY EQUIVALENCE RELATION ON SUBGROUPS

ALESSANDRO ANDRETTA, RICCARDO CAMERLO, AND GREG HJORTH

Abstract. If G is a countable group containing a copy of F_{2} then the conjugacy equivalence relation on subgroups of G attains the maximal possible complexity.

1. Introduction

This paper is primarily directed towards the study of subgroups of countable groups and the complexity of the conjugacy equivalence relation, E_{c}(G, Sgr(G)), on the space of these subgroups Sgr(G).

It had previously been shown that:

Lemma 1.1 (Stuck, Zimmer, see [8] 3.9). The conjugacy equivalence relation on subgroups of F_{2}, the free group on two generators, is not smooth.

We give the precise definition of smooth below in §2. Roughly speaking 1.1 states that there is no Borel function assigning elements of ℝ as complete invariants to the equivalence classes of E_{c}(F_{2}, Sgr(F_{2})).

This was recently strengthened in [9]:

Theorem 1.2 (Thomas, Veličković). E_{c}(F_{2}, Sgr(F_{2})) is a universal countable Borel equivalence relation.

Again the exact definitions can be found in §2. In essence 1.2 states that E_{c}(F_{2}, Sgr(F_{2})) attains the maximal possible complexity. In [3] Su Gao showed E_{c}(G, Sgr(G)) to be universal for a variety of finitely generated groups, including F_{2}, all of which contained F_{2} as a subgroup.

In this present paper we obtain a completely general result:

Theorem 1.3. For G a countable group containing F_{2} as a subgroup, E_{c}(G, Sgr(G)) is universal.

For instance Theorem 1.3 implies that the conjugacy equivalence relation on SL_{2}(ℤ) is universal since, as noted in [10], SL_{2}(ℤ) contains a copy of F_{2}. The universality of this specific conjugacy relation does not seem to follow from the arguments of Gao or Thomas and Veličković.

The proof of 1.3 came about as a result of thinking about the following still open and seemingly difficult problem.

1991 Mathematics Subject Classification. 03E15,20E05,20F05.

Key words and phrases. Countable Borel equivalence relations, Subgroup conjugacy.

The first author would like to thank the UCLA Math department for hospitality and support during the 1998–1999 academic year, when the results were obtained. The third author gratefully acknowledges support of grant DMS-9970403 and a generous fellowship from the Sloan foundation.

Question 1.4. Must any countable Borel equivalence relation including a universal countable Borel equivalence relation itself be universal?

It is easily seen that E_{c}(F_{2}, Sgr(F_{2})) includes a universal countable Borel equivalence relation, and hence so too does E_{c}(G, Sgr(G)) whenever F_{2} ⊆ G. The proof of 1.3 below demonstrates universality of E_{c}(G, Sgr(G)) by going to a subspace of Sgr(G) on which the universal equivalence relation included in E_{c}(G, Sgr(G)) exactly equals E_{c}(G, Sgr(G)); in other words, we restrict to a subspace on which the extra parts of E_{c}(G, Sgr(G)) are killed off and only the universal countable equivalence relation remains. In some sense the proof can be thought of as a kind of trial effort to affirmatively answer the above open question, but using all the extra information given by the specific context.

The proof of 1.3 also uses the following improvement of a theorem by Dougherty and Kechris:

Theorem 1.5. For G a countable group of permutations including the recursive permutations, ≅_{G}^{5} is universal.

Here ≅_{G}^{5} is the equivalence relation on 5^{ℕ} arising from the natural shift action on this space.

Previously it was shown:

Theorem 1.6 (Dougherty, Kechris, see [2]). For G a countable group of permutations including the recursive permutations, ≅_{G}^{ℕ} is universal.

These results came as an attempt to settle the following open problem.

Question 1.7. Is ≡_{T}, the relation of Turing equivalence on ℕ^{ℕ} (or equivalently 2^{ℕ}), universal among countable Borel equivalence relations?

An affirmative answer to 1.4 together with 1.6 would yield an affirmative answer to 1.7 which in turn would refute in a very strong way a conjecture of Martin’s in recursion theory—see the Appendix in [5].

2. Notation and definitions

We give a stick figure sketch of the most of the definitions and notation. The reader is referred to [7] for basic facts on descriptive set theory, while more extensive introductions to the theory of Borel equivalence relations can be found in [1] or [4].

A topological space X is said to be Polish if it is separable and completely metrizable. For example k^{ℕ} and ℕ^{ℕ} are both Polish with the topology of pointwise convergence. (Here and below we adopt the usual convention of identifying an integer k with the set of all of its predecessors {0, …, k − 1} and A^{B} with the set of all functions from B to A.) We say that B ⊆ X is Borel if it appears in the smallest σ-algebra containing the open sets. A function f : X → Y between Polish spaces is Borel if f^{−1}[U] is Borel for any open U ⊆ Y.

An equivalence relation E on X is Borel if is Borel as a subset of X × X. For E and F Borel equivalence relations on Polish spaces X and Y we say that E is Borel reducible to F, written E ≤_{B} F, if there is a Borel function f : X → Y which embeds E in F, in the sense that for all x_{1}, x_{2} ∈ X

x_{1} E x_{2} ⟺ f(x_{1}) F f(x_{2}).

We say that E on X is smooth if E ≤_{B} Δ(ℝ), the equality equivalence relation on ℝ. We say that E on X is countable if all of its equivalence classes are countable. A countable Borel equivalence relation E is said to be universal if for any other countable Borel equivalence relation F we have F ≤_{B} E.

It is a somewhat non-trivial fact that there is a universal countable Borel equivalence relation. We work towards giving an example due to Dougherty, Jackson, and Kechris.

Let G be an infinite countable group. Then G acts on 2^{G} by left shift, namely we define G × 2^{G} → 2^{G}, (g, x) ↦ g.x, to be

∀h ∈ G ((g.x)(h) = x(g^{−1}h)) .

We then denote the resulting orbit equivalence relation on 2^{G} by E(G, 2). Note that 2^{G} is Polish, being homeomorphic to 2^{ℕ}, and that E(G, 2) is countable Borel.

Theorem 2.1 (Dougherty, Jackson, Kechris, see [1]). E(F_{2}, 2) is universal.

For G a countable group, we let Sgr(G) be the collection of all subgroups of G. Under the natural identification of P(G) with 2^{G} we obtain that Sgr(G) is a closed subset of 2^{G}, and hence a Polish space in its own right. We then let G act on Sgr(G) by conjugation and define E_{c}(G, Sgr(G)) to be the resulting orbit equivalence relation. Thus for H_{1}, H_{2} ⊆ G we have

H_{1} E_{c}(G, Sgr(G)) H_{2} ⟺ ∃g ∈ G (gH_{1}g^{−1} = H_{2}) .

For X a set Sym(X) is the group of all permutations of X. Sym(ℕ) is usually denoted by S_{∞}. We let S_{∞} act on the right on k^{ℕ}, by k^{ℕ} × S_{∞} → k^{ℕ}, (x, g) ↦ x ∘ g. We then obtain for any subgroup G ⊆ S_{∞} the corresponding equivalence relation ≅_{G}^{k}

x ≅_{G}^{k} y ⟺ ∃g ∈ G (x ∘ g = y) .

Similarly we define ≅_{G}^{ℕ} on ℕ^{ℕ}.

3. Groups of permutations

We now prove Theorem 1.5. In fact we will prove a slightly stronger assertion.

Theorem 3.1. There is a countable group of recursive permutations G_{0} ⊆ S_{∞} such that G_{0} ≅ F_{2}, and for every countable group G with G_{0} ⊆ G ⊆ S_{∞}, the equivalence relation ≅_{G}^{5} on 5^{ℕ} is universal among countable Borel equivalence relations. In particular this holds when G = Rec, the group of recursive bijections.

Proof. Rather than working with subgroups of S_{∞} we will look at subgroups G of Sym(M), where M = F_{2} × ℕ^{2}. The set M is best visualized as F_{2}-many copies of the square ℕ × ℕ

\underbrace{⋯  ℕ × ℕ  ⋯  ℕ × ℕ  ⋯  ℕ × ℕ  ⋯}_{F_{2}}

A generic element of M is denoted by (w, n, k) with n ranging on the x-axis and k ranging on the y-axis of the w-th square. Thus a set of the form {(w, n, k) ∈ M | k_{0} ≤ k ≤ k_{1}} is called a horizontal strip of M.

For every w ∈ F_{2} let ŵ ∈ Sym(M) be defined by

ŵ(v, n, k) = (vw, n, k)

and let G_{0} = {ŵ | w ∈ F_{2}}. (Note that the map F_{2} → G_{0}, w ↦ ŵ^{−1}, is an isomorphism.) An element of the form ŵ acts by right multiplication on the F_{2}-coordinate, leaving the other two coordinates unchanged. Let G be a countable group with G_{0} ⊆ G ⊆ Sym(M). If G were equal to G_{0} then we would be done by 2.1 and E(G_{0}, 2) ≤_{B} ≅_{G_{0}}^{5}. So we try to analyze how different from an element of G_{0} can an element of G be. Fix an enumeration (g_{i})_{i>0} of G. (For notational reasons it is more convenient to avoid 0 as an index here.) An element g ∈ G is called a quasi-shift above ℓ iff

∀(w, n, k) ∈ M[k > ℓ ⟹

g(w, n, k) = (φ(w, n, k), n, k) & g^{−1}(w, n, k) = (ψ(w, n, k), n, k)]

for some functions φ, ψ : M → F_{2}. In other words, a quasi-shift respects pointwise the second and third coordinates of M. If the functions φ, ψ above depend on F_{2} only, i.e., g(w, n, k) = (φ(w), n, k) and g^{−1}(w, n, k) = (ψ(w), n, k), then g is a shift. Elements of G_{0} are particular types of shifts.

An increasing sequence of integers (ℓ_{i})_{i∈ℕ} is defined inductively.

Set ℓ_{0} = −1 and suppose ℓ_{i−1} has been defined for some i ≥ 1. We now distinguish two cases:

• g_{i} is not a quasi-shift above ℓ_{i−1}, i.e., there is a w_{0} ∈ F_{2} and there are (n_{0}, k_{0}) ∈ ℕ^{2} such that g_{i}(w_{0}, n_{0}, k_{0}) = (w′_{0}, n′_{0}, k′_{0}) and (n_{0}, k_{0}) ≠ (n′_{0}, k′_{0}), with k_{0} > ℓ_{i−1} or k′_{0} > ℓ_{i−1}. Then we have the following possibilities:

(i) g_{i}(w_{0}, n_{0}, k_{0}) = (w′_{0}, n′_{0}, k′_{0}), for some (w_{0}, n_{0}, k_{0}), (w′_{0}, n′_{0}, k′_{0}) ∈ M with k_{0} > ℓ_{i−1} and k_{0} > k′_{0};

(ii) g_{i}^{−1}(w_{0}, n_{0}, k_{0}) = (w′_{0}, n′_{0}, k′_{0}), for some (w_{0}, n_{0}, k_{0}), (w′_{0}, n′_{0}, k′_{0}) ∈ M with k_{0} > ℓ_{i−1}

and k_{0} > k′_{0}, and (i) fails; (iii) g_{i}(w_{0}, n_{0}, k_{0}) = (w′_{0}, n′_{0}, k_{0}), for some (w_{0}, n_{0}, k_{0}), (w′_{0}, n′_{0}, k_{0}) ∈ M with k_{0} > ℓ_{i−1} and

n_{0} ≠ n′_{0}, and both (i) and (ii) fail. Then set ℓ_{i} = k_{0}, for the least possible k_{0} as above.

• Otherwise, that is: g_{i} is a quasi-shift above ℓ_{i−1}. Then set ℓ_{i} = ℓ_{i−1} + 1.

Suppose g_{i} is a quasi-shift above ℓ_{i−1}. Then g_{i} shuffles the ℓ_{i}-th rows among the various squares, and, in particular, ∀n ∈ ℕ ∃w ∈ F_{2} (g_{i}(1_{F_{2}}, n, ℓ_{i}) = (w, n, ℓ_{i})).

We say that g_{i} is good if there is an increasing sequence of natural numbers (n_{m})_{m} and a fixed w_{∞} ∈ F_{2} such that

∀m ∈ ℕ (g_{i}(1_{F_{2}}, n_{m}, ℓ_{i}) = (w_{∞}, n_{m}, ℓ_{i})) .

If g_{i} is not good then it is called bad. In this case we can find an increasing sequence of natural numbers (n_{m})_{m} and a sequence of distinct (w_{m})_{m} in F_{2} such that

∀m ∈ ℕ (g_{i}(1_{F_{2}}, n_{m}, ℓ_{i}) = (w_{m}, n_{m}, ℓ_{i})) .

Let also z_{m+1} = w_{m+1}w_{m}^{−1} and define μ : 2^{F_{2}} → {1, 2, …, ∞}

μ(x) = \{ \begin{matrix}the least m ≥ 1 such that z_{m}.x ≠ x , \\ ∞ if ∀m ≥ 1 (z_{m}.x = x) . \end{matrix}

We record a few simple facts about μ whose proof is left to the reader.

Claim 3.2. ∀j < μ(w_{0}.x) (w_{j}.x = w_{0}.x), and if μ(w_{0}.x) < ∞ then μ(w_{μ(w_{0}.x)}.x) ≤ μ(w_{0}.x).

Obviously all of the above (n_{m}’s, w_{m}’s, z_{m}’s, μ) depend on i so we should really write n_{m}^{(i)}, w_{m}^{(i)}, etc.

We shall define a Borel map 2^{F_{2}} → 5^{M}, x ↦ x^{∗}, witnessing the reduction E(F_{2}, 2) ≤_{B} ≅_{G}^{5}. The map x^{∗} : M → 5 assigns to each element of M a colour, i.e., an integer between 0 and 4. The colouring of x^{∗} will encode x in a sufficiently “rigid” way so that for all x, y ∈ 2^{F_{2}}

1. ∀w ∈ F_{2} (w.x = y ⟹ x^{∗} ∘ ŵ = y^{∗}), hence x E(F_{2}, 2) y ⟹ x^{∗} ≅_{G}^{5} y^{∗},

2. ∀g ∈ G ∃w ∈ F_{2} (x^{∗} ∘ g = y^{∗} ⟹ w.x = y), and hence x^{∗} ≅_{G}^{5} y^{∗} ⟹ x E(F_{2}, 2) y. The function x^{∗} : M → 5 will be defined on the horizontal strips

{(w, n, k) ∈ M | ℓ_{i−1} < k ≤ ℓ_{i}}

by induction on i ≥ 1 in such a way that if g_{i} is not a quasi shift then the value of x^{∗} is independent of x, i.e.,

g_{i} not a quasi shift ⟹

∀x, y ∈ 2^{F_{2}} ∀(w, n, k) (ℓ_{i−1} < k ≤ ℓ_{i} ⟹ x^{∗}(w, n, k) = y^{∗}(w, n, k)) .

The horizontal strip {(w, n, k) ∈ M | ℓ_{i−1} < k ≤ ℓ_{i}} is used to “kill” the g_{i}’s which are not quasi-shifts, i.e., it is used to make sure that ∀x, y ∈ 2^{F_{2}} (x^{∗} ∘ g_{i} ≠ y^{∗}). If instead g_{i} is a quasi-shift, then ℓ_{i−1} + 1 = ℓ_{i} and the set {(w, n, ℓ_{i}) | n ∈ ℕ} is used either to kill g_{i} or else to encode w.x. Also the map x ↦ {(w, n, k) | x^{∗}(w, n, k) = 4} will be constant, that is, whether or not x^{∗}(w, n, k) = 4 will not depend on x but on (w, n, k) only.

Now the details. We will consider two cases depending on whether or not g_{i} is a quasishift.

g_{i} is a quasi-shift above ℓ_{i−1}.

Then ℓ_{i−1} + 1 = ℓ_{i} and we only have to define x^{∗}(w, n, ℓ_{i}) for w ∈ F_{2} and n ∈ ℕ. Let (n_{m})_{m} be as in the definition of good/bad quasi-shift. Fix an enumeration without repetitions (u_{m})_{m} of F_{2}.

(0) For n ∉ {n_{m} | m ∈ ℕ} set x^{∗}(w, n, ℓ_{i}) = 0.

(1) If g_{i} is good then set for every w ∈ F_{2} and m ∈ ℕ

x^{∗}(w, n_{m}, ℓ_{i}) = (w.x)(u_{m}) ∈ {0, 1} .

In other words, we are encoding w.x on the sequence (n_{m})_{m} in the w-th square. Therefore ∀(w, m) ∈ F_{2} × ℕ

x^{∗}(w, n_{m}, ℓ_{i}) = (w.x)(u_{m})
= (w.x)^{∗}(1_{F_{2}}, n_{m}, ℓ_{i})

and thus ∀w ∈ F_{2} ∀n ∈ ℕ (x^{∗}(w, n, ℓ_{i}) = (w.x)^{∗}(1_{F_{2}}, n, ℓ_{i})) by (0).

(2) If g_{i} is bad and μ(w.x) = ∞ then set, for every m ∈ ℕ,

x^{∗}(w, n_{0}, ℓ_{i}) = 0 ,
x^{∗}(w, n_{1}, ℓ_{i}) = 3 ,
x^{∗}(w, n_{m+2}, ℓ_{i}) = (w.x)(u_{m}) .

Also in this case w.x is encoded on (n_{m})_{m} in the w-th square, but a “flag” 03 is attached at the very beginning. Again it is easy to check that ∀w ∈ F_{2} ∀n ∈ ℕ (x^{∗}(w, n, ℓ_{i}) = (w.x)^{∗}(1_{F_{2}}, n, ℓ_{i})).

So we may assume g_{i} is bad and 0 < μ(w.x) < ∞. We will need the following result which is an immediate consequence of Proposition 4.6 of [6].

Lemma 3.3. Let T : X → X be a Borel transformation on a standard Borel space X. There are pairwise disjoint Borel sets X^{(0)}, X^{(1)}, X^{(2)} such that X^{(0)} ∪ X^{(1)} ∪ X^{(2)} = X and such that for all x ∈ X and j ∈ {0, 1, 2}

(x ≠ T (x) & x ∈ X^{(j)}) ⟹ T (x) ∉ X^{(j)} .

That is to say: if x is not a fixed point of T then x and T (x) belong to different pieces of the partition {X^{(0)}, X^{(1)}, X^{(2)}}.

For every m ∈ ℕ the map T_{m} : 2^{F_{2}} → 2^{F_{2}}, x ↦ z_{m}.x is a Borel transformation, where (z_{m})_{m} is as in the definition of bad quasi-shift. Let X_{m}^{(0)}, X_{m}^{(1)}, and X_{m}^{(2)} be as in the lemma, with T = T_{m}. Then set

J_{m}(x) = the unique j ∈ {0, 1, 2} such that x ∈ X_{m}^{(j)} .

(Note that the definition of J_{m} depends on z_{m} and hence on the index i.)

(3) If g_{i} is bad and 0 < μ(w.x) < ∞ then

x^{∗}(w, n_{m}, ℓ_{i}) = \begin{cases}3 & if m < μ(w.x) − 1, \\ J_{μ(w.x)}(w.x) & if m = μ(w.x) − 1 or m = μ(w.x), \\ 3 & if m > μ(w.x). \end{cases}

In this case x^{∗} is not encoding w.x on {(w, n_{m}, ℓ_{i}) | m ∈ ℕ}: the particular definition of x^{∗}(w, n_{m}, ℓ_{i}) will be used to show that x^{∗} ∘ g_{i} ≠ y^{∗}, for any y ∈ 2^{F_{2}}.

We now want to check that the behaviour of x^{∗} on the set {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} determines whether we are in case (1), (2), or (3) above.

Claim 3.4. Let i ≥ 1 be such that g_{i} is a quasi-shift above ℓ_{i−1} and let x, y ∈ 2^{F_{2}} be such that ∀m (x^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}) = y^{∗}(1_{F_{2}}, n_{m}, ℓ_{i})).

Suppose the definition of x^{∗} on the set {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} is as in case

(1), (2), or (3),

then also the definition of y^{∗} on {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} is as in case

(1), (2), or (3),

respectively.

Moreover the sequence (x^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}))_{m} is of the form:

• an element of 2^{ℕ}, if x^{∗} is defined as in (1),

• 03 followed by an element of 2^{ℕ}, if x^{∗} is defined as in (2),

• (3, …, 3, n, n, 3, 3, …) starting with a possibly empty sequence of 3’s then two consecutive n’s with n ∈ {0, 1, 2}, at position μ(x) − 1 and μ(x), and then 3 from now on. This happens when x^{∗} is defined as in (3).

Proof. If x^{∗} on {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} is defined as in (1) then g_{i} must be good, hence also y^{∗} is defined as in (1).

For the other cases notice that if x^{∗}(1_{F_{2}}, n_{0}, ℓ_{i}) ∈ {1, 2, 3} then x^{∗} (and hence y^{∗}) is defined as in (3), while if x^{∗}(1_{F_{2}}, n_{0}, ℓ_{i}) = 0 then either x^{∗}(1_{F_{2}}, n_{1}, ℓ_{i}) = 0 and we are in case (3) with μ = 1 or else x^{∗}(1_{F_{2}}, n_{1}, ℓ_{i}) = 3 and we are in case (2).

Remark 3.5. The only reason for using the flag 03 before the sequence coding w.x in (2) is to be able to distinguish, assuming g_{i} is bad, whether (x^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}))_{m} is defined as in (2) or (3) only by looking at its first 2 elements. Had we been less stingy with the number of colours and used, say, 5 and 6 instead of 0 and 1 in (2) then we could have avoided using the flag 03.

We now consider the other case, namely

g_{i} is not a quasi-shift above ℓ_{i−1}.

Let w_{0}, n_{0}, k_{0}, w′_{0}, n′_{0}, k′_{0} be as in cases (i)–(iii). We must define x^{∗}(w, n, k) for all w ∈ F_{2}, n ∈ ℕ and ℓ_{i−1} < k ≤ ℓ_{i}.

Suppose case (i) holds.

If k′_{0} ≤ ℓ_{i−1} then set

x^{∗}(w, n, k) = \begin{cases}0 & if x^{∗}(w′_{0}, n′_{0}, k′_{0}) = 4, \\ 4 & if x^{∗}(w′_{0}, n′_{0}, k′_{0}) ≤ 3. \end{cases}

(This is the only way for x^{∗} to achieve value 4.)

If ℓ_{i−1} < k′_{0} then set

x^{∗}(w, n, k) = \begin{cases}1 & if k = k′_{0}, \\ 0 & if k ≠ k′_{0}. \end{cases}

If case (ii) holds then proceed as in case (i).

y^{∗} = x^{∗} ∘ g_{i} [figure] [figure]

g_{i} is a ; quasi-shift

[figure] [figure]

g_{i} is not a quasi-shift

[figure]

g_{i} is good

[figure]

g_{i} is bad

[figure] [figure]

x^{∗} ∘ g_{i} is not in the range of the reduction: a contradiction!

y = w_{∞}.x μ(w_{0}.x) ≠ ∞

[figure]

μ(w_{0}.x) = ∞

[figure]

x^{∗} ∘ g_{i} is not in the range of the reduction: a contradiction!

y = w_{0}.x

Figure 1. Plan of the Proof of Theorem 3.1

If case (iii) holds then set

x^{∗}(w, n, k) = \begin{cases}1 & if n = n′_{0}. \\ 0 & if n ≠ n′_{0}, \end{cases}

This concludes the definition of x^{∗}.

We must check that x ↦ x^{∗} is indeed a reduction. As the value of x^{∗}(w, n, k) is independent of x and w, when ℓ_{i−1} < k ≤ ℓ_{i} and g_{i} is not a

quasi-shift, or else depends on w.x only (when g_{i} is a quasi-shift), then it is straightforward to check that

∀v ∈ F_{2} ∀(w, n, k) ∈ M ((v.x)^{∗}(w, n, k) = x^{∗} ∘ v̂(w, n, k)) .

We will now show that

∃i (y^{∗} = x^{∗} ∘ g_{i}) ⟹ ∃v ∈ F_{2} (y = v.x)

and hence x ↦ x^{∗} is a reduction. The reader may find useful to refer to Figure 1 while checking the details.

Suppose y^{∗} = x^{∗} ∘ g_{i}.

Claim 3.6. g_{i} is a quasi-shift above ℓ_{i−1}.

Proof. Deny. Let w_{0}, n_{0}, k_{0}, w′_{0}, n′_{0}, and k′_{0} be as in (i)–(iii) above. Notice that their choice as well as the decision as to which of (i)–(iii) we fall into as well as the definition of x^{∗}(w, n, k) for ℓ_{i−1} < k ≤ k_{0} are independent of x. In particular x^{∗} and y^{∗} agree on (w_{0}, n_{0}, k_{0}). If we are in case (i) then

y^{∗}(w_{0}, n_{0}, k_{0}) = x^{∗}(w′_{0}, n′_{0}, k′_{0}) ≠ x^{∗}(w_{0}, n_{0}, k_{0}) ,

and if we are in case (ii) then

x^{∗}(w_{0}, n_{0}, k_{0}) = y^{∗}(w′_{0}, n′_{0}, k′_{0}) ≠ y^{∗}(w_{0}, n_{0}, k_{0}) ,

in both cases reaching a contradiction. If we are in case (iii) then

0 = y^{∗}(w_{0}, n_{0}, ℓ_{i}) = x^{∗}(w′_{0}, n′_{0}, ℓ_{i}) = 1

a contradiction again.

Therefore we may assume that

g_{i} is a quasi-shift.

Again we take cases. Suppose w_{∞} ∈ F_{2} and (n_{m})_{m} ⊆ ℕ witness that g_{i} is good. Then

y^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}) = x^{∗} ∘ g_{i}(1_{F_{2}}, n_{m}, ℓ_{i})
= x^{∗}(w_{∞}, n_{m}, ℓ_{i})
= (w_{∞}.x)^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}) .

As g_{i} is good then both (w_{∞}.x)^{∗} and y^{∗} are defined on {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} as in (1), hence ∀m (y(u_{m}) = (w_{∞}.x)(u_{m})). Therefore

g_{i} is good ⟹ y = w_{∞}.x.

So we may assume that g_{i} is bad and let (w_{m})_{m} ⊆ F_{2} and (n_{m})_{m} ⊆ ℕ witness this so that

∀m ∈ ℕ (y^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}) = x^{∗} ∘ g_{i}(1_{F_{2}}, n_{m}, ℓ_{i}) = x^{∗}(w_{m}, n_{m}, ℓ_{i})) .

Suppose first μ(w_{0}.x) = ∞. Then by Claim 3.2 ∀m((w_{m}.x)^{∗} = (w_{0}.x)^{∗}) hence

x^{∗}(w_{m}, n_{m}, ℓ_{i}) = (w_{m}.x)^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}) = (w_{0}.x)^{∗}(1_{F_{2}}, n_{m}, ℓ_{i}) .

As (w_{0}.x)^{∗} is defined on {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} as in (2) then y^{∗} is defined on {(1_{F_{2}}, n_{m}, ℓ_{i}) | m ∈ ℕ} as in (2) and hence ∀m (y(u_{m}) = w_{0}.x(u_{m})). Therefore

μ(w_{0}.x) = ∞ ⟹ y = w_{0}.x.

Suppose now 1 ≤ μ(w_{0}.x) = m < ∞. Then by Claim 3.2

∀j < m (μ(w_{j}.x) = m & J_{m}(w_{j}.x) = J_{m}(w_{0}.x)) and μ(w_{m}.x) ≤ m .

Using (3), the first m elements of the sequence (x^{∗}∘g_{i}(1_{F_{2}}, n_{j}, ℓ_{i}))_{j} are (3, …, 3, J_{m}(w_{0}.x)). If m > 1 (so that the sequence starts with 3) or if J_{m}(w_{0}.x) ≠ 0 then by Claim 3.4 the next element must be

x^{∗}(w_{m}, n_{m}, ℓ_{i}) = J_{m}(w_{0}.x) ∈ {0, 1, 2} .

If m = 1 and J_{m}(w_{0}.x) = 0 then the sequence starts with 0 hence the next element can only be 0 or 3, i.e.,

x^{∗}(w_{m}, n_{m}, ℓ_{i}) ∈ {0, 3} .

In order to compute this value and eventually reach a contradiction we must consider two cases.

Suppose μ(w_{m}.x) = m. Since w_{0}.x = w_{m−1}.x and z_{m}.w_{0}.x = w_{m}.x are distinct, they belong to different X_{m}^{(j)}’s and therefore, using (3),

x^{∗}(w_{m}, n_{m}, ℓ_{i}) = J_{m}(w_{m}.x) ∉ {J_{m}(w_{0}.x), 3} ,

a contradiction.

Suppose 0 < μ(w_{m}.x) < m. Then m > 1 and by (3)

x^{∗}(w_{m}, n_{m}, ℓ_{i}) = 3 ≠ J_{m}(w_{0}.x) ,

a contradiction.

Therefore we have shown that

1 ≤ μ(w_{0}.x) < ∞ ⟹ x^{∗} ∘ g_{i} is not in the range of the reduction.

This concludes the proof.

Notice that for k ≥ 5 or k = ℕ and G as in the theorem, the inclusion map 5^{ℕ} ↪ k^{ℕ} witnesses ≅_{G}^{k} is universal. Focusing on Rec, the group of recursive permutations, one can show that

≅_{Rec}^{ℕ}↾ {x ∈ ℕ^{ℕ} | x : ℕ ↠ ℕ is onto}

is universal. To see this assign to each non-empty subset S ⊆ 5 = {0, …, 4} an integer ρ(S) > 0, and consider the map 5^{ℕ} → {x ∈ ℕ^{ℕ} | x : ℕ ↠ ℕ is onto}, x ↦ x^{∗}, defined as follows: on the even integers we copy x, i.e., ∀n (x^{∗}(2n) = x(n)) and on the odd integers we start with ρ(range(x))-many 5’s followed by the increasing enumeration of ℕ\(range(x)∪ {5}). It is easy to check that x^{∗} is indeed onto and that x ↦ x^{∗} is Borel. If x ∘ f = y for some recursive f then letting g(2n + 1) = 2n + 1 and g(2n) = 2f(n) we have that x^{∗} ∘ g = y^{∗}. Suppose instead x^{∗} ∘ f = y^{∗} for some recursive bijection f. Since the number of 5’s in x^{∗} and in x^{∗} ∘ f = y^{∗} are the same, then range(x) = range(y) hence f restricted to the even numbers must be a bijection. Letting h(n) = \frac{1}{2}f(2n) we see that x ∘ h = y. Therefore x ↦ x^{∗} is a reduction of ≅_{Rec}^{5} to ≅_{Rec}^{ℕ}↾ {x ∈ ℕ^{ℕ} | x : ℕ ↠ ℕ is onto}.

By extracting the salient features of Rec used above we get

Corollary 3.7. Let G_{0} ⊆ G ⊆ S_{∞} be as in the theorem. Suppose G has the following closure property:

- if f ∈ G then g ∈ G where g(2n + 1) = 2n + 1 and g(2n) = 2f(n),

- if f ∈ G and f is a bijection when restricted to the set of even numbers (i.e., ∀n ∃m (f(2m) = 2n) and ∀n ∃m (f(2n) = 2m)) then h ∈ G where h(n) = \frac{1}{2}f(2n).

Then ≅_{G}^{ℕ}↾ {x ∈ ℕ^{ℕ} | x : ℕ ↠ ℕ is onto} is universal.

Let L be a language consisting of one binary relation symbol and let X_{L} = 2^{ℕ^{2}} be the space of all L-structures with universe ℕ. Let Eq(k) ⊆ X_{L} be the set of all structures which are models for equivalence relations whose equivalence classes are of size at most k, that is x ∈ Eq(k) iff the relation E^{x} on ℕ defined by

nE^{x}m ⟺ x(n, m) = 1

is an equivalence relation on ℕ and ∀n ∈ ℕ (|[n]_{E^{x}}| ≤ k). For x, y ∈ X_{L} set x ≅_{G}^{L} y just in case the models ⟨ℕ, E^{x}⟩ and ⟨ℕ, E^{y}⟩ are isomorphic via a bijection in G.

For G ⊆ S_{∞} let ∼_{G} denote the conjugation relation on S_{∞} via elements in G

x ∼_{G} y ⟺ ∃g ∈ G (g^{−1} ∘ x ∘ g = y) .

Let also ∼_{G}^{k} = ∼_{G}↾ {x ∈ S_{∞} | x is a product of cycles of length ≤ k}.

A group G ⊆ S_{∞} is closed under pairing if there is a pairing function, i.e., a bijection j : ℕ^{2} → ℕ with inverses (j(n, m))_{0} = n and (j(n, m))_{1} = m such that:

For every g ∈ G the bijection h ∈ S_{∞} defined by

h(j(n, m)) = j(g(n), m)

is in G, and if

f(n) = (g(j(n, 0)))_{0}

is a bijection, then f is also in G. For example Rec is closed under pairing.

Proposition 3.8. Let G ⊆ S_{∞} be a countable group closed under pairing. Then

≅_{G}^{k} ⊑_{c} ≅_{G}^{L}↾ Eq(k + 1)

that is to say: the equivalence relation given by the right action of G on k^{ℕ} is continuously embeddable into the G-isomorphism relation between equivalence relations on ℕ with equivalence classes of size ≤ k + 1.

Similarly ≅_{G}^{k} continuously embeds into conjugacy on S_{∞} via elements of G restricted to products of cycles of size ≤ k + 1:

≅_{G}^{k} ⊑_{c} ∼_{G}^{k+1} .

In particular for all G_{0} ⊆ G ⊆ S_{∞} as in the theorem ≅_{G}^{L}↾ Eq(6) and ∼_{G}^{6} are both universal.

Proof. Let ϑ : k^{ℕ} → Eq(k + 1) be defined by

j(n, m)E^{ϑ(x)}j(n′, m′) ⟺ n = n′ & (m = m′ ∨ m, m′ ≤ x(n) + 1)

where j is the pairing function for G. (It is most convenient to visualize E^{ϑ(x)} as the equivalence relation on ℕ^{2} obtained by connecting on each vertical line {(n, m) | m ∈ ℕ} all the points ≤ x(n) + 1.) It is immediate to check that ϑ(x) ∈ Eq(k + 1) and that ϑ is continuous and injective.

Suppose first x, y ∈ k^{ℕ} and x ∘ g = y for some g ∈ G. Let h ∈ G be defined by h(j(n, m)) = j(g(n), m). Then

h(j(n, m))E^{ϑ(x)}h(j(n′, m′)) ⟺ j(g(n), m)E^{ϑ(x)}j(g(n′), m′)
⟺ j(n, m)E^{ϑ(y)}j(n′, m′)

that is ϑ(y) ≅_{G}^{L} ϑ(x) via h.

Conversely suppose ϑ(y) ≅_{G}^{L} ϑ(x) via some g ∈ G. Let f ∈ G be defined by f(n) = (g(j(n, 0)))_{0}. We must show that x ∘ f = y. Fix n ∈ ℕ. Since [j(n, 0)]_{E^{ϑ(y)}} has y(n) + 1many elements and g is an isomorphism between E^{ϑ(y)} and E^{ϑ(x)} then [g(j(n, 0))]_{E^{ϑ(x)}} has also y(n) + 1-many elements. In particular [g(j(n, 0))]_{E^{ϑ(x)}} is not a singleton. But g(j(n, 0)) = j(f(n), ℓ) for some ℓ, so [j(f(n), ℓ)]_{E^{ϑ(x)}} = [j(f(n), 0)]_{E^{ϑ(x)}} has x(f(n)) + 1many elements. Therefore y(n) = x(f(n)), which is what we had to prove.

For ∼_{G}^{k+1} we use essentially the same reduction: for x ∈ k^{ℕ} let φ(x) ∈ S_{∞} be defined by φ(x) = ∏_{n} c_{n}(x) where c_{n}(x) is the cycle

\xymatrix{j(n, 0) \ar@{|->}[r] & j(n, 1) \ar@{|->}[r] & ⋯ \ar@{|->}[r] & j(n, x(n) + 1) \ar@{|->}[lll]} .

It is immediate to check that x ≅_{G}^{k} y ⟺ φ(x) ∼_{G}^{k+1} φ(y).

Even if the theorem holds for k = 2 (as we conjecture) the proposition above does not yield any information about the universality of ≅_{G}^{L}↾ Eq(2). We can still though relate this equivalence relation to ∼_{G}.

For x ∈ Eq(2) let x^{∗} ∈ S_{∞} be defined by

x^{∗}(n) = \begin{cases}m & if [n]_{E^{x}} = \{n, m\} and n ≠ m, \\ n & if [n]_{E^{x}} = \{n\}. \end{cases}

Then x^{∗} ∈ I =^{def} {f ∈ S_{∞} | f ∘ f = id}, the set of all involutions, and the map Eq(2) → I, x ↦ x^{∗}, is clearly a Borel bijection. Moreover if G ⊆ S_{∞} is a subgroup, g ∈ G, and x, y ∈ Eq(2) then g : ⟨ℕ, E^{x}⟩ → ⟨ℕ, E^{y}⟩ is an isomorphism iff g ∘x^{∗} ∘g^{−1} = y^{∗}. Therefore we have proved

Proposition 3.9. Let G ⊆ S_{∞} be a subgroup. The logic action of G on Eq(2) is isomorphic to the conjugacy of G on elements of I. In particular

≅_{G}^{L}↾ Eq(2) ≅_{B} ∼_{G}↾ I .

4. Conjugacy of subgroups

We will now prove Theorem 1.3. The proof will use a combination of the techniques used in proving 3.1 together with a few facts about free groups.

Let F(X) be the free group on the set X ≠ ∅, let x ∈ X and let w ∈ F(X). Let x_{1}^{k_{1}} ⋯ x_{n}^{k_{n}} be the unique reduced word for w. Then we say that w starts with x_{1} and ends with x_{n}. Whenever we write “vw is a reduced word” we mean that both v and w are already written as reduced words, and for no x ∈ X, v ends with x and w starts with x. We say that x^{k} occurs in w, (k ∈ ℤ \ {0}) if w = v_{0}x^{k}v_{1} and v_{0}x^{k}v_{1} is a reduced word, i.e., v_{0} and v_{1} are reduced and neither v_{0} ends with x nor v_{1} begins with x. If x^{k} occurs in w then we say that x is a generator in w. It is easy to see that if x is a generator in w, then it is a generator in every w^{n}, for n ≠ 0. A word w is symmetric if it can be written in reduced form as w = v_{0}x^{k}v_{0}^{−1}; otherwise it is asymmetric.

Lemma 4.1. If w ∈ F(X) is asymmetric then there is a fixed bound M depending on w such that if x^{k} occurs in any w^{n} then |k| ≤ M, i.e.,

∃M > 0 ∀x ∈ X ∀k ∈ ℤ \ {0} ∀n (x^{k} occurs in w^{n} ⟹ |k| ≤ M) .

Proof. It is enough to show that for any x ∈ X which is a generator of w there is an M_{x} such that if x^{h} occurs in w^{n}, then |h| ≤ M_{x}, so that we can set

M = sup{M_{x} | x is a generator in w} .

Let x be a generator in w so that w = v_{0}x^{k}v_{1} is a reduced word and v_{1} ≠ v_{0}^{−1}. Then the reduced form of v_{1}v_{0} cannot start and end with x since otherwise either v_{1} would have to start with x or v_{0} would have to end with x, hence v_{0}x^{k}v_{1} would not be reduced. Consider the product

w^{n} = v_{0} x^{k} v_{1} · v_{0} x^{k} v_{1} ⋯ v_{0} x^{k} v_{1} .

After the reduction:

- if v_{1} · v_{0} in reduced form does not start or end with x, then the boxed occurrences of x^{k} remain unchanged, so let

M_{x} = max (|k|, sup{|h| | x^{h} occurs in v_{0}, or in v_{1}, or in v_{1}v_{0}}) ,

- if v_{1} · v_{0} in reduced form is ux^{h} or x^{h}u, then the first (respectively: the last) boxed occurrence of x^{k} remains unchanged, so let

M_{x} = max (|k|, |k + h|, sup{|j| | x^{j} occurs in v_{0}, or in v_{1}, or in u}) .

This completes the proof.

We now start proving theorem 1.3.

Proof. Since inside every free group on two generators there is a copy of the free group on three generators, pick a, b, c ∈ G independent elements so that ⟨a, b, c⟩ is a free group on 3 generators. Let F_{3} = ⟨a, b, c⟩ be this particular realization of the free group on 3 generators and let F_{2} = ⟨a, b⟩ ⊂ F_{3}. We want to construct copy of F_{ω}, the free group of rank ℵ_{0}, inside F_{3}. We need the following lemma.

Lemma 4.2. Let w_{1}, …, w_{n} ∈ F_{2} be distinct. Then

⟨w_{1}cw_{1}^{−1}, …, w_{n}cw_{n}^{−1}⟩

is a free group on n generators.

In particular if (w_{n})_{n} ⊆ F_{2} are all distinct then ⟨w_{1}cw_{1}^{−1}, w_{2}cw_{2}^{−1}, … ⟩ is a free group of rank ℵ_{0}.

Proof. Choose new letters σ_{1}, …, σ_{n}, and let ⟨σ_{1}, …, σ_{n}⟩ be the free group of rank n generated by them. It is enough to show that ker(φ) is null, where φ : ⟨σ_{1}, …, σ_{n}⟩ ↠ ⟨w_{1}cw_{1}^{−1}, …, w_{n}cw_{n}^{−1}⟩ is the epimorphism induced by the map σ_{i} ↦ w_{i}cw_{i}^{−1}. Let v = σ_{i_{1}}^{k_{1}}σ_{i_{2}}^{k_{2}} ⋯ σ_{i_{m}}^{k_{m}} be a reduced word of ⟨σ_{1}, …, σ_{n}⟩. If

φ(v) = w_{i_{1}}c^{k_{1}}w_{i_{1}}^{−1} · w_{i_{2}}c^{k_{2}}w_{i_{2}}^{−1} ⋯ w_{i_{m}}c^{k_{m}}w_{i_{m}}^{−1} = 1_{F_{2}}

and m > 1, then w_{i_{j}} = w_{i_{j+1}} for all 1 ≤ j < m, hence σ_{i_{j}} = σ_{i_{j+1}}. Therefore m = 1, v = σ_{i_{1}}^{k_{1}} and hence φ(v) = w_{i_{1}}c^{k_{1}}w_{i_{1}}^{−1} = 1_{F_{2}} implies k_{1} = 0. This contradicts the assumption that v is reduced.

Define also the free group on two generators F̃_{2} = ⟨a^{2}, b^{2}⟩ ⊂ F_{2}, and let w ↦ w̃ be the isomorphism F_{2} → F̃_{2} given by a ↦ a^{2} and b ↦ b^{2}. For any w ∈ F_{2} and n ∈ ℤ let

γ(w, n) = w̃^{−1}ba^{2n}ca^{−2n}b^{−1}w̃ ∈ F_{3} .

Let Γ = ⋃_{w∈F_{2}} Γ_{w} ⊂ F_{3}, where Γ_{w} = {γ(w, n) | n ∈ ℤ}. Suppose γ(w, n) = γ(z, m). Then

w̃^{−1}ba^{2n}ca^{−2n}b^{−1}w̃ = z̃^{−1}ba^{2m}ca^{−2m}b^{−1}z̃.

As there is only one occurrence of c in both sides of the equation then

w̃^{−1}ba^{2n} = z̃^{−1}ba^{2m} .

As w̃, z̃ ∈ F̃_{2} then it is easy to see that w = z and n = m. Therefore

∀w, z ∈ F_{2} (w ≠ z ⟹ Γ_{z} ∩ Γ_{w} = ∅) .

Since γ(w, n) = (w̃^{−1}ba^{2n})c(w̃^{−1}ba^{2n})^{−1} and w̃^{−1}ba^{2n} ∈ F_{2}, then 4.2 implies that Γ is a countable set of independent elements and

F_{ω} = ⟨Γ⟩ ⊂ F_{3} ⊆ G

is a free group on ℵ_{0}-many generators. We now concentrate on subgroups of F_{ω} and from now on words will mean words built from elements in Γ. Notice that in our set-up F_{2} ⊈ F_{ω}.

The plan is to associate, in a Borel way, to each x ∈ 2^{F_{2}} a group H(x) ⊆ F_{ω} such that H(x) ≅ F_{ω} and

∀w ∈ F_{2} ∀x ∈ 2^{F_{2}} (H(w.x) = w̃H(x)w̃^{−1})
∀g ∈ G ∀x, y ∈ 2^{F_{2}} (H(y) = gH(x)g^{−1} ⟹ ∃w ∈ F_{2}(w.x = y)) .

This implies that the shift action of F_{2} on 2^{F_{2}} is reducible to E_{c}(G, Sgr(G)), proving the universality of the latter.

The group H(x) will be given via an infinite set G(x) of generators so that

(1) G(x) is an independent set of elements of F_{ω} and ⟨G(x)⟩ = H(x) ≅ F_{ω}.

In order to define the G(x)’s we need to re-arrange the enumeration of Γ a bit: fix a bijection j : ℕ^{2} → ℤ and set

α(w, n, m) = γ(w, j(n, m)) .

The third component of the indexing gives the level of the elements of Γ, so we say that α(w, n, m) is of level m. Fix for every i > 0 an infinite set S_{i} ⊆ ℙ = the set of all primes, such that i ≠ j ⟹ S_{i} ∩ S_{j} = ∅. As in the proof of 3.1 an increasing sequence of integers (ℓ_{i})_{i∈ℕ} with ℓ_{0} = −1 will be defined inductively. At stage i the only elements added to G(x) will be of the form γ^{p}, where γ ∈ Γ is of level between ℓ_{i−1} and ℓ_{i} and p is some unique element of S_{i}; moreover some such element should be added at this stage:

(2) \begin{matrix}∀z ∈ G(x) ∃α(w, n, m) ∈ Γ ∃p (α(w, n, m)^{p} = z & (ℓ_{i−1} < m ≤ ℓ_{i} ⟹ p ∈ S_{i})) \\ & ∀γ ∈ Γ ∀p, q ∈ ℙ(γ^{p}, γ^{q} ∈ G(x) ⟹ p = q) . \end{matrix}

(3) ∃α(w, n, m) ∈ Γ ∃p ∈ S_{i} (ℓ_{i−1} < m ≤ ℓ_{i} & α(w, n, m)^{p} ∈ G(x)).

(4) ∀w ∈ F_{2} (w̃G(x)w̃^{−1} = G(w.x)).

(5) If w ∈ H(x) and α(w, n, m)^{k} occurs in w and ℓ_{i−1} < m ≤ ℓ_{i} then

∃p ∈ S_{i} (p|k & α(w, n, m)^{p} ∈ G(x)) .

In particular Γ ∩ G(x) = ∅. By (2) the prime p is unique.

(6) If vw is a reduced word then vw ∈ H(x) ⟹ v, w ∈ H(x).

Notice that Properties (2) and (3) imply Properties (1) and (5), Property (6) follows from Property (5), and as z̃^{−1}γ(w, n)^{k}z̃ = γ(wz, n)^{k} for any z, w ∈ F_{2} and n, k ∈ ℤ, then Property (4) will hold.

We now start the construction.

In analogy with the proof of 3.1, say that an element g ∈ G is a quasi-shift above ℓ if

∀w, n(g^{−1} · α(w, n, ℓ + 1) · g ∈ F_{ω} & every generator from Γ in g^{−1} · α(w, n, ℓ + 1) · g is either of the form α(z, m, k) with k ≤ ℓ or else of the form α(z, n, ℓ + 1)

& ∃z α(z, n, ℓ + 1) is a generator in g^{−1} · α(w, n, ℓ + 1) · g) .

Fix an enumeration (g_{i})_{i≥1} of G.

Set ℓ_{0} = −1 and suppose ℓ_{i−1} has been defined for some i ≥ 1. We now distinguish two cases:

• g_{i} is not a quasi-shift above ℓ_{i−1}. Then letting k_{0} = ℓ_{i−1} + 1, we have the following possibilities:

(i) ∃w_{0}, n_{0} (g_{i}^{−1} · α(w_{0}, n_{0}, k_{0}) · g_{i} ∉ F_{ω}). (ii) Case (i) fails and

∃w_{0}, n_{0}, w′_{0}, n′_{0}, k′_{0}(k′_{0} > k_{0} & α(w′_{0}, n′_{0}, k′_{0}) is a generator in g_{i}^{−1} · α(w_{0}, n_{0}, k_{0}) · g_{i}) .

(iii) Cases (i) and (ii) fail and

∃w_{0}, n_{0}, w′_{0}, n′_{0}(n_{0} ≠ n′_{0} & α(w′_{0}, n′_{0}, k_{0}) is a generator in g_{i}^{−1} · α(w_{0}, n_{0}, k_{0}) · g_{i}) .

(iv) Cases (i), (ii), and (iii) fail and

∃w_{0}, n_{0} ∀w′_{0}, n′_{0}, k′_{0}(α(w′_{0}, n′_{0}, k′_{0}) is a generator in g_{i}^{−1} · α(w_{0}, n_{0}, k_{0}) · g_{i} ⟹ k′_{0} < k_{0}) .

Then set ℓ_{i} = max(k_{0}, k′_{0}). (Notice that if g_{i} is not a quasi-shift above ℓ_{i−1} because of (iv) then all of the generators of g_{i}^{−1} · α(w_{0}, n_{0}, k_{0}) · g_{i} are of level < k_{0}.)

• Otherwise, that is: g_{i} is a quasi-shift above ℓ_{i−1}. In this case set ℓ_{i} = ℓ_{i−1} + 1.

Suppose g_{i} is a quasi-shift above ℓ_{i−1}. We say that g_{i} is good if there is an increasing sequence of natural numbers (n_{m})_{m} and a w_{∞} ∈ F_{2} such that

α(w_{∞}, n_{m}, ℓ_{i}) is a generator in g_{i}^{−1} · α(1_{F_{2}}, n_{m}, ℓ_{i}) · g_{i} .

If g_{i} is not good then it is called bad. In this case there is an increasing sequence of natural numbers (n_{m})_{m} and a sequence of distinct (w_{m})_{m} in F_{2} such that

∀m ∈ ℕ (α(w_{m}, n_{m}, ℓ_{i}) is a generator in g_{i}^{−1} · α(1_{F_{2}}, n_{m}, ℓ_{i}) · g_{i}) .

Let also (z_{m})_{m≥1}, μ and J_{m} be defined as in the proof of 3.1. Finally we define the map x ↦ G(x), and hence the reduction H : 2^{F_{2}} → Sgr(G),

x ↦ H(x), so that Properties (1)–(6) hold.

g_{i} is not a quasi-shift above ℓ_{i−1}. Let w_{0}, n_{0}, k_{0}, w′_{0}, n′_{0}, k′_{0} be as in cases (i)–(iv).

Suppose case (i) holds. Then ℓ_{i} = k_{0}. Let r be the least positive integer such that g_{i}^{−1}·α(w_{0}, n_{0}, k_{0})^{r} ·g_{i} ∈ F_{ω}, if such integer exists, or r = 0 otherwise. Let p = min(S_{i}\{r}) be the least element of S_{i} different from r. We now require in our construction that

∀x ∈ 2^{F_{2}} ∀w ∈ F_{2} (α(w, n_{0}, ℓ_{i})^{p} ∈ G(x)) .

Suppose case (ii) holds. Then k_{0} = ℓ_{i−1} + 1 < ℓ_{i}. Let p = min(S_{i}) and set

∀x ∈ 2^{F_{2}} ∀w ∈ F_{2} (α(w, n_{0}, k_{0})^{p} ∈ G(x)) .

Suppose case (iii) or (iv) holds. Let p = min(S_{i}) and set

∀x ∈ 2^{F_{2}} ∀w ∈ F_{2} (α(w, n_{0}, ℓ_{i})^{p} ∈ G(x)) .

For k ∈ (ℓ_{i−1}, ℓ_{i}] and n ∈ ℕ, p ∈ ℙ place α(w, n, k)^{p} in G(x) only if required by the cases above.

We now consider the other case, namely

g_{i} is a quasi-shift above ℓ_{i−1}. There are two possibilities.

• For some α(w_{0}, n_{0}, ℓ_{i}) ∈ Γ, the reduced word v obtained from g_{i}^{−1} · α(w_{0}, n_{0}, ℓ_{i}) · g_{i} is either asymmetric or else it is symmetric of the form v_{1} · α(w′_{0}, n′_{0}, k)^{m} · v_{1}^{−1} with k < ℓ_{i} and m ≠ 0. In either case, by Lemma 4.1 or by inspection, there is M such that

∀r (α(z, n_{0}, ℓ_{i})^{k} occurs in v^{r} ⟹ |k| ≤ M) .

When this happens g_{i} is said to be bounded. Let p be the least element in S_{i} larger than M and set

∀x ∈ 2^{F_{2}} ∀w ∈ F_{2} (α(w, n_{0}, ℓ_{i})^{p} ∈ G(x)) .

• Otherwise ∀w ∈ F_{2} ∀n ∈ ℕ ∃z ∈ F_{2} ∃u ∈ F_{ω} such that

g_{i}^{−1} · α(w, n, ℓ_{i}) · g_{i} = u · α(z, n, ℓ_{i})^{r(w,n)} · u^{−1}

where r(w, n) ∈ ℤ \ {0}. In this case g_{i} is said to be unbounded.

Case 1: ∃w_{0}, n_{0} (|r(w_{0}, n_{0})| > 1), that is, for some w_{0}, n_{0}, z, u

g_{i}^{−1} · α(w_{0}, n_{0}, ℓ_{i}) · g_{i} = u · α(z, n_{0}, ℓ_{i})^{r} · u^{−1}

with r = r(w_{0}, n_{0}) and |r| > 1. Then let p = min(S_{i}) and set

∀x ∈ 2^{F_{2}} ∀w ∈ F_{2} (α(w, n_{0}, ℓ_{i})^{p} ∈ G(x)) .

Case 2: ∀w ∈ F_{2} ∀n ∈ ℕ (|r(w, n)| = 1), that is

∀w ∈ F_{2} ∀n ∈ ℕ ∃z ∈ F_{2} ∃u ∈ F_{ω} (g_{i}^{−1} · α(w, n, ℓ_{i}) · g_{i} = u · α(z, n, ℓ_{i})^{±1} · u^{−1}) .

Then we can mimic the construction of 3.1. Fix an enumeration without repetitions (u_{m})_{m} of F_{2}. Let p_{0}, …, p_{5} be the first six elements of S_{i}. We distinguish three possibilities.

• g_{i} is good.

Then ∃w_{∞} ∃(n_{m})_{m} ∃(v_{m})_{m} such that (n_{m})_{m} is increasing and g_{i}^{−1} · α(1_{F_{2}}, n_{m}, ℓ_{i}) · g_{i} = v_{m}·α(w_{∞}, n_{m}, ℓ_{i})^{±1}·v_{m}^{−1}. By thinning down the sequence we may assume that the exponent is constant, say = 1. Set

α(w, n_{m}, ℓ_{i})^{p_{1}} ∈ G(x) ⟺ w.x(u_{m}) = 1
α(w, n, ℓ_{i})^{p_{0}} ∈ G(x) ⟺ (n = n_{m} & w.x(u_{m}) = 0) ∨ n ∉ {n_{m} | m ∈ ℕ} .

So we may assume that g_{i} is bad hence ∃(w_{m})_{m} ∃(n_{m})_{m} ∃(v_{m})_{m} such that the n_{m}’s are increasing, the w_{m}’s are distinct, and g_{i}^{−1} · α(1_{F_{2}}, n_{m}, ℓ_{i}) · g_{i} = v_{m} · α(w_{m}, n_{m}, ℓ_{i})^{±1} · v_{m}^{−1}. Again by thinning down we may assume that the exponent is = 1.

• g_{i} is bad and μ(w.x) = ∞.

Set

α(w, n_{m}, ℓ_{i})^{p_{1}} ∈ G(x) ⟺ w.x(u_{n}) = 1
α(w, n, ℓ_{i})^{p_{0}} ∈ G(x) ⟺ (n = n_{m} & w.x(u_{n}) = 0) ∨ n ∉ {n_{m} | m ∈ ℕ} .

• g_{i} is bad and μ(w.x) < ∞.

Then set

α(w, n, ℓ_{i})^{p_{j}} ∈ G(x) ,

where

j = \begin{cases}0 & if n ∉ \{n_{m} | m ∈ ℕ\} , \\ 2 & if n = n_{m} and m < μ(w.x) − 1 or m > μ(w.x) , \\ J_{μ(w.x)}(w.x) + 3 & if n = n_{m} and m ∈ \{μ(w.x), μ(w.x) − 1\} . \end{cases}

Finally, no γ^{p} not mentioned in the above is allowed in G(x).

This concludes the definition of x ↦ G(x).

It is straightforward to check that Properties (1)–(6) hold and therefore

∀x ∈ 2^{F_{2}} ∀w ∈ F_{2} (H(w.x) = w̃H(x)w̃^{−1}) .

The following Claim, whose proof is left to the reader, is the analogue of 3.4.

H(y) = g_{i}H(x)g_{i}^{−1} [figure] [figure]

g_{i} is a ; quasi-shift

[figure]

g_{i} is not a quasi-shift

[figure]

g_{i} is bounded

[figure]

g_{i} is unbounded

[figure]

g_{i}H(x)g_{i}^{−1} is not in the range of H: a contradiction!

g_{i}H(x)g_{i}^{−1} is not in the range of H: a contradiction!

|r| > 1

[figure]

|r| = 1

[figure]

g_{i}H(x)g_{i}^{−1} is not in the range of H: a contradiction!

g_{i} is bad

[figure]

g_{i} is good

[figure]

μ(w_{0}.x) ≠ ∞

[figure]

μ(w_{0}.x) = ∞

[figure]

y = w_{∞}.x

g_{i}H(x)g_{i}^{−1} is not in the range of H: a contradiction!

y = w_{0}.x

Figure 2. Plan of the Proof of Theorem 1.3

Claim 4.3. Suppose g_{i} is an unbounded quasi-shift satisfying case 2, i.e.,

∀w ∈ F_{2} ∀n ∈ ℕ ∃z ∈ F_{2} ∃u ∈ F_{ω} (g_{i}^{−1} · α(w, n, ℓ_{i}) · g_{i} = u · α(z, n, ℓ_{i})^{±1} · u^{−1}) .

Suppose also (w_{m})_{m}, (n_{m})_{m}, and (v_{m})_{m} witness that g_{i} is bad. Then for all x ∈ 2^{F_{2}}

μ(x) = ∞ ⟺ ∀m (α(1_{F_{2}}, n_{m}, ℓ_{i})^{p_{0}} ∈ G(x) ∨ α(1_{F_{2}}, n_{m}, ℓ_{i})^{p_{1}} ∈ G(x))

and if μ(x) < ∞ and α(1_{F_{2}}, n_{m}, ℓ_{i})^{p} ∈ G(x) then

p = \begin{cases}p_{2} & if m ∉ \{μ(x) − 1, μ(x)\} \\ p_{j} & if m ∈ \{μ(x) − 1, μ(x)\} and j = J_{μ(x)}(x) + 3 . \end{cases}

We will now show that

∃i (g_{i}H(x)g_{i}^{−1} = H(y) ⟹ ∃w ∈ F_{2} (y = w.x)) .

The reader may find it useful to refer to Figure 2 while checking the details. Assume that

H(y) = g_{i}H(x)g_{i}^{−1} .

Suppose g_{i} is not a quasi-shift, and let w_{0}, n_{0}, k_{0}, w′_{0}, n′_{0}, k′_{0} be as in (i)–(iv).

If (i) holds then k_{0} = ℓ_{i} and α(w_{0}, n_{0}, k_{0})^{p} ∈ G(y), where p = min(S_{i} \ {r}) and r > 0 is least such that g_{i}^{−1} · α(w_{0}, n_{0}, k_{0})^{r} · g_{i} ∈ F_{ω}, if such r exists, or r = 0 otherwise. Since α(w_{0}, n_{0}, k_{0})^{p} ∈ H(y) then

g_{i}^{−1} · α(w_{0}, n_{0}, k_{0})^{p} · g_{i} ∈ H(x) ⊆ F_{ω}

hence r > 0. As r and p are relatively prime let λ, ν ∈ ℤ be such that λr + νp = 1 so that

g_{i}^{−1} · α(w_{0}, n_{0}, k_{0}) · g_{i} = (g_{i}^{−1} · α(w_{0}, n_{0}, k_{0})^{r} · g_{i})^{λ} · (g_{i}^{−1} · α(w_{0}, n_{0}, k_{0})^{p} · g_{i})^{ν} ∈ F_{ω}

contradicting our assumption case.

If (ii) holds then ℓ_{i−1} + 1 = k_{0} < ℓ_{i} = k′_{0}, α(w_{0}, n_{0}, k_{0})^{p} ∈ G(y), where p = min(S_{i}), and

∀w, n, r α(w, n, k′_{0})^{r} ∉ G(x) .

By case hypothesis α(w′_{0}, n′_{0}, k′_{0}) is a generator in g_{i}^{−1} · α(w_{0}, n_{0}, k_{0})^{p} · g_{i} ∈ H(x), hence by (5) above, α(w′_{0}, n′_{0}, k′_{0})^{q} ∈ G(x) for some q ∈ S_{i} such that q|p. A contradiction.

If (iii) holds then k_{0} = ℓ_{i}, α(w_{0}, n_{0}, ℓ_{i})^{min(S_{i})} ∈ G(y), and α(w′_{0}, n′_{0}, ℓ_{i})^{r} ∉ G(x), for any r. But g_{i}^{−1} · α(w_{0}, n_{0}, ℓ_{i})^{min(S_{i})} · g_{i} ∈ H(x) implies by (5) that α(w′_{0}, n′_{0}, ℓ_{i})^{q} ∈ G(x) for some appropriate q ∈ S_{i}. A contradiction.

So suppose (iv) holds. Then k_{0} = ℓ_{i}, α(w_{0}, n_{0}, ℓ_{i})^{p} ∈ G(y) ⊆ H(y), where p = min(S_{i}), and all generators of g_{i}^{−1} · α(w_{0}, n_{0}, ℓ_{i}) · g_{i} are of level < ℓ_{i}. For notational ease let v = g_{i}^{−1} · α(w_{0}, n_{0}, ℓ_{i}) · g_{i} so that v^{p} ∈ H(x). If we show that v ∈ H(x) then we will reach the desired contradiction, since this would imply that α(w_{0}, n_{0}, ℓ_{i}) = g_{i} · v · g_{i}^{−1} ∈ H(y), against (5).

If v were a generator then, by case assumption, its level would be between ℓ_{j−1} and ℓ_{j}, with j < i, so since v^{p} ∈ H(x) and using (5), there should be a q ∈ S_{j} such that q|p, which is absurd. Therefore we may assume that v ∉ Γ. If v ⋯ v is in reduced form (in other words: if v starts and ends with different generators) then we are done by (6), so we may assume otherwise. Let v_{0} be the longest initial segment of the word v ∈ F_{ω} such that v ends with v_{0}^{−1}, and let v = v_{0} · v_{1} · v_{0}^{−1}. Suppose first v_{0} is non-empty. Then either (a) v_{0} · v_{1} · v_{0}^{−1} is a reduced word, or else

(b) v_{0} ends with the same generator that starts v_{1}, or else

(c) v_{1} ends with the same generator that starts v_{0}^{−1}, and (b) fails. If v_{0} is empty, then

(d) v = γ^{h} · u · γ^{k} with γ ∈ Γ, h, k ∈ ℤ \ {0}, h + k ≠ 0, and u does not start or end with γ.

Note that cases (a), (b), (c), and (d) are mutually exclusive.

Let us deal with case (d) first. Then

v^{p} = γ^{h} · u · γ^{h+k} · u ⋯ u · γ^{h+k} · u · γ^{k}

is a reduced word, so by (6) γ^{h}, u, γ^{k} ∈ H(x) and therefore v = γ^{h} · u · γ^{k} ∈ H(x).

If case (a) holds then we have two cases. Either v_{1} ⋯ v_{1} is in reduced form so that v^{p} can be written in reduced form as

v^{p} = v_{0} · \underbrace{v_{1} ⋯ v_{1}}_{p} · v_{0}^{−1} ,

and hence by (6) v_{0}, v_{1} ∈ H(x), and thus v ∈ H(x). Or else v_{1} starts and ends with the same generator, so by (6) and case (d) applied to v_{1},

v_{0} · v_{1}^{p} · v_{0}^{−1} ∈ H(x) ⟹ v_{0}, v_{1}^{p} ∈ H(x) ⟹ v_{0}, v_{1} ∈ H(x) ,

hence v ∈ H(x).

If case (b) holds, let γ ∈ Γ be such that v_{0} = z · γ^{h} and v_{1} = γ^{k} · u are both reduced words. By case assumption, z does not end with γ, and h, k ∈ ℤ \ {0} have the same sign. Then

v^{p} = z · γ^{h+k} · u · γ^{k} · u ⋯ γ^{k} · u · γ^{−h} · z

is in reduced form, so by (6) z, u, γ^{k}, γ^{−h} ∈ H(x) and therefore

v = (z · γ^{h}) · (γ^{k} · u) · (z · γ^{h})^{−1} ∈ H(x) .

Case (c) is similar and left to the reader.

Therefore in all cases v ∈ H(x), reaching a contradiction. Thus

g_{i} is not a quasi-shift above ℓ_{i−1} ⟹ g_{i}H(x)g_{i}^{−1} is not in the range of H.

So we may assume from this point on that g_{i} is a quasi-shift above ℓ_{i−1}.

Suppose g_{i} is bounded and let α(w_{0}, n_{0}, ℓ_{i}) witness this. Let also α(z, n_{0}, ℓ_{i}) be a generator in v = g_{i}^{−1} ·α(w_{0}, n_{0}, ℓ_{i})·g_{i}. Since α(w_{0}, n_{0}, ℓ_{i})^{p} ∈ H(y), then g_{i}^{−1} ·α(w_{0}, n_{0}, ℓ_{i})^{p} · g_{i} = v^{p} ∈ H(x) hence its generators to some appropriate prime powers must be in G(x). In particular this must be true of α(z, n_{0}, ℓ_{i}): by Property (1) and (5) there is q ∈ S_{i} and k such that α(z, n_{0}, ℓ_{i})^{k} occurs in v^{p}, q|k and α(z, n_{0}, ℓ_{i})^{q} ∈ G(x). But by definition of G when g_{i} is bounded, q = p > |k|: a contradiction.

Thus

g_{i} is bounded ⟹ g_{i}H(x)g_{i}^{−1} is not in the range of H.

So we may assume that g_{i} is unbounded.

Suppose case 1 holds: let g_{i}^{−1}·α(w_{0}, n_{0}, ℓ_{i})·g_{i} = v = u·α(z, n_{0}, ℓ_{i})^{r}·u^{−1} and r = r(w_{0}, n_{0}), |r| > 1. Since α(w_{0}, n_{0}, ℓ_{i})^{p} ∈ H(y) and v^{p} = v_{0}·α(z, n_{0}, ℓ_{i})^{rp}·v_{0}^{−1} ∈ H(x) is reduced, then v_{0}, α(z, n_{0}, ℓ_{i})^{p} ∈ H(x) by Properties (5) and (6). Therefore v_{0} · α(z, n_{0}, ℓ_{i})^{p} · v_{0}^{−1} ∈ H(x) and computing in H(y)

(g_{i} · v_{0} · α(z, n_{0}, ℓ_{i})^{p} · v_{0}^{−1} · g_{i}^{−1})^{r} = g_{i} · v_{0} · α(z, n_{0}, ℓ_{i})^{pr} · v_{0}^{−1} · g_{i}^{−1}
= g_{i} · v^{p} · g_{i}^{−1}
= α(w_{0}, n_{0}, ℓ_{i})^{p}

a contradiction, since α(w_{0}, n_{0}, ℓ_{i})^{p} ∈ G(y) is a generator of H(y) hence it is not the r-th power of any element.

Thus

g_{i} is unbounded & |r| > 1 ⟹ g_{i}H(x)g_{i}^{−1} is not in the range of H.

Therefore we may assume we are in case 2, that is ∀w ∈ F_{2} ∀n |r(w, n)| = 1.

Suppose g_{i} is good, so that g_{i}^{−1} · α(1_{F_{2}}, n_{m}, ℓ_{i}) · g_{i} = v_{m} · α(w_{∞}, n_{m}, ℓ_{i})^{r(1_{F_{2}},n_{m})} · v_{m}^{−1}. Then, by Property (6), for e = 0, 1

y(u_{m}) = e ⟺ α(1_{F_{2}}, n_{m}, ℓ_{i})^{p_{e}} ∈ H(y)
⟺ v_{m} · α(w_{∞}, n_{m}, ℓ_{i})^{p_{e}·r(1_{F_{2}},n_{m})} · v_{m}^{−1} ∈ H(x)
⟹ α(w_{∞}, n_{m}, ℓ_{i})^{p_{e}} ∈ H(x)
⟺ w_{∞}.x(u_{m}) = e

that is w_{∞}.x = y.

g_{i} is good ⟹ y = w_{∞}.x.

Therefore we may assume g_{i} is bad, hence g_{i}^{−1}·α(1_{F_{2}}, n_{m}, ℓ_{i})·g_{i} = v_{m}·α(w_{m}, n_{m}, ℓ_{i})^{r(1_{F_{2}},n_{m})}· v_{m}^{−1}. Suppose μ(w_{0}.x) = ∞.

Then by Claim 3.2 in the proof of 3.1 ∀m(w_{m}.x = w_{0}.x) hence

∀m (μ(w_{m}.x) = ∞ and H(w_{m}.x) = H(w_{0}.x)) .

For p ∈ S_{i} and using Property (6) and the fact that r(1_{F_{2}}, n_{m}) = ±1

α(1_{F_{2}}, n_{m}, ℓ_{i})^{p} ∈ H(y) ⟺ v_{m} · α(w_{m}, n_{m}, ℓ_{i})^{p·r(1_{F_{2}},n_{m})} · v_{m}^{−1} ∈ H(x)
⟹ α(w_{m}, n_{m}, ℓ_{i})^{p} ∈ H(x)
⟺ α(1_{F_{2}}, n_{m}, ℓ_{i})^{p} ∈ H(w_{m}.x) = H(w_{0}.x)
⟹ p = p_{0} ∨ p = p_{1} .

By Claim 4.3 μ(y) = ∞ hence, for e = 0, 1,

y(u_{m}) = e ⟺ α(1_{F_{2}}, n_{m}, ℓ_{i})^{p_{e}} ∈ H(y)
⟹ α(1_{F_{2}}, n_{m}, ℓ_{i})^{p_{e}} ∈ H(w_{0}.x)
⟺ w_{0}.x(u_{m}) = e

that is w_{0}.x = y.

Thus

g_{i} is bad & μ(w_{0}.x) = ∞ ⟹ w_{0}.x = y.

Suppose μ(w_{0}.x) = m < ∞. Then by 3.2

∀j < m (μ(w_{j}.x) = m & J_{m}(w_{j}.x) = J_{m}(w_{0}.x)) and μ(w_{m}.x) ≤ m .

Let e_{j} ∈ {0, …, 5} be the unique value such that

α(w_{j}, n_{j}, ℓ_{i})^{p_{e_{j}}} ∈ G(x) .

Then the first m-many elements of (e_{j})_{j} are (2, …, 2, J_{m}(w_{0}.x) + 3) and by Claim 4.3 the next element must be J_{m}(w_{0}.x) + 3.

Suppose μ(w_{m}.x) = m. Since w_{0}.x = w_{m−1}.x and z_{m}.w_{0}.x = w_{m}.x are distinct, J_{m}(w_{0}.x) ≠ J_{m}(w_{m}.x), a contradiction.

Suppose μ(w_{m}.x) < m. Then e_{m} = 2 ≠ J_{m}(w_{0}.x) + 3, a contradiction again. Thus

g_{i} is bad & μ(w_{0}.x) < ∞ ⟹ g_{i}H(x)g_{i}^{−1} is not in the range of H.

This concludes the proof.

References

[1] R. Dougherty, S. Jackson, and A. S. Kechris, The structure of hyperfinite Borel equivalence relations, Transactions of the American Mathematical Society 341 (1994), 193–225.

[2] R. Dougherty and A. S. Kechris, How many Turing degrees are there?, to appear in Proceedings of the AMS Summer Research Conference on Computability Theory and Applications, Boulder, Colorado, June 1999.

[3] S. Gao, Coding subset shift by subgroup conjugacy, to appear in the Bulletin of the London Mathematical Society.

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

[5] A. S. Kechris and Y. N. Moschovakis, Cabal Seminar 76-77, LNM 689, Springer Verlag, 1978.

[6] A. S. Kechris, S. Solecki, and S. Todorčević, Borel chromatic numbers, Advances in Mathematics 141 (1999), 1–44.

[7] A. S. Kechris, Classical Descriptive Set Theory, Springer Verlag, 1995.

[8] G. Stuck and R. J. Zimmer, Stabilizers for ergodic actions of higher rank semi-simple groups, Annals of Mathematics 139 (1994), 723–747.

[9] S. Thomas and B. Veličković, On the complexity of the isomorphism relation for finitely generated groups, Journal of Algebra 217 (1999), 352–373.

[10] S. Wagon, The Banach Tarski Paradox, Encyclopedia of Mathematics and its Applications, 24. Cambridge University Press, 1985.

Dip. di Matematica, Università di Torino, Italy

 E-mail address: andretta@dm.unito.it     camerlo@dm.unito.it

Department of Mathematics, University of California at Los Angeles

 E-mail address: greg@math.ucla.edu