Free Groups, Generators, and Relations

November 15, 2010, 07:03
Filed under: Algebra, Math | Tags: algebra, group theory, MaBloWriMo, Math

Last time we talked about the cosets of a subgroup. We showed that for a normal subgroup, the left and right cosets coincide, and thus you could multiply any two cosets to get a third coset, defining a group operation on the set of equivalence classes of cosets, or quotient group. We proved the powerful First Isomorphism Theorem, which characterized normal subgroups as the kernels of homomorphisms and showed that the quotient of a homomorphism’s domain with its kernel was isomorphic to its image.

Today, we’re going to introduce a new “type” of group and use the First Isomorphism Theorem to develop a new way of representing groups.

BUT FIRST let’s do the random group theory factoid-of-the-day! We defined the kernel of a homomorphism last time as the set of elements that get sent to the identity. Here’s an easy way to check if a homomorphism is injective:

Proposition. A homomorphism is injective iff its kernel is the identity.

Proof. Let $f:G\rightarrow H$ be an injective homomorphism. We know that $f(e_G)=e_H$ , so nothing else can hit the identity, by injectivity. So $\ker(f)=\{e_G\}$ . Conversely, if $f$ is a homomorphism with the identity for its kernel, and $f(a)=f(b)$ , then $f(ab^{-1})=f(a)f(b)^{-1}=e_H$ , so $a=b$ . Thus, $f$ is injective. $\square$

On to the main topic. Let’s start with some arbitrary set: $\{a,b,c\}$ . The free group on that set is the set of finite formal products of its elements and their inverses, with no interaction between them other than “adjacent inverses have to cancel” — like $a^4b^{-1}cb^3c^{-3}a$ . Such a product is called a (reduced) word. We define the product of two words to be the word you get when you write them next to each other, then cancel adjacent inverses: so $ac^3\cdot c^{-1}b^{-2}a^6b=ac^2b^{-2}a^6b$ . This product is a group operation, with identity given by the empty word, which I’ll just write $e$ , and with $(s_1^{p_1}s_2^{p_2}\dotsm s_n^{p_n})^{-1}=s_n^{-p_n}\dotsm s_2^{-p_2}s_1^{-p_1}$ , where $s_i$ are symbols in the set and $p_i$ are their powers.

We’ll write the free group on a set $A$ as $F_A$ . It’s clearly very infinite for nonempty $A$ , but still quite well-behaved: given an unreduced word in the group, it’s easy to tell what group element that word represents: just scan it for adjacent inverses and delete them. Moreover, if $A$ and $B$ have the same cardinality, then $F_A\cong F_B$ , so in general, we’ll write free groups on finite sets of cardinality $n$ as $F_n$ .

We can also look at free groups through a universal property. Let $G$ be a group, and let $S$ be a set, with a map $f:S\rightarrow G$ . Then there is a unique group homomorphism $\tilde{f}:F_S\rightarrow G$ that restricts to $f$ on $S$ . Thus, the homomorphisms from $F_S$ to $G$ biject with the functions from $S$ to $G$ . Why should you care? Because when we study other algebraic structures besides groups, this very same property can characterize “free objects” in them, too. We call the set $S$ a basis for the free object constructed in this way.

Theorem. The definitions of “free group” given above are equivalent.

Proof. Given a map $f:S\rightarrow G$ , just define $\tilde{f}(s)=f(s)$ for $s\in S$ , and $\tilde{f}(st)=\tilde{f}(s)\tilde{f}(t)$ recursively. Pretty much by definition, this is clearly the only possible homomorphism on $F_S$ that restricts to $S$ . Look at what’s happening here: we’re actually defining a map on the monoid of unreduced words, but then in order to make this a group homomorphism, its kernel must include all words of the form $aa^{-1}$ and so on. Then we just declare it to be a group homomorphism, automatically adding more stuff to the kernel. For example, the map $\{f,r\}\rightarrow D_8$ gives a homomorphism of $F_2$ into $D_8$ , with the kernel including words like $rfr$ and $f^2$ .

Conversely, let $E_S$ be a group containing $S$ that has the universal property for the set $S$ , and let $F_S$ be the actual free group on $S$ . Then since $S\subset F_S$ , the inclusion map gives a group homomorphism $E_S\rightarrow F_S$ . Likewise, since $S\subset E_S$ , we get another homomorphism $F_S\rightarrow E_S$ . I’ll leave it to you to show that they are inverses, and the groups are isomorphic. $\square$

