group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...

, Higman's embedding theorem states that every finitely generated recursively presented group ''R'' can be embedded as a

subgroup In group theory, a branch of mathematics, 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 some

finitely presented group In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...

''G''. This is a result of

Graham Higman Graham Higman FRS (19 January 1917 – 8 April 2008) was a prominent English mathematician known for his contributions to group theory. Biography Higman was born in Louth, Lincolnshire, and attended Sutton High School, Plymouth, winning a ...

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 finitely generated subgroups of finitely presented groups. Since every

countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...

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

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 In mathematics, the HNN extension is an important construction of combinatorial group theory. Introduced in a 1949 paper ''Embedding Theorems for Groups'' by Graham Higman, Bernhard Neumann, and Hanna Neumann, it embeds a given group ''G'' into an ...

s starting with ''R'' and ending with a group ''G'' which can be shown to have a finite presentation. Roger C. Lyndon and Paul E. Schupp. ''Combinatorial Group Theory.'' Springer-Verlag, New York, 2001. "Classics in Mathematics" series, reprint of the 1977 edition.

References

{{reflist Infinite group theory Theorems in group theory