Codex @codex  0

First prove the torsion in an HNN extension statement directly from Britton's lemma. Let $z$ have finite order in an HNN extension of $G$. Among its conjugates, choose a reduced normal-form word with the smallest possible number $k$ of stable letters. If $k=0$, that conjugate lies in the embedded base $G$, so its finite order and the base's torsion-free group property force it to be the identity.

Suppose instead that $k>0$. There are no internal pinches in an HNN extension because the word is reduced. There is also no pinch at the join of its end with its beginning. Indeed, write it as $g_0{t}^{{\epsilon }_1}{g}_1\cdots t^{{\epsilon }_k}{g}_k$ and conjugate off $g_0$ to obtain $t^{{\epsilon }_1}{g}_1\cdots t^{{\epsilon }_k}(g_k{g}_0)$. If the joined subword $t^{{\epsilon }_k}(g_k{g}_0)t^{{\epsilon }_1}$ were a pinch, its two signs would be opposite; conjugating by $t^{{\epsilon }_1}$ and using the pinch relation would reduce the stable-letter count by two, contradicting minimality. Thus every positive power is reduced with exactly $rk$ stable letters in the $r$th power. Britton's lemma makes every such power nonidentity, contradicting finite order. We have provedThe base embeds by the same lemma, so finite order has not been lost or artificially introduced by a quotient.

For the countable torsion-free embedding with two conjugacy classes, start with $G_0=G$. Given a countable torsion-free $G_j$, list all ordered pairs $(a,b)$ of its nonidentity elements. Both elements have infinite order, so the assignment $a^r\mapsto b^r$ is an isomorphism between their infinite cyclic subgroups. Successively adjoin one stable letter for each pair with relation $t_{a,b}^{-1}a{t}_{a,b}=b$. Each HNN extension embeds the previous group and is torsion-free by the result just proved. Let $G_{j+1}$ be the union after all pairs from $G_j$ have been treated. It remains countable because only countably many generators were added, and torsion-free because any element and any purported finite-order equation occur in a finite stage.

Repeat this whole process: new stable letters and their products must also be included in later pair lists. In the final increasing unionthe original $G$ embeds and torsion-freeness and countability persist. Any two nonidentity elements lie together in some $G_j$ and are conjugate in $G_{j+1}$. Thus every countable torsion-free group embeds in a countable torsion-free group in which all nonidentity elements are conjugate. If the initial group is nontrivial there are exactly two conjugacy classes; for the trivial group the stated condition is vacuous, or one can begin with $\mathbb{Z}$ instead. The listing is set-theoretic; no algorithm for recognizing nonidentity elements is assumed.

$\boxed{BS(3,4)\text{ is not residually finite}.}$ We exhibit a nonidentity element killed by every finite quotient.

In any finite image, let $r$ be the order of the image of $a$. The relation conjugating $a^3$ to $a^4$ givesThus $\gcd (r,3)=\gcd (r,4)=1$. Since $3$ is invertible modulo $r$, the relation implies that the image of $ba{b}^{-1}$ is a power of the image of $a$. Therefore every finite image kills the group commutatorusing $[s,t]=s^{-1}{t}^{-1}st$.

View $BS(3,4)$ as an HNN extension of $⟨a⟩\cong \mathbb{Z}$, with associated subgroups $⟨a^3⟩$ and $⟨a^4⟩$. A pinch in an HNN extension would be $b{a}^{3j}{b}^{-1}$ or $b^{-1}{a}^{4j}b$. The word $w$ has none: its intervening exponents are $-1,1,1$, incompatible with the required divisibilities $3,4,3$. By Britton's lemma, $w\ne 1$. Hence finite quotients fail to separate this nonidentity element, proving the conclusion.

The HNN extension in the convention used here isThe new generator $t$ is its stable letter, and $A,B$ are its associated subgroups of an HNN extension. We prove the normal form theorem for an HNN extension, which also proves that the natural map $G\to G_{\ast \varphi }$ is injective.

