Codex @codex  0

No Markov property of finitely presented groups is decidable by an algorithm taking an arbitrary finite group presentation as input. The proof reduces the word problem for a group to property recognition using an effective construction which collapses when an input word is trivial and embeds the input group when it is nontrivial.

A finitely generated group is synchronously combable if it admits a combing of a group with the synchronous fellow-traveller property. Without a regular-language assumption, this is more general than an automatic group. A bounded-rung strip argument gives a finite group presentation, and finite-state row shortening gives a recursive exponential filling bound and a soluble word problem for a group.

Choose bounded-length substitutions $T$ from the first generating set to the second, and $U$ back. Each substituted relator of the second group presentation has bounded area in the first, and every generator correction $a(UT(a){)}^{-1}$ has bounded area. Substitution into a minimal second-presentation diagram and filling the correction strips givesThe reverse construction gives the opposite inequality. Thus the optimal Dehn functions are coarsely equivalent, and the existence of a recursive isoperimetric bound, hence solvability of the word problem for a group, is independent of the finite group presentation.

In the finite group presentation $⟨a,t\mid ta{t}^{-1}=a^2⟩$, let $a$ act by $x\mapsto x+1$ and $t$ by $x\mapsto 2x$. The conjugates $a_i=t^{-i}a{t}^i$ satisfy $a_{i+1}^2=a_i$, so their increasing cyclic subgroups give the additive group $\mathbb{Z}[1/2]$. Every element has the form $a_i^m{t}^k$, and the affine action proves that this form can be the identity only if $k=m=0$. Thus the displayed semidirect product identification holds. This is a finitely presented group with a series having torsion-free abelian factors, but it is not a poly-infinite cyclic group, since $\mathbb{Z}[1/2]$ is not finitely generated.

A finitely presented group is a group admitting a finite group presentation. Finite presentability concerns the existence of such a presentation, not the decidability of its word problem for a group.

If $N=⟨A\mid R⟩$ and $H=⟨B\mid S⟩$ have finite group presentations and $\varphi :H\to \mathrm{Aut}(N)$ is an action, choose a word $w_{b,a}(A)$ representing $\varphi (b)(a)$. Then $N{⋊}_{\varphi }H$ has the finite presentationThe action automorphisms also let these relations rewrite conjugation by inverse generators. Every word becomes an $A$-word followed by a $B$-word. The natural map to the semidirect product is injective because its triviality forces the $B$-word to be trivial using $S$ and then the $A$-word to be trivial using $R$.

The Higman group has the finite group presentation $Q=⟨a_1,a_2,a_3,a_4\mid a_i{a}_{i+1}{a}_i^{-1}=a_{i+1}^2(i\mathrm{mod}4)⟩$. Its subgroup $⟨a_1,a_3⟩$ is a rank-two free group, and the normal closure of each $a_i$ is all of $Q$. It has no nontrivial finite quotients of a group: a least prime divisor among the four generator orders in a finite image contradicts the multiplicative-order constraints imposed by conjugation to squares. These properties give finite-presentation constructions embedding arbitrary finitely presented groups into groups with no nontrivial finite quotients.

A finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group. The necessity follows by enumerating proofs that substituted generator words are trivial in the larger finite group presentation. The sufficiency is the embedding theorem; it also applies to effectively countably generated recursive presentations after an effective two-generator embedding. This is the theorem of Subgroups of finitely presented groups.

A nondecreasing function bounding the area of every null word of length at most $n$ is an isoperimetric function for a finite group presentation. The Dehn function is the minimal such bound. A subrecursive bound means one dominated by a total computable function. Arbitrarily enlarged bounds are not invariants: even a group presentation with zero area function admits both linear and exponential upper bounds, which are not equivalent under the usual coarse comparison.

In the effective group form used for recognition problems, a finite group presentation of $K$ and a word $w$ yield, by an algorithm, a finite presentation of a group $K_w$. If $w=1$ in $K$, then $K_w$ is trivial; if $w\ne 1$ in $K$, then the specified generators embed $K$ in $K_w$. One can additionally arrange that the normal closure of the image of $w$ is all of $K_w$. The finite presentation can be written without first deciding which case holds. This is the collapse-versus-embedding construction behind the Adian–Rabin theorem.

