On the complexity of the isomorphism relation for finitely generated groups ^{∗}

Simon Thomas ^{†}and Boban Velickovic ^{‡}

Abstract

Confirming a conjecture of Hjorth and Kechris [HK], we prove that the isomorphism relation for finitely generated groups is a universal essentially countable Borel equivalence relation. We also prove the corresponding result for the conjugacy relation for subgroups of the free group F_{2} on two generators.

Introduction

Given a class K of structures for a fixed countable first order language L, it is natural to ask what kinds of complete invariants can be used to classify the elements of K up to isomorphism. For those classes consisting of the countable models of some L_{ω_{1},ω}-sentence, Friedman and Stanley [FS] proposed to use the methods of descriptive set theory to study their possible invariants and defined the notion of Borel reducibility between such classes of structures. In [HK], Hjorth and Kechris continued this study and situated it within the general theory of Borel equivalence relations. This provided tools for the analysis of the isomorphism relation and a framework for measuring the complexity of possible invariants.

∗ 1980 Mathematics Subject Classification Primary 04A15, 20A10 Secondary 20E06, 20F05

† Research partially supported by NSF grants ‡ Work done while visiting DIMACS, which is an NSF Science and Technology Centre, funded under contract STC-91-19999; and which also receives support from the New Jersey Commission on Science and Technology.

In this paper, we shall show that the isomorphism relation for finitely generated groups is as complex as it conceivably could be. We shall also prove the corresponding result for the conjugacy relation for subgroups of the free group F_{2} on two generators. The proofs are straightforward arguments in combinatorial group theory, and we shall refer to descriptive set theory only for the relevant definitions and for motivation for the results.

Since most algebraists will be unfamiliar with descriptive set theory, this introductory section contains a detailed discussion of the relevant background material. In particular, we have provided worked examples from the theory of infinite abelian groups to illustrate each of the main notions. It should be stressed that none of the results in the introduction are due to the authors; and all of these results are well-known to the experts in this area. However, this introduction was not written for the experts.

We shall begin by presenting the three examples which we will be using throughout the introduction.

Example 1. Let K_{0} be the class of countable divisible abelian groups. If G ∈ K_{0}, then G = D ⊕ T, where T is the torsion subgroup and D is torsion-free. Let r_{0}(G) ∈ ℕ ∪ {∞} be the rank of D; and for each prime p, let r_{p}(G) ∈ ℕ ∪ {∞} be the rank of the p-component T_{p} of T. Then the invariant

ρ(G) = (r_{0}(G), r_{2}(G), r_{3}(G), …, r_{p}(G), …)

determines G up to isomorphism. (For example, see Section 19 of Fuchs [F].)

Example 2. Let K_{1} be the class of rank 1 torsion-free abelian groups; ie. G ∈ K_{1} iff G is isomorphic to a subgroup of ℚ. In this case, we can obtain a complete invariant as follows. Let G ∈ K_{1} and let 0 ≠ a ∈ G. For each prime p, the p-height h_{p}(a) of a is the maximum integer k ≥ 0 such that the equation p^{k}x = a is solvable in G, if such a maximum k exists. Otherwise, h_{p}(a) = ∞. The sequence

h(a) = (h_{2}(a), h_{3}(a), …, h_{p}(a), …)

is called the height of a. If we choose another element 0 ≠ b ∈ G, then h(b) is not necessarily equal to h(a). However, it is similar to h(a) in the following sense. Let G_{1}, G_{2} ∈ K_{1} and let a_{i} ∈ G_{i} for i = 1, 2. Then the heights h(a_{1}), h(a_{2}) are similar, written h(a_{1}) ∼ h(a_{2}), iff (i) h_{p}(a_{1}) = h_{p}(a_{2}) for almost all primes p; and

(ii) if h_{p}(a_{1}) ≠ h_{p}(a_{2}), then both h_{p}(a_{1}) and h_{p}(a_{2}) are finite.

Clearly ∼ is an equivalence relation. If G ∈ K_{1}, then the type of G is the ∼-equivalence class τ(G) = [h(a)], where a is any nonzero element of G. By Theorem 42.2 [F], the invariant τ(G) determines G up to isomorphism.

Example 3. For each n ≥ 2, let K_{n} be the class of torsion-free abelian groups of rank at most n; ie. G ∈ K_{n} iff G is isomorphic to a subgroup of ℚ^{n}. Currently no satisfactory complete invariants for the elements of K_{n} are known. (For a discussion of this problem, see Section 45 of Fuchs [F].)

It is natural to ask whether a less complex complete invariant exists for the class K_{1}, and whether there exists any satisfactory complete invariant for the class K_{n} when n ≥ 2. In order to have the tools to give negative answers to these kinds of questions, we shall formulate these problems within the context of descriptive set theory.

First we shall describe how to represent the class of countably infinite structures of a given countable first order language by the elements of a Polish space. For convenience, we shall work only with relational first order languages. If there are function symbols, as is the case with the language of group theory, then we replace them by relation symbols representing the graphs of the associated functions. Given a countable language L = {R_{i} : i ∈ I}, where R_{i} is an n_{i}-ary relation symbol, let

X_{L} = ∏_{i∈I} 2^{ℕ^{n_{i}}}.

(Here 2^{ℕ^{n_{i}}} denotes the space of all n_{i}-ary functions f : ℕ^{n_{i}} → {0, 1} with the natural product topology.) Then X_{L} is a Polish space; and the elements of X_{L} code L-structures with universe ℕ as follows. Given x = (x_{i})_{i∈I} ∈ X_{L} the structure

M_{x} = ⟨ℕ, R_{i}^{x}⟩_{i∈I}

represented by x is defined by:

R_{i}^{x}(k_{1}, …, k_{n_{i}}) ⇔ x_{i}(k_{1}, …, x_{n_{i}}) = 1.

For x ∈ X_{L}, we let [x] = {y ∈ X_{L} : M_{y} ≅ M_{x}} denote the isomorphism class of x. The symmetric group S_{∞} on ℕ is a Polish group with the usual product topology inherited from ℕ^{ℕ}; and X_{L} together with the natural action of S_{∞} is a Polish S_{∞}-space. Notice that x, y ∈ X_{L} lie in the same S_{∞}-orbit iff M_{x} ≅ M_{y}. For this reason, the action is usually called the logic action of S_{∞} on X_{L}. Given an L_{ω_{1},ω} sentence σ,

Mod(σ) = {x ∈ X_{L} : M_{x} ⊧ σ}

represents the class of all countably infinite models of σ. Note that Mod(σ) is an isomorphism-invariant Borel subset of X_{L}. Moreover, by a theorem of Lopez and Escobar, every such set is of the form Mod(σ) for some σ ∈ L_{ω_{1},ω}. We shall denote the restriction of the isomorphism relation ≅ to Mod(σ) by ≅_{σ}; and when working with Mod(σ), we shall usually identify M_{x} with x.

In this paper, we shall be particularly interested in the class F GG of all finitely generated groups. Clearly this class is axiomatizable by an L_{ω_{1},ω} sentence in the language L = {R} consisting of a ternary relation which represents the graph of the multiplication operation.

