6
$\begingroup$

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$
  • $\begingroup$ Where did you see Peano (wrt Peano's Axioms of the natural numbers, of course) deals with substraction? $\endgroup$ – DonAntonio Aug 7 '13 at 8:10
  • 1
    $\begingroup$ I haven't. I guess my question should be "Is there a Peano definition of subtraction?" $\endgroup$ – David Bandel Aug 7 '13 at 8:34
7
$\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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The division algorithm I suggested doesn't work. I will try to correct it, but not today. $\endgroup$ – MJD Nov 11 '16 at 3:37
  • $\begingroup$ The division algorithm you suggested seems to work at every step except the final step where you perform 0-a=0 (truncated subtraction). As such the result will always be 1 higher than the actual quotient. Any ideas on how to fix this? $\endgroup$ – Ozaner Hansha May 24 '18 at 20:09
  • $\begingroup$ I don't see it, and the three examples I tried seem to work. Could you please give an example? $\endgroup$ – MJD May 25 '18 at 3:56
  • $\begingroup$ 5/3 = S(4)/S(2) = S((4-2)/S(2)) = S(2/S(2)) = S(S(1)/S(2)) = S(S((1-2)/S(2))) = S(S(0/S(2))) = S(S(0)) = 2 $\endgroup$ – Ozaner Hansha May 25 '18 at 13:15
  • 1
    $\begingroup$ @MJD I think $S(a) \div S(b) = S((S(a) - S(b)) \div S(b))$ is the correct formula. $\endgroup$ – corvus_192 Jul 13 '18 at 12:28
0
$\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.

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm not sure I understand how S(a) - b = S(a - b) works. Example: 4 - 1 becomes S(3) - 1 = S(4 - 1), which doesn't seem to take us anywhere. Whereas, using my definition 4 - 1 becomes S(4 - S(1)) = S(4 - 2), which eventually will recurse down to S(S(S(0))) which evaluates to 3. I may be misunderstanding what you mean by "constructive." $\endgroup$ – David Bandel Aug 7 '13 at 8:32
  • $\begingroup$ 4 - 1 becomes S(3) - 1 = S(3 - 1), so now you have to compute 3 - 1 instead of 4 - 1. Then you work your way down to S(S(S(1-1) = 3 $\endgroup$ – Greebo Aug 7 '13 at 8:51
  • $\begingroup$ I see. But how is this any better or more "constructive" than my formulation? $\endgroup$ – David Bandel Aug 7 '13 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.