Decision Problems for Finitely Presented Groups

Because the relator language of the recursive presentation is recursively enumerable, there is a procedure that lists all relator words in $R$ and hence also all pairs $(r,\epsilon )$ with $r\in R$ and $\epsilon \in \{1,-1\}$. By dovetailing over lengths, one can therefore enumerate all finite lists of conjugators and signed relators.

First freely reduce the input word $w$ to a reduced word $\bar{w}$. For each finite list from step 1.1, form the corresponding product of conjugates from [L2] and freely reduce it in the ambient free group. Whenever the result is $\bar{w}$, accept. If $w$ is trivial in the presented group, then [L1] and [L2] supply a relator expression representing the same free-group element as $w$, so its free reduction is $\bar{w}$ and the search eventually halts; if $w$ is nontrivial, the search may run forever.

Hence the trivial words are exactly the words on which this procedure halts, so they form a recursively enumerable language.

By [L1], it is enough to show that each single Tietze transformation preserves solvability of the word problem.

A relator-addition or relator-deletion Tietze move does not change which words are trivial in the presented group, by the equality criterion [L2]. So the same decision procedure works before and after such a move.

A generator-addition move introduces one new generator $y$ together with a defining word $u(X)$. To decide whether a word in the enlarged alphabet is trivial, replace each $y^{\pm 1}$ by $u(X{)}^{\pm 1}$ and run the original algorithm on the resulting word. The inverse generator-deletion move is the same transport in the opposite direction.

Every finite Tietze chain transports a decision procedure step by step, so solvability for $\mathcal{P}$ is equivalent to solvability for $\mathcal{Q}$.

Repeatedly apply the elementary cancellations of [L1] until no adjacent inverse pair remains. Because each cancellation shortens the word by two letters, the process halts after finitely many steps with a reduced word $r$.

The free group element represented by $w$ is the same as that represented by $r$, because step 1.1 used only the free-equivalence moves of [L1]. By [L2], the identity class has exactly one reduced representative, namely the empty word. Therefore $w$ represents the identity if and only if $r$ is empty.

The halting free-reduction procedure of step 1.1 therefore decides the word problem in $F(X)$.

In each factor, solvability of the word problem lets us compare any two words. Enumerating the words in shortlex order therefore computes a canonical representative for every group element, and in the amalgam case it also computes the least representative of every left coset of $K$: two words represent the same left coset exactly when their quotient lies in the embedded copy of $K$, which is decidable by hypothesis. The extra hypothesis also makes every factor word that represents an element of $K$ effectively translatable into a canonical word in the fixed generators of $K$.

For an input alternating word in the generators of the factors, first replace each factor block by its canonical representative. Whenever two consecutive blocks lie in the same factor, multiply them there and recanonize. In the amalgam case, if a block lies in the amalgamating subgroup, step 1.1 translates it to the canonical $K$-word and then into the generators of the opposite factor, so the amalgam relation pushes it across the next syllable effectively. The computable coset representatives from step 1.1 ensure that each such rewrite strictly shortens the syllable length.

The reduction process of step 2.1 halts with the normal form from [L1]. By uniqueness in [L1], the input represents the identity exactly when the final normal form has length zero and terminal $K$-part equal to the identity. Hence the procedure decides the word problem in $G{\ast }_{K}H$.

Taking $K=\{e\}$ gives the free-product case, so both clauses follow.

Because $w$ is null, the admissible lengths in [L1] form a nonempty subset of $\mathbb{N}$: every relator expression for $w$ contributes one such length, and the empty product contributes the value $0$ in the boundary case.

Every nonempty subset of $\mathbb{N}$ has a least element. Applying this to the set of admissible lengths from step 1.1 gives a least $m$, and [L1] defines that least number to be ${\mathrm{Area}}_{\mathcal{P}}(w)$.

Hence the minimal algebraic relator area exists for every null word.

Enumerate binary strings first by length, then lexicographically, starting with the empty string as index zero. Both the indexing and its inverse are computable by finite scans. Let $S\subseteq \mathbb{N}$ be the indices of the halting language from [L1]. Dovetail its recognizer on all strings to enumerate $S$. A decider for $S$ would decide the halting language by computing an index. Hence $S$ is enumerable and undecidable.

In $F(a,b)$ put $u_i=a^{-i}b{a}^i$ for $i\in \mathbb{N}$. A nonempty reduced word in the formal symbols $u_i^{\pm 1}$ can be collected as $u_{i_1}^{e_1}\cdots u_{i_r}^{e_r}$ with $e_j\mathrm{\ne }0$ and adjacent indices distinct. Its expansion is $a^{-i_1}{b}^{e_1}{a}^{i_1-i_2}{b}^{e_2}\cdots a^{i_{r-1}-i_r}{b}^{e_r}{a}^{i_r}\mathrm{.}$ Every interior power of $a$ is nonzero and every displayed power of $b$ is nonzero, so this is a nonempty reduced word after omitting any zero end power. Thus the $u_i$ freely generate their subgroup. In particular $u_j$ lies in $U=⟨u_i:i\in S⟩$ exactly when $j\in S$: otherwise equality with a word on the selected basis elements would give a nonempty reduced relation.

In the disjoint free group $F(c,d)$ put $v_i=c^{-i}d{c}^i$ and $V=⟨v_i:i\in S⟩$. The same proof applies, and $u_i\mapsto v_i$ for $i\in S$ extends to an isomorphism $U\to V$. By [L4], amalgamating this isomorphism gives the recursive presentation ${\mathcal{P}}_S=⟨a,b,c,d\mid a^{-i}b{a}^i{c}^{-i}{d}^{-1}{c}^i,i\in S⟩\mathrm{.}$ Its relators can be listed by the enumeration in step 1.1.

Set $w_j=u_j{v}_j^{-1}$. If $j\in S$, then $w_j=1$ by its defining relation. If $j\mathrm{\notin }S$, step 2.1 and its counterpart for $V$ put the two factors outside the amalgamated subgroup, so [L4] makes $w_j\mathrm{\ne }1$. The required coset transversals exist without a choice axiom: order the finite-alphabet reduced words by length and then lexicographically, and take the unique least word in each coset. This selection need not be computable; it is only used for the normal-form proof. Rewriting either non-subgroup factor in these transversals gives a nonidentity representative, and absorbing the intervening subgroup element into the other factor leaves that factor outside its subgroup, yielding a positive-length normal word. Thus $w_j{=}_{{\mathcal{P}}_S}1⟺j\in S\mathrm{.}$

The map $j\mapsto w_j$ is computable by writing the four indicated powers. A word-problem decider for this one presentation would therefore decide $S$, contrary to step 1.1. Yet its trivial words are enumerable by [L2] and step 3.1. This presentation is the required counterexample. Its relator list is allowed to be infinite, as the Statement imposes no finite-presentation hypothesis.

Tietze-equivalent finite presentations present the same group, so [L1] applies to them.

Hence either both word problems are solvable or neither is. They cannot differ, so the statement is false.