I came up with this:
(S.1) $a - a = 0$
(S.2) $a - b = S(a - S(b))$
This seems to work. At least for $a$$\ge$$b$.
Is this the correct or most efficient formulation?
Also, does there happen to be one for division? Of course I would imagine that that division would only work for $a/b$, where $a$ is a multiple of $b$.
What I've come up for this one is:
(D.1) $0 / a = 0$
(D.2) $a / b = 1 + (a - b)/b$
$\endgroup$ 23 Answers
$\begingroup$From an implementation point of view, your definition is inefficient, because at each step you have to to decide whether to apply the $a-a = 0$ rule, which requires that you check to see if the two arguments of $-$ are equal, and this will take a long time if the arguments are large.
A more efficient implementation is:
$$\begin{array}{rll} a&-0 &= a \\ 0&-S(b) &= 0 \qquad\text{(or leave this undefined)}\\ S(a)&-S(b) & = a-b \end{array}$$
Here you can decide in constant time which of the three cases applies: is the second argument zero? If so apply the first rule, if not, is the first argument zero? If it is apply the second rule; if not apply the third rule.
Leave the middle case undefined if you want ordinary subtraction, but defined as 0 if you want so-called "truncated subtraction" in which $a-b = 0$ when $a<b$.
For division, you are better off splitting it into integer operations. For every $a$ and $b$ there is an integer quotient $q$ and an integer remainder $r$ such that $$a = qb+r$$ and $0\le r < b$; if $r = 0$ then $b$ divides $a$ exactly and $q = a\div b$. Calculating the integer quotient and remainder in Peano arithmetic isn't hard. The quotient is:
$$\begin{array}{rll} 0&\div S(b) &= 0 \\ S(a)&\div S(b) &= S((a∸ b)\div S(b)) \end{array}$$
Where ∸ denotes truncated subtraction. Then the remainder is just $a - b\cdot(a\div b)$.
$\endgroup$ 7 $\begingroup$Your definition would work, and as Peano only defines the natural numbers, you would only need subtraction when $a \geq b$. Normally the Peano axioms do not define subtraction, but subtraction is just defined as the inverse of addition, i.e. $a - b = a + (-b)$, where $-b$ is the number defined by $b + (-b) = 0$. For this to work you need the whole $\mathbb{Z}$ to work with though.
$\endgroup$ $\begingroup$If all you want is a definition, the simplest one should be: $$a-b = c \iff a = b+c$$
If you want a constructive formula, you want the $S$ on the left. I'd suggest:
- $a-a = 0$ (same as your S.1)
- $S(a) - b = S(a-b)$
This of course only works if $a\ge b$, but if $a<b$, the difference is not defined in the natural numbers.
$\endgroup$ 3
