DIOPHANTINE GEOMETRY OVER GROUPS VI:

THE ELEMENTARY THEORY OF A FREE GROUP

Z. Sela^{1,2}

posted Nov. 26, 2000

This paper is the sixth in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the sixth paper we use the quantifier elimination procedure presented in the fifth paper in the sequence, to answer some of A. Tarski’s problems on the elementary theory of a free group, and to classify f.g. groups that are elementary equivalent to a non-abelian f.g. free group.

In the first 5 papers in the sequence on Diophantine geometry over groups we studied sets of solutions to systems of equations in a free group, and developed basic techniques and objects required for the analysis of sentences and elementary sets defined over a free group. The techniques we developed, enabled us to present an iterative procedure that analyzes EAE sets defined over a free group (i.e., sets defined using 3 quantifiers), and shows that every such set is in the Boolean algebra of AE sets defined over a free group ([Se5], 1.3).

In this paper we apply the tools and techniques presented in the previous 5 papers in the sequence, to answer some of A. Tarski’s problems on the elementary theory of a free group, and generalizations of these problems. We start by showing that every elementary set defined over a f.g. free group is in the Boolean algebra of AE sets, which is a direct corollary of our analysis of EAE sets presented in [Se5]. We continue by showing that for coefficient-free elementary sets, the quantifier elimination procedure can be done uniformly for all f.g. non-abelian free groups (theorem 2). We then use this ”uniform” quantifier elimination procedure, to prove the equivalence of the elementary theories of all non-abelian f.g. free groups (theorem 3). A similar uniform quantifier elimination procedure can be used to show that if 2 ≤ k ≤ ℓ, the standard embedding of the free group F_{k} into the free group F_{ℓ} is an elementary embedding (theorem 4). We further analyze the entire collection of f.g. groups that are elementary equivalent to a f.g. non-abelian free group. We prove that a f.g. group is elementary equivalent to a non-abelian f.g. free group if and only if it is a non-elementary hyperbolic ωresidually free tower (such towers were presented in section 6 of [Se1]).

Theorems 3 and 4 of this paper, on the elementary equivalence of non-abelian free groups, and the elementary properties of the standard emeddings of f.g. free groups, answer questions of A. Tarski’s. During the period our work was conducted, several authors have announced solutions to these problems (see [Kh-My]). However, at the time this paper is prepared, none of these manuscripts were available to the author.

1Hebrew University, Jerusalem 91904, Israel.

2Partially supported by an Israel academy of sciences fellowship.

In the fifth paper of this sequence, we proved that the Boolean algebra of AE sets defined over a free group is invariant under projections, or equivalently, we proved that an EAE set is in the Boolean algebra of AE sets ([Se5],1.3). This clearly implies that every elementary set defined over a free group is in the Boolean algebra of AE sets.

Theorem 1. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let Q(p) be a definable set over F_{k}. Then Q(p) is in the Boolean algebra of AE sets over F_{k}.

Proof: If Q(p) is defined using not more than 3 quantifiers, then the theorem follows from theorem 1.3 of [Se5]. Otherwise, the theorem follows by a standard induction on the number of quantifiers that defines the elementary set Q(p).

□

Theorem 1 proves that every definable set over a free group is in the Boolean algebra of AE sets. To show the equivalence of the elementary theories of free groups of various ranks, we need to show that for coefficient free predicates, our quantifier elimination procedure does not depend on the rank of the coefficient group.

Theorem 2. Let Q(p) be a set defined by a coefficient-free predicate over a group. Then there exists a set L(p) defined by a coefficient-free predicate which is in the Boolean algebra of AE predicates, so that for every free group F_{k}, k ≥ 2, the sets Q(p) and L(p) are equivalent.

Proof: If a system of equations over a non-abelian free group is coefficient free, then by construction, its associated (canonical) Makanin-Razborov diagram is coefficientfree, and the diagram does not depend on the rank of the non-abelian free group. Similarly, the (multi-) graded Makanin-Razborov diagram associated with a coefficientfree parametric system of equations defined over a non-abelian free group, is coefficientfree and it does not depend on the rank of the non-abelian free group. Furthermore, the bounds on the numbers of rigid solutions of the rigid limit groups in that diagram, and the bounds on the numbers of strictly solid solutions of the solid limit groups in the diagram, do not depend on the rank of the free group as well.

Let V be the variety associated with some coefficient-free system of equations defined over a non-abelian free group, and let

∀y ∈ V ∃x (Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1)

be a coefficient-free sentence. Since the Makanin-Razborov diagram associated with a coefficient-free system of equations defined over a non-abelian free group, does not depend on the rank of the free group, the formal Makanin-Razborov diagram associated with a coefficient-free sentence as above, is coefficient-free and it does not depend on the rank of the free group. Similarly, the graded formal Makanin-Razborov diagram associated with a coefficient-free parametric sentence defined over a non-abelian free group, is coefficient-free and does not depend on the rank of the free group.

