Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 1 / 6

False. Take the finite, hence countable, cyclic group $C_6=⟨a\mid a^6=1⟩$. Its elements $a^3$ and $a^2$ have orders two and three. A group embedding preserves the order of every element, whereas conjugate group elements have the same order: $(s^{-1}xs{)}^r=s^{-1}{x}^{r}s$. Therefore their images cannot be conjugate in any containing group. This gives the required obstruction. The torsion-free group hypothesis in Question 5 avoids this conflict of element orders.

False: free rank is not monotone under subgroup embeddings. In fact every finite-rank free group embeds in $F_2$, hence in every $F_m$ with $m>1$. Let $a,b$ freely generate a rank-two subgroup and set $z_i=a^{i}b{a}^{-i}$ for $0\le i<n$.

To prove that these form a free basis of a group for their subgroup, take a nonempty reduced word and combine each maximal run with the same index into a block $z_{i_1}^{e_1}\cdots z_{i_r}^{e_r}$, with $e_j\ne 0$ and $i_{j+1}\ne i_j$. Its expansion isEvery interior $a$ power and every $b$ power is nonzero, so the free reduction leaves a nonempty word. This proves the conjugates of one free generator freely generate property and injectivity of $F_n\to F_m$. In particular,

False. We construct a two-generated countable group that cannot embed in any finitely presented group. Choose a subset $S\subseteq {\mathbb{N}}_{>0}$ which is not a recursively enumerable set, for example a positive-integer coding of the complement of the halting set. Such sets exist because there are only countably many finite programs but uncountably many subsets of the positive integers. On generators $b_i$ indexed by $i\in \mathbb{Z}$, form the possibly infinite-graph Right-angled Artin groupThe shift $\sigma (b_i)=b_{i+1}$ preserves the defining relations and has inverse shift $i\mapsto i-1$, so it is an automorphism. Form the semidirect productIts base embeds by the definition of a semidirect product. Since $b_i=t^i{b}_0{t}^{-i}$, the group is generated by just $b_0,t$ and is countable.

The shift-invariant graph groups encode arbitrary sets construction has the exact testThe forward direction for $n\in S$ is a defining edge relation. If $n\notin S$, kill all vertex generators except $b_0,b_n$. Every defining commutator then either contains a killed generator or is trivial; no relation is imposed between these two retained generators. Thus there is a retraction of $B_S$ onto the rank-two free group on $b_0,b_n$. Their commutator is a nonempty reduced word there, so it is nonidentity in $B_S$ and remains so in $G_S$.

Now suppose $G_S$ embedded in a finitely presented group $P$. Choose fixed words $u,v$ in its finite generators representing the images of $b_0,t$. The null words of $P$ are recursively enumerable: enumerate all finite products of conjugates of its relators and their inverses, then freely reduce. Substituting $u,v$ into $[b_0,t^n{b}_0{t}^{-n}]$ and dovetailing these enumerations for all $n>0$ would enumerate exactly $S$, contradicting its choice. These finitely many image words may be hard-coded; the argument does not require an algorithm finding an embedding. This proves the enumerable identities of finitely generated subgroups obstruction and supplies a concrete construction of the required countable counterexample.

True. Let $G=⟨X\mid R⟩$ and $H=⟨Y\mid S⟩$, using disjoint finite generating alphabets. The direct product of groups has finite presentationThe commuting relations let every word be reordered as a word in $X$ followed by a word in $Y$; the two projections then show that no additional relations within either factor are imposed. For an input word $w$, form its projections $w_X$ and $w_Y$ by deleting all letters from the other factor. Evaluate each projection with the given word problem for a group algorithm for that factor. The product coordinates giveBoth component algorithms halt, so this is a terminating algorithm. No subgroup-membership procedure or comparison between unknown presentations is required.

False. Use the two-generated group $G_S$ constructed in part (iii) for a non-recursively-enumerable $S$. Sending the two free generators to $b_0,t$ gives a surjective group homomorphismThe source is a finitely presented group, with presentation $⟨a,b\mid ⟩$. The target is not finitely presented: if it were, its null words could be enumerated from a finite set of relators, and the tested commutators would enumerate $S$, as proved in part (iii). Thus even a quotient of a rank-two free group need not admit a finite presentation. A quotient by a finitely normally generated kernel would be finitely presented, but the assertion places no such restriction on its kernel.

False, even when the HNN extension also has a finite presentation. Take the base $P=F_m\times F_m$ and its Mihailova subgroup $L$ from Question 4(b). Its word problem for a group is soluble: project a word to each free factor and freely reduce both projections, as in part (iv). The base is finitely presented, but the HNN extensionhas insoluble word problem by the explicit reduction in Question 4(b). Namely, for an input word $w$ in the presentation with insoluble word problem, set $p=(1,w)$; thenThe obstruction is undecidable membership in the associated subgroup, not undecidable equality in the base. Soluble base word problem alone does not let one recognize the pinches needed for a normal form theorem for an HNN extension algorithm.