View source for Monus

{{short description|Truncating subtraction on natural numbers, or a generalization thereof}}
In mathematics, '''monus''' is an operator on certain [[commutative property|commutative]] [[monoid#Commutative monoid|monoid]]s that are not [[group (mathematics)|group]]s. 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 '''&minus;''' symbol because the [[natural number]]s are a CMM under [[subtraction]]; it is also denoted with the <math>\mathop {\dot -}</math> symbol to distinguish it from the standard subtraction operator.

== Notation ==
{| class="wikitable" style="text-align:center; width:70%"
! [[glyph]]
! [[Unicode]] name
! Unicode code point<ref>[[Character (computing)|Character]]s in Unicode are referenced in prose via the "U+" notation. The [[hexadecimal]] number after the "U+" is the character's Unicode code point.</ref>
! [[List of XML and HTML character entity references|HTML character entity reference]]
! HTML/[[XML]] [[numeric character reference]]s
![[TeX]]
|-
| ∸
| <small>DOT MINUS</small>
| U+2238
|
| <code>&amp;#8760;</code>
| <code>\dot&nbsp;-</code>
|-
| −
| <small>MINUS SIGN</small>
| U+2212
| <code>&amp;minus;</code>
| <code>&amp;#8722;</code>
| <code>-</code>
|}

== Definition ==
Let <math>(M, +, 0)</math> be a commutative [[monoid]]. Define a [[binary relation]] <math>\leq</math> on this monoid as follows: for any two elements <math>a</math> and <math>b</math>, define <math>a \leq b</math> if there exists an element <math>c</math> such that <math>a + c = b</math>. It is easy to check that <math>\leq</math> is [[reflexive relation|reflexive]]<ref>taking <math>c</math> to be the [[neutral element]] of the monoid</ref> and that it is [[transitive relation|transitive]].<ref>if <math>a \leq b</math> with witness <math>d</math> and <math>b \leq c</math> with witness <math>d'</math> then <math>d + d'</math> witnesses that <math>a \leq c</math></ref> <math>M</math> is called ''naturally ordered'' if the <math>\leq</math> relation is additionally [[antisymmetric relation|antisymmetric]] and hence a [[partial order]]. Further, if for each pair of elements <math>a</math> and <math>b</math>, a unique smallest element <math>c</math> exists such that <math>a \leq b + c</math>, then {{math|''M''}} is called a ''commutative monoid with monus''<ref name="Amer">
  {{citation
    |last=Amer
    |first=K.
    |title=Equationally complete classes of commutative monoids with monus
    |journal=Algebra Universalis
    |year=1984
    |doi=10.1007/BF01182254
    |volume=18
    |pages=129&ndash;131}}</ref>{{rp|129}} and the ''monus'' <math>a \mathop {\dot -} b
</math> of any two elements <math>a</math> and <math>b</math> can be defined as this unique smallest element <math>c</math> such that <math>a \leq b + c</math>.

An example of a commutative monoid that is not naturally ordered is <math>(\mathbb{Z}, +, 0)</math>, the commutative monoid of the [[integer]]s with usual [[addition]], as for any <math>a, b \in \mathbb{Z}</math> there exists <math>c</math> such that <math>a + c = b</math>, so <math>a \leq b</math> holds for any <math>a, b \in \mathbb{Z}</math>, so <math>\leq</math> is not a partial order. There are also examples of monoids that are naturally ordered but are not semirings with monus.<ref>{{cite web
  |title=Example of a naturally ordered semiring which is not an m-semiring
  |author=M.Monet
  |publisher=Mathematics Stack Exchange
  |date=2016-10-14
  |accessdate=2016-10-14
  |url=https://math.stackexchange.com/q/1968090
}}</ref>

== Other structures ==

Beyond monoids, the notion of monus can be applied to other structures. For instance, a '''naturally ordered semiring''' (sometimes called a '''dioid'''<ref>[http://marcpouly.ch/pdf/internal_100712.pdf Semirings for breakfast], slide 17</ref>) 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 ==
If {{math|''M''}} is an [[Semigroup#Subsemigroups and ideals|ideal]] in a [[Boolean algebra]], then {{math|''M''}} is a commutative monoid with monus under <math>a + b = a \vee b
</math> and <math>a \mathop {\dot {-}} b = a \wedge \neg b
</math>.<ref name="Amer" />{{rp|129}}

=== Natural numbers ===
The [[natural number]]s including 0 form a commutative monoid with monus, with their ordering being the usual order of natural numbers and the monus operator being a [[Saturation arithmetic|saturating]] variant of standard subtraction, variously referred to as '''truncated subtraction''',<ref name="Computable Functions">
{{cite book
  |last=Vereschchagin
  |first=Nikolai K.
  |last2=Shen
  |first2=Alexander
  |translator=V. N. Dubrovskii
  |title=Computable Functions
  |publisher=[[American Mathematical Society]]
  |year= 2003
  |isbn = 0-8218-2732-4
  |pages = 141}}</ref> '''limited subtraction''', '''proper subtraction''', '''doz''' (''difference or zero''),<ref name="Warren_2013">{{cite book
  |title=Hacker's Delight
  |first=Henry S.
  |last=Warren Jr.
  |date=2013
  |edition=2
  |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]]
  |isbn=978-0-321-84268-8}}</ref> and '''monus'''.<ref name="Wirsing">
{{cite book
  |title = Algebraic Methodology and Software Technology
  |chapter = Coalgebraic Specifications and Models of Deterministic Hybrid Systems
  |last = Jacobs
  |first = Bart
  |pages = 522
  |editor-last = Wirsing
  |editor-first = Martin
  |editor-last2 = Nivat
  |editor-first2 = Maurice
  |year = 1996
  |publisher = Springer
  |isbn = 3-540-61463-X
  |series = Lecture Notes in Computer Science
  |volume = 1101
  |chapter-url = https://www.cs.ru.nl/B.Jacobs/PAPERS/AMAST96.ps
}}</ref> Truncated subtraction is usually defined as<ref name="Computable Functions" />
:<math>a \mathop {\dot -} b =
\begin{cases}
0 & \mbox{if } a < b \\
a - b & \mbox{if } a \ge b,
\end{cases}
</math>
where &minus; denotes standard [[subtraction]]. For example, 5 &minus; 3 = 2 and 3 &minus; 5 = &minus;2 in regular subtraction, whereas in truncated subtraction 3 ∸ 5 = 0. Truncated subtraction may also be defined as<ref name="Wirsing" />
:<math>a \mathop {\dot -} b = \max(a - b, 0).</math>

In [[Peano axioms|Peano arithmetic]], truncated subtraction is defined in terms of the predecessor function {{math|''P''}} (the inverse of the [[successor function]]):<ref name="Computable Functions" />
:<math>
\begin{align}
P(0)    &= 0 \\
P(S(a)) &= a \\
a \mathop {\dot -} 0 &= a \\
a \mathop {\dot -} S(b) &= P(a \mathop {\dot -} b).
\end{align}
</math>

A definition that does not need the predecessor function is:
:<math>
\begin{align}
a \mathop {\dot -} 0 &= a \\
0 \mathop {\dot -} b &= 0 \\
S(a) \mathop {\dot -} S(b) &= a \mathop {\dot -} b.
\end{align}
</math>

Truncated subtraction is useful in contexts such as [[primitive recursive function]]s, which are not defined over negative numbers.<ref name="Computable Functions" /> Truncated subtraction is also used in the definition of the [[multiset#Multiplicity function|multiset]] [[set difference|difference]] operator.

== Properties ==
The class of all commutative monoids with monus form a [[Variety (universal algebra)|variety]].<ref name="Amer" />{{rp|129}} The equational basis for the variety of all CMMs consists of the axioms for [[monoid#Commutative monoid|commutative monoids]], as well as the following axioms:

<math>\begin{align}
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{align}</math>

== Notes ==
<references />

[[Category:Algebraic structures]]