# Freely reduced word

https://arbital.com/p/freely_reduced_word

by Patrick Stevens Jul 22 2016 updated Jul 25 2016

"Freely reduced" captures the idea of "no cancellation" in a free group.

[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".

We can use the freely reduced words to construct the free group on a given set $X$; this group has as its elements the 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$$$\. 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\.
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.