Let Res(t, v) be a (graded, multi-graded) coefficient-free well-separated resolution defined over some non-abelian free group. Then, by construction, the induced resolution, IndRes(< v >, Res(t, v)), is coefficient-free and it does not depend on the rank of the free group. If Res(t, v) is a (graded, multi-graded) coefficient-free well-separated resolution defined over some non-abelian free group, then the core resolution constructed by the procedure presented in section 4 of [Se5], is coefficientfree and does not depend on the rank of the free group.

Suppose that EAE(p) is an EAE set that is defined by a coefficient-free predicate over a non-abelian free group. The two iterative procedures used for the analysis of the set EAE(p) in [Se5], the procedure for the construction of the tree of stratified sets, and the sieve procedure, are built from graded and multi-graded Makanin-Razborov resolutions, core and induced resolutions, and graded formal Makanin-Razborov diagrams. Hence, when these two iterative procedures are applied to the coefficient-free set EAE(p), all the constructions made along these two iterative procedures are coefficient free, and they do not depend on the rank of the free group over which the set EAE(p) is defined. Therefore, there exists a set L(p) that is defined over a non-abelian free group by a coefficient-free predicate which is in the Boolean algebra of AE sets, and for every non-abelian free group Q(p) = L(p). The standard finite induction used in the proof of theorem 1, finally implies the claim of the theorem for an arbitrary coefficient-free set defined over a non-abelian free group.

□

Theorem 2 proves that in handling coefficient-free predicates, our quantifier elimination procedure does not depend on the rank of the coefficient (free) group. This clearly implies an affirmative answer to Tarski’s problem on the equivalence of the elementary theory of (f.g.) free groups.

Theorem 3. The elementary theories of non-abelian f.g. free groups are equivalent.

Proof: By theorem 2, a coefficient-free elementary set defined over a non-abelian free group, is equivalent to a coefficient-free set that is in the Boolean algebra of AE sets, and the equivalence does not depend on the rank of the free group. Hence, every coefficient-free sentence defined over a non-abelian free group can be reduced, in a way that is independent of the rank of the free group, to a coefficientfree sentence that is in the Boolean algebra of AE sentences. Hence, to prove the equivalence of the elementary theories of non-abelian f.g. free groups, it is enough to prove that a coefficient-free AE sentence defined over a non-abelian free group is true if and only if it is a truth sentence over any other non-abelian f.g. free group.

The equivalence of the AE theories of non-abelian free groups was previously known ([Sa],[Hr]), but we chose to give an alternative argument using our machinery. Given a coefficient-free AE sentence defined over a non-abelian free group, we apply the procedure used for the construction of the tree of stratified sets to validate it. Since the sentence is coefficient-free, all the constructions made along the procedure are coefficient-free and independent of the rank of the free group. Hence, if a coefficient-free sentence is a truth sentence over a given f.g. non-abelian free group it is a truth sentence over every non-abelian f.g. free group.

□

Arguments similar to the ones used to prove theorems 2 and 3, enable us to answer affirmatively another question of Tarski’s.

Theorem 4. Let F_{k}, F_{ℓ} be free groups for 2 ≤ k ≤ ℓ. Then the standard embedding F_{k} → F_{ℓ} is an elementary embedding.

Proof: Let F_{k} =< a_{1}, …, a_{k} >, and suppose that Σ(y, a) is a system of equations over F_{k}. Instead of studying all the solutions to the system Σ in the coefficient group F_{k}, we study all its solutions in all free groups of the form F_{k} ∗ F, where F is a f.g. free group. Our construction of the Makanin-Razborov diagram applies to study the entire collection of solutions of the system Σ in all free groups of the form F_{k} ∗ F, hence, we are able to associate with this collection of solutions, a canonical Makanin-Razborov diagram. The standard embedding F_{k} → F_{ℓ} naturally enables us to interpret the system of equations Σ as a system of equations over the free group F_{ℓ}. Again, we study the entire set of solutions to the system Σ in all free groups of the form F_{ℓ} ∗ F, and associate with this set of solutions a canonical Makanin-Razborov diagram. Since the system of equations Σ involves only the (image of the) generators a_{1}, …, a_{k} of F_{ℓ}, the (canonical) Makanin-Razborov diagrams associated with the system Σ over F_{ℓ} is obtained from the (canonical) Makanin-Razborov diagram of Σ over F_{k}, by replacing each (restricted) limit group L in the diagram associated with F_{k} with the limit group L ∗ F_{ℓ−k}, and in particular the structure of the two diagrams is essentially the same.

Using the same type of construction, if Σ(y, p, a) is a parametric system of equations over F_{k}, then using the standard embedding F_{k} → F_{ℓ}, Σ can be viewed as a parametric system over the free group F_{ℓ}, and the graded Makanin-Razborov diagram of Σ over F_{ℓ} is obtained from the one associated with F_{k}, by replacing each of the graded limit groups L with L ∗ F_{ℓ−k}. Clearly, the same relation holds for multi-graded Makanin-Razborov diagrams associated with F_{k} and F_{ℓ}

