Commutativity and all that

One of the nice things about our new definitions of addition and multiplication is that they make proving basic properties of the operations a snap. Looking at the recursive definitions, it’s not at all obvious that 3+5 is 5+3, or that 4⋅5 is 5⋅4. Or, more accurately, it’s obvious for any specific number (because you can just compute each one out and compare the results), but it’s not obvious how to show in general that n+m and m+n are always equal. It happens that it is possible, using a technique called induction… but that proof method, while beautiful in its way, is often pretty unenlightening. It forces you to accept that things are true, but it doesn’t help you understand why they’re true.

If our only definition of arithmetic were the recursive one, we would have no choice but to use induction. But since we’ve got a more (ahem) natural definition, we have a chance to get into the why of things.

Unfortunately there will be no stunning new abstractions in this post. It’s mostly application of the stuff I’ve already talked about, in the form of a long string of proofs. But the proofs themselves are pretty short and easy to follow. In fact, that’s the whole point I’m trying to demonstrate: once you’ve found the right definitions, results often just fall into your lap.

The laws of putting stuff together

Take addition, for example. Some day, a guy named Giuseppe might try to tell you that the real way to prove addition is commutative is this:

  • First prove that n+0 and 0+n are the same number.
  • Then prove that whenever n+m and m+n are the same number, n+next(m) and next(m)+n are the same number as well.
  • It will follow by induction that n+m and m+n are always the same number.

Don’t listen to that guy.

The reason addition is commutative isn’t because we can prove it using a clever technique, it’s because putting things together is commutative! It makes no difference which order you put two sets of things together—whether I’m taking about “all the fingers on my left hand and my right hand” or “all the fingers on my right hand and my left hand,” I’m still talking about the same bunch of fingers.

Theorem 1 (commutativity of addition). n+m is the same number as m+n, for any two natural numbers n and m. That is, addition is commutative.

Proof. If A and B are two disjoint sets of sizes n and m respectively, then AB and BA will have sizes n+m and m+n respectively. But AB and BA are exactly the same set: the one having every element in either A or B. So n+m and m+n must be the same number.  ∎

Likewise, addition is associative not by virtue of a clever argument, but because putting sets together is associative.

Theorem 2 (associativity of addition). n+(m+k) is the same number as (n+m)+k, for any three natural numbers n, m, and k. That is, addition is associative.

Proof. Let A, B, and C be disjoint sets of size n, m, and k respectively. Then A∪(BC) and (AB)∪C have sizes n+(m+k) and (n+m)+k respectively. But these are the same set: the one having every element in A or B or C. So n+(m+k) and (n+m)+k must be the same number.  ∎

Order matters—maybe

And then we come to multiplication. It’s not really so obvious how to deal with that one. (And it’s especially not obvious if you think multiplication is repeated addition, which it isn’t—why in the world should adding 7 to itself five times, and adding 5 to itself seven times, have the same result?)

The one point of concern is that set products aren‘t commutative: the order matters. Well, sort of.


[IMG: the product of PEANUTBUTTER and JELLY]

I’ve pointed out before that ordered pairs are ordered: the pairs (left shoe, right shoe) and (right shoe, left shoe) aren’t the same thing, as I discovered while dressing myself this morning. Likewise, the sets PEANUTBUTTER×JELLY1 and JELLY×PEANUTBUTTER aren’t equal—since the pair (Jif, grape) is in the first set but not the second, while the pair (grape, Jif) is in the second set but not in the first.


[IMG: the product of JELLY and PEANUTBUTTER]


But that’s no reason to start doing things Giuseppe’s way. To get a set-theoretic proof that multiplication is commutative, we don’t need the sets above to actually be the same set. We just need them to be the same size. And for that sort of thing we have bijections. And the bijection here is obvious: if someone hands you a jelly and peanut butter sandwich, turn it over!

Theorem 3 (commutativity of multiplication). nm is the same number as mn, for any two natural numbers n and m.

