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!

  • $\begingroup$ Just playing around with the algebra, it doesn't seem very likely. I'll see if I can construct a counterexample. (I could of course be wrong). $\endgroup$
    – Dan Rust
    Aug 18, 2013 at 15:51

2 Answers 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.)


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.

  • $\begingroup$ Interesting! By any chance do you know of any countable counterexamples? $\endgroup$
    – Andy
    Aug 18, 2013 at 17:07
  • $\begingroup$ No, unfortunately I don't know. $\endgroup$ Aug 18, 2013 at 17:50
  • $\begingroup$ @Andy: Since you have a countable axiomatization of monoids with left common multiples and no right cancellation, you can trivially get a countable model from mere consistency by the standard Henkin construction as used in the proof of the completeness theorem for first-order logic. $\endgroup$
    – user21820
    May 20, 2018 at 12:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .