3
$\begingroup$

We are working with a commutative monoid. Subtraction might be useful for us.

However, we're not sure how to proceed -- negative elements have no meaning.

  • How do we deal with allowing subtraction in certain cases, but not in others?
  • What algebraic structure (if any) do we apply here?

I think our problem is similar to this:

The commutative monoid is the non-negative integers, together with addition. 4 - 2 = 2 would be useful, but 2 - 4 = ??? would not be useful, since the answer would not be a non-negative integer.

  • 2
    Well, if your monoid is cancellative (ie if $a+b=a+c$ implies that $b=c$ for all $a,b,c$ in the monoid), then you can form the quotient group in a similar way to how one forms the quotient field of an integral domain.2011-11-28
  • 0
    @Jack, quotient by what?2011-11-28
  • 0
    @AlexeiAverchenko - Take a look at my answer below, along with Qiaochu Yuan's answer. Given an integral domain, one may form the quotient field (or field of fractions http://en.wikipedia.org/wiki/Field_of_fractions). There is an analogous construction of the quotient group of a commutative cancellative monoid.2011-11-28
  • 1
    Related: http://math.stackexchange.com/questions/79453/when-a-semigroup-can-be-embedded-into-a-group2011-11-28
  • 0
    The forgetful functor from commutative groups to commutative monoids has a left adjoint: see this [Wikipedia entry](http://en.wikipedia.org/wiki/Adjoint_functors#In_algebra).2011-11-29

2 Answers 2

1

I decided to expand upon my comment a bit. I'll denote the monoid in question by $M$ and assume that $M$ is cancellative and that the operation of $M$ is denoted additively (of course, if it isn't, then replace subtraction by reciprocal, etc...the notation for the monoid operation isn't terribly important).

So, going back to the case of $\mathbb{M}=\mathbb{N}_0:=\mathbb{N}\cup \{0\}$, what would we mean by something like -2? Assuming that we knew what subtraction meant, we could write -2 in many ways: $-2=2-4=5-7=131-133$, etc (just like there are many ways to write fractions: $\frac{1}{3}=\frac{3}{9}=\frac{7}{21}$, etc). This may smell a bit as though there's an equivalence relation afoot, and there is.

Consider the relation $\sim$ on $M\times M$ by $(a,b) \sim (c,d)\,\Leftrightarrow a+d=b+c$ (ie if we knew what subtraction was, we'd have $a-b=c-d$). It turns out that this is an equivalence relation (it would be a good exercise to provide a proof of this). We then define the quotient group $Q$ of $M$ to be the set of equivalence classes of $\sim$ on $M\times M$. The operation in $Q$, which I'll denote by $\oplus$ (so that we don't confuse it with the operation in $M$), is merely defined by

$[a,b]\oplus [c,d] = [a+c,b+d]$, where $[x,y]$ denotes the equivalence class of $(x,y)$ (ie $[x,y]=${$(a,b)\in M\times M\,\vert\,(a,b)\sim (x,y)$}).

So, we have $0_Q=[m,m]$ for any $m\in M$, and we can identify $m\in M$ with $[m,0]\in Q$. Of course, it's a worthwhile exercise to prove that the elements of $Q$ form a group under $\oplus$.

3

The result of the subtraction $a - b$ is any element $c$, if it exists, such that $a = b + c$. Unfortunately, in a general commutative monoid,

  • $c$ may not exist, or
  • there may exist more than one such $c$.

The non-negative integers gives a simple example of the first case. As a simple example of the second case, consider the non-negative integers under the operation $\text{min}(a, b)$.

In other words, in general subtraction is partially defined and multivalued; it is better thought of as a relation than as a function.

I am not sure what "working with" means here so I don't know what else would be useful to say.


To explain Jack Maney's comment, associated to any commutative monoid $M$ is a universal map to an abelian group $M \to A$. The group $A$ is called the Grothendieck group of $M$ and is, roughly speaking, the minimal way to adjoin inverses to $M$. It can explicitly be constructed as the quotient of the monoid of pairs $(m, n) \in M^2$ under componentwise addition by the following equivalence relation:

$$(m, n) \sim (p, q) \Leftrightarrow \exists r : m + q + r = n + p + r.$$

(One should think of $(m, n)$ as formally representing $m - n$.) When fed the non-negative integers this construction returns the integers. Unfortunately, the map $M \to A$ is not injective in general, so one loses information in general. It is injective if and only if $M$ is cancellative.

  • 0
    Thanks for the response. This is part of a programming project using Haskell; we want to understand our data as fully as possible using algebraic structures. So basically, we shouldn't worry about putting subtraction into our algebraic structure? That's perfectly acceptable for us.2011-11-28
  • 0
    @Matt: if your monoid isn't cancellative, and especially if computing all possible subtractions might be difficult, I wouldn't worry about it until a specific need arises.2011-11-28
  • 0
    I know this post is rather old, but shouldn't you use $\max$ instead of $\min$ to get a commutative, non-cancellative monoid structure on the non-negative integers? This way $0$ is an identity element.2014-08-14