\documentstyle[12pt]{article}
\textwidth=16cm
\textheight=24cm
\oddsidemargin=3cm
\topmargin=5mm


\title{Logical languages and axioms for groups with a length function 
       \footnote{Preprint N20 of IITAM SB RAS. - Omsk: OmSU, 1995. - 8 p.}}
\author{O.Kharlampovich, A.Myasnikov, V.Remeslennikov}
\date{}

\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{corollary}{Corollary}
\newtheorem{problem}{Problem}


\begin{document}

\maketitle

We study groups with a length function from logical point of view.
The most important subclasses of groups with a length function are
(finitely) axiomatizable as two-sorted models (see $\S 2$). We also
give a local description and the system of axioms in group signature
of groups with a length function (see $\S 3$).

\section{Preliminaries}

Let us remind the notion of a length function on a group.

Let $G$ be a group and $\Lambda$ be an ordered abelian group.
Then a function $l:G \longrightarrow \Lambda$ is called
{\it a length function} on the group $G$ with values in the group $\Lambda$
if the following conditions hold:

1) $ \forall x l(x) \geq 0, l(1)=0$;

2) $ \forall x l(x) = l(x^{-1})$;

3) $ \forall x \forall y \forall z (d(x,y)>d(x,z) \Longrightarrow
      d(x,y)=d(y,z)),$

      $\ \ \ where \ d(x,y)=\frac{1}{2} (l(x)+l(y)-l(x^{-1}y))$.


To define $d(z,y)$ correctly one can assume that $\Lambda$ is canonically
embedded in its divisible completion $\Lambda \otimes \bf{Q}$
(thus, in latter group every element is divisible by 2), which
is an ordered abelian group and the order extends the order on G. From
other hand one can formulate the axiom 3) using the function
$d_{0}(x,y) = 2d(x,y)$ instead of $d(x,y)$.

It is known \cite{A-B} that a group G acts on some $\Lambda$-tree iff there
is a length function
$l: G \longrightarrow \Lambda$ satisfying the additional axiom:

4) $\forall x \forall y d(x,y) \in \Lambda$

A length function $l: G \longrightarrow \Lambda$ uniquely (up to embedding
$\Lambda \longrightarrow \Lambda \otimes \bf{Q}$) induces a
length function $l_1 : G \longrightarrow \Lambda \otimes \bf{Q}$ which always
satisfies the axiom 4). Therefore, any group with a $\Lambda$-length
function acts on some $\Lambda \otimes \bf {Q}$-tree.



Moreover, the group $G$ acts freely on some $\Lambda$-tree if and only if
the length function $l:G \longrightarrow \Lambda$
satisfies the following axiom (if this is the case it is called
{\it free length function}):

5) $\forall x(x \neq 1 \longrightarrow l(x^2) \geq l(x)$

Originally, length functions arose from the canonical length function on
a free group, where $d(x,y)$ is exactly the length of the longest common
initial segment of $x$ and $y$.
Let us axiomitize the class of length functions with this property.

From now on we fix a free length function $l:G \longrightarrow \Lambda$.
For elements $x_1,\ldots , x_n \in G$ the notation
$x = x_1 \circ \ldots \circ x_n$
means that $x = x_1  \ldots  x_n$  and $l(x) = l(x_1) + \ldots + l(x_n)$.

\begin{definition}
The length function $l:G \longrightarrow \Lambda$ is called {\sf regular}
iff the following axiom holds:

6) $ \forall x \forall y \exists u \exists x_1 \exists y_1
     (x = u \circ x_1 \& y = u \circ y_1 \& l(u) = d(x,y).$

\end{definition}

Now we start to discuss the situation when each element of $G$ can be
decomposed into a product of further indecomposable elements (one can
keeps in mind a free group with some fixed base).

\begin{definition}
 An element $a \in G$ is called {\sf an atom} (with respect to the
length function  $l:G \longrightarrow \Lambda$)
if the following condition holds:

7) $ \forall x \forall y (a = x \circ y \longrightarrow  l(x) = 0 \vee
     l(y) = 0)$

\end{definition}

