Commutativity of multiplication in $\mathbb{N}$ I'm trying to prove that $a\cdot b=b\cdot a$ when $a$ and $b$ are two natural numbers.
In the rest of this question I'm using $a'$ for the successor of $a$.
Addition is defined as:


*

*$a+0=a$

*$a+b'=(a+b)'$


Multiplication is defined as:


*

*$a\cdot 0=0$

*$a\cdot b'=a+ab$


I already proved commutativity and associativity for addition. I also proved that $a\cdot 1=1\cdot a=a$.
I tried with induction on $b$. I can easily show that $a\cdot 0=0\cdot a$. Then I suppose $a\cdot b=b\cdot a$ and try to show that $a\cdot b'=b'\cdot a$.
Here I can no longer go on. The main problem is I can't use distributivity laws since I haven't proved them yet. I hope to do that immediately after this problem is fixed. Also, $b'\cdot a$ is problematic because $b'$ is at the left.
Any hints?
 A: Assume commutativity of the products $ab$, $ab'$ and $a'b$. Then you can rewrite $b'a'$ and $a'b'$ in terms of $a$, $b$ and $ab$ using commutativity and associativity of addition and the induction hypothesis to show that they are equal. I'll be happy to provide more details, but you asked for hints.
A: This is how I would go about it, in three steps.


*

*Prove $0=m\cdot 0=0\cdot m$ for all $m\in\omega$. As you said, you can easily show this.

*Prove $m'n=mn+n$ for all $m,n\in\omega$.
We can do this by induction. Let
$$
K=\{n\in\omega\ |\ m'n=mn+n\}
$$
By definition, $m'\cdot 0=0$, and $m\cdot 0+0=0+0=0$, so $0\in K$. Suppose $n\in K$. Then
$$
m'n'=m'+m'n=m'+mn+n=m+mn+n'=mn'+n'
$$
where I have used the second facts you listed for addition and multiplication, and I assume you know $a'+b=(a+b)'=a+b'$, which is usually used in proving the commutativity of addition. So $n'\in K$. 

*We can now prove $mn=nm$ for all $m,n\in\omega$.
Let $S=\{m\in\omega\ |\forall_{n\in\omega}\ mn=nm\}$. By Step 1, $0\in S$. Let $m\in S$. Then 
$$
m'n=mn+n=nm+n=n+nm=nm'
$$
so $m'\in S$, so $S$ is inductive, and $S=\omega$.
A: Have you tried proving either associativity or the existence of an identity for multiplication?
(Identity:  Define 1 = 0'.  Show that 1⋅a = a⋅1 for all a)
I don't see the answer right now, but my guess is that you may need one of these before you can prove commutativity.
