# Freely reduced word

make Free Group a parent of this

make the summary a bit better

Given a set \(X\), we can make a new set \(X^{-1}\) consisting of “formal inverses” of elements of \(X\). That is, we create a set of new symbols, one for each element of \(X\), which we denote \(x^{-1}\); so \($X^{-1} = \{ x^{-1} \mid x \in X \}\)$

By this stage, we have not given any kind of meaning to these new symbols. Though we have named them suggestively as \(x^{-1}\) and called them “inverses”, they are at this point just objects.

Now, we apply meaning to them, giving them the flavour of group inverses, by taking the union \(X \cup X^{-1}\) and making finite “words” out of this combined “alphabet”.

A finite word over \(X \cup X^{-1}\) consists of a list of symbols from \(X \cup X^{-1}\). For example, if \(X = \{ 1, 2 \}\) noteThough in general \(X\) need not be a set of numbers., then some words are:

The empty word, which we commonly denote \(\varepsilon\)

\((1)\)

\((2)\)

\((2^{-1})\)

\((1, 2^{-1}, 2, 1, 1, 1, 2^{-1}, 1^{-1}, 1^{-1})\)

For brevity, we usually write a word by just concatenating the “letters” from which it is made:

The empty word, which we commonly denote \(\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 together successive instances of the same letter. 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 definition of a **freely reduced** word: it is a word which has no subsequence \(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, indeed, as \(\{ x, y, z \}\), because there’s no meaning inherent in the \(a^{-1}\) symbol 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 examples of words over \(X \cup X^{-1}\) are:

The empty word, which we commonly denote \(\varepsilon\)

\(a\)

\(aaaa\)

\(b\)

\(b^{-1}\)

\(ab\)

\(ab^{-1}cbb^{-1}c^{-1}\)

\(aa^{-1}aa^{-1}\)

Of these, all except the last two are freely reduced. However, \(ab^{-1}cbb^{-1}c^{-1}\) contains the substring \(bb^{-1}\), so it is not freely reduced; and \(aa^{-1}aa^{-1}\) is not freely reduced (there are several ways to see this: it contains \(aa^{-1}\) twice and \(a^{-1} a\) once).

If we had (rather perversely) gone with \(\{ x, y, z \}\) as the corresponding “inverses” to \(\{ a, b, c \}\) (in that order), rather than \(\{ a^{-1}, b^{-1}, c^{-1} \}\) as our “inverses” <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 commonly denote \(\varepsilon\)

\(a\)

\(aaaa\), which we might also write as \(a^4\)

\(b\)

\(y\)

\(ab\)

\(aycbyz\)

\(axax\)

For the same reasons, all but the last two would be freely reduced. However, \(aycbyz\) contains the substring \(by\) so it is not freely reduced; and \(axax\) is not freely reduced (there are several ways to see this: it contains \(ax\) twice and \(xa\) once). %%

# Why are we interested in this?

We can use the freely reduced words to construct the free group on a given set \(X\); this group has as its elements the freely reduced words over \(X \cup X^{-1}\), and as its group operation “concatenation followed by free reduction” (that is, removal of pairs \(r r^{-1}\) and \(r^{-1} r\)). noteWe make this construction properly rigorous, and check that it is indeed a group, on the Free group page. The notion of “freely reduced” basically tells us that \(r r^{-1}\) is the identity for every letter \(r \in X\), as is \(r^{-1} r\); this cancellation of inverses is a property we very much want out of a group.

The free group is (in a certain well-defined sense from category theorynoteSee free group functor is left adjoint to forgetful for the rather advanced reason why.) the purest way of making a group containing the elements \(X\), but to make it, we need to throw in inverses for every element of \(X\), and then make sure the inverses play nicely with the original elements (which we do by free reduction). That is why we need “freely-reducedness”.

Parents:

- Mathematics
Mathematics is the study of numbers and other ideal objects that can be described by axioms.

Are all the words in the free group, or just the freely-reduced words?

If the latter, does saying that the group operation involves free reduction imply that only freely-reduced words will end up in the free group? Because, by default I would assume that “the group has as its element the words over \(X \cup X^{-1}\)” means that all the words (including non-freely-reduced ones) are in the free group.

You’re quite right to flag this up; I was being sloppy. There are three main ways to construct the free group, and I’ve kind of mixed together the two of them which are most intuitive. I’m trying not to simply define the free group here, but you’re right that I’ve done it confusingly. 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 gratifying to know that someone is actually reading this carefully!

That’s right. I know very little group theory.

I was just remarking to Stephanie how I was able to understand everything on this page, right before I got to that sentence that I found confusing :-)

Are you otherwise broadly Math 3? It would be good to have a guinea pig for group theory.

Probably more like Math 2 or 2.5. I’m a programmer without any formal training in math beyond what’s required to get an electrical engineering degree.

Occasionally I skim math blogs out of curiosity, but frequently don’t understand what I’m reading.