Monus

Truncating subtraction on natural numbers, or a generalization thereof

In mathematics, monus is an operator on certain commutative monoids that are not groups. A commutative monoid on which a monus operator is defined is called a commutative monoid with monus, or CMM. The monus operator may be denoted with the − symbol because the natural numbers are a CMM under subtraction; it is also denoted with the  − ˙ {\displaystyle \mathop {\dot {-}} } symbol to distinguish it from the standard subtraction operator.

## Notation

[edit]

glyph | Unicode name  | Unicode code point[1] | HTML character entity reference | HTML/XML numeric character references | TeX

|
|
|
|
|

∸  | DOT MINUS | U+2238  |  | `&#8760;` | `\dot -`
−  | MINUS SIGN | U+2212  | `&minus;` | `&#8722;` | `-`

## Definition

[edit]

Let  ( M , + , 0 ) {\displaystyle (M,+,0)} be a commutative monoid. Define a binary relation ≤ {\displaystyle \leq } on this monoid as follows: for any two elements  a {\displaystyle a} and  b {\displaystyle b} , define  a ≤ b {\displaystyle a\leq b} if there exists an element  c {\displaystyle c} such that  a + c = b {\displaystyle a+c=b} . It is easy to check that  ≤ {\displaystyle \leq } is reflexive[2] and that it is transitive.[3] M {\displaystyle M} is called naturally ordered if the  ≤ {\displaystyle \leq } relation is additionally antisymmetric and hence a partial order. Further, if for each pair of elements  a {\displaystyle a} and  b {\displaystyle b} , a unique smallest element  c {\displaystyle c} exists such that  a ≤ b + c {\displaystyle a\leq b+c} , then M is called a commutative monoid with monus[4]: 129 and the monus a − ˙ ⁡ b {\displaystyle a\mathop {\dot {-}} b} of any two elements  a {\displaystyle a} and  b {\displaystyle b} can be defined as this unique smallest element  c {\displaystyle c} such that  a ≤ b + c {\displaystyle a\leq b+c} .

An example of a commutative monoid that is not naturally ordered is  ( Z , + , 0 ) {\displaystyle (\mathbb {Z} ,+,0)} , the commutative monoid of the integers with usual addition, as for any  a , b ∈ Z {\displaystyle a,b\in \mathbb {Z} } there exists  c {\displaystyle c} such that  a + c = b {\displaystyle a+c=b} , so  a ≤ b {\displaystyle a\leq b} holds for any  a , b ∈ Z {\displaystyle a,b\in \mathbb {Z} } , so  ≤ {\displaystyle \leq } is not a partial order. There are also examples of monoids that are naturally ordered but are not semirings with monus.[5]

## Other structures

[edit]

Beyond monoids, the notion of monus can be applied to other structures. For instance, a naturally ordered semiring (sometimes called a dioid[6]) is a semiring where the commutative monoid induced by the addition operator is naturally ordered. When this monoid is a commutative monoid with monus, the semiring is called a semiring with monus, or m-semiring.

## Examples

[edit]

If M is an ideal in a Boolean algebra, then M is a commutative monoid with monus under  a + b = a ∨ b {\displaystyle a+b=a\vee b} and  a − ˙ ⁡ b = a ∧ ¬ b {\displaystyle a\mathop {\dot {-}} b=a\wedge \neg b} .[4]: 129

### Natural numbers

[edit]

The natural numbers including 0 form a commutative monoid with monus, with their ordering being the usual order of natural numbers and the monus operator being a saturating variant of standard subtraction, variously referred to as truncated subtraction,[7] limited subtraction, proper subtraction, doz (difference or zero),[8] and monus.[9] Truncated subtraction is usually defined as[7]

