# A modified proof for Higman’s embedding theorem

V. H. Mikaelian

###### Abstract.

We suggest a modified and briefer version for the proof of Higman’s embedding
theorem stating that a finitely generated group can be embedded in a finitely
presented group if and only if it is recursively presented. In particular, we
shorten the main part of original proof establishing characterization of
recursive relations in terms of benign subgroups in free groups. Also, some
technical lemmas on homomorphisms in free constructions are replaced by simple
combinatorial observations on words of specific type.

###### Key words and phrases:

Recursive group, finitely presented group, embedding of group, benign
subgroup, free product of groups with amalgamated subgroup, HNN-extension of
group

###### 1991 Mathematics Subject Classification:

20E22, 20E10, 20K01, 20K25, 20D15.

“We do fundamental research, not only to acquire results solely,
but because the process is an ennobling one”
Graham Higman, 1987

##  1\. Introduction

Our aim is to suggest a shorter and we hope considerably simpler version of
the proof for Higman’s remarkable embedding theorem:

######  Theorem 1.1 (Theorem 1 in [11]).

A finitely generated group can be embedded in a finitely presented group if
and only if it is recursively presented.

Recursive presentation for a group $G$ presumes that there is a presentation
$G=\langle x_{1},\ldots,x_{n}\mathrel{|}r_{1},r_{2},\ldots\,\rangle$ such that
the set of defining relations $\\{r_{1},r_{2},\ldots\\}$ is recursive
enumerable, i.e., it is the range of some recursive function. This result
establishes deep connections between the logical notion of recursion and group
theory. For many of its applications we refer to Ch. 12 of [24], Ch. IV of
[12], Ch. I, IV, VI in [3], and to newer work of Ol’shanskii and Sapir [21].

###  1.1. The main steps of Higman’s proof

[11] starts by Kleene’s formal characterization of partial recursive functions
on the set of non-negative integers as the class of functions that can be
obtained from the zero, successor and identity functions using the operations
of composition, primitive recursion, and minimization (see [8, 23] or the
newer text [6]). Let ${\mathbb{Z}}$ be the set of all integers, and
$\mathcal{E}$ be the set of all functions $f:{\mathbb{Z}}\to{\mathbb{Z}}$ with
finite supports in the sense that $f(i)=0$ for all but finitely many integers
$i\in{\mathbb{Z}}$. To each such function $f\in{\mathcal{E}}$ one can
constructively assign a unique non-negative Gödel number. This makes
$\mathcal{E}$ an effectively enumerable set, and one may put into
correspondence to each subset ${\mathcal{B}}$ of ${\mathcal{E}}$ the
respective set of non-negative integers corresponding to the functions
$f\in{\mathcal{B}}$. Then ${\mathcal{B}}$ is recursively enumerable, if that
set is the range of a recursive function. Next, Section 2 in [11] gives a
different characterization for recursively enumerable subsets of
${\mathcal{E}}$: two initial subsets ${\mathcal{Z}}$ and ${\mathcal{S}}$ of
${\mathcal{E}}$, and a series of operations on subsets of ${\mathcal{E}}$ are
introduced (see (H) in 2.2 below), and Theorem 3 states that ${\mathcal{B}}$
is recursively enumerable if and only if it can be obtained from
${\mathcal{Z}}$ and ${\mathcal{S}}$ by operations (H). Only after these
preparations the group-theoretical argument starts in [11]. The key concept of
benign subgroup is introduced (see 3.1), and to each ${\mathcal{B}}$ a
specific subgroup $A_{\mathcal{B}}$ of the free group $G=\langle a,b,c\rangle$
of rank $3$ is put into correspondence. The main result of Section 3 and of
Section 4 in [11] is:

######  Theorem 1.2 (Theorem 4 in [11]).

The subset $\mathcal{B}$ of $\mathcal{E}$ is recursively enumerable if and
only if $A_{\mathcal{B}}$ is a benign subgroup in $G=\langle a,b,c\rangle$.

Then in final brief Section 5 the above theorem is generalized: a subgroup of
any finitely generated free group is recursively enumerable if and only if it
is benign. The “Higman Rope Trick”, as it is often called [9], closes the
proof by showing how a recursively presented group can be embedded in a
finitely presented group. Here we suggest a shorter proof for Theorem 1.2, and
our sections 3, 4 roughly correspond to sections 3, 4 in [11].

###  1.2. Comparison of the current modification with [11]

Leaving aside minor changes, here are the main modifications done to Higman’s
original construction.

We construct a very different group to show that the set of all subsets
$\mathcal{B}\subseteq{\mathcal{E}}$, for which the subgroup
$A_{\mathcal{B}}=\langle a_{f}\;|\;f\in\mathcal{B}\,\rangle$ is benign, is
closed under Higman operation $\omega_{m}$. In [11] this is done by the group
$M*_{\langle a,b,c\rangle}K$ built using Lemma 4.10, Lemma 3.9 and Lemma 3.10,
which perhaps form the most complicated part in [11]. Compare them with the
part “$\boldsymbol{\mathscr{S}}$ is closed under $\omega_{m}$” in Section 4
below.

Three lemmas 3.2–3.4 on homomorphisms are extensively used in [11] to study
subgroups in free constructions. We obtain similar results using simple
combinatorics on words, and trivial observations made in 2.6. Compare, for
instance, Lemma 3.8 and Lemma 3.9 of [11] with direct proofs in examples
listed in 3.2 below.

We accompany all concepts by examples, and give much more detailed proofs. In
particular, we do prove the part “These two conditions are easy, but a little
tedious, to check, and this is left to the reader” on p. 472 in [11], and we
do give a proof for Lemma 2.2 mentioned in [11] as “obvious from the normal
form theorem”. In fact, we could shorten the proofs even more by evolving some
of our wreath product methods [14]–[17]. However, we intentionally keep
technique within free products with amalgamations and HNN-extensions to
preserve Higman’s original idea of investigation of recursion via free
constructions.

###  1.3. Other proofs for Higman’s embedding theorem

Higman’s original proof is very complicated, and this motivated others to
suggest alternative proofs for Theorem 1.1. Lindon and Schupp present in
Section IV . 7 of [12] a proof related to Valiev’s approach [26]. Solving
Hilbert’s Tenth Problem [13] established that a subset of ${\mathbb{Z}}^{n}$
is recursively enumerable if and only if it is Diophantine. The proof in [12]
uses this Diophantine characterization, i.e., it relies on a “third party”
result (which itself has a complicated proof).

A proof reflecting Aanderaa’s work [1] is given by Rotman in Ch. 12 of [24].
It applies the auxiliary construction interpreting Turing machines via
semigroups, and also uses the Boone-Britton group [5, 7]. Group diagrams allow
[24] to shorten the proof of [1].

Besides the mentioned two well known textbooks, other proofs can be found in
the Appendix of Shoenfield’s textbook on logic [25], in the article of Adyan
and Durnev [2], etc. Typically, they relay on auxiliary constructions, such as
those built to show undecidability of the word problem in semigroups [22, 19]
and in groups [20, 5, 7].

This comparison stresses Higman’s more straightforward approach of “mimicking
recursion” by some elegant group-theoretical constructions. And a motivation
of our modification is to emphasize that Higman’s original idea still is one
of the clearest approaches to handle this subject.

### Acknowledgements

The current work is supported by the joint grant 18RF-109 of RFBR and SCS MES
RA, and by the 18T-1A306 grant of SCS MES RA. I would like to also thank my
both universities, YSU and AUA, for permanent and substantial support. The
work was announced at the International Algebraic Conference in memory of A.
G. Kurosh, May 23-25, 2018, Moscow.

##  2\. Notations and preliminary information

###  2.1. Sets of integer-valued funations

In 1.1 we introduced the set $\mathcal{E}$ of all functions
$f:{\mathbb{Z}}\to{\mathbb{Z}}$ with finite supports. If $f(i)=0$ for any
$i<0$ and $i\geq n$, we may record such a function as
$f=(a_{0},\ldots,a_{n-1})$ assuming $f(i)=a_{i}$ for $i=0,\ldots,n\\!-\\!1$.
Say, $f=(0,0,7,-8,5,5,5,5)$ means $f(2)=7$, $f(3)=-8$, $f(i)=5$ for
$i=4,\ldots,7$, and $f(i)=0$ for any $i<2$ or $i\geq 8$. Denote by $f=(0)$ the
constant zero function on ${\mathbb{Z}}$. For a fixed integer $m$ and for an
$f\in\mathcal{E}$ denote the functions $f_{m}^{+}$ and $f_{m}^{-}$ as follows.
$f_{m}^{+}(i)=f_{m}^{-}(i)=f(i)$ for all $i\\!\neq\\!m$, and
$f_{m}^{+}(m)=f(m)+1$, $f_{m}^{-}(j)=f(m)-1$. When $m$ is given by the
context, we may shorten these to $f_{m}^{+}=f^{+}$ and $f_{m}^{-}=f^{-}$. Say,
for the above $f$ we get $f_{5}^{+}\\!\\!=(0,0,7,-8,5,6,5,5)$, and
$f^{-}\\!\\!=(0,0,7,-8,5,5,5,4)$, provided $m=8$ is given.

###  2.2. The Higman operations on subsets of ${\mathcal{E}}$

Define some specific subsets of ${\mathcal{E}}$:

${\mathcal{Z}}\\!=\\!\big{\\{}(0)\big{\\}},\;\;{\mathcal{S}}\\!=\\!\big{\\{}(a,a+\\!1)\mathrel{|}a\\!\in\\!{\mathbb{Z}}\big{\\}},\;\;{\mathcal{E}}_{m}\\!\\!=\\!\big{\\{}(a_{0},\ldots,a_{m-1})\mathrel{|}a_{i}\\!\in\\!{\mathbb{Z}},\;i\\!=\\!0,\ldots,\\!m-1\big{\\}},\,m\\!=\\!0,\\!1,\ldots$

(${\mathcal{E}}_{0}$ consists of zero function only). We will use the
following operations from [11]:

(H)
$\iota,\;\upsilon;\quad\quad\rho,\;\sigma,\;\tau,\;\theta,\;\zeta,\;\pi,\;\omega_{m}\;\;(\text{for
each $m=1,2,\ldots$})$

which we call Higman operations. For any subsets $\mathcal{A},\mathcal{B}$ of
${\mathcal{E}}$ define
$\iota(\mathcal{A},\mathcal{B})=\mathcal{A}\cap\mathcal{B}$ and
$\upsilon(\mathcal{A},\mathcal{B})=\mathcal{A}\cup\mathcal{B}$. The rest of
Higman operations are unary functions on the subsets of $\mathcal{E}$:

$f\in\rho(\mathcal{A})$ iff there is a $g\in\mathcal{A}$ such that
$f(i)=-g(i)$,

$f\\!\in\\!\sigma(\mathcal{A})$ iff there is a $g\in\mathcal{A}$ such
that $f(i)=g(i-1)$,

$f\\!\in\tau(\mathcal{A})$ iff there is a $g\\!\in\\!\mathcal{A}$ such that
$f(0)\\!=\\!g(1)$, $f(1)\\!=\\!g(0)$ and $f(i)\\!=\\!g(i)$ for
$i\\!\neq\\!0,1$,

$f\in\theta(\mathcal{A})$ iff there is a $g\in\mathcal{A}$ such that
$f(i)=g(2i)$,

$f\in\zeta(\mathcal{A})$ iff there is a $g\in\mathcal{A}$ such that
$f(i)=g(i)$ for $i\neq 0$,

$f\in\pi(\mathcal{A})$ iff there is a $g\in\mathcal{A}$ such that $f(i)=g(i)$
for $i\leq 0$,

$f\in\omega_{m}(\mathcal{A})$ iff for every $i\in{\mathbb{Z}}$ there is a
$g=\big{(}f(mi),\;f(mi+1),\ldots,f(mi+m-1)\big{)}\in\mathcal{A}$. Since the
support of any $f\in{\mathcal{E}}$ is finite, either $\mathcal{A}$ contains
the zero function, or $\omega_{m}(\mathcal{A})=\emptyset$.

The more general operations $\alpha$ and $\lambda$ mentioned [11] are not used
here.

######  Example 2.1.

Some simple applications of Higman operations are easy to check:

$\rho({\mathcal{S}})=\big{\\{}f\in{\mathcal{E}}\mathrel{|}f(-1)=f(0)+1,f(i)=0\text{
for }i\neq-1,0\big{\\}}$.

Thus,
$\sigma\rho({\mathcal{S}})=\big{\\{}(a+\\!1,a)\mathrel{|}a\\!\in\\!{\mathbb{Z}}\big{\\}}=\tau({\mathcal{S}})$.

Since
$\zeta({\mathcal{Z}})=\big{\\{}(a)\mathrel{|}a\in{\mathbb{Z}}\big{\\}}=\big{\\{}(a,0)\mathrel{|}n\in{\mathbb{Z}}\big{\\}}$,
we have
$\iota\big{(}\\!\tau({\mathcal{S}}),\zeta({\mathcal{Z}})\big{)}=\big{\\{}(1,0)\big{\\}}=\big{\\{}(1)\big{\\}}$.

As
$\sigma\zeta({\mathcal{Z}})=\big{\\{}(0,a)\mathrel{|}a\in{\mathbb{Z}}\big{\\}}$,
we have
$\zeta(\sigma\zeta)^{2}({\mathcal{Z}})=\big{\\{}(a_{0},a_{1},a_{2})\mathrel{|}a_{0},a_{1},a_{2}\in{\mathbb{Z}}\big{\\}}={\mathcal{E}}_{3}$.

Since $\pi({\mathcal{Z}})=\\{f\in{\mathcal{E}}\mathrel{|}\ f(i)=0\text{ for
}i\leq 0\\}$, then
$\sigma^{3}\rho\pi({\mathcal{Z}})=\\{f\in{\mathcal{E}}\mathrel{|}\
f(i)=0\text{ for }i\geq 3\\}$.

Clearly, $\theta({\mathcal{E}}_{4})=\big{\\{}(a_{0},a_{2})\mathrel{|}\text{
for each
}(a_{0},a_{1},a_{2},a_{3})\in{\mathcal{E}}_{4}\big{\\}}={\mathcal{E}}_{2}$.

$\omega_{2}\big{(}\\!\upsilon({\mathcal{S}},{\mathcal{Z}})\big{)}=\\{f\in{\mathcal{E}}\mathrel{|}\
f(2i+1)=f(2i)+1\text{ \,or\,}f(2i+1)=f(2i)=0\text{ for any
}i\in{\mathbb{Z}}\\}$. Say,
$(7,8,\;0,0,\;2,3)\in\omega_{2}\big{(}\\!\upsilon({\mathcal{S}},{\mathcal{Z}})\big{)}$
because $(7,8),(2,3)\in{\mathcal{S}}$ and $(0,0)\in{\mathcal{Z}}$. Also,
$\omega_{2}({\mathcal{S}})=\emptyset$.

###  2.3. Notations for groups and homomorphisms

Below we may use the functions $f\in\mathcal{E}$ to define specific elements
in free groups. Here is a typical context: if $G=\langle a,b,c\rangle$ is a
free group of rank $3$, then the elements
$b_{i}=b^{c^{i}}=c_{i}^{-1}b\,c_{i}^{\vphantom{8}}$, $i\in{\mathbb{Z}}$, are
generating a free subgroup of countable rank in $G$. For every
$f\in{\mathcal{E}}$ we can define the element $b_{f}=\cdots
b_{-1}^{f(-1)}b_{0}^{f(0)}b_{1}^{f(1)}\cdots$ In particular, when
$f=(a_{0},\ldots,a_{m-1})\in\mathcal{E}$, we define $b_{f}=b_{0}^{f(0)}\cdots
b_{m-1}^{f(m-1)}$. The elements of type $a_{f}=a^{b_{f}}$ generate yet
another free subgroup in $G$.

If $G=\langle\,X\mathrel{|}R\,\rangle$ is the presentation of the group $G$ by
its generators $X$ and definning relations $R$, then for an alphabet $Y$
(disjoint from $X$) and for any set $S\subseteq F_{Y}$ of words on $Y$ we
denote $\langle G,Y\mathrel{|}S\,\rangle=\langle\,X\cup Y\mathrel{|}R\cup
S\,\rangle$ (the cases when $X=\emptyset$ or $S=\emptyset$ are not ruled out).

If $\varphi:G\to H$ is a homomorphism defined on any group $G=\langle
a,b,\ldots\rangle$ by the images $\varphi(a)=a^{\prime}$,
$\varphi(b)=b^{\prime},\ldots$ of its generators $a,b,\ldots$ , we may for
briefness refer to $\varphi$ as the homomorphism sending $a,b,\ldots$ to
$a^{\prime},b^{\prime},\ldots$

###  2.4. Notations for free constructions

We are going to extensively use the operations of free products of groups with
amalgamated subgroups and of HNN-extensions of groups by one or more stable
letters. Referring for background information to [12, 4, 24], here we just
state the notations we use.

If the groups $G$ and $H$ have subgroups, respectively, $A$ and $B$ isomorphic
under the isomorphism $\varphi:A\to B$, then we denote the (generalized) free
product $\Gamma=\langle G,H\mathrel{|}a=a^{\varphi}\text{ for all $a\in
A$}\,\rangle$ of $G$ and $H$ with amalgamated subgroups $A$ and $B$ by
$G*_{\varphi}\\!H$. In the simplest case, when $G$ and $H$ are overgroups of
the same subgroup $A$, and $\varphi$ is just the identical isomorphism on $A$,
we may prefer to write $\Gamma=G*_{A}H$.

If the group $G$ has subgroups $A$ and $B$ isomorphic under the isomorphism
$\varphi:A\to B$, then we denote the HNN-extension $\Gamma=\langle
G,t\mathrel{|}a^{t}=a^{\varphi}\text{ for all $a\in A$}\,\rangle$ of the base
$G$ by the stable letter $t$ with respect to the isomorphism $\varphi$ by
$G*_{\varphi}t$. In case when $A=B$ and $\varphi$ is identity on $A$, we may
write $\Gamma=G*_{A}t$. We also use HNN-extensions with more than one stable
letters. If we have the isomorphisms $\varphi_{1}:A_{1}\to
B_{1},\;\varphi_{2}:A_{2}\to B_{2},\ldots$ for pairs of subgroups in $G$, we
denote the respective HNN-extension $\langle
G,t_{1},t_{2},\ldots\mathrel{|}a_{1}^{t_{1}}=a_{1}^{\varphi_{1}}\\!\\!,\;a_{2}^{t_{2}}=a_{2}^{\varphi_{2}}\\!\\!,\,\ldots\;\text{
for all $a_{1}\in A_{1}$, $a_{2}\in A_{2},\ldots$}\,\rangle$ by
$G*_{\varphi_{1},\varphi_{2},\ldots}(t_{1},t_{2},\ldots)$. Our usage of the
normal forms in free constructions is closer to [4] (see the proof for Lemma
2.2 and examples in 3.2).

###  2.5. Subgroups in free constructions

Lemma 2.2 is a slight variation of Lemma 3.1 given in [11] without a proof111A
remark for the Editor and Referee. The proof of Lemma 2.2 is an application of
basic facts on the normal form in free product with amalgamation. Higman omits
the proof in [11]. If this proof is too basic, I can remove it here, too. On
the other hand, I can add the proof to Lemma 2.4, if needed.. Lemma 2.4 is
the analog of the latter for HNN-extensions.

######  Lemma 2.2.

Let $\Gamma=G*_{\varphi}\\!H$ be the free product of the groups $G$ and $H$
with amalgamated subgroups $A\leq G$ and $B\leq H$ with respect to the
isomorphism $\varphi:A\to B$. If $G^{\prime},H^{\prime}$ respectively are
subgroups of $G,H$, such that for $A^{\prime}=G^{\prime}\cap A$ and
$B^{\prime}=H^{\prime}\cap B$ we have $\varphi(A^{\prime})=B^{\prime}$, then
for the subgroup $\Gamma^{\prime}=\langle G^{\prime},H^{\prime}\rangle$ of
$\Gamma$ and for the restriction $\varphi^{\prime}$ of $\varphi$ on
$A^{\prime}$ we have:

  1. (1)

$\Gamma^{\prime}=G^{\prime}*_{\varphi^{\prime}}H^{\prime}$,

  2. (2)

$\Gamma^{\prime}\cap A=A^{\prime}$ and $\Gamma^{\prime}\cap B=B^{\prime}$,

  3. (3)

$\Gamma^{\prime}\cap G=G^{\prime}$ and $\Gamma^{\prime}\cap H=H^{\prime}$.

###### Proof.

By definition $\Gamma=(G*H)/N$ where $N$ is the normal closure of
$\\{\varphi(a)\,a^{\\!-1}\\!\mathrel{|}a\in A\\}$. Each element in
$\Gamma^{\prime}$ can be presented as $c=c_{0}\cdots c_{m-1}c_{m}$ with each
term $c_{i}$ picked from the factors $G^{\prime}$ or $H^{\prime}$ (the case
$m=0$ is not ruled out). By where necessary merging the factors, we may
suppose any two consecutive terms $c_{i},c_{i+1}$ are picked from different
factors. Fix a transversal $T_{A^{\prime}}$ to $A^{\prime}$ in $G^{\prime}$,
and a transversal $T_{B^{\prime}}$ to $B^{\prime}$ in $H^{\prime}$, and apply
to $c$ the “analog” of procedure of bringing to a normal form. Namely, If,
say, $c_{m}\\!\\!\in G^{\prime}$, write $c_{m}=u\,l_{n}$ where $u\in
A^{\prime}$ and $l_{n}\in T_{A^{\prime}}$ (ignore the value $n$ for now).
Since $c_{m-1}\\!\in H^{\prime}$, then $c_{m-1}\,u=c_{m-1}v\in H^{\prime}$ for
$v=\varphi(u)\in B^{\prime}$, and so $c_{m-1}v=w\,l_{n-1}$ where $w\in
B^{\prime}$ and $l_{n-1}\in T_{B^{\prime}}$. We already have the last two
terms for $c=c_{0}\cdots c_{m-2}\cdot w\,l_{n-1}l_{n}$. Continuing the process
we get:

(2.1) $c=l_{0}\,l_{1}\cdots l_{n-1}l_{n}$

where $n\leq m$, $l_{0}\in A^{\prime}$ or $l_{0}\in B^{\prime}$, and each of
terms $l_{1},\ldots,l_{n}$ is a non-trivial element from $T_{A^{\prime}}$ or
$T_{B^{\prime}}$ such that no two consecutive terms are from the same
transversal.

