# Peano addition commutativity proof by induction

I hope you are already familiar with the five Peano axioms, from which point we use the standard numerals $$0,1,2,3,\dots$$ as some shorthand notation for each element of our set $$\mathbb{N}$$. The successor function from axiom #2, $$S$$, simply adds $$1$$ in the familiar fashion e.g. $$S(2)=3$$.

From this we can define addition by the following rules: \begin{align} \\\text{For all } x,y\in\mathbb{N}, \\ \\x\oplus0&=x \\x\oplus S(y)&=S(x\oplus y) \end{align} I’m not using the standard addition sign because we do not yet know if it is both associative and commutative.

I can prove associativity by induction. Suppose there is some $$k$$ where $$(a\oplus b)\oplus k = a\oplus (b\oplus k)$$ for all $$a,b\in\mathbb{N}$$. Now we need to see that $$(a\oplus b)\oplus S(k)=a\oplus\big(b\oplus S(k)\big)$$:

\begin{align} \\(a\oplus b)\oplus S(k)&=S\big((a\oplus b)\oplus k\big) \\&=S\big(a\oplus(b\oplus k)\big) \\&=a\oplus S(b\oplus k) \\&=a\oplus\big(b\oplus S(k)\big) \end{align}

Then we finish with the base case: \begin{align} \\(a\oplus b)\oplus0&=a\oplus b \\&=a\oplus(b\oplus0) \end{align} Proving commutativity comes in two parts.

Firstly, we prove that every element of $$\mathbb{N}$$ is commutable with $$0$$. Suppose there is some $$k$$ where $$k\oplus0=0\oplus k$$. To prove that $$S(k)\oplus0=0\oplus S(k)$$: \begin{align} \\S(k)\oplus0&=S(k) \\&=S(k\oplus0) \\&=S(0\oplus k) \\&=0\oplus S(k) \end{align} (No base case required since it’s obvious $$0\oplus0=0\oplus0$$.)

This is where I need your help. Given some $$k$$ where $$k\oplus a=a\oplus k$$ for all $$a\in\mathbb{N}$$, how do I show that $$S(k)\oplus a=a\oplus S(k)$$?

Note: It is alright to explicitly say $$S(0)=1$$, $$S(1)=2$$, etc. in your proof. Again, base case is trivial since we already proved every element of $$\mathbb{N}$$ is commutable with $$0$$.

Intuitively, the argument you would like to make is: $$(k+1) + a = k+(1+a) = k+(a+1) = (k+a)+1 = (a+k)+1 = a+(k+1)$$
The only step that needs to be fixed is the commutativity of addition with $$1$$. We proceed by induction to show that $$S(0)$$ commutes with every natural number $$a$$. Indeed, $$S(0)$$ commutes with $$0$$. Now, suppose that it commutes with some arbitrary natural number $$a$$. Then: $$S(0) \oplus S(a) = S(S(0) \oplus a) = S(a \oplus S(0)) = S(S(a \oplus 0)) = S(S(a)) = S(S(a) \oplus 0) = S(a) \oplus S(0)$$
Hence, it follows that: $$a \oplus S(k) = S(a \oplus k) = S(k \oplus a) = k \oplus S(a) = k \oplus S(a \oplus 0) = k \oplus (a \oplus S(0)) = k \oplus (S(0) \oplus a) = (k \oplus S(0)) \oplus a = S(k \oplus 0) \oplus a = S(k) \oplus a$$
• Is there a way to do it while having only proven commutativity with $0$ and not $1$? Aug 21, 2022 at 14:48
• Hmm I'm somewhat doubtful. The thing is, $1$ makes a very natural appearance in the inductive step and its behavior with respect to addition hasn't been determined if you just start with commutativity with $0$. I'll think about this a bit more. Aug 21, 2022 at 14:51