Proof. Let A and B be two sets of sizes n and m respectively. Then the product A×B has size nm, and the product B×A has size mn. But there is a bijective correspondence between A×B and B×A: to each pair (a,b) in A×B, associate the pair (b,a) in B×A. So A×B and B×A have the same size, which means nm and mn are the same number.  ∎

This goes just as well for associativity, if not more so. You can make a (Jif and grape jelly) and fluff sandwich, or a Jif and (grape jelly and fluff) sandwich, depending on which side you prefer to put your jelly on. But there’s a pretty obvious mapping between one and the other.

Theorem 4 (associativity of multiplication). n⋅(mk) is the same number as (nm)⋅k, for any three natural numbers n, m, and k. That is, multiplication is associative.

Proof. Let A, B, and C be any three sets of size m, n, and k respectively. Then the set A×(B×C) has size n⋅(mk), and the set (A×B)×C has size (nm)⋅k. But there is a bijective correspondence between these two sets: to each pair (a,(b,c)) in A×(B×C), associate the pair ((a, b),c) in (A×B)×C. So A×(B×C) and (A×B)×C have the same size, which means n⋅(mk) and (nm)⋅k are the same number.  ∎

Moving on

There is one other law of arithmetic worth mentioning, namely distributivity. For the sake of completeness I ought to include it.

Theorem 5 (distributivity). n⋅(m+k) is the same number as (n⋅m)+(n⋅k), for any three natural numbers n, m, and k.

I’m going to omit the proof of this one. This isn’t because I can’t think of a proof, but because the proof is so similar to all the others that I think it’s safe to leave it as an exercise for the reader. Just interpret n, m, and k as the sizes of sets, and everything becomes clear.

And with that, I think this topic is winding to a close: once I’ve defined exponentiation, I’ll be just about done with the “natural number sequence,” at least for the near future. Which leaves me with a question for my readers: what should I talk about next?

At the moment I have two ideas.

Option 1 is to give this same sort of treatment to the integers, rational numbers, algebraic numbers, and possibly the real numbers and complex numbers. I’ll probably have to refer to these things again and again, so it would be nice to settle what they are once and for all. On the other hand, I might start giving people the impression that math is all about nitpicking the obvious.

Option A is to look at infinite sets, and what “size” means for them. Most of the machinery we’ve developed on finite sets applies just as well to not-so-finite ones, and results in a whole new class of numbers called cardinals. This has the advantage of novelty, and I think it would be sort of fun to write.

I’ll probably write on both topics sooner or later, but I can put either one off for quite a while yet. In fact, I could head off in just about any direction from here—these two ideas are just at the forefront of my mind.

So, what say you: Option 1 or Option A (or something else)?

[1] As an American, I understand that jelly is a translucent fruit spread, set with pectin. It’s certainly not gelatin, as the Brits think it is for some reason.



5 responses to “Commutativity and all that

  1. Wow! Read through all of them and it is quite amazing! Actually when I first entered I read this post and I understood it perfectly, but reading from the start I realize you have only been using stuff inside your posts! That was quite breathtaking!

    • Thanks—I’m glad you enjoyed it! I don’t have a lot of readers yet, so it’s nice to get a comment when someone finds his way here. Do you have an opinion on what I should cover next?

      • Its in the fora! I’m tckthomas. and now you know my email… My suggestion was including subtraction. Solving an additive equation doesn’t work. What is an equation? Our mathematician doesn’t know equations yet!

  2. I will keep reading either way (you are giving me a nice alternate perspective on what is being taught in my Discrete Math I class), but I think I would like a topic that has some reasonably understandable open problems which you can present at the end of each post.

  3. Suppose we stay with the “repeated addition” concept of multiplication. Then how can you explain that repeating a commutative, associative operation once (addition->multiplication) gives a commutative, associative operation, another time (multiplication->exponentiation) it does not. What is the key difference between addition and multiplication that makes their repetition become different in terms of commutativity and associativity?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s