To prove point (1) it is enough to show that (2.1) is unique for any
$c\in\Gamma^{\prime}$ (unique normal forms are one of the ways to define free
products with amalgamations). Notice that if $l_{i},l_{j}$ from
$T_{A^{\prime}}$ are distinct modulo $A^{\prime}$, they also are distinct
modulo $A$ because $l_{i},l_{j}$ are in $G^{\prime}$, and so
$l_{i}^{\vphantom{8}}l_{j}^{-1}\\!\in A$ would imply
$l_{i}^{\vphantom{8}}l_{j}^{-1}\\!\in(G^{\prime}\cap A)=A^{\prime}$. So we can
choose a transversal $T_{A}$ to $A$ in $G$, containing $T_{A^{\prime}}$ as its
subset. Similarly, since if $l_{i},l_{j}$ from $T_{B^{\prime}}$ are distinct
modulo $B^{\prime}$, they also are distinct modulo $B$, and we can choose a
transversal $T_{B}$ to $B$ in $H$, containing $T_{B^{\prime}}$. Finally, we
may consider $l_{0}$ as an element from $A$ or $B$. Thus, (2.1) is nothing but
the normal form of $c$ in $\Gamma=G*_{\varphi}H$ written using $T_{A}$ and
$T_{B}$. Since it is unique, point 1 is proved.

Points (2), (3) now follow from point (1), and from uniqueness of the normal
form. ∎

######  Corollary 2.3.

If $\Gamma=G*_{A}H$, then in $\Gamma$:

  1. (1)

for any $G^{\prime}\\!\\!\leq\\!G$, $H^{\prime}\\!\leq\\!H$, such that
$G^{\prime}\cap\,A=H^{\prime}\cap\,A$ , we have $\langle
G^{\prime}\\!\\!,H^{\prime}\rangle=G^{\prime}\\!*_{G^{\prime}\cap\;A}H^{\prime}$,

  2. (2)

for any $G^{\prime}\\!\leq G$, $H^{\prime}\leq H$, both containing $A$ , we
have $\langle G^{\prime},H^{\prime}\rangle=G^{\prime}*_{A}H^{\prime}$.

######  Lemma 2.4.

Let $\Gamma=G*_{\varphi}t$ be the HNN-extension of the base group $G$ by the
stable letter $t$ with respect to the isomorphism $\varphi:A\to B$ of the
subgroups $A,B\leq G$. If $G^{\prime}$ is a subgroup of $G$ such that for
$A^{\prime}=G^{\prime}\cap\,A$ and $B^{\prime}=G^{\prime}\cap\,B$ we have
$\varphi(A^{\prime})=B^{\prime}$, then for the subgroup
$\Gamma^{\prime}=\langle G^{\prime},t\rangle$ of $\Gamma$ and for the
restriction $\varphi^{\prime}$ of $\varphi$ on $A^{\prime}$ we have:

  1. (1)

$\Gamma^{\prime}=G^{\prime}*_{\varphi^{\prime}}t$,

  2. (2)

$\Gamma^{\prime}\cap G=G^{\prime}$,

  3. (3)

$\Gamma^{\prime}\cap\,A=A^{\prime}$ and $\Gamma^{\prime}\cap B=B^{\prime}$.

The proof can be conducted in analogy with the proof of Lemma 2.2.

######  Corollary 2.5.

If $\Gamma=G*_{A}t$, then in $\Gamma$:

  1. (1)

for any subgroup $G^{\prime}$ of $G$ we have $\langle
G^{\prime},t\rangle=G^{\prime}*_{G^{\prime}\cap\;A}t$,

  2. (2)

for any subgroup $G^{\prime}$ of $G$ containing $A$ we have $\langle
G^{\prime},t\rangle=G^{\prime}*_{A}t$.

###  2.6. The “conjugates collecting” process

Let ${\mathfrak{X}}$ and ${\mathfrak{Y}}$ be any disjoint subsets in a group
$G$. It is easy to see that any element
$w\in\langle{\mathfrak{X}},{\mathfrak{Y}}\rangle$ can be written as:

(2.2) $w=u\cdot v=x_{1}^{\pm v_{1}}x_{2}^{\pm v_{2}}\cdots x_{k}^{\pm
v_{k}}\cdot v$

with some $v_{1},v_{2},\ldots,v_{k},\,v\in\langle{\mathfrak{Y}}\rangle$, and
$x_{1},x_{2},\ldots,x_{k}\in{\mathfrak{X}}$. Indeed, since $w$ is in
$\langle{\mathfrak{X}},{\mathfrak{Y}}\rangle$, present $w$ as a product of
elements from ${\mathfrak{X}}$, from ${\mathfrak{Y}}$ and of their inverses.
Then by grouping where necessary some elements from ${\mathfrak{Y}}$, and by
adding some trivial elements we can rewrite it as:

(2.3) $w=z_{1}^{\vphantom{8}}x_{1}^{\pm 1}z_{2}^{\vphantom{8}}\,x_{2}^{\pm
1}z_{3}^{\vphantom{8}}\cdots z_{k}^{\vphantom{8}}\,x_{k}^{\pm
1}z_{k+1}^{\vphantom{8}}$

where $x_{1},\ldots,x_{k}\in{\mathfrak{X}}$ and
$z_{1},\ldots,z_{k+1}\in\langle{\mathfrak{Y}}\rangle$. For instance, if
${\mathfrak{X}}=\\{x_{1},x_{2},x_{3}\\}$ and
${\mathfrak{Y}}=\\{y_{1},y_{2}\\}$, then
$w=x_{2}^{-1}y_{1}^{3}y_{2}^{\vphantom{8}}x_{1}^{2}x_{3}^{\vphantom{8}}$ can
be rewritten as
$w=z_{1}\,x_{2}^{-1}z_{2}^{\vphantom{8}}x_{1}z_{3}^{\vphantom{8}}x_{1}z_{4}^{\vphantom{8}}x_{3}^{\vphantom{8}}z_{5}^{\vphantom{8}}$,
where $z_{1}=1$, $z_{2}=y_{1}^{3}y_{2}^{\vphantom{8}}$, $z_{3}=z_{4}=z_{5}=1$
are in $\langle{\mathfrak{Y}}\rangle$. Next, (2.3) can be transformed to:

$w=z_{1}^{\vphantom{8}}x_{1}^{\pm
1}z_{1}^{-1}\\!\cdot\,z_{1}^{\vphantom{8}}z_{2}^{\vphantom{8}}\,x_{2}^{\pm
1}(z_{1}^{\vphantom{8}}z_{2}^{\vphantom{8}})^{-1}\\!\cdot\,z_{1}^{\vphantom{8}}z_{2}^{\vphantom{8}}z_{3}^{\vphantom{8}}\cdots(z_{1}^{\vphantom{8}}\\!\cdots
z_{k}^{\vphantom{8}})\,x_{k}^{\pm 1}(z_{1}^{\vphantom{8}}\\!\cdots
z_{k}^{\vphantom{8}})^{-1}z_{1}^{\vphantom{8}}\\!\cdots
z_{k}^{\vphantom{8}}z_{k+1}^{\vphantom{8}},$

which is (2.2) for $v_{1}^{\vphantom{8}}\\!=z_{1}^{-1}$,
$v_{2}^{\vphantom{8}}\\!=(z_{1}z_{2})^{-1}$,
$v_{3}^{\vphantom{8}}\\!=(z_{1}z_{2}z_{3})^{-1}$, $\ldots$
$v_{k}^{\vphantom{8}}\\!=(z_{1}\cdots z_{k})^{-1}$,
$v\\!=z_{1}^{\vphantom{8}}\\!\cdots\;z_{k}^{\vphantom{8}}z_{k+1}^{\vphantom{8}}$.

In particular, setting ${\mathfrak{X}}=\\{x\\}$ and ${\mathfrak{Y}}=\\{y\\}$
in a 2-generator group $G=\langle x,y\rangle$ we can present any element $w\in
G$ as a product of some conjugates of $x$ and of some power of $y$:

(2.4) $w=x^{\pm y^{n_{1}}}\\!x^{\pm y^{n_{2}}}\\!\\!\cdots\,x^{y^{\pm
n_{s}}}\\!\\!\cdot y^{k}=\\!u\cdot v\,.$

##  3\. The main properties and basic examples of benign subgroups

###  3.1. Definition and main properties of benign subgroups

The central group-theoretical notion used in [11] to construct embeddings into
finitely presented groups is the concept of benign subgroups. Higman gives
three equivalent definitions of which we use the first one:

######  Definition 3.1.

A subgroup $H$ of a finitely generated group $G$ is called a benign subgroup
in $G$, if $G$ can be embedded in a finitely presented group $K$ which has a
finitely generated subgroup $L$ such that $G\cap L=H$.

As a first evident example of a benign subgroup one may take any finitely
generated subgroup $H$ in any finitely presented group $G$. Then we just have
to choose $L\\!=\\!H$.

Let us illustrate benign subgroups by a construction giving some insight of
how a benign subgroup can help to embed a group with infinitely many relations
into a finitely presented group. Assume $A=\langle
a_{0},a_{1},\ldots,a_{n}\mathrel{|}\text{$\big{[}a_{0},\,h_{i}(a_{1},\ldots,a_{n})\big{]}=1$,\;
$i=1,2,\ldots$}\,\rangle$ is a group presentation with infinitely many
relations requiring that the frist generator $a_{0}$ commutes with some words
$h_{i}=h_{i}(a_{1},\ldots,a_{n})$ on the rest of generators. Suppose the
subgroup $H=\langle h_{i},\,i=1,2,\ldots\rangle$ is benign in the free group
$G=\langle a_{1},\ldots,a_{n}\rangle$, let $K$ be the finitely presented group
containing $G$, and let $L=\langle l_{1},\ldots,l_{t}\rangle\leq K$. Then
$\Gamma=K*_{L}t=\langle K,t\mathrel{|}\text{$l^{t}=l$ for each $l\in
L$}\rangle$ is finitely presented, since we should require $l^{t}=l$ for
$l_{1},\ldots,l_{t}$ only, and since $K$ demands finitely many relations. On
the other hand, by Corollary 2.5 (1) the subgroup $\Gamma^{\prime}=\langle
G,t\rangle$ of $\Gamma$ is equal to $G*_{G\cap L}t=G*_{H}t$. It remains to
rename $t$ by $a_{0}$ to see that $G*_{H}\\!t\,\cong\,A$.

It is interesting to compare Definition 3.1 with Theorem V (a variation of the
well-known theorem on embeddings of countable groups into 2-generator groups)
in earlier article [10].

The following properties have simple proofs covered in [11] by Lemma 3.6 and
Lemma 3.7:

######  Lemma 3.2.

Let $G$ be a finitely generated group with two benign subgroups
$H,\,H^{\prime}$. Then:

  1. (1)

$H\cap H^{\prime}$ is benign in $G$,

  2. (2)

$\langle H,H^{\prime}\rangle$ is benign in $G$.

######  Lemma 3.3.

Let $G,\,N$ be finitely generated groups both possessing embeddings into some
finitely presented groups, and let $\varphi:G\to N$ be any homomorphism. Then:

  1. (1)

if a subgroup $H$ is benign in $G$, then its image $\varphi(H)$ is benign in
$N$,

  2. (2)

if a subgroup $H$ is benign in $N$, then its (complete) pre-image
$\varphi^{-1}(H)$ is benign in $G$.

######  Remark 3.4.

It is trivial to verify by Definition 3.1 that the subgroup $H$ of a finitely
generated group $G$ is benign in $G$, provided that $H$ is benign in a
finitely generated group $G^{\prime}$ containing $G$. On the other hand, if we
additionally require that $G^{\prime}$ (and, therefore, also $G$) can be
embedded into a finitely presented group, then $H$ is benign in $G^{\prime}$,
provided that $H$ is benign in $G$. To see this just apply Lemma 3.3 (1) to
the identical embedding $G\to G^{\prime}$. Combining these facts, let us
following [11] agree to call $H$ benign (without specifying in which group
$G$), whenever there is a finitely presented overgroup containing the groups
discussed.

###  3.2. Examples of benign subgroups

