In mathematics, one method of defining a group is by a presentation. One specifies a set S of generators so that every element of the group can be written as a product of some of these generators, and a set R of relations among those generators. We then say G has presentation Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... In abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses. ...

Informally, G has the above presentation if it is the "freest group" generated by S subject only to the relations R. Formally, the group G is said to have the above presentation if it is isomorphic to the quotient of a free group on S by the normal subgroup generated by the relations R. In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. ... In mathematics, given a group G and a normal subgroup N of G, the quotient group, or factor group, of G over N is intuitively a group that collapses the normal subgroup N to the identity element. ... The Cayley graph of the free group on two generators a and b In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many... In mathematics, a normal subgroup N of a group G is a subgroup invariant under conjugation; that is, for each element n in N and each g in G, the element g−1ng is still in N. The statement N is a normal subgroup of G is written: . There are...

As a simple example, the cyclic group of order n has the presentation In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na...

where e is the group identity.

Every group has a presentation, and in fact many; a presentation is often the most compact way of describing the structure of the group.

A closely related, but different concept, is that of an absolute presentation of a group. In mathematics, one method of defining a group is by an absolute presentation. ...

Background

A free group on a set S = {s_i} is a group where each element can be uniquely described as a finite length product of the form: The Cayley graph of the free group on two generators a and b In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many...

x₁^a₁ x₂^a₂ ... x_n^a_n

where each x_i is a member of S, and x_i ≠ x_i+1 for any i; and each a_i is any non-zero integer. In less formal terms, the group consists of words in the generators and their inverses, subject only to canceling a generator with its inverse.

If G is any group, and S is a generating subset of G, then every element of G is also of the above form; but in general, these products will not uniquely describe an element of G.

For example, the dihedral group D₈ can be generated by a rotation, r, of order 4; and a flip, f, of order 2; and certainly any element of D₈ is a product of r 's and f 's. This article may be confusing for some readers, and should be edited to enhance clarity. ...

However, we have, for example, r f r = f, r³ = r⁻¹, etc.; so such products are not unique in D₈. Each such product equivalence can be expressed as an equality to the identity; such as

r f r f = 1

r ⁴ = 1

f ² = 1

Informally, we can consider these products on the left hand side as being elements of the free group F = <r,f>, and can consider the subgroup R of F which is generated by these strings; each of which would also be equivalent to 1 when considered as products in D₈.

If we then let N be the subgroup of F generated by all conjugates x⁻¹ R x of R, then N is a normal subgroup of F; and each element of N, when considered as a product in D₈, will also evaluate to 1. Thus D₈ is isomorphic to the quotient group F/N. We then say that D₈ has presentation In mathematics, given a group G and a normal subgroup N of G, the quotient group, or factor group, of G over N is intuitively a group that collapses the normal subgroup N to the identity element. ...

Formal definition

