# Testing for the cancellation laws

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.

## 1 Answer

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.

• 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. – Bartek Jan 16 '14 at 7:53