a − ˙ ⁡ b = { 0 if a < b a − b if a ≥ b , {\displaystyle a\mathop {\dot {-}} b={\begin{cases}0&{\mbox{if }}a<b\\\a-b&{\mbox{if }}a\geq b,\end{cases}}}

where − denotes standard subtraction. For example, 5 − 3 = 2 and 3 − 5 = −2 in regular subtraction, whereas in truncated subtraction 3 ∸ 5 = 0. Truncated subtraction may also be defined as[9]

a − ˙ ⁡ b = max ( a − b , 0 ) . {\displaystyle a\mathop {\dot {-}} b=\max(a-b,0).}

In Peano arithmetic, truncated subtraction is defined in terms of the predecessor function P (the inverse of the successor function):[7]

P ( 0 ) = 0 P ( S ( a ) ) = a a − ˙ ⁡ 0 = a a − ˙ ⁡ S ( b ) = P ( a − ˙ ⁡ b ) . {\displaystyle {\begin{aligned}P(0)&=0\\\P(S(a))&=a\\\a\mathop {\dot {-}} 0&=a\\\a\mathop {\dot {-}} S(b)&=P(a\mathop {\dot {-}} b).\end{aligned}}}

A definition that does not need the predecessor function is:

a − ˙ ⁡ 0 = a 0 − ˙ ⁡ b = 0 S ( a ) − ˙ ⁡ S ( b ) = a − ˙ ⁡ b . {\displaystyle {\begin{aligned}a\mathop {\dot {-}} 0&=a\\\0\mathop {\dot {-}} b&=0\\\S(a)\mathop {\dot {-}} S(b)&=a\mathop {\dot {-}} b.\end{aligned}}}

Truncated subtraction is useful in contexts such as primitive recursive functions, which are not defined over negative numbers.[7] Truncated subtraction is also used in the definition of the multiset difference operator.

## Properties

[edit]

The class of all commutative monoids with monus form a variety.[4]: 129 The equational basis for the variety of all CMMs consists of the axioms for commutative monoids, as well as the following axioms:

a + ( b − ˙ ⁡ a ) = b + ( a − ˙ ⁡ b ) , ( a − ˙ ⁡ b ) − ˙ ⁡ c = a − ˙ ⁡ ( b + c ) , ( a − ˙ ⁡ a ) = 0 , ( 0 − ˙ ⁡ a ) = 0. {\displaystyle {\begin{aligned}a+(b\mathop {\dot {-}} a)&=b+(a\mathop {\dot {-}} b),\\\\(a\mathop {\dot {-}} b)\mathop {\dot {-}} c&=a\mathop {\dot {-}} (b+c),\\\\(a\mathop {\dot {-}} a)&=0,\\\\(0\mathop {\dot {-}} a)&=0.\\\\\end{aligned}}}

## Notes

[edit]

1. ^ Characters in Unicode are referenced in prose via the "U+" notation. The hexadecimal number after the "U+" is the character's Unicode code point.
2. ^ taking  c {\displaystyle c} to be the neutral element of the monoid
3. ^ if  a ≤ b {\displaystyle a\leq b} with witness  d {\displaystyle d} and  b ≤ c {\displaystyle b\leq c} with witness  d ′ {\displaystyle d'} then  d + d ′ {\displaystyle d+d'} witnesses that  a ≤ c {\displaystyle a\leq c}
4. ^ a b c Amer, K. (1984), "Equationally complete classes of commutative monoids with monus", Algebra Universalis, 18: 129–131, doi:10.1007/BF01182254
5. ^ M.Monet (2016-10-14). "Example of a naturally ordered semiring which is not an m-semiring". Mathematics Stack Exchange. Retrieved 2016-10-14.
6. ^ Semirings for breakfast, slide 17
7. ^ a b c d Vereschchagin, Nikolai K.; Shen, Alexander (2003). Computable Functions. Translated by V. N. Dubrovskii. American Mathematical Society. p. 141\. ISBN 0-8218-2732-4.
8. ^ Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley \- Pearson Education, Inc. ISBN 978-0-321-84268-8.
9. ^ a b Jacobs, Bart (1996). "Coalgebraic Specifications and Models of Deterministic Hybrid Systems". In Wirsing, Martin; Nivat, Maurice (eds.). Algebraic Methodology and Software Technology. Lecture Notes in Computer Science. Vol. 1101\. Springer. p. 522\. ISBN 3-540-61463-X.