A free group is intuitive, but the proofs are somewhat technical. I'll present some intuition first, then get down to business.
A free group on three letters consists of strings of these letters and their inverses. If A B and C are the three letters, let A B and C be their inverses. Multiplication in the group is now concatenation followed by cancellation. Thus AAC * CAB becomes AB.
This certainly seems associative. Parentheses shouldn't matter as you tack three words together. Also, every word has an inverse, by reversing and inverting the letters. So it looks like a group.
A free group is based on a set of generators, or symbols, or letters - different names for the same thing. Each letter is paired with a modified version of itself, which acts as its inverse. This modified letter can be written with a bar over it, as in A. The letters and their inverses form an alphabet that will be used to build words of finite length.
A word is reduced if a letter never sits next to its inverse. The reduced words, including the empty word, are the elements of the group.
Group multiplication consists of concatenation followed by cancellation. But is this well defined? We need to show that an unreduced word always leads to the same reduced word, no matter how you proceed.
Suppose an unreduced word yields two different reduced words. Start at one end, one of the reduced words, then proceed step by step through the unreduced word, and wind up at the other reduced word. Each step creates a pair of inverse letters, or cancels a pair of inverse letters. Call these words w1 through wn, where w1 and wn are distinct reduced words.
Since w1 and wn are different words, there are at least two words in the sequence. In fact there are more than two, because w1 is reduced, and the step from w1 to w2 can only create a symbol inverse pair, which means w2 is not reduced. So there are at least three words in the sequence.
Let the size of a sequence be the sum of the lengths of the words, and assume we have a valid sequence of minimal size. Let wi be the longest word in the sequence. Moving into wi creates a pair, and moving on to wi+1 cancels a pair. If these pairs are independent, reverse the order - cancel first, then create. Now wi is a shorter word by 4, which is a contradiction.
If the same pair is created and destroyed, remove wi and wi+1 to find a smaller sequence. If the two pairs overlap in one letter, the neighboring words are identical, and you can remove wi and wi+1. These are all the cases, hence there is no sequence connecting distinct reduced words. Each unreduced word collapses to a unique reduced word.
To show associativity, consider (w1w2)w3 and w1(w2w3). In each case the reduced word comes from the unreduced word w1w2w3, hence the parentheses can't change the outcome.
The empty word is the identity element, and the inverse of a word is the reverse of its inverse letters. A group is born.
If the group is generated by the single letter X (and its inverse), each word is a sequence of n copies of X or X. Map these words to the integers n and -n respectively. Verify that this group is isomorphic to Z. Of course a free group on multiple letters is more interesting.
All well and good - but is this group really a free object in the category of groups and group homomorphisms?
Let S be the set of generators of a free group and let G be an arbitrary group. Map S into G in any way you like, according to a function h, and the free group must follow from there. If S contains A B and C, then the word ABC in the free group has to map to h(A)h(B)h(C) in G. Concatenate words together in the free group, and join their images in G. Cancellation of xx kills h(x)h(x) in G, which leaves the word in G unchanged. The map is a valid homomorphism, and it is the only possible group homomorphism consistent with h(S).
Every group G is the homomorphic image of a free group. Let S be a set of generators for G, and let F be the free group on S. Now F wraps around G, with the words of F mapping to the corresponding words in G. Since S generates G, F maps onto G, and the homomorphism is an epimorphism.
The kernel of this map is a normal subgroup of F. These are the words that produce e in G.
If a set of strings generates the kernel, these strings are called relators, and they necessarily map into e in G. Specifying S and the relators is sufficient to describe G up to isomorphism.
Conversely, given any free group F on S and a set of relators Y, one can construct a normal subgroup K containing Y, and hence a quotient group G = F/K.
In the above description, S and Y form a presentation for the group G. A presentation consists of a set of generators, and a set of relators, words in the free group on S. The group defined by this presentation is the free group mod the normal subgroup implied by the relators.
In fact, G is the largest group that carries the relators to e. A larger kernel, beyond K, maps to a normal subgroup of G by correspondence, which in turn leads to some factor group of G.
A finite presentation has finitely many generators and relators.
In the above I was careful to use the word relator, rather than relation, although these terms are sometimes used interchangeably. A relater is a word, an element in the free group. A relation sets one word eequal to another. This is of no consequence when dealing with groups, since w1 = w2 is the same as w1/w2. However, there is a category where the distinction is important.
A monoid is almost a group, but it doesn't have inverses. The free monoid on S consists of words formed from the letters of S. There are no inverse letters, and there is no cancellation. Consider the free monoid on A and B, with the relation A = B. This turns any string into a string of A's having the same length as the original string. There is no relator A/B, because there is no B inverse. In fact the quotient monoid cannot be produced using relators, because the kernel is empty. A and B both map to A, BB maps to AA, and so on. Only e maps to e, so there aren't any relators generating a kernel.
Monoids are not a typical category. When dealing with groups, abelian groups, modules, or ring extensions, one can specify relations or relators, which are then used to build the kernel for the quotient map. As mentioned earlier, relators are sometimes called relations, with no real distinction between the two. When extending the rationals by i, we sometimes expressed the algebraic extension as i2 = -1, or equivalently, i2+1 becomes 0.
In the category of modules, the relators generate a submodule that becomes the kernel for the quotient map. The situation is a little more complicated with groups, because the subgroup generated by the relators in Y may not be normal in F. You need to take the normal closure of Y. Expand Y to include wx/w for every relator x in Y and every word w in F. The normal closure of Y has to include wx/w, and when all these conjugates are folded into Y, the subgroup K, spanned by Y, is normal in F. For instance, take v from F and conjugate w1x1/w1 * w2x2/w2 and get vw1x1/w1/v * vw2x2/w2/v, or (vw1)x1/(vw1) * (vw2)x2/(vw2), which is generated by Y.
Of course it is not practical to write down wx/w for every w in F, but that's the idea.
The quotient group is often easier to understand when relators are turned into relations. If you are given the relation A = B, you can replace B with A wherever it appears in the quotient group. This relation is equivalent to the relator A/B, and every conjugate thereof. Assume uBv is in the quotient group. Multiply on the left by u*(A/B)/u, an element in the kernel, and get uAv.
It is sometimes convenient to multiply a relation on the left or right by a letter or word. The result is another relation that must hold trure. In the above example, uBv = uAv is a valid relation, though it was not part of the original presentation. This trick will be used in the next example.
Consider the presentation with generators A and B, and the following relations.
AB/A = B2
BA/B = A2
Multiply the first by 1/B on the right, and invert the second.
AB/A/B = B
B/A/B = 1/A2
Substitute the second into the first, and 1/A = B, or AB = 1. Plug this into the first relation and 1/1 = B, or B = 1. Since AB = 1, A = 1, and the group is trivial.
Given a presentation, verify that the following steps do not change the resulting group.
Relabel the generators.
Invert a relator. You can add the inverse into the mix, or replace the original relator with its inverse. After all, the normal subgroup K generated by Y includes all the finite products and inverses of all the conjugates of all the relators in Y.
Conjugate a relator. Add this in or replace; you can always unconjugate to get the original back again.
Multiply two relators together. The product is folded into the mix, and one of the relators can optionally be removed, but the product cannot replace both relators.
remove the trivial relator e.
Remove a generator x and its sole relation x = e.
Let G1 G2 G3 etc be an indexed set of groups. We want to build the product and coproduct of these objects in the category of groups.
The product is easy; let G be the direct product of the component groups Gi. If homomorphisms fi map some other group H into each Gi, let f map H into G according to each fi mapping H into Gi. You can now go from H into Gi, or from H into G, then restrict to Gi; the result is the same. And the composite map f is uniquely determined; hence G is the product.
The coproduct is also called the free product, and is somewhat intuitive, though a formal proof is a bit tedious. Assume the groups Gi are disjoint, just as we did when taking the direct product. Let G consist of words using symbols from all the groups Gi. If adjacent symbols come from the same constituent group Gi, replace them with their product, two symbols for one, just as you would in Gi. A word is reduced if adjacent symbols always come from different groups. Each unreduced word collapses to a unique reduced word. The proof is very much like the one given at the top of this chapter. xx pairs pop in and out of existence, as before, and if a pair production and reduction overlap then the sequence can be shortened, as before, but now there are additional productions to consider. If B expands to BAA, then shrinks to CA, where BA = C in the same group, then we could have simply expanded B into CA directly. If CX becomes ABX, which then becomes AY, realize that all 5 symbols belong to the same group, replace CX with Z, and then push Z back out to AY, giving a lesser sequence. Once again the resulting structure is a group.
Each Gi embeds in G in the obvious way. These are the injections into the coproduct.
Let fi map Gi into another group H. Let f map G into H by mapping each symbol, e.g. x from Gi, to fi(x) in H. Since f is a homomorphism it is now defined on every word in G. Since f is compatible with each fi, and is uniquely determined, G is the coproduct.
When the component groups are cyclic, G becomes a free group, which is why it is called a free product. Let Gi be a cyclic group generated by the symbol Xi. Every member of Gi is Xin for some integer n, where n might be negative to represent the inverse of Xi. Replace this expression with a string of Xi of length n, and G becomes free on the generators Xi. When there are three generators, A B and C, G looks like the free group described at the top of this chapter, strings of letters and their inverses, such that a letter and its inverse are never adjacent.
Let's build a free abelian group, which is a free object in the category of abelian groups.
Let S be a set of letters, and build words from these letters and their inverses, but this time all the A's appear first, then all the B's, and so on. This is because symbols commute past each other, as you would expect from an abelian group. For notational convenience, each letter is paired with an integer, representing the number of copies of that letter. The integer is negative if the inverse letter is used. The integer may appear as an exponent or a coefficient as a matter of taste. Remember that additive notation is often used when dealing with abelian groups, as shown by the second example below.
x3y5 * xy4 = x4y9
3x+5y + x+4y = 4x+9y
The free abelian group F on S is equal to the direct sum of copies of Z - one copy for each generator in S. The coefficients are the integer entries drawn from each copy of Z.
If S is mapped into any abelian group G, F follows S, and wraps around G uniquely. Thus the free abelian group is indeed a free object. Furthermore, every abelian group is the quotient of a free abelian group, with a presentation consisting of generators and relators. This time we don't have to conjugate the relators, because the subgroup of an abelian group is already normal.
Every cardinality admits a free abelian group; take the direct sum of that many copies of Z. Yet the converse also holds; each free group F has a well defined rank, or dimension, according to the number of generators of F. Suppose two free groups of different dimensions are isomorphic. I'll illustrate with an isomorphism h from Z2 to Z3.
The isomorphism is onto, and that's trouble right there. You can't map 2 dimensions onto 3. Here's why. Embed each copy of Z, in the domain and in the range, into the rationals Q. Extend h to a homomorphism on all of Q2 in a canonical fashion. If h(1,0) is x in the range, then h(½,0) is x/2. If h(0,1) is y in the range, then h(0,¼) is y/4. Thus h is defined on all of Q2, and h is a linear transformation from 2 space into 3 space. Furthermore, h is onto. The preimage of [½,0,0] is half the preimage of [1,0,0], and so on for all the rationals and all three generators in the range. Therefore a 2 dimensional vector space maps onto a 3 dimensional vector space, and that is a contradiction. Therefore free abelian groups correspond 1 for 1 with cardinality.
Just as a free abelian group cannot map onto a larger group, so a free abelian group cannot embed into a smaller one. The proof is essentially the same. Extend the monomorphism h to a homomorphism on the corresponding Q vector space, then show that the new homomorphism h is still injective. Suppose a linear combination of generators, with rational coefficients, maps to 0 under h. Multiply through by a common denominator and find a linear combination of generators, with integer coefficients, that maps to 0 under h. This contradicts the assumption that h is injective on the abelian group. Thus h embeds a larger Q vector space into a smaller one, which is impossible. Therefore h cannot embed a free abelian group into a smaller one.
There is a wonderful connection between free groups and free abelian groups. Let F be the free group on S, and include a relation xy = yx for every pair of generators x and y in S. Since x and y commute past each other, the quotient group G is abelian. In fact the map from F onto G gathers like symbols together and adds exponents, giving one coefficient for each symbol in S. For example: ABBABCBA → 3A+2B+C.
The kernel, spanned by these relations, is called the commutator subgroup of F. Express the relations as relators, and the kernel is generated by xy/x/y, which are the commutators. Thus G = F/F′. The abelianization of the free group on S is the free abelian group on S.
As shown above, the rank of a free abelian group is well defined. Use this to make the same assertion about free groups. If two free groups are isomorphic, yet they have different ranks, i.e. different numbers of generators, mod out by their commutator subgroups and find two isomorphic free abelian groups with different ranks. This is a contradiction, hence the rank of a free group is well defined. The free group on 3 letters is not equivalent to the free group on 2 letters, or the free group on an infinite set of letters.
If a homomorphism takes the free group E onto the free group F, E cannot have lesser rank. Each commutator xy/x/y in E becomes a commutator in F. Treat the commutator subgroups as kernels. Since the kernel of E maps into the kernel of F, the map on quotient groups is well defined. The abelianization of E maps onto the abelianization of F, and that is impossible, as shown above. Hence the rank of E is at least the rank of F.
We'll see in the next section, however, that a free group can fit inside another free group of lesser rank. This is quite different from the abelian case, where a free abelian group cannot fit inside a smaller free abelian group.
The free group on two letters contains within it the free group on a countably infinite set. (Since the size of this group is countable, there isn't room for an uncountable set.)
If F is based on A and B, map the ith generator, from an infinite set of generators, to AiBi. This is a group homomorphism from the free group on an infinite set into F. We only neeed show it is injective.
Let a block be a string that consists entirely of A, A, B, or B. Thus the first symbol, with image AiBi, introduces two blocks.
Words in the domain are reduced, so adjacent symbols will not be inverses of each other. The next block will not perfectly cancel the previous block. This assures at least one more block with each new symbol. The constructed word cannot collapse to e, and the free group of infinite rank embeds in the free group of rank 2.
Another construction maps the ith symbol to AiB/Ai. Each symbol introduces another B or B to the word in F.
One can embed the free abelian group of countable rank into the positive rationals under multiplication. Map the ith generator into the ith prime. Unique factorization guarantees each word maps to a unique rational number.
Moving away from rationals and back to integers, one can embed the free monoid on n letters into the upper triangular 2×2 matrices over Z, by carrying the ith generator to [1,i] on top, and [0,n] below. Number the generators starting with 0, so that i runs from 0 to n-1. Multiply k of these matrices together, and the lower right entry is nk. Read the upper right entry in base n to reproduce the word in the free monoid.
Even more impressive, one can embed the free group of infinite rank into the 2×2 integer matrices with determinant 1. A free group of infinite rank embeds in a free group of rank 2, as shown in the previous section, so it is enough to embed the free group F on A and B.
Start with the identity matrix and replace 0, in the lower left, with 2. This is the image of A. Start with the identity matrix and replace 0, in the upper right, with 2. This is the image of B. Replace 2 with -2 to find the inverses of A and B. Since every word is a product of these 2×2 matrices, each word leads to an invertible matrix with integer coefficients.
The map from F into SL2(Z) is a homomorphism, but is it a monomorphism? We need to show that a reduced word cannot produce the identity matrix.
Look at the action of each matrix on the xy plane. Partition the plane into 8 regions, using the axes and the diagonals. Number the regions 1 through 8 counterclockwise, starting above the positive x axis. If x,y lies inside region 2, with y > x, place x,y in a column vector on the right of A and multiply, giving x,2x+y. The point has been pushed up in the xy plane, and is still in region 2. Similarly, points in region 1 are pushed up into region 2, and even points in region 8, below the x axis, are pushed up into region 2.
On the other side, A drives points in regions 4 5 and 6 down to region 6.
While A shifts the plane up on the right and down on the left, A inverse does the opposite. It moves three regions into region 7, and three regions into region 3.
B moves x,y to x+2y,y, carrying three regions into region 1 and three regions into region 5. B inverse moves three regions into region 4, and three regions into region 8.
If B moves a point into region 1, subsequent B's are going to keep this point in region 1. We can treat the entire block of B's as a single B. Of course B inverse is not going to follow B, so we don't have to worry about that.
If a point is in region 2, 3, 6, or 7, and B or B inverse is applied, or an entire block thereof, the point moves to region 1, 4, 5, or 8, and sits there, waiting for A or A inverse to come along. Similarly, if a point is in region 1, 4, 5, or 8, and A or A inverse is applied, the point moves to region 2, 3, 6, or 7, and sits there, waiting for B or B inverse to come along.
If a word begins and ends with A or A inverse, start in region 1, and wind up in region 2, 3, 6, or 7. This is not the identity map on the xy plane - not the identity matrix.
If a word begins and ends with B or B inverse, start in region 2, and wind up in region 1, 4, 5, or 8.
If the word starts with A and ends with B or B inverse, start in region 2 and wind up somewhere else. If the word starts with A inverse and ends with B or B inverse, start in region 7 and wind up somewhere else. Similar results hold for words that start with B or B inverse and end with A or A inverse.
No word produces the identity map, and F embeds.
Let a1 a2 a3 etc be a set of generators for the group G, and let H be a subgroup of G.
Let b1 b2 b3 etc be a set of left cosreps of H in G, one representative for each coset. Let ci be the inverse of bi.
For convenience, let b1, the representative of H itself, equal 1, the identity element. Thus c1 is also equal to 1.
We would like to build a set of generators for H, using the generators of G and the cosreps. This process is called Schreier Nielsen rewriting.
For each i and j, build a word vi,j = biajck. In each case, choose k so that the constructed element winds up back in H. In other words, bk represents the same coset as biaj. There will be one value of k that makes this work.
The inverse of vi,j applies a cosrep, then the inverse of aj, then another cosrep that pulls the word back into H.
Everything in G, and in H, is spanned by the generators of G. Assume a word, built from these generators, lies in H. If the first symbol is a7, replace it with v1,7. This leaves some ck at the end. If the next symbol is a3, replace it with vk,3. The adjacent letters ckbk cancel, leaving a7a3, as they appeared in the original word. Continue this process, replacing each symbol with one of our new generators vi,j, or its inverse if the symbol is inverted. Once the word is rewritten, the last ck has to be 1, because the word lies in H.
Each generator lies in H, and every word in H has been spanned. We have constructed a set of generators for the subgroup H.
If G is finitely generated and H has finite index in G, (finitely many left cosets), H is finitely generated.
There is no need to include a generator that is effectively empty. If b3a7 happens to equal b4, not just as cosets but as elements of G, the new generator v3,7 = b3a7c4 is empty, and can be omitted.
Let G be a free group with a subgroup H.
Well order the generators of G and their inverses. Thus the generators of G are a0 a1 a2 a3, and so on.
Order the words of G by length, then lexicographically.
Let bi be the minimum word in the ith left coset of H. This will be the canonical representative for that coset. Notice that e represents H.
This system of cosreps is closed under left substrings. In other words, every left substring of a cosrep bi is some other cosrep bj. To illustrate, let b3 represent the third coset of H in G, and assume b1u = b3. We're talking specifically about concatenation here; there is no cancellation. The first part of b3 is b1, and the second part is u.
If b1 and b3 represent the same coset then we should have selected b1 in the first place; it's shorter. Thus b1 represents some other coset of H.
Suppose w lies in H, and wb1 is smaller than b1. This time juxtaposition means group multiplication; so cancellation is possible. The product wb1 is either shorter, or it is the same length and begins with an earlier letter. Bring in u, and if there is no additional cancellation from u, wb1u is shorter, or has the same length and begins with an earlier letter. This builds a smaller cosrep for b3.
If cancellation occurs (because w has swallowed all of b1 and part of u), then the rest of w, after swallowing b1, is no longer than b1, and some of that eats u, so the string is shorter still. Once again wb1u is a lesser representative for the third coset, and that is a contradiction. Each left substring is the cosrep for its left coset in G, and all the left substrings represent distinct cosets.
With these cosreps in place, use schreier nielsen rewriting to create a set of generators for H. A typical generator is biaj/bk, where bk brings the element back into H. This three part word cannot be reduced. Suppose bi ends with the inverse of aj, thus permitting cancellation. The result is a left substring, which is some other cosrep, say bk. To bring this back into H, we divide by bk. The result is e, the trivial generator. These can be left on the cuttingroom floor.
Suppose bk ends in aj, so that aj gets eaten by the inverse of bk on the right. Let w equal bk with aj removed. Thus bi/w lies in H. Multiply by w on the right and bi and w represent the same coset of H. Since w is a left substring, it is the canonical cosrep, as is bi. Therefore w = bi, and once again the generator collapses to e, and can be ignored. If a schreier generator biaj/bk survives, it cannot be reduced at all.
The schreier generators span a group that covers all of H. If none of the words produced by these generators collapses to e, then H is free. Thus the subgroup of a free group is free.
The heart of each schreier generator is the letter aj in the middle. These letters never go away, hence the string never drops down to e. Put two generators together and watch what happens.
Consider the adjacent schreier generators b1a2/b3 * b4a5/b6.
Suppose b3 = b4, hence they cancel each other exactly. If a2 and a5 are inverses, then b1/b6 lies in H. Both represent the same coset of H, and b1 = b6. The two schreier generators were inverses, and the word, written in schreier generators, was not reduced. This is a contradiction, hence b3 ≠ b4. (This same logic applies even if b3 and b4 equal e.)
Next suppose 1/b3 eats b4 and a5 (and perhaps part of b6 as well). Now b4a5 is a left substring of b3. This becomes a cosrep, in the same coset as b6, and equal to b6. That makes b4a5/b6 a trivial generator.
Finally, suppose a2/b3 is eaten by b4 on the right. This makes b3/a2 a cosrep, equal to b1, and b1a2/b3 goes away.
None of the central elements cancel, a schreier word never becomes empty, and H is free.
If you're curious, a subgroup of a free abelian group is free abelian, but that's coming up later.
A torsion element has finite order and a torsion group has all torsion elements. A torsion free group has no torsion elements.
In a locally finite group, the subgroup generated by any finite set of elements is finite. The polynomials over a finite field form a torsion, locally finite group under addition, even though the entire group is infinite.
Is there a torsion group that is not locally finite? There is, the Tarski monster group, but that is beyond the scope of this book.