1
$\begingroup$

This isn't that rigorous, in that assumes that axioms about the addition of natural numbers have already been shown and proven, and I think it also assumes distributivity of multiplication. I don't know if the distributive property is something that has to be shown or assumed.

Anyway, for any natural number $n$, we have that $$n*1 = 1*n $$ because the left hand side is $$ \underbrace{1+ 1 + \dots + 1}_{n\ \text{times}} $$ which is the definition of $n$. Likewise, the right hand side is defined to be $n$. So they are equal.

Now we can use this to show that multiplication with $2$ is commutative, i.e. for any $n$ $$n * 2 = 2 *n$$ The left hand side equals $$ n * (1+1) = n*1 + n*1 = n + n = 1*n + 1*n = (1+1)*n = 2*n$$ Then we can show that multiplication with $3$ is commutative knowing that multiplication with both $1$ and $2$ is commutative, and that multiplication with arbitrary $m$ is commutative knowing that multiplication with $1$ and $m-1$ is commutative.

Is this correct? I see at least two potential problems:

  1. It assumes the distributive property of multiplication for natural numbers. While I find this axiom to be more "common sense" than commutativity, perhaps it should also be proved somehow. And maybe the proof relies essentially on commutativity of multiplication, leading to circular reasoning.

  2. It seems to use not only regular induction, but strong induction. In other words, I am not sure if multiplication being commutative for $m-1$ can be used as the induction hypothesis in regular induction or not, since it seems like it uses implicitly that multiplication is commutative for all lower natural numbers. I think ultimately this comes down to my not understanding the difference between induction and strong induction -- they are supposed to be equivalent, but I imagine that at such a foundational level the distinction between them might be important. What's the difference between simple induction and strong induction?

Context: This might be related to this question: Why Does Induction Prove Multiplication is Commutative? To be honest I am not sure though since I don't understand that question.

I remember reading somewhere, after doing a Google search, that one can prove that multiplication of natural numbers is commutative by induction. I didn't understand the argument at the time, probably because I didn't put in the effort to understand it properly, but I think I have the idea now, and want to confirm or verify that this is correct. It was stated similar to this: proof of commutativity of multiplication for natural numbers using Peano's axiom

$\endgroup$
  • 2
    $\begingroup$ If this is a proof under the Peano's axioms you need them, and the definition of multiplication by Peano. The definition of multiplication under the Peano context is $$S(m)\cdot n=(m\cdot n)+m$$ where $S(n)$ is the succesor function. If it is under the context of a group it will be different. $\endgroup$ – Masacroso Oct 1 '16 at 8:30
  • $\begingroup$ @Masacroso I am just looking for a way to explain to a 3rd grader learning multiplication for the first time that it is commutative. $\endgroup$ – Chill2Macht Oct 1 '16 at 9:18
  • 1
    $\begingroup$ If it is for the first time you can just say to them that it is commutative, i.e. that $ab=ba$. If you want to explain a bit more it will be interesting use a rectangle to represent multiplication, then they can see that is the same rectangle no matter what go first. $\endgroup$ – Masacroso Oct 1 '16 at 9:24
  • 1
    $\begingroup$ thre is a proof for non-negative ints on quora quora.com/… $\endgroup$ – user211299 Aug 21 '18 at 16:42
  • 1
    $\begingroup$ You need (strong) induction and the binary operation $+$ to splice in the commutative multiplication operation. See math.stackexchange.com/questions/2974212/… $\endgroup$ – CopyPasteIt Oct 30 '18 at 10:33
0
$\begingroup$

[Community wiki] First, one can establish that there is a proof of the left distributive property that doesn't rely on commutativity of multiplication. (And it seems that the right distributive property's proof also doesn't rely on commutativity of multiplication, basically by using the same argument as at the top of this post or an analogous version of the argument for left distributivity. I.e. we don't need to appeal to use commutativity of multiplication to prove right-distributivity either.)

I.e. using distributivity to prove commutativity of multiplication seems kosher to me.

Now it must again be warned that my understanding of the distinction between "regular" and strong induction is weak (especially since both principles can be used to prove the other, so in some sense they are logically equivalent? not sure that's actually true),

but anyway it seems that this answer on Quora by Jeff David (brought to my attention by @user211299) gives a proof sketch only using distributivity and what seems to more obviously be regular induction than the proof sketch given above in this post. Since quora seems like an unreliable place to store a good answer, I will copy-paste it here without claiming credit for it:

Here is a proof for all non-negative integers.

We are attempting to show that $ab=ba$, where $a$ and $b$ are non-negative integers. Let’s introduce a new equivalence, $b+e=a$ (i.e. $e$ is defined as the difference between $a$ and $b$; note that if $e=0$ then the proof becomes trivial. Also note that we assume $a \ge b$; this does not affect our result as the variables are symmetrical). Now we write:

1) $ab= \sum_{i=i}^a b $

This is nothing more than stating the definition of b multiplied by a, ie b summed a times. We can also write:

2) $ba=b(b+e)$

since $b+e=a$, by our own definition. We now try to show that equation (2) can be rewritten in the form of equation (1). We expand on equation (2) by writing:

3) $b(b+e)=\sum_{i=1}^b (b+e)$

This is very similar to what we did regarding equation (1), ie $b(b+e)$ is just $(b+e)$ summed $b$ times. Using some properties of addition, we can transform the right hand side of (3) to read:

4) $\sum_{i=1}^b (b+e)=\sum_{i=1}^b b+\sum_{i=1}^b e$

Now what we are going to do is assume the very thing we set out to prove! That is usually a big no-no unless you are using induction, which is basically where this is going.

5) Assume: $\sum_{i=1}^b e =\sum_{i=1}^e b$

We now substitute (5) back into (4) and proceed:

6) $\sum_{i=1}^b (b+e) = \sum_{i=1}^b b + \sum_{i=1}^e b$

The right hand side of (6) can be simplified:

7) $\sum_{i=1}^b b + \sum_{i=1}^e b = \sum_{i=1}^{b+e} b$

Finally, we make use of the fact that $b+e=a$:

8) $\sum_{i=1}^{b+e}b = \sum_{i=1}^a b$

Comparing (8) to (1) yields what we set out to prove:

9) $ab=ba$

Note that the proof hinges on equation (5), which is nothing more than a restatement of that which we set out to prove, namely:

5a) $be=eb$

The advantage that we have now (after going through all that work) is that we have reduced the number space of the original problem; $e$ by definition is less than $a$ (in the case where $e$ is equal to $a$, $b$ is identically $0$, and the whole proof becomes trivial). We can continue in this way to reduce the number space of the problem until we eventually get to a base case which can be shown to be trivially true (namely when $e=0$); this is the nature of inductive proof .

I know this isn’t as formal as a textbook proof, but it is a cute little intuitive proof that I had not yet seen presented in such a way on the internet, so I thought I would submit it. I really hope it helps someone!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.