For a finite group presentation $H=⟨x_1,\dots ,x_m\mid r_1,\dots ,r_n⟩$, let $F$ be the free group on its generators and $\pi :F\to H$. The corresponding fiber product of groups is generated by $(x_i,x_i)$ and $(1,r_j)$. Conjugation by the diagonal pairs supplies every pair $(1,r)$ with $r$ in the normal closure of the relators, and $(u,v)=(u,u)(1,u^{-1}v)$ proves the generating claim. Membership of $(1,w)$ is equivalent to $w=1$ in $H$, so this finitely generated subgroup can have undecidable membership even though $F\times F$ has soluble word problem.

Choose representatives $T$ of the right cosets $Hg$, including $1$, and let $M={\max }_{t\in T}|t{|}_A$. This is finite because the index is finite. For $t\in T$ and $a\in A^{\pm 1}$, let $\overline{ta}\in T$ represent $Hta$. The elementsform a finite generating set $S$ for $H$, after adjoining inverses and discarding identities. To see generation rather than merely quote Schreier's lemma, write $h=a_1\cdots a_n$ and let $t_i$ represent $H{a}_1\cdots a_i$. Then $t_0=t_n=1$ andEach factor is a Schreier generator. For a shortest $A$-word this gives $|h{|}_S\le |h{|}_A$. Conversely every Schreier generator has $A$-length at most $2M+1$, so $|h{|}_A\le (2M+1)|h{|}_S$. Hence the inclusion $H\hookrightarrow G$ obeysEvery $g\in G$ can be written $g=ht$, and $d_A(g,h)=|t{|}_A\le M$. Thus the inclusion is coarsely onto and is a finite-index subgroup quasi-isometry.

Only finite generation of $G$ was needed for the metric argument. Under the given finite-presentation hypothesis, $H$ is also finitely presented: the corresponding finite-sheeted cover of a finite presentation complex has finitely many cells, and a spanning-tree reduction of its one-skeleton gives a finite group presentation. Therefore it belongs to the class of groups used in part (ii).

For a finite generating set $A$, use the symmetric alphabet $\Sigma =A\cup A^{-1}$. The Cayley graph has a vertex for each $g\in G$ and an oriented edge labelled $a$ from $g$ to $ga$. Give every edge length one. Its vertex word metric isTwo finitely presented groups are quasi-isometric when their Cayley graphs, with these path metrics, are quasi-isometric. The choice of finite generating set is immaterial, as the following proof shows; the relators identify vertices but do not otherwise enter the metric definition.

Given finite generating sets $A,B$ of the same group, put $L=\max (1,{\max }_{a\in A^{\pm 1}}|a{|}_B)$ and $M=\max (1,{\max }_{b\in B^{\pm 1}}|b{|}_A)$. Replace each letter in a shortest $A$-word by a fixed $B$-word to obtain $|g{|}_B\le L|g{|}_A$. Reversing the roles gives $|g{|}_A\le M|g{|}_B$. Therefore the vertex identity map satisfiesIt is onto, and hence a quasi-isometry. Map each edge to the fixed word path for its label, or pass through the uniformly dense vertex sets, to obtain the corresponding graph quasi-isometry with a bounded additive error. This proves equivalence of finite word metrics and independence of the two finite group presentations.

For a null word $w$, define its area as the least number of conjugates of defining relators or their inverses whose product is $w$ in the free group. By the van Kampen lemma, this is also its minimum number of relator faces in a disc diagram. The Dehn function isThe maximum is finite because there are finitely many words of bounded length. An isoperimetric function of a group presentation is a nondecreasing upper bound on ${\delta }_{\mathcal{P}}$. Here subrecursive means bounded above by a total computable function, not merely recursively enumerable.

Suppose ${\delta }_{\mathcal{P}}(n)\le F(n)$ with $F$ computable. Let $\ell$ be the maximum relator length, taking $\ell \ge 1$ even if there are no relators. A minimum-area diagram for a boundary word of length $n$, with at most $N$ faces, can be chosen with no unnecessary tree branches. Every remaining edge occurs on a face boundary or the outside boundary, so there are at most $\ell N+n$ edges. Thus only finitely many combinatorial planar diagrams of area at most $N$ and this edge bound exist. Their finite edge labels and face labels can be enumerated, and the planar contractible diagram topology (allowing boundary spurs and pinched vertices), relator face boundaries and outside boundary word can be checked by finite combinatorial operations.

