Higman's Embedding Theorem
   HOME

TheInfoList



OR:

In
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 In mathematics, a presentation is one method of specifying a group (mathematics), group. A presentation of a group ''G'' comprises a generating set of a group, set ''S'' of generators—so that every element of the group can be written as a produ ...
''R'' can be embedded as a
subgroup In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation  ...
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 ...
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 (mathematics), set is countable if either it is finite set, 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 fro ...
group is a subgroup of a finitely generated group, the theorem can be restated for those groups. As a
corollary In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
, 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 group In mathematics, a presentation is one method of specifying a group (mathematics), group. A presentation of a group ''G'' comprises a generating set of a group, set ''S'' of generators—so that every element of the group can be written as a produ ...
s (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 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 ...
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 ...
s starting with ''R'' and ending with a group ''G'' which can be shown to have a finite presentation.
Roger C. Lyndon Roger Conant Lyndon (December 18, 1917 – June 8, 1988) was an American mathematician, for many years a professor at the University of Michigan.. He is known for Lyndon words, the Curtis–Hedlund–Lyndon theorem, Craig–Lyndon interpolation ...
and
Paul E. Schupp Paul Eugene Schupp (March 12, 1937 – January 24, 2022) was an American-born British professor emeritus of mathematics at the University of Illinois at Urbana Champaign. He is known for his contributions to geometric group theory, computational c ...
. ''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