View source for Higman's embedding theorem

'''Higman's embedding theorem''' is a theory in [[group theory]], by [[Graham Higman]].

== Description ==

The theory states that every finitely generated recursively presented group R can be embedded as a subgroup of some finitely presented group G.

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 (up to isomorphism) exactly the 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 (up to isomorphism).  In fact, its finitely generated subgroups are exactly the finitely generated recursively presented groups (again, up to isomorphism).

Higman's embedding theorem also implies the Novikov-Boone theorem (originally proved in the 1950s by other methods) 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.

== Proof ==

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.

== See also ==

* [[Computability theory]]
* [[Graham Higman]]
* [[Group theory]]
* [[Mathematics]]
* [[Recursion]]

==  External links ==

* [https://en.wikipedia.org/wiki/Higman%27s_embedding_theorem Higman's embedding theorem] @ Wikipedia