Monus

Short description: 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 [math]\displaystyle{ \mathop {\dot -} }[/math] symbol to distinguish it from the standard subtraction operator.

## Contents

* 1 Notation
* 2 Definition
* 3 Other structures
* 4 Examples
* 4.1 Natural numbers
* 5 Properties
* 6 Notes

## Notation

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

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

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

## Other structures

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

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

### Natural numbers

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]

[math]\displaystyle{ a \mathop {\dot -} b = \begin{cases} 0 & \mbox{if } a \lt b \\\ a - b & \mbox{if } a \ge b, \end{cases} }[/math]

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]

[math]\displaystyle{ a \mathop {\dot -} b = \max(a - b, 0). }[/math]

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

[math]\displaystyle{ \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]\displaystyle{ \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 functions, which are not defined over negative numbers.[7] Truncated subtraction is also used in the definition of the multiset difference operator.

## Properties

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:

[math]\displaystyle{ \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

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 [math]\displaystyle{ c }[/math] to be the neutral element of the monoid
3. ↑ if [math]\displaystyle{ a \leq b }[/math] with witness [math]\displaystyle{ d }[/math] and [math]\displaystyle{ b \leq c }[/math] with witness [math]\displaystyle{ d' }[/math] then [math]\displaystyle{ d + d' }[/math] witnesses that [math]\displaystyle{ a \leq c }[/math]
4. ↑ 4.0 4.1 4.2 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. https://math.stackexchange.com/q/1968090. Retrieved 2016-10-14.
6. ↑ Semirings for breakfast, slide 17
7. ↑ 7.0 7.1 7.2 7.3 Vereschchagin, Nikolai K.; Shen, Alexander (2003). Computable Functions. American Mathematical Society. pp. 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. ↑ 9.0 9.1 Jacobs, Bart (1996). "Coalgebraic Specifications and Models of Deterministic Hybrid Systems". in Wirsing, Martin. Algebraic Methodology and Software Technology. Lecture Notes in Computer Science. 1101. Springer. pp. 522. ISBN 3-540-61463-X. https://www.cs.ru.nl/B.Jacobs/PAPERS/AMAST96.ps.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Monus. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Monus&oldid=3431421"