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={x*_{1},...,x_{n}}
then we we write

*<x*_{1},...,x_{n}> =
<{x_{1},...,x_{n}}>

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 *D*_{4}.

Recall that this group consists of the elements

*
{ 1, r, r*^{2}, r^{3}, s, rs, r^{2}s, r^{3}s }

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: *r*^{4} = 1, s^{2} = 1, sr=r^{-1}s (*)

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

*r*^{i}s^{j} and

*r*^{n}s^{m}
the rules in (*) again suffice.
For example to multiply

*rs.r* we use

*sr=r*^{-1}s and we get

*rs.r = r.r*^{-1}s = 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

*
s*_{1}....s_{n} where each *s*_{i} 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^{-1}aa, 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*^{-1}a
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

*w*_{0}.
For example

*
baa*^{-1}b^{-1}a^{-1}bb^{-1}
--> bb^{-1}a^{-1}bb^{-1}
--> a^{-1}bb^{-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

*w*_{0}=v_{0}.
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=w*_{0}. 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

*
a*_{1}...a_{n}

with each

*a*_{i} in

*S U S*^{-1}.
We just define

*h(x)=h(a*_{1})...h(a_{n})
with each of the

*h(a*_{i}) 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, *r*_{i}, 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 *r*_{i}=1.

For example,
the group with generators: *r* and *s*
and relations: *r*^{4} = 1, s^{2} = 1, rsrs=1
is isomorphic to the Dihedral group *D*_{4}.

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