Proof: Multiplication is commutative

[HMPARTICLE]

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.

 

[Joffan]

regarding Lemma 2, it looks like you are jumping way ahead of the available proven results.

I would suggest that, given the desired n x (m++) = (n x m) + n (note, corrected from your comment)
- you run induction on the first term of this, not the second. (show that, from [ n x (m++) = (n x m) + n ] you can deduce [ n++ x (m++) = (n++ x m) + n++ ]
You will need associativity and commutivity of addition. Be very careful not to switch your multiplication terms around - this is what you are aiming to prove, so using it within your proof is senseless. Essentially you need a lot of very small steps to gradually switch the expression into the desired state.

 

[HMPARTICLE]

Thanks again! it is ok to say that $$ ((n \times m) + m) + (n++)) = ((n \times m) + m) + (n+1)) $$ ? isn't it? because... its true? if so then i have definitely got it. then by using the propositions/lemma's that addition is associative and commutative i eventually get the same expression for the R.H.S as the L.H.S.

MANY thanks again. haha.

 

[Joffan]

I didn't need that, since I think we already had that (n + (m++)) = (n + m)++ = ((n++) + m)

However, since 1 is 0++, I think you could quickly prove that n++ = n+1

 

[epenguin]

For benefit of most of us could you tell us what m++ etc., the thing we were always told you couldn't write and doesn't mean anything, means?

 

[Joffan]

For benefit of most of us could you tell us what m++ etc., the thing we were always told you couldn't write and doesn't mean anything, means?

It's in his textbook, (I found http://www.scribd.com/doc/236152665/Analysis-I-First-4-Chapters-Second-Edition-Terence-Tao) and n++ just means the successor of n - what I have seen elsewhere written as S(n). I agree it can be a slightly confusing notation used inside addition expressions.

 

[epenguin]

I guessed it must be something like that - I thought I could do the proof if for ++ I could write +1.
I guess that is a bit crude of me, and 'successor of m' is philosophically and logically more minimal?

 

[Joffan]

I guessed it must be something like that - I thought I could do the proof if for ++ I could write +1.
I guess that is a bit crude of me, and 'successor of m' is philosophically and logically more minimal?

The successor concept is part of the Peano axioms. Here they are, using S(n) instead of n++:

1. 0 is a natural number
   
2. For every natural number n, S(n) is a natural number
   
3. For every natural number n, S(n) = 0 is false
   
4. For all natural numbers m and n, if S(m) = S(n), then m = n
   
5. If K is a set such that:
   • 0 is in K, and
   • for every natural number n, if n is in K, then S(n) is in K,
   then K contains every natural number

- the last one asserting the completeness of the successor function in generating all natural numbers.

Addition is defined using successors:

1. a + 0 = a
2. a + S(b) = S(a + b)

The definition of "1" is the successor of zero, S(0). So m+1 is a more complex concept, in this scheme, than S(m).

 

[rb120134]

regarding Lemma 2, it looks like you are jumping way ahead of the available proven results.

I would suggest that, given the desired n x (m++) = (n x m) + n (note, corrected from your comment)
- you run induction on the first term of this, not the second. (show that, from [ n x (m++) = (n x m) + n ] you can deduce [ n++ x (m++) = (n++ x m) + n++ ]
You will need associativity and commutivity of addition. Be very careful not to switch your multiplication terms around - this is what you are aiming to prove, so using it within your proof is senseless. Essentially you need a lot of very small steps to gradually switch the expression into the desired state.

How do you solve [ n++ x (m++) = (n++ x m) + n++ ], how can you show that this is the same?

Source https://www.physicsforums.com/threads/proof-multiplication-is-commutative.782057/

 

[Mark44]

How do you solve [ n++ x (m++) = (n++ x m) + n++ ],

You don't "solve" this equation, you deduce that it is true.

how can you show that this is the same?

The notation may be obscuring things. "n++" is computer notation, specifically the C and C++ programming languages, as well as other languages that are derived from C.

In this problem n++ seems to be shorthand for n + 1, and similarly for m++.

So, the task is to deduce (i.e., show) that $(n + 1) \times (m + 1)$ is identically equal to $[(n + 1) \times m] + (n + 1)$.

Source https://www.physicsforums.com/threads/proof-multiplication-is-commutative.782057/

This reference is useless, as it points to this very thread.

 

[rb120134]

You don't "solve" this equation, you deduce that it is true.
The notation may be obscuring things. "n++" is computer notation, specifically the C and C++ programming languages, as well as other languages that are derived from C.

In this problem n++ seems to be shorthand for n + 1, and similarly for m++.

So, the task is to deduce (i.e., show) that $(n + 1) \times (m + 1)$ is identically equal to $[(n + 1) \times m] + (n + 1)$.

This reference is useless, as it points to this very thread.

Thanks, but how do you deduce (n+1) x (m+1)=[(n+1) x m] + (n+1) I am stuck on the deducing part.