\begin{definition}
The length function $l:G \longrightarrow \Lambda$ into an Archimedian group
$\Lambda$ is called {\sf atomness} if it satisfies the following axiom:

8) $\forall x ( \bigvee_{i=1}^{\infty} \exists y_1 \ldots y_i
(x = y_1 \circ \ldots \circ y_i \& y_1, \ldots, y_i \ are \ atoms))$

\end{definition}

At last, we would like to consider the generalization of the notion of
atomness functions to the case of a non-Archimedian group $\Lambda$.
Suppose that an ordered abelian group $\Lambda$ has a main series of
convex subgroups
$$
0 = \Lambda_0 < \ldots < \Lambda_i < \ldots ,
$$
where $\Lambda_{i+1} \setminus \Lambda_i$, is Archimedian for any
$ i \in I$ and I is an well-ordered set.
The preimage $l^{-1} (\Lambda_i) = G_i$, is a subgroup
in $G$, so the  series in $\Lambda$ induces a series of subgroups
in $G$:
$$
1 \leq G_0 \leq \ldots \leq G_i \leq \ldots, \ i \in I
$$
Let us denote the restriction of $l$ on $\Lambda_i$ by $l_i$.
Then $l_i:G_i \longrightarrow \Lambda_i$  is a length function on $G_i$.
The order on $\Lambda_i$ induces an order on
$\overline{\Lambda}_i=\Lambda_{i+1} \setminus \Lambda_i$
it allows one to consider the induced length function
$\overline{l}_i:G_i \longrightarrow \overline{\Lambda}_i$.



\begin{definition}
A length function $l:G \longrightarrow \Lambda$  is called
{\sf step-like}  if for any $i \in I$ the length function
$\overline{l}_i:G_i \longrightarrow \overline{\Lambda}_i$ is atomness.
\end{definition}


\section{Logical languages for groups with a length function and
         exponential groups}


Let us next consider the class of groups with a length function from
model-theoretic point of view.  All definitions and results from model
theory we need are available in \cite{K-Ch}.

Let $l:G \longrightarrow \Lambda$ be a length function on a group $G$ with
values in an ordered abelian group $\Lambda$. From the pure algebraic point
of view this length function can be described as a two sorted model
$$
{\cal M} = < G, \Lambda, l>,
$$
where $G$ is a group with a group multiplication; $\Lambda$ is an
ordered abelian group with an addition $+$ and an order $<$;
$l:G \longrightarrow \Lambda$ is an unary operation defined on $G$. To
the model $< G, \Lambda, l >$ one can assign a two-sorted language (one
sort of variables for elements from $G$ and another sort for elements from
$\Lambda$ ) with the all mentioned above operations and predicates in the
language. Moreover, if one is going to consider step-like length functions
he has to introduce in the language an unary predicate $P_i(x)$ for
each nontrivial convex subgroup $\Lambda_i < \Lambda$. The described
language $\cal L$ is called {\sl language of groups with a length function}.

It is clear that axioms 1)-6) are formulas of the language $\cal L$,
therefore the classes ${\cal M}_l, {\cal M}_{fl}, {\cal M}_{rl}$
of all groups correspondingly with a length function, with a free length
function (axiom 5)) and with a regular length function are finitely
axiomatizable (as two-sorted models!) in the language $\cal L$. The
corresponding theories are denoted through $T_l,  T_{fl}, T_{rl}$.

In contrary, the atomness axiom 8) contains the infinite disjunction,
so to write it down one needs more powerfull languages (for example,
$\omega_1 \omega$ -languages), but it is out of the frame of this paper.
To investigate the notions like "atomness" in the language $\cal L$
we will use the notion of type from the model theory.

By definition {\sl n-type over a theory T} is a set $p$ of formulas
$\psi (x_1,\ldots, x_n)$ which is consistent with the theory T.
A semantical criteria for $p$ to be a type is the following:
for any finite set of formulas $\psi_1, \ldots, \psi_s$ from $p$ there
exists a model $\cal A$ of the theory $T$ (i.e. all sentences from $T$
are valid in $\cal A$) and elements $a_1, \ldots, a_n \in \cal A$ such that
$\psi_1 (a_1,\ldots, a_n), \ldots, \psi_s (a_1,\ldots, a_n)$
are valid in $\cal A$. Further the validity of $\psi_n (a_1,\ldots, a_n)$
in $\cal A$ is denoted by ${\cal A} \models \psi (\overline{a})$,
where $\overline{a}=(a_1,\ldots, a_n)$. There are two very important
methods to create new models in Model Theory: the realization of types
and the omitting




of types theorems. To {\sl realize an n-type p in a model} $\cal A$
one needs to find an $n$-tuple $\overline{a}$ of elements in $\cal A$
such that ${\cal A} \models \psi (\overline{a})$ for any $\psi \in p$.
{\sl A type $p$ is omitting in} ${\cal A}$ if there are no elements in
${\cal A}$ realizing this type.

The {\it Realization Types Theorem (RTT)} can be formulated as follows:
{\it for any set of types $p_i, i \in I$, over a theory $T$ there exists
a model ${\cal A}$ of $T$ such that every type $p_i$ can be realized in
${\cal A}$}.

To formulate the omitting types theorem we need some definitions. A type
$p$ is called {\sl principle} if there exists a formula $\psi$ which is
consistent with $T$ (so $\psi$ is valid in some model of $T$) such that
if $\psi$ is valid in a model ${\cal A}$ of $T$ on the tuple $\overline{a}$
then this tuple realizes the type $p$. Of course, any principal type can
not be omitted in a model of $T$.

The {\sl Omitting Types Theorem (OTT)} claimes that {\sl if a theory $T$
is countable than any countable set of non-principal types
$p_1, p_2, \ldots,$ can be omitted in some countable model of $T$.}

For any set of formulas $\phi_1, \phi_2, \ldots$ and any model $\cal A$
one has the following chain of equivalencies:
$$
{\cal A} \models \forall x ( \bigvee_{i=1}^{\infty} \phi_i )
\Longleftrightarrow {\cal A} \not \models \neg ( \forall x
( \bigvee_{i=1}^{\infty} \phi_i ) \Longleftrightarrow {\cal A} \not \models
\exists x ( \bigwedge_{i=1}^{\infty} \neg \phi_i (x) )
\Longleftrightarrow
$$
$$
{\cal A} \  omitts \ the \ set \ \{ \neg \phi_i (x) \mid i = 1,2, \ldots \}
$$

Let us return to the atomness axiom 8). It has exactly a form
$\forall x ( \bigvee_{i=1}^{\infty} \phi_i )$, where
$\phi_i =  \exists y_1 \ldots y_i (x = y_1 \circ \ldots \circ y_i \& y_1,
\ldots, y_i \ are \ atoms)$.
So the validity of axiom 8) in a model $\cal A$ means exactly that $\cal A$
omits the corresponding set
$p_{at} = \{ \neg \phi_i \mid i \in {\cal N} \}$.
Using logical equivalencies one can rewrite $p_{at}$ as follows
$$
p_{at} = \{ \forall y_1 \ldots y_i (y_1 \ldots y_i \ are \ atoms )
\longrightarrow (x \neq y_1 \circ \ldots \circ y_i) \}
$$

Every finite subset of $p_{at}$ can be realized in a nonabelian free group
with the standard length function, hence $p_{at}$ is a type over the theory
$T_{fl}$ of groups acting freely on $\Lambda$-trees.

The previous statement and RTT imply that the notion of atomness can not be
axiomatizable in the language $\cal L$. Indeed, let $< G, \Lambda, l >$ be
any group with atomness length function, $T = Th(< G, \Lambda, l >)$ is its
complete theory in the language $\cal L$. Due to RTT one can realize the
type $p_{at}$ in some model $< G_1, \Lambda_1, l_1 >$ of the theory $T$.
Hence, the latter model is elementary equivalent to $< G, \Lambda, l >$ but
$l$ is not atomness.

We summarize the obtained results in the following

\begin{proposition}

a) The classes ${\cal M}_l, \ {\cal M}_{fl}$ of groups with length function
and groups acting freely on trees are finitely universally axiomatazible
in the language $\cal L$;





