- #1
HMPARTICLE
- 95
- 0
Homework Statement
Let n,m be natural numbers. Then n x m = m x n.
Prove this.
Homework Equations
In order to prove this i am asked to prove 2 Lemma that will be useful.
In my solution i will (attempt to) prove these first.Definition of multiplication;
for all m in N
0 x m = 0,
(n++) x m := (n x m) + m.
The Attempt at a Solution
Lemma 1*
For any natural number n, n x 0 = 0.
Consider the base case, n = 0, 0 x 0 = 0 since 0 x m = 0 for every natural number and 0 is a natural number.
suppose inductively that n x 0 = 0. we wish to show that (n++) x 0 = 0. But by the definition of multiplication (n++) x 0 = n x 0 + 0 which is equal to 0 by the inductive hypothesis.
Lemma 2*
for any natural numbers n,m
n x (m++) = (m x n) + m
we induct on n. The base case, n = 0 gives m x 0++ = m and (m x 0) + m = m by lemma 1.
suppose inductively that m x ( n++) = (m x n) + m. we must show that m x (n++)++ = (m x (n++)) + m.
Now the right hand side is equal to ((m x n) + m) + m by the inductive hypothesis. rearranging we obtain m x n + 2 x m. Now the left hand side of the equation is m x (n+2) = m x n + 2 x m. Thus both sides are equal and we have closed the induction.
{ The above lemma is my main problem, it just doesn't seem correct. The book these exercises are from limit the use of operations until they are mentioned. Tao / analysis 1}
Let n, m be natural numbers. Then n x m = m x n.
we shall induct on n keeping m fixed.
First we do the base case n =0, we show 0 x m = m x 0. By the definition of multiplication 0 x m = 0, while by lemma 1, m x 0 = 0. Thus the base case is done.
Now suppose inductively that n x m = m x n. Now we prove that (n++) x m = m x (n++) to close the induction.
By the definition of multiplication (n++) x m = (n x m) + m;
By lemma 2 m x (n++) = (m x n) + m;
But by the inductive hypothesis (m x n) is equal to (n x m). and hence m x (n++) = (n++) x m and n x m = m x n.
Thus both sides are equal and we have closed the induction.
NOTE;
I have been plastering these pages with sub standard proofs, for that, i am sorry. I'd like some comments please. There are no solutions to the exercises so i am having to reply on forums. PF seems to be the best.
Last edited: