monus

Let $(M,\; +,\; 0)$ be a commutative monoid. Define a binary relation $\backslash leq$ on this monoid as follows: for any two elements $a$ and $b$, define $a\; \backslash leq\; b$ if there exists an element $c$ such that $a\; +\; c\; =\; b$. It is easy to check that $\backslash leq$ is reflexivetaking $c$ to be the neutral element of the monoid and that it is transitive.if $a\; \backslash leq\; b$ with witness $d$ and $b\; \backslash leq\; c$ with witness $d\text{'}$ then $d\; +\; d\text{'}$ witnesses that $a\; \backslash leq\; c$ $M$ is called naturally ordered if the $\backslash leq$ relation is additionally antisymmetric and hence a partial order. Further, if for each pair of elements $a$ and $b$, a unique smallest element $c$ exists such that $a\; \backslash leq\; b\; +\; c$, then {{math|M}} is called a commutative monoid with monus

{{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–131}}{{rp|129}} and the monus $a\; \backslash mathop\; \{\backslash dot\; -\}\; b$

of any two elements $a$ and $b$ can be defined as this unique smallest element $c$ such that $a\; \backslash leq\; b\; +\; c$.

An example of a commutative monoid that is not naturally ordered is $(\backslash mathbb\{Z\},\; +,\; 0)$, the commutative monoid of the integers with usual addition, as for any $a,\; b\; \backslash in\; \backslash mathbb\{Z\}$ there exists $c$ such that $a\; +\; c\; =\; b$, so $a\; \backslash leq\; b$ holds for any $a,\; b\; \backslash in\; \backslash mathbb\{Z\}$, so $\backslash leq$ is not a partial order. There are also examples of monoids that are naturally ordered but are not semirings with monus.{{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

}}

Beyond monoids, the notion of monus can be applied to other structures. For instance, a naturally ordered semiring (sometimes called a dioid[http://marcpouly.ch/pdf/internal_100712.pdf Semirings for breakfast], slide 17) 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.

If {{math|M}} is an ideal in a Boolean algebra, then {{math|M}} is a commutative monoid with monus under $a\; +\; b\; =\; a\; \backslash vee\; b$

and $a\; \backslash mathop\; \{\backslash dot\; \{-\}\}\; b\; =\; a\; \backslash wedge\; \backslash neg\; b$

.{{rp|129}}

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,

{{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}} limited subtraction, proper subtraction, doz (difference or zero),{{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}} and monus.

{{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

}} Truncated subtraction is usually defined as

:$a\; \backslash mathop\; \{\backslash dot\; -\}\; b\; =$

\begin{cases}

0 & \mbox{if } a < b \\

a - b & \mbox{if } a \ge 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

:$a\; \backslash mathop\; \{\backslash dot\; -\}\; b\; =\; \backslash max(a\; -\; b,\; 0).$

In Peano arithmetic, truncated subtraction is defined in terms of the predecessor function {{math|P}} (the inverse of the successor function):

:$$

\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}

A definition that does not need the predecessor function is:

:$$

\begin{align}

a \mathop {\dot -} 0 &= a \\

0 \mathop {\dot -} b &= 0 \\

S(a) \mathop {\dot -} S(b) &= a \mathop {\dot -} b.

\end{align}

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

The class of all commutative monoids with monus form a variety.{{rp|129}} The equational basis for the variety of all CMMs consists of the axioms for commutative monoids, as well as the following axioms:

$\backslash 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}

Category:Algebraic structures