The notion of Borel reducibility will enable us to compare the complexity of equivalence relations on Borel subsets of Polish spaces; and, in particular, will provide us with a measure of the complexity of the isomorphism relation ≅_{σ}. If X and Y are Borel sets and E and F are equivalence relations on X and Y respectively, then we say that E is Borel reducible to F and write E ≤_{B} F if there exists a Borel function f : X → Y such that xEy ⇔ f(x)F f(y). This means that elements of X can be effectively classified up to E-equivalence by invariants which are themselves F -equivalence classes. We say that E and F are Borel bireducible and write E ∼_{B} F if E ≤_{B} F and F ≤_{B} E. We say that E is smooth if there exists a Polish space Y such that E ≤_{B} Δ(Y), where Δ(Y) is the equality relation on Y. If ≅_{σ} is smooth, then we say that the models of σ are concretely classifiable.

Example 1 continued. Let σ_{0} be the sentence of L_{ω_{1},ω} which axiomatizes the class of divisible abelian groups. We shall show that Mod(σ_{0}) is concretely classifiable. To accomplish this, we shall show that the invariant

ρ(G) = (r_{0}(G), r_{2}(G), r_{3}(G), …, r_{p}(G), …)

can be coded naturally by an element γ_{G} of the Polish space 2^{ℕ}. Let {p_{n} : n ∈ ℕ} be the increasing enumeration of the primes and let π : ℕ → ℕ × ℕ be a recursive bijection. Then we can define a Borel function f : Mod(σ_{0}) → 2^{ℕ} by f(G) = γ_{G}, where

(i) γ_{G}(k) = 1 if π(k) = ⟨ℓ, n⟩ and p_{ℓ}^{n} ≤ r_{p_{ℓ}}(G); and

(ii) γ_{G}(k) = 0 otherwise.

Clearly if G, H ∈ Mod(σ_{0}), then G ≅ H iff f(G) = f(H).

There are many examples of non-smooth Borel equivalence relations, the simplest of them being the Vitali equivalence relation E_{0} on 2^{ℕ}, defined by xE_{0}y iff there exists an integer n such that x(m) = y(m) for all m ≥ n.

Example 2 continued. Let σ_{1} be the sentence of L_{ω_{1},ω} which axiomatizes the class of rank 1 torsion-free abelian groups. We shall show that ≅_{σ_{1}}∼_{B} E_{0}. In particular, Mod(σ_{1}) is not concretely classifiable; and it is not possible to find a less complex complete invariant for Mod(σ_{1}) than the type τ(G). First we define a Borel function f : Mod(σ_{1}) → 2^{ℕ} as follows. Let G = ⟨ℕ, ∗⟩ ∈ Mod(σ_{1}) and let a be the least nonidentity element of G. Then f(G) = φ_{G}, where

(i) φ_{G}(k) = 1 if π(k) = ⟨ℓ, n⟩ and n ≤ h_{p_{ℓ}}(a); and

(ii) φ_{G}(k) = 0 otherwise.

Notice that if G, H ∈ Mod(σ_{1}), then G ≅ H iff φ_{G}E_{0}φ_{H}. Thus ≅_{σ_{1}}≤_{B} E_{0}.

Next we shall define a Borel function g : 2^{ℕ} → Mod(σ_{1}). First fix an effective bijection β : ℚ → ℕ. Then for every subgroup A of ℚ, β induces a canonical isomorphism of A with a corresponding element A^{β} ∈ Mod(σ_{1}). Now let φ ∈ 2^{ℕ}; and let h = (h_{2}, h_{3}, …, h_{p}, …) be the corresponding height, as in the previous paragraph. Let A be the subgroup of ℚ which is generated by the rational numbers p^{−k} for all primes p and all k ≤ h_{p}. Then 1 ∈ A and h(1) = (h_{2}, h_{3}, …, h_{p}, …). Finally let g(φ) = A^{β} ∈ Mod(σ_{1}) be the corresponding group which is canonically isomorphic to A. Clearly if φ, ψ ∈ 2^{ℕ}, then φE_{0}ψ iff g(φ) ≅ g(ψ). Thus E_{0} ≤_{B}≅_{σ_{1}}. Hence we have shown that ≅_{σ_{1}}∼_{B} E_{0}.

In general, if σ is an arbitrary sentence of L_{ω_{1},ω}, then the isomorphism relation ≅_{σ} is analytic rather than Borel. But there is a large class of theories σ for which ≅_{σ} is a Borel relation. In particular, ≅_{σ} is Borel for those theories σ whose models have “finite rank” in a broad sense, such as: the theory of finitely generated groups, or more generally finitely generated structures in a given language; the theory of finite rank torsion-free abelian groups; the theory of fields of finite transcendence degree, etc. In order to study these examples, it is useful to introduce the notion of an essentially countable equivalence relation. An equivalence relation E is said to be countable if each equivalence class of E is countable. Given a theory σ, we say that ≅_{σ} is essentially countable iff ≅_{σ}≤_{B} E for some countable Borel equivalence relation E on a Borel set X. In this case, Kechris [Ke1] has shown that there exists a countable Borel equivalence relation F such that ≅_{σ}∼_{B} F. There is a natural model-theoretic characterisation of essentially countable theories; namely Hjorth and Kechris [HK] have shown that the following are equivalent:

(i) ≅_{σ} is essentially countable;

(ii) there is a countable fragment F ⊆ L_{ω_{1},ω} containing σ such that if M = ⟨ℕ, −⟩ is a model of σ, there exists ā ∈ ℕ^{<ω} such that Th_{F} (⟨M, ā⟩) is ℵ_{0}-categorical.

( Condition (ii) can be interpreted as saying that the models of σ have “finite rank” in some sense.) Now for such σ, we can use the theory of countable Borel equivalence relations to study the possible complete invariants of Mod(σ). (For the general theory of such equivalence relations, see [JKL].)

The least complex countable Borel equivalence relations are those which are smooth. Next in complexity come those countable Borel equivalence relations E such that E and the Vitali equivalence relation E_{0} are Borel bireducible. It turns out that there is also a most complex countable Borel equivalence relation. Define a countable Borel equivalence relation E to be universal if F ≤_{B} E for any other countable Borel equivalence relation F. If such an equivalence relation exists, then it is clearly unique up to Borel bireducibility. But before we can explain why a universal countable Borel equivalence relation exists, we first need to introduce some group-theoretic notation.

In this paper, permutation groups always act on the right. If (G, Ω) is a permutation group, α ∈ Ω and g ∈ G, then the image of α under g will be denoted by either αg or α^{g}; and the corresponding orbit equivalence relation will be denoted by E(G, Ω). Given any set X and any group G, the shift action of G on X^{G} = {f | f : G → X} is defined by

f^{g}(h) = f(hg^{−1}).

Now we are ready to explain why there exists a universal countable Borel equivalence relation. Let F_{ω} be the free group on countably many generators and let E(F_{ω}, Ω) be the orbit equivalence relation of the shift action of F_{ω} on Ω = (2^{ℕ})^{F_{ω}}. Following [DJK], we shall show that E(F_{ω}, Ω) is a universal countable Borel equivalence relation. So suppose that E is any countable Borel equivalence relation on a Borel subset X of a Polish space. Then a remarkable theorem of Feldman and Moore [FM] states that there is a countable group H and a Borel action of H on X such that E = E(H, X). Let π : F_{ω} → H be a surjective homomorphism. Then we can define a Borel action of F_{ω} on X by

x↦^{g}x.g^{π}