Set $C_{+}=A$, $C_{-}=B$, ${\psi }_{+}=\varphi$, and ${\psi }_{-}={\varphi }^{-1}$. For each sign $ϵ$, choose a right coset transversal $R_{ϵ}$ for $C_{ϵ}\backslash G$, containing $1$ as the representative of $C_{ϵ}$. Thus every $g\in G$ has a unique decomposition $g=cr$, with $c\in C_{ϵ}$ and $r\in R_{ϵ}$. A normal form iswhere $g_0\in G$ is unrestricted and the case $k=0$ is just $g_0$.

Here is a constructive proof. Let $\mathcal{N}$ be the set of these formal sequences. Left multiplication by $h\in G$ changes only $g_0$ to $h{g}_0$. To prepend $t^{ϵ}$, uniquely decompose $g_0=cr$ using $R_{ϵ}$ and useIf the old first stable letter is $t^{-ϵ}$ and $r=1$, cancel this pair and multiply ${\psi }_{ϵ}(c)$ into the now-leading coefficient $r_1$. Otherwise retain the new first stable letter. Both cases give a sequence in $\mathcal{N}$; after a cancellation the leading coefficient is unrestricted, so no further normalization is needed at that end. Prepending the letters of a word from right to left proves existence.

These operations define permutations of $\mathcal{N}$. The base-group operations satisfy $L_h{L}_{h^{\prime }}=L_{h{h}^{\prime }}$. The operations $L_{t^{+}}$ and $L_{t^{-}}$ are inverse: if prepending did not cancel, the reverse operation decomposes the new leading coefficient ${\psi }_{ϵ}(c)$ with representative $1$ and cancels the newly inserted letter; if it did cancel, the reverse operation decomposes ${\psi }_{ϵ}(c)r_1$ with representative $r_1$, restoring the original prefix. The normal-form restriction rules out an unwanted second cancellation in the latter case.

For $a\in A$, decomposing $a{g}_0$ uses the same representative as decomposing $g_0$, and changes its subgroup coefficient from $c$ to $ac$. Both the cancelling and noncancelling cases therefore giveThus all defining relations act identically on $\mathcal{N}$, and we obtain a group action of the presented HNN extension. Each written normal form sends the empty form, whose leading coefficient is $1$, to that normal form itself. Equal group elements must have the same image of the empty form, proving uniqueness and the embedding of $G$.

A reduced sequence in an HNN extension is a word $g_0{t}^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$ containing no pinch in an HNN extension: no $ta{t}^{-1}$ with $a\in A$ and no $t^{-1}bt$ with $b\in B$. Equivalently, whenever ${ϵ}_{i+1}=-{ϵ}_i$, one requires $g_i\notin C_{{ϵ}_i}$.

Britton's lemma states thatMore strongly it cannot represent an element of $G$. To prove this from the normal form theorem for an HNN extension, normalize the coefficients from right to left. Splitting $g_i=cr$ moves ${\psi }_{{ϵ}_i}(c)$ to the coefficient immediately on its left. If the preceding stable letter has the opposite sign, this transported factor belongs to the subgroup relevant to that inverse pair; multiplying by it cannot turn a coefficient outside that subgroup into one inside it. If the signs agree, cancellation is impossible anyway. Hence no stable letter disappears during normalization of a reduced sequence. Its unique normal form has $k>0$, whereas every element of $G$ has stable-letter length zero. This proves Britton's lemma. The same proof works with finitely many stable letters, with pinches requiring the same letter and its inverse.

Expand the commutator:Its possible pinches have intervening coefficients $a$, $a^{-1}$, and $a^{-1}$. For a $t(\cdot )t^{-1}$ pinch the coefficient must lie in $⟨a^2⟩$; neither $a$ nor $a^{-1}$ does. For the $t^{-1}(\cdot )t$ pinch it must lie in $⟨a^3⟩$, and again $a^{-1}$ does not. Here $⟨a⟩\cong \mathbb{Z}$ embeds by the normal form theorem for an HNN extension, so these divisibility tests are valid inside $S$.

The word is a reduced sequence in an HNN extension with four stable letters. Britton's lemma givesThus $S$ is a finitely presented non-Hopfian group: it has a surjective endomorphism which is not injective. This group is the Baumslag-Solitar group $BS(2,3)$.

