# Proof: Multiplication is commutative

1. Nov 15, 2014

### HMPARTICLE

1. The problem statement, all variables and given/known data
Let n,m be natural numbers. Then n x m = m x n.

Prove this.

2. Relevant 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.

3. 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: Nov 15, 2014
2. Nov 16, 2014

### 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.

3. Nov 18, 2014

### HMPARTICLE

Thanks again! it is ok to say that $$((n \times m) + m) + (n++)) = ((n \times m) + m) + (n+1))$$ ? isnt 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.

4. Nov 18, 2014

### 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

5. Nov 23, 2014

### 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?

6. Nov 24, 2014

### Joffan

It's in his text book, (I found a preview of a few pages) 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.

7. Nov 26, 2014

### 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?

8. Nov 26, 2014

### Joffan

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).

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted