Monus

Definition

Let ( M , + , 0 ) be a commutative monoid. Define a binary relation ≤ on this monoid as follows: for any two elements a . and b , we set a ≤ b if and only if there exists another element c such that a + c = b . It is easy to check that ≤ is reflexive (taking c to be the neutral element of the monoid) and that it is transitive (if a ≤ b with witness c and b ≤ c with witness c ′ then c + c ′ witnesses that a ≤ c ). We call M naturally ordered if the ≤ relation is additionally antisymmetric, so that ≤ is a partial order. Further, if for each pair of elements a and b , there exists a unique smallest element c such that a ≤ b + c , then we call M a commutative monoid with monus and we can then define the monus a ∸ b of any two elements a and b as this unique smallest element c such that a ≤ b + c .

An example of a commutative monoid which is not naturally ordered is ( Z , + , 0 ) , the commutative monoid of the integers with usual addition, as for any a , b ∈ Z there exists c such that a + c = b , so we have a ≤ b for any a , b ∈ Z , so ≤ is not a partial order. There are also examples of monoids which are naturally ordered but are not semirings with monus.

Other structures

Beyond monoids, the notion of monus can be applied to other structures. For instance, a naturally ordered semiring (sometimes called a dioid) 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 and a ∸ b = a ∧ ¬b.

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 variant of standard subtraction, variously referred to as truncated subtraction, limited subtraction, proper subtraction, and monus. Truncated subtraction is usually defined as

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

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

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.

Properties

The class of all commutative monoids with monus form a variety. 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.