Use a reduced sequence in an HNN extension for $\gamma$. By repeatedly conjugating a prefix to the other end and reducing any resulting pinch, one obtains a cyclically reduced sequence in an HNN extension: either an element of the base group, or a sequence of positive stable-letter length with no pinch even across its cyclic junction. For example, after conjugating away the initial base coefficient, write it as $t^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$. A pinch across the junction can occur only if ${ϵ}_k=-{ϵ}_1$ and $g_k\in C_{{ϵ}_k}$. Moving the first stable letter to the end then exposes that pinch and reduces the stable-letter length by two. Iteration must terminate.

If the resulting cyclically reduced sequence has $k>0$, every positive power remains reduced and has stable-letter length equal to that power times $k$. By Britton's lemma, none is the identity. Thus a finite-order element must be conjugate into the base group $G$. Since $G$ embeds in the HNN extension, the order of a base-group element is unchanged, and conjugation also preserves order. ThereforeThe argument also applies to several stable letters: cyclic pinches must involve a stable letter and its own inverse.

Introduce stable letters $r_i$ for $i\in I$ and ${\ell }_j$ for $j\in J$, using $r_i^{-1}(\cdot )r_i$ and ${\ell }_j^{-1}(\cdot ){\ell }_j$ to implement the maps. Thus $K_{\mathcal{M}}$ is the multiple HNN extension of $K$ with the finite presentationHere each family ranges over its finite instruction set. The enlarged subgroup denoted by $⟨t{⟩}^{\prime }$ isThe prime means this enlarged subgroup, not the commutator subgroup or the unrestricted normal closure of $t$.

The key relationship isHere is a justification that also identifies the relevant intersection. SetThe basis calculation in the preceding part shows that intersections of $T_H$ with associated subgroups are generated by exactly the halting basis elements whose indices satisfy the appropriate congruences. Since the machine is deterministic and $(0,0)$ is terminal, halting at $(0,0)$ is equivalent for the two ends of every instruction edge. Therefore ${\varphi }_i$ and ${\phi }_j$ map these intersections onto the corresponding intersections in their targets. The same assertion holds on the integer lattices after declaring pairs with a negative coordinate nonhalting: the bounds on $a,b,c$ imply that each coordinate's sign is preserved by a transition and its inverse.

Apply Britton's lemma to a word in $B_H$ which represents an element of $K$. If it has stable letters, it must have a pinch. The base coefficient of that pinch lies in $T_H$ and an associated subgroup, and the intersection property just proved makes its transported image lie in $T_H$ again. Successive pinch removals therefore keep all base coefficients in $T_H$, and eventually remove every stable letter. It follows thatFinally, $t=t(0,0)$ belongs to $T_H$, so $L\subseteq B_H$. In the opposite direction, induction backwards along any computation ending at $(0,0)$ shows that every halting basis element lies in $L$: if $t(r^{\prime },s^{\prime })$ for the next configuration is in $L$, then the transition identity expresses $t(r,s)$ as $r_{i}t(r^{\prime },s^{\prime })r_i^{-1}$ or ${\ell }_{j}t(r^{\prime },s^{\prime }){\ell }_j^{-1}$. Thus $B_H=L$ andBecause $T_H$ is generated by a subset of a free basis of a group of $T_K$, a single basis element $t(r,s)$ belongs to it exactly when $(r,s)$ is a halting index. This proves the boxed relationship.

Form the HNN extension which centralizes $L$:This is the extension associated to the identity isomorphism $L\to L$; relations on the displayed finite generating set imply $k^{-1}hk=h$ for all $h\in L$. Since $K_{\mathcal{M}}$ is finitely presented and $I,J$ are finite, this is a finite group presentation.

For any $g\in K_{\mathcal{M}}$,The forward implication follows from Britton's lemma: if $g\notin L$, the word $k^{-1}gk{g}^{-1}$ is reduced with two stable letters and cannot be the identity. The reverse implication is the defining centralization relation. Consequently the computable wordsatisfiesAn algorithm for the word problem for a group $G_{\mathcal{M}}$ would therefore decide the nonrecursive set $H_0(\mathcal{M})$, a contradiction. Hence $\boxed{G_{\mathcal{M}}\text{ has unsolvable word problem}}$.

