∸

☆ Save On Wikipedia ↗

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 minus sign, " − {\displaystyle -} {\displaystyle -}", because the natural numbers are a CMM under subtraction. It is also denoted with a dotted minus sign, " − ˙ {\displaystyle \mathbin {\dot {-}} } {\displaystyle \mathbin {\dot {-}} }", 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
− ˙ {\displaystyle \mathbin {\dot {-}} } {\displaystyle \mathbin {\dot {-}} } DOT MINUS U+2238 ∸ \dot -
− MINUS SIGN U+2212 − − -

A use of the monus symbol is seen in Dennis Ritchie's PhD Thesis from 1968.[2]

Definition

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

An example of a commutative monoid that is not naturally ordered is ( Z , + , 0 ) {\displaystyle (\mathbb {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} } {\displaystyle a,b\in \mathbb {Z} } there exists c {\displaystyle c} {\displaystyle c} such that a + c = b {\displaystyle a+c=b} {\displaystyle a+c=b}, so a ≤ b {\displaystyle a\leq b} {\displaystyle a\leq b} holds for any a , b ∈ Z {\displaystyle a,b\in \mathbb {Z} } {\displaystyle a,b\in \mathbb {Z} }, so ≤ {\displaystyle \leq } {\displaystyle \leq } is not antisymmetric and therefore not a partial order. There are also examples of monoids that are naturally ordered but are not semirings with monus.[6]

Other structures

Beyond monoids, the notion of monus can be applied to other structures. For instance, a naturally ordered semiring (sometimes called a dioid[7]) 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 ∨ b {\displaystyle a+b=a\vee b} {\displaystyle a+b=a\vee b} and a − ˙ b = a ∧ ¬ b {\displaystyle a\mathbin {\dot {-}} b=a\wedge \neg b} {\displaystyle a\mathbin {\dot {-}} b=a\wedge \neg b}.[5]

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,[8] limited subtraction, proper subtraction, doz (difference or zero),[9] and monus.[10] Truncated subtraction is usually defined as[8]

a − ˙ b = { 0 if  a < b a − b if  a ≥ b , {\displaystyle a\mathbin {\dot {-}} b={\begin{cases}0&{\mbox{if }}a<b\\a-b&{\mbox{if }}a\geq b,\end{cases}}} {\displaystyle a\mathbin {\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 {\displaystyle 5-3=2} {\displaystyle 5-3=2} and 3 − 5 = − 2 {\displaystyle 3-5=-2} {\displaystyle 3-5=-2} in regular subtraction, whereas in truncated subtraction 3 − ˙ 5 = 0 {\displaystyle 3\mathbin {\dot {-}} 5=0} {\displaystyle 3\mathbin {\dot {-}} 5=0}. Truncated subtraction may also be defined as[10]

a − ˙ b = max ( a − b , 0 ) . {\displaystyle a\mathbin {\dot {-}} b=\max(a-b,0).} {\displaystyle a\mathbin {\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):[8]

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\mathbin {\dot {-}} 0&=a\\a\mathbin {\dot {-}} S(b)&=P(a\mathbin {\dot {-}} b).\end{aligned}}} {\displaystyle {\begin{aligned}P(0)&=0\\P(S(a))&=a\\a\mathbin {\dot {-}} 0&=a\\a\mathbin {\dot {-}} S(b)&=P(a\mathbin {\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\mathbin {\dot {-}} 0&=a\\0\mathbin {\dot {-}} b&=0\\S(a)\mathbin {\dot {-}} S(b)&=a\mathbin {\dot {-}} b.\end{aligned}}} {\displaystyle {\begin{aligned}a\mathbin {\dot {-}} 0&=a\\0\mathbin {\dot {-}} b&=0\\S(a)\mathbin {\dot {-}} S(b)&=a\mathbin {\dot {-}} b.\end{aligned}}}

Truncated subtraction is useful in contexts such as primitive recursive functions, which are not defined over negative numbers.[8] 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.[5] 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\mathbin {\dot {-}} a)&=b+(a\mathbin {\dot {-}} b),\\(a\mathbin {\dot {-}} b)\mathbin {\dot {-}} c&=a\mathbin {\dot {-}} (b+c),\\(a\mathbin {\dot {-}} a)&=0,\\(0\mathbin {\dot {-}} a)&=0.\\\end{aligned}}} {\displaystyle {\begin{aligned}a+(b\mathbin {\dot {-}} a)&=b+(a\mathbin {\dot {-}} b),\\(a\mathbin {\dot {-}} b)\mathbin {\dot {-}} c&=a\mathbin {\dot {-}} (b+c),\\(a\mathbin {\dot {-}} a)&=0,\\(0\mathbin {\dot {-}} a)&=0.\\\end{aligned}}}

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. Brailsford, Kernighan & Ritchie 2022.
  3. taking c {\displaystyle c} {\displaystyle c} to be the neutral element of the monoid
  4. if a ≤ b {\displaystyle a\leq b} {\displaystyle a\leq b} with witness d {\displaystyle d} {\displaystyle d} and b ≤ c {\displaystyle b\leq c} {\displaystyle b\leq c} with witness d ′ {\displaystyle d'} {\displaystyle d'} then d + d ′ {\displaystyle d+d'} {\displaystyle d+d'} witnesses that a ≤ c {\displaystyle a\leq c} {\displaystyle a\leq c}
  5. Amer 1984, p. 129.
  6. Monet 2016.
  7. Pouly 2010, p. 22, slide 17.
  8. Vereschchagin & Shen 2003.
  9. Warren Jr. 2013.
  10. Jacobs 1996.

References

  • Amer, K. (1984), "Equationally complete classes of commutative monoids with monus", Algebra Universalis, 18: 129–131, doi:10.1007/BF01182254