Presentation of A Group - Definition

Definition

Let S be a set and let F_S be the free group on S. Let R be a set of words on S, so R naturally gives a subset of F_S. To form a group with presentation <S|R>, the idea is to take F_S quotient by the smallest normal subgroup such that each element of R gets identified with the identity. Note that R might not be a subgroup, let alone a normal subgroup of F_S, so we cannot take a quotient by R. The solution is to take the normal closure N of R in F_S. The group <S|R> is then defined as the quotient group

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 G is isomorphic to <S|R>.

It is a common practice to write relators in the form = where and are words on . 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. in the list of relators is equivalent with . Another common shorthand is to write for a commutator .

A presentation is said to be finitely generated if is finite and finitely related if 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 is indexed by a set 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 to the natural numbers, such that we can find algorithms that, given, calculate, and vice versa. We can then call a subset of recursive (respectively recursively enumerable) if is recursive (respectively recursively enumerable). If is indexed as above and 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 recursively enumerable then it has another one with recursive.

For a finite group, the multiplication table provides a presentation. We take to be the elements of and 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 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.