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.

• This word­ing sug­gests the group con­tains only some of the el­e­ments from the fol­low­ing list. I think you meant the op­po­site—that the fol­low­ing el­e­ments are only some of the things it con­tains.

• Pedan­tic re­mark: Aren’t you miss­ing the iden­tity of free groups in your in­tu­itive con­struc­tion?

We have the $$\rho_x$$ and the $$\rho_{x^{-1}}$$. Where is $$\rho_\epsilon$$?

• Thanks: quite cor­rect.