for each x ∈ X and g ∈ F_{ω}. Clearly we have that E(F_{ω}, X) = E(H, X) = E. Now let (B_{n} | n ∈ ℕ) be a sequence of Borel subsets of X which separate the points of X; and let x ↦ f_{x} be the Borel map from X to Ω = (2^{ℕ})^{F_{ω}} such that

(f_{x}(g)) (n) = 1 iff x.g^{−1} ∈ B_{n}

for each x ∈ X, g ∈ F_{ω} and n ∈ ℕ. Then this map is injective, and it is easily checked that f_{x}^{g} = f_{x.g} for each x ∈ X and g ∈ F_{ω}. Consequently xE(F_{ω}, X)y iff f_{x}E(F_{ω}, Ω)f_{y}; and so E(F_{ω}, X) ≤_{B} E(F_{ω}, Ω). Thus E(F_{ω}, Ω) is a universal countable Borel equivalence relation.

Unfortunately E(F_{ω}, Ω) is a little unwieldy to work with. But let E(F_{2}, 2^{F_{2}}) be the orbit equivalence relation induced by the shift action of the free group F_{2} on two generators on 2^{F_{2}}. In [DJK], it was shown that E(F_{2}, 2^{F_{2}}) is also a universal countable Borel equivalence relation. Clearly the permutation group (F_{2}, 2^{F_{2}}) can be naturally identified with the permutation group (F_{2}, P(F_{2})), where F_{2} acts on its powerset P(F_{2}) via right translations; and so E_{∞} = E(F_{2}, P(F_{2})) and E(F_{2}, 2^{F_{2}}) are Borel bireducible. If ≅_{σ}∼_{B} E_{∞}, then we say that ≅_{σ} is a universal essentially countable Borel equivalence relation. In this case, it follows that any kind of complete invariants used to classify models of ≅_{σ} must necessarily be rather complex. ( For a more detailed discussion and many examples, we refer the reader to [HK].)

Example 3 continued. For each n ≥ 2, let K_{n} be the class of torsion-free abelian groups of rank at most n. Then each ≅_{σ_{n}} is an essentially countable Borel equivalence relation. In [HK], Hjorth and Kechris conjectured that ≅_{σ_{n}}∼_{B} E_{∞} for each n ≥ 2. If true, this would explain why no satisfactory complete invariants have been discovered for Mod(σ_{n}). Recently Hjorth [H] has shown that if n ≥ 2, then ≅_{σ_{n}} is not Borel reducible to the Vitali equivalence relation E_{0}. In particular, it is now known that if n ≥ 2, then the isomorphism relation ≅_{σ_{n}} is strictly more complex than the isomorphism relation ≅_{σ_{1}}.

The main result of this paper is that the isomorphism relation for finitely generated groups is a universal essentially countable Borel equivalence relation. This proves Conjecture 5.8 of [HK]. We shall also prove that the conjugacy relation for subgroups of the free group F_{2} is a universal countable Borel equivalence relation. This improves a result of Stuck and Zimmer [SZ], who proved that this conjugacy relation is not smooth.

Finally we shall prove that the theory of finitely generated groups does not admit canonical models. Here a sentence σ of L_{ω_{1},ω} is said to admit canonical models if there exists an “effectively definable” function f which to each countable model M ∈ Mod(σ) assigns a countable model f(M) of σ such that

M ≅ N implies f(M) = f(N) ≅ M.

We usually cannot expect to choose f so that the structure f(M) also has universe ℕ; since Burgess has shown that for any sentence σ of L_{ω_{1},ω}, the following statements are equivalent:

(i) Mod(σ) is concretely classifiable;

(ii) there exists a Borel function f : Mod(σ) → Mod(σ) such that M ≅ N implies f(M) = f(N) ≅ M.

In [HK], Hjorth and Kechris showed that there are many interesting theories which are not concretely classifiable and yet do admit canonical models, including the theories of rank 1 torsion-free abelian groups and of rigid locally finite trees; and they also proved that the theory of locally finite trees does not admit canonical models.

Example 2 continued. In order to give the reader a sense of what is meant by “effectively definable”, we shall show that the theory σ_{1} of rank 1 torsion-free abelian groups admits canonical models. Let G = ⟨ℕ, ∗⟩ ∈ Mod(σ_{1}) and let a be the least nonidentity element of G. Let

H_{G} = {(t_{2}, t_{3}, …, t_{p}, …) : t ∼ h(a)};

and for each t ∈ H_{G}, let A_{t} be the subgroup of ℚ which is generated by the rational numbers p^{−k} for all primes p and all k ≤ t_{p}. Then for each pair t, u ∈ H_{G}, there exists a canonical isomorphism π_{t,u} : A_{t} → A_{u} defined as follows. Let {p_{1}, …, p_{ℓ}} be the set of primes p such that t_{p} ≠ u_{p}; and let

r_{t,u} = \frac{p_{1}^{t_{p_{1}}} … p_{ℓ}^{t_{p_{ℓ}}}}{p_{1}^{u_{p_{1}}} … p_{ℓ}^{u_{p_{ℓ}}}} .

Then x^{π_{t,u}} = r_{t,u}x for all x ∈ A_{t}. Notice that if t, u, v ∈ H_{G}, then π_{t,v} = π_{t,u}π_{u,v}. Hence we can define an equivalence relation ∼ on X = ⋃{A_{t} × {t} : t ∈ H_{G}} by

⟨x, t⟩ ∼ ⟨y, u⟩ iff x^{π_{t,u}} = y.

For each element ⟨x, t⟩ ∈ X, let [x, t] be the corresponding ∼-equivalence class. Let f(G) = {[x, t] : ⟨x, t⟩ ∈ X}, equipped with the group operation defined by

[x, t] ∗ [y, u] = [z, v] iff x ∗ y^{π_{u,t}} = z^{π_{v,t}}.

Then clearly G_{1} ≅ G_{2} implies that f(G_{1}) = f(G_{2}) ≅ G_{1}.

It is quite difficult to give a precise formulation of the notion of “effectively definable” in the case when Mod(σ) is not concretely classifiable. An exact definition can be found in Section 7 of [HK]; but unfortunately some set-theoretic sophistication is necessary in order to understand this definition. Fortunately Hjorth and Kechris have found the following algebraic property which is equivalent to admitting canonical models. Suppose that G is a Polish group and that a : X × G → X is a Borel action of G on the Borel space X. Let E_{a} be the associated orbit equivalence relation on X. A Borel function α : E_{a} → G is called a cocycle if whenever xE_{a}y and yE_{a}z, then α(x, z) = α(x, y)α(y, z). We say that the action a has the cocycle property if there exists a Borel cocycle α such that a(x, α(x, y)) = y. (For the basic facts concerning Polish group actions, we refer the reader to [BK] or [Ke2].) In [HK], Hjorth and Kechris proved that for any sentence σ of L_{ω_{1},ω}, the following statements are equivalent:

(i) σ admits canonical models;

(ii) the logic action of S_{∞} on Mod(σ) has the cocycle property.

Thus the question of whether σ admits canonical models is intimately connected with the question of whether it is possible to define canonical isomorphisms between isomorphic models of σ.

We shall end this introduction with a few more words on our grouptheoretic notation. Suppose that F is a group. Then for each x ∈ F, the right and left translation maps by x will be denoted by x^{ρ}, x^{λ} respectively. We define F^{ρ} = {x^{ρ} : x ∈ F } and F^{λ} = {x^{λ} : x ∈ F }. The holomorph of F is the group

