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)\wedge (m>0)⟹(nm>0)$

Base case: $n=0$ give us

$$(0>0)\wedge (m>0)⟹(0\times m>0)$$

This simplifies to $\text{false}⟹\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)\wedge (m>0)⟹(1\times m>0)$$

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

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

$$((n++)>0)\wedge (m>0)⟹((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\ne 0$. 

This gives us

$$(m>0)⟹((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)\wedge (m>0)⟹((n++)\times m>0)$ reduces to $\text{true}⟹\text{true}$, which is true, and so the inductive step succeeds.

 By induction, we have shown  $(n>0)\wedge (m>0)⟹(nm>0)$. $◻$

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

$$(n\times m=0)⟺(n=0)\vee (m=0)$$

We need to prove this in both directions.

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

$$\mathrm{\neg }((n=0)\vee (m=0))⟹\mathrm{\neg }(n\times m=0)$$

This simplifies to

$$(n>0)\wedge (m>0)⟹(n\times m>0)$$

This is precisely what we have just proved above.

Let's consider right to left.

$$(n=0)\vee (m=0)⟹(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)⟺(n=0)\vee (m=0)$. $◻$