b) The class ${\cal M}_{rl}$ of groups with regular length function is
finitely $\forall \exists$-axioma-tizable in the language $\cal L$;

c) The class of groups with atomness (or step-lil'e) length function is
not axiomatizable in $\cal L$.
\end{proposition}

Let us consider now the same classes of groups but in ordinary group language.
{\sl A group G is called a group-reduct of the two-sorted model}
$< G, \Lambda, l >$. Denote by $K_l,K_{fl},K_{rl}$
the corresponding reducts of the classes
${\cal M}_l,{\cal M}_{fl},{\cal M}_{rl}$. One needs to distinguish the
two-sorted models and their reducts, at least, when applying logic. For
example, classes of groups with a length function and groups acting on trees
are distinct as two-sorted models, but the classes of their reducts coincide.

\begin{proposition}
The classes $K_l,K_{fl}$ are universally axiomatizable in the group
language.
\end{proposition}

{\bf Proof}. Let ${\cal M} \in \{ {\cal M}_l,{\cal M}_{fl} \}$.
$K$ is a reduct of $\cal M$. To prove the proposition one needs
only to verify that the class $K$ is closed under ultraproducts and
taking subgroups ( see \cite{K-Ch}). If $G_i$ is a group-reduct of
${\cal M}_i =< G_i, \Lambda_i, l_i > \in K$, the ultruproduct $\tilde{G}$
of $G_i, \ i \in I$, is the group-reduct of the ultraproduct $\tilde{\cal M}$
of ${\cal M}_i, \ i \in I$. By proposition 1 $\tilde{G} \in K$. It is
obvious that a subgroup of a group from $K$ belongs to the $K$.

Now we will introduce a language of exponential groups. Let $A$ be an
arbitrary associative ring with identity and $G$ be a group. Fix an action
of the ring $A$ on $G$, i.e. a map $G \times A \longrightarrow G$.
The result of the action of $\alpha \in A$ on $g \in G$ is written as
$g^{\alpha}$. Consider the following axioms:

     1. $g^1=g, \ g^0=1, \ 1^{\alpha}=1  ;$

     2. $g^{\alpha + \beta} = g^{\alpha} \cdot g^{\beta}, \
         g^{\alpha \beta}= (g^{\alpha})^{\beta};$

     3. $(h^{-1} g h)^{\alpha}=h^{-1}g^{\alpha} h;$

     4. $[g,h]=1 \Longrightarrow (gh)^{\alpha}=g^{\alpha}h^{\alpha}.$



\begin{definition}
Groups with $A$-actions satisfying axioms 1) - 4) are called $A$ - groups.
\end{definition}


In particular,  an arbitrary group $G$ is a $\bf Z$-group ($g^n$  is  the
$n$-th power of $g$). Many groups
acting on $\bf R$-trees are {\it partial} $\bf R$-groups. By definition
(see \cite{M-R} for details) a group $G$ is a partial $A$-group iff
$g^{\alpha}$ is defined for some $g \in G,\  \alpha \in A$,
and axioms 1) - 4) hold




wherever the action is defined (this means, in particular, that if
one side of equalities 1) - 4) is defined, then so is the other side,
and they are equal to each other).

One can associate with an $A$-group $G$ a two-sorted model
${\cal N} = < G, A, f >$, where $G$ is a group, $A$ is a ring with a unit
and $f$ is an operation of the action of $A$ on $G$. The
corresponding two-sorted language will be denoted by $\cal E$.

Sometimes the group G can be equiped by a length function
$l: G \longrightarrow \Lambda$ and by an action
of some ring $A$. In this case we will consider three-sorted models
$$
{\cal G} = < G, \Lambda ,A ;l,f >
$$
and the corresponding three-sorted language $\cal LE$ which is in fact
the union of the languages $\cal L$ and $\cal E$.

For example, a free non-abelian group $F$ admits a free regular atomness
length function $l:  F \longrightarrow {\bf Z}^+$ and an action of the  ring
$\bf Z$. So $F$ can be considered as the model
$< F,Z^+,Z;l, f >$.