Hol(F) = ⟨F^{ρ}, Aut(F)⟩ ⩽ Sym(F).

It is easily checked that if x ∈ F and π ∈ Aut(F), then π^{−1}x^{ρ}π = (x^{π})^{ρ}. Thus Hol(F) = F^{ρ} ⋊ Aut(F). It follows easily that each φ ∈ Hol(F) can be expressed as

φ = g^{ρ}π = θh^{λ}

for suitably chosen elements g, h ∈ F and π, θ ∈ Aut(F).

Given groups G_{1} and G_{2} with a common subgroup H, we denote the free product of G_{1} and G_{2} with amalgamation over H by G_{1}∗_{H} G_{2}. If X is a set of right coset representatives of H in G_{1} such that 1 ∈ X and Y is a set of right coset representatives of H in G_{2} such that 1 ∈ Y, then every element of G_{1} ∗_{H} G_{2} has a unique normal form

g = ha_{1} … a_{n}

where h ∈ H, each a_{i} ∈ (X ∪ Y) \ {1}, and a_{i}, a_{i+1} are not both in X or both in Y. We shall repeatedly use the fact that any element of G_{1} ∗_{H} G_{2} of finite order is conjugate to an element of either G_{1} or G_{2}. For these and other basic results in combinatorial group theory, we refer the reader to [LS], [MKS], or [Se].

1 The holomorph action

Let F = ⟨a, b⟩ be the free group on two generators. Let (F, Ω) be the permutation group such that Ω = F, and F acts on Ω via the right regular representation. In the next section, for each S ⊆ Ω, we shall construct a finitely generated group G_{S} such that G_{S} ≅ G_{T} iff there exists an automorphism (π, φ) of the permutation group (F, Ω) with S^{φ} = T. Remember that the pair (π, φ) is an automorphism of (F, Ω) iff:

(i) π ∈ Aut(F);

(ii) φ : Ω → Ω is a bijection; and

(iii) (x^{φ})^{g^{π}} = (x^{g})^{φ} for each x ∈ Ω and g ∈ F.

There are two basic kinds of automorphism of (F, Ω). (I) For each a ∈ F, let i_{a} ∈ Inn(F) be the corresponding inner automorphism. Then (i_{a}, a^{ρ}) is an automorphism of (F, Ω). (II) For each π ∈ Aut(F), (π, π) is an automorphism of (F, Ω). It turns out that every automorphism of (F, Ω) is the product of an automorphism of type (I) followed by an automorphism of type (II). (This is essentially proved in the next section.) Thus G_{S} ≅ G_{T} iff there exists φ ∈ Hol(F) such that S^{φ} = T. Consequently, in order to show that the isomorphism relation for finitely generated groups is a universal essentially countable Borel equivalence relation, we must first show that E(Hol(F), P(F)) is a universal countable Borel equivalence relation. For technical reasons, we shall work with P^{∗}(F) = P(F) \ {∅, F } rather than with P(F). Of course, it is easily shown that E(F, P^{∗}(F)) ∼_{B} E_{∞} = E(F, P(F)).

Theorem 1 E(Hol(F), P^{∗}(F)) is a universal countable Borel equivalence relation.

PROOF: Clearly E(Hol(F), P^{∗}(F)) is a countable Borel equivalence relation. Thus it suffices to show that: E(F, P^{∗}(F)) ≤_{B} E(Hol(F), P^{∗}(F)). Let [F, F] be the commutator subgroup of F. By [Serre, p.6], [F, F] is a free group of infinite rank. Let {x_{n} : n ∈ ℕ} be a set of free generators of [F, F] and let G = ⟨x_{0}, x_{1}⟩.

Claim 1 N_{F} (G) = G.

PROOF: Let N = N_{F} (G). By [MKS, Exercise 2.4.5], whenever H is a finitely generated subgroup of a free group, then H has finite index in its normalizer. In particular, [N : G] < ∞. Clearly N ∩ [F, F] = G. Applying the Second Isomorphism Theorem, we see that

N/G = N/(N ∩ [F, F]) ≅ N[F, F]/[F, F] ⩽ F/[F, F].

Thus N/G is isomorphic to a finite subgroup of the torsion-free group F/[F, F] ≅ ℤ ⊕ ℤ. It follows that N = G.

□

For each subset S ∈ P^{∗}(G), we define:

Ŝ = S ⊔ x_{2}G ⊔ [F, F]a ⊔ [F, F]b ⊔ [F, F]a^{2}.

Notice that S ⊔ x_{2}G ⊊ [F, F]. Suppose now that T ∈ P^{∗}(G) and that there exists π ∈ Hol(F) such that Ŝ^{π} = T̂. We shall show that π = g^{ρ} for some g ∈ G such that Sg = T. This will complete the proof of Theorem 1.

Let F̄ = F/[F, F] ≅ ℤ ⊕ ℤ. Then under the natural mapping

φ : Aut(F) → Aut(F̄)

we have that:

(a) φ maps Aut(F) onto Aut(F̄) ≅ GL(2, ℤ); and

(b) ker φ = Inn(F), the group of inner automorphisms of F.

(For example, see [LS, Proposition 4.5]). Notice that F^{ρ} also acts naturally on F̄ by translations. Thus Hol(F) also acts on F̄ ≅ ℤ ⊕ ℤ as the group of affine transformations (ℤ ⊕ ℤ) ⋊ GL(2, ℤ). Since π permutes the cosets of [F, F], and both Ŝ and T̂ consist of three complete cosets and one nonempty proper subset of a coset, it follows that

(S ⊔ x_{2}G)^{π} = T ⊔ x_{2}G.

In particular, [F, F]^{π} = [F, F]. Hence if we identify [F, F]a and [F, F]b with the vectors v = (1, 0) and w = (0, 1) in ℤ⊕ℤ, then π corresponds to an affine transformation π̄ such that

(i) (0, 0)π̄ = (0, 0); and (ii) {v, w, 2v}π̄ = {v, w, 2v}.

Let π = g^{ρ}θ, where g ∈ F and θ ∈ Aut(F). By (i), g ∈ [F, F]; and so g^{ρ} acts trivially on F̄. Consequently, π̄ is the linear transformation induced by θ. By (ii), we must have that π̄ = 1. It follows that θ ∈ ker φ = Inn(F); say, θ is conjugation by h. Thus for all c ∈ F, we have that c^{π} = h^{−1}cgh. Hence π = y^{λ}z^{ρ}, where y = h^{−1} and z = gh. Thus:

T ⊔ x_{2}G = (S ⊔ x_{2}G)^{π}
= ySz ⊔ yx_{2}Gz
= yzz^{−1}Sz ⊔ yx_{2}zz^{−1}Gz
= yzS^{z} ⊔ yx_{2}zG^{z}.

Claim 2 x_{2}G = yx_{2}zG^{z}.

PROOF: Let A = T ⊔x_{2}G. Then A consists of a complete and a partial coset of G in F. First we shall explain how to group-theoretically recognise the complete coset in this decomposition. Let a = x_{2}g ∈ x_{2}G. Then for each element b = x_{2}h ∈ x_{2}G, we have that

ba^{−1}b = x_{2}hg^{−1}x_{2}^{−1}x_{2}h ∈ x_{2}G.

