Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 2 / 4

The Higman embedding theorem says that a finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group, that is, a presentation on finitely many generators with a recursively enumerable set of relators. We use its embedding direction as an assumed theorem. The reverse direction follows by expressing subgroup generators as words in the larger group and enumerating finite products of conjugates of its relators and their inverses; comparison after free reduction enumerates all null words in the subgroup. This is the enumerable identities of finitely generated subgroups argument. The theorem does not assume that the recursively presented group's word problem for a group is decidable.

Take a recursively enumerable set $S\subseteq {\mathbb{N}}_{>0}$ that is not recursive, for example the diagonal halting set from Question 2 shifted by one. To obtain a finitely generated group with recursive presentation but undecidable word problem for a group, first define the countable Right-angled Artin groupTranslation of the indices gives an automorphism $a_i\mapsto a_{i+1}$. The semidirect product with its infinite cyclic shift is generated by $a=a_0,t$ and has presentationTo verify this presentation, the semidirect product satisfies its relators, while the reverse map sends $a_i$ to $t^{i}a{t}^{-i}$; all translated commutation relations follow by conjugation. These maps are inverse on their generators. Thus $B_S$ embeds in $G_S$.

For $n\in S$, the word $[a_0,a_n]$ is trivial. For $n\notin S$, map $a_0,a_n$ to the free generators $x,y$ of $F(x,y)$ and every other $a_i$ to one. Every defining commutator of $B_S$ maps to one, since the only possible relation involving both surviving generators would have separation $n$, which is absent. The resulting group homomorphism sends $[a_0,a_n]$ to the nontrivial reduced word $[x,y]$. HenceThis proves the shift-invariant graph groups encode arbitrary sets construction rather than supposing that a missing relator automatically means a nontrivial word. A word algorithm for $G_S$ would decide $S$, so none exists. Since $S$ is enumerable, the displayed two-generator presentation is a recursive presentation of a group. By the Higman embedding theorem, $G_S$ embeds in a finitely presented group $G_0$. A word algorithm for $G_0$, composed with substitution of the two fixed generator-image words, would solve the word problem for $G_S$. Therefore $\boxed{G_0\text{ is finitely presented with insoluble word problem}}$.

Write $R=⟨⟨r_j:j\in J⟩{⟩}_F$ and let $\pi :F\to G_0=F/R$ be the quotient group homomorphism. The subgroup in the question is exactly the fiber product of groupsEvery specified generator belongs to the right-hand side, so one inclusion is immediate. For the reverse inclusion, diagonal generator pairs produce $(u,u)$ for every $u\in F$. Alsoso their products and inverses produce $(1,r)$ for every $r\in R$. If $\pi (u)=\pi (v)$, then $u^{-1}v\in R$ and $(u,v)=(u,u)(1,u^{-1}v)\in H$, proving equality.

In particular $\boxed{(1,w)\in H⟺w\in R⟺w=1\text{ in }{G}_0}$. Constructing the input pair $(1,w)$ is effective, so a solution of the membership problem for a subgroup $H\le F\times F$ would solve the insoluble word problem for a group in $G_0$. The subgroup membership problem is therefore undecidable. This is the Mihailova subgroup construction; its finite generating set follows from the finiteness of $X,J$.