Let V be the variety associated with some system of equations defined over F_{k}, and let

∀y ∈ V ∃x (Σ_{1}(x, y, a) = 1∧Ψ_{1}(x, y, a) ≠ 1) ∨…∨ (Σ_{r}(x, y, a) = 1∧Ψ_{r}(x, y, a) ≠ 1)

be a sentence defined over F_{k}. Using the standard embedding F_{k} → F_{ℓ}, both the variety V and the sentence can be interpreted as a variety and a sentence defined over the free group F_{ℓ}. Since the Makanin-Razborov diagrams associated with the variety V over F_{ℓ} is obtained from the Makanin-Razborov diagram associated with V over F_{k} by replacing each limit group L with L ∗ F_{k}, the formal Makanin-Razborov diagram associated with the above sentence over F_{ℓ} is obtained from the formal Makanin-Razborov diagram over F_{k}, by replacing each formal limit group F L with F L ∗ F_{ℓ−k}. Clearly, the same holds for the graded formal Makanin-Razborov diagram associated with a predicate defined over F_{k}.

Let Res(t, v, a) be a (graded, multi-graded) well-separated resolution defined over F_{k}. Using the standard embedding F_{k} → F_{ℓ}, The resolution Res(t, v, a) can be modified to a well-separated resolution Res^{ℓ}(t, v, a) be replacing each limit group L in Res(t, v, a) by L ∗ F_{ℓ−k}. Then, by construction, the induced resolution, IndRes(< v, a >, Res^{ℓ−1}(t, v, a)), is obtained from the induced resolution IndRes(< v, a >, Res(t, v, a)), by replacing each limit group L with L ∗ F_{ℓ−k}, and the same hold for the two core resolutions, Core(< v, a >, Res^{ℓ}(t, v, a)) and Core(< v, a >, Res(t, v, a)), constructed by the procedure presented in section 4 of [Se5].

Suppose that EAE(p) is an EAE set defined over F_{k}. By the standard embedding F_{k} → F_{ℓ}, the predicate defining the set EAE(p), can be interpreted as a predicate defined over F_{ℓ}. The two iterative procedures used for the analysis of the set EAE(p) in [Se5], the procedure for the construction of the tree of stratified sets, and the sieve procedure, are built from graded and multi-graded Makanin-Razborov resolutions, core and induced resolutions, and graded formal Makanin-Razborov diagrams. Hence, when these two iterative procedures are applied to the set EAE(p) over F_{k} and F_{ℓ}, all the constructions made along these two iterative procedures are essentially similar. Hence, the set EAE(p) defined over F_{k}, can be defined using a predicate in the Boolean algebra of AE sets over F_{k}, this predicate can be naturally interpreted as a predicate defined over F_{ℓ}, and when interpreted over F_{ℓ} it defines the set EAE(p) over F_{ℓ}.

Using the standard embedding F_{k} → F_{ℓ}, every sentence defined over F_{k} can be naturally interpreted as a sentence defined over F_{ℓ}. Since our reduction procedures over F_{k} and F_{ℓ} are similar, a sentence defined over F_{k} is equivalent to a sentence in the Boolean algebra of AE sentences defined over F_{k}, and the reduction is valid when the two sentences are interpreted over F_{ℓ} as well.

The equivalence of an AE sentence defined over F_{k} to the same AE sentence interpreted as a sentence defined over F_{ℓ} was previously known ([Sa],[Hr]). It also follows by applying the procedure used for the construction of the tree of stratified sets to validate it over F_{k} and F_{ℓ}.

□

Tarski’s problems deal with the equivalence of the elementary theory of free groups of different ranks. Our next goal is to modify the tools used for quantifier elimination for predicates defined over a free group, in order to get a complete classification of all the f.g. groups that are elementary equivalent to a free group. We start by proving a necessary condition for a f.g. group to be elementary equivalent to a f.g. non-abelian free group, and then we show that the necessary condition is also sufficient.

Non-abelian limit groups are known to be universally equivalent to a non-abelian free group. A group that contains a free abelian group of rank 2, can not be elementary equivalent to a free group. Hence, a f.g. group that is elementary equivalent to a non-abelian free group must be a non-elementary hyperbolic limit group. However, not every non-elementary hyperbolic limit group is elementary equivalent to a free group. Suppose that G = F ∗_{<w>} F =< b_{1}, b_{2} > ∗_{<w>} < b_{3}, b_{4} > is a double of a free group of rank 2, suppose that w has no roots in F, and suppose that the given amalgamated product is the abelian JSJ decomposition of the group G. By our assumptions, G is clearly a hyperbolic limit group.

Claim 5. The group G = F ∗_{<w>} F is not elementary equivalent to the free group F.

Proof: We look at a system of equations Σ(y_{1}, …, y_{4}) = 1 that corresponds to the given presentation of G, i.e., a (coefficient-free) system of equations with 4 variables y_{1}, …, y_{4} and the equation w(y_{1}, y_{2}) = w(y_{3}, y_{4}). Clearly, there is a single limit group associated with this system, which is the limit group G.