Let us collect some examples for later use. We intentionally bring them in an
order displaying development of some basic ideas. Take the free group
$G=\langle a,b,c\rangle$, its subgroup $G_{0}=\langle b,c\rangle$, and denote
$b_{i}=b^{c^{i}}$ for $i\in{\mathbb{Z}}$ as in 2.3.

######  Example 3.5.

The subgroup $A_{0}=\langle b_{i}\mathrel{|}i\in{\mathbb{Z}}\,\rangle$ is
benign in $G_{0}$. Indeed, let $\varphi$ be the isomorphism of $G_{0}$ sending
$b,c$ to $b^{c}\\!,c$. Then $\Gamma\\!=\\!G_{0}\,\\!*_{\varphi}\\!t$ is
finitely presented, and it is enough to verify $G_{0}\cap\langle
b,t\rangle\\!=A_{0}$. Each $b_{i}\\!=b^{c^{i}}\\!\\!=b^{t^{i}}$ is in
$G_{0}\cap\langle b,t\rangle$. Next, applying 2.6 to any $w\in\langle
b,t\rangle$ for ${\mathfrak{X}}=\\{b\\}$ and ${\mathfrak{Y}}=\\{t\\}$, we get
$w=u\cdot v$ where $u$ is a product of factors of type $b^{\pm
t^{i}}\\!\\!=b_{i}^{\pm 1}$, and $v=t^{k}$. If also $w\in G_{0}$, then $v=1$
by uniqueness of the normal form, i.e., $w\in A_{0}$.

######  Example 3.6.

The subgroup $A_{k,l}=\langle
b_{n}\mathrel{|}n=ik+l,\;i\in{\mathbb{Z}}\,\rangle$ is benign in $G_{0}$ for
any $k,l=1,2,\ldots$ To see this just apply to $A_{\,0}$ the homomorphism
$\varphi$ sending $b,\,c$ to $b^{c^{l}}\\!\\!,\;c^{k}$. Since
$A_{k,l}=\varphi(A_{0})$, it remains to use Lemma 3.3 (1).

######  Example 3.7.

The subgroup $B_{0}=\langle b_{i}\mathrel{|}i\geq 0\rangle$ is benign in
$G_{0}$. Indeed, let $\varphi$ be the homomorphism sending $b,c$ to
$b^{c}\\!=b_{1},\;c^{2}$, and let $\psi$ be the homomorphism sending $b,c$ to
$b,\,c^{2}$. Denoting $A=G_{0}$, $B=\langle b_{1},c^{2}\rangle$, $C=G_{0}$,
$D=\langle b,c^{2}\rangle$ we have $B=\varphi(A)$ and $D=\psi(C)$. Then
$\Gamma=G_{0}*_{\varphi,\psi}(t,s)$ is finitely presented, and since $\langle
B_{0},t,s\rangle=\langle b_{1},t,s\rangle$, it will be enough to show
$G_{0}\cap\langle B_{0},t,s\rangle=B_{0}$. One side is evident, so we verify
$G_{0}\cap\langle B_{0},t,s\rangle\leq B_{0}$.

Collect some information on a transversal to $B$ in $G_{0}$. For
$F^{\prime}\\!=\\!\langle b_{i}\mathrel{|}\text{$i$ is odd}\rangle$ and
$F^{\prime\prime}=\langle b_{i}\mathrel{|}\text{$i$ is even}\rangle$ we
clearly have $F^{\prime}*F^{\prime\prime}=A_{0}$. Applying 2.6 for
${\mathfrak{X}}=\\{b\\}$ and ${\mathfrak{Y}}=\\{c\\}$, we can write each
element $g\in G_{0}$ as $g=b^{\pm c^{n_{1}}}\\!\\!\cdots\,b^{\pm
c^{n_{s}}}c^{k}\;=\;b^{\pm 1}_{n_{1}}\cdots\,b^{\pm 1}_{n_{s}}\,c^{k}$ for
some $n_{1},\ldots,n_{s},\,k\in{\mathbb{Z}}$. And $g$ is in $A_{0}$ if and
only if $c^{k}=1$. Moreover, $g$ is in $F^{\prime}$ if and only if all the
$n_{1},\ldots,n_{s}$ are odd. Applying this on $g=w^{-1}w^{\prime}$ with any
$w,w^{\prime}\in A_{0}$, we see that $w^{-1}w^{\prime}\in B=\langle
F^{\prime},c^{2}\rangle$ if and only if $w^{-1}w^{\prime}\in F^{\prime}$,
i.e., $F^{\prime}w=F^{\prime}w^{\prime}$. Thus, any transversal
$T_{F^{\prime}}$ to $F^{\prime}$ in $A_{0}$ can be continued to a transversal
$T_{B}$ to $B$ in whole $G_{0}$. Since $A_{0}$ is free, $T_{F^{\prime}}$ is
easy to describe as follows. Write:

(3.1) $w=b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{r-1}}^{\varepsilon_{r-1}}\cdot b_{n_{r}}^{\varepsilon_{r}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}\in A_{0}$

where $n_{r}$ is the first even index, and all $n_{1},\ldots,n_{r-1}$ are odd.
Then $b_{n_{1}}^{\varepsilon_{1}}\\!\cdots b_{n_{r-1}}^{\varepsilon_{r-1}}\in
F^{\prime}\leq B$ and $b_{n_{r}}^{\varepsilon_{r}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}\in T_{F^{\prime}}\subseteq T_{B}$. If, in
addition, $w$ is from $B_{0}$, then all indices $n_{1},\ldots,n_{s}$ are non-
negative.

Similarly, any transversal $T_{F^{\prime\prime}}$ to $F^{\prime\prime}$ in
$A_{0}$ can be continued to a transversal $T_{D}$ to $D$ in whole $G_{0}$. Any
element from $B_{0}$ can be written similarly to (3.1) such that $n_{r}$ is
the first odd index, all $n_{1},\ldots,n_{r-1}$ are even, and all
$n_{1},\ldots,n_{s}$ are non-negative. Then
$b_{n_{1}}^{\varepsilon_{1}}\\!\cdots b_{n_{r-1}}^{\varepsilon_{r-1}}\in
F^{\prime\prime}\leq D$ and $b_{n_{r}}^{\varepsilon_{r}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}\in T_{F^{\prime\prime}}\subseteq T_{D}$. Finally,
set trivial transversals $T_{A}=T_{C}=\\{1\\}$ because $A=C=G_{0}$.

Each $x\in\langle B_{0},t,s\rangle$ is a product of some elements $w\in
B_{0}$, and of some $t^{\pm 1}$, $s^{\pm 1}$. Above preparations show how
to reduce $x$ to its normal form in $\Gamma$. Scanning $x$ from right to left:

replace in $x$ a subword of type $t^{-1}w$ by
$t^{-1}b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}\,t\cdot
t^{-1}=b_{2n_{1}+1}^{\varepsilon_{1}}\\!\cdots
b_{2n_{s}+1}^{\varepsilon_{s}}t^{-1}$,

replace a subword of type $s^{-1}w$ by
$s^{-1}b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}\,s\cdot
s^{-1}=b_{2n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{2n_{s}}^{\varepsilon_{s}}s^{-1}$,

replace a subword of type $tw$ by $t\,b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{r-1}}^{\varepsilon_{r-1}}\,\,t^{-1}\cdot\,t\;b_{n_{r}}^{\varepsilon_{r}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}=\varphi^{-1}(b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{r-1}}^{\varepsilon_{r-1}})$ $\cdot
t\;b_{n_{r}}^{\varepsilon_{r}}\\!\cdots b_{n_{s}}^{\varepsilon_{s}}$
$=b_{(n_{1}-1)/2}^{\varepsilon_{1}}\\!\cdots
b_{(n_{r-1}-1)/2}^{\varepsilon_{r-1}}\cdot
b_{n_{r}}^{\varepsilon_{r}}\\!\cdots b_{n_{s}}^{\varepsilon_{s}}$, which is
doable, as $n_{1},\ldots,n_{r-1}$ are odd,

replace a subword of type $sw$ by $s\,b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{r-1}}^{\varepsilon_{r-1}}\,\,s^{-1}\cdot\,s\;b_{n_{r}}^{\varepsilon_{r}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}=\psi^{-1}(b_{n_{1}}^{\varepsilon_{1}}\\!\cdots
b_{n_{r-1}}^{\varepsilon_{r-1}})$ $\cdot
s\;b_{n_{r}}^{\varepsilon_{r}}\\!\cdots b_{n_{s}}^{\varepsilon_{s}}$
$=b_{n_{1}/2}^{\varepsilon_{1}}\\!\cdots
b_{n_{r-1}/2}^{\varepsilon_{r-1}}\cdot b_{n_{r}}^{\varepsilon_{r}}\\!\cdots
b_{n_{s}}^{\varepsilon_{s}}$, which is doable, as $n_{1},\ldots,n_{r-1}$ are
even this time.

Applying these four actions to $x$, we never get a new
$b_{i}^{\varepsilon_{i}}$ with negative $i$, i.e., the normal form of $x$
consists of some factors $b_{i}^{\varepsilon_{i}}$ with non-negative $i$, and
of some $t^{\pm 1}$, $s^{\pm 1}\\!\\!$. If, moreover, $x$ is in $G_{0}$,
then by uniqueness of the normal form we rule out such $t^{\pm 1}$, $s^{\pm
1}\\!\\!$, and get $g\in B_{0}$.

######  Example 3.8.

The subgroup $B_{k,l}=\langle b_{i}\mathrel{|}i<k\text{ or }i\geq l\rangle$ is
benign in $G_{0}$ for any fixed integers $k\leq l$. Let $\mu(x)=x^{c}$ be an
inner automorphism on $G_{0}$. Since $\mu^{j}(b_{i})=b_{i}^{c^{j}}=b_{i+j}$,
it is clear that $\mu^{j}(B_{0})=\langle b_{i}\mathrel{|}i\geq j\rangle$. In
particular, for $j=l$ the subgroup $\mu^{l}(B_{0})=\langle
b_{i}\mathrel{|}i\geq l\rangle$ is benign in $G_{0}$ by previous example and
by repeated application of Lemma 3.3 (1). $G_{0}$ has a homomorphism $\chi$
sending $b,c$ to $b,c^{-1}$. The image $\chi(B_{0})=\langle
b_{i}\mathrel{|}i\leq 0\rangle$ and the image
$\mu^{k-1}\big{(}\chi(B_{0})\big{)}=\langle b_{i}\mathrel{|}i\leq k-1\rangle$
both are benign in $G_{0}$. Since $B_{k,l}$ is a free group, we have
$B_{k,l}=\big{\langle}\mu^{l}(B_{0}),\;\mu^{k-1}\big{(}\chi(B_{0})\big{)}\big{\rangle}$,
and this subgroup also is benign by Lemma 3.2 (2).

To put some more generators into the game setup the free group $G^{*}=\langle
a,b,c,g,h,k\rangle$. In analogy to $b_{i}$ and $b_{f}$ introduce
$h_{i}=h^{k^{i}}$ for $i\in{\mathbb{Z}}$ and $h_{f}=h_{0}^{f(0)}\cdots
h_{m-1}^{f(m-1)}$ along with $g_{f}=g^{h_{f}}$ for $f\in{\mathcal{E}}_{m}$.
Using the elements $a,b_{i},g,h_{i}$ we can choose new free subgroups of
$G^{*}$, such as $G_{1}\\!=\\!\langle g,\,h_{0},\ldots,h_{m-1}\rangle$. Below
we are going to construct some benign subgroups inside such subgroups. To make
discussion simpler, we treat a group of type $G_{1}$ as a free group on
generators $g,\,h_{0},\ldots,h_{m-1}$, “forgetting” the fact that $h_{i}$ is
the conjugate $h^{k^{i}}$ for some $k$. In such groups we still can use the
notations like $b_{i}$, $b_{f}$, $a_{f}$, $h_{i}$, $h_{f}$, $g_{f}$. The
reason of this manner of notations is to make the main proof in Section 4
clearer.