On the other hand, if b ∈ T ⩽ G, then

ba^{−1}b = bg^{−1}x_{2}^{−1}b ∉ G ⊔ x_{2}G.

For each a ∈ A define:

S(a) = {b ∈ A : ba^{−1}b ∈ A}.

Then we have just shown that if a ∈ x_{2}G, then S(a) = x_{2}G. It is easily checked that if a ∈ T, then S(a) ⊆ T. Thus a ∈ x_{2}G iff there exists g ∈ F with A ⊆ S(a) ∪ gS(a).

Now consider the decomposition A = yzS^{z} ⊔ yx_{2}zG^{z}. This time, we have expressed A as a complete and a partial coset of G^{z} in F. Arguing as above, we find that if a ∈ yx_{2}zG^{z}, then yx_{2}zG^{z} ⊆ S(a); and hence there exists g ∈ F with A ⊆ S(a) ∪ gS(a). Consequently, yx_{2}zG^{z} ⊆ x_{2}G; and so G^{z} ⩽ G. If we also had that yzS^{z} ∩ x_{2}G ≠ ∅, this would yield that yzG^{z} ∩ x_{2}G ≠ ∅, and so yzG^{z} ⊆ x_{2}G. But this implies that

A ⊆ yzG^{z} ⊔ yx_{2}zG^{z} ⊆ x_{2}G,

which is a contradition. Thus yx_{2}G^{z} = x_{2}G.

□

In particular, G^{z} = G and so z ∈ N_{F} (G) = G. Thus x_{2}G = yx_{2}zG^{z} = yx_{2}G; and so y ∈ x_{2}Gx_{2}^{−1}. We also have that ySz = T, and so yG = G. Hence y ∈ G ∩ x_{2}Gx_{2}^{−1} = {1}. But this means that π = z^{ρ} for some z ∈ G such that Sz = T, as desired. This completes the proof of Theorem 1.

□

2 Finitely generated groups

In this section, we prove our main theorem which says that the isomorphism relation on the class F GG of finitely generated groups is a universal essentially countable Borel equivalence relation. Formally, in this section, we are required to produce groups with underlying set ℕ. But since the groups which we define all have canonical isomorphisms to such groups, we can consider F GG to be an isomorphism-invariant Borel subset of X_{L}, where L = {R} is the language consisting of a ternary relation R which represents the graph of the multiplication operation. Throughout this section, we let 𝔽 denote the 2-element field GF (2) and V = ⨁_{w∈F} 𝔽w̃ denote the vector space over 𝔽 with basis indexed by elements of F. Thus V is an elementary abelian 2-group which is isomorphic to ([F]^{<ω}, Δ), the group of all finite subsets of F with the symmetric difference operation Δ. Let P = V ⋊ F, where g^{−1}w̃g = w̃g for each w, g ∈ F. Let B = {w̃ : w ∈ F }; so that B is a basis of the vector space V.

Lemma 1 B is the unique F -orbit on V such that V = ⟨B⟩.

PROOF: Suppose otherwise. Then for some n > 1, there exists an n-subset {w_{1}, …, w_{n}} of F such that

∑_{i=1}^{m}(w̃_{1}g_{i} + … + { \atop w_{n}g_{i}}) = ˜1

for some g_{1}, …, g_{m} ∈ F. But then, working in the group ring 𝔽[F], we obtain the equation

(w_{1} + … + w_{n})(g_{1} + … + g_{m}) = 1.

Thus (w_{1} + … + w_{n}) is a nontrivial unit in 𝔽[F]. But it is wellknown that the group ring 𝔽[F] has no nontrivial units. (For example, see [Pa, Chapter 13].)

□

Lemma 2 Suppose that π ∈ Aut(P). Then:

(i) B^{π} = B; and

(ii) there exists φ ∈ Hol(F) such that w^{π} = w̃^{φ} for all w ∈ F.

PROOF: Clearly V is a characteristic subgroup of P; and so V^{π} = V. By Lemma 1, B is the set of elements v of V such that the conjugacy class v^{P} generates V. Hence B^{π} = B. Clearly there exists an automorphism θ ∈ Aut(F) and a function w ↦ v_{w} from F into V such that

w^{π} = v_{w}w^{θ}

for all w ∈ F. Let ˜1^{π} = x̃; and let φ = θx^{λ} ∈ Hol(F). We claim that w^{π} = w̃^{φ} for all w ∈ F. To see this, note that

w^{π} = (w^{−1}˜1w)^{π}
= (w^{θ})^{−1}v_{w}^{−1}x̃v_{w}w^{θ}
= x̃w^{θ}.
□

For each S ∈ P^{∗}(F), we shall define an associated finitely generated group G_{S} such that G_{S} ≅ G_{T} iff there exists π ∈ Hol(F) such that S^{π} = T. First we shall define an auxillary group H_{S}. It is almost certainly true that H_{S} already satisfies our requirements; but when we attempted to verify this, we found that our arguments were becoming unpleasantly complicated. So in order to keep the proofs as straightforward as possible, we decided to work with the slightly larger group G_{S}.

Definition 1 For each S ∈ P^{∗}(F), let

H_{S} = ⟨P, t|t^{3} = 1, [t, w̃] = 1 for w ∈ S⟩.

Lemma 3 Let π = θx^{λ} ∈ Hol(F), where x ∈ F and θ ∈ Aut(F). If S^{π} = T, then we can define an isomorphism f : H_{S} → H_{T} by:

w^{f} = w̃^{π}, w ∈ F
g^{f} = g^{θ}, g ∈ F
t^{f} = t.

PROOF: This is an easy calculation. Simply note that w̃g^{f} = { \atop x(wg)^{θ}} and that

(g^{−1}w̃g)^{f} = (g^{θ})^{−1}x̃w^{θ}g^{θ}
= { \atop xw^{θ}g^{θ}}
= { \atop x(wg)^{θ}}.

Thus f induces an automorphism of P = V ⋊ F such that {w̃ : w ∈ S}^{f} = {w̃ : w ∈ T }. The result follows.

□

Definition 2 For each S ∈ P^{∗}(F), let:

G_{S} = ⟨H_{S}, z|z^{5} = 1, [z, t] = 1, [z, w̃] = 1 for all w ∈ F ⟩.

Note that G_{S} is generated by {˜1, a, b, t, z}. Thus it suffices to prove the following result.

Theorem 2 G_{S} ≅ G_{T} iff there exists π ∈ Hol(F) such that S^{π} = T.

Given this, we see that the map which to each S ∈ P^{∗}(F_{2}) associates G_{S} is a Borel reduction of E(Hol(F_{2}), P^{∗}(F_{2})) to (F GG, ≅); and thus, by Theorem 1, we obtain the following.

Theorem 3 (F GG, ≅) is a universal essentially countable Borel equivalence relation.

We shall prove Theorem 2 via a sequence of lemmas.

Lemma 4 If there exists π ∈ Hol(F) such that S^{π} = T, then G_{S} ≅ G_{T}.

PROOF: Let f : H_{S} → H_{T} be the isomorphism defined in Lemma 3. Then we can extend f to an isomorphism f̂ : G_{S} → G_{T} by setting zf̂ = z.

□

From now on, fix some S ∈ P^{∗}(F). We first define some important subgroups of G_{S}.

