Monus

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 $\mathop {\dot {-}}$ symbol to distinguish it from the standard subtraction operator.

Notation

glyph	Unicode name	Unicode code point^[1]	HTML character entity reference	HTML/XML numeric character references	TeX
∸	DOT MINUS	U+2238		`∸`	`\dot -`
−	MINUS SIGN	U+2212	`−`	`−`	`-`

Definition

Let $(M,+,0)$ be a commutative monoid. Define a binary relation $\leq$ on this monoid as follows: for any two elements $a$ and $b$ , define $a\leq b$ if there exists an element $c$ such that $a+c=b$ . It is easy to check that $\leq$ is reflexive^[2] and that it is transitive.^[3] $M$ is called naturally ordered if the $\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\leq b+c$ , then $M$ is called a commutative monoid with monus^[4]^: 129 and the monus $a\mathop {\dot {-}} b$ of any two elements $a$ and $b$ can be defined as this unique smallest element $c$ such that $a\leq b+c$ .

An example of a commutative monoid that is not naturally ordered is $(\mathbb {Z} ,+,0)$ , the commutative monoid of the integers with usual addition, as for any $a,b\in \mathbb {Z}$ there exists $c$ such that $a+c=b$ , so $a\leq b$ holds for any $a,b\in \mathbb {Z}$ , so $\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

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 $a+b=a\vee b$ and $a\mathop {\dot {-}} b=a\wedge \neg b$ .^[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]

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

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

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

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:

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

↑ Characters in Unicode are referenced in prose via the "U+" notation. The hexadecimal number after the "U+" is the character's Unicode code point.
↑ taking $c$ to be the neutral element of the monoid
↑ if $a\leq b$ with witness $d$ and $b\leq c$ with witness $d'$ then $d+d'$ witnesses that $a\leq c$
1 2 3 Amer, K. (1984), "Equationally complete classes of commutative monoids with monus", Algebra Universalis, 18: 129–131, doi:10.1007/BF01182254
↑ M.Monet (2016-10-14). "Example of a naturally ordered semiring which is not an m-semiring". Mathematics Stack Exchange. Retrieved 2016-10-14.
↑ Semirings for breakfast, slide 17
1 2 3 4 Vereschchagin, Nikolai K.; Shen, Alexander (2003). Computable Functions. Translated by V. N. Dubrovskii. American Mathematical Society. p. 141. ISBN 0-8218-2732-4.
↑ Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
1 2 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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$ to be the neutral element of the monoid

[3] $a\leq b$ with witness $d$ and $b\leq c$ with witness $d'$ then $d+d'$ witnesses that $a\leq c$

[Amer-4] 1 2 3 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

[Computable_Functions-7] 1 2 3 4 Vereschchagin, Nikolai K.; Shen, Alexander (2003). Computable Functions. Translated by V. N. Dubrovskii. American Mathematical Society. p. 141. ISBN 0-8218-2732-4.

[Warren_2013-8] Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

[Wirsing-9] 1 2 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]