Addition(+) is defined using the successor function(++) in Peano arithmetic as:

  1. 0 + m = m
  2. (n++) + m = (n + m)++

While these are intuitive axioms that are consistent with my previous, elementary, understanding of addition, I don't understand how it follows from these axioms that n + m is the same thing as incrementing m n times.

Although I can see that it is true for specific cases:

  1. 1 + m = (0++) + m = (0 + m)++ = m++
  2. 2 + m = (1++) + m = (1 + m)++ = (m++)++
  3. etc.

Thanks very much.

  • 2
    $\begingroup$ You continue the pattern and prove with induction. $\endgroup$ – Gareth Ma Apr 3 at 15:53
  • 1
    $\begingroup$ I think I would have defined it as $m+0=m$ and $m+(n++)=(m+n)++$. $\endgroup$ – Angina Seng Apr 3 at 16:02
  • $\begingroup$ @AnginaSeng Isn't that equivalent to "0 + m = 0" and "(n++) + m = (n + m)++"? i.e. You could just do induction to get the other. $\endgroup$ – Haziq Muhammad Apr 3 at 16:44

We can prove it by induction on $m$. If $m=0$, $n+m=n+0=n$ is the result of not incrementing $n$ at all, i.e. doing it $0$ times. Suppose $n+k$ is the result of $k$ increments starting from $n$. For the inductive step, associativity of $+$ gives $n+(k+1)=(n+k)+1$, i.e. we increment $k$ times, then once more.

| cite | improve this answer | |
  • $\begingroup$ Thanks, that makes a lot of sense. But I was a bit unsure about doing induction like that because I didn't know how I would define "k increments." $\endgroup$ – Haziq Muhammad Apr 3 at 16:30
  • 1
    $\begingroup$ @HaziqMuhammad You would define it recursively: $0$ increments leaves $n$ unchanged, $1$ changes it to $n$'s successor $n+1$, & $k+1$ increments applies $k$ then $1$. $\endgroup$ – J.G. Apr 3 at 16:32
  • $\begingroup$ Thanks again. It's nice to know that I won't have to go through Peano's axioms every time I want to add two numbers. $\endgroup$ – Haziq Muhammad Apr 3 at 16:46
  • 1
    $\begingroup$ @HaziqMuhammad Ditto with multiplication, for which Presburger arithmetic is at a distinct disadvantage. $\endgroup$ – J.G. Apr 3 at 16:58

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.