Prove Lemma 2.3.3.
Lemma 2.3.3 (positive natural numbers have no zero divisors):
Let $n$, $m$ be natural numbers. Then $n\times m=0$ if and only if at least one of $n$, $m$ is equal to zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive.
We need to prove both implications:
- if $n\times m=0$ then at least one of $n,m$ is zero
- if at least one of $n,m$ is zero then $n\times m=0$
$(\implies)$
We will prove the logically equivalent contrapositive ``if $n$ and $m$ are both positive, then $nm$ is also positive''.
Since $n$ is positive, by Lemma 2.2.10 there exists a unique natural number $x$ such at that $x++=n$. And so $nm=(x++)\times m$. By Definition 2.3.1 (multiplication of natural numbers) this is $nm=(x\times m)+m$. By Proposition 2.2.8, since $m$ is a positive number, then the sum $nm=(x\times m)+m$ is also positive.
By proving the contrapositive, we have proven the implication that if $n\times m=0$ then at least one of $n,m$ is zero.
$(\impliedby)$
There are two cases to consider, $n=0$ and $m=0$. In the first case $n=0$, Definition 2.3.1 immediately gives us $0\times m=0$. In the second case $m=0$, by Lemma 2.3.2 (multiplication is commutative) and Definition 2.3.1 we have $n\times0=0\times n=0$.
In both cases $nm=0$, proving the implication that if at least one of $n,m$ is zero then $n\times m=0$.
By showing both implications, we have proved that $n\times m=0$ if and only if at least one of $n, m$ is equal to zero, for natural numbers $m, n$.
