Higman's embedding theorem
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.
≈ 2 min read
Higman's embedding theorem. encyclopegia.org, snapshot enwiki-001293499726. /a/higman-s-embedding-theorem
Names in other languages
- caTeorema d'incrustació de Higman
- EnglishHigman's embedding theorem
- eoplonĝo-teoremo de Higman
- DeutschHigmans Einbettungssatz
- 日本語Higman の埋め込み定理
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 finitely generated 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 extensions starting with R and ending with a group G which can be shown to have a finite presentation.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1293499726 under CC BY-SA 4.0; modifications have been made.