Proof of Arithmetic of Addition on the Natural Numbers

We refer to the four recursive identities of Natural Numbers by number: (i) $S(n)=n+1$, (ii) $m+S(n)=S(m+n)$, (iii) $m\cdot 1=m$, (iv) $m\cdot S(n)=m\cdot n+m$. We also use from that definition that $S(n)\ne 1$ for every $n\in\mathbb{N}$ and that $S$ is injective. Every appeal to induction below means an application of Principle of Induction for the Natural Numbers to the set of natural numbers for which the property in question holds; it therefore suffices to verify the property at $1$ and to pass from $n$ to $S(n)$.

Claim 1. The identity $a+1=S(a)$ is (i). For $1+a=S(a)$ we induct on $a$. For $a=1$ the assertion reads $1+1=S(1)$, which is (i). Assume $1+a=S(a)$. Then, by (ii) and the inductive hypothesis,

which is the assertion for $S(a)$.

Claim 2. Fix $a$ and induct on $b$. For $b=1$, by (i) applied twice,

Assume $S(a)+b=S(a+b)$. Then, using (ii), the inductive hypothesis, and (ii) again,

Claim 3. Fix $a,b$ and induct on $c$. For $c=1$, by (i), (i) and (ii),

Assume $(a+b)+c=a+(b+c)$. Then, using (ii), the inductive hypothesis, and (ii) twice,

Claim 4. Fix $a$ and induct on $b$. For $b=1$, Claim 1 gives $a+1=S(a)=1+a$. Assume $a+b=b+a$. Then, using (ii), the inductive hypothesis, and Claim 2,

Claim 5. Induct on $c$. For $c=1$: if $a+1=b+1$ then $S(a)=S(b)$ by (i), so $a=b$ because $S$ is injective. Assume the assertion for $c$, and suppose $a+S(c)=b+S(c)$. By (ii) this reads $S(a+c)=S(b+c)$, so $a+c=b+c$ by injectivity of $S$, and the inductive hypothesis gives $a=b$.

Claim 6. Let $A=\{k\in\mathbb{N}: k=1\ \text{or}\ k=S(j)\ \text{for some}\ j\in\mathbb{N}\}$. Then $1\in A$, and for $k\in A$ we have $S(k)\in A$ because $S(k)$ is the successor of $k\in\mathbb{N}$. By induction $A=\mathbb{N}$, so every $k\ne 1$ is of the form $S(j)$. Such a $j$ is unique because $S$ is injective.

Claim 7. Let $a,b\in\mathbb{N}$. If $b=1$ then $a+b=a+1=S(a)$ by (i), and $S(a)\ne 1$. Otherwise $b=S(c)$ for some $c\in\mathbb{N}$ by Claim 6, and then $a+b=a+S(c)=S(a+c)$ by (ii), which again differs from $1$. In both cases $a+b\ne 1$.

Claim 8. Fix $b$ and induct on $a$. For $a=1$ the assertion reads $1+b\ne 1$, which is Claim 7 with the summands in the order $1$ and $b$. Assume $a+b\ne a$. By Claim 2 we have $S(a)+b=S(a+b)$. If $S(a)+b=S(a)$, then $S(a+b)=S(a)$, so $a+b=a$ by injectivity of $S$, contradicting the inductive hypothesis. Hence $S(a)+b\ne S(a)$, which is the assertion for $S(a)$.