# The Unapologetic Mathematician

## Generators and Relations

Now it’s time for the reason why free groups are so amazingly useful. Let $X$ be any set, $F(X)$ be the free group on $X$, and $G$ be any other group. Now, every function $f$ from $X$ into $G$ extends to a unique homomorphism $f: F(X)\rightarrow G$. Just write down any word in $F(X)$, send each letter into $G$ like the function tells you, and multiply together the result!

So what does this get us? Well, for one thing every group $G$ is (isomorphic to) a quotient of a free group. If nothing else, consider the free group $F(G)$ on the set of $G$ itself. Then send each element to itself. This extends to a homomorphism $f$ from $F(G)$ to $G$ whose image is clearly all of $G$. Then the First Isomorphism Theorem tells us that $G$ is isomorphic to $F(G)/{\rm Ker}(f)$. That’s pretty inefficient, but it shows that we can write $G$ like that if we want to. How can we do better?

In a moment we’ll need this little technical construction. Remember that not every subgroup is suitable as the kernel of a homomorphism — it needs to be normal. We can beef up any subgroup to a normal one in a straightforward way, though. First notice that the intersection of any collection of normal subgroups is a normal subgroup again (check it). Now if $G$ is a group with subgroup $H$, consider the collection of all normal subgroups of $G$ that contain $H$. There’s always at least one, since $G$ itself is an example. Now take their intersection and call it $N$. This is the smallest normal subgroup of $G$ containing $H$, since it’s contained in every other one. We call it the “normal closure” of $H$ in $G$.

Okay, so what we want is a free group $F$ and a normal subgroup $N$ of $F$ so that $G$ is isomorphic to $F/N$. By the previous paragraph, we can settle for any subgroup and take its normal closure to get our $N$. But this subgroup is a group in its own right, and is itself the image of some homomorphism from another free group $F'$.

Now we’re getting somewhere. Let $X$ and $Y$ be any two sets, so we have the free groups $F(X)$ and $F(Y)$. Now take a function from $Y$ to $F(X)$. This extends to a homomorphism, whose image is some subgroup of $F(X)$. Take the normal closure $N$ of this subgroup and get the quotient $F(X)/N$. We can get any group at all like this! We call the elements of $X$ “generators” and the words in the image of $Y$ “relations”.

The best situation is when a group is “finitely presented” — $X$ and $Y$ are finite sets. In this case we just have to write down the names of elements of $X$, the words on $X$ in the image of $Y$, and the machinery above gives us back a group. Quite a lot of groups arise like this. We write such a presentation as $$ for the $n$ generators $x_i$ and $r$ relations $w_j$.

• The cyclic group $\mathbb{Z}_n$ is $$.
• The symmetric group $S_n$ is $$.
• The free group $F_n$ is $$.

So this should provide a way to tell if groups are isomorphic, right? Wrong. You might think that you should be able to tell when two presentations give isomorphic groups, but in fact it’s known that there’s no way to tell in general. The hangup is in what’s called the “word problem” for a group: given a presentation of a group and a word on the generators, do the relations make the word correspond to the trivial element of the group? It’s known that there is no method that solves this problem for all groups, and that many groups have no method for solving it at all.

Still, presentations by generators and relations are extremely useful for understanding the structure of a given group. As for free groups we can specify a homomorphism from $G$ by defining it on a generating set, though now we have to check that the relations are respected so the image of an element of $G$ doesn’t depend on the word we use to represent it. We can also prove facts about elements of $G$ “by induction”: show a statement holds for a generator and that composition and inversion preserve the truth of the statement. We can’t do everything we’d like with presentations, but they’re still one of the most concrete ways to actually get our hands on a group.

February 24, 2007 -

1. The whole presentation business only gets more interesting when you look away from groups as well. You can play the same game with algebras, and you’ll get different results for different conditions on the algebras; but with the common denominator that you end up with some sort of Gröbner basis type theory each time.

So, the classical Gröbner bases are basically an answer to the problem “If I have a set X, and consider the algebra FX of all commutative polynomials with the elements in X as variables, then how do I work with the quotient ring FX/I – for some I given by a set of generators for the relations?”

We get, in the end, a highly algorithmic method where we complete the generating set of I until it represents enough of the ideal, and then almost any task is reduced to the Euclidean algorithm for division (with some modifications).

And once you take a good look at it, if all your polynomials are linear – then all this is nothing else than classic first term linear algebra.

Comment by Mikael Johansson | February 25, 2007 | Reply

2. [...] the properties of such presentations, any function of the generators — of — defines a linear function on if and only if it [...]

Pingback by Tensor products of abelian groups « The Unapologetic Mathematician | April 6, 2007 | Reply

3. Maybe I’m missing something, but the development here seems more indirect than necessary. The inefficiency of the F(G)/Ker F construction lies in listing the entire kernel, bit the normal closure construction works just as well an arbitrary subsets of F(G) as on subgroups of it, so, if we’re lucky, we might only need to specify a small or otherwise intelligible subset of Ker F. So why introduce the extraneous set Y and then F(Y)?

I really like this ‘blath’, and the general idea of ‘math for outsiders’ (such as myself).

Comment by Avery Andrews | September 19, 2007 | Reply

4. ok i am interesting in mathematics and playings chess games and seeing a english movies. thanks have you comments me then my e-mail address.