reduced word

Let $X$ be a set, and ${\left(X\coprod X^{-1}\right)}^{\ast }$ the free monoid with involution on $X$. An element $w\in {\left(X\coprod X^{-1}\right)}^{\ast }$ can be uniquely written by juxtaposition of elements of $\left(X\coprod X^{-1}\right)$, i.e.

$$w=w_1{w}_2\mathrm{\dots }{w}_n,w_j\in \left(X\coprod X^{-1}\right),$$

then we may improperly say that $w$ is a word on ${\left(X\coprod X^{-1}\right)}^{\ast }$, considering ${\left(X\coprod X^{-1}\right)}^{\ast }$ simply as the free monoid on $\left(X\coprod X^{-1}\right)$.

The word $w=w_1{w}_2\mathrm{\dots }{w}_n\in {\left(X\coprod X^{-1}\right)}^{\ast }$ is called reduced when $w_j\ne w_{j+1}^{-1}$ for each $j\in \{1,2,\mathrm{\dots },n-1\}$.

Now, starting from a word $w=w_1{w}_2\mathrm{\dots }{w}_n\in {\left(X\coprod X^{-1}\right)}^{\ast }$, we can iteratively erase factors $w_j{w}_{j+1}$ from $w$ whenever $w_j=w_{j+1}^{-1}$, and this iterative process, that we call reduction of $w$, produce a reduced word $w^{\prime }\in {\left(X\coprod X^{-1}\right)}^{\ast }$. At each step of the process there may be more than one couple of adiacent letters candidate to be erased, so we may ask if different sequences of erasing may produce different reduced words. The following theorem answers the question.

Theorem 1

Each couple of reduction of a same word $w\mathrm{\in }{\mathrm{\left(}X\mathrm{\coprod }{X}^{\mathrm{-}\mathrm{1}}\mathrm{\right)}}^{\mathrm{\ast }}$ produce the same reduced word $w^{\mathrm{\prime }}\mathrm{\in }{\mathrm{\left(}X\mathrm{\coprod }{X}^{\mathrm{-}\mathrm{1}}\mathrm{\right)}}^{\mathrm{\ast }}$.

The unique reduced word $w^{\prime }$ is called the reduced form of $w$. Thus there exists a well define map $\mathrm{red}:{\left(X\coprod X^{-1}\right)}^{\ast }\to {\left(X\coprod X^{-1}\right)}^{\ast }$ that send a word $w$ to his reduced form $\mathrm{red}(w)$.

We can use the map $\mathrm{red}$ to build the free group on $X$ in the following way. Let $\mathrm{FG}(X)=\mathrm{red}\left({\left(X\coprod X^{-1}\right)}^{+}\right)$ be the set of reduced words on $\left(X\coprod X^{-1}\right)$, i.e.

$$\mathrm{FG}(X)=\mathrm{red}\left({\left(X\coprod X^{-1}\right)}^{+}\right)=\{\mathrm{red}(w)|w\in {\left(X\coprod X^{-1}\right)}^{+}\}=\{w\in {\left(X\coprod X^{-1}\right)}^{+}|w=\mathrm{red}(u)\}.$$

Note that $\mathrm{red}\left({\left(X\coprod X^{-1}\right)}^{\ast }\right)=\mathrm{red}\left({\left(X\coprod X^{-1}\right)}^{+}\right)$, being that $\mathrm{red}(x{x}^{-1})=\epsilon$, where $\epsilon$ denotes the empty word. Now, we define a product $\cdot$ on $\mathrm{FG}(X)$ that makes it a group: given $v,w\in \mathrm{FG}(X)$ we define

$$v\cdot w=\mathrm{red}(vw),$$

i.e. $v\cdot w$ is the reduced form of the juxtaposition of the words $v$ and $w$. The we have the following result.

Theorem 2

$\mathrm{FG}(X)$ with the product $\mathrm{\cdot }$ is a group. Moreover, it is the free group on $X$, in the sense that it solves the following universal problem: given a group $G$ and a map $\mathrm{\Phi }\mathrm{:}X\mathrm{\to }G$, a group homomorphism $\overline{\mathrm{\Phi }}\mathrm{:}\mathrm{FG}\mathit{}\mathrm{(}X\mathrm{)}\mathrm{\to }G$ exists such that the following diagram commutes:

where $\iota \mathrm{:}X\mathrm{\to }\mathrm{FG}\mathit{}\mathrm{(}X\mathrm{)}$ is the inclusion map.

It is well known from universal algebra that $\mathrm{FG}(X)$ is unique up to isomorphisms. With this construction, the map $\mathrm{red}:{\left(X\coprod X^{-1}\right)}^{+}\to \mathrm{FG}(X)$ [resp. $\mathrm{red}:{\left(X\coprod X^{-1}\right)}^{\ast }\to \mathrm{FG}(X)$] is the quotient projection from the free semigroup with involution on $X$ [resp. the free monoid with involution on $X$] and the free group on $X$.

Title	reduced word
Canonical name	ReducedWord
Date of creation	2013-03-22 16:11:47
Last modified on	2013-03-22 16:11:47
Owner	Mazzu (14365)
Last modified by	Mazzu (14365)
Numerical id	16
Author	Mazzu (14365)
Entry type	Definition
Classification	msc 20E05
Defines	reduced word
Defines	reduced form
Defines	reduction