Question on cancellation property

[mnb96]

I have a monoid (M,+), and I assume that for any two elements a,b in M it is always possible to find a third element k such that:

a + k = b + k

Is it possible to prove that M must be a cancellative monoid?
In other words, can I prove that a+k=b+k \Rightarrow a=b ?

 

[Martin Rattigan]

No - try a+b=b (which gives you a semigroup) then give the semigroup a 0 (which gives you a monoid).

In fact if you could prove what you say it would immediately follow that the monoid has only one element. Did you mean it is always possible to find k such that a+k=b?

 

[mnb96]

Thanks for the answer, though I feel a bit confused now.
When you were still answering I made an attempt and I don't know if it is correct or not.

we have that \forall a,b \in M, \\ a+k=b+k for some k. This is the hypothesis.
We want to check if this statements implies cancellativity.
Let's suppose that (M,+) is not cancellative; this means that the statement "a+k=b+k implies a=b" might not be valid in general.
From this follows there might exist some x,y for which we have x+k'=y+k' implies x\neq y.

Whenever this happens we have the following:
(*) for any x,y we have x+k = y+k for some k.
(**) (x+k)+k' = (y+k)+k' implies (x+k)\neq(y+k)

(**) clearly contradicts the hypothesis (*), so shall we conclude (M,+) must be cancellative? Is this proof correct?

 

[Martin Rattigan]

The following is the table for a monoid constructed as I suggested. (I've used 1 instead of 0 for the identity.)

\[ \left( \begin{array}{ccccc}<br /> &amp; | &amp; a &amp; b &amp; 1\\<br /> -&amp; | &amp; -&amp; -&amp;-\\<br /> a &amp; | &amp; a &amp; b&amp;a\\<br /> b &amp; | &amp; a &amp; b&amp;b\\<br /> 1 &amp; |&amp;a&amp;b&amp;1<br /> \end{array} \right)\]

Note that x+a=a for each x, so a will do as the "some k". But x+a=y+a with x=a,y=b and a\neq b, so ii's not a right cancellation semigroup.

I couldn't understand the proof, but unless I'm totally misunderstanding what you're saying it must be wrong.

 

[Landau]

Let's suppose that (M,+) is not cancellative; this means that the statement "a+k=b+k implies a=b" might not be valid in general.
From this follows there might exist some x,y for which we have x+k&#039;=y+k&#039; implies x\neq y.

No, this is NOT the negation. The negation of "for all x: A(x) => B(x)" is "there exists x such that A(x) holds, and B(x) does not hold". You are saying that the negation is "there exists x such that A(x) implies that B(x) does not hold".
That's why your conclusion (**) is incorrect.

(*) for any x,y we have x+k = y+k for some k.
(**) (x+k)+k' = (y+k)+k' implies (x+k)\neq(y+k)

You should read the first reply again. Is its very simple:
Assume that the result holds, i.e. M is indeed cancellative. Then:

for all a,b there exists k such that a+k=b+k
for all a,b,l we have that if a+l=b+l, then a=b.

Together, taking l=k, we get that for all a,b we have a=b. In other words, every element is the same: the monoid is trivial. The only monoid for which the result holds is the trivial one, containing only the identity.

 

[mnb96]

Hello,
thanks Martin for the concrete example and also thanks to Landau for the clear explanation.
It is very clear why that monoid can't be cancellative (unless it is the trivial monoid).

Now this discussion made me feel even more confused about a wikipedia article on the Grothendieck Group (the group which embeds an abelian semigroup or monoid).

Here it is said that a commutative monoid must have the property "for all a,b a+k=b+k for some k" in order to be embedded in a group: http://en.wikipedia.org/wiki/Grothendieck_group#Explicit_construction

Instead, in this other article it is said that a necessary and sufficient condition for embedding a commutative semigroup in a group is that the semigroup must be cancellative: http://en.wikipedia.org/wiki/Cancellative_semigroup#Embeddability_in_groups

This is very confusing.

 

[Martin Rattigan]

Now this discussion made me feel even more confused about a wikipedia article on the Grothendieck Group (the group which embeds an abelian semigroup or monoid).

Here it is said that a commutative monoid must have the property "for all a,b a+k=b+k for some k" in order to be embedded in a group: http://en.wikipedia.org/wiki/Grothendieck_group#Explicit_construction

Instead, in this other article it is said that a necessary and sufficient condition for embedding a commutative semigroup in a group is that the semigroup must be cancellative: http://en.wikipedia.org/wiki/Cancellative_semigroup#Embeddability_in_groups

This is very confusing.

I couldn't find the quote you referred to in the first link, the nearest I found was the specification of the equivalence relation used for the construction viz.

"We say that (m1, m2) is equivalent to (n1, n2) if, for some element k of M, m1 + n2 + k = m2 + n1 + k."

Note that the article doesn't say that the commutative monoid M is necessarily embedded in the constructed group (though this will be the case if it's a cancellation monoid - in this case the equivalence relation reduces to m1 + n2 = m2 + n1).

For example if you look at the table for a monoid M below (I've made it commutative and switched back to 0 as the identity):

\[ \left( \begin{array}{ccccc}<br /> &amp; | &amp; a &amp; b &amp; 0\\<br /> -&amp; | &amp; -&amp; -&amp;-\\<br /> a &amp; | &amp; a &amp; a&amp;a\\<br /> b &amp; | &amp;a &amp; b&amp;b\\<br /> 0 &amp; |&amp;a&amp;b&amp;0\end{array} \right)\]

this is not a cancellation monoid because e.g. b+a=0+a and b\neq 0. For any {(m_1,m_2),(n_1,n_2)\in M\times M} we have {m_1+n_2+a=m_2+n_1+a} so {(m_1,m_2)\sim(n_1,n_2)} and there is only one equivalence class, hence only one member in the Grothendieck group. So M (with 3 members) obviously can't be embedded in this case.

 

[mnb96]

Thanks a lot Martin!
That was a very clever observation.

If I understood correctly, the end of the story is that:

1) an abelian semigroup (monoid) must be cancellative in order to be embedded in group.
2) the explicit construction of the Grothendieck group is just a construction. If the monoid is not cancellative, the Grothendieck group can not embed it.
3) the property of the equivalence relation "there exist some k such that a+b'+k=b+a'+k" does not imply cancellativity. This was the main point I misunderstood.

Thanks again.