Difference between revisions of "Higman's embedding theorem"

Revision as of 18:27, 21 April 2016

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

• Higman's embedding theorem @ Wikipedia