Higman's embedding theorem
- 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". This is a result of Graham Higman from the 1960s. [ Graham Higman, "Subgroups of finitely presented groups." Proceedings of the Royal Society. Series A. Mathematical and Physical Sciences. vol. 262 (1961), pp. 455-475.]
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 extensions 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. ISBN-13: 9783540411581 ]
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Graham Higman — FRS (19 January 1917 ndash; 8 April 2008) was a leading British mathematician. He is known for his contributions to group theory. He earned his PhD from the University of Oxford in 1941. His thesis, The units of group rings , was written under… … Wikipedia
Graham Higman — (* 19. Januar 1917 in Louth in Lincolnshire; † 8. April 2008 in Oxford) war ein englischer Mathematiker, der sich mit Algebra, speziell der Gruppentheorie, beschäftigte. Graham Higman 1960 … Deutsch Wikipedia
List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… … Wikipedia
List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… … Wikipedia
Dehn function — In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group (that is a freely reduced word in the … Wikipedia
SQ universal group — In mathematics, in the realm of group theory, a countable group is said to be SQ universal if every countable group can be embedded in one of its quotient groups. SQ universality can be thought of as a measure of largeness or complexity of a… … Wikipedia
HNN extension — In mathematics, the HNN extension is a basic construction of combinatorial group theory.Introduced in a 1949 paper Embedding Theorems for Groups [ cite journal|title=Embedding Theorems for Groups|journal=Jornal of the London Mathematical… … Wikipedia
Word problem for groups — In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a recursively presented group G is the algorithmic problem of deciding whether two words represent the same element. Although it… … Wikipedia
Well-quasi-ordering — In mathematics, specifically order theory, a well quasi ordering or wqo is a well founded quasi ordering with an additional restriction on sequences that there is no infinite sequence x i with x i ot le x j for all i < j . Motivation We can use… … Wikipedia
Théorème de Robertson-Seymour — En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour (parfois également appelé le théorème des mineurs, et connu, avant qu il soit démontré, sous le nom de conjecture de Wagner), est un théorème démontré… … Wikipédia en Français