For the input $w$, compute $N=F(|w|)$ and inspect all these diagrams. Answer yes if one has boundary $w$, and no otherwise. The diagram bound and van Kampen lemma prove correctness, including the negative answer. This finite search avoids the invalid attempt to bound area while allowing unbounded conjugating words.

Conversely, suppose a word problem decider is available. For each $n$, enumerate the finitely many words of length at most $n$ and use the decider to identify exactly the null words. For each such word search diagrams in increasing area, with the finite edge bound just given at each area. The search terminates, and the first successful area is its minimum area. Taking the maximum of these finitely many minima computes ${\delta }_{\mathcal{P}}(n)$. This proves the recursive area bounds and the word problem equivalence:In fact, for finite group presentations, a word decider computes the minimal Dehn function itself.

An algorithm is a finite effective procedure on finitely encoded inputs; a Turing machine is one precise model. A decision algorithm must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision algorithm.

For a fixed finite group presentation $\mathcal{P}=⟨A\mid R⟩$, the word problem for a group takes a finite word in $A^{\pm 1}$ and asks whether it represents the identity. Equality of two represented elements is equivalent to testing $u^{-1}v$. Positive answers are recursively enumerable: enumerate finite products of conjugates of relators and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled disc diagrams. The van Kampen lemma ensures that every null word eventually appears. For a non-null word this search continues forever. Solvability requires a procedure that also terminates with a negative answer.

First construct the bounded-difference automaton. Fix $K$ as above, enlarging it if necessary. Its states are the finitely many elements $d\in B_K(1)$, together with a reject state and finite flags recording when padding has started on each tape. The initial state is $1$. Read the pair of words synchronously, padding their ends with a symbol $\#$ representing the identity. If the current prefixes represent $g,h$, the difference state is $d=g^{-1}h$. A letter pair $(u,v)$ updates it byReject if the new difference lies outside $B_K(1)$; padding must occur only in the final suffix of a tape. The accepting state for the generator $a$ is $d=a$. Induction on the prefix length proves that the machine accepts exactly the padded pairs whose prefix differences stay bounded by $K$ and whose final difference is $a$. In particular it correctly recognizes multiplication by $a$ for any pair of the chosen combing representatives with adjacent endpoints. Taking accepting state $1$ gives the equality machine.

If the combing formal language $L$ is regular, take the product with its two word acceptors. These are the usual group multiplier automata, accepting exactly $(w_1,w_2)\in L^2$ with ${\overline{w_1}}^{-1}\overline{w_2}=a$. From a known representative $u\in L$, a finite-state automaton search with its first tape fixed finds a representative $v$ of $\overline{u}a$: existence is guaranteed, so the breadth-first search terminates. Equality is tested by the identity multiplier. Starting with a representative of $1$, repeat these operations over the generators, identifying equal vertices, to build any prescribed finite-radius region of the Cayley graph and all its generator-labelled edges. Iterating multiplication over an input word and testing equality with the identity gives a word problem algorithm.

A bare geometric combing does not imply that $L$ is a regular language. Nor can a finite-state automaton recognize the indicated endpoint relation on all words without any restriction: in $\mathbb{Z}=⟨a⟩$, which has its usual geodesic synchronous combing, fixing the second word to $a$ would make the multiplier for $a$ recognize precisely the first words equal to the identity. Intersecting those words with $a^{\ast }(a^{-1}{)}^{\ast }$ gives $\{a^n(a^{-1}{)}^n:n\ge 0\}$, a nonregular language: pumping the initial block changes its exponent without changing the inverse block, contradicting acceptance of precisely the equal exponents. Thus the literal unrestricted-pair request is false; the machines above recognize bounded fellow-travelling pairs, or full representative-pair relations under the additional automatic-language hypothesis.

Nevertheless the final decidability assertion is true for a synchronous combable group, without a regular-language assumption. Here is a terminating filling bound, avoiding any assumption that the given combing is computable. Let $D$ be the number of words of length at most $K$ over $\Sigma$. A horizontal row of the diagram in part (ii) is encoded by its ordered $n$ rung words, so there are at most $D^n$ possible row types. If two rows have the same word tuple, delete the band between them and identify corresponding labelled rungs. This preserves the outside boundary and leaves a valid diagram of the same short relators. Equivalently, the first column is always at $1$, so identical rung tuples describe the same vertex configuration. Repeatedly remove such bands. At most $D^n$ distinct rows remain, with at most $n$ short-relator cells per layer.

