Free group

In­tu­itively, the free group \(F(X)\) on the set \(X\) is the group whose el­e­ments are the freely re­duced words over \(X\), and whose group op­er­a­tion is “con­cate­na­tion fol­lowed by free re­duc­tion”.

The free group can be con­structed rigor­ously in sev­eral equiv­a­lent ways, some of which are easy to con­struct but hard to un­der­stand, and some of which are in­tu­itive but rather hard to define prop­erly. Our for­mal con­struc­tion (de­tailed on the For­mal Defi­ni­tion lens) will be one of the more opaque defi­ni­tions; there, we even­tu­ally show that the for­mal con­struc­tion yields a group which is iso­mor­phic to the in­tu­itive ver­sion, and this will prove that the in­tu­itive ver­sion does in fact define a group with the right prop­er­ties for the free group.

In­tu­itive definition

Given a set \(X\), the free group \(F(X)\) (or \(FX\)) on \(X\) has:

Example

The free group on the set \(X = \{ a, b \}\) con­tains the fol­low­ing el­e­ments (among oth­ers):

  • The word \((a,b,a,a,a,b^{-1})\), which is writ­ten in short­hand as \(abaaab^{-1}\) or (most com­monly) as \(aba^3b^{-1}\)

  • The empty word \(()\), which is writ­ten as \(\varepsilon\)

  • The word \((b,b,b)\), which is writ­ten as \(b^3\)

  • The word \((a^{-1}, b^{-1}, b^{-1})\), or \(a^{-1} b^{-2}\)

(From now on, we will only use the com­mon short­hand to de­note words, ex­cept in cases where this in­terferes with some­thing else we’re do­ing.)

Some things which the same free group does not con­tain are:

  • \(aa^{-1}\), since this is not freely reduced

  • \(c\), for the fatu­ous rea­son that \(c\) is not a word over the alpha­bet \(\{a,b\}\)

  • \(abb^{-1}a\), since this is not freely re­duced.

Some ex­am­ples of this group’s group op­er­a­tion (which we will write as \(\cdot\)) in ac­tion are:

  • \(aba \cdot bab = ababab\)

  • \(aba^2 \cdot a^3b = aba^5b\)

  • \(aba^{-1} \cdot a = ab\), ob­tained as the free re­duc­tion of \(aba^{-1}a\)

  • \(ab \cdot b^{-1} a^{-1} = \varepsilon\), ob­tained as \(abb^{-1}a^{-1} = aa^{-1}\) (re­duc­tion of \(b\)) and then \(a a^{-1} = \varepsilon\).

Examples

  • The free group on the empty set is just the triv­ial group, the group with just one el­e­ment. In­deed, we must have an iden­tity (the empty word), but there are no ex­tra gen­er­a­tors to throw in, so there are no longer words.

  • The free group on a set with one el­e­ment is iso­mor­phic to the group of in­te­gers un­der ad­di­tion. In­deed, say our set is \(\{ a \}\); then ev­ery mem­ber of the free group is a word of the form \(a^n\) or \(a^{-n}\) or \(a^0\). Then the iso­mor­phism is that \(a^i\) is sent to \(i \in \mathbb{Z}\).

  • The free group on two el­e­ments is countable. In­deed, its el­e­ments are all of the form \(a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_n} b^{j_n}\), and so the free group in­jects into the set of nat­u­ral num­bers by the (rather con­voluted)

    $$a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_n} b^{j_n} \mapsto 2^{\mathrm{sgn}(i_1)+2} 3^{|i_1|} 5^{\mathrm{sgn}(j_1)+2} 7^{|j_1|} \dots$$
    where we pro­duce the nat­u­ral num­ber noteUniquely, by the fun­da­men­tal the­o­rem of ar­ith­metic. whose prime fac­tors tell us ex­actly how to con­struct the origi­nal word. noteThis trick is ex­tremely use­ful in de­ter­min­ing whether a set is countable, and you should go over it un­til you are sure you un­der­stand it. (The \(\mathrm{sgn}\) func­tion out­puts \(-1\) if its in­put is nega­tive; \(1\) if the in­put is pos­i­tive; and \(0\) if its in­put is \(0\).) As a re­lated ex­er­cise, you should prove that the free group on a countable set is countable.

Why are the free groups im­por­tant?

It is a fact that ev­ery group is a quo­tient of a free group. There­fore the free groups can be con­sid­ered as a kind of col­lec­tion of “base groups” from which all other groups can be made as quo­tients. This idea is made more con­crete by the idea of the group pre­sen­ta­tion, which is a no­ta­tion that speci­fies a group as a quo­tient of a free group. noteAlthough it’s not usu­ally pre­sented in this way at first, be­cause the no­ta­tion has a fairly in­tu­itive mean­ing on its own.

Free groups “have no more re­la­tions than they are forced to have”

The crux of the idea of the group pre­sen­ta­tion is that the free group is the group we get when we take all the el­e­ments of the set \(X\) as el­e­ments which “gen­er­ate” our pu­ta­tive group, and then throw in ev­ery pos­si­ble com­bi­na­tion of those “gen­er­a­tors” so as to com­plete it into a bona fide group. We ex­plain why the free group is (in­for­mally) a “pure” way of do­ing this, by walk­ing through an ex­am­ple.

If we want a group which con­tains the el­e­ments of \(X = \{ a, b \}\), then what we could do is make it into the cyclic group on the two el­e­ments, \(C_2\), by in­sist­ing that \(a\) be the iden­tity of the group and that \(b \cdot b = a\). How­ever, this is a very ad-hoc, “non-pure” way of mak­ing a group out of \(X\). %%note:For those who are look­ing out for that sort of thing, to do this in gen­er­al­ity will re­quire heavy use of the ax­iom of choice.%% It adds the “re­la­tion” \(b^2 = a\) which wasn’t there be­fore.

In­stead, we might make the free group \(FX\) by tak­ing the two el­e­ments \(a, b\), and throw­ing in ev­ery­thing we are forced to make if no non-triv­ial com­bi­na­tion is the iden­tity. For ex­am­ple:

  • we have no rea­son to sus­pect that ei­ther \(a\) or \(b\) is already the iden­tity, so we must throw in an iden­tity which we will la­bel \(\varepsilon\);

  • we have no rea­son to sus­pect that \(a \cdot b\) should be equal to \(a\) or to \(b\) or to \(\varepsilon\), so we must throw in an el­e­ment equal to \(a \cdot b\) which we will la­bel \(ab\);

  • we do have a rea­son to sus­pect that \(a^{-1} \cdot a\) is already in the group (be­cause it “ought to be” the iden­tity \(\varepsilon\)), so we don’t throw in the el­e­ment \(a^{-1} a\);

  • and so on through all the words, such as \(a^{-1}ba^2b^{-2}\) and so forth.

This way adds an awfully large num­ber of el­e­ments, but it doesn’t re­quire us to im­pose any ar­bi­trary re­la­tions. <div><div>

Univer­sal prop­erty of the free group

The free group has a uni­ver­sal prop­erty, let­ting us view groups from the view­point of cat­e­gory the­ory. To­gether with the idea of the quo­tient (which can be for­mu­lated in cat­e­gory the­ory as the co­equal­iser) and the sub­se­quent idea of the group pre­sen­ta­tion, this lets us con­struct any group in a cat­e­gory-the­o­retic way.

In­deed, ev­ery group \(G\) has a pre­sen­ta­tion \(\langle X \mid R \rangle\) say, which ex­presses \(G\) as a quo­tient (i.e. a cer­tain co­equal­iser) of the free group \(F(X)\). We can con­struct \(F(X)\) through the uni­ver­sal prop­erty, so we no longer need to say any­thing at all about the el­e­ments or group op­er­a­tion of \(G\) to define it.

Properties

  • It is not ob­vi­ous, but \(FX\) is iso­mor­phic to \(FY\) if and only if \(X\) and \(Y\) have the same car­di­nal­ity as sets. (Proof.) This com­pletely clas­sifies the free groups and tells us just when two free groups are “the same”, which is nice to have.

  • The only two abelian groups which are free are the triv­ial group (of one el­e­ment; i.e. the free group on no gen­er­a­tors), and \(\mathbb{Z}\) the free group on one gen­er­a­tor. No oth­ers are abelian be­cause if there are two or more gen­er­a­tors, pick \(a, b\) to be two of them; then \(ab \not = ba\) by free-ness. noteTo be com­pletely pre­cise about this, us­ing the for­mal defi­ni­tion, \(\rho_a \rho_b \not = \rho_b \rho_a\) be­cause they have differ­ent effects when ap­plied to the empty word \(\varepsilon\). One pro­duces \(ab\); the other pro­duces \(ba\).

  • The free groups are all tor­sion-free note”Tor­sion-free” means “free of tor­sion”, where the word “free” is noth­ing to do with “free group”.: that is, no el­e­ment has finite or­der un­less it is the iden­tity \(\varepsilon\). (Proof.) This prop­erty helps us to recog­nise when a group is not free: it is enough to iden­tify an el­e­ment of finite or­der. How­ever, the test doesn’t go the other way, be­cause there are tor­sion-free groups which are not free.

Sup­pose the or­der of an el­e­ment \(x \in \mathbb{Q}\) were finite and equal to \(n \not = 0\), say. Then \(x+x+\dots+x\), \(n\) times, would yield \(0\) (the iden­tity of \((\mathbb{Q}, +)\)). But that would mean \(n \times x = 0\), and so \(n=0\) or \(x = 0\); since \(n \not = 0\) already, we must have \(x = 0\), so \(x\) is the iden­tity af­ter all.

The group is not free: sup­pose it were free. It is abelian, so it must be iso­mor­phic to ei­ther the triv­ial group (clearly not: \(\mathbb{Q}\) is in­finite but the triv­ial group isn’t) or \(\mathbb{Z}\). It’s not iso­mor­phic to \(\mathbb{Z}\), though, be­cause \(\mathbb{Z}\) is cyclic: there is a “gen­er­at­ing” el­e­ment \(1\) such that ev­ery el­e­ment of \(\mathbb{Z}\) can be made by adding to­gether (pos­si­bly nega­tively-many) copies of \(1\). \(\mathbb{Q}\) doesn’t have this prop­erty, be­cause if \(x\) were our at­tempt at such a gen­er­at­ing el­e­ment, then \(\frac{x}{2}\) could not be made, so \(x\) couldn’t ac­tu­ally be gen­er­at­ing af­ter all. <div><div>

Children:

Parents:

  • Group

    The alge­braic struc­ture that cap­tures sym­me­try, re­la­tion­ships be­tween trans­for­ma­tions, and part of what mul­ti­pli­ca­tion and ad­di­tion have in com­mon.