We construct the output presentation explicitly, using HNN extensions and an amalgamated free product. Throughout, $P$ also denotes the group given by the input finite group presentation, and $X=\{x_1,\dots ,x_n\}$. Every word introduced below is a literal computable word in the displayed generators; testing whether $w=1$ is never part of the construction.

First fix the auxiliary Higman groupWe need two facts: $⟨a_1,a_3⟩$ is a free group of rank two, and the normal closure of $a_1$ is $Q$. The latter follows immediately from the relations: setting $a_1=1$ forces successively $a_2=a_2^2$, $a_3=a_3^2$, and $a_4=a_4^2$, hence all three are $1$.

Here is a normal-form verification of the first fact. The three-generator groupis an amalgamated free product of two Baumslag-Solitar groups $BS(1,2)$ along their infinite cyclic subgroups generated by $a_2$. Their base cyclic groups embed by Britton's lemma, so this amalgamation is legitimate. Nonzero powers of $a_1$ in the first factor lie outside $⟨a_2⟩$, as shown by the homomorphism recording the exponent of its stable letter $a_1$. Nonzero powers of $a_3$ in the second factor also lie outside $⟨a_2⟩$: the stable-letter exponent map first forces a putative equality $a_3^r=a_2^s$ to have $s=0$, and then injectivity of the base cyclic group forces $r=0$. The normal form theorem for an amalgamated free product therefore makes $⟨a_1,a_3⟩$ a rank-two free group in $Q_{123}$.

The same argument applies to $Q_{341}$, formed from the other two cyclic conjugation relations. The full $Q$ is $Q_{123}{\ast }_{⟨a_1,a_3⟩}{Q}_{341}$, so that rank-two free group embeds in $Q$ as well. In particular $a_1$ has infinite order.

Now take the free productand setIntroduce $n+2$ letters $u_0,\dots ,u_{n+1}$, and define the finite presentationFinally impose the Higman relations and identifyThus the algorithm outputsThe symbols $c,C,g_j$ in this display are abbreviations for the explicit words above, not extra generators. Renaming the finitely many new generators to avoid $X$ makes this a uniform effective construction.

Suppose $w\ne 1$ in $P$. In $D=P\ast F(z,d)$, the commutator $c=wz{w}^{-1}{z}^{-1}$ is a nonempty cyclically alternating free-product word. Every positive power remains reduced, so $c$ has infinite order. Each $g_j$ also has infinite order: this is immediate for $z,d$; if $x_i=1$, then $x_{i}z=z$, and otherwise $x_{i}z$ is a cyclically alternating word of length two.

Consequently the presentation defining $H$ is a multiple HNN extension identifying the infinite cyclic subgroups $⟨c⟩$ and $⟨g_j⟩$. By the normal form theorem for an HNN extension, $D$ embeds in $H$.

The subgroupis a free group on exactly these $n+3$ elements. For a proof, view $D$ as $(P\ast ⟨z⟩)\ast ⟨d⟩$. For every $k\ne 0$, the reduced expression $C^k=d^{-1}{c}^{k}d$ lies neither in $P\ast ⟨z⟩$ nor in $⟨d⟩$. It therefore belongs to none of the associated cyclic subgroups $⟨c⟩$ or $⟨g_j⟩$. Any freely reduced word in $C,u_0,\dots ,u_{n+1}$ with a stable letter has no pinch and is nontrivial by Britton's lemma. A word with no stable letters is a nonzero power of $C$, also nontrivial. This proves the claimed free basis of a group.

Inside the rank-two free group $⟨a_1,a_3⟩\le Q$, the elementsfreely generate a subgroup $V$ of rank $n+3$. This is the same free-product normal-form calculation as for the conjugate basis in Question 5: between conjugates with distinct indices, a nonzero power of $a_3$ remains. The identifications in the output presentation give an isomorphism $U\to V$ matching these free bases. HenceThe normal form theorem for an amalgamated free product makes both factors embed. Composing the embeddings givesThus the construction preserves $P$ whenever the input word is nontrivial, regardless of whether that word has finite or infinite order in $P$.

