proof of diamond lemma
If the cancellations $aa^{-1}$ and $bb^{-1}$ overlap then either:
- The occurrences of $aa^{-1}, bb^{-1}$ are the same word, so $w=paa^{-1}q=pbb^{-1}q$ and $w_1=pq=w_2$.
- If the occurrences of $aa^{-1}, bb^{-1}$ overlap but are non-equal then $w=paa^{-1}aq$, where $a^{-1}a=bb^{-1}$ (i.e. $a=b^{-1}$ and $a^{-1}=b$), and we have $$ paq=w_1\xleftarrow{aa^{-1}}w\xrightarrow{a^{-1}a}w_2=paq. $$
In both cases, we have that $w_1=w_2$, and the result follows.