When we use computers to calculate things about groups we very often describe our groups by generators and relations. There are some ideas in common with generators and relations for algebras but the case of groups is really quite different becuase of the cancellations we get from inverses. Let's give some definitions. Let S be a subset of a group G. We write <S> for the smallest subgroup of G that contains the subset S and call this the subgroup generated by S. Write
S-1 = {s-1: s in S}
Then a typical element of <S> is a product of a finite number of elements from S U S-1. If S is finite, say S={x1,...,xn} then we we write
<x1,...,xn> = <{x1,...,xn}>
for short. For example <x> is the cyclic subgroup generated by x consisting of the powers of x. We say the subset S generates G (and that S is a generating set) if G=<S>. A relation in G is an equation of the form r = 1, with r some product in G.

Let's think about an example, the Dihedral group of symmetries of the square D4.

Recall that this group consists of the elements

{ 1, r, r2, r3, s, rs, r2s, r3s }
See Dihedral group for which symmetries these actually are but for now the only important thing is that
The group has generators: r and s
It has relations: r4 = 1, s2 = 1, sr=r-1s (*)
Now suppose that we wanted to write out the multiplication table of the Dihedral group. Suppose that we know nothing about Dihedral group except the generators and relations above. Just from these rules we can see that the elements of the group are as described above. Furthermore to multiply two arbitrary elements risj and rnsm the rules in (*) again suffice. For example to multiply rs.r we use sr=r-1s and we get
rs.r = r.r-1s = s
This is important if we want to compute things on the computer because we have reduced calculation in the group to something that doesn't depend on any knowledge of the elemnts of the group at all, we just need to know generators and relations.

At this point we would like to be able to formulate the idea of a group given just by generators and relations. To do this we need the idea of the free group. Since there is only one binary operation in a group, as opposed to two for an algebra, this ought to be simpler than the free algebra. But in fact it is a little more involved. The reason for this is cancellation can occur whenever a group element and its inverse are grouped together in a product.

Start with an arbitary set S. We are going to form the free group on S. Let S-1 be a set in one-one correspondence with S but has no elements in common with S. If s is in S we use the notation s-1 for the corresponding element in S-1. Of course, this notation is not accidental, S-1 is going to represent inverse elements. A word is a formal expression

s1....sn where each si is in S U S-1.
By convention we write 1 for the empty word. Let H denote the set of all such formal expressions. We can define a binary operation on H in the obvious way namely v.w=vw. Just stick the words together. But H is not the right candidate for the free group. The problem is that there are two many things in H that are distinct but really ought to be equal. For example if a is in S then
aaa-1, a-1aa, a
are all different elements of H but it seems natural to be able to cancel the products of an element and its inverse. So given a word w in H we do all possible cancellations of aa-1 or a-1a with a in S to obtain a new word in which cancellations are no longer possible. This new word is called the reduced form of w and is denoted by w0. For example
baa-1b-1a-1bb-1 --> bb-1a-1bb-1 --> a-1bb-1 --> a-1
Obviously, it may be possible to do these cancellations in several different ways. But a short induction based on word length shows that the reduced form obtained is always the same. It follows that we get an equivalence relation on H if we define w R v iff w0=v0. It is now easy to see (by cancelling to reduced words) that if w R w' and v R v' then wv R w'v', that is the product of equivalent words is equivalent.

Let G be the set of equivalence classes of elements of H. If w is in H write w for its equivalence class. Thus w=w0. Now define a binary operation on G by

w.v = wv
We know that this is well-defined from the above discussion. It is easy to see that this makes G into a group with identity element 1 and with w-1=w-1. G is called the free group on S. The free group has a universal property (which defines it up to unique isomorphism). Let i:S-->G be the natural injection that maps an element a to a.

Theorem Let A be a group and let f:S-->A be a function. Then there exists a unique group homomorphism h:G-->A such that f=hi.

Proof: This is fairly obvious. First of all if a in S then we define h(a)=f(a) and likewise h(a-1)=f(a)-1 An element x of G looks like

with each ai in S U S-1. We just define h(x)=h(a1)...h(an) with each of the h(ai) defined as above. It is easy to see that this is a well-defined homomorphism with the required property.

Now we can define precisley what we mean by generators and relations. Start as before with a set S and form G the free group on S. Now suppose that we are given some elements of the free group, ri, for i in some index set I. Then we can form the normal subgroup N of G that they generate. This is the smallest normal subgroup that contains these elements. The quotinet group G/N is the group given by generators S and relations ri=1.

For example, the group with generators: r and s and relations: r4 = 1, s2 = 1, rsrs=1 is isomorphic to the Dihedral group D4.

The usual notation for the group given by generators S and relations R is <S|R>.