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{array}{rl}((a++)\times b)\times c& =((a\times b)+b)\times c\\ \\ & =((a\times b)\times c)+(b\times c)\end{array}$$

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

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

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)⟹P(a++)$, and so by induction, $(a\times b)\times c=a\times (b\times c)$ is true for all natural numbers $a$. $◻$