We first examine the system of equations Σ as a system of equations over a f.g. non-abelian free group. Since by our assumptions, the limit group G is not isomorphic to a free product of free groups and surface groups, the (canonical) Makanin-Razborov diagram of the limit group G is non-trivial, which implies that there exists a (canonical) finite collection of limit groups G_{1}, …, G_{ℓ} that are all proper quotients of G, so that given an arbitrary solution of the system Σ in a non-abelian free group, we can act on the given solution with the modular group associated with G, so that the obtained solution factors through at least one of the limit groups G_{1}, …, G_{ℓ}.

We then view the system of equations Sigma as a system of equations over the limit group G. Let y_{1}^{t}, …, y_{4}^{t} be the tautological solution of the system Σ over the limit group G, i.e., the solution obtained by substituting y_{i}^{t} = b_{i} for i = 1, …, 4. If we act by an arbitrary element of the modular group of G on the tautological solution y_{1}^{t}, …, y_{4}^{t}, the subgroup generated by the obtained solution is still isomorphic to G, hence, the obtained solution does not factor through any of the subgroups G_{1}, …, G_{ℓ}, which are all proper quotients of G.

Since the action of the modular group of G on a given solution of Σ, gives rise to a conjugation of the specializations of y_{3} and y_{4} by an element that commutes with the specialization of w, the fact that every solution of Σ, viewed as a system of equations over a non-abelian free group, can be modified by an action of the modular group of G, to a solution that factors through at least one of the groups G_{1}, …, G_{ℓ}, can be translated to a coefficient-free AE sentence, which is a truth sentence over a non-abelian free group. However, that coefficient-free AE sentence is not a truth sentence over the limit group G.

□

The argument used to prove claim 5, demonstrates that hyperbolic limit groups with no QH vertex groups in their canonical JSJ decomposition are not elementary equivalent. In section 6 of [Se1] we have presented ω-residually free towers, as an example for limit groups.

A hyperbolic ω-residually free tower is constructed in finitely many steps. In its first level there is a non-cyclic free product of (possibly none) (closed) surface groups and a (possibly trivial) free group in its base level, where each surface in this free product is a hyperbolic surface (i.e., with negative Euler characteristic), except the non-orientable surface of genus 2. In each additional level we add a punctured surface that is amalgamated to the group associated with the previous levels along its boundary components, and in addition there exists a retract map of the obtained group onto the group associated with the previous levels. The punctured surfaces are supposed to be of Euler characteristic bounded above by -2, or a punctured torus.

The argument used to prove claim 5 can be generalized to show that if a hyperbolic limit group is elementary equivalent to a non-abelian free group, then it must be a hyperbolic ω-residually free tower.

Proposition 6. Let G be a f.g. group that is elementary equivalent to a non-abelian f.g. free group. Then G is a non-elementary hyperbolic ω-residually free tower.

Proof: Let G be a f.g. group that is elementary equivalent to a f.g. non-abelian free group. Since G is universally equivalent to a non-abelian free group it must be a limit group, and since it is AE equivalent to a non-abelian free group, it can not contain a non-cyclic free abelian subgroup, hence, G must be a non-elementary hyperbolic limit group.

If G is isomorphic to the free product of several surface groups and a free group, G is a hyperbolic ω-residually free tower, hence, we may assume that in the canonical (Grushko’s) free decomposition of G, G = B_{1} ∗ … ∗ B_{m} ∗ F_{u}, at least one of the factors B_{i} is not isomorphic to a surface group. We analyze the structure of the various factors B_{i} that appear in the free decomposition of G, and are not isomorphic to a surface group in parallel. Hence, we continue with a single such factor, that we denote B. Since G is a hyperbolic limit group, the factor B is a hyperbolic limit group as well. By section 3 of [Se1], since B is a freely-indecomposable hyperbolic limit group that is not isomorphic to a surface group, it admits a non-trivial abelian JSJ decomposition, and since B is hyperbolic, its abelian JSJ decomposition is a cyclic JSJ decomposition with no non-cyclic abelian vertex groups.

Let Λ be the cyclic JSJ decomposition of the factor B. If Λ contains no QH vertex groups, then the argument used to prove claim 5, implies that the group G is not elementary equivalent to a non-abelian free group. Hence, Λ contains QH vertex groups. At this point we apply an argument similar to the one used to prove claim 5, to show that there exists a retract in B which is the free product of the fundamental groups of disjoint subgraphs of Λ, so that at least one of the QH vertex groups in Λ does not belong to any of these subgraphs.

