Exercise 2.3.1 (Multiplication is commutative)

Question

Prove Lemma 2.3.2. (Hint: modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4.)\par 

	extbf{Lemma 2.3.2} (Multiplication is commutative) Let $n,m$ be natural numbers. Then $n	imes m = m	imes n$.

Issa Rice · Accepted Answer

extbf{How to think about the exercise.} In the solution below, we prove two facts that help us with the actual proof. You might wonder where these two facts came from. And you might answer "well, you can just peek at Lemmas 2.2.2 and 2.2.3". That's quite right, but what if you didn't have access to the textbook? It turns out that you can \emph{try} to solve the exercise without proving the two facts, and see where you get stuck. Then, you can turn those parts into lemmas. Let's see how this works in practice.\par

We want to show $n	imes m = m	imes n$. We fix $m$ and induct on $n$. For the base case, we need $0	imes m = m	imes 0$. By the definition of multiplication, the left side is zero. What about the right side? Well, it would be nice if we could show that $m	imes 0 = 0$. So spin this off into a lemma. [Insert proof of the lemma here.]\par

Now suppose inductively that we have $n	imes m = m	imes n$. We want to show $(n{{+}\!{+}})	imes m = m	imes (n{{+}\!{+}})$. By definition of multiplication and the inductive hypothesis, the left side is $(n{{+}\!{+}})	imes m = n	imes m + m = m	imes n + m$. What about the right side? It would be nice if we could show that $m	imes (n{{+}\!{+}}) = m	imes n + m$. So spin this off into a second lemma. [Insert proof of lemma here.] This closes the induction, and completes the proof.\par

So as you can see, the source of the lemmas isn't mysterious: it's what you naturally get by attempting the proof and getting stuck.\par

extbf{Model solution.} We first show two facts analogous to Lemmas 2.2.2 and 2.2.3:
\begin{enumerate}
\item For any natural number $n$, $n	imes 0 = 0$: We induct on $n$. The base case is $0	imes 0 = 0$, which follows from the definition of multiplication. Now suppose inductively that $n	imes 0 = 0$. We want to show $(n{{+}\!{+}})	imes 0 = 0$. By definition of multiplication and the inductive hypothesis, $(n{{+}\!{+}})	imes 0 = (n	imes 0) + 0 = 0$. This closes the induction.

\item For any natural numbers $n$ and $m$, $n	imes (m{{+}\!{+}}) = (n	imes m) + n$: We induct on $n$ (keeping $m$ fixed). For the case $n=0$, we have to show $0	imes (m{{+}\!{+}}) = (0	imes m) + 0$. But $0	imes (m{{+}\!{+}}) = 0$ by definition of multiplication, and $(0	imes m) + 0 = 0+0=0$, so they are equal. Now suppose inductively that $n	imes (m{{+}\!{+}}) = (n	imes m) + n$. We want to show that $(n{{+}\!{+}})	imes (m{{+}\!{+}}) = ((n{{+}\!{+}})	imes m) + (n{{+}\!{+}})$. By definition of multiplication, $(n{{+}\!{+}})	imes (m{{+}\!{+}})$ is equal to $n	imes (m{{+}\!{+}}) + (m{{+}\!{+}})$, which is equal to $n	imes m + n + (m{{+}\!{+}})$ by the inductive hypothesis. Similarly, we have $((n{{+}\!{+}})	imes m) + (n{{+}\!{+}}) = (n	imes m + m) + (n{{+}\!{+}})$ by the definition of multiplication. Thus both sides are equal to $n	imes m + m + n + 1$.
\end{enumerate}

Now we can prove the actual lemma. We fix $m$ and induct on $n$. For the base case, we need $0	imes m = m	imes 0$. By the definition of multiplication, the left side is zero, and by fact (1) above the right side is also zero.\par

Now suppose inductively that we have $n	imes m = m	imes n$. We want to show $(n{{+}\!{+}})	imes m = m	imes (n{{+}\!{+}})$. By definition of multiplication, the left side is $(n{{+}\!{+}})	imes m = n	imes m + m$. By fact (2) above, the right side is $m	imes (n{{+}\!{+}}) = m	imes n + m$. Thus we have to show $n	imes m + m = m	imes n + m$, but this follows from the inductive hypothesis.\par

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

Khagan Gulusoy · Answer

The proof of the commutativity of multiplication is rather similar to the proof of the commutativity of addition. Recall that we have used the following schema to prove the latter:
\begin{figure}[H] \centering
    \begin{tabular}{lll|lll} 
    \multicolumn{3}{c|}{Commutativity of addition} & \multicolumn{3}{c}{Commutativity of multiplication}\
    \multicolumn{3}{c|}{$n+m = m+n$} & \multicolumn{3}{c}{$n\times m = m \times n$}\[10pt]
    Base case: &\multicolumn{2}{l|}{$0 + m=m+0$ (Lemma 2.2.2)} & Base case: &\multicolumn{2}{l}{$0 \times m=m \times 0$ (Lemma 1)}\[10pt]
    Induction hypothesis: &\multicolumn{2}{l|}{$n + m=m+n$} & Induction hypothesis: &\multicolumn{2}{l}{$n \times m=m \times n$}\[10pt]
    Induction step: &$(n++) + m$ &$= m + (n++)$ & Induction step: &$(n++) \times m$ &$= m \times (n++)$\
    &Lemma 2.2.3: &$= (m + n)++$ & &Lemma 2: &$= (m \times n)++$\
    &IH: &$= (n+m)++$ & &IH: &$= (n \times m)++$\
    \end{tabular}
