Higman's embedding theorem

Last updated

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. [1]

Group theory branch of mathematics that studies the algebraic properties of groups

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 axioms. Groups recur throughout mathematics, and the methods of group theory have influenced many parts of algebra. Linear algebraic groups and Lie groups are two branches of group theory that have experienced advances and have become subject areas in their own right.

Finitely generated group group G that has some finite generating set S so that every element of G can be written as the product of finitely many elements of the finite set S and of inverses of such element

In algebra, a finitely generated group is a group G that has some finite generating set S so that every element of G can be written as the combination of finitely many elements of the finite set S and of inverses of such elements.

Subgroup Subset of a group that forms a group itself

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 G if the restriction of ∗ to H × H is a group operation on H. This is usually denoted H ≤ G, read as "H is a subgroup of G".

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).

A corollary is a statement that follows readily from a previous statement.

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.

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. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G. If B is another finite generating set for G, then the word problem over the generating set B is equivalent to the word problem over the generating set A. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G.

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. [2]

In mathematics, the HNN extension is an important construction of combinatorial group theory.

Related Research Articles

Abelian group group whose group operation is commutative

In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, these are the groups that obey the axiom of commutativity. Abelian groups generalize the arithmetic of addition of integers. They are named after early 19th century mathematician Niels Henrik Abel.

Simple group

In mathematics, a simple group is a nontrivial group whose only normal subgroups are the trivial group and the group itself. A group that is not simple can be broken into two smaller groups, namely a nontrivial normal subgroup and the corresponding quotient group. This process can be repeated, and for finite groups one eventually arrives at uniquely determined simple groups, by the Jordan–Hölder theorem.

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 a set R of relations among those generators. We then say G has presentation

Finite group mathematical group based upon a finite number of elements

In abstract algebra, a finite group is a group, of which the underlying set contains a finite number of elements.

In geometric topology, a field within mathematics, the obstruction to a homotopy equivalence of finite CW-complexes being a simple homotopy equivalence is its Whitehead torsion which is an element in the Whitehead group . These concepts are named after the mathematician J. H. C. Whitehead.

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively determined. A theory in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership can exist for them.

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 group.

In mathematics, one method of defining a group is by an absolute presentation.

In mathematics, a Hopfian group is a group G for which every epimorphism

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.

In the mathematical subject of group theory, the rank of a groupG, denoted rank(G), can refer to the smallest cardinality of a generating set for G, that is

In abstract algebra, the focal subgroup theorem describes the fusion of elements in a Sylow subgroup of a finite group. The focal subgroup theorem was introduced in and is the "first major application of the transfer" according to. The focal subgroup theorem relates the ideas of transfer and fusion such as described in. Various applications of these ideas include local criteria for p-nilpotence and various non-simplicity criterion focussing on showing that a finite group has a normal subgroup of index p.

In the mathematical subject of group theory, the Adian–Rabin theorem is a result which states that most "reasonable" properties of finitely presentable groups are algorithmically undecidable. The theorem is due to Sergei Adian (1955) and, independently, Michael O. Rabin (1958).

In mathematics, the Muller–Schupp theorem states that a finitely generated group G has context-free word problem if and only if G is virtually free. The theorem was proved by David Muller and Paul Schupp in 1983.

References

  1. ↑ Graham Higman, Subgroups of finitely presented groups. Proceedings of the Royal Society. Series A. Mathematical and Physical Sciences. vol. 262 (1961), pp. 455-475.
  2. ↑ 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   978-3-540-41158-1
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.