Let Δ be the (cyclic) graph of groups obtained from Λ by collapsing all the edge groups in Λ that connect between two non-QH vertex groups. Let Σ(y) = 1 be a system of equations that corresponds to a presentation of the factor B =< b_{1}, …, b_{s} >. With the system Σ(y) = 1 we associate its Makanin-Razborov diagram over a non-abelian free group. Let G_{1}, …, G_{n} be the limit groups that appear in the second level of this Makanin-Razborov diagram. By the construction of the diagram, G_{1}, …, G_{m} are proper quotients of B, and every solution of the system Σ(y) = 1 can be modified by an element of the modular group of the factor B, to a specialization of at least one of the limit groups G_{1}, …, G_{m}.

Clearly, the system of equations Σ(y) = 1 has a tautological solution in G, obtains by setting y_{i} = b_{i}, i = 1, …, s. Since the modular group of B preserves the conjugacy classes of the edge groups and vertex groups in the JSJ decomposition Λ of the factor B, it preserves the conjugacy classes of the edge groups and non-QH vertex groups in the cyclic decomposition Δ of B. Hence, if the original limit group is elementary equivalent to a non-abelian free group F, then there exists an homomorphism: μ : B → G that has non-trivial kernel, and for which each non-QH vertex group and each edge group in Δ is mapped to a conjugate in G.

We modify the endomorphism μ : B → B as follows. The image of the factor B, μ(B), inherits a free decomposition from the (Grushko’s) free decomposition of G, G = B_{1} ∗ … ∗ B_{s} ∗ F_{u}, μ(B) = D_{1} ∗ … ∗ D_{r} ∗ F_{ℓ}, where each of the factors D_{j} can be conjugated into one of the factors B_{j}, and the image of each non-QH vertex group and each edge group in Δ can be conjugated into one of the factors D_{j} that is contained in a conjugate of the factor B. Given the homomorphism μ, we define an endomorphism μ_{1} : B → B, by mapping each of the factors D_{j} that are subgroups of a conjugate of B, back into the factor B by a corresponding conjugation, and mapping the free factor F_{u}, and all the factors D_{j} that are subgroups of conjugates of factors other than B, into the identity. Since the homomorphism μ : B → G has non-trivial kernel, the endomorphism μ_{1} : B → B has non-trivial kernel, and since μ maps each non-QH vertex group and each edge group in Δ into a conjugate in G, μ_{1} maps each non-QH vertex group and each edge group in Δ into a conjugate in the factor B.

With each QH vertex group Q in Δ, we associate a (possibly trivial) maximal collection of s.c.c. that are mapped to the identity element by μ_{1}. Using the maximal collections of s.c.c. on the QH vertex groups in Δ we construct a graph of groups Δ̂ obtained from the graph of groups Δ by cutting the QH vertex groups along their associated collections of s.c.c. filling each of the s.c.c. that we cut along with disks, and erase those pieces that are not connected to any of the boundary components of the original QH vertex groups in the graph of groups Δ. We set B̂ to be the fundamental group of the graph of groups Δ̂. By construction there is a natural epimorphism: ν : B → B̂. We define a homomorphism τ : B̂ → B, by defining τ on each factor of B̂, associated with a connected component in the graph of groups Δ̂, to be the image under μ_{1} of a preimage of that factor in B. Note that since the collections of s.c.c. on each of the QH vertex groups in Δ are assumed to be maximal collections of disjoint non-homotopic s.c.c. that are mapped to the identity by μ_{1}, no non-trivial s.c.c. on a QH vertex group in Δ̂ is mapped by τ to the trivial element in B. We set the endomorphism μ_{2} : B → B to be μ_{2} = τ ∘ ν. Since the endomorphism μ_{1} : B → B has non-trivial kernel, the endomorphism μ_{2} : B → B has non-trivial kernel, and since μ_{1} maps each non-QH vertex group and each edge group in Δ into a conjugate in B, μ_{2} maps each non-QH vertex group and each edge group in Δ into a conjugate in the factor B.

The endomorphism μ_{2} maps each non-QH vertex group and each edge group in Δ into a conjugate in B. Since the endomorphism μ_{2} = τ ∘ μ, if the image of a QH vertex group Q in Δ, μ_{2}(Q), contains a finite index subgroup of a conjugate of a vertex group Q′ in Δ, then by lemma 1.4 of [Se4], the topological complexity of Q′, (|χ(Q′)|, genus(Q′)) is bounded by the topological complexity of Q, and if the topological complexities are equal, then Q is mapped by μ_{2} isomorphically onto Q′. If for every QH vertex group Q′ in Δ, the image of μ_{2} contains a conjugate of a finite index subgroup of Q′, then each QH subgroup Q in Δ is mapped by μ_{2} isomorphically onto a conjugate of a QH subgroup in Δ, and distinct QH subgroups in Δ are mapped onto conjugates of distinct QH vertex groups in Δ. In this case, μ_{2} maps the factor B onto itself, and since B is ω-residually free and ω-residually free groups are Hopf, μ_{2} being an epimorphism is also a monomorphism, a contradiction since μ_{2} was assumed to have non-trivial kernel.