Now, Cayley’s Theorem allowed us to write every group as a subset of a symmetric group: this is the regular or permutation representation of a group. Here’s a theorem that basically works the opposite way:

Theorem. Every group is isomorphic to a quotient of a free group.

Proof. Let $S$ be a set of generators for a group $G$ . The inclusion of $S$ into $G$ gives us a homomorphism $\tilde{i}:F_S\rightarrow G$ . By the First Isomorphism Theorem, $G\cong F_S/\ker(\tilde{i})$ . $\square$

Of course, every group has a set of generators: at most, it’s the set $G$ itself. We call a group finitely generated if a finite set of generators exists. In general, the above theorem is only used on finitely generated groups: for bigger groups, there tend to be more efficient ways to talk about things.

The kernel of $\tilde{i}$ is a subgroup of $F_S$ . As it turns out, every subgroup of a free group is free (we’ll prove this tomorrow, when I can do the cool proof instead of the boring one). So $\ker{\tilde{i}}$ is free on some subset of $F_S$ . We call the elements of such a subset the relations of $G$ . These are the words of generators that get cancelled completely in $G$ . This is all we need to determine the structure of $G$ : just like injective homomorphisms are characterized by their behavior at the identity, we can also characterize all the other cancellations in $G$ by the things that get cancelled to the identity.

This presentation is called the generators and relations presentation of $G$ . Generally it’s written as $G=\langle g_1,g_2,\dotsc|r_1,r_2,\dotsc\rangle$ , or as $G=\langle g_1,g_2,\dotsc\rangle/\langle r_1,r_2,\dotsc\rangle$ , where the $g_i$ are generators and the $r_i$ are relations. If a group has finite generators and relations, it is finitely presented.

As an example, $\mathbb{Z}\cong\langle a\rangle$ , and $\mathbb{Z}_n\cong\langle a|a^n\rangle$ . The dihedral group $D_{2n}\cong\langle f,r|f^2,r^n,rfr\rangle$ , as you should prove if you haven’t already. Symmetric groups have their own theory that we haven’t really investigated: can you find generators and relations for them?

Sadly, generators and relations don’t actually tell us all that much. The word problem for a given group is to find a systematic way to tell whether two words in the group’s generators represent the same element. It is, in general, unsolvable from the group’s presentation: the proof is really out of our way for now, but Wikipedia proves it and gives an example of a group with only 10 generators and an unsolvable word problem. Fortunately, all the groups we deal with are nice enough that we can solve their word problems: in particular, every finite group has a solvable word problem. We actually solved the word problem for dihedral groups back when we introduced them, by saying that you can move all the rotations to one side. When we go into detail about symmetric groups, we will solve their word problem, too.

I lied a tiny bit last time, in saying this was all we needed to do the Banach-Tarski Paradox. It’s all of the abstract stuff we need, but to go on we’ll need to talk a little more about group actions, the vector space structure of $\mathbb{R}^3$ , and $SO(3)$ , its group of vector space isometries. Still, exciting times are ahead.

About these ads

5 Comments

5 Comments so far
Leave a comment

[...] 16 11 2010 Today we’re going to take the abstract group machinery we’ve been building up, and unleash it on some sets. When mathematicians say that “groups describe symmetry,” [...]

Pingback by Group Actions « Gracious Living November 16, 2010 @ 15:01

[...] now let’s get a little more abstract. Remember when we talked about free groups? It turns out that the free group on two generators, , is paradoxical under its action on itself. [...]

Pingback by Banach-Tarski part 1 « Gracious Living November 21, 2010 @ 06:34

[...] family of groups. Dual to the direct product is the free product, which generalizes the idea of a free group. The amalgamated free product is just a free product that we neutralize on the image of some map. [...]

Pingback by More Products of Groups « Gracious Living November 27, 2010 @ 22:40

[...] fact, they do. Here’s a somewhat lengthy proof. Let , say, be the group generated by this presentation, that is, the group where is always at least . Since satisfies the same relations as , [...]

Pingback by Symmetric Groups « Gracious Living December 18, 2010 @ 11:36

[...] post for a while. As I promised quite a while back, let’s prove together that subgroups of free groups are free. It’s surprising that this is nontrivial to prove: just try to come up with some [...]

Pingback by Subgroups of Free Groups are Free « Gracious Living December 28, 2010 @ 07:33

RSS feed for comments on this post. TrackBack URI

Gracious Living

Categories

Archives

Links

Follow “Gracious Living”

Gracious Living

Categories

Archives

Links

Share this:

Like this:

Leave a Reply Cancel reply

Follow “Gracious Living”