Commutativity of Multiplication in Natural Numbers – Induction Proof

inductionnatural numbers

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?

Best Answer

This is how I would go about it, in three steps.

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

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

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