[proofplan]
We prove the algebraic laws from the recursive definitions of addition and multiplication on the positive natural numbers $\mathbb{N}=\{1,2,3,\dots\}$. First we establish the two successor identities for addition, then use induction with base case $1$ to prove associativity and commutativity of addition. Next we prove the corresponding successor identity for multiplication, and use the additive laws to prove distributivity, associativity, and commutativity of multiplication. Throughout, write $s(n):=n+1$ for the successor of $n$.
[/proofplan]
[step:Fix the recursive definitions and prove the addition successor identities]
Because $\mathbb{N}=\{1,2,3,\dots\}$, the base case $1$ and successor step give the full recursion. For each $a \in \mathbb{N}$, addition is defined recursively by
\begin{align*}
a+1=s(a)
\end{align*}
and
\begin{align*}
a+s(b)=s(a+b)
\end{align*}
for every $b \in \mathbb{N}$.
We first prove that
\begin{align*}
1+b=s(b)
\end{align*}
for every $b \in \mathbb{N}$. For $b=1$, the recursive definition gives $1+1=s(1)$. If $1+b=s(b)$, then
\begin{align*}
1+s(b)=s(1+b)=s(s(b)).
\end{align*}
Thus the identity follows by induction.
Next we prove that
\begin{align*}
s(a)+b=s(a+b)
\end{align*}
for all $a,b \in \mathbb{N}$. Fix $a \in \mathbb{N}$ and induct on $b$. For $b=1$,
\begin{align*}
s(a)+1=s(s(a))
\end{align*}
by the recursive definition, and also
\begin{align*}
s(a+1)=s(s(a)).
\end{align*}
Thus $s(a)+1=s(a+1)$. If $s(a)+b=s(a+b)$, then
\begin{align*}
s(a)+s(b)=s(s(a)+b)=s(s(a+b)).
\end{align*}
Also, since $a+s(b)=s(a+b)$,
\begin{align*}
s(a+s(b))=s(s(a+b)).
\end{align*}
Hence $s(a)+s(b)=s(a+s(b))$. Induction gives the claimed identity for every $b \in \mathbb{N}$.
[guided]
We begin by making explicit which recursive rules are being used. Since $\mathbb{N}=\{1,2,3,\dots\}$, induction starts at $1$, so a value at $1$ together with a successor rule determines the operation on every [natural number](/page/Natural%20Number). For each fixed $a \in \mathbb{N}$, the map $b \mapsto a+b$ is generated by
\begin{align*}
a+1=s(a)
\end{align*}
and
\begin{align*}
a+s(b)=s(a+b).
\end{align*}
These two formulas say how to add $1$ and how to move from adding $b$ to adding its successor.
The first useful identity is that adding to $1$ on the right-recursive side has the expected form:
\begin{align*}
1+b=s(b).
\end{align*}
For $b=1$, this is exactly $1+1=s(1)$. Suppose now that $1+b=s(b)$. Applying the recursive rule with first argument $1$ gives
\begin{align*}
1+s(b)=s(1+b).
\end{align*}
Substituting the inductive hypothesis into the right-hand side gives
\begin{align*}
1+s(b)=s(s(b)).
\end{align*}
This is precisely the desired formula with $s(b)$ in place of $b$.
The second useful identity says that successor in the first argument can be moved outside the sum:
\begin{align*}
s(a)+b=s(a+b).
\end{align*}
Fix $a \in \mathbb{N}$. For $b=1$, the recursive definition gives
\begin{align*}
s(a)+1=s(s(a)).
\end{align*}
Since $a+1=s(a)$, applying $s$ to both sides gives
\begin{align*}
s(a+1)=s(s(a)).
\end{align*}
Therefore $s(a)+1=s(a+1)$.
Assume now that $s(a)+b=s(a+b)$. Using the recursive definition first with first argument $s(a)$, and then substituting the inductive hypothesis, we get
\begin{align*}
s(a)+s(b)=s(s(a)+b)=s(s(a+b)).
\end{align*}
On the other hand, the recursive rule for $a+s(b)$ gives $a+s(b)=s(a+b)$, so applying $s$ gives
\begin{align*}
s(a+s(b))=s(s(a+b)).
\end{align*}
The two displayed equalities have the same right-hand side, hence
\begin{align*}
s(a)+s(b)=s(a+s(b)).
\end{align*}
This proves the successor step, and induction proves the identity for every $b \in \mathbb{N}$.
[/guided]
[/step]
[step:Prove associativity and commutativity of addition]
We prove associativity of addition. Fix $a,b \in \mathbb{N}$ and induct on $c$. For $c=1$,
\begin{align*}
(a+b)+1=s(a+b)=a+s(b)=a+(b+1).
\end{align*}
If $(a+b)+c=a+(b+c)$, then
\begin{align*}
(a+b)+s(c)=s((a+b)+c)=s(a+(b+c))=a+s(b+c)=a+(b+s(c)).
\end{align*}
Thus
\begin{align*}
(a+b)+c=a+(b+c)
\end{align*}
for all $a,b,c \in \mathbb{N}$.
We prove commutativity of addition. Fix $a \in \mathbb{N}$ and induct on $b$. For $b=1$, the first successor identity gives $1+a=s(a)$, while the recursive definition gives $a+1=s(a)$; hence $a+1=1+a$. If $a+b=b+a$, then
\begin{align*}
a+s(b)=s(a+b)=s(b+a)=s(b)+a.
\end{align*}
Since $s(b)=b+1$, this is $a+s(b)=s(b)+a$. Hence
\begin{align*}
a+b=b+a
\end{align*}
for all $a,b \in \mathbb{N}$.
[/step]
[step:Prove the multiplication successor identity]
Again using the convention $\mathbb{N}=\{1,2,3,\dots\}$, multiplication is fully determined by its value at $1$ and its successor rule. For each $a \in \mathbb{N}$, multiplication is defined recursively by
\begin{align*}
a1=a
\end{align*}
and
\begin{align*}
a\,s(b)=ab+a
\end{align*}
for every $b \in \mathbb{N}$.
We prove that
\begin{align*}
s(a)b=ab+b
\end{align*}
for all $a,b \in \mathbb{N}$. Fix $a \in \mathbb{N}$ and induct on $b$. For $b=1$,
\begin{align*}
s(a)1=s(a)=a+1=a1+1.
\end{align*}
If $s(a)b=ab+b$, then using the recursive definition of multiplication, associativity and commutativity of addition, and the inductive hypothesis,
\begin{align*}
s(a)s(b)=(s(a)b)+s(a)=(ab+b)+(a+1).
\end{align*}
By associativity and commutativity of addition,
\begin{align*}
(ab+b)+(a+1)=(ab+a)+(b+1).
\end{align*}
Using $s(b)=b+1$ and $a\,s(b)=ab+a$, this becomes
\begin{align*}
s(a)s(b)=a\,s(b)+s(b).
\end{align*}
Induction gives the claimed identity.
[/step]
[step:Prove distributivity of multiplication over addition]
Fix $a,b \in \mathbb{N}$ and induct on $c$. For $c=1$,
\begin{align*}
a(b+1)=a\,s(b)=ab+a=ab+a1.
\end{align*}
If $a(b+c)=ab+ac$, then by the recursive definition of addition, the recursive definition of multiplication, and associativity of addition,
\begin{align*}
a(b+s(c))=a\,s(b+c)=a(b+c)+a=(ab+ac)+a.
\end{align*}
Since $a\,s(c)=ac+a$, associativity of addition gives
\begin{align*}
(ab+ac)+a=ab+(ac+a)=ab+a\,s(c).
\end{align*}
Thus
\begin{align*}
a(b+s(c))=ab+a\,s(c).
\end{align*}
Induction proves
\begin{align*}
a(b+c)=ab+ac
\end{align*}
for all $a,b,c \in \mathbb{N}$.
[/step]
[step:Prove associativity of multiplication]
Fix $a,b \in \mathbb{N}$ and induct on $c$. For $c=1$,
\begin{align*}
(ab)1=ab=a(b1).
\end{align*}
If $(ab)c=a(bc)$, then by the recursive definition of multiplication and distributivity,
\begin{align*}
(ab)s(c)=(ab)c+ab=a(bc)+ab=a(bc+b).
\end{align*}
Since $b\,s(c)=bc+b$, this gives
\begin{align*}
(ab)s(c)=a(b\,s(c)).
\end{align*}
Induction proves
\begin{align*}
(ab)c=a(bc)
\end{align*}
for all $a,b,c \in \mathbb{N}$.
[/step]
[step:Prove commutativity of multiplication and collect the laws]
We prove first that
\begin{align*}
1b=b
\end{align*}
for every $b \in \mathbb{N}$. For $b=1$, this is $1\,1=1$. If $1b=b$, then
\begin{align*}
1s(b)=1b+1=b+1=s(b).
\end{align*}
Thus $1b=b$ by induction.
Now fix $a \in \mathbb{N}$ and induct on $b$ to prove $ab=ba$. For $b=1$,
\begin{align*}
a1=a=1a.
\end{align*}
If $ab=ba$, then
\begin{align*}
a\,s(b)=ab+a=ba+a=s(b)a,
\end{align*}
where the final equality is the multiplication successor identity with first argument $b$ and second argument $a$. Hence $a\,s(b)=s(b)a$, so induction proves
\begin{align*}
ab=ba
\end{align*}
for all $a,b \in \mathbb{N}$.
We have proved, for arbitrary $a,b,c \in \mathbb{N}$,
\begin{align*}
a+b=b+a,\qquad (a+b)+c=a+(b+c),\qquad ab=ba,\qquad (ab)c=a(bc),\qquad a(b+c)=ab+ac.
\end{align*}
This is exactly the asserted collection of arithmetic laws.
[/step]