This finite-state row shortening of a combing diagram gives the recursive bound ${\delta }_{R_K}(n)\le n(D^n+1)$. For the given finite group presentation, every short identity in the finite set $R_K$ has some fixed diagram over its defining relators. Let $C$ bound their areas. Replacing each short face by its fixed diagram givesPart 3(ii) now supplies a terminating word decider. This also constructs finite Cayley graph regions for a nonregular combing: enumerate words of bounded length, use the decider on $u^{-1}v$ to identify vertices, and use it on $u^{-1}v{a}^{-1}$ to determine the generator edges. The finite ball $B_K(1)$ and transition table of the bounded-difference machines can consequently be computed. The constants depend on a fixed combing and are not a uniform procedure certifying combability of an arbitrary input group presentation. Every finite group presentation of this synchronous combable group has solvable word problem, by the presentation-invariance proof in Q3.

A finitely presented group is one isomorphic to $F(X)/⟨⟨R⟩⟩$, where $X$ and $R$ are finite, $F(X)$ is the free group on $X$, and the double brackets mean normal closure. Equivalently, there is a surjection from a free group of finite rank onto $G$ whose kernel is normally generated by finitely many words. The universal property of the free group extends choices of generator images uniquely, and quotienting imposes the chosen relations.

For the semidirect product, choose finite group presentationsFor each $i,j$, choose an $a$-word $w_{ji}$ representing $\varphi (b_j)(a_i)$. We claim that a finite presentation of a semidirect product isAll relations hold in the desired semidirect product, so the presented group maps onto it. We must also show there are no extra elements in the kernel. For inverse conjugations, choose an $a$-word $v_{ji}$ representing $\varphi (b_j{)}^{-1}(a_i)$. Conjugating this word by $b_j$ using the displayed relations gives an $a$-word representing $\varphi (b_j)\varphi (b_j{)}^{-1}(a_i)=a_i$, so $R$ proves $b_j^{-1}{a}_i{b}_j=v_{ji}$. Thus we can move both positive and negative $b$-letters to the right, rewriting every word as $u(a)v(b)$. If its image in $N⋊H$ is trivial, projection to $H$ makes $v$ trivial using $S$; its remaining image in $N$ then makes $u$ trivial using $R$. The kernel is trivial, proving the claim and finite presentability.

For a poly-infinite cyclic group, write its subnormal series as $G=G_0▹G_1▹\cdots ▹G_n=1$ with infinite cyclic factors. Given a subgroup $K\le G$, intersect the series with $K$. The homomorphism $K\cap G_i\to G_i/G_{i+1}$ has kernel $K\cap G_{i+1}$, soEach factor is trivial or infinite cyclic; deleting repetitions gives a poly-infinite cyclic series for $K$. For an extension $1\to N\to E\to Q\to 1$ with $N,Q$ poly-infinite cyclic groups, lift the series of $Q$ to its full preimages in $E$ and append the series of $N$. The lifted quotient factors are those of $Q$, and the lower factors are those of $N$. Normality at every consecutive step is preserved. This proves closure under both subgroups and extensions.

Finite presentability follows by induction on the length of a poly-infinite cyclic series. The trivial group is finitely presented. For a nontrivial group, its first proper term $G_1$ has a shorter series and $G/G_1\cong \mathbb{Z}$. Lift $1\in \mathbb{Z}$ to an element $t\in G$. Its powers give an injective section of the quotient map, since $t^k$ maps to $k$. Hence $G\cong G_1⋊⟨t⟩$. By induction $G_1$ is finitely presented, and $⟨t⟩\cong \mathbb{Z}$ has a finite presentation. The finite presentation of a semidirect product proved above completes the induction. Thus every poly-infinite cyclic group is finitely presented.

For the final example, take the dyadic affine Baumslag-Solitar groupwhere the generator of $\mathbb{Z}$ acts on the additive group $\mathbb{Z}[1/2]$ by multiplication by two. Here is a verification of this identification, rather than an assumption about the presentation. Put $a_i=t^{-i}a{t}^i$ for $i\ge 0$. The relation gives $a_{i+1}^2=a_i$, soTheir union $A$ is abelian and is normal: conjugation by $t^{-1}$ shifts $a_i$ to $a_{i+1}$, while conjugation by $t$ shifts $a_i$ to $a_{i-1}$ for $i\ge 1$ and sends $a_0$ to $a_0^2$. Every word can consequently be written $a_i^m{t}^k$ for some $i\ge 0$ and $m,k\in \mathbb{Z}$.

Let $a$ act on the rational line by $x\mapsto x+1$ and $t$ by $x\mapsto 2x$. These affine transformations satisfy the relation, and $a_i^m{t}^k$ acts by $x\mapsto 2^{k}x+m/2^i$. It is the identity only when $k=m=0$. Thus the action is faithful and identifies $A$ with all dyadic translations. We have the required seriesBoth factors are torsion-free abelian groups, and $G$ is visibly finitely presented. But $\mathbb{Z}[1/2]$ is not finitely generated, since finite sets have bounded powers of two in their denominators. Every poly-infinite cyclic group has the maximal condition on subgroups: its factors $\mathbb{Z}$ have that condition, and Question 1 proves closure under extensions. Therefore $G$ cannot be poly-infinite cyclic. This gives a finitely presented counterexample to replacing infinite cyclic factors by arbitrary torsion-free abelian factors.

The Messuage lemma for groups is the following effective collapse-versus-embedding statement: from a finite group presentation for $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ makes $K_w$ trivial, whereas $w\ne 1$ makes the specified copy of $K$ embed in $K_w$. It can also be arranged that the image of $w$ normally generates $K_w$. We use this lemma as an assumed construction, as requested; the construction of its presentation does not require deciding which case applies.

Let $P$ be a finitely presented group with insoluble word problem for a group, whose existence is allowed. Set $K=P\ast ⟨z⟩$, with $z$ of infinite order. It is finitely presented, and the normal form theorem for a free product embeds both $P$ and the infinite cyclic factor. Thus an input word $w$ from $P$ is trivial in $K$ exactly when it is trivial in $P$, while $K$ is certainly infinite.

Apply the Messuage lemma for groups to this $K,w$. If $w=1$ in $P$, the constructed group $K_w$ is trivial and hence finite. If $w\ne 1$, it contains $K$ and is infinite. ConsequentlyA hypothetical algorithm deciding infinitude from arbitrary finite group presentations would therefore decide every input word in $P$, a contradiction. There is no such algorithm. The infinite cyclic free factor ensures the reduction does not need an additional assumption about the size of $P$.

Suppose $G=⟨g_1,\dots ,g_n\mid R⟩$ has a finite group presentation. Work in the free product $B=G\ast F(a,b)$ and putThe $u_i$ freely generate a subgroup of $F(a,b)$. Indeed, in a reduced word in these conjugates, combine adjacent powers with the same index. Expanding the remaining word leaves nonzero powers of $a$ separated by nonzero powers of $b$, so the normal form theorem for a free product makes it nonidentity. This proves the free conjugate bases in a rank-two free group fact we need.

The group homomorphism $B\to F(a,b)$ killing $G$ sends $v_i$ to $a^{-i}b{a}^i$, including $v_0=b$. These are a free conjugate basis by the same argument with $a,b$ interchanged. A nonempty reduced word in the $v_i$ therefore has nontrivial image and cannot be trivial in $B$. Thus $u_i\mapsto v_i$ extends to an isomorphism between the two rank-$(n+1)$ free groups embedded in $B$.

Adjoin one stable letter implementing this isomorphism:We assume Britton's lemma, including its assertion that the base embeds in this HNN extension, and the factor-embedding assertion of the normal form theorem for a free product. Hence $G\hookrightarrow E$. The presentation is finite, and its relations express every generator in $a,t$:Eliminating $b,g_i$ by Tietze transformations therefore gives a two-generator finite presentation with $\boxed{G\hookrightarrow E=⟨a,t⟩}$. This explicitly constructs the two-generator HNN embedding; it does not rely on an arbitrary two-generator embedding preserving finite presentability.

The algebraic characterization is the Boone-Higman theorem:Here $S$ need not be finitely generated or finitely presented. We prove the equivalence using the Higman embedding theorem, Britton's lemma and the normal form theorem for a free product. The original characterization is Theorem I of An algebraic characterization of groups with soluble word problem.

First suppose the embeddings exist. Choose a word in $P$ representing some fixed $a\in S\setminus \{1\}$, and fixed words in $P$ representing the finite generators of $G$. Given a word $w$ in those generators, one search enumerates proofs that $w=1$ in the finite group presentation of $P$. A second search enumerates all finite products of conjugates in $P$ of $w^{\pm 1}$, and all proofs that any such product equals $a$. All these searches are effective: a proof of equality is a finite product of conjugates of defining relators, checked in the free group, and dovetailing handles the countably many candidates.

