1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof: Multiplication is commutative

  1. Nov 15, 2014 #1
    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.

    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. jcsd
  3. Nov 16, 2014 #2
    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.
  4. Nov 18, 2014 #3
    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.
  5. Nov 18, 2014 #4
    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
  6. Nov 23, 2014 #5


    User Avatar
    Homework Helper
    Gold Member

    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?
  7. Nov 24, 2014 #6
    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.
  8. Nov 26, 2014 #7


    User Avatar
    Homework Helper
    Gold Member

    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?
  9. Nov 26, 2014 #8
    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted