Given a set $X$ and two words on $X$, $w=x_1^{\varepsilon_1} \cdots x_n^{\varepsilon_n}$ and $w'=y_1^{\delta_1} \cdots y_m^{\delta_m}$, we define that $w$ is equivalent to $w'$, $w \sim w'$, if there exists a finite sequence $w_0, w_1, \cdots, w_k$ of words such that $w_0=w$, $w_k=w'$ and for every $i=0, \cdots, k-1$, $w_{i+1}$ is obtained from $w_i$ by applying one of the following operations:
- Introduce at the beggining, at the end or between two letters of $w_i$ the empty word or a word of the form $xx^{-1}$ or $x^{-1}x$
- Delete from $w_i$ the empty word or a word of the form $xx^{-1}$ or $x^{-1}x$
Now I've proven by induction on the length of the word that every word is equivalent to a reduced word (that's one with no empty word or blocks of the form $xx^{-1}$ or $x^{-1}x$ as subwords) but I'm not able to rigurouly prove that this word is unique, that is, that two distinct reduced words cannot be equivalent.
Could someone give a rigurous proof of this fact?
Thank you.
Best Answer
Suppose that $w_1$ and $w_2$ are equivalent reduced words. We want to prove that $w_1=w_2$.
So there is a path from $w_1$ to $w_2$, where each move in the path consists of either inserting or deleting a word $xx^{-1}$ or $x^{-1}x$.
Let $l$ be the maximum length of any word in this path, and suppose that $k$ words in this path have length $l$. Choose a path with $kl$ minimal. We will derive a contradiction by replacing the path by a different path with a smaller value of $kl$.
If the path has length $0$ then there is nothing to prove, and otherwise there must be successive words $v_1$, $v_2$, $v_3$ in the path where $v_2$ has length $l$ and $v_1$ and $v_3$ have length $l-1$.
So we get $v_2$ from $v_1$ by inserting $xx^{-1}$ somewhere and $v_3$ from $v_2$ by deleting $yy^{-1}$, where $x$ and $y$ are generators or inverses of generators.
If the substrings $xx^{-1}$ of $v_2$ do not overlap, then we can get to $v_3$ by first deleting $yy^{-1}$ and then inserting $xx^{-1}$ thereby reducing $kl$.
Otherwise they overlap. If they are equal then we can just eliminate them both. Otherwise they overlap in a single generator, and $v_2$ contains the substring $xx^{-1}y$ with $y=x$, or $yxx^{-1}$ with $y=x^{-1}$, and in both cases we have $v_1=v_3$, so we can again eliminate both moves, reducing $kl$.
There may be quicker proofs than this, but I like it because it extends to a much more general result in the theory of string rewriting syaytems, which says that local confluence implies confluence.