Higman embedding theorem

Remarks

One direction is easy. Let $G$ be generated by finitely many elements of a finitely presented group $P$. A program can list all consequences of the finitely many relators of $P$. So it can list all words in the generators of $G$ that equal $1$ in $P$. The other direction is the hard part of Higman's 1961 proof. It builds the finitely presented group by a long chain of HNN extensions and amalgamated free products that encode the enumeration of $R$.

Example: the wreath product $\Z \wr \Z$ has the presentation $\langle a, t \mid [a, t^n a t^{-n}] = 1 \text{ for } n \ge 1 \rangle$. The set of relators is computably enumerable, so $\Z \wr \Z$ embeds in a finitely presented group, although it is not finitely presented itself.

There are uncountably many $2$-generated groups up to isomorphism, but only countably many finitely presented groups, each with countably many finitely generated subgroups. So the hypothesis cannot be dropped: some finitely generated groups do not embed in any finitely presented group.

Going deeper

For a student

The theorem shows that there is a finitely presented group that contains every finitely presented group as a subgroup. It also gives another route to finitely presented groups with unsolvable word problem. Take a computably enumerable set of integers that is not computable. Encode it into the relators of a recursively presented group with unsolvable word problem, and embed this group in a finitely presented group. The word problem of the big group cannot be solvable, since it would solve the word problem of the subgroup.