Exercise 2.3.2 (Positive natural numbers have no zero divisors)

Hints. You can use induction, but you don’t need to use induction.

How to think about the exercise. We want to show

This is equivalent to showing two things:

and

The first of these is equivalent to

since it is the contrapositive. But "not equal to zero" is the same thing as "positive", so this last implication means exactly the same thing as what Tao wrote in the statement of the lemma: "In particular, if $n$ and $m$ are both positive, then $\mathit{nm}$ is also positive."

In the proof below, we will first show

and then we will show

And actually, in the proof below, the two parts are completely independent, i.e. it doesn’t matter what order you do them in. So then why does Tao’s hint say to prove the second one (i.e. the starred implication) first? I think Tao’s thinking was something like this: at this stage, it might be difficult to manipulate implications like I did above, and to realize that proving the contrapositive is equivalent to proving the original implication. So instead, if you prove the contrapositive version (as stated by Tao), then you can very easily prove the original implication using a proof by contradiction. In other words, you could say: "Suppose $n\times m=0$. Now suppose for a contradiction that neither $n$ nor $m$ is zero. Then we see that $\mathit{nm}$ is positive, a contradiction." I think that is what Tao intended.

Model solution. Suppose $n$ and $m$ are positive. By Lemma 2.2.10, there exist natural numbers $a,b$ such that $a++=n$ and $b++=m$. Thus $n\times m=(a++)\times (b++)=\mathit{ab}+a+b+1$ which is positive. (For suppose $(\mathit{ab}+a+b)+1$ is not positive. Then by Corollary 2.2.9 we see that $1=0$, a contradiction.)

Now suppose $n=0$ or $m=0$. If $n=0$, then $\mathit{nm}=0\times m=0$ by definition of multiplication. If $m=0$, then $\mathit{nm}=\mathit{mn}=0\times n=0$ by commutativity of multiplication and the definition of multiplication.

Source: Issa Rice’s blog.

We first prove the second statement. Since $n$ and $m$ are positive, by Lemma 2.2.10, both of these numbers have predecessors:

Then, we get:

Thus, by Axiom 2.3 we get that $nm\ne 0,$ and thus, $nm$ is positive.
We now prove that $n\times m=0$ if and only if at least one of $n,m$ is equal to zero.

$⟹$

Assume for the sake of contradiction that the statement "if $n\times m=0$, at least one of $n,m$ is equal to zero" is false. Thus, we have to prove that: $$nm=0\wedge (n\ne 0\wedge m\ne 0).$$

But since $n\ne 0,m\ne 0$, $nm$ is positive (from the proof above). Thus, we get an contradiction.

$⟸$

We now prove that "if at least one of $n,m$ is equal to zero, $n\times m=0$." We have 2 cases:

• $n=0.$ Then, we get that $nm=0\times m=0$ by definition.

• $m=0.$ Then, we have $nm=n\times 0=0\times n=0$ by definition and commutativity law.