Let S be a set and let <S> be the free group on S; that is the set of all words on S. Let R be a set of words on S, so R is a subset of <S>. To form a group with presentation <S|R> the idea is take the largest quotient of <S> so that each element of R gets identified with the identity element. Note that R may not be a subgroup, let alone a normal subgroup of <S>, so we cannot take a naive quotient by R. The solution is to take the normal closure N of R in <S>, which is defined as the smallest normal subgroup in <S> which contains R. The group <S|R> is then defined as the quotient group The Cayley graph of the free group on two generators a and b In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many... In group theory, given a group G under a binary operation *, we say that some subset H of G is 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 is a group... In mathematics, a normal subgroup N of a group G is a subgroup invariant under conjugation; that is, for each element n in N and each g in G, the element g−1ng is still in N. The statement N is a normal subgroup of G is written: . There are... In group theory, the conjugate closure of a subset S of a group G is the subgroup of G which is generated by the elements of S and their conjugates SG = {x &#8712; G | there exists g &#8712; G and s &#8712; S such that x = g&#8722;1sg}, The... In mathematics, given a group G and a normal subgroup N of G, the quotient group, or factor group, of G over N is intuitively a group that collapses the normal subgroup N to the identity element. ...

The elements of S are called the generators of <S|R> and the elements of R are called the relators. A group G is said to have the presentation <S|R> if it is isomorphic to <S|R>.

It is a common practice write relators in the form x = y where x and y are words on S. What this means is that . This has the intuitive meaning that the images of x and y are supposed to be equal in the quotient group. Thus e.g. rⁿ in the list of relators is equivalent with rⁿ = 1. Another common shorthand is to write [x,y] for a commutator xyx ^{− 1}y ^{− 1}. In mathematics, the commutator gives an indication of how poorly a certain binary operation fails to be commutative. ...

A presentation is said to be finitely generated if S is finite and finitely related if R is finite. If both are finite it is said to be a finite presentation. A group is finitely generated (respectively finitely related, finitely presented) if it has a presentation that is finitely generated (respectively finitely related, a finite presentation).

If S is indexed by a set I consisting of all the natural numbers or a finite subset of them, then it is easy to set up a simple one to one coding (or Gödel numbering) from the free group on S to the natural numbers, such that we can find algorithms that, given f(w), calculate w, and vice versa. We can then call a subset U of recursive (respectively recursively enumerable) if f(U) is recursive (respectively recursively enumerable). If S is indexed as above and R recursively enumerable, then the presentation is a recursive presentation and the corresponding group is recursively presented. This usage may seem odd, but it is possible to prove that if a group has a presentation with R recursively enumerable then it has another one with R recursive. In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input &#8212; typically an integer or a tuple of integers or a sequence of characters &#8212; eventually halts...

For a finite group G, the multiplication table provides a presentation. We take S to be the elements g_i of G and R to be all words of the form , where is an entry in the multiplication table. A presentation can then be thought of as a generalization of a multiplication table.

Every finitely presented group is recursively presented, but there are recursively presented groups that cannot be finitely presented. However a remarkable theorem of Graham Higman states that a finitely generated group has a recursive presentation if and only if it can be embedded in a finitely presented group. From this we can deduce that there are (up to isomorphism) only countably many finitely generated recursively presented groups. Bernhard Neumann has shown that there are uncountably many non-isomorphic two generator groups. Therefore there are finitely generated groups that cannot be recursively presented. Graham Higman (b. ... In mathematics the term countable set is used to describe the size of a set, e. ... Bernhard Neumann (15 Oct 1909 - 20 Oct 2002) was a German born mathematician who was one of the leading figures in group theory greatly influencing the direction of the subject. ... In mathematics, an uncountable set is a set which is not countable. ...

Examples

The following table lists some examples of presentations for commonly studied groups. Note that in each case there are many other presentations that are possible. The presentation listed is not necessarily the most efficient one possible.

To meet Wikipedias quality standards, this article or section may require cleanup. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... The icosahedral rotation group I with fundamental domain Apart from the two infinite series of prismatic and antiprismatic symmetry, rotational icosahedral symmetry or chiral icosahedral symmetry of chiral objects and full icosahedral symmetry or achiral icosahedral symmetry are the discrete point symmetries (or equivalently, symmetries on the sphere) with the... Cycle diagram of Q. Each color specifies a series of powers of any element connected to the identity element (1). ... In mathematics, in the sub-field of geometric topology, a Dehn twist is a certain type of self-homeomorphism of a surface (two-dimensional manifold). ... A torus. ...

Some theorems

Every group G has a presentation. To see this consider the free group <G> on G. Since G clearly generates itself one should be able to obtain it by a quotient of <G>. Indeed, by the universal property of free groups there exists a unique group homomorphism φ : <G> → G which covers the identity map. Let K be the kernel of this homomorphism. Then G clearly has the presentation <G|K>. Note that this presentation is highly inefficient as both G and K are much larger than necessary. In various branches of mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique morphism under certain conditions. ... Given two groups (G, *) and (H, ·), a group homomorphism from (G, *) to (H, ·) is a function h : G -> H such that for all u and v in G it holds that h(u * v) = h(u) · h(v) From this property, one can deduce that h maps the identity element... In the various branches of mathematics that fall under the heading of abstract algebra, the kernel of a homomorphism measures the degree to which the homomorphism fails to be injective. ...

Every finite group has a finite presentation.

The negative solution to the word problem for groups states that there is a finite presentation <S|R> for which there is no algorithm which, given two words u, v, decides whether u and v describe the same element in the group. In abstract algebra, the word problem for groups is the problem of deciding whether two given words of a presentation of a group represent the same element. ...

Free product

If G has presentation <S|R> and H has presentation <T|Q> with S and T being disjoint then the free product G * H has presentation <S,T|R,Q>. In abstract algebra, the free product of groups constructs a group from two or more given ones. ...

Direct product

If G has presentation <S|R> and H has presentation <T|Q> with S and T being disjoint then the direct product of G and H has presentation <S,T|R,Q, [S,T]>. Here [S,T] means that every element from S commutes with every element from T. In mathematics, one can often define a direct product of objects already known, giving a new one. ...

See also

• Cayley graph

The Cayley graph of the free group on two generators a and b In mathematics, a Cayley graph, named after Arthur Cayley, is a graph that encodes the structure of a group. ...

References

• Johnson, D. L. (1990). Presentations of Groups. Cambridge: Cambridge University Press. ISBN 0-521-37824-9. Schreier's method, Nielsen's method, free presentations, subgroups and HNN extensions, Golod-Shafarevitch theorem, etc.

• Coxeter, H. S. M; and Moser, W. O. J. (1980). Generators and Relations for Discrete Groups. New York: Springer-Verlag. ISBN 0-387-09212-9. This useful reference has tables of presentations of all small finite groups, the reflection groups, and so forth.