It is convenient to consider only algeraic structures which contains
only predicates (no operations). The general method to reduce any
algebraic structure $\cal A$ to the predicate type is to replace each
operation by its graph as a new predicate. The resulting algebraic
structure ${\cal A}^*$ is called {\it the relation model corresponding
to} $\cal A$. This approach allow one to consider naturally partial
operations on $A$ (i.e. corresponding predicates) and also
consider finite substructures of $A$. For example, the free group $F$
has only trivial finite subgroup, but in its relation model $F^*$
every finite subset constitute a finite submodel (in the group case
a finite submodel is a finite set of elements with the partial multiplication
which is inherited from the original group).

Let ${\cal F}({\cal A})$ be the set of all finite submodels of an
algebraic structure $\cal A$. The set ${\cal F}({\cal A})$
characterize the universal theory $Th_{\forall}({\cal A})$ of
$\cal A$ (i.e. the set of all $\forall$-sentences which are
valid in $\cal A$). Namely, it is easy to see that
$$
{\cal F}({\cal A}) = {\cal F}({\cal B}) \Longleftrightarrow
Th_{\forall}({\cal A}) = Th_{\forall}({\cal B})
$$
The coincidence of the universal theories of $\cal A$ and $\cal B$ will
be denoted by ${\cal A} \equiv_{\forall} \cal B$.
The condition ${\cal A} \not \equiv_{\forall} \cal B$ implies that there exists a
finite model $K \in {\cal F}({\cal A}) - {\cal F}({\cal B})$ (or
$K \in {\cal F}({\cal B}) - {\cal F}({\cal A})$) which is said to be
an obstacle for ${\cal A} \equiv_{\forall} \cal B$.




\section{A local  description and axioms of groups with a length
function}

Proposition 2 claims that the properties of a group $G$ to act on
a tree or to act freely on a tree are {\it local}, i. e. they can be
described by finite submodels of $G$.

\begin{proposition}
A group $G$ admits a length function (free length function) if each
submodel of $G$ admits a length function (free length function).
\end{proposition}

