Tao Analysis I - 2.3.3

Exercise 2.3.3

Prove Proposition 2.3.5. (Hint: modify the proof of Proposition 2.2.5 and use the
distributive law.)

Let's write down Proposition 2.3.5.

Proposition 2.3.5 (Multiplication is associative). For any natural numbers $a$, $b$, $c$, we have $(a \times b) \times c = a \times (b \times c)$.

The question hints that we should modify the proof of Proposition 2.2.5 regarding the associatibity of addition.

Let's use induction on $a$. The proposal $P(a)$ says that $(a \times b) \times c = a \times (b \times c)$

The induction hypothesis is that $P(a)$ is true. That is

$$(a \times b) \times c = a \times (b \times c)$$

The base case $P(0)$ is

$$(0 \times b) \times c = 0 \times (b \times c)$$

We can use Definition 2.3.1, $0 \times m:= 0$, to simplify

$$(0) \times c = 0 \times (b \times c)$$

This simplifies again to $0 = 0$ which is true. So the base case $P(0)$ is true.

The inductive step requires us to show $P(a++)$ is true. That is

$$((a++) \times b) \times c = (a++) \times (b \times c)$$

Let's consider the LHS and use Definition 2.3.1, $( n ++ ) \times m : = ( n \times m ) + m$, and then the distributive law of Proposition 2.3.4.

$$\begin{align}((a++) \times b) \times c &= ((a \times b) + b) \times c \\ \\ &= ((a \times b) \times c) + (b \times c)\end{align}$$

Let's now consider the RHS and use Definition 2.3.1, and the inductive hypothesis,

$$\begin{align}(a++) \times (b \times c) &= (a \times (b \times c)) + (b \times c) \\ \\ &= ((a \times b)\times c)) + (b \times c)\end{align}$$

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

We have shown the base case $P(0)$ is true, and that $P(a) \implies P(a++)$, and so by induction, $(a \times b) \times c = a \times (b \times c)$ is true for all natural numbers $a$. $\square$