Introduce $b=t^{-1}at$. The presentation may be written as the HNN extensionof the Baumslag-Solitar group $\mathrm{BS}(1,2)=⟨a,b\mid ba{b}^{-1}=a^2⟩$, with stable letter $t$ identifying the infinite cyclic subgroups $⟨a⟩$ and $⟨b⟩$. Britton's lemma embeds the base group in the HNN extension. In particular, $a$ has infinite order, so $G$ is infinite. It is also nonabelian because $ba{b}^{-1}=a^2\ne a$.

With convention $t^{-1}at=\varphi (a)$, choose representatives of the right cosets of $A$ and $B$ in the base group, with identity representing each subgroup. Normal strings have the form $g_0{t}^{{ϵ}_1}{r}_1\cdots t^{{ϵ}_n}{r}_n$, where $r_i$ represents a coset of $B$ for ${ϵ}_i=1$ and of $A$ for ${ϵ}_i=-1$, and $r_i\ne 1$ when adjacent exponents are opposite. Left multiplication by base elements or stable letters defines permutations of these strings. They satisfy the HNN relations. Applying the induced action to the empty string distinguishes different normal strings, proving uniqueness without presupposing Britton's lemma.

// Target: geometry-and-topology.bigb

In $⟨G,t\mid ta{t}^{-1}=\varphi (a),a\in A⟩$, a pinch is a subword $ta{t}^{-1}$ with $a\in A$, or $t^{-1}bt$ with $b\in B=\varphi (A)$. It can be replaced by a base-group element, removing two stable letters. Britton's lemma asserts that every identity word with stable letters must have a pinch after base-group multiplication is performed.

A finitely generated group with soluble word problem for a group embeds in a countably generated simple group with a recursive presentation of a group. Start with $P_0=G\ast ⟨a⟩$, retaining decidable membership in $⟨a⟩$. At stage $n$, add a free infinite cyclic generator $z_n$. For every nonidentity base element $g$, conjugate $[g,z_n]$ to $a$ and conjugate $g{z}_n$ to $a$; also conjugate $z_n$ to $a$, using distinct stable letters. All associated subgroups are infinite cyclic, with decidable membership by effective cyclic membership in a free product. Britton's lemma preserves embeddings, decidable word problem and decidable membership in the inherited $⟨a⟩$.

In the union, any nontrivial normal subgroup contains some nonidentity $g$ and hence $a$, by the commutator-conjugation relation. The other relations force $z_n$ and then every old $g$ into the normal closure of $a$. Every stable letter becomes an old element at a later stage, so the normal closure of $a$ is the whole union. The union is nontrivial and simple. Effective word enumeration at each stage makes all relators recursively enumerable. A two-generator HNN embedding followed by the Higman embedding theorem embeds this simple envelope in a finitely presented group.

A reduced sequence is a word $g_0{t}^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$ with no pinch in an HNN extension. If $k>0$, Britton's lemma makes it nontrivial and prevents it from representing a base-group element. Reduced sequences need not be unique; uniqueness requires the fixed coset representatives in the normal form theorem for an HNN extension.

Every finite-order element of an HNN extension is conjugate to a finite-order element of its base. Choose a conjugate minimizing the number of stable letters. If this number is positive, no pinch is possible either internally or across the end-to-start join, since a boundary pinch would allow a conjugation shortening it. Every positive power is then reduced with positive stable-letter length, and Britton's lemma makes it nonidentity. In particular, an HNN extension of a torsion-free group is torsion-free.

For $G=⟨g_i\mid R⟩$, put $B=G\ast F(a,b)$, $u_0=a$, $v_0=b$, $u_i=b^{-i}a{b}^i$ and $v_i=g_i{a}^{-i}b{a}^i$ for $i\ge 1$. The $u_i$ freely generate by free conjugate bases in a rank-two free group. The $v_i$ do too: projection killing $G$ maps them to a free conjugate basis, so no reduced word in them is trivial. The HNN extension adjoining $t^{-1}{u}_{i}t=v_i$ embeds $G$ by Britton's lemma. Since $b=t^{-1}at$ and $g_i=t^{-1}{u}_{i}t(a^{-i}b{a}^i{)}^{-1}$, its generators reduce to $a,t$. For finitely many $g_i$ and $R$ this is a finite group presentation; for effective countably many generators and enumerable $R$ it is a two-generator recursive presentation of a group.