Higman's embedding theorem
Encyclopedia
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 (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.
The usual proof of the theorem uses a sequence of HNN extension
s starting with R and ending with a group G which can be shown to have a finite presentation.
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
, Higman's embedding theorem states that every finitely generated recursively presented group R can be embedded as a subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of some finitely presented group G. This is a result of Graham Higman
Graham Higman
Graham Higman FRS was a leading British mathematician. He is known for his contributions to group theory....
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 (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
Corollary
A corollary is a statement that follows readily from a previous statement.In mathematics a corollary typically follows a theorem. The use of the term corollary, rather than proposition or theorem, is intrinsically subjective...
, 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
Word problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...
. 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 extension
HNN extension
In mathematics, the HNN extension is a basic construction of combinatorial group theory.Introduced in a 1949 paper Embedding Theorems for Groups by Graham Higman, B. H...
s starting with R and ending with a group G which can be shown to have a finite presentation.