######  Example 3.9.

The subgroup $G_{{\mathcal{E}}_{m}}\\!=\langle
g_{f}\mathrel{|}f\in{\mathcal{E}}_{m}\rangle$ is benign in
$G_{1}\\!=\\!\langle g,\,h_{0},\ldots,h_{m-1}\rangle$. Indeed, for each
$r=0,\ldots,m-1$ there is an isomorphism $\varphi_{r}$ on $G_{1}$ sending
$g,\,h_{0},\ldots,h_{r-1},h_{r},\ldots,h_{m-1}$ to
$g^{h_{r}}\\!,\,h_{0}^{h_{r}}\\!,\ldots,h_{r-1}^{h_{r}},h_{r},\ldots,h_{m-1}$.
Then
$\Gamma=G_{1}*_{\varphi_{0},\ldots,\varphi_{m-1}}\\!(t_{0},\ldots,t_{m-1})$ is
finitely presented. The action $g_{f}^{t_{r}^{\pm 1}}\\!\\!=g_{f_{r}^{\pm}}$
in $\Gamma$ is trivial to verify. Say, for $f=(2,5,3)$ and $r=1$ we have:

$\big{(}g^{h_{0}^{2}\,h_{1}^{5}\,h_{2}^{3}}\big{)}^{t_{1}}\\!\\!=\big{(}h_{2}^{-3}h_{1}^{-5}h_{0}^{-2}\big{)}^{t_{1}}\\!g^{t_{1}}\,\big{(}h_{0}^{2}\,h_{1}^{5}\,h_{2}^{3}\big{)}^{t_{1}}\\!\\!=h_{2}^{-3}h_{1}^{-5}\big{(}h_{0}^{-2}\big{)}^{h_{1}}g^{h_{1}}\,\big{(}h_{0}^{2}\big{)}^{h_{1}}h_{1}^{5}h_{2}^{3}=g^{h_{0}^{2}\,h_{1}^{5+1}\,h_{2}^{3}}\\!\\!=g^{h_{f_{1}^{+}}}\
$

with $f_{1}^{+}\\!\\!=\\!(2,6,3)$. Thus, $L=\langle
g,\,t_{0},\ldots,t_{m-1}\rangle$ contains the elements
$g_{f}=g^{t_{0}^{f(0)}\cdots\,t_{m-1}^{f(m-1)}}$ for all
$f\in{\mathcal{E}}_{m}$. On the other hand, applying 2.6 to any word $w\in L$
for ${\mathfrak{X}}=\\{g\\}$ and ${\mathfrak{Y}}=\\{t_{0},\ldots,t_{m-1}\\}$
we rewrite it as $w=u\cdot v$, where $u$ is a product of some conjugates of
$g$ by some words in $t_{i}$ (and they are equal to some $g_{f}$ as we just
saw), while $v$ is another word in $t_{i}$. If $w$ also is in $G_{1}$, then
$v=1$ by uniqueness of the normal form, and so $G_{1}\cap L\subseteq
G_{{\mathcal{E}}_{m}}$.

######  Example 3.10.

If $v_{f}=g_{f^{+}}\,b^{-1}_{m-1}g_{f}^{-1}$, then the subgroup
$V_{{\mathcal{E}}_{m}}\\!\\!=\langle
v_{f}\mathrel{|}f\in{\mathcal{E}}_{m}\rangle$ is benign in
$G_{2}\\!=\\!\langle b_{m-1},\,g,\,h_{0},\ldots,h_{m-1}\rangle$. Let
$\varphi_{r}$ be the isomorphism on $G_{2}$ fixing $b_{m-1}$, and with same
effect on other generators as in previous example.
$\Delta\\!=\\!G_{2}*_{\varphi_{0},\ldots,\varphi_{m-1}}\\!(t_{0},\ldots,t_{m-1})$
is finitely presented. The equality $v_{f}^{t_{r}^{\pm
1}}\\!\\!=v_{f_{r}^{\pm}}^{\vphantom{1}}$ is trivial to verify in $\Delta$.
Say, for $f=(2,5,3)$ and $r=1$:

$v_{f}^{t_{1}}=\\!\big{(}g^{h_{0}^{2}\,h_{1}^{5}\,h_{2}^{3+1}}\big{)}^{t_{1}}(b_{m-1}^{-1})^{t_{1}}\big{(}g^{-\,h_{0}^{2}\,h_{1}^{5}\,h_{2}^{3}}\big{)}^{t_{1}}=g^{h_{0}^{2}\,h_{1}^{5+1}\,h_{2}^{3+1}}b_{m-1}^{-1}g^{-b_{0}^{2}\,h_{1}^{5+1}\,h_{2}^{3}}=v_{f_{1}^{+}}\,.$

If $v_{(0)}\\!=g^{h_{m-1}}\,b_{m-1}^{-1}g^{-1}$, then the above shows that
$L=\langle v_{(0)},\,t_{0}\ldots,t_{m-1}\rangle$ contains
$v_{f}\\!=\\!v_{(0)}^{t_{0}^{f(0)}\cdots\,t_{m-1}^{\,f(m-1)}}$ for all
$f\in{\mathcal{E}}_{m}$. On the other hand, applying 2.6 to $w\in L$ for
${\mathfrak{X}}\\!=\\!\\{v_{(0)}\\}$ and
${\mathfrak{Y}}\\!=\\!\\{t_{0},\ldots,t_{m-1}\\}$ we like in previous example
get $G_{2}\cap L\subseteq V_{{\mathcal{E}}_{m}}$. I.e.,
$V_{{\mathcal{E}}_{m}}$ is benign.

######  Example 3.11.

If $z_{f}=g_{f}^{\vphantom{8}}b_{f}^{-1}$, then the subgroup
$Z_{{\mathcal{E}}_{m}}=\langle\,z_{f}\\!\mathrel{|}f\in{\mathcal{E}}_{m}\rangle$
is benign in $G_{3}=\langle
b_{0},\ldots,b_{m-1},\,g,\,h_{0},\ldots,h_{m-1}\rangle$. First verify that
$\langle
Z_{{\mathcal{E}}_{m-1}},V_{{\mathcal{E}}_{m}}\rangle=Z_{{\mathcal{E}}_{m}}$.
We have $V_{{\mathcal{E}}_{m}}\\!\leq Z_{{\mathcal{E}}_{m}}$ because
$v_{f}=g_{f^{+}}\,b_{m-1}^{-1}\,g_{f}^{-1}=g_{f^{+}}^{\vphantom{8}}\,b_{f^{+}}^{-1}\cdot
b_{f}^{\vphantom{8}}g_{f}^{-1}=z_{f^{+}}^{\vphantom{8}}\\!\\!\cdot
z_{f}^{-1}\in Z_{{\mathcal{E}}_{m}}$. And since also
$Z_{{\mathcal{E}}_{m-1}}\\!\leq Z_{{\mathcal{E}}_{m}}$, we have $\langle
Z_{{\mathcal{E}}_{m-1}},V_{{\mathcal{E}}_{m-1}}\rangle\leq
Z_{{\mathcal{E}}_{m}}$. Next, show by induction on $f(m-1)$ that
$z_{f}\in\langle Z_{{\mathcal{E}}_{m-1}},V_{{\mathcal{E}}_{m}}\rangle$. When
$f(m-1)=0$, then $z_{f}\in Z_{{\mathcal{E}}_{m-1}}$. And, since then
$f^{+}(m-1)=1$, we from $v_{f}^{\vphantom{+}}=z_{f^{+}}^{\vphantom{+}}\\!\cdot
z_{f}^{-1}\in V_{{\mathcal{E}}_{m}}$ get $z_{f^{+}}\in\langle
Z_{{\mathcal{E}}_{m-1}},V_{{\mathcal{E}}_{m}}\rangle$. Say, for $f=(2,5,0)$ we
have $Z_{{\mathcal{E}}_{3-1}}\\!\ni
v_{(2,5,0)}=z_{(2,5,0+1)}^{\vphantom{+}}\cdot z_{(2,5,0)}^{-1}$, and so
$z_{(2,5,0+1)}\in\langle
Z_{{\mathcal{E}}_{3-1}},V_{{\mathcal{E}}_{3}}\rangle$. The cases with
$f(m\\!-\\!1)=1,2,\ldots$ are covered similarly. Symmetric arguments cover the
case with negative $f(m\\!-\\!1)$. Since $Z_{{\mathcal{E}}_{m}}=\langle
Z_{{\mathcal{E}}_{m\\!-\\!1}},V_{{\mathcal{E}}_{m}}\rangle$, the fact that
$Z_{{\mathcal{E}}_{m}}$ is benign follows by induction:
$Z_{{\mathcal{E}}_{0}}=\langle
g_{(0)}^{\vphantom{8}}b_{(0)}^{-1}\rangle=\langle g\rangle$ is benign, as it
is finitely generated. If $Z_{{\mathcal{E}}_{m\\!-\\!1}}$ is benign, then
$Z_{{\mathcal{E}}_{m}}=\langle
Z_{{\mathcal{E}}_{m\\!-\\!1}},V_{{\mathcal{E}}_{m}}\rangle$ is benign by Lemma
3.2 (2) and by previous example.

##  4\. The modified proof of Theorem 1.2

Denote by $\boldsymbol{\mathscr{S}}$ the set of all subsets
${\mathcal{B}}\subseteq{\mathcal{E}}$ for which $A_{{\mathcal{B}}}=\langle
a_{f}\;|\;f\in{\mathcal{B}}\,\rangle$ is benign in $G=\langle a,b,c\rangle$.
First show that ${\mathcal{Z}},{\mathcal{S}}\in\boldsymbol{\mathscr{S}}$, and
then verify that if a subset ${\mathcal{B}}$ is obtained from ${\mathcal{Z}}$
and/or ${\mathcal{S}}$ by Higman operations (H), then ${\mathcal{B}}$ also is
in $\boldsymbol{\mathscr{S}}$. This proves Theorem 1.2 as by Theorem 3 in [11]
every recursively enumerable subset ${\mathcal{B}}\subseteq\mathcal{E}$ can be
obtained that way.

The free group $B\\!=\\!\langle
a,b_{i}\mathrel{|}i\\!\in\\!{\mathbb{Z}}\rangle$ is a product $B_{0}*B_{1}$
for $B_{0}\\!=\\!\langle b_{i}\mathrel{|}i\geq 0\rangle$ and $B_{1}=\langle
a,b_{i}\mathrel{|}i<0\rangle.$ Of these $B_{0}$ is benign by Example 3.7, and
$B_{1}$ is benign by Lemma 3.3 and by Lemma 3.2 (2) because
$B_{1}=\big{\langle}\mu^{-1}\big{(}\chi(B_{0})\big{)},a\big{\rangle}$, where
$\mu,\chi$ are those used in Example 3.8. So there are finitely presented
groups $K_{0}$ and $K_{1}$ which contain $G$, and which have finitely
generated subgroups, respectively, $L_{0}$ and $L_{1}$ such that $G\cap
L_{0}=B_{0}$ and $G\cap L_{1}=B_{1}$. Then both HNN-extensions
$\Lambda_{0}=K_{0}*_{L_{0}}\\!t$ and $\Lambda_{1}=K_{1}*_{L_{1}}\\!s$ are
finitely presented.