\end{figure}

We now mimic this strategy for the multiplication as pointed out above.

% LEMMA 1
\begin{lemma}
For any natural number $m$, $m\times 0 = 0$.
\end{lemma}
\begin{proof}
We prove it using induction:
\begin{itemize}
    \item (\textit{Base Case}) We first take a look at the base case $m = 0.$ We have:
    $$0\times 0 = 0,$$
    which is true by Definition 2.3.1.
    \item (\textit{Induction Hypothesis}) Now suppose inductively that $m\times 0 = 0$ is true. 
    \item (\textit{Induction Step}) We now prove $P(m++)$, which is:
    $$(m++)\times 0 = 0.$$
    The left-hand side of the above statement by Definition 2.3.1 is equal to:
    $$(m++)\times 0 = m\times 0 + 0.$$
    By Lemma 2.2.2, this can be further simplified as:
    $$m\times 0 + 0 = m\times 0.$$
    By the induction hypothesis, we have:
    $$m\times 0 = 0,$$
    and we are done.
\end{itemize}
\end{proof}

% LEMMA 2 
We now prove one more statement, which is:
\begin{lemma}
For any natural numbers $n$ and $m$, $m\times (n++) = m\times n+m.$
\end{lemma}
\begin{proof} We induct on $m$ (keeping $n$ fixed). 
\begin{itemize}
\item \textit{(Base case)} We first verify the base case $m = 0:$
\begin{equation}
    0\cdot (n++) = 0\times n+0
\end{equation}
By Definition 2.3.1, $0\times (n++) = 0$ and $0\times n = 0.$ Thus, (1) is equivalent to the following:
\begin{equation}
    0 = 0+0
\end{equation}
which is true by Lemma 2.2.2.
\item \textit{(Induction step)} Now we suppose inductively that $m \times (n++) = m\times n+m$ is true for some $m.$ We now prove $P(m++),$ which is:
$$(m++)\times (n++) = (m++)\times n + (m++).$$
By Definition 2.3.1,
$$(m++)\times (n++) = m\times (n++)+(n++).$$
By induction hypothesis,
$$m\times (n++)+(n++) = m\times n + m + (n++).$$
Since $n++ = n+1$ (see page 26), we have:
$$m\times n + m + (n++) = m\times n + m + n + 1,$$
which is equal to
$$m\times n + m + n + 1 = m\times n + n + m + 1.$$
Since $m+1 = m++$ (see page 26), we have:
$$m\times n + n + m + 1 = m\times n + n + (m++).$$
By Definition 2.3.1, $$m\times n + n  = (m++)\times n.$$ Thus, we have:
$$m\times n + n + (m++) = (m++)\times n + (m++).$$
We now have $(m++)\times (n++) = (m++)\times n + (m++)$, as desired. Since our choice of $n$ was arbitrary, the assertion follows for any natural number $n$, as well.  
\end{itemize}
\end{proof}

Having proved these two lemmata, we can start with the proof of the exercise assertion.
\begin{proof}
We induct on $n.$
\begin{itemize}
    \item \textit{(Base case)} We first verify the base case $n = 0:$
    $$m\times 0 = 0\times m,$$
    which is true by Lemma 1 and Definition 2.3.1.
    \item (\textit{Induction Hypothesis}) Now suppose inductively that $m\times n = n\times m$ is true for some natural number $n.$
    \item \textit{(Induction Step}) We now prove $P(n++),$ which is
    \begin{equation}
        m\times (n++) = (n++)\times m
        \label{commut_1}
    \end{equation}
    By Lemma 2, the left-hand side of the equation \ref{commut_1} is equal to the following:
    \begin{equation}
        m\times (n++) = m\times n + m.
        \label{commut_2}
    \end{equation}
    By the definition of multiplication, the right-hand side of \ref{commut_1} is equal to:
    \begin{equation}
        (n++)\times m = n\times m+m.
        \label{commut_3}
    \end{equation}
    Substituting statements \ref{commut_2} and \ref{commut_3} into the statement \ref{commut_1}, we equivalently rewrite the assertion that we have to prove as:
    $$m\times n + m = n\times m+m.$$
    Since $m\times n= n\times m$ by induction hypothesis, we have:
    $$m\times n + m = m\times n+m.$$
    Thus, we've proven $P(n++).$
\end{itemize}
Since our choice of $m$ was arbitrary, the assertion follows for any natural number $m$, as well.
\end{proof}

Commutativity of addition			Commutativity of multiplication
$n + m = m + n$			$n \times m = m \times n$

Base case:	$0 + m = m + 0$ (Lemma 2.2.2)		Base case:	$0 \times m = m \times 0$ (Lemma 1)

Induction hypothesis:	$n + m = m + n$		Induction hypothesis:	$n \times m = m \times n$

Induction step:	$(n + +) + m$	$= m + (n + +)$	Induction step:	$(n + +) \times m$	$= m \times (n + +)$
	Lemma 2.2.3:	$= (m + n) + +$		Lemma 2:	$= (m \times n) + +$
	IH:	$= (n + m) + +$		IH:	$= (n \times m) + +$

Exercise 2.3.1 (Multiplication is commutative)

Answers

Comments

Comments

Exercise 2.3.1 (Multiplication is commutative)

Answers

Comments

Comments

Add answer