It is well-known that a non-abelian free group can be uniquelly
characterazied as a group which has an integral (i.e.with the values in
${\bf Z}^+$ free length function. The main goal of this section is to prove
that groups acting freely on $\Lambda$-trees locally have integral free
length functions and vice versa.

\begin{theorem}
A group $G$ has a free $\Lambda$-length function iff each finite
submodel of $G$ has a free length function with the values in
the ordered group ${\bf Z}^+$.
\end{theorem}

{\bf Proof}. Let $G$ be a group with a free length function
$l: G \longrightarrow \Lambda$ and $K$ a finite submodel
of $G$. Then $l(K)$ is a finite submodel of the ordered group $\Lambda$.
Any two ordered abelian groups are universally equivalent to one another
\cite{G-K}. So $\Lambda \equiv_{\forall} {\bf Z}^+$ and hence there
exists a submodel $K' \in {\bf Z}^+$ which is isomorphic to $l(K)$.
Therefore there exists a free length function
$l': K \longrightarrow  {\bf Z}^+$.

Now suppose that all finite submodels of a group $G$ have a free
length function. One can consider a theory $T = T_{fl} \cap D(G)$ in the
language $\cal L$, where $T_{fl}$ is the theory of groups with three
length functions and $D(G)$ is the diagram of $G$, i.e. the set of all
formulas of the type $g_i g_j = g_k$ or $g_i g_j \neq  g_k$ which are
true in $G$ (here we consider the elements $g_i, g_j, g_k \in G$ as
new constants in the language $\cal L$). The theory $T$ is consistent,
because every finite subset is valid in $G$. Therefore, by compactness
arguments (or by RTT) one can conclude that $T$ has some model, say $H$.
By our construction $H$ has some free length function and $G$ is a
subgroup of $H$, so is $G$. The theorem is proved.

\begin{remark}
It is not the case that if $G$ has a free length function then every finitely
generated subgroup of $G$ has an integral free length function.
\end{remark}

\begin{proposition}
There is an algorithm which for any finite submodel $K$ of a group
determines whether $K$ admits an integral free length function or not.
\end{proposition}





{\bf Proof}. It is enough to prove that there exists a recursive function
$f(n)$ such that if a finite model $K$ admits an integral free length
function then $K$ has a free length function
$l_0: K \longrightarrow {\bf Z}^+$ with the property
$l_0(x) \leq f(\mid K \mid)$ for any $x \in K$ (here and further $\mid K \mid$
is the number of elements in $K$ ). Indeed, there are only finitely many
integral functions on $K$ with the latter property and one can effectively
sort them out. Thus, it is enough to construct a recursive function $f(n)$
such that for any finite submodel $K$ of ${\bf Z}^+$ there exists an
isomorphic to it model $K'$ of ${\bf Z}^+$ such that
$\mid x \mid \leq f(n)$ for any $x \in K$, where $n=\mid K \mid$.

Since the universal theory of the ordered group $\bf Z$ is solvable
\cite{G-K} then it is possible to enumerate effectively all abstract
finite submodels of the theory of this model consisting of $n$ elements,
$n=1,2, \ldots$. It is possible also to enumerate effectively all finite
submodels of the group $\bf Z$ consisting of $n$ elements, $n=1,2 \ldots$.
Sorting out all concrete submodels consisting of $n$ elements and
determining their absract isomorphism type, one can evaluate effectively
a value of the function $f(n)$.

By more subtle reasonings it is possible to obtain the explicit form of
the function $f(n)$.

\begin{corollary}
There is an algorithm which for every finitely generated group $G$ with
decidable word problem stops on the input $(X, n)$, where $X$ is a set
of generators of $G$ and n is a code of the Turing machine which solves
the word problem with respect to $X$, if and only if the group $G$ does
not act freely on any tree.
\end{corollary}

\begin{problem}
Does there exist an algorithm which for any finitely generated group $G$
with decidable word problem determines whether $G$ acts freely on some
tree or not?
\end{problem}

As the another corollary of theorem 1 we will describe a set of axioms
(in the group-theoretical language !) of the class $K_{fl}$ of groups
acting freely on trees.

Let ${\cal F}(K_{fl})$ be a set of all finite group-theoretic models
which are submodels of groups from the class $K_{fl}$ and which are
pair-wise non-isomorphic to one another. The complement of the
${\cal F}(K_{fl})$ in the set of all finite group-theoretic models
(one from each type of isomorphism) is the set of obstacles for a group
to act freely on some tree. For each finite group-theoretic model $K$ one
can associate a group-theoretic formula $\phi_K$ on the variables
$\{x_1, x_2, \ldots , x_{\mid K \mid} \}$, which describes the diagramm
$D(K)$ (i.e. the table of multiplication of $K$ ). Then the sentence
$$
\forall x_1 \ldots x_{\mid K \mid} \neg \phi_K
$$
is valid in a group $G$ iff G has no a submodel isomorphic to $K$.
Hence a theory




$$
T_{{\cal K}_{fl}} = T_{group} \bigcup \{ \forall x_1 \ldots x_{\mid K \mid}
\neg \phi_K \mid K \not \in {\cal F}({\cal K}_{fl}) \}
$$

where $T_{group}$ is the theory of groups, describes groups without
obstacles to act freely on some tree, i.e. groups from the class $K_{fl}$.
So we have proved the following

\begin{proposition}
The set $T_{{\cal K}_{fl}}$ described above is the set of axioms for the
class ${\cal K}_{fl}$.
\end{proposition}

\begin{problem}
Is the set $T_{{\cal K}_{fl}}$ recursive ?
\end{problem}

\begin{problem}
Is the elementary group-theory of the class of all groups acting freely
one some tree decidable?
\end{problem}


\section{Universally-free groups}


In the previous section we described the tree-free groups as the groups
which locally have free integral length functions, so locally they are
very close to the free groups, but not entirely. The following notion
describes groups which locally coincide with free groups.

\begin{definition} \cite{R1}
A group $G$ is called {\sl universally-free} or {\sl existencially-free}
if ${\cal F}(G) = {\cal F}(F)$ for some (any) free non-abelian group $F$.
\end{definition}

The following remark explanes the name of these groups.

\begin{remark}
The conditions below are equivalent (see section 2):

1) A group $G$ is universally-free;

2) $G \equiv_{\forall} F$;

3) $G \equiv_{\forall} F$.
\end{remark}

From theorem 1 one can immeduately derive the

\begin{proposition}
Every universally-free group is a tree-free group.
\end{proposition}

However, not all tree-free groups are universally-free \cite{R2,G-S}.
The non-orien-table surface group of genus 3
$$
G=<x,y,z \mid x^2 y^2 z^2 =1>
$$
provides, probably, the most simple example of such type. Indeed, it
has a free length function with values in ${\bf Z} \times {\bf Z}$  but
it is not universally-free (see below).

Let us describe the universally-free groups inside the class of
tree-free groups.




\begin{proposition}
A tree-free group $G$ is universally-free iff every finitely generated
subgroup of $G$ is residually free.
\end{proposition}

By definition {\it a group $G$ is $n$-residually free} iff for any finite
set of elements $g_1, \ldots, g_n \in G$ there exists a homomorphism
$\phi : G \Longrightarrow F$ on a free non-abelian group $F$ such that
$\phi (g_i) \neq 1$ for any $i$ (such $\phi$ is called an
{\it approximation homomorphism} ). If $G$ is $n$-residually free for
all finite $n$ then it is called $\omega$-{\it residually free} or
{\it fully residually free}. In the case $n = 1$ $G$ is said to be
{\it residually free}. The following proposition clarifies
the links between all these notions.

\begin{proposition} \cite{R1}
A group $G$ is universally-free iff every finitely generated subgroup
of $G$ is $\omega$-residually free.
\end{proposition}

Now we are able to describe in the pure group-theoretic terms the difference
between the tree-free groups and universally-free groups.

\begin{proposition}
A tree-free group $G$ is universally-free iff $G$ is non-abelian and every
finitely generated subgroup of $G$ is residually free.
\end{proposition}

{\bf Proof}.
It is known \cite{R1} that a residually-free group $G$ is $\omega$-residually
free if and only if the commutation in $G$ is equivalent relation on the
set $G - \{1\}$. It  follows (see \cite{B}) that any tree-free group is
commutative transitive. Combining these two facts with the proposition above
one obtaines the statement.

The group $G =< x,y,z \mid x^2 y^2 z^2 = 1 >$ mentioned above is not
universally free, because it is not residually free. Really, one can not
approximate the element $[x, y]$ in a free non-abelian group $F$, because
in $F$ solutions of the equation $x^2 y^2 z^2 = 1$ pairwise
commute.


\begin{thebibliography}{99}

\bibitem{G-K}
{\em Гуревич Ю.Ш., Кокорин А.И. Универсальная эквивалентность
упорядоченных абелевых групп. Алгебра и логика, 1963, т.2, N1, 37-39}

\bibitem{K-Ch}
{\em Кейслер Г., Чэн Ч.Ч. Теория моделей. М.: Мир, 1977}

\bibitem{M-R}
{\em Мясников А.Г., Ремесленников В.Н. Степенные группы 1: Основы теории
и тензорные пополнения. Сибирский математический журнал, 1994, т.35, N5,
1106-1118}

\bibitem{R1}
{\em Ремесленников В.Н. $\exists$-свободные группы. Сибирский
математический журнал, 1989, т.30, N6, 193-197}

\bibitem{R2}
{\em Ремесленников В.Н. $\exists$-свободные группы как группы с
функцией длины. Украинский математический журнал, 1992, т.44, N6, 813-818}

\bibitem{A-B}
{\em Alperin R., Bass H. Length functions of groups actions on
$\Lambda$-trees. Combinatorial group theory and topology. Annals of Math.
Studies, 1987, No 111, 265-378}

\bibitem{B}
{\em Bass H. Groups acting on non-archimedean trees. Arboreal group theory,
1991, 69-130}

\bibitem{G-S}
{\em Gaglione A.M., Spellman D. Does Lyndon's length function imply
the universal theory of free groups?. Preprint}

\end{thebibliography}


\end{document}
