# Freely reduced word

make Free Group a par­ent of this

make the sum­mary a bit better

Given a set $$X$$, we can make a new set $$X^{-1}$$ con­sist­ing of “for­mal in­verses” of el­e­ments of $$X$$. That is, we cre­ate a set of new sym­bols, one for each el­e­ment of $$X$$, which we de­note $$x^{-1}$$; so

$$X^{-1} = \{ x^{-1} \mid x \in X \}$$

By this stage, we have not given any kind of mean­ing to these new sym­bols. Though we have named them sug­ges­tively as $$x^{-1}$$ and called them “in­verses”, they are at this point just ob­jects.

Now, we ap­ply mean­ing to them, giv­ing them the flavour of group in­verses, by tak­ing the union $$X \cup X^{-1}$$ and mak­ing finite “words” out of this com­bined “alpha­bet”.

A finite word over $$X \cup X^{-1}$$ con­sists of a list of sym­bols from $$X \cup X^{-1}$$. For ex­am­ple, if $$X = \{ 1, 2 \}$$ noteThough in gen­eral $$X$$ need not be a set of num­bers., then some words are:

• The empty word, which we com­monly de­note $$\varepsilon$$

• $$(1)$$

• $$(2)$$

• $$(2^{-1})$$

• $$(1, 2^{-1}, 2, 1, 1, 1, 2^{-1}, 1^{-1}, 1^{-1})$$

For brevity, we usu­ally write a word by just con­cate­nat­ing the “let­ters” from which it is made:

• The empty word, which we com­monly de­note $$\varepsilon$$

• $$1$$

• $$2$$

• $$2^{-1}$$

• $$1 2^{-1} 2 1 1 1 2^{-1} 1^{-1} 1^{-1}$$

For even more brevity, we can group to­gether suc­ces­sive in­stances of the same let­ter. This means we could also write the last word as $$1 2^{-1} 2 1^3 2^{-1} 1^{-2}$$.

Now we come to the defi­ni­tion of a freely re­duced word: it is a word which has no sub­se­quence $$r r^{-1}$$ or $$r^{-1} r$$ for any $$r \in X$$.

# Example

If $$X = \{ a, b, c \}$$, then we might write $$X^{-1}$$ as $$\{ a^{-1}, b^{-1}, c^{-1} \}$$ (or, in­deed, as $$\{ x, y, z \}$$, be­cause there’s no mean­ing in­her­ent in the $$a^{-1}$$ sym­bol so we might as well write it as $$x$$).

Then $$X \cup X^{-1} = \{ a,b,c, a^{-1}, b^{-1}, c^{-1} \}$$, and some ex­am­ples of words over $$X \cup X^{-1}$$ are:

• The empty word, which we com­monly de­note $$\varepsilon$$

• $$a$$

• $$aaaa$$

• $$b$$

• $$b^{-1}$$

• $$ab$$

• $$ab^{-1}cbb^{-1}c^{-1}$$

• $$aa^{-1}aa^{-1}$$

Of these, all ex­cept the last two are freely re­duced. How­ever, $$ab^{-1}cbb^{-1}c^{-1}$$ con­tains the sub­string $$bb^{-1}$$, so it is not freely re­duced; and $$aa^{-1}aa^{-1}$$ is not freely re­duced (there are sev­eral ways to see this: it con­tains $$aa^{-1}$$ twice and $$a^{-1} a$$ once).

This chunk is de­signed to get you fa­mil­iar with the idea that the sym­bols $$a^{-1}$$, $$b^{-1}$$ and so on in $$X^{-1}$$ don’t have any in­her­ent mean­ing.

If we had (rather per­versely) gone with $$\{ x, y, z \}$$ as the cor­re­spond­ing “in­verses” to $$\{ a, b, c \}$$ (in that or­der), rather than $$\{ a^{-1}, b^{-1}, c^{-1} \}$$ as our “in­verses” <div><div>note:Which you should never do. It just makes things harder to read.%%, then the above words would look like:

• The empty word, which we com­monly de­note $$\varepsilon$$

• $$a$$

• $$aaaa$$, which we might also write as $$a^4$$

• $$b$$

• $$y$$

• $$ab$$

• $$aycbyz$$

• $$axax$$

For the same rea­sons, all but the last two would be freely re­duced. How­ever, $$aycbyz$$ con­tains the sub­string $$by$$ so it is not freely re­duced; and $$axax$$ is not freely re­duced (there are sev­eral ways to see this: it con­tains $$ax$$ twice and $$xa$$ once). %%

# Why are we in­ter­ested in this?

We can use the freely re­duced words to con­struct the free group on a given set $$X$$; this group has as its el­e­ments the freely re­duced words over $$X \cup X^{-1}$$, and as its group op­er­a­tion “con­cate­na­tion fol­lowed by free re­duc­tion” (that is, re­moval of pairs $$r r^{-1}$$ and $$r^{-1} r$$). noteWe make this con­struc­tion prop­erly rigor­ous, and check that it is in­deed a group, on the Free group page. The no­tion of “freely re­duced” ba­si­cally tells us that $$r r^{-1}$$ is the iden­tity for ev­ery let­ter $$r \in X$$, as is $$r^{-1} r$$; this can­cel­la­tion of in­verses is a prop­erty we very much want out of a group.

The free group is (in a cer­tain well-defined sense from cat­e­gory the­o­rynoteSee free group func­tor is left ad­joint to for­get­ful for the rather ad­vanced rea­son why.) the purest way of mak­ing a group con­tain­ing the el­e­ments $$X$$, but to make it, we need to throw in in­verses for ev­ery el­e­ment of $$X$$, and then make sure the in­verses play nicely with the origi­nal el­e­ments (which we do by free re­duc­tion). That is why we need “freely-re­duced­ness”.

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

• Are all the words in the free group, or just the freely-re­duced words?

If the lat­ter, does say­ing that the group op­er­a­tion in­volves free re­duc­tion im­ply that only freely-re­duced words will end up in the free group? Be­cause, by de­fault I would as­sume that “the group has as its el­e­ment the words over $$X \cup X^{-1}$$” means that all the words (in­clud­ing non-freely-re­duced ones) are in the free group.

• You’re quite right to flag this up; I was be­ing sloppy. There are three main ways to con­struct the free group, and I’ve kind of mixed to­gether the two of them which are most in­tu­itive. I’m try­ing not to sim­ply define the free group here, but you’re right that I’ve done it con­fus­ingly. I’ll fix it.

• It sounds like you didn’t already know what the free group is; in that case (and even if you did already know), it’s very grat­ify­ing to know that some­one is ac­tu­ally read­ing this care­fully!

• That’s right. I know very lit­tle group the­ory.

I was just re­mark­ing to Stephanie how I was able to un­der­stand ev­ery­thing on this page, right be­fore I got to that sen­tence that I found con­fus­ing :-)

• Are you oth­er­wise broadly Math 3? It would be good to have a guinea pig for group the­ory.

• Prob­a­bly more like Math 2 or 2.5. I’m a pro­gram­mer with­out any for­mal train­ing in math be­yond what’s re­quired to get an elec­tri­cal en­g­ineer­ing de­gree.

Oc­ca­sion­ally I skim math blogs out of cu­ri­os­ity, but fre­quently don’t un­der­stand what I’m read­ing.