Definition 3 (i) V_{S} = ⊕_{w∈S}𝔽w̃

(ii) B_{S} = V_{S} ⊕ ⟨t⟩

(iii) C_{S} = ⟨V, t⟩

(iv) D_{S} = C_{S} ⊕ ⟨z⟩.

Now we shall describe some important structural features of G_{S}. The following lemma is completely straightforward.

Lemma 5 We have the following decompositions as free product with amalgamation:

(a) C_{S} = V ∗_{V_{S}} B_{S}

(b) H_{S} = P ∗_{V_{S}} B_{S}

(c) G_{S} = H_{S} ∗_{C_{S}} D_{S}.

Lemma 6 D_{S} = N_{G_{S}}(⟨z⟩).

PROOF: Let X = {1, z, z^{2}, z^{3}, z^{4}}, so that X is a set of right coset representatives of C_{S} in D_{S}. Let Y be a set of right coset representatives of C_{S} in H_{S} such that 1 ∈ Y. Then each element of G_{S} = H_{S} ∗_{C_{S}} D_{S} has a unique normal form

g = ca_{1} … a_{n}

where c ∈ C_{S}, each a_{i} ∈ (X ∪ Y) \ {1}, and a_{i}, a_{i+1} are not both in X or both in Y. Since every element of D_{S} commutes with z, it follows that D_{S} ⩽ N_{G_{S}}(⟨z⟩). For the other direction, suppose g normalises ⟨z⟩ and let g = ca_{1} … a_{n} be its normal form. Then there exists an integer 1 ≤ ℓ ≤ 4 such that g^{−1}zg = z^{ℓ}. Thus

cza_{1} … a_{n} = ca_{1} … a_{n}z^{ℓ}.

It follows easily that a_{1}, a_{n} ∈ X \ {1}; and then a moment’s thought shows that n = 1 and ℓ = 1. Hence g ∈ D_{S}.

□

Lemma 7 P = N_{H_{S}}(V).

PROOF: This time we work with the free product with amalgamation decomposition H_{S} = P ∗_{V_{S}} B_{S}. Choose I = {1, t, t^{2}} as a set of right coset representatives of V_{S} in B_{S}; and let J be a set of right coset representatives of V_{S} in P such that 1 ∈ J. Clearly P ≤ N_{H_{S}}(V). Let g ∈ N_{H_{S}}(V) be any element and let g = ac_{1} … c_{n} be its normal form. Choose any w̃ ∈ B. Then

c_{n}^{−1} … c_{1}^{−1}a^{−1}w̃ac_{1} … c_{n} = c_{n}^{−1} … c_{1}^{−1}w̃c_{1} … c_{n} ∈ V.

If c_{1} ∈ I \ {1}, choose w̃ ∈ B \ S̃, where S̃ = {w̃ : w ∈ S}. Then c_{n}^{−1} … c_{1}^{−1}w̃c_{1} … c_{n} is essentially in normal form, and hence is not an element of V. Thus c_{1} ∈ P. If n > 1, choose w̃ such that c_{1}^{−1}w̃c_{1} ∈ B \ S̃. Once again, we reach a contradiction. Thus g = ac_{1} ∈ P.

□

Now we are ready to begin the proof of Theorem 2. So suppose that φ : G_{S} → G_{T} is an isomorphism for some S, T ∈ P^{∗}(F). Let u = z^{φ}. Then u has order 5. By [MKS, Corollary 4.4.5], u is contained in a conjugate of either H_{T} or D_{T}. Hence, by adjusting φ by an inner automorphism of G_{T}, we can suppose that z^{φ} ∈ ⟨z⟩. Applying Lemma 6, we now find that

D_{S}^{φ} = N_{G_{S}}(⟨z⟩)^{φ} = N_{G_{T}} (⟨z⟩) = D_{T} .

Notice that

D_{S} = (V ⊕ ⟨z⟩) ∗_{V_{S}⊕⟨z⟩} (B_{S} ⊕ ⟨z⟩).

Hence, by [MKS, Corollary 4.5], Z(D_{S}) = V_{S} ⊕ ⟨z⟩. It follows that

(V_{S} ⊕ ⟨z⟩)^{φ} = V_{T} ⊕ ⟨z⟩;

and hence V_{S}^{φ} = V_{T}. Choose any element v ∈ V \ V_{S}. Then v^{φ} is conjugate in D_{T} to an element of V \ V_{T}. (Note that any element v ∈ V \ V_{S} is noncentral, and hence is not conjugate to an element of V_{S} ≤ Z(D_{S}). We will make repeated use of this observation.) Hence, after adjusting φ by an inner automorphism corresponding to a suitably chosen element of D_{T}, we can suppose that:

(i) ⟨z⟩^{φ} = ⟨z⟩,

(ii) V_{S}^{φ} = V_{T}, and

(iii) there exists v ∈ V \ V_{S} such that v^{φ} ∈ V \ V_{T}.

Claim 3 V^{φ} = V

PROOF: Choose any x ∈ V \ V_{S}. Then:

(a) neither x^{φ} nor v^{φ} is contained in a conjugate of V_{T} ⊕ ⟨z⟩;

(b) v^{φ} ∈ V ⊕ ⟨z⟩;

(c) [x^{φ}, v^{φ}] = 1.

By [MKS, Theorem 4.5], x^{φ} ∈ V ⊕ ⟨z⟩ and so x^{φ} ∈ V. Thus V^{φ} ≤ V. Since V is clearly a maximal elementary abelian 2-subgroup of D_{S}, it follows that V^{φ} = V.

□

This implies that N_{G_{S}}(V)^{φ} = N_{G_{T}} (V). In particular, P^{φ} ≤ N_{G_{T}} (V). Now let:

ψ : G_{T} = H_{T} ∗_{C_{T}} D_{T} → H_{T}

be the homomorphism such that h^{ψ} = h for all h ∈ H_{T}, and z^{ψ} = 1. Note that N_{G_{T}} (V)^{ψ} ≤ N_{H_{T}} (V) = P; and so N_{G_{T}} (V)^{ψ} = P. Let π = ψ ∘ φ ↾ P. Then:

(i) V^{π} = V,

(2) V_{S}^{π} = V_{T}, and

(3) P^{π} ≤ P.

Claim 4 π ∈ Aut(P).

PROOF: First we shall show that π is injective. Suppose 1 ≠ x ∈ ker π. Let x = vg, where v ∈ V and g ∈ F. Since π ↾ V is an automorphism of V, we must have g ≠ 1. But then

x^{−1}˜1x = g^{−1}˜1g = g̃ ≠ ˜1.

Applying π, we obtain that (x^{π})^{−1}˜1^{π}x^{π} ≠ ˜1^{π}. Hence x^{π} ≠ 1, which is a contradiction. Thus ker π = {1}.

Now we shall show that π is surjective. Let v ∈ V be any element, and let w ∈ V be the element such that w^{π} = v. Then there exist g_{1}, …, g_{n} ∈ F such that

w = g_{1}^{−1}˜1g_{1} + … + g_{n}^{−1}˜1g_{n}.

Applying π, we obtain that

v = w^{π} = (g_{1}^{π})^{−1}˜1^{π}g_{1}^{π} + … + (g_{n}^{π})^{−1}˜1^{π}g_{n}^{π}.

Hence {h^{−1}˜1^{π}h : h ∈ P^{π}} generates V; and so {h^{−1}˜1^{π}h : h ∈ P^{π}} = B. In particular, there exists a ∈ F such that ˜1^{π} = ã. Now let g ∈ F be any element. Then there exists h ∈ P^{π} such that

h^{−1}ãh = h^{−1}˜1^{π}h = ãg.

It follows that h = ug for some u ∈ V; and so g ∈ P^{π}. Hence π is surjective.

□

By Lemma 2, B^{π} = B and there exists θ ∈ Hol(F) such that w^{π} = w̃^{θ}, for all w ∈ F. Notice that

{w̃ : w ∈ S}^{π} = (V_{S} ∩ B)^{π} = V_{T} ∩ B = {w̃ : w ∈ T }.

It follows that S^{θ} = T. This completes the proof of Theorem 2.

□

In the remainder of this section, we shall prove that the theory of finitely generated groups does not admit canonical models. We shall make use of the following results of Hjorth and Kechris [HK].

Theorem 4 If σ ∈ L_{ω_{1},ω}, then the following are equivalent.

(i) σ admits canonical models.

(ii) The logic action of S_{∞} on Mod(σ) has the cocycle property.

Theorem 5 The shift action of the free group F = ⟨a, b⟩ on P(F) does not have the cocycle property.

It follows easily that the shift action of F on P^{∗}(F) = P(F)\{∅, F } also does not have the cocycle property.

Lemma 8 The action of Hol(F) on P^{∗}(F) does not have the cocycle property.

PROOF: We shall use the notation which was introduced in the proof of Theorem 1. Suppose that the Borel cocycle α witnesses that the action (Hol(F), P^{∗}(F)) has the cocycle property. Consider the shift action of G on P^{∗}(G). Then whenever S, T ∈ P^{∗}(G) lie in the same G-orbit, the cocycle α selects an element π = α(Ŝ, T̂) ∈ Hol(F) such that Ŝ^{π} = T̂. Now the proof of Theorem 1 shows that π = g^{ρ} for some element g ∈ G such that Sg = T. But then the Borel function β defined by

β(S, T) = α(Ŝ, T̂)

witnesses that the action (G, P^{∗}(G)) has the cocycle property, which is a contradiction.

□

Lemma 9 N_{G_{T}} (⟨z⟩) ∩ N_{G_{T}} (V) = V ⊕ ⟨z⟩.

PROOF: Using Lemmas 6 and 7, we obtain that

N_{G_{T}} (⟨z⟩) ∩ N_{G_{T}} (V) = D_{T} ∩ N_{G_{T}} (V)
= N_{C_{T}} (V) ⊕ ⟨z⟩
= (P ∩ C_{T}) ⊕ ⟨z⟩
= V ⊕ ⟨z⟩.
□

Theorem 6 Let σ be the theory of finitely generated groups. Then the logic action of S_{∞} on Mod(σ) does not have the cocycle property.

PROOF: We shall use the notation which was introduced in the proof of Theorem 2. Suppose that the Borel cocycle α witnesses that the logic action of S_{∞} on Mod(σ) has the cocycle property. For each S ∈ P^{∗}(F), there exists an element M_{S} ∈ Mod(σ) and a canonical isomorphism π_{S} : G_{S} → M_{S}. Thus whenever G_{S} ≅ G_{T}, then the map

β(G_{S}, G_{T}) = π_{S}α(M_{S}, M_{T})π_{T}^{−1}

is an isomorphism from G_{S} onto G_{T}. Furthermore, if G_{S} ≅ G_{T} ≅ G_{U}, then

β(G_{S}, G_{U}) = β(G_{S}, G_{T})β(G_{T} , G_{U}).

Now identify F with the subset B = {w̃ : w ∈ F }; and define γ by

γ(S, T) = β(G_{S}, G_{T})i_{a} ↾ B ∈ Sym(F),

where a ∈ G_{T} is any element such that β(G_{S}, G_{T})i_{a} maps ⟨z⟩ onto ⟨z⟩ and maps V onto V. Then the proof of Theorem 2 shows that γ(S, T) is an element of Hol(F) such that S^{γ(S,T)} = T. Furthermore, if b ∈ G_{T} is another element such that β(G_{S}, G_{T})i_{b} maps ⟨z⟩ onto ⟨z⟩ and maps V onto V, then

a^{−1}b ∈ N_{G_{T}} (⟨z⟩) ∩ N_{G_{T}} (V) = V ⊕ ⟨z⟩ ⩽ C_{G_{T}} (V);

and so

β(G_{S}, G_{T})i_{b} ↾ B = β(G_{S}, G_{T})i_{a}i_{a^{−1}b} ↾ B
= β(G_{S}, G_{T})i_{a} ↾ B.

Thus γ(S, T) is independent of the choice of the element a ∈ G_{T}.

Now suppose that G_{S} ≅ G_{T} ≅ G_{U}; and let a ∈ G_{T} and b ∈ G_{U} be such that γ(S, T) = β(G_{S}, G_{T})i_{a} ↾ B and γ(T, U) = β(G_{T} , G_{U})i_{b} ↾ B. Let π = β(G_{S}, G_{T}) and φ = β(G_{T} , G_{U}). Then an easy calculation shows that

β(G_{S}, G_{T})i_{a}β(G_{T} , G_{U})i_{b} = πi_{a}φi_{b}
= πφi_{a^{φ}}i_{b}
= β(G_{S}, G_{T})β(G_{T} , G_{U})i_{a^{φ}b}
= β(G_{S}, G_{U})i_{a^{φ}b}.

Thus γ(S, T)γ(T, U) = γ(S, U); and so γ witnesses that the action of Hol(F) on P^{∗}(F) has the cocycle property. But this contradicts Lemma 8.

□

Combining Theorems 4 and 6, it follows that the theory of finitely generated groups does not admit canonical models.

3 Conjugacy of subgroups

In this section, we shall show that another natural action of the free group F_{2} gives rise to a universal countable Borel equivalence relation. For any group G, let Sg(G) denote the set of all subgroups of G. If G is countable, then Sg(G) is a closed subset of P(G) with the product topology and thus is a Polish space. Let (G, Sg(G)) denote the conjugacy action of G on Sg(G). In [SZ, Lemma 3.9], Stuck and Zimmer proved that the countable Borel equivalence relation E(F_{2}, Sg(F_{2})) is not smooth. The main theorem of this section is the following strengthening of their result.

Theorem 7 E(F_{2}, Sg(F_{2})) is a universal countable Borel equivalence relation.

We begin by making some easy reductions of the problem. For each n ≥ 1, F_{n} denotes the free group on n generators.

Definition 4 A subgroup H of a group G is said to be malnormal iff whenever g ∈ G \ H, then g^{−1}Hg ∩ H = {1}.

Proposition 1 E(F_{n}, Sg(F_{n})) is Borel reducible to E(F_{2}, Sg(F_{2})) for each n ≥ 1.

PROOF: By [KS, p.950], the set {a^{ℓ}b^{ℓ}a^{ℓ} : ℓ ≥ 1} freely generates a malnormal subgroup T of the free group F = ⟨a, b⟩. For each ℓ ≥ 1, let x_{ℓ} = a^{ℓ}b^{ℓ}a^{ℓ}. Then G = ⟨x_{1}, … x_{n}⟩ is clearly a malnormal subgroup of T; and hence G is also a malnormal subgroup of F.

