Peano addition commutativity proof by induction

Question

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$.

Answer 1

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$$

as was desired.