Tao Analysis I - 2.3.1

Thisset of of exercises is about multiplication.

Before we dive in, let's write out the minimal definitions we're given about multiplication.

Definition 2.3.1 (Multiplication of natural numbers). Let $m$ be a natural number. To multiply zero to $m$, we define $0 \times m := 0$. Now suppose inductively that we have defined how to multiply $n$ to $m$. Then we can multiply $n++$ to $m$ by defining $( n ++ ) \times m : = ( n \times m ) + m$. 

We can see this mirrors the definition for addition.

 

Exercise 2.3.1

Prove Lemma 2.3.2. (Hint: modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4)

Let's write out Lemma 2.3.2.

Lemma 2.3.2 (Multiplication is commutative). Let $n$, $m$ be natural numbers. Then $n \times m = m \times n$.

There are many parallels to the provided proof that addition is commutative, hence the suggestion to modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4. So let's develop our parallel lemmas based on those.

 

Lemma 1: For any natural number $n$, $n \times 0=0$.

Despite appearing obvious, we need to show it is true because the definition we have is $0 \times m := 0$.

We use induction. The induction hypothesis is that $n \times 0=0$.

The base case $n=0$ gives us $0 \times 0 = 0$. We can use $0 \times m := 0$ from the Definition 2.3.1 with $m=0$ to confirmt the base case is true.

Now let's consider the induction step. We want to show that $(n++) \times 0 = 0$ using the inductive hypothesis. By Definition 2.3.1 $(n++) \times 0 = (n \times 0) + 0$. Now, $(n \times 0)=0$ is the inductive hypothesis, so we have $(n++) \times 0 = 0 + 0 = 0$. So the induction step suceeds. 

Using induction, we have shown $n$, $n \times 0=0$. $\square$

Lemma 2: For any natural numbers $n$ and $m$, $n \times (m++)=(n \times m)+n$.

Despite appearing obvious, we do need to show it, because the definition only gives us $( n ++ ) \times m : = ( n \times m ) + m$.

We induct on $n$ keeping $m$ fixed. The induction hypothesis is $n \times (m++)=(n \times m)+n$.

The base case $n=0$ is $0 \times (m++)=(0 \times m)+0$. The LHS is 0 by Definition 2.3.1. The RHS also uses Definition 2.3.1 to give $(0) +0 = 0$. So the base case is true.

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

$$(n++) \times (m++)=((n++) \times m)+(n++)$$

Let's start with the LHS, and use Definition 2.3.1, and then the induction hypothesis.

$$\begin{align}(n++) \times (m++) &= (n \times m++) + (m++) \\ \\ &= (n \times m) + n + (m++) \\ \\ &= (n \times m) + (n + m)++ \end{align}$$

Now consider the RHS, and use Definition 2.3.1.

$$\begin{align}((n++) \times m)+(n++) &= (n \times m) + m + (m++) \\ \\ &= (n \times m) + (n + m)++ \end{align}$$

The LHS and RHS are equivalent.  And so the induction step succeeds.

By induction we have shown that $n \times (m++)=(n \times m)+n$. $\square$

Lemma 2.3.2

We can now finally establish Lemma 2.3.2 that $n \times m = m \times n$.

Again we use induction on $n$, keeping $m$ fixed.

The induction hypothesis is that $n \times m = m \times n$ for natural numbers $m$ and $n$.

The base case $n=0$ gives us $0 \times m = m \ times 0$. The LHS is 0 by Definition 2.3.1. The RHS is 0 by Lemma 1, proved above. Thus the base case is true.

The induction step requires us to show that

$$(n++) \times m = m \times (n++)$$

Let's consider the LHS.

By Definition 2.3.1 we have

$$(n++) \times m =(n \times m) + m$$

Let's now consider the RHS, and apply Lemma 2, proved above, and then the induction hypothesis.

$$\begin{align}m \times (n++) &= (m \times n) + m \\ \\ &= (n \times m) + m\end{align}$$

The LHS and RHS are equivalent, so the induction step succeeds.

By induction we have shown that multiplication of natural numbers is commutative, $n \times m = m \times n$. $\square$