Suppose that H_{1}, H_{2} ∈ Sg(G) \ {1} and that g ∈ F satisfies g^{−1}H_{1}g = H_{2}. Then g^{−1}Gg ∩ G ≠ {1}, and so g ∈ G. Thus E(G, Sg(G)) is Borel reducible to E(F, Sg(F)).

□

Let (Aut(F_{5}), Sg(F_{5})) denote the natural action of Aut(F_{5}) on Sg(F_{5}). Most of our effort will go into proving the following result.

Theorem 8 E(Aut(F_{5}), Sg(F_{5})) is a universal countable Borel equivalence relation.

Before proving Theorem 8, we shall use it to complete the proof of Theorem 7. First note that there is a natural embedding F_{5} ↪ Aut(F_{5}), obtained by sending each w ∈ F_{5} to the corresponding inner automorphism i_{w} ∈ Inn(F_{5}). Identify F_{5} with Inn(F_{5}) via this natural embedding. Then F_{5} ⊴ Aut(F_{5}) and the natural action of Aut(F_{5}) becomes identified with the conjugacy action of Aut(F_{5}) on Inn(F_{5}), since π^{−1}i_{w}π = i_{w^{π}} for w ∈ F_{5}, π ∈ Aut(F_{5}). Thus we can regard (Aut(F_{5}), Sg(F_{5})) as a subaction of the conjugation action (Aut(F_{5}), Sg(Aut(F_{5}))). Now recall that Aut(F_{5}) is a finitely presented group, say arising from the surjective homomorphism

φ : F_{n} ↠ Aut(F_{5}).

For each subgroup H of Aut(F_{5}), let H̃ = φ^{−1}[H]. Note that if H_{1}, H_{2} are subgroups of Aut(F_{5}) then the following statements are equivalent.

(a) There exists π ∈ Aut(F_{5}) such that π^{−1}H_{1}π = H_{2}.

(b) There exists w ∈ F_{n} such that w^{−1}H̃_{1}w = H̃_{2}.

Thus E(Aut(F_{5}), Sg(F_{5})) is Borel reducible to E(F_{n}, Sg(F_{n})); and applying Proposition 1, we obtain Theorem 7.

Now we turn to the proof of Theorem 8. Let F = ⟨a, b⟩; and for each S ∈ P^{∗}(F), let G_{S} be the group which was defined in §3. Note that G_{S} has the following presentation.

- Generators: ˜1, a, b, t, z, which we regard as generators of F_{5}.

- Relators:

• w^{−1}˜1˜1w, for w ∈ F;

• [w^{−1}˜1w, u^{−1}˜1u], for w, u ∈ F;

• [t, w^{−1}˜1w], for w ∈ S;

• [z, t]

• [z, w^{−1}˜1w], for w ∈ F.

For each S ∈ P^{∗}(F), let N_{S} be the normal subgroup of F_{5}, generated as a normal subgroup by the relators for G_{S}. Thus G_{S} ≅ F_{5}/N_{S}. Theorem 8 is an immediate consequence of the following result.

Lemma 10 For S, T ∈ P^{∗}(F), the following statements are equivalent:

(a) There exists π ∈ Aut(F_{5}) such that N_{S}^{π} = N_{T}.

(b) G_{S} ≅ G_{T}.

PROOF: It is clear that (a) implies (b), and so we concentrate on proving that (b) implies (a). Notice first that the proof in §3 shows that there exists φ = θx^{λ} ∈ Hol(F), where x ∈ F and θ ∈ Aut(F) such that S^{φ} = T. Define a homomorphism π : F_{5} → F_{5} by:

• a ↦ a^{θ}

• b ↦ b^{θ}

• t ↦ t

• z ↦ z

• ˜1 ↦ x^{−1}˜1x.

Notice that {a^{θ}, b^{θ}, t, z, x^{−1}˜1x} generates F_{5} and hence is a basis of F_{5}. Thus π ∈ Aut(F_{5}). It only remains to check that N_{S}^{π} = N_{T}. So we consider the action of π on each normal generator of N_{S}. First,

w^{−1}˜1˜1w ↦ (w^{θ})^{−1}x^{−1}˜1˜1xw^{θ}.

So π merely permutes these relators. Similarly π permutes the relators of the form [w^{−1}˜1w, u^{−1}˜1u], and the relators of the form [z, w^{−1}˜1w]; and fixes the relator [z, t]. Finally we see that

[t, w^{−1}˜1w] ↦ [t, (w^{θ})^{−1}x^{−1}˜1xw^{θ}] = [t, (xw^{θ})^{−1}˜1xw^{θ}],

and T = {xw^{θ} : w ∈ S}. Hence N_{S}^{π} = N_{T}.

□

The methods of this section clearly yield the following result.

Theorem 9 Let G be a countable group. If G has a malnormal free nonabelian subgroup, then E(G, Sg(G)) is a universal countable Borel equivalence relation.

In particular, if G is an arbitrary countable nonabelian free group, then E(G, Sg(G)) is a universal countable Borel equivalence relation. We hope to give some less trivial applications of Theorem 9 in a later paper.

References

[BK] H. Becker and A. Kechris, The descriptive set theory of Polish group actions, London Math Society Lecture Note Series, Cambridge Univ. Press, 1997

[DJK] R. Dougherty, S. Jackson and A. Kechris, “The structure of hyperfinite Borel equivalence relations”, Transactions of the American Math Society, vol. 341, (1994), pp. 193-225.

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

[FS] H. Friedman and L. Stanley, “A Borel reducibility theory for classes of countable structures”, Journal of Symbolic Logic, vol. 54, (1989), pp. 894-914.

[F] L. Fuchs, Abelian groups, Pergamon Press, Oxford, 1967.

[H] G. Hjorth, “Around nonclassifiability for countable torsion-free abelian groups, preprint (1998).

[HK] G. Hjorth and A. Kechris, “Borel equivalence relations and classification of countable models”, Annals of Pure and Applied Logic, vol. 82, (1996), pp. 221-272.

[JKL] S. Jackson, A. Kechris, and A. Louveau, “Countable Borel equivalence relations”, in preparation.

[Ke1] A. Kechris, “Countable sections for locally compact group actions”, Ergodic Theory Dynamical Systems, vol. 12, (1992), pp. 283-295 [Ke2] A. Kechris, Classical Descriptive Set Theory, Springer-Verlag,

1995

[KS] A. Karras and D. Solitar, “The free product of two groups with a malnormal amalgamated subgroup”, Can. J. Math, vol. 23, (1971), pp. 933-959.

[LS] R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977

[MKS] W. Magnus, A. Karras, and D. Solitar, Combinatorial Group Theory, Wiley, New York, 1966

[Pa] D.S. Passman, The algebraic structure of group rings, Wiley-Interscience, New York, 1977

[Se] J.P. Serre, Trees, Springer Verlag, 1980

[SZ] G. Stuck and R. J. Zimmer, “Stablizers for ergodic actions of higher rank semisimple groups”, Annals Math., vol. 139 (1994), pp. 723-747.

S. Thomas Department of Mathematics Rutgers University New Brunswick, NJ 08903 U.S.A.

B. Velickovic Equipe de Logique, URA 753 Universite de Paris 7 2 Place Jussieu 75251 Paris, FRANCE