Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publisher's TeX code    *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you either view the HTML version or    *
%_ * retrieve the article in DVI, PostScript, or PDF format.                *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{9-DEC-1998,9-DEC-1998,9-DEC-1998,9-DEC-1998}
 
\documentclass{era-l}
%\documentstyle[12pt]{article}
%\textwidth 6.2 in
%\topmargin -0.5 in

\bibliographystyle{c:/pctex/texbib/plain}

%\newtheorem{ct}{\indent Connection}

%\newtheorem{thm}{\indent  Theorem}
%\newtheorem{df}{\indent  Definition}
%\newtheorem{prop}{\indent Proposition}
%\newtheorem{rk}{\indent Remark}
%\newtheorem{lm}{\indent Lemma}
%\newtheorem{prb}{\indent Problem}
%\newtheorem{con}{\indent Conjecture}
%\newtheorem{cy}{\indent Corollary}
%\newcommand{\beq}{\begin{equation}}
%\newcommand{\eeq}{\end{equation}}

\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lm}{Lemma}
\newtheorem{cy}{Corollary}

\theoremstyle{definition}
\newtheorem{df}{Definition}
\newtheorem{con}{Conjecture}

\theoremstyle{remark}
\newtheorem{rk}{Remark}



\begin{document}
\title[TARSKI'S PROBLEM]
{Tarski's problem about the elementary theory of free 
groups has a positive solution}

%    Information for first author
\author{Olga Kharlampovich}
%    Address of record for the research reported here
\address{Department of Mathematics and Statistics,
McGill University,
805 Sherbrooke St. West,
Montreal, QC, Canada  H3A 2K6}
\email{olga@Math.McGill.CA} 

\author{Alexei Myasnikov}
\address{Department of Mathematics,
City College,
Convent Ave. \& 138th St.,
New York, NY  10031}
\email{Alexei@rio.sci.ccny.cuny.edu}

%    General info
\subjclass{Primary 20E05, 20F10; Secondary 03B25, 03C68}


\issueinfo{4}{14}{}{1998}
\dateposted{December 14, 1998}
\pagespan{101}{108}
\PII{S 1079-6762(98)00047-X}
\def\copyrightyear{1998}
\copyrightinfo{1998}{American Mathematical Society}

%\date{October 13, 1997}
\date{May 25, 1998}

\commby{Efim Zelmanov}

%\dedicatory{}

\keywords{Free group, elementary theory, Tarski}

\begin{abstract}
We prove that 
the elementary theories of all  nonabelian 
free groups coincide and that 
the elementary theory of a free group is decidable.
These results answer two  old questions that were raised by A. Tarski around
1945.
\end{abstract}

\maketitle


The object of this announcement is to sketch proofs of the following two 
theorems.
\begin{thm}
The elementary theories of all  nonabelian 
free groups coincide.
\end{thm}
\begin{thm}
The elementary theory of a free group is decidable.
\end{thm}
These theorems answer two  old questions that were raised by A. Tarski around
1945. We recall that the {\em elementary theory $Th(G)$} of a group $G$ is 
the set of all first order sentences
in the language of group theory which are true in $G$.
Notice that in the language  of group theory
every sentence  is equivalent to a sentence  of the following type:
\begin{eqnarray}
\label{form}
 \Phi = \forall X_1\exists Y_1\dots \forall X_k\exists Y_k
\bigvee_{p=1}^{r} (\bigwedge_{i=1}^{s} u_{pi} (X_1,Y_1,\dots ,X_k, Y_k) = 1  \\
%$$ $$
\bigwedge_{j=1}^{t}v_{pj}(X_1,Y_1,\dots ,X_k,Y_k) \neq 1).\nonumber
\end{eqnarray}

A discussion of this problem can be found in several textbooks 
on model theory (see, for example, C. Chang and H. Keisler  \cite{CK} or 
Yu. Ershov  and E. Palutin \cite{EP}) as well as in several textbooks on group 
theory (see, for example,
R. Lyndon and P. Schupp \cite{LS}).

Our solution of Tarski's problem takes on the strongest possible, positive
form, namely: {\it the free group $F(a_1, \dots, a_n)$ 
freely generated by $a_1,\dots,a_n$ is an 
elementary subgroup of $F(a_1, \dots, a_n, \dots ,a_{n+p})$ 
for every $n \geq 2$ and $p \geq 0$}.
Moreover, we prove also that: {\it  the elementary theory $Th(F)$ of 
a free group $F$ even with constants from $F$ in the language is decidable. }

Observe, by comparison, that it is relatively easy to prove that  free 
abelian groups of finite rank are elementarily equivalent if and only if their 
ranks coincide. The same is true for free nilpotent groups of finite rank
and for free semigroups of finite rank. Notice also that the elementary theory 
of any free abelian group of finite rank is decidable  \cite{Sz}, but that
the  elementary theory of a free nilpotent nonabelian group of finite 
rank is undecidable \cite{Mal3}. Moreover, the elementary theory 
of a finitely generated free semigroup of rank at least two
is also undecidable \cite{Qu}.

During the last 50 
years Tarski's problem for free groups has proved to be, on the one hand, 
very challenging, and  on the other hand,
rather fruitful.  Here we mention just a few results from 
group theory which have been inspired by Tarski's problem.

Around 1959, R. Vaught asked whether the sentence
%$$
\[
\forall x \forall y \forall z(x^2y^2z^2= 1 \rightarrow xy = yx \  \& \ xz 
= zx \ \& \ yz
= zy )
\] %$$
holds  in all free groups. Shortly afterwards,  R. Lyndon proved that, 
for each solution $x,y, z$  of the quadratic equation 
$x^2y^2z^2 = 1$ in a free group, the elements
$x,y,z$  commute pairwise \cite{Ly0}. This little theorem  
launched the whole theory of  equations over free groups. 
The first general results in this area are due to  R. Lyndon \cite{Ly1},
A. Lorenc \cite{Lor} and K. Appel \cite{Appel}, where they  described 
the solution set of an arbitrary
equation of one variable over a free group.  In 1966 A. Mal'tsev described 
the
solution set of the equation $[x,y] = [a,b]$ over the free group 
$F(a,b)$. This has a nontrivial implication  for the elementary theory 
of  a free group of rank 2, namely that  the set of all (free) bases
of $F(a,b)$ can be defined by a first order formula in
 the language of group theory: {\it the elements $u,w \in F(a,b)$ form 
a basis in $F(a,b)$ if and only if they satisfy the following formula 
(with constants $a, b$):
%$$
\[
\exists z ([u,w] = z^{-1}[a,b]z \vee [u,w] = z^{-1}[b,a]z).
\] %$$
}
The focus of investigation subsequently turned to quadratic 
equations
over free groups, i.e., equations in which every variable occurs exactly 
twice (for example, Mal'tsev's equation above). In the 
papers of C. Edmund and L. Commerford
\cite{ComEd}, \cite{EC} and R. Grigorchuck and P. Kurchanov  
\cite{Gr}, \cite{GrK} the
solution sets of standard quadratic equations 
over arbitrary free group  were described. This finished off the quadratic
case, because it follows from the work of
A. Hoar, A. Karras and D. Solitar \cite{HKS1}, \cite{HKS2} that every quadratic 
equation is automorphically equivalent to a  standard  one.

In 1982 G. Makanin \cite{Mak82} proved the crucial result about the
algorithmic decidability of Diophantine problem over free groups. 
He proved that if  a given equation over a free group  $F$ has a solution 
in $F$,
then this equation has a solution of bounded length (and this bound can 
be
effectively computed from the equation itself). 
In his paper G. Makanin developed an extremely powerful
 technique to deal with equations over free groups (as 
well as over free semigroups). We will have  more to say
about this  later.  G. Makanin's work then made it possible for
A. Razborov to describe the solution
set of an arbitrary system of equations over $F$
 ~\cite{Razborov}, \cite{Razborov1}.


Shortly afterwards G. Makanin  \cite{Mak84} extended his results, proving that
the universal theory $Th_{\forall}(F)$
of $F$ is algorithmically decidable. Recall that given  a group $G$,
 the universal theory  $Th_{\forall}(G)$  
 consists of  all universal sentences that are true in $G$ 
(a  sentence is termed  universal  if it is  equivalent to one of the 
type (\ref{form}) in which  only universal quantifiers occur). 
Notice that any two finitely generated
nonabelian free groups have exactly the same universal 
theory; this follows readily from the fact that any two such groups 
are embeddable into each other and the fact that any universal sentence 
which is true in a group is also true in every subgroup of this group. 
Since the theory $Th(F)$ is complete (i.e., for every sentence either 
the sentence or its negation lies in $Th(F)$), it follows immediately 
that any two free nonabelian groups satisfy exactly the same boolean 
combinations of universal formulas. 


Now, denote by $Th_+(G)$ the positive theory of the group $G$, i.e., 
the set of all   positive sentences from $Th(G)$ 
(a  sentence is called positive  if it is equivalent 
to one of the type  (\ref{form}) that does  not contain inequalities).
In 1966 Yu. Merzlyakov   proved the remarkable theorem that any two  nonabelian 
free groups of finite rank have  the same positive theory  \cite{Merz}. 
Combining  results on the decidability of $Th_{\forall}(F)$ with the
above-mentioned  theorem, G. Makanin showed that the positive theory $Th_+(G)$ 
is decidable \cite{Mak84}.

Another part of the elementary theory which was shown to be the same for 
any two nonabelian free groups of finite rank consists of all  so-called 
$\forall \exists$-sentences or, sometimes, $\Pi_2$-sentences 
(a $\forall \exists $-sentence is a  sentence which  is equivalent to a 
sentence of the type 
$\forall X \exists Y \phi(X,Y)$, where formula $\phi$ does not 
contain quantifiers, and $X$ and $Y$ are arbitrary tuples of variables). 
The corresponding part of $Th(F)$ is denoted by $Th_{\forall \exists}(F)$. 
That result is due to G. Sacerdote \cite{Sac}. He used Merzlyakov's ideas and 
the  small cancellation technique in Van-Kampen diagrams for group 
presentations. Again, it follows from his theorem that free 
nonabelian groups of finite rank satisfy the same boolean combinations 
of $\forall \exists$-sentences.

So, two important pieces of Tarski's conjecture, 
$Th_+(F)$ and $Th_{\forall \exists}(F)$, have already been proved to be true.
In order to understand more of $Th(F)$ some new ingredients were needed.
The new tools in our investigation of $Th(F)$ are 
algebraic geometry over groups, the theory of exponential groups, 
a technique involving what is termed discrimination,  
an implicit function theorem  (over free groups) and a 
description of irreducible algebraic varieties (over free groups) 
in terms of trianglular quasi-quadratic systems. It is to these topics that
we need to turn now.


It was clear from the beginning that to deal with the Tarski problem 
one needed a precise description of solution sets of equations 
(and inequations) over free groups. In the classical case, algebraic 
geometry  has been shown to be very useful in dealing with polynomial 
equations over fields. An analog of algebraic geometry over groups has 
been developed by G.~Baumslag, A.~Myasnikov and V.~Remeslennikov in \cite{BMR}. 
It provides the necessary
topological machinery as well as a method for transcribing
 geometric notions into the language of pure group theory. Following 
\cite{BMR} and \cite{KMNull} 
we can use standard algebraic geometry notions such as algebraic sets, the
Zariski topology, Noetherian domains, irreducible   varieties, radicals and 
coordinate groups to organize an approach to finding a solution of
Tarski's problem.
Some of these ideas go back to R. Bryant \cite{Br}, V. Guba \cite{Gub}, 
B. Plotkin \cite{Pl}  and   E. Rips. 


Another  essential ingredient in our treatment of the
Tarski problem is  the theory of exponential groups. 
This area starts with results of  P.~Hall, A.~Mal'tsev, G.~Baumslag and
R.~Lyndon.  R. Lyndon was the first who recognized  the importance of 
exponential groups for solving equations over groups. He found that  the 
solution set of any equation with one variable over a free group $F$ can be 
obtained from finitely many ``parametric'' words by specializing their 
parameters into the ring of integers \cite{Ly1}. More precisely, a 
parametric word over $F$ with parametrs in the polynomial ring 
$Z[t_1, \dots, t_n]$ is a formal expression that can be obtained 
from a basis of $F$  by finitely many concatenations  and exponentiations by 
elements  from $Z[t_1, \dots, t_n]$. If one specializes 
the parameters $t_1, \dots, t_n$ into integers (i.e., one substitutes 
some particular integers in place  of the $t_i$'s), then this
 gives rise to a specialization of a given parametric word 
into an element of the group $F$. What  R. Lyndon proved is that for 
any equation with one variable (and, perhaps, constants from $F$) one 
can effectively find  a finite set of parametric words  with parameters 
from the ring $Z[t_1, \dots, t_n]$, such that any solution of this 
equation can be obtained by some specialization of one of these words. 
Later K. Appel refined this result, proving that the solution set 
of an equation in one variable over a free group can be parametrized 
by finitely many words of the type $fg^th$, where $f,g,h \in F$ and 
$t$ is a parameter (from $Z[t]$)   \cite{Appel}. This  led R. Lyndon to 
introduce the notion  of a group with parametric exponents in an 
associative unitary  ring  $A$. In particular, he described   and studied the 
  free exponential group $F^{ Z[t]}$ over 
the ring $Z[t]$. One of the crucial results of this study was that the 
group $F^{ Z[t]}$ is discriminated by $F$, i.e., for any 
finitely many nontrivial 
elements in  $F^{ Z[t]}$ there exists a homomorphism
 $\phi:F^{ Z[t]} \rightarrow F$, which is the identity
 on $F$, such that all the images under $\phi$ of the given 
elements are also nontrivial. In 1989 V. Remeslennikov established 
a surprising connection between residual properties of groups and 
their universal theories, namely, that a finitely generated group $H$ can 
be  discriminated by a nonabelian free group $F$  if and only if $H$ has 
exactly the same universal theory as $F$ \cite{R1}.
It follows then immediately from Lyndon's result that all finitely 
generated subgroups of $ F^{Z[t]}$ have the same universal theory 
as $F$. This emphasized once more the role of $ F^{Z[t]}$ in the 
investigation of $Th(F)$. 

 A modern treatment of exponential groups is contained in the paper by 
A. Myasnikov and V. Remeslennikov \cite{MyasExpo2}. In particular, they 
proved that the group $ F^{Z[t]}$ 
can be obtained starting from $F$ by an infinite chain of  HNN-extensions 
of a very specific type,  so-called extensions of centralizers. 
If $G$ is a group 
and $C$ is the centralizer of a nontrivial element in $G$, then the 
following HNN-extension:
%$$
\[
G(C,s) = \langle G, s \mid s^{-1} c s = c  \ \ (c \in C) \rangle
\] %$$
is called a {\it free  extension of the centralizer $C$ by $s$}. 
Thus, to construct 
$ F^{Z[t]}$ one needs to extend each centralizer sufficiently many 
times until every proper centralizer is isomorphic to a free abelian 
group of infinite rank (i.e., the additive group of $Z[t]$). This 
implies that any finitely generated subgroup of $ F^{Z[t]}$ is actually 
a   subgroup of a group which can be obtained from $F$  by finitely 
many extensions of centralizers, and  for such groups  one can apply the
techniques of H. Bass and J.-P. Serre to describe the structure of 
these subgroups.

In the same paper \cite{MyasExpo2} the authors put forward the
following conjecture: {\it a finitely generated group is discriminated  
by a nonabelian free group $F$ if and only if it is embeddable into  
$ F^{Z[t]}$}. A positive solution of this conjecture would provide
a description of finitely generated groups which are 
discriminated by $F$ as well as 
a description of all finitely generated groups which have the 
same universal theory as $F$. 


This conjecture was positively solved by O. Kharlampovich 
and A. Myasnikov in a series of two papers \cite{KMNull} and \cite{KMIrc}. 
Our present work is a continuation of these two papers
 and makes  use of the results and methods developed there. 
In the first of these papers we proved the following result:  
the coordinate group $F_{Rad(S)}$ of the algebraic set $V_F(S)$ defined 
by a quadratic equation $S = 1$ with coefficients in $F$ is embeddable 
into a group obtained from $F$ by finitely many extensions 
of centralizers (and hence is a subgroup of   $F^{Z[t]}$).
 This implies that the variety
$V_F(S)$ is irreducible in the Zariski topology over $F^n.$ Moreover, we 
completely described the radical $Rad(S)$. It turns out that 
the radical $Rad(S)$ coincides
(with a few special classes of exceptions) with the normal 
closure of $S$ in the group $F*F(X)$. 
This embedding theorem has its roots in G. Baumslag's
 paper \cite{GB1}, where he considered discrimination of  
surface groups, which are exactly (with few exceptions) the 
coordinate groups of the standard quadratic equations 
without coefficients. For quadratic equations with coefficients 
the embeddings are not easy to construct. We need to use a particular 
form of such embeddings in order to prove a so-called implicit function 
theorem over free groups, which we will discuss in due course. In 
the second paper \cite{KMIrc} we refined the Makanin--Razborov process 
to get much simpler descriptions of solution sets of arbitrary 
systems of equations with coefficients over free groups. To explain 
what this means,  we need the following definition. 
%\vspace{3in}

 Let $G$ be a group and let
$X_1,\dots ,X_m$ be disjoint tuples of variables. 
A system (with coefficients from $G$)
%$$
\[
S_1( X_1,\dots, X_m) \hspace{.5in} = 1\] %$$ 
%$$
\[\hspace{.25in} S_2( X_2,\dots, X_m) \hspace{.25in} = 1\] %$$
%$$
\[\hspace{.5in} \ddots\] %$$
%$$
\[\hspace{1in} S_m(X_m)\   = 1\] %$$
is said to be {\it triangular quasi-quadratic} if for every $i$ 
 the equation $S_i(X_i,\dots ,X_m)=1$ is quadratic in  the 
variables from $X_i$. 

Such a system is said to be {\it nondegenerate} if 
 the equation $S_i(X_i,\dots ,X_m)=1$ over the coordinate group 
%$$
\[G_{i+1} = G[X_{i+1},\dots X_{m}]/
Rad( S_{i+1}(X_{i+1}, \dots,X_m), \dots, S_m(X_m)), \ \ \  G_m = G\] %$$
(with elements from $X_i$ considered as variables 
and elements from $X_{i+1},\dots ,X_{m}$ as coefficients from $G_{i+1}$) 
 has a solution in $G_{i+1}$ for each $i$. 

Notice that to solve a nondegenerate triangular quasi-quadratic 
system over $G$ one needs to solve the last quadratic equation 
$S_m(X_m) = 1$ over $G$, then the previous one (which is again quadratic!) 
$S_{m-1}(X_{m-1},X_m) = 1$ over the coordinate group $G_{m-1}$,
 and continue the process going  up along the triangular system 
until the first equation $S_1( X_1,\dots, X_m)=1$ has been 
solved in the group $G_1$. Now, to get  
solutions of this system in the initial group $G$, 
one needs to specialize the solutions obtained into $G$ 
(in this case to specialize means to take an arbitrary homomorphism
 from $G_1$ into $G$ and apply it   to the obtained set of solutions 
in $G_1$). 
Now, the following crucial result from \cite{KMIrc} describes  
the solution set in $F$ of an arbitrary  system  $S(X) = 1$ 
with coefficients from $F$: for any such $S(X) = 1$ one can 
effectively find a finite family of nondegenerate triangular 
quasi-quadraitc systems $U_1(Y_1)= 1, \dots, U_n(Y_n)= 1$ 
(here $Y_i$'s are disjoint tuples of variables of, possibly, 
different length) and word mappings 
$p_1(Y_1), \dots, p_n(Y_n)$ such that 
%$$
\[
V_F(S) = p_1(V_F(U_1)) \cup \dots \cup p_n(V_F(U_n)).
\] %$$

The possibility of some weak form  of  such  description  of   solution sets  
was conjectured by
A. Razborov in \cite{Razborov2} and also by E. Rips. 
 
The  main technical result needed in this work is the  
following ``implicit function theorem''
for quadratic equations over $F$, which is interesting in its own right.

{\it Let 
%$$
\[S(x_1,\dots ,x_n,c_1,\dots ,c_k)=1\] %$$
be  a ``nonexceptional'' quadratic equation in variables 
$X = (x_1,\dots ,x_n)$  with constants
 $c_1,\dots,c_k$ in $F$ (roughly speaking, ``nonexeptional'' 
means that the radical of $S$  coincides with the normal 
closure of $S$ and $S$ is not an equation of one of few very specific types). 
Suppose now that for 
each solution of the equation $S(X) = 1$ some other equation 
%$$
\[T(x_1,\dots,x_n,y_1, \dots, y_m,c_1,\dots ,c_k)=1\] %$$ 
 has a solution in $F$; then $T(X,Y)=1$ has a solution 
$Y = (y_1,\dots ,y_m)$ in the
coordinate group $F_{Rad(S)}$ of the  equation $S(X)= 1$.} 

 This implies that locally (in terms of Zariski's topology), i.e., in the 
neighbourhood defined by  the equation $S(X) = 1$, the implicit functions 
$y_1,\dots ,y_m$ 
can be expressed as an explicit word in variables $x_1, \dots, x_n$ 
and constants from $F$, say $Y = P(X)$.  This result  allows one to 
eliminate a quantifier from the following formula:
%$$
\[ \Phi = \forall X \exists Y (S(X) = 1 \ \ \rightarrow \ \ T(X,Y) = 1).\] %$$
Indeed, the sentence $\Phi$ is equivalent in $F$ to the following one:
%$$
\[
\Psi = \forall X (S(X) = 1 \ \ \rightarrow \ \ T(X, P(X)) = 1).
\] %$$



The following theorem then holds.


\begin{thm}
Let $F = F(a_1, \dots, a_n, \dots, a_{n+p}), \ n \geq 2, p \geq 0 $,
be a free  group with a basis $a_1, \dots, a_{n+p}$. There exists an 
algorithm which,  given a first order sentence $\Psi$  in the language of
group theory with constants $a_1, \dots, a_n$, finds  a finite boolean 
combination $\Psi^*$ of universal sentences in the same language, 
such that $\Psi$ is true in $F$ if and only if $\Psi^*$ is true in $F$. 
Moreover, this boolean combination $\Psi^*$ does not depend on $p$.
\end{thm}


We are very thankful to V. Remeslennikov and 
E. Rips for numerous discussions. In 1991--1992 V. Remeslennikov 
suggested a new 
approach for
finding a system of axioms for the elementary theory $Th(F)$. 
In 1995, in several talks in New York and  Montreal,
 E. Rips  acquainted the authors with some  methods due to 
Yu. Merzlyakov and G. Makanin and also with  an interesting 
scheme for eliminating   quantifiers for arbitrary  formulas in 
free groups to obtain Diophantine formulas. We used a different approach, 
but it seems  
that the methods presented here might  help to carry out their projects.

We also would like to mention that in our research we made use of the software 
package ``Magnus'' developed at CCNY of CUNY (which can be found on
their home page at
http://zebra.sci.ccny.cuny.edu/web ). This software enabled us to solve some  
awkward equations over 
free groups and henceforth  to find particular embeddings of some groups 
into $F^{Z[t]}$.

%\bibliography{proj}

\begin{thebibliography}{10}

\bibitem{Appel}
K. I. Appel, {\it
One-variable equations in free groups},
Proc. Amer. Math. Soc. {\bf 19} (1968), 912--918. \MR{38:1149}

\bibitem{BMR}
G. Baumslag, A. Myasnikov, and V. Remeslennikov, {\it
Algebraic geometry over groups},
1996, submitted to Invent. Math., 1998.


\bibitem {GB1}  G. Baumslag,
{\it On generalised free products},
Math. Zeitschr. {\bf 78} (1962),  423--438. \MR{25:3980}

\bibitem{Br} R. Bryant,
{\it The verbal topology of a group},
Journal of Algebra {\bf 48} (1977), 340--346. \MR{56:12131}

\bibitem{CK}
C. C. Chang and H. J. Keisler,
{\it Model theory},
North-Holland, London and New York, 1973. \MR{53:12927}

\bibitem{EC}
L. P. Comerford jr. and C. C. Edmunds, {\it
Quadratic equations over free groups and free products},
Journal of Algebra {\bf 68} (1981), 276--297. \MR{82k:20060}

\bibitem{ComEd}
\bysame,
{\it Solutions of equations in free groups},
Walter de Gruyter, Berlin and New York, 1989. \MR{90a:20067}

\bibitem{EP}
Yu.~L. Ershov and E.~A. Palutin,
{\it Mathematical logic},
Walter de Gruyter, Berlin and New York, 1989. \MR{88i:03002}

\bibitem{GrK}
R.~I. Grigorchuk and P.~F. Kurchanov,
{\it Some questions of group theory connected with geometry},
Algebra, 7, Itogi Nauki i Tekhniki, VINITI AN SSSR, Moscow, 1989. (Russian)
\MR{92e:20002}
\bibitem{Gr}
\bysame, {\it On quadratic equations in free groups},
Contemp. Math., vol. 131 (1), pp. 159--171, Amer. Math. Soc., Providence, RI,
1992. \MR{94m:20074}
\bibitem  {Gub} 
V. Guba,
{\it Equivalence of infinite systems of equations in free groups and 
semigroups to  finite subsystems},
Mat. Zametki {\bf 40} (1986), 321--324. (Russian)
\MR{88d:20060}

\bibitem{HKS1}
A. Hoare, A. Karrass, and D. Solitar,
{\it Subgroups of finite index of Fuchsian groups},
Math. Z. {\bf 120} (1971), 289--298. \MR{44:2837}

\bibitem{HKS2}
\bysame, {\it Subgroups of infinite index of Fuchsian groups},
Math. Z. {\bf 125} (1972), 59--69. \MR{45:2029}

\bibitem{KMNull}
O. Kharlampovich and A. Myasnikov,
{\it Irreducible affine varieties over a free group. 1: Irreducibility of
  quadratic equations and Nullstellensatz},
J. of Algebra {\bf 200} (1998), 472--516. \CMP{98:09}

\bibitem{KMIrc}
\bysame, {\it Irreducible affine varieties over a free group. 2: Systems 
in triangular quasi-quadratic form and description of residually free groups},
 J. Algebra {\bf 200} (1998), 
517--570. \CMP{98:09}

\bibitem{Lor}
A. A. Lorenc,
{\it The solution of systems of equations in one unknown in free groups},
Dokl. Akad. Nauk SSSR {\bf 148} (1963), 262--266. (Russian) \MR{32:1285}
\bibitem{Ly0}
R. C. Lyndon,
{\it The equation $a^2b^2 = c^2$ in free groups},
Michigan Math. J. {\bf 6} (1959), 155--164. \MR{21:1999}

\bibitem{Ly1}
\bysame, {\it Equations in free groups},
Trans. Amer. Math. Soc. {\bf 96} (1960), 445--457. \MR{27:1488}

\bibitem{Ly2}
\bysame, {\it Groups with parametric exponents},
Trans. Amer. Math. Soc. {\bf 96} (1960), 518--533. \MR{27:1487}

\bibitem{Ly3}
\bysame, {\it Length functions in groups},
Math. Scand. {\bf 12} (1963), 209--234. \MR{29:1246}

\bibitem{Ly4}
\bysame, {\it Equations in groups},
Bol. Soc. Bras. Mat. {\bf 11} (1980), 79--102. \MR{82j:20070}

\bibitem{LS}
Roger~C. Lyndon and Paul~E. Schupp,
{\it Combinatorial group theory},
Springer, Berlin and New York, 1977. \MR{58:28182}

\bibitem{Mak84}
G. S. Makanin,
{\it Decidability of the universal and positive theories of a free group},
Izv. Akad. Nauk SSSR, Ser. Mat., {\bf 48(1)} (1985), 735--749; English
transl. in Math. USSR Izv. {\bf 25} (1985). \MR{86c:03009}

\bibitem{Mak82}
\bysame, {\it Equations in a free group}, 
Izv. Akad. Nauk SSSR, Ser. Mat., {\bf 46} (1982), 1199--1273; English 
transl. in Math. USSR Izv. {\bf 21} (1983). \MR{84m:20040}

\bibitem{Mal3}
A.~I. Mal'tsev,
{\it On some correspondence between rings and groups},
Mat. Sbornik {\bf 50} (1960), 257--266. (Russian)  \MR{22:9448}

\bibitem{Merz}
Yu.~I. Merzlyakov,
{\it Positive formulae on free groups},
Algebra i Logika {\bf 5(4)} (1966), 25--42. (Russian) \MR{36:5201}

\bibitem{MyasExpo2}
A.~G. Myasnikov and V.~N. Remeslennikov,
{\it Exponential groups 2: Extension of centralizers and tensor completion
  of csa-groups},
Interntional Journal of Algebra and Computation {\bf 6(6)} 
(1996), 687--711. \MR{97j:20039}

\bibitem{Pl} B. Plotkin, 
{\it Varieties of algebras and algebraic varieties. Categories of 
algebraic varieties},
Preprint, Hebrew University, Jerusalem, 1996.

\bibitem{Qu}
W. Quine,
{\it Concatenation as a basis for arithmetic},
J. of Symb. Logic {\bf 11} (1946), 105--114. \MR{8:307b}

\bibitem{Razborov1}
A. Razborov,
{\it On systems of equations in a free group},
Math. USSR Izvestiya {\bf 25(1)} (1985), 115--162. \MR{86c:20033}

\bibitem{Razborov}
\bysame,
{\it On systems of equations in a free group},
PhD Thesis, Steklov Math. Institute, Moscow, 1987.

\bibitem{Razborov2}
\bysame,
{\it On systems of equations in free groups},
Combinatorial and geometric group theory (Edinburgh, 1993),
pp. 269--283, Cambridge University Press, 1995. \MR{96c:20039}

\bibitem {R1} 
V. N. Remeslennikov, 
{\it $\exists$-free groups},
Siberian Math. J. {\bf 30} (1989), 998--1001. \MR{91f:03077}

\bibitem{Sac}
G. S. Sacerdote,
{\it Elementary properties of free groups},
Trans. of the AMS {\bf 178} (1973), 127--138. \MR{47:8686}

\bibitem{Sz}
W. Szmielew,
{\it Elementary properties of Abelian groups},
Fund. Math. {\bf 41} (1955), 203--271.
\MR{17:233e}

\bibitem{Stal}
J. R. Stallings,
{\it Finiteness properties of matrix representations},
Ann. Math. {\bf 124} (1986), 337--346. \MR{88b:20105}
\end{thebibliography}
\end{document}





\endinput

<\PRE>