Gracious Living


Free Groups, Generators, and Relations
November 15, 2010, 07:03
Filed under: Algebra, Math | Tags: , , ,

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.

Advertisements

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

[…] 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

[…] 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

[…] 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

[…] 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




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: