1
$\begingroup$

Let $ X $ be a monoid which is generated by the elements $ x_1, x_2, \hat x_1, \hat x_2 $ and the relations $ \hat x_i x_i = 1 $ and $ x_i \hat x_j = \hat x_j x_i $ for any distinct $ i, j = 1, 2 $.

By the relations, any element of $ X $ can be written as an element of the form $ \omega \hat \omega $ with $ \omega = \prod_{i = 1}^r c_i $ and $ c_i \in \langle x_1, x_2 \rangle $ and $ \hat \omega = \prod_{i = 1}^{\hat r} \hat c_i $ and $ \hat c_i \in \langle \hat x_1, \hat x_2 \rangle $.

Now, since there are no further defining relations, I think the $ c_i $ and $ \hat c_i $ should be uniquely determined. But I am not sure, how to prove this rigorously.

Thanks

$\endgroup$
9
  • 1
    $\begingroup$ This is a complete rewriting system I believe and your normal forms are the irreducible forms so they are distinct. You could also build an action on those normal forms to use the van der Waerden trick $\endgroup$ Mar 13, 2021 at 13:16
  • 1
    $\begingroup$ You can build operators $y_i$ and $\hat{y_i}$ that act on your normal forms by $y_i$ places $x_i$ at the left end and $\hat{y_i}$ removes the left most occurrence of $x_i$ if there is any and if not it inserts $\hat{x_i}$ as the leftmost hatted letter. You can check these satisfy your defining relations and a y-word sends the empty normal form to the x-word normal form of the y-word $\endgroup$ Mar 13, 2021 at 13:21
  • 1
    $\begingroup$ I think it's just a standard name for the trick where you solve the word problem for a monoid or group by having our act on the set of normal forms. I learned that terminology in grad school $\endgroup$ Mar 13, 2021 at 15:57
  • 1
    $\begingroup$ If you are acting on the left then i think you should get the normal form from the empty word not the reversed. That means the normal form Is unique because different normal forms act differently on the empty word $\endgroup$ Mar 14, 2021 at 3:41
  • 1
    $\begingroup$ Anyway, this is a neat trick. Thank you for explaining it. $\endgroup$
    – diddy
    Mar 14, 2021 at 9:26

1 Answer 1

1
$\begingroup$

The suggestion 'defining a complete rewriting system' in one of the comments of BenjaminSteinberg yields the following proof:

We use the definitions and theorems in https://en.wikipedia.org/wiki/Abstract_rewriting_system#Normal_forms_and_the_word_problem

Let $ \Sigma^* $ be the free monoid in the alphabet $ \Sigma = \{ z_1, z_2, \hat z_1, \hat z_2 \} $. We define the rewriting system $ R = \{ \hat z_i z_i \to 1, \hat z_i z_j \to z_j \hat z_i : i, j = 1, 2 \text{ and } i \ne j \} $. Let $ S $ be the equivalence relation on $ \Sigma^* $ which is generated by $ R $. Then $ \Sigma^* \to X $ via $ z_i \mapsto x_i $ and $ \hat z_i \mapsto \hat x_i $ induces an isomorphism $ \Sigma^* / S \to X $. Thus, we may identify $ X $ with $ \Sigma^* / S $. Then the starting question becomes: Is there exactly one $ R $-irreducible form in each class in $ \Sigma^* / S $?

For that, we show that $ ( \Sigma^*, R ) $ is Noetherian and locally confluent. Then Newman's Lemma provides that $ ( \Sigma^*, R ) $ is also confluent (this is the door opener) and, therefore, canonical (also called complete). Those systems provide that there is exactly one $ R $-irreducible form in each class in $ \Sigma^* / S $.

For $ ( \Sigma^*, R ) $ being Notherian: There are only finitely many times that only the rules $ \hat z_i z_j \to z_j \hat z_i $ can be applied on a word. Then the word is either irreducible or the rule $ \hat z_i z_i \to 1 $ can be applied for some $ i = 1, 2 $. But, this shortens the word. Hence, the second case only appear finitely many times.

For $ ( \Sigma^*, R ) $ being locally confluent: Independent of this particular rewriting system, it is enough to check local confluence for words $ w $ of the form $ w = u v t $ and rules of the form $ u v \to u' $ and $ v t \to t' $. But, there are no such rules in $ R $. Therefore, it follows trivially that $ ( \Sigma^*, R ) $ is locally confluent. q.e.d

I am a little suspicious because the statement (uniqueness in the question) followed more or less without effort. Either I made a mistake or the actual work was done by Newmann's Lemma.

$\endgroup$
11
  • 1
    $\begingroup$ Do you really mean "words of the form $w = u v w$"? I understand that there's no contradiction since you're working in a monoid rather than a group, but it looks a little surprising. $\endgroup$
    – LSpice
    Mar 13, 2021 at 16:52
  • 1
    $\begingroup$ @LSpice you are right. Thanks. I change that. $\endgroup$
    – diddy
    Mar 13, 2021 at 16:54
  • $\begingroup$ You are missing many cases of local confluence (and this is the only non-trivial part of this being a complete rewriting system, so it is very important to get right!). For example, if you have $x_1 \hat{x}_2 \to \hat{x}_2 x_1$ and $\hat{x}_2 \hat{x}_2 \to 1$, then these overlap in the word $w \equiv x_1 \hat{x}_2 \hat{x}_2$. $\endgroup$ Mar 13, 2021 at 17:01
  • $\begingroup$ @Carl-FredrikNybergBrodda what you wrote is not an overlap. His rule is to move hats to the left. I think the proof he wrote is fine $\endgroup$ Mar 13, 2021 at 17:13
  • $\begingroup$ @Carl-FredrikNybergBrodda all is rules move hats to the left so there is never an ambiguity. You can only apply rules disjointly $\endgroup$ Mar 13, 2021 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.