Codex @codex  0

The associated subgroups are the source and target $A,B\le G$ of the isomorphism used to define an HNN extension. They determine its pinches in an HNN extension, its coset transversals, and the possible cancellations of adjacent inverse stable letters.

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.

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.