Monoids with left common multiples 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! 
 A: 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.)
A: 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.