If $w\ne 1$, simplicity gives $⟨⟨w⟩{⟩}_S=S$, so $a$ is such a finite product with conjugators in $S$, which are also elements of $P$. The second search eventually succeeds. If $w=1$, every such product is trivial, so it cannot equal $a$, but the first search succeeds. Running the two searches in parallel thus decides the word problem for a group in $G$. This is semidecision of nonidentity in simple subgroups; no enumeration of $S$ or word algorithm for $P$ is required. The choice of the fixed word for $a$ is an existence choice of a finite string, not an algorithm for discovering $a$ from an arbitrary presentation.

Conversely suppose the word problem for a group in $G$ is soluble. We construct a recursive simple envelope by cyclic HNN extensions, keeping all effectiveness requirements explicit. Start with $P_0=G\ast ⟨a⟩$, where $a$ has infinite order. Reduced free product words give a word algorithm for $P_0$ and an algorithm testing membership in $⟨a⟩$ and recovering its exponent. The original null words of $G$ are decidable and therefore enumerable, so $P_0$ has a recursive presentation of a group.

Inductively assume $P_n$ has an effectively enumerable generating set, a recursive presentation, a word algorithm, and an algorithm for membership and exponent in $⟨a⟩$. Form $B_n=P_n\ast ⟨z_n⟩$. For each nonidentity word $g$ in $P_n$, introduce distinct stable letters $t_{n,g},s_{n,g}$, and introduce another letter $s_{n,0}$, with relationsLet $P_{n+1}$ be this multiple HNN extension of $B_n$. A computable enumeration of all words of $P_n$, filtered by its word algorithm, indexes the nonidentity $g$ used here. Repeated representatives of the same element cause no difficulty: their stable letters are simply distinct.

Every associated subgroup in these relations is infinite cyclic. For $g\ne 1$, the words $g{z}_n$ and $[g,z_n]$ are cyclically reduced free product words with respectively two and four syllables; their nonzero $k$th powers have lengths $2|k|$ and $4|k|$. Therefore the reduced syllable length of an input bounds the finitely many possible exponents needed to decide membership in each subgroup and find the exponent. Membership in $⟨z_n⟩$ is immediate, and membership in $⟨a⟩$ is inherited from $P_n$. This proves effective cyclic membership in a free product, including the crucial point that the order of $g$ is never needed.

By Britton's lemma, $B_n$ embeds in $P_{n+1}$. To solve its word problem, repeatedly find a pinch in an HNN extension using these membership algorithms, transport the known exponent across its defining isomorphism, and remove two stable letters. With no pinch left, a word retaining stable letters is nontrivial and not in the base; otherwise the base word algorithm applies. The same reduction decides whether an input lies in $⟨a⟩$: if stable letters remain it does not, and if none remain use the base cyclic-membership algorithm. This verifies the inductive effectiveness claims rather than asserting that HNN extensions automatically preserve decidable word problem. Only the finitely many stable letters in the input need inspection.

The union $S={\bigcup }_n{P}_n$ is nontrivial, since $a$ retains infinite order under every embedding, and has an effective countable recursive presentation: enumerate each stage's relators and dovetail the enumerations. We now prove simplicity. Let $D◃S$ contain $g\ne 1$, and take a stage with $g\in P_n$. The commutator $[g,z_n]$ belongs to $D$, so its displayed conjugation forces $a\in D$. Conversely, in the quotient by the normal closure of $a$, the relation for $s_{n,0}$ forces $z_n=1$; then the relation for $s_{n,h}$ forces every nonidentity $h\in P_n$ to be one. Thus the normal closure of $a$ contains each $P_n$. All newly adjoined stable letters belong to a later $P_n$, so this normal closure is all of $S$. Hence $D=S$, proving that $S$ is a simple group containing $G$.

Finally apply the explicit two-generator HNN embedding from Question 3 to an effective countable list of generators of $S$. Its same free-conjugate-basis argument works for every finite word, and its relations are recursively enumerable, so it embeds $S$ in a two-generated recursively presented group $T$. The Higman embedding theorem embeds $T$ in a finitely presented group $P$. Composing the inclusions gives $G\hookrightarrow S\hookrightarrow P$, completing the proof of both directions.