0

I am trying to prove Lemma 2.3.2 in Tao's analysis text: that for any two natural number, $n$ and $m$, we have $n \times m = m \times n$. I only have the properties of the natural numbers and addition to work with, along with Tao's definition of multiplication. I have been able to piece together most of the proof, but am struggling with the inductive step.

Proof. Induct on $m$, holding $n$ constant.

Base Case: ($m = 0$) When $m = 0$, we need to prove $n \times 0 = 0 \times n$. The RHS is $0$ by the definition of multiplication. To show the LHS is $0$, we induct on $n$. When $n = 0$, we have $0 \times 0 = 0$ by the definition of multiplication. Our inductive hypothesis is that $n \times 0 = 0$, and need to show that $n++ \times 0 = 0$. By the definition of multiplication, $n++ \times 0 = (n \times 0) + 0$. Using the inductive hypothesis and the properties of addition, we then have $(n \times 0) + 0 = 0 + 0 = 0$. Thus, our LHS is also $0$.

Induction Hypothesis: Assume $n \times m = m \times n$.

Induction Step: We must show that $n \times (m++) = (m++) \times n$.

I am able to manipulate the right-hand side, but it doesn't seem I am able to do much to the left-hand side.

We have: \begin{align*} (m++) \times n & = (m \times n) + n & & \text{Definition of multiplication} \\ & = (n \times m) + n & & \text{Inductive hypothesis} \\ & = (n++) \times m & & \text{Definition of multiplication} \end{align*} It doesn't seem I can do anything directly to the LHS without commutativity. My strategy was to manipulate the above into the LHS, but I can't think of where to go next.

Any help would be greatly appreciated.

Community
  • 1

1 Answers1

3

Perhaps we will learn something from showing $1\times n=n\times 1$? $$1\times n=0{+}{+}\times n =0\times n+n=0+n=n.$$ To show that $n\times 1=n$, we use induction: $$ 0\times 1=0$$ and $$ n{+}{+}\times 1=n\times 1+1=n+1=n+0{+}{+}=(n+0){+}{+}=n{+}{+},$$ voila!

Now to the general case. You already showed $$m{+}{+}\times n=m\times n+n=n\times m+n.$$ So what we need to show is

Claim. $n\times m{+}{+}=n\times m+n$

Proof. (By induction on $n$) For $n=0$, the claim follows from $0\times m{+}{+}=0$ and $0\times m+0=0+0=0$.

Now assume $n\times m{+}{+}=n\times m+n$; we want to show $n{+}{+}\times m{+}{+}=n{+}{+}\times m+n{+}{+}$. We have $$\begin{align}n{+}{+}\times m{+}{+}&=n\times m{+}{+}+ m{+}{+} \\&=(n\times m+n)+ m{+}{+}\\&=n\times m+(n+ m{+}{+}) \\&=n\times m+(n+ m){+}{+} \\&=n\times m+(m+n){+}{+}\\ &=n\times m+(m+n{+}{+})\\ &=(n\times m+m)+n{+}{+}\\ &=n{+}{+}\times m+n {+}{+}\end{align}$$ $\square$

Hagen von Eitzen
  • 374,180
  • Thank you for the extremely helpful answer. If I could ask just one more question: I understand every step you wrote, but where do we use the fact that $1 \times n = n \times n$? Is that needed in the inductive step? –  May 27 '19 at 23:08
  • You're not using it directly. He's using it to motivate and illustrate the general inductive step. – Robert Shore May 28 '19 at 07:51