# Proving undecidability of group isomorphism problem from an unsolvable word problem

From The Princeton Companion to Mathematics, IV Branches of Mathematics, pages 126-127:

Suppose that $$\Gamma = \langle A | R \rangle$$ is a finitely presented group with an unsolvable word problem, where $$A = \{ a_1,\ldots,a_n$$ and no $$a_i$$ equals the identity in $$\Gamma$$. For each word $$w$$ made out of the letters in $$A$$ and their inverses, define a group $$\Gamma_w$$ to have presentation $$\langle A,s,t|R,t^{-1}(s^i a_i s^{-i})t(s^i w s^{-i}),i =1,\ldots,n \rangle$$ It is not hard to show that if $$w =1$$ in $$\Gamma$$ then $$\Gamma_w$$ is the free group generated by $$s$$ and $$t$$. If $$w \neq 1$$, then $$\Gamma_w$$ is an HNN extension. In particular, it contains a copy of $$\Gamma$$, and hence has an unsolvable word problem, which means that it cannot be a free group. Thus, since there is no algorithm to decide whether $$w = 1$$ in $$\Gamma$$, one cannot decide which of the groups $$\Gamma_w$$ are isomorphic to which others.

I can't get why if $$w \neq 1$$, then $$\Gamma_w$$ contains a copy of $$\Gamma$$. I find that $$w^{-1}$$ and $$a_i$$s are conjugate in the because of the relators $$t^{-1}(s^i a_i s^{-i})t(s^i w s^{-i})$$, and I think in $$\Gamma_w$$ the subgroup generated by $$a_i$$s may not be isomorphic to $$\Gamma$$. Also, I can't see how $$\Gamma_w$$ is an HNN extension of some group.

PS: Please forgive me for possibly asking a stupid question. I don't know anything about combinatorial group theory. I just took a logic course and now reading some results of undecidable problems.

The important point is that $$\Gamma_w$$ is a HNN extension, i.e., an extension of $$\Gamma$$ (or rather of $$\Gamma$$ already freely extended by $$s$$) by a new element $$t$$ and using an isomorphism $$\alpha\colon H\to K$$ between two subgroups of $$\Gamma$$ two subgroups $$H,K$$ of $$\Gamma$$ in such a way that conjugation with $$t$$ applied to $$H$$ acts like $$\alpha$$; in other words, $$\langle\, S\mid R\,\rangle$$ becomes $$\langle\,S,t\mid R,\forall h\in H\colon t^{-1}ht=\alpha(h)\,\rangle$$. We clearly have a homomorphism $$\langle\, S\mid R\,\rangle\to \langle\,S,t\mid R,\forall h\in H\colon t^{-1}ht=\alpha(h)\,\rangle$$ by sending $$S$$ to itself. A priori, this need not be an injective homomoprhism, and it is not obvious that it should be, but it is the key result of the theory of HNN that it is indeed injective.
The subgroups $$H,K$$ we use here are two free subgroups on $$n$$ generators contained in $$\langle \Gamma,s\rangle$$, one generatied by $$s^ia_is^{-i}$$, $$1\le i\le n$$, and free because none of the $$a_i$$ is $$1$$, the other generated by $$s^iws^{-i}$$, $$1\le i\le n$$, and free because $$w\ne 1$$. The isomorphism $$\alpha$$ is just that sending $$s^ia_is^{-i}$$ to $$s^iw^{-1}s^{-i}$$ (the inverse because of the way the relation is written). As $$H,K$$ are free, it suffices to add the HNN relations for the generators only.
In total we have thus two injections $$\Gamma = \langle\,A\mid R\,\rangle\hookrightarrow\langle\,A,s\mid R\,\rangle\stackrel{\text{HNN}}\hookrightarrow\langle\,A,s,t\mid R,\forall i=1,\ldots, n\colon s^ia_is^{-i}=s^iw^{-1}s^{-i}\,\rangle=\Gamma_w$$ with $$H=\langle\,sa_1s^{-1},\ldots, s^na_ns^{-n}\,\rangle \cong F_n\cong \langle\,sws^{-1},\ldots, s^nws^{-n}\,\rangle=K.$$
• Thank you very much! I still have a question though. How can I show that the subgroups $H$ and $K$ in $\langle \Gamma,s\rangle$ are free? I mean, does there exist a torsion-free $\Gamma$ so $H$ and $K$ are indeed free? – 2.38423103 May 2 at 6:18
• @2.38423103 This is the same as the usual proof that all at most countably generated free groups embed in $F_2$. See e.g. math.hunter.cuny.edu/olgak/slides_lecture2part2.pdf. – Carl-Fredrik Nyberg Brodda May 12 at 17:57