Tao Analysis I - 2.3.2

Exercise 2.3.2

Prove Lemma 2.3.3. (Hint: prove the second statement first.)

Let's write down 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.

It is worth recalling the definition of a positive number.

Definition 2.2.7 (Positive natural numbers). A natural number $n$ is positive
iff it is not equal to 0.

 

Let's take the hint and prove the second statement first. Let's do it by inducting on $n$ and fixing $m$.

Inductive hypothesis: $(n > 0) \land (m > 0) \implies (nm > 0)$

Base case: $n=0$ give us

$$(0 > 0) \land (m > 0) \implies (0 \times m > 0)$$

This simplifies to $\text{false} \implies \text{false}$, which is true, and so the base case is true.

Although not necessary, it is insightful to see what happens with $n=1$. This gives us

$$(1 > 0) \land (m > 0) \implies (1 \times m > 0)$$

This simplifies to $(m > 0) \implies (m > 0)$, which is also true.

Now let's turn to the induction step. We need to show that

$$((n++) > 0) \land (m > 0) \implies ((n++)\times m > 0)$$

Now, we know that if $n>0$ then $n++ > 0$, because by definition $n = 0 + d$ and  so $n++ = 0 + (d++)$ where $d \neq 0$. 

This gives us

$$(m > 0) \implies ((n++)\times m > 0)$$

Let's focus on $(n++) \times m$. By Definition 2.3.1 this is $nm + m$. And so if $nm > 0$, then $(n++) \times m = nm + m > 0$, because $m>0$ by inductive hypothesis.

So finally $((n++) > 0) \land (m > 0) \implies ((n++)\times m > 0)$ reduces to $\text{true} \implies \text{true}$, which is true, and so the inductive step succeeds.

 By induction, we have shown  $(n > 0) \land (m > 0) \implies (nm > 0)$. $\square$

Now we need to prove the first statement in Lemma 2.3.3, which is

$$(n \times m = 0) \iff (n=0) \lor (m=0)$$

We need to prove this in both directions.

Let's consider left to right, $(n \times m = 0) \implies (n=0) \lor (m=0)$. The contrapositive which is equivalent to the original statement.

$$\neg ( (n=0) \lor (m=0)) \implies \neg (n \times m = 0)$$

This simplifies to

$$ (n >0) \land (m > 0) \implies (n \times m > 0)$$

This is precisely what we have just proved above.

Let's consider right to left.

$$(n=0) \lor (m=0) \implies(n \times m = 0)$$

This covers three cases:

• $n=0$ which gives $0 \times m$ which by Definition 2.3.1 is 0.
• $m=0$ which gives $n \times 0$ which by commutativity of multiplication (Lemma 2.3.2) is also 0.
• $n=m=0$ which is covered by the $n=0$ case.

By proving both directions, we have shown $(n \times m = 0) \iff (n=0) \lor (m=0)$. $\square$