Higman's embedding theorem
In group theory, Higman's embedding theorem states that every finitely generated recursively presented group R can be embedded as a subgroup of some finitely presented group G. This is a result of Graham Higman from the 1960s.
On the other hand, it is an easy theorem that every finitely generated subgroup of a finitely presented group is recursively presented, so the recursively presented finitely generated groups are exactly the finitely generated subgroups of finitely presented groups.
Since every countable group is a subgroup of a finitely generated group, the theorem can be restated for those groups.
As a corollary, there is a universal finitely presented group that contains all finitely presented groups as subgroups ; in fact, its finitely generated subgroups are exactly the finitely generated recursively presented groups.
Higman's embedding theorem also implies the Novikov-Boone theorem about the existence of a finitely presented group with algorithmically undecidable word problem. Indeed, it is fairly easy to construct a finitely generated recursively presented group with undecidable word problem. Then any finitely presented group that contains this group as a subgroup will have undecidable word problem as well.
The usual proof of the theorem uses a sequence of HNN extensions starting with R and ending with a group G which can be shown to have a finite presentation.
