Monoids with left common multiples

Question

So this is a result which I think is true but have yet to find a quick proof for.

Say $M$ is a monoid which is left cancellative ($xy=xz\Rightarrow y=z$) and admits left common multiples ($\forall y,z \exists w,x \,(wy=xz)$). Is it then true that $M$ is right cancellative? If not, can you provide an explicit counterexample? Thanks!

Answer 1

If your monoid $M$ is right cancellative, then it embeds into a group [A. H. Clifford, G. B. Preston, The algebraic theory of semigroups, Theorem 1.23 (Ore theorem)]. On another hand there are left cancellative semigroups with left common multiples which do not embed into a group. For example Baer--Levi semigroups [A. H. Clifford, G. B. Preston, Theorem 8.2] are right cancellative with right common multiples and they do not embed into groups. So a semigroups, antiisomorphic to Baer--Levi semigroups, are desired counterexamples.

Answer 2

Consider the monoid of one-to-one functions from the set $\mathbb N$ of natural numbers into (not necessarily onto) itself. The monoid operation is composition, and my notational convention is that $xy$ means first apply $y$ and then apply $x$. This is left cancellative because the functions are one-to-one. To prove the existence of left common multiples, I'll prove a little more, namely that, for any $z$, there exists $x$ such that $xz$ is the function $n\mapsto2n$. Given $z$, it's easy to define such an $x$: On the range of $z$, it's defined (as it must be) by $x(z(n))=2n$; off the range of $z$, it maps everything in a one-to-one way into the set of odd numbers. Applying this construction to $z$ and also to a given $y$, we get the $x$ and $w$ needed for the left common multiples property. But right cancellation fails, because our maps need not be onto $\mathbb N$. Given any non-surjective $z$ in our monoid, we can construct $x$ as above and then, as the complement of the range of $z$ isn't empty, construct a different $x'$ that differs from $x$ at a point not in the range of $z$ but has $x'z=xz$.

For a countable example, just cut down to the set of arithmetically definable elements of this monoid. (By "arithmetically definable", I mean definable in first-order logic with symbols for addition and multiplication and with variables ranging over $\mathbb N$. The point is that all the constructions used above can easily be done definably.)