2
$\begingroup$

When I'm given a presentation of a finitely generated semigroup/monoid, are there any tricks I could use to check if it is cancellative on both sides? I'm not asking for a general algorithm, as I believe it could be impossible to find one, but just tips on how to deal with the problem when faced with a, say, two- or three-generated semigroup with not too many relations. Are there any useful necessary or sufficient conditions?

I know for example that any idempotent in a cancellative semigroup is necessarily an identity element, which can be used to refute cancellativity easily in some cases. Are there any other (preferably more powerful) useful methods?

Edit: The reasons for this question are strongly noncommutative. I would be happy to learn something useful about the commutative case, but what I'm interested in at the moment are noncommutative semigroups.

Edit 2: Oh, and of course I do realize that a relation like $xy=zy$ will rule cancellativity out whenever I can prove $x\neq z$. I'd better show an example of what I mean (I do not know whether this is cancellative or not):

$$\langle x,y\,|\,x^2=y^2\rangle.$$

I would like to know some methods by which I could crack examples like this.

$\endgroup$
1
$\begingroup$

I cannot help in general, but your example is cancellative.

It has a confluent rewriting system, $y^2 \to x^2$, $yx^2 \to x^2y$, which allows you to rewrite all elements to a normal form that looks like $x^i(yx)^j$ or $x^i(yx)^jy$ with $i,j \ge 0$.

Suppose that $w_1,w_2$ are elements with $xw_1=xw_2$. Then none of the rules used to rewrite these words to normal form will involve the initial $x$, so $w_1$ and $w_2$ must rewrite to the same normal form word, and hence $w_1=w_2$.

Then by symmetry $w_1x=w_2x$, $yw_1=yw_2$ and $w_1y=w_2y$ all imply $w_1=w_2$, so the monoid/semigroup is cancellative.

$\endgroup$
  • $\begingroup$ Dear Derek, this seems to be a great answer, exactly what I expected, actually. Unfortunately, I don't undestand it yet. I don't know anything about rewriting systems; I only encountered the term yesterday. But it does seem to be something I just have to understand, so I'm optimistic. If you could give some explanation in the answer, that would be great, but if you can't I will accept this answer soon too. $\endgroup$ – Bartek Jan 16 '14 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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