Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question on cancellation property

  1. May 24, 2010 #1
    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 [itex]\Rightarrow[/itex] a=b ?
  2. jcsd
  3. May 24, 2010 #2
    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?
    Last edited: May 24, 2010
  4. May 24, 2010 #3
    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 [itex]\forall a,b \in M, \\ a+k=b+k[/itex] 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 [itex]x+k'=y+k'[/itex] implies [itex]x\neq y[/itex].

    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 [itex](x+k)\neq(y+k)[/itex]

    (**) clearly contradicts the hypothesis (*), so shall we conclude (M,+) must be cancellative? Is this proof correct?
  5. May 25, 2010 #4
    The following is the table for a monoid constructed as I suggested. (I've used 1 instead of 0 for the identity.)

    [tex]\[ \left( \begin{array}{ccccc}
    & | & a & b & 1\\
    -& | & -& -&-\\
    a & | & a & b&a\\
    b & | & a & b&b\\
    1 & |&a&b&1
    \end{array} \right)\][/tex]

    Note that [itex]x+a=a[/itex] for each [itex]x[/itex], so [itex]a[/itex] will do as the "some k". But [itex]x+a=y+a[/itex] with [itex]x=a,y=b[/itex] and [itex]a\neq b[/itex], 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.
  6. May 25, 2010 #5


    User Avatar
    Science Advisor

    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.
    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.
  7. May 25, 2010 #6
    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.
  8. May 25, 2010 #7
    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 [itex]M[/itex] below (I've made it commutative and switched back to [itex]0[/itex] as the identity):

    [tex]\[ \left( \begin{array}{ccccc}
    & | & a & b & 0\\
    -& | & -& -&-\\
    a & | & a & a&a\\
    b & | &a & b&b\\
    0 & |&a&b&0\end{array} \right)\][/tex]

    this is not a cancellation monoid because e.g. [itex]b+a=0+a[/itex] and [itex]b\neq 0[/itex]. For any [itex]{(m_1,m_2),(n_1,n_2)\in M\times M}[/itex] we have [itex]{m_1+n_2+a=m_2+n_1+a}[/itex] so [itex]{(m_1,m_2)\sim(n_1,n_2)}[/itex] and there is only one equivalence class, hence only one member in the Grothendieck group. So [itex]M[/itex] (with 3 members) obviously can't be embedded in this case.
  9. May 25, 2010 #8
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook