Proving $mn=nm$ for all $n,m\in \mathbb N$

Question

How can I prove that $mn=nm ,\forall m,n \in \mathbb N$, by using just the following axioms?

1. $(\forall n \in \mathbb N)(n\cdot 0=0)$

2. $(\forall m,n \in \mathbb N)(m(n+1)=mn+m)$,

3. The axioms and properties of addition.

Answer 1

You need induction (over $m$).

First prove that for $m=0$, then $0\cdot n=n\cdot 0$ and that is the first part of the induction. You already know by axiom that $n\cdot 0=0$, so you must prove that $0n=0$ (which can be prove by induction over $n$).

Now you assume by induction hypothesis that for $m=k$ and any $n$ is true that $kn=nk$, then prove that for $m=k+1$ then $(k+1)n=n(k+1)$, which requires induction over $n$.

For $n=0$ it is already solved, so we assume that for $n=i$ it is true that $ki=ik$ implies $(k+1)i=i(k+1)$, we must then prove that $k(i+1)=(i+1)k$ implies $(k+1)(i+1)=(i+1)(k+1)$. \begin{align} (k+1)(i+1) &= (k+1)i+(k+1)&\text{by axiom 2}\\ &= i(k+1)+(k+1)&\text{by induction over $n$}\\ &=(ik+i)+(k+1)&\text{by axiom 2}\\ &=(ik+k)+(i+1)&\text{by properties of addition}\\ &=(ki+k)+(i+1)&\text{by induction hypothesis}\\ &=k(i+1)+(i+1)&\text{by axiom 2}\\ &=(i+1)k+(i+1)&\text{by induction hyp. over $m$}\\ &=(i+1)(k+1)&\text{by axiom 2} \end{align} The justification of the second step is a little fuzzy, but this is the idea.

Answer 2

Claim 1: $0 \cdot n = 0$ for every natural number.

Proof: We induct on n. The base case is $0 \cdot 0 = 0$ but that follows immediately by definition of product, since $m \cdot 0 = 0$ for every $m$ in particular when $m=0$. Now suppose inductively that the claim holds for n. We have to show that also holds for $n+1$.

$0 \cdot (n+1) = 0 \cdot n + 0$. But by hypothesis we know that $0 \cdot n = 0$, so $ 0 \cdot n + 0 = 0 +0 = 0$, which close the induction.

Claim 2: $(m+1) \cdot n = m \cdot n+n$ for every natural number.

Proof: We induct on $n$. When $n=0$ then we have $(m+1) \cdot 0 = 0$ and $m \cdot 0+0 = 0$. Assume that the claim holds for $n$ in other words assume that $(m+1) \cdot n = m \cdot n+n$ we wish to show that also holds for $n+1$.

$(m+1) \cdot (n+1) = (m+1) \cdot n + (m+1)$ and by the inductive hypothesis we know that $(m+1) \cdot n = m \cdot n+n $. Thus we have:

$(m+1) \cdot n + (m+1) = (m \cdot n+n )+ m +1= m \cdot (n+1) +(n+1)$ as desired.

Proposition: $m \cdot n = n\cdot m$ for each natural number.

Proof: We induct on n. When $n =0$ by definition we know that $m \cdot 0 =0$ and by the claim 1 it follows that $0\cdot m = 0$ which prove the base case.

Now suppose the claim holds for $n$ and we shall show that also holds for $n+1$.

$m \cdot (n+1) = m \cdot n + m$ by definition of product and $(n+1)\cdot m = n \cdot m +m$ by the claim 2. Furthermore, by the inductive hypothesis we know that $ m \cdot n = n \cdot m$. Thus $m \cdot (n+1) = (n+1)\cdot m$ which close the induction.