[todo: make Free Group a parent of this]

[todo: make the summary a bit better] [summary: A "word" over a set $~$X$~$ is a finite ordered list of elements from $~$X$~$ and $~$X^{-1}$~$ (where $~$X^{-1}$~$ is the set of formal inverses of the elements of $~$X$~$), as if we were treating the elements of $~$X$~$ and $~$X^{-1}$~$ as letters of an alphabet. A "freely reduced" word over $~$X$~$ is one which doesn't contain any consecutive cancelling letters such as $~$x x^{-1}$~$.]

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 \}$~$ %%note:Though 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).

%%hidden(Alternative, more opaque, treatment which might help with one aspect): This chunk is designed to get you familiar with the idea that the symbols $~$a^{-1}$~$, $~$b^{-1}$~$ and so on in $~$X^{-1}$~$ don't have any inherent meaning.

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" %%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$~$). %%note:We 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 theory%%note:See [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".

## Comments

Eric Rogstad

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.