Prove that multiplication is commutative

1. Aug 10, 2012

1. The problem statement, all variables and given/known data
n * m = m * n where m, n are natural numbers.

2. Relevant equations
I am working from Terrence Tao's class notes and he includes 0 in the natural numbers. m++ stands for m+1. He calls it incrementation and uses it to explain the rules of addition.

3. The attempt at a solution
Proof. We will induct on m holding n constant. For the base case, let m = 0. Then we have n * 0 = 0 * n. Both sides of the equation equal to 0. Now we assume inductively that n * m = m * n. For the inductive step we need to show that n * (m++) = (m++) * n. Since m is a natural number, we know from a previous proposition that m++ is also a natural number. Thus we can choose q to be the successor of m or in other words q = m++. Then we have n * q = q * n. According to the inductive hypothesis, this is true. This closes our induction.

Can someone take a quick look at my proof and tell me if there is anything wrong with it? Thanks!

2. Aug 10, 2012

HallsofIvy

Staff Emeritus
It sounds to me like you are using "Peano's axioms" which take induction,
"If a set X contains 0 and, whenever it contains a number a, it also contains a++, then X is the set of all non-negative integers", as a defining property of the non-negative integers. In particular, a+ b is defined by "b+ 1= b++" and if c is not 0, then there exist a such that c= a++ in which case b+ c= (b+a)++.

However, the difficulty appears to be that you do not understand what induction says! You say, first, "Now we assume inductively that n * m = m * n." Later you say "Then we have n * q = q * n. According to the inductive hypothesis, this is true." No, it isn't. The "induction hypothesis" is that n*m= m*n for those particular values of m and n. q is NOT m so n*q= m*q does NOT follow from n*m= m*n. You are essentially asserting that your "induction hypothesis" is just what you are trying to prove.

I also note that you don't say anything about how multiplication is defined here. You can't very well prove something about "multiplication" without using the definition of "multiplication"! I recommend that you talk to your teacher about this.

3. Aug 10, 2012