Exercise 2.3.3 (Multiplication is associative)

Question

Prove Proposition 2.3.5. (Hint: modify the proof of \href{./exercise_2-2-1}{Proposition 2.2.5} and use the distributive law.)\par 

	extbf{Proposition 2.3.5} (Multiplication is associative) For any natural numbers $a,b,c$, we have $(a	imes b)	imes c = a	imes (b	imes c)$.

Issa Rice · Accepted Answer

We keep $b,c$ fixed and induct on $a$. For the base case, we have to show $(0	imes b) 	imes c = 0	imes (b	imes c)$. The left hand side is $0	imes c=0$ and the right hand side is $0$ so the two sides are equal.\par

Now suppose inductively that $(a	imes b) 	imes c = a	imes (b	imes c)$. We want to show that $((a{{+}\!{+}})	imes b) 	imes c = (a{{+}\!{+}})	imes (b	imes c)$. Starting from the left hand side, $((a{{+}\!{+}})	imes b)	imes c$ equals $(a	imes b + b)	imes c$ by the definition of multiplication, which equals $(a	imes b)	imes c + b	imes c$ by the distributive law, which equals $a	imes (b	imes c) + b	imes c$ by the inductive hypothesis, which equals $(a{{+}\!{+}})	imes (b	imes c)$ by the definition of multiplication. Thus, the two sides are equal, which closes the induction.\par

Source: \href{https://issarice.com/}{Issa Rice's blog}.

Khagan Gulusoy · Answer

\begin{proof}
We induct on $c$ (keeping $a,b$ fixed). We first verify the base case $c=0:$
$$(a	imes b)	imes 0 = a	imes(b	imes 0).$$
By commutativity law and definition of multiplication, we have:
$$0 = a	imes 0.$$
By commutativity law and definition of multiplication, again:
$$0 = 0.$$
Thus, we've proven the base case. Now suppose inductively that $(a	imes b)	imes c = a	imes(b	imes c)$ is true for some natural number $c.$ We now prove $P(c++),$ which is:
$$(a	imes b)	imes (c++) = a	imes (b	imes (c++)).$$
We now keep changing the left hand side until we get the right-hand side. By commutativity law for multiplication,
$$(a	imes b)	imes (c++) = (c++)	imes (a	imes b).$$
By definition of multiplication:
$$(c++)	imes (a	imes b) = cab + ab.$$
By distributive law,
$$cab + ab = a(cb + b).$$
By distributive law, again:
$$a(cb + b) = a(b(c+1)).$$
Since $c+1 = c++$ (see page 26), we have
$$a(b(c+1)) = a(b(c++)).$$
\end{proof}

Exercise 2.3.3 (Multiplication is associative)

Answers

Comments

Comments

Exercise 2.3.3 (Multiplication is associative)

Answers

Comments

Comments

Add answer