Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  user5137 Nov 28 '11 at 16:43
    
@Jack, quotient by what? –  Alexei Averchenko Nov 28 '11 at 17:03
    
@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 en.wikipedia.org/wiki/Field_of_fractions). There is an analogous construction of the quotient group of a commutative cancellative monoid. –  user5137 Nov 28 '11 at 17:18
1  
Related: math.stackexchange.com/questions/79453/… –  Martin Sleziak Nov 28 '11 at 17:24
    
The forgetful functor from commutative groups to commutative monoids has a left adjoint: see this Wikipedia entry. –  Pierre-Yves Gaillard Nov 29 '11 at 5:29
add comment

2 Answers

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Matt Fenwick Nov 28 '11 at 17:11
    
@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. –  Qiaochu Yuan Nov 28 '11 at 17:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.