Therefore, there must exist QH vertex groups in Δ, so that μ_{2}(B) does not contain any finite index subgroups of their conjugates. Let T_{1}, …, T_{f} be the fundamental groups of the connected components of the graph of groups obtained from Δ by erasing these QH vertex groups. By lemma 1.5 of [Se4], the subgroup generated by T_{1}, …, T_{f} in B, < T_{1}, …, T_{f} >= T_{1}∗…∗T_{f}. By lemma 1.5 of [Se4], μ_{2}(B) inherits a free decomposition from the graph of groups Δ, μ_{2}(B) = H_{1} ∗ … ∗ H_{v}, where each of the factors H_{j} in this free decomposition can be conjugated in B into one of the subgroups T_{i}. By composing the endomorphism μ_{2} : B → B, with a homomorphism that sends each of the factors H_{j} into its conjugate in the factor T_{i}, we get an endomorphism μ_{3} : B → B, where:

μ_{3}(B) < < T_{1}, …, T_{f} >= T_{1} ∗ … ∗ T_{f}.

Hence, the subgroup < T_{1}, …, T_{f} >= T_{1} ∗ … ∗ T_{f} is a proper retract of the factor B, obtained by mapping the ”erased” QH vertex group in Δ, into their image in < T_{1}, …, T_{f} > according to the endomorphism μ_{3}.

So far we have constructed a proper retract of the original limit group G, onto its proper subgroup. We now continue in the same way with this proper subgroup. We start with its (Grushko’s) free decomposition, and then look at all the factors that are not surface (or free) groups. Since G is elementary equivalent to a free group, the same construction applied for the factor B, proves that each such factor must admit a proper retract into a proper subgroup of itself. Since limit groups satisfy the ascending chain condition ([Se1],5.1), this construction of proper retracts terminates after finitely many steps, and the limit group G is indeed a hyperbolic ω-residually free tower.

□

Proposition 6 shows that a f.g. group that is elementary equivalent to a free group must be a non-elementary hyperbolic ω-residually free tower. The techniques used in our quantifier elimination procedure can be modified to prove the converse, hence, we finally obtain a classification of the f.g. groups that are elementary equivalent to a non-abelian f.g. free group.

Theorem 7. A f.g. group is elementary equivalent to a non-abelian f.g. free group if and only if it is a non-elementary hyperbolic ω-residually free tower.

Proof: Proposition 6 proves that a f.g. group that is elementary equivalent to a f.g. non-abelian free group must be a non-elementary hyperbolic ω-residually free tower. Hence, it is left to prove that if G is a non-elementary hyperbolic ω-residually free tower, then G is elementary equivalent to a f.g. non-abelian free group.

Let G be a non-elementary ω-residually free tower. With the structure of the ω-residually free tower associated with G, we can naturally associate a (coefficientfree) resolution Res_{G}(b) over a non-abelian free group. By construction, the resolution Res_{G}(b) is a complete resolution, and since G is assumed to be hyperbolic, the resolution Res_{G}(b) contains no non-cyclic abelian vertex groups. Let F be a f.g. non-abelian free group, and let Σ(y) = 1 be a (coefficient-free) system of equations. With the system Σ(y) = 1, interpreted as a system of equations over the free group F, we have associated a taut Makanin-Razborov diagram. With each resolution in this taut Makanin-Razborov diagram we have associated its completion. Let Comp(Res_{1})(z, y), …, Comp(Res_{d})(z, y) be the set of these completions.

Lemma 8. Let y′ be a solution of the system Σ(y) = 1, interpreted as a system of equations over the ω-residually free tower G. Then there exist elements z′ in G, so that the tuple (z′, y′) is a specialization of (at least) one of the completions Comp(Res_{1})(z, y), …, Comp(Res_{d})(z, y), i.e., it is the image of a homomorphism from the limit group associated with one of these completions into the group G.

