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
a1...an
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>.