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.