Proof: We look at a test sequence of the (coefficient-free) resolution, Res_{G}(b), in the free group F. Let y′_{n} ∈ F be the sequence of specializations of the elements y′ ∈ G along the given test sequence. Since Σ(y′) = 1 in G, the sequence y′_{n} satisfies Σ(y′_{n} = 1 in F, for every index n. Hence, for every index n, there exist elements z′_{n} ∈ F, so that the tuple (z′_{n}, y′_{n}) is a specialization of one of the completions Comp(Res_{1})(z, y), …, Comp(Res_{d})(z, y). If for every n we choose the shortest such z′_{n}, then the techniques used for the construction of a formal solution ([Se2],1.17), prove that there exists a subsequence of tuples (z′_{n}, y′_{n}) that are all specializations of the same completion, Comp(Res_{i})(z, y), that converge into tuple (z′, y′) ∈ G, and the tuple (z′_{n}, y′_{n}) is a specialization of the completion Comp(Res_{i})(z, y).

□

Clearly, the same argument used to prove lemma 8 applies to specializations of graded and multi-graded systems of equations, and the completions of the corresponding taut graded and multi-graded taut Makanin-Razborov diagrams. Let Θ(y) = 1 be a coefficient-free system of equations, and let:

(∀y) (Θ(y) = 1) ∃x Σ(x, y) = 1 ∧ Ψ(x, y) ≠ 1

be a coefficient-free sentence. Suppose that the sentence is a truth sentence over the free group F. By theorem 1.17 of [Se2], with each resolution Res(y) in the taut Makanin-Razborov diagram associated with the system Θ(y) = 1, it is possible to associate a formal solution x = x(z, y) defined over the completion of that resolution, Comp(Res)(z, y), for which:

(i) Σ(x(z, y), y) = 1 in the limit group corresponding to the completion Comp(Res)(z, y). (ii) there exists a specialization (z_{0}, y_{0}) (in the free group F), of the completion

Comp(Res)(z, y), for which Ψ(x(z_{0}, y_{0}), y_{0}) ≠ 1. By lemma 8, if y′ is a solution of the system Θ(y) = 1 interpreted as a system

of equations over the ω-residually free tower G, then there exists elements z′ in G, so that the tuple (z′, y′) is a specialization of (at least) one of the completions Comp(Res_{1})(z, y), …, Comp(Res_{d})(z, y) of the resolutions in the taut Makanin-Razborov diagram associated with the system of equations Θ(y) = 1. Hence, there exists a formal solution x_{i}(z, y), for which: x_{i}(z′, y′) = 1. Clearly, the graded and multi-graded categories are completely analogous.

Proposition 9. Let:

∀y ∃x (Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1)

be a coefficient-free AE sentence. Then the AE sentence is a truth sentence over the f.g. non-abelian free group F if and only if it is a truth sentence over the nonelementary hyperbolic ω-residually free tower G. i.e., the AE theories of non-abelian free groups and non-elementary hyperbolic ω-residually free towers are equivalent.

Proof: Suppose that

∀y ∃x (Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1)

is a coefficient-free sentence. If the sentence is a truth sentence over a f.g. nonabelian free group F, then it is possible to apply the iterative procedure presented in [Se4], and associate iteratively with the sentence a (finite) sequence of (coefficientfree) anvils, developing resolutions and formal solutions defined over them, that prove the validity of the sentence over the free group F. By the arguments given above, the proof given by the sequence of (coefficient-free) anvils, developing resolutions, and formal solutions defined over them, is valid over the non-elementary hyperbolic ω-residually free tower G.

Suppose that the given sentence is false over the free group F. By applying the iterative procedure for validation of a sentence presented in [Se4], there exists a coefficient free resolution Res(z, y), so that there exists a test sequence of specializations of this resolution, for which for the corresponding specializations of the variables y, there is no specialization of the variables x (in the free group F) for which:

(Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1).

We want to show that the given (coefficient-free) sentence is false over the non-elementary hyperbolic ω-residually free tower G. G is, in particular, a nonelementary hyperbolic group, hence, the free group F admits a quasi-isometric embedding into G. Let F_{G} be the (quasi-isometric) image of that embedding in G. By our assumptions, the resolution Res(z, y) has a test sequence of specializations in the free group F, so that for the corresponding sequence of specializations of the variables y, there are no specializations of the variables x in F, for which:

(Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1).

The free group F is isomorphic to the subgroup F_{G} of G, hence, we can naturally interpret the given test sequence of specializations of the resolution Res(z, y) in F, as a test sequence of specializations of Res(z, y) in its isomorphic image F_{G}. Suppose that our given sentence is a truth sentence over the group G. Then for each specialization of the variables y from our given test sequence, there exists a specialization of the variables x in G for which:

(Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1)

where the equalities and inequalities are in the hyperbolic group G. Let X be the Cayley graph of the hyperbolic group G. For each specialization of the variables y from the given test sequence, we pick the specializations of the variables x in G, which are the shortest possible for which the above disjunction of conjunctions of equalities and inequalities hold. Since the Cayley graph X of G is δ-hyperbolic, we can extract a subsequence of specializations of the variables (x, z, y) from our given sequence, that converges in the Gromov-Hausdorff topology on metric spaces (after rescaling). Since the specializations z, y form a test sequence, and since the specializations of the variables x were taken to be the shortest possible, the subsequence of specializations (x, z, y) converges into a faithful action of a limit group of the form L =< x, z, y >= Cl(Res)(s, z, y) ∗ M on a real tree Y. In the limit group L:

(Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1)

hence, for the original test sequence of specializations of the resolution Res(z, y) in the free group F, it is possible to extract a subsequence, for which for the corresponding specializations of the variables y, there exist specializations of the variables x (in F), for which:

(Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1)

in the free group F, and we get a contradiction.

□

Proposition 9 proves that the AE theories of non-abelian free groups and nonelementary hyperbolic ω-residually free towers are equivalent. To prove the equivalence of the elementary theories of these groups, it remains to prove that for coefficient-free predicates the quantifier elimination procedure constructed in [Se5] for predicates defined over a free group, works for all non-elementary hyp. ωresidually free towers. The quantifier elimination procedure presented in [Se5] is composed from two parts, the procedure for the construction of the tree of stratified sets, and the sieve procedure. We start by showing that the procedure for the construction of stratified sets remains valid over the ω-residually free tower G.

The procedure for the construction of the tree of stratified sets analyzes the remaining set of y’s using multi-graded resolutions, and their associated developing resolutions, and then we associate with each developing resolution, its entire collection of formal solutions, which are encoded in the graded formal diagram. Since the predicates we consider are all coefficient-free, all the constructions along the procedure for the construction of the tree of stratified sets are coefficient-free as well. Lemma 8 proves that the set of the remaining y’s over the group G can be completed to specializations that factor through the completions of the multi-graded resolutions at each step of the procedure for the construction of the tree of stratified sets. We have also argued that if p_{0} is in the definable set of the given predicate, interpreted as a predicate over G, then with each ungraded resolution associated with the (graded) developing resolution and p_{0}, there exists a formal solution (over G) that satisfies the properties of theorem 1.17 of [Se2]. The ungraded resolution defined over G, can be approximated by a sequence of ungraded resolutions over the free group F. From the existence of a formal solution defined over the given ungraded resolution over F, it follows that all the approximating resolutions over F admit formal solutions that approximate the formal solution over G. Hence, the given formal solution defined over G, factors through the completion of at least one of the graded formal resolutions associated with the given developing resolution over the free group F.

The iterative procedure for validation of an AE sentence, shows that if an AE sentence over a free group F is a truth sentence, then it has a proof using a finite collection of formal solutions. By the proof of lemma 8, the same is true for sentences defined over G.

Let L(p, w) be a coefficient-free AE predicate. Let Q_{F} (w, p) be the set defined by L(p, w) over the free group F, and Q_{G}(p, w) be the set defined by L(p, w) over the hyp. ω-residually free tower G. The tree of stratified sets constructed over the free group F, shows that if (p_{0}, w_{0}) ∈ Q_{F} (p, w), then the sentence corresponding to the specialization (p_{0}, w_{0}) can be proved using a sequence of formal solutions according to one of the proof systems given by the tree of stratified sets over F.

The argument given above, shows that if (p_{0}, w_{0}) ∈ Q_{G}(p, w), then the sentence corresponding to the specialization (p_{0}, w_{0}) can be proved using a sequence of formal solutions according to one of the proof systems given by the same (coefficient-free) tree of stratified sets. Furthermore, if Rgd(x, p) (Sld(x, p)) is a (coefficient-free) rigid (solid) limit group, then the maximal rigid (families of strictly solid) specializations of Rgd(x, p) (Sld(x, p)) for a specialization of the defining parameter p is identical over the free group F and the ω-residually free tower F. Hence, the collection of proof systems associated with the tree of stratified sets is identical over F and over G, i.e., for the two sets Q_{F} (w, p) and Q_{G}(w, p).

If the tree of stratified sets over the free group F is coefficient-free, so is the collections of varieties and resolutions associated with the sieve procedure over F. The tree of stratified sets over F is coefficient-free and is also the tree of stratified sets defined over G. The collection of proof systems associated with the tree of stratified sets over F and over G are identical. Any valid P S statement over G can be approximated by a sequence of valid P S statements over F. Furthermore, any valid P S statement over G does not factor through any of the Non-Rigid, Non-Solid or Left P S resolutions constructed along the Sieve procedure, and if it factors through an extra P S resolution, it has to factor through either one of the collapse extra P S limit groups associated with it, or one of the formal collapse extra P S resolutions associated with it. Hence, any valid P S statement belongs to at least one of the T SP S(p) sets constructed along the sieve procedure (over the free group F). Therefore, the reduction of a coefficient-free predicate to a (coefficientfree) predicate in the Boolean algebra of AE sets, can be done uniformly for all non-elementary hyperbolic ω-residually free towers. Since the AE theories of these towers are equivalent by proposition 9, the elementary theories of non-elementary hyperbolic residually free towers are equivalent, which implies that they are all elementary equivalent to a non-abelian free group.

□

References

[Hr] E. Hrushovski, private communication.

[Kh-My] O. Kharlampovich and A. Myasnikov, Tarski’s problem about the elementary theory of free groups has a positive solution, ERA-AMS, 4 (1998), 101-108.

[Ri-Se] E. Rips and Z. Sela, Cyclic splittings of finitely presented groups and the canonical JSJ decomposition, Annals of Mathematics 146 (1997), 53-104.

[Sa] G. S. Sacerdote, Elementary properties of free groups, Transactions Amer. Math. Soc. 178 (1973), 127-138.

[Se1] Z. Sela, Diophantine geometry over groups I: Makanin-Razborov diagrams, preprint.

[Se2] , Diophantine geometry over groups II: Completions, closures and formal solutions, preprint.

[Se3] , Diophantine geometry over groups III: Rigid and solid solutions, preprint.

[Se4] , Diophantine geometry over groups IV: An iterative procedure for validation of a sentence, preprint.

[Se5] , Diophantine geometry over groups V: Quantifier elimination, preprint.