Amalgamating $G$ in $\Lambda_{0}$ and $\Lambda_{1}$ we get the finitely
presented group $\Theta\\!=\\!\Lambda_{0}*_{G}\Lambda_{1}$ in which the
subgroups $G^{t}$ and $G^{s}$ intersect trivially, since $G^{t}\\!\cap
G^{s}\,\leq\,(G^{t}\\!\cap G)\,\cap\,(G^{s}\\!\cap
G)\,\leq\,B_{0}\,\cap\,B_{1}=\\{1\\}.$ So in $\Theta$ we have $\langle
G^{t},G^{s}\rangle=G^{t}*\,G^{s}$ and, thus, $\langle
B_{0}^{t},B_{1}^{s}\rangle=B_{0}^{t}*B_{1}^{s}\cong B_{0}*B_{1}=B$. Therefore,
the identical automorphism on $G^{t}$ and the automorphism given by
conjugation by $b^{s}$ on $G^{s}$ possess a common extension $\omega$ on
$\langle G^{t},G^{s}\rangle$. The respective HNN-extension
$\Psi=\Theta*_{\omega}\\!d$ is finitely presented as $\omega$ can be defined
by its values on just six generators
$a^{t}\\!\\!,b^{t}\\!\\!,c^{t}\\!\\!,\;a^{\,s}\\!\\!,b^{s}\\!\\!,c^{s}$ of
$G^{t}*G^{s}$. For the generators of $B$ we in $\Psi$ clearly have:

(4.1) $b_{i}^{d}=b_{i}$ for $i\geq 0$, $a^{d}=a^{b}$, $b_{i}^{d}=b_{i}^{b}$
for $i<0$.

Next, take $\delta$ to be the automorphism on $G$ which sends $a,b,c$ to
$a,b^{c}\\!\\!,\,c$. Then $\Delta=\Psi*_{\delta}e$ is finitely presented. In
$\Delta$ denote $d_{i}=d^{e^{i}}$ for $i\in{\mathbb{Z}}$. From (4.1), from the
action of $e$ on $a,b,c$ and from
$b_{i}^{e^{j}}=(c^{-i})^{e^{j}}b^{e^{j}}(c^{i})^{e^{j}}=c^{-i}b^{c^{j}}c^{i}=b_{i+j}$
it follows:

(4.2) $b_{i}^{d_{j}}=b_{i}$ for $i\geq j$, $a^{d_{j}}=a^{b_{j}}$,
$b_{i}^{d_{j}}=b_{i}^{b_{j}}$ for $i<j$.

Here is the main feature for the sake of which $\Delta$ was built:

######  Lemma 4.1.

For any $f\in\mathcal{E}$ and for any fixed integer $j$ we have
$a_{f}^{d_{j}}=\\!a_{f_{j}^{+}}$ and
$a_{f}^{\,d_{j}^{-1}}\\!\\!=a_{f_{j}^{-}}$.

###### Proof.

Clearly, $a_{f}^{d_{j}}\\!=\\!b_{f}^{\\!-\,d_{j}}\,a^{d_{j}}b_{f}^{\,d_{j}}$.
By (4.2) the effect of conjugation of factors $b_{i}^{f(i)}$ in $b_{f}$ by
$d_{j}$ is so that in $b_{f}$ all the factors standing before $b_{j}^{f(j)}$
are conjugated by the same $b_{j}$, while other factors are not changed. After
cancellations of all $b_{j}^{\vphantom{8}}b_{j}^{-1}$ in and between the
factors of $a_{f}^{\\!-b_{j}}$, $a^{b_{j}}$ and $a_{f}^{b_{j}}$ we get the
needed equality. The second equality is considered similarly. ∎

######  Example 4.2.

Let $j=1$ and $f=(2,5,3)$. Then $b_{f}=b_{0}^{2}\,b_{1}^{5}\,b_{2}^{3}$, and
by (4.2) we have:
$a_{f}^{d_{1}}=\big{(}b_{2}^{\\!-3}b_{1}^{\\!-5}b_{0}^{\\!-2}\;a\;b_{0}^{2}b_{1}^{5}b_{2}^{3}\,\big{)}^{d_{1}}\\!\\!=b_{2}^{-3}\,b_{1}^{-5}\,\big{(}b_{1}^{\\!-1}b_{0}^{\\!-2}b_{1}^{\vphantom{8}}\big{)}\;\big{(}b_{1}^{\\!-1}ab_{1}^{\vphantom{8}}\big{)}\;\big{(}b_{1}^{\\!-1}b_{0}^{2}b_{1}^{\vphantom{8}}\big{)}\,b_{1}^{5}\,b_{2}^{3}$,
which after cancellations is equal to
$b_{2}^{\\!-3}b_{1}^{\\!-\,6}b_{0}^{\\!-2}\;a\;b_{0}^{2}b_{1}^{6}b_{2}^{3}=a_{f_{1}^{+}}$
with $f_{1}^{+}=(2,6,3)$.

######  Lemma 4.3.

$\boldsymbol{\mathscr{S}}$ contains the sets ${\mathcal{Z}}$ and
${\mathcal{S}}$.

###### Proof.

Since ${\mathcal{Z}}$ consists of $f\\!=\\!(0)$ only, then
$A_{{\mathcal{Z}}}=\langle a\rangle$. Being finitely generated $\langle
a\rangle$ is benign.

${\mathcal{S}}$ contains the function $f=(0,1)$. Apply Lemma 4.1 to $a_{f}$
repeatedly we get:

(4.3)
$a_{f}^{(d_{0}d_{1})^{n}}\\!\\!=\big{(}a_{(0,1)}^{d_{0}}\big{)}^{d_{1}\,(d_{0}d_{1})^{n-1}}\\!\\!\\!\\!=a_{(0+1,\,1)}^{d_{1}\,(d_{0}d_{1})^{n-1}}\\!\\!\\!=a_{(1,\,1+1)}^{(d_{0}d_{1})^{n-1}}\\!\\!\\!=a_{(2,3)}^{(d_{0}d_{1})^{n-2}}\\!\\!\\!=\cdots=a_{(n,n+1)}.$

Thus, $a_{(n,n+1)}\in\langle a_{f},d_{0}d_{1}\rangle$ for any
$n\in{\mathbb{Z}}$, and so $A_{{\mathcal{S}}}\leq\langle
a_{f},d_{0}d_{1}\rangle$. Using (2.4) for $x=a_{f}$ and $y=d_{0}d_{1}$, we can
rewrite any element $w\in\langle a_{f},d_{0}d_{1}\rangle$ as $w=u\cdot v$,
where $u$ is a product of some conjugates
$a_{f}^{\pm(d_{0}d_{1})^{n_{i}}}$, and $v=(d_{0}d_{1})^{k}$. By (4.3) all
those conjugates are in $G$. Thus, if also $w\in G$, then $v\in G$. Let us
show this may happen for $v=1$ only. Since $d\notin G$, we can include it in
any transversal $T_{G}$ to $G$ in $\Psi$. Then
$v=(d^{e^{0}}d^{e^{1}})^{k}=(d\,e^{-1}\\!d\,e)^{k}$ is in normal form in
$\Delta$ (with respect to $T_{G}$), i.e., $k=0$, if $v\in G$. So $G\cap\langle
a_{f},d_{0}d_{1}\rangle=A_{{\mathcal{S}}}$, and $A_{{\mathcal{S}}}$ is benign.
∎

######  Theorem 4.4.

The set $\boldsymbol{\mathscr{S}}$ is closed under the Higman operations (H).

This fact at once follows from Lemma 3.2 for binary operations $\iota$ and
$\upsilon$. The proofs for unary operations
$\rho,\,\sigma,\,\tau,\,\theta,\,\zeta,\,\pi,\,\omega_{m}$ follow from
specific cases and examples below. In each of them we suppose ${\mathcal{B}}$
is in $\boldsymbol{\mathscr{S}}$, and show that a Higman operation keeps it in
$\boldsymbol{\mathscr{S}}$.

$\boldsymbol{\mathscr{S}}$ is closed under $\rho$ because for the automorphism
$\varphi$ of $G$ sending $a,b,c$ to $a,b,c^{-1}$ we have
$\varphi(b_{i})=\varphi(b^{c^{i}})=b^{c^{-i}}=b_{-i}$. So
$A_{\rho({\mathcal{B}})}=\varphi(A_{{\mathcal{B}}})$ is benign by Lemma 3.3
(1).

$\boldsymbol{\mathscr{S}}$ is closed under $\sigma$. Indeed, for the
automorphism $\varphi$ of $G$ sending $a,b,c$ to $a,b^{c}\\!\\!,\,c$ we have
$\varphi(b_{i})=\varphi(b^{c^{i}})=b^{c^{i+1}}\\!=b_{i+1}$, and so
$A_{\sigma({\mathcal{B}})}=\varphi(A_{{\mathcal{B}}})$ is benign by Lemma 3.3
(1).

$\boldsymbol{\mathscr{S}}$ is closed under $\zeta$. For each
$f\in{\mathcal{B}}$ we in $\Delta$ by Lemma 4.1 have
$a_{f}^{d^{k}}\\!\\!=a_{f^{\prime}}^{\vphantom{8}}$, with
$f^{\prime}(0)\\!=\\!f(0)+k$, and $f^{\prime}(i)\\!=\\!f(i)$ for
$i\\!\neq\\!0$. Any $f^{\prime}\\!\\!\in\\!\zeta({\mathcal{B}})$ can be
obtained this way, and so $R\\!=\\!\langle\,A_{{\mathcal{B}}},d\rangle$
contains $A_{\zeta({\mathcal{B}})}$. On the other hand, for any $w\\!\in\\!R$
we apply 2.6 for ${\mathfrak{X}}=\\{a_{f}\mathrel{|}f\in{\mathcal{B}}\\}$ and
${\mathfrak{Y}}=\\{d\\}$ to get $w=u\cdot v$, where $u$ is a product of
factors of type $a_{f}^{\pm d^{k_{i}}}\\!\\!\\!\in A_{\zeta({\mathcal{B}})}$,
and where $v=d^{k}$. If also $w\in G$, then $v\\!=\\!1$ by uniqueness of
normal form, i.e., $w\in A_{\zeta({\mathcal{B}})}$ and
$G\\!\cap\\!R=A_{\zeta({\mathcal{B}})}$. Since $R$ is benign by Lemma 3.2 (2),
$A_{\zeta({\mathcal{B}})}$ is benign by Lemma 3.2 (1).

$\boldsymbol{\mathscr{S}}$ is closed under $\pi$. In previous case take
$R=\langle\,A_{{\mathcal{B}}},d_{1},d_{2},\ldots\,\rangle$ instead. $R$
contains $A_{\pi({\mathcal{B}})}$, and applying 2.6 for
${\mathfrak{X}}=\\{a_{f}\mathrel{|}f\in{\mathcal{B}}\\}$ and
${\mathfrak{Y}}=\\{d_{1},d_{2},\ldots\\}$ we get
$G\cap\,R=A_{\pi({\mathcal{B}})}$. Since $B_{0}$ is benign in $\langle
b,c\rangle$ by Example 3.7, its image $\langle d_{0},d_{1},\ldots\rangle$
together with the subgroup $\langle d_{1},d_{2},\ldots\rangle$ are benign in
$\langle d,e\rangle$ and, thus, in $\Delta$. Hence $R$ is benign by Lemma 3.2
(2). Then $A_{\pi({\mathcal{B}})}$ is benign by Lemma 3.2 (1).

$\boldsymbol{\mathscr{S}}$ is closed under $\theta$. Modify the idea of
previous points. The subgroup $\langle d_{i}\mathrel{|}\text{all odd
$i$}\,\rangle$ is benign as it is the isomorphic image of the benign subgroup
$A_{2,1}$ from Example 3.6. Since $A_{{\mathcal{B}}}$ is benign,
$R_{1}=\langle\,A_{{\mathcal{B}}},d_{i}\mathrel{|}\text{all odd $i$}\,\rangle$
also is benign. Applying 2.6 for
${\mathfrak{X}}=\\{a_{f}\mathrel{|}f\in{{\mathcal{B}}}\\}$ and
${\mathfrak{Y}}=\\{d_{i}\mathrel{|}\text{all odd $i$}\,\\}$ we get that $G\cap
R_{1}=A_{{{\mathcal{B}}}_{1}}$, where $f^{\prime}\in{{\mathcal{B}}}_{1}$ if
and only if there is an $f\in{{\mathcal{B}}}$ such that $f^{\prime}(i)=f(i)$
for all even $i$ (there can be any values $f^{\prime}(i)$ for odd $i$).
Similarity, $\langle d_{i}\mathrel{|}\text{all even $i$}\,\rangle$ is benign
(use $A_{2,0}$ this time). Thus, $R_{2}=\langle\,a,d_{i}\mathrel{|}\text{all
even $i$}\,\rangle$ also is benign. Applying 2.6 for ${\mathfrak{X}}=\\{a\\}$
and ${\mathfrak{Y}}=\\{d_{i}\mathrel{|}\text{all even $i$}\,\\}$ we get that
$G\cap R_{2}=A_{{\mathcal{B}}_{2}}$ where $f^{\prime}\in{\mathcal{B}}_{2}$ if
and only if $f^{\prime}(i)=0$ for all odd $i$ (there can be any values
$f^{\prime}(i)$ for even $i$). Then $A_{{\mathcal{B}}_{1}}\\!\cap
A_{{\mathcal{B}}_{2}}$ is benign. Since the $a_{f}$ are free generators,
$A_{{\mathcal{B}}_{1}}\\!\cap A_{{\mathcal{B}}_{2}}\\!\\!=\\!A_{\mathfrak{Y}}$
where ${\mathfrak{Y}}\\!=\\!{\mathcal{B}}_{1}\\!\cap{\mathcal{B}}_{2}$. But
${\mathcal{B}}_{1}\\!\cap{\mathcal{B}}_{2}$ clearly consists of all those
functions $f^{\prime}$ which coincide with some $f\in{\mathcal{B}}$ on all
even $i$, and are zero elsewhere. Let $\gamma$ be the homomorphism sending
sending $a,b,c$ to $a,b,c^{2}$. Then
$A_{\theta({\mathcal{B}})}=\gamma^{-1}(A_{\mathfrak{Y}})$, and so
$A_{\theta({\mathcal{B}})}$ is benign by Lemma 3.3 (2).

$\boldsymbol{\mathscr{S}}$ is closed under $\tau$. By Example 3.8 $B_{0,2}$ is
benign in $G$. Take $K$ to be a finitely presented group with a finitely
generated subgroup $L$ such that $G\cap L=B_{0,2}$, and set
$\Lambda=K*_{L}\\!t$. As it is easy to check $\langle K,K^{t}\rangle$ is equal
to $K*_{L}K^{t}$. Since $B\cap B_{0,2}=B_{0,2}=G^{t}\cap B_{0,2}$, we by
Corollary 2.3 (1) have $\langle B,G^{t}\rangle=B*_{B_{\,0,2}}\\!\\!G^{t}$ in
$\Lambda$. Since $B$ is free, it has an automorphism swapping $b_{0}$ and
$b_{1}$, while fixing $a$ and $b_{i}$ for any $i\neq 0,1$. This automorphism
and the identical automorphism of $G^{t}$ agree on $B_{0,2}$, so they have a
common extension $\xi$ on entire $B*_{B_{\,0,2}}\\!\\!G^{t}$. Then
$\Phi=\Lambda*_{\xi}q$ is finitely presented as $\xi$ can be defined by its
values on just six generators $a,b_{0},b_{1};\;a^{t}\\!,b^{t}\\!,c^{t}$ of
$B*_{B_{0,2}}\\!G^{t}$. For every $f\\!\in\mathcal{E}$ we clearly have
$\tau(b_{f})=b_{f^{\prime}}$ where $f^{\prime}(0)=f(1)$, $f^{\prime}(1)=f(0)$,
and $f^{\prime}(i)=f(i)$, for $i\neq 0,1$. Thus,
$A_{\tau({\mathcal{B}})}=A_{{\mathcal{B}}}^{q}$ in $\Phi$. Applying Lemma 3.3
(1) for the trivial embedding $\alpha:G\to\Phi$ we get that
$A_{{\mathcal{B}}}$ is benign in $\Phi$. By the above construction and again
by Lemma 3.3 (1) $A_{\tau({\mathcal{B}})}=A_{{\mathcal{B}}}^{\,q}$ also is
benign in $\Phi$. The pre-image $\alpha^{-1}(A_{\tau({\mathcal{B}})})$ in $G$
clearly is $A_{\tau({\mathcal{B}})}$, which then is benign in $G$ by Lemma 3.3
(2).

$\boldsymbol{\mathscr{S}}$ is closed under $\omega_{m}$ for each
$m=1,2,\ldots$ Denote
${\mathcal{B}}_{m}={\mathcal{B}}\cap{\mathcal{E}}_{m}=\iota({\mathcal{B}},{\mathcal{E}}_{m})$.
Since by Example 3.9 $A_{{\mathcal{E}}_{m}}$ is benign,
$A_{{\mathcal{B}}_{m}}$ is benign also. Clearly,
$\omega_{m}({\mathcal{B}})=\omega_{m}({\mathcal{B}}_{m})$, and we may suppose
${\mathcal{B}}={\mathcal{B}}_{m}$. Since $B_{0,m}$ is benign in $\langle
b,c\rangle$ by Example 3.8, $\langle b,c\rangle$ is embeddable into some
finitely presented group $K$ with a finitely generated subgroup $P$ such that
$\langle b,c\rangle\cap P=B_{0,m}$. Set $\Sigma=K*_{P}(g,h,k)$, where each of
$g,h,k$ stabilizes $P$ (and also $B_{0,m}$).

Since the intersection of $\langle b_{0},\ldots,b_{m-1}\rangle$ with $B_{0,m}$
and, thus, with $P$ is trivial, by Lemma 2.4 or directly by the normal form
theorem the elements $b_{0},\ldots,b_{m-1},\,g,h,k$ generate in $\Sigma$ the
free product $\langle b_{0},\ldots,b_{m-1}\rangle*\langle g,h,k\rangle$, i.e.,
the free subgroup $\langle b_{0},\ldots,b_{m-1},\,g,h,k\rangle$. Denoting
$h_{i}=h^{k^{i}}$ for $i\in{\mathbb{Z}}$, we get another free subgroup
$\langle b_{0},\ldots,b_{m-1},\,g,\,h_{0},\ldots,h_{m-1}\rangle$ in $\Sigma$.
Setting $h_{f}=h_{0}^{f(0)}\\!\cdots\,h_{m-1}^{f(m-1)}$ and $g_{f}=g^{h_{f}}$
we by Example 3.11 get its benign subgroup $L=\langle
g_{f}^{\vphantom{8}}b_{f}^{-1}\mathrel{|}f\in\mathcal{E}_{m}\rangle$. I.e.,
$\Sigma$ is embeddable into a finitely presented $M$ with a finitely generated
subgroup $R$ such that $\Sigma\cap R=L$. Take $\Pi=M*_{R}a$, with some $a$
fixing $R$.

If we show that $a,b,c$ generate a free subgroup in $\Pi$, we can identify it
with our initial group $G=\langle a,b,c\rangle$. By Lemma 2.4 that will be
shown if we verify $\langle a\rangle\cap R=\\{1\\}$ (which is evident) and
$\langle b,c\rangle\cap R=\\{1\\}$. By construction $\langle b,c\rangle\cap
R=\langle b,c\rangle\cap L$. Any two distinct words on letters
$b_{0},\ldots,b_{m-1}$ are distinct modulo $B_{0,m}$ and, thus, are distinct
in $K$ modulo $P$. I.e., we can choose a transversal $T_{P}$ to $P$ in $K$
containing all the words on $b_{0},\ldots,b_{m-1}$. Any non-trivial product
$v$ of elements of type
$g_{f}^{\vphantom{8}}b_{f}^{-1}\\!=\\!g^{h_{0}^{f(0)}\\!\cdots\,h_{m-1}^{f(m-1)}}b_{m-1}^{-f(m-1)}\\!\cdots
b_{0}^{-f(0)}$ already is in normal form in $\Sigma$ (with respect to $T_{P}$)
because it is a product of stable letters and transversal’s elements. It will
be in $\langle b,c\rangle$ only if no stable letter is preset, i.e., if it is
trivial.

Since $G=\langle a,b,c\rangle$ is free, using its isomorphism $\rho$ sending
$a,b,c$ to $a,b^{c^{m}}\\!\\!\\!\\!\\!,\;c$ define $\Omega=\Pi*_{\rho}r$.
Denote $W_{{\mathcal{B}}}=\langle
g_{f}\\!,\,a,\,r\mathrel{|}f\in{\mathcal{B}}\rangle$. For any
$l\in\omega_{m}{\mathcal{B}}$ the element $a_{l}=a^{b_{l}}$ is in
$W_{{\mathcal{B}}}$. Let us show this simple fact by a step-by-step
construction example. Let $m=3$ and let $(2,5,3)$, $(7,2,4)\in{\mathcal{B}}$.
Then $\omega_{3}{\mathcal{B}}$ contains, say,
$l=(0,0,0,\;7,2,4,\;0,0,0,\;2,5,3,\;7,2,4)$. To show that $a^{b_{l}}\in
W_{{\mathcal{B}}}$ start by the initial function $l_{1}=(7,2,4)$, and then
modify it to achieve the value $l$ above. The relation
$(g_{f}^{\vphantom{8}}b_{f}^{-1})^{a}=g_{f}^{\vphantom{8}}b_{f}^{-1}$ is
equivalent to $a^{g_{f}\vphantom{j}}\\!=a^{b_{f}}$.

Step 1. Since $f=l_{1}=(7,2,4)$ is in ${\mathcal{B}}$, then $g_{l_{1}}\in
W_{{\mathcal{B}}}$, and so
$a^{g_{l_{1}}}\\!\\!=a^{b_{l_{1}}}=a^{b_{0}^{7}\,b_{1}^{2}b_{2}^{4}}\in
W_{{\mathcal{B}}}$.

Step 2. Conjugating the above element by $r$ we get that

$(a^{b_{l_{1}}})^{r}\\!\\!=(a^{r})^{(b_{0}^{7}\,b_{1}^{2}b_{2}^{4})^{r}}\\!\\!=a^{b_{3}^{7}\,b_{4}^{2}b_{5}^{4}}=a^{b_{0}^{0}\,b_{1}^{0}b_{2}^{0}\;\cdot\;b_{3}^{7}\,b_{4}^{2}b_{5}^{4}}=a^{b_{l_{2}}}\in
W_{{\mathcal{B}}}\text{\quad(with $l_{2}=(0,0,0,\;7,2,4)$)}.$

Conjugate the above by $g_{f}$ for $f=(2,5,3)$. We have:
$\big{(}\\!a^{b_{l_{2}}}\big{)}^{g_{f}}\\!\\!\\!=\,a^{b_{l_{2}}\cdot\,g_{f}}\\!\\!=a^{b_{3}^{7}\,b_{4}^{2}b_{5}^{4}\;\cdot\,g_{f}}\\!$.

Step 3. Each of $g,h,k$ commutes with each of $b_{i}$ for $i<0$ or $i\geq
m=3$, and so $g_{f}$ commutes with $b_{3}^{7}\,b_{4}^{2}b_{5}^{4}$, and
$a^{b_{l_{2}}\cdot\,g_{f}}=a^{g_{f}\cdot\,b_{3}^{7}\,b_{4}^{2}b_{5}^{4}}$.
Then again applying step 1 we get:

$\big{(}\\!a^{g_{f}}\\!\big{)}^{b_{3}^{7}\,b_{4}^{2}b_{5}^{4}}=a^{b_{0}^{2}\,b_{1}^{5}b_{2}^{3}\;\cdot\;b_{3}^{7}\,b_{4}^{2}b_{5}^{4}}=a^{b_{l_{3}}}\in
W_{{\mathcal{B}}}\text{\quad(with $l_{3}=(2,5,3,\;7,2,4)$)}.$

Then we apply step 2 twice, i.e., conjugate the above by $r^{2}$ to get the
element $a^{b_{l_{4}}}$ with $l_{4}=(0,0,0,\;0,0,0,\;2,5,3,\;7,2,4)$. Next
apply step 3 and step 1 again to conjugate $a^{b_{l_{4}}}$ by $g_{f}$ for
$f=(7,2,4)$. We get the element $a^{b_{l_{5}}}$ with
$l_{5}=(7,2,4,\;0,0,0,\;2,5,3,\;7,2,4)$. Finally, we again apply step 2, i.e.,
conjugate $a^{b_{l_{5}}}$ by $r$ to discover in $W_{{\mathcal{B}}}$ the
element $a^{b_{l}}=a_{l}$. Since this procedure can easily be performed for an
arbitrary $l\in\omega_{m}{\mathcal{B}}$, we get that
$A_{\omega_{m}{\mathcal{B}}}\leq W_{{\mathcal{B}}}$.

Let us single out an auxiliary “slimmer” subgroup $\Omega^{\prime}$ in
$\Omega$. Since $\langle b,c\rangle\cap P=B_{0,m}$, the subgroup
$\big{\langle}\langle b,c\rangle,g,h,k\big{\rangle}$ is equal to
$\Sigma^{\prime}=\langle b,c\rangle*_{B_{0,m}}(g,h,k)$. Since
$\Sigma^{\prime}$ contains each of $b,c,g,h,k$ it also contains $L$. Thus,
$\Sigma^{\prime}\cap R=L$, and using Lemma 2.4 we see that
$\langle\Sigma^{\prime},a\rangle$ is equal to
$\Pi^{\prime}=\Sigma^{\prime}*_{L}a$. Finally, since $a,b,c\in\Pi^{\prime}$,
the subgroup $\langle\Pi^{\prime},r\rangle$ is equal to
$\Omega^{\prime}=\Pi^{\prime}*_{\rho}r$. The advantage of $\Omega^{\prime}$ is
that it is an extension of $\langle b,c\rangle$ by means of three “nested”
HNN-extensions, and we, thus, possess the full list of defining relations of
$\Omega^{\prime}$.

Since any $w\in W_{{\mathcal{B}}}$ also is in $\Omega^{\prime}$, it can be
brought to its normal form evolving $r$ and some elements from $\Pi^{\prime}$.
The latters can in turn be brought to normal forms evolving $a$ and some
elements from $\Sigma^{\prime}$. Then the latters can further be brought to
normal forms evolving $g,h,k$ and some elements from $\langle b,c\rangle$.
I.e., $w$ can be brought to a unique “nested” normal form. Detect the cases
when it evolves $a,b,c$ only. The only relations of $\Omega^{\prime}$ evolving
$g,h,k$ are $a^{g_{f}}\\!=a^{b_{f}}$. Thus, the only way by which $g,h,k$ may
be eliminated in the normal form is to have in $w$ subwords of type
$g_{f}^{\\!-1}a\,g_{f}^{\vphantom{8}}=a^{g_{f}}$, to replace them by
respective $a^{b_{f}}\in\langle a,b,c\rangle$. If after that some subwords
$g_{f}$ still remain, then three scenario cases are possible:

Case 1. We may have a subword of type
$w^{\prime}=g_{f}^{-1}a^{b_{l}}g_{f}^{\vphantom{8}}$ for such an $l$ that
$l(i)=0$ for $i=0,\ldots,m-1$. Check example of step 1, when this is achieved
for $l=l_{2}=(0,0,0,\;7,2,4)$ and $f=(2,5,3)$. Then just replace $w^{\prime}$
by $a^{b_{l_{3}}}$ for an $l_{3}\in\omega_{m}{\mathcal{B}}$ (e.g.
$l_{3}=(2,5,3,\;7,2,4)$).

Case 2. If $w^{\prime}=g_{f}^{-1}a^{b_{l}}g_{f}$, but the condition $l(i)=0$
fails for an $i=0,\ldots,m-1$, then $g_{f}$ does not commute with $b_{l}$, so
we cannot apply the relation $a^{g_{f}}\\!=a^{b_{f}}$, and so $w\notin\langle
a,b,c\rangle$. Turning to example in steps 1–3, notice that for, say,
$f=(2,5,3)\in{\mathcal{B}}$ we may never get something like
$a^{(g_{f})^{\,2}}\\!\\!=(a^{b_{0}^{2}\,b_{1}^{5}\,b_{2}^{3}})^{g_{f}}\\!\\!=a^{(b_{0}^{2}\,b_{1}^{5}\,b_{2}^{3})^{2}}$
because $g_{f}$ does not commute with $b_{0},b_{1},b_{2}$. That is, all the
new functions $l$ we get are from $\omega_{m}{\mathcal{B}}$ only.

Case 3. If $g_{f}$ is in $w$, but not in a subword $g_{f}^{-1}a^{b_{l}}g_{f}$,
we again have $w\notin\langle a,b,c\rangle$.

This means, if $w\in\langle a,b,c\rangle$, then elimination of $g,h,k$ turns
$w$ to a product of elements from $\langle r\rangle$ and of some $a^{b_{l}}$
for some $l\in\omega_{m}{\mathcal{B}}$ ($a$ also is of that type, as
$(0)\in{\mathcal{B}}$). Now apply 2.6 for
${\mathfrak{X}}=\\{a^{b_{l}}\mathrel{|}l\in\omega_{m}{\mathcal{B}}\\}$ and
${\mathfrak{Y}}=\\{r\\}$ to state that $w$ is a product of some power $r^{k}$
and of some elements each of which is an $a^{b_{l}}$ conjugated by a power
$r^{n_{i}}$ of $r$. These conjugates are in $\omega_{m}{\mathcal{B}}$, and so
$w\in\langle a,b,c\rangle$ if and only if $k=0$, i.e., if $w\in
A_{\omega_{m}{\mathcal{B}}}$.

We have now done all the hard work, and it remains to notice that since
$G=\langle a,b,c\rangle$ is a free group, $G\cap
W_{{\mathcal{B}}}=A_{\omega_{m}{\mathcal{B}}}$. Since $A_{{\mathcal{B}}}$ is
benign, its image $\langle g_{f}\mathrel{|}f\in{\mathcal{B}}\rangle$ also is
benign. Then $W_{{\mathcal{B}}}=\langle
g_{f}\\!,\,a,\,r\mathrel{|}f\in{\mathcal{B}}\rangle$ is benign by Lemma 3.2
(2), and $A_{\omega_{m}{\mathcal{B}}}$ is benign by Lemma 3.2 (1).

## References

  * [1] S.O. Aanderaa, A proof of Higman’s embedding theorem using Britton extensions of groups, Word Probl., Decision Probl. Burnside Probl. Group Theory, Studies Logic Foundations Math. 71 (1973), 1–18.
  * [2] S.I. Adyan, V.G. Durnev, Decision problems for groups and semigroups, Usp. Mat. Nauk 55 (2000), 2, 3–94 (Russian). Translation: Russ. Math. Surv. 55 (2000), 2, 207–296.
  * [3] G. Baumslag, Topics in Combinatorial Group Theory, Lectures in Math. ETH Zuerich, Biuser Basel (1993).
  * [4] O. Bogopolski, Introduction to group theory, EMS Textbooks in Mathematics. Zürich: EMS (2008).
  * [5] W.W. Boone, Certain simple, unsolvable problems of group theory. III-VI, Nederl. Akad. Wet., Proc., Ser. A, 58 (1955), 252–256, 571–577; 60 (1957), 22–27, 227–232.
  * [6] G. Boolos, J. Burgess, R. Jeffrey, Computability and Logic. 4th Ed., Cambridge U. Press, Cambridge (2002).
  * [7] J.L. Britton, The word problem for groups, Proc. Lond. Math. Soc., III. Ser. 8 (1958), 493–506.
  * [8] M. Davis, Computability and unsolvability New York: McGraw-Hill (1958).
  * [9] Why is “The Higman Rope Trick” thus named? https://mathoverflow.net/questions/195011
  * [10] G. Higman, B. Neumann, Hanna Neumann, Embedding theorems for groups, J. London Math. Soc., 3, 24, (1949), 247–254.
  * [11] G. Higman, Subgroups of finitely presented groups, Proc. R. Soc. Ser. A (1961), 262, 455–475.
  * [12] R.C. Lyndon, P. E. Schupp, Combinatorial group theory groups, Ergebnisse der Mathematik und ihrer Grenzgebiete. 89. Berlin-Heidelberg-New York: Springer-Verlag. (1977).
  * [13] Yu.V. Matiyasevich, Enumerable sets are Diophantine, Dokl. AN SSSR, 191 (1970), 279–282 (Russian). Translation: Soviet Math. Dokl. 11 (1970), 354–357.
  * [14] V. H. Mikaelian, Subnormal embedding theorems for groups J. London Math. Soc., 62.2 (2000), 398–406.
  * [15] V. H. Mikaelian, Metabelian varieties of groups and wreath products of abelian groups, Journal of Algebra, 2007 (313), 2, 455–485.
  * [16] V. H. Mikaelian, A.Yu. Olshanskii, On abelian subgroups of finitely generated metabelian groups, Journal of Group Theory, 16 (2013), 695–705.
  * [17] V. H. Mikaelian, Subvariety structures in certain product varieties of groups, Journal of Group Theory, 21 (2018), 5, 865–884.
  * [18] Hanna Neumann, Varieties of Groups, Springer–Verlag, Berlin (1967).
  * [19] A.A. Markov, The impossibility of certain algorithms in the theory of associative systems, Dokl. AN SSSR, 55 (1947), 587–590 (Russian). Translation: Soviet Math. Dokl., 55 (1947), 583–586.
  * [20] P. S. Novikov, On algorithmic undecidability of the problem of equality in the theory of groups, Trudi Matem. Inst, AN SSSR, 44 (1955), 1–143.
  * [21] A.Yu. Ol’shanskii, M.V. Sapir, The conjugacy problem and Higman embeddings, M. AMS 804 (2004), 133.
  * [22] E.L. Post, Recursive unsolvability of a problem of Thue, J. Symb. Log., 12 (1947), 1–11.
  * [23] H. Rogers, The Theory of Recursive Functions and Effective Computability, MIT Press (1967).
  * [24] J.J. Rotman, An introduction to the theory of groups, 4th ed., Graduate Texts in Mathematics. 148. New York, NY: Springer-Verlag. (1995).
  * [25] J.R. Shoenfield, Mathematical Logic, Addison-Wesley (1967).
  * [26] M.K. Valiev, A theorem of G. Higman, Algebra and logic, 9 (1968), 9–22.

Informatics and Appl. Mathematics Department | College of Science and Engineering
---|---
Yerevan State University | American University of Armenia
Alex Manoogian 1 | Marshal Baghramyan Avenue 40
Yerevan 0025, Armenia | Yerevan 0019, Armenia
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>|