The commutative law

Everybody believes the commutative law for multiplication of natural numbers: for any two natural numbers m and n, we have

m × n  =  n × m.

But even professional mathematicians have heated debates about exactly what counts as a proof of this law.

Here are three proofs.

First proof

It’s obvious. Consider the “dot diagram”

• • • • •
• • • • •
• • • • •

The equation 5×3 = 3×5 is clear from the diagram, and the method works for any number of dots.

Seecond proof

This is a theorem of Peano arithmetic, and we prove it from the Peano axioms. These involve a constant 0 and a unary successor function s; the axioms assert that

  • every element except 0 has a unique predecessor (that is, given n, if n ≠ 0 then there exists a unique m such that s(m) = n), while 0 has no predecessor; and
  • the Principle of Induction holds (that is, a set containing 0 and closed under s contains all natural numbers).

A way of stating the Principle of Induction without mentioning sets is that, if 0 has a certain property P, and if whenever a number n has property P then so does its successor, then we conclude that every natural number has property P. (The advantage is that we can restrict to properties defined in the first-order language.)

The Principle of Induction also allows us to use inductive definitions: that is, we define something for 0, and define it for the successor of a number in terms of its definition at that number, and the Principle guarantees that it is defined everywhere.

Now we can define addition and multiplication:

  • m+0 = n, and m+s(n) = s(m+n), for all m,n.
  • m×0 = 0, and m×s(n) = (m×n)+m, for all m,n.

Note in passing that, if 1 denotes the successor of 0, then

s(n) = s(n+0) = n+s(0) = n+1,

as we would expect.

Now the commutative law can be proved from the axioms. The proof is not completely straightforward; the left-hand side of the law is defined by induction on n, and the right-hand side by induction on m, so a double induction is required. I leave this as an exercise.

Third proof

Using von Neumann’s method, we can construct the natural numbers within Zermelo–Fraenkel set theory, and prove the commutative law there. The Zermelo–Fraenkel axioms are rather complicated, and I won’t give them here. The method is to define the successor of a set X to be X∪{X}. Then take 0 to be the empty set ∅ the natural numbers are everything we can get from this by applying the successor operation (that is, the intersection of all sets closed under s and containing ∅). In particular, we have 1 = {∅}, 2 = {∅,{∅}}, and so on. Conveniently, n is a set with n elements for all n, so these “natural numbers” can be used as standard sets for counting like the standard metre or kilogram for measuring or weighing.

We could now verify that these constructed natural numbers satisfy the Peano axioms, and use our earlier proof. But it is convenient to do something different. We say that a set X is finite if there is a bijection between X and some natural number n. (Such a set is sometimes called Peano finite; I will return to this.) We can prove that the same set cannot have a bijection to two different natural numbers; so we can (as hinted above) define the cardinality of a finite set to be the unique natural number bijective with it. It is now clear that, if X and Y are sets with a bijection between them, and one is finite, then so is the other, and they have the same cardinality.

The Cartesian product X×Y of two sets X and Y is the set of all ordered pairs (x,y), where xX and yY. Now it is clear that there is a bijection between X×Y and Y×X (just turn the ordered pairs around). Moreover, it is not hard to see that m×n is finite for any two natural numbers m and n. So the commutative law holds.

Commentary

The first proof is immediately convincing, and for most of the history of our subject no mathematician would have looked for any other proof. However, it has at least two major flaws:

  • How do we know that when we count the same collection of dots in different ways (by rows and by columns), we get the same answer?
  • Can we be sure that the “dot diagram” principle is still valid for unimaginably large numbers of dots (much larger than the number of elementary particles in the observable universe)?

The second proof rests on the two, rather simple, axioms of Peano arithmetic. You might regard either or both of them as problematic – plenty of people do – but they avoid the difficulties of the first proof, and if you do accept the axioms, the proof is logical and convincing. However, it is extremely unnatural. Why should such a simple fact require a complicated argument involving double induction in its proof?

The Zermelo–Fraenkel axioms seem on first sight to be rather a lot to take on trust. In fact, commonly accepted current mathematical practice is to take them as the basis on which all our mathematics is built. There are still some difficulties, which I will come to. But from then on, everything is good: the construction of the natural numbers is simple, and the proof seems to capture precisely the intuition of the first proof, as well as avoiding its difficulties. Turning the coordinates of the dots around transposes the dot diagram, so that rows become columns and vice versa, just as we want.

Our difficulties with this proof, I think, come from the Zermelo–Fraenkel axioms themselves. Here is one example.

There is another definition of a finite set in ZF. A set X is Dedekind finite if there does not exist a bijection between X and a proper subset of itself. The idea is that the simplest infinite set, the natural numbers, has a bijection (the successor function) which is a bijection between all the natural numbers and all except 0. With this definition that a Dedekind finite set cannot have a bijection to a proper subset of itself, and so the fact that a set cannot be bijective with two different natural numbers is clear. (By construction, of any two natural numbers, one is a subset of the other.)

But the two types of finiteness are not equivalent in ZF; we need to assume some version of the Axiom of Choice to prove this. (If a set is not Peano finite, then we can pick a sequence of elements x0, x1, …, and never run out of elements to pick. Now these chosen elements form a subset bijective with the set of all natural numbers, and we can map it bijectively to all except x0, and fix all the elements we didn’t pick. So the set is not Dedekind finite.

I think this sort of thing gives some people a feel of unease with arguments in ZF, and probably explains why they are unhappy with it.

Exercise

  • Prove the Commutative Law in Peano arithmetic.
  • Translate your proof into Zermelo–Fraenkel set theory.
  • Explain this proof in the language of dot diagrams. (It suddenly becomes quite simple!)
Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , . Bookmark the permalink.

19 Responses to The commutative law

  1. dratman says:

    If the commutativity of multiplication is to be discussed as a law of natural science, we do not know if it is true, and never can know, because it is supposed to apply to sets whose size has no limit, and we as humans will always be limited by physical and temporal barriers.

    Personally I am agnostic about commutativity when discussing objects bigger than, let us say, our galaxy. Or even my living room, to be honest — if only because I am far too lazy to undertake any test that might take me beyond the edge of a piece of typing paper. So I have to be humble. Also, I can say without any uncertainty at all that I will lose count within a very modest range. If that is going to be the criterion, I might as well assume the law is in general false, and only very occasionally true, probably by virtue of multiple mistakes.

    But if the commutativity of multiplication is viewed as not depending on the physical world as we happen to find it, then, in that sense, there are no “unimaginably large numbers of dots,” because we are letting our axioms represent us in the world of that particular type of imagination. If the axioms cannot even stand in for us in such simple situations, we might as well not have them at all.

    I mean, has anyone actually laid out dots numbered in, say, 20 digits? Yet we feel extremely confident about success with such relatively small numbers — and, as a bonus, the semiconductor manufacturers will eventually do the 10^20 problem with an array of memory bits, which will subsequently be extensively tested in ways that depend on all sorts of related congruences, in millions of locations all over the world, by consumers who will definitely complain if any of their rectangles fail to behave as expected.

  2. Try to multiply

    98734
    X 879
    _____

    Now try to multiply the same numbers as follows:

    879
    X 98734
    _______

    The second one is very difficult to do!

    So in real life, there is no commutativity!!!
    Am I right?

    Alireza Abdollahi

  3. That’s a nice puzzle. Both sums require 15 single-digit multiplications, or table lookups; the first requires 12 carries in the multiplication, the second only 10. But the second requires 5 numbers to be added at the end, the first only 3. So there is no great difference in the computational difficulty. Yet I feel you are right, and I guess that almost everyone faced with this sum would use the first layout. I am not sure why.

  4. Ross Templeman says:

    [disclaimer – please note that the tone of this post is not meant to be aimed at Professor Cameron, he was one of my best teachers when I was an undergraduate, (I am just venting)]

    “the Principle of Induction holds (that is, a set containing 0 and closed under s contains all natural numbers”

    Suppose we imagine a rectangle. We infer that a smaller rectangle could exist within it and within that one yet another smaller rectangle and so on. Yet we do not suppose that we could carry out an actual drawing of unending rectangles. Rather we intuit that since space has no smallest possible region, the notion of a yet smaller region is well founded.

    It strikes me that this is an alternative way of characterizing induction that doesn’t assume that all the counting placeholders actually exist at a given moment and so is more intuitive.

    I would say that the problem with the inductive proof is not that the general idea is wrong in itself (obviously it isn’t) but that the presentation of basic ideas, such as induction, is done so poorly (and so unnecessarily poorly) by mathematicians that a feeling of being overwhelmed by obscurity is almost inevitable.

  5. Ross Templeman says:

    RE: dratman

    “But if the commutativity of multiplication is viewed as not depending on the physical world as we happen to find it, then, in that sense, there are no “unimaginably large numbers of dots,” because we are letting our axioms represent us in the world of that particular type of imagination. If the axioms cannot even stand in for us in such simple situations, we might as well not have them at all”.

    etc etc etc…

    I am never quite sure what to make of posts like this. Sometimes I think its all just a wind up and sometimes I think I am reading the words of a man who has lost his marbles. I am going to assume it is a wind up in this case, since anyone who feels the need to hide behind a pseudonym on a maths blog written by a liberal maths professor, probably isn’t intending to be taken seriously.

    For those that are interested in thought going wrong, there is a rather entertaining essay available on line; “What is Wrong with our Thoughts: a neo-positivist credo” by the late Australian philosopher David Stove (he uses numbers as an example which is why I mention it here). Just type the title and author in to a search engine and you will find it easily enough.

  6. This is a response to Ross Templeman’s f irst post (and thanks for the disclaimer – much appreciated!)
    I don’t think your rectangle analogy is really an alternative explanation of induction, for two reasons. First, because there are two important parts of induction: the starting point zero, and the successor function: everything must have a unique successor. Now a rectangle doesn’t contain a unique “next smaller” rectangle within it. The second objection is that it is possible to imagine (and some physicists, e.g. Lee Smolin, do so) that space is discrete; the rectangles cannot go on getting smaller for ever.

    I think the test of induction is to find a situation where it fails, a “non-standard model” if you like. For just the zero and successor, this is easily done. Imagine that you have the natural numbers, starting at zero, stretching out to the right. Above the line carrying them is another line, with integer points stretching out both ways; then another, and another; as many as you like (finitely or infinitely many such lines). We have a zero (on the bottom line) and a successor function (which moves one step right on whichever line you are on); every point except zero has a unique predecessor. But induction fails. A set containing zero, and having the property that if it contains some point then it contains its successor, need not contain everything: it must have all the points on the bottom line but could contain an arbitrary number of the other lines.

    Thus it is the principle of induction which guarantees that the natural numbers are just what we think they are, no more.

  7. Ross Templeman says:

    I Thank Professor Cameron for his response (Re: disclaimer – you are quite welcome, I still help myself to the lecture notes you keep on your web page).

    My first posting wasn’t as detailed as it should be, I would fully accept that, however I must respectfully disagree with the specific objections stated below.

    “I don’t think your rectangle analogy is really an alternative explanation of induction, for two reasons. First, because there are two important parts of induction: the starting point zero, and the successor function: everything must have a unique successor. Now a rectangle doesn’t contain a unique “next smaller” rectangle within it. The second objection is that it is possible to imagine (and some physicists, e.g. Lee Smolin, do so) that space is discrete; the rectangles cannot go on getting smaller for ever”.

    I will address the second objection first because I think it is sounds more damaging to my case. Professor Cameron says that it is possible to imagine that space is discrete. I have heard this on quite a few occasions but I have never been able to fathom how the advocate of it believes that it undermines the notion of a smaller region of space. Rather it seems we are being told that we cannot physically probe such a smaller region even in principle, which is a very different matter. In physics this is undoubtedly of much importance (and interest), but for the issue we are discussing I do not see the relevance.

    Moving on to the first objection. It is true that there is no unique next smaller rectangle, but is it not the case that we are only conceiving of a single new rectangle immediately within the former (like Russian dolls)? This strikes me as being sufficient to capture the idea of unending succession beginning from the ‘blank’ initial rectangle which captures the notion of a starting point (the zero).

    I think perhaps I should start from scratch and pay more attention to detail this time. Okay then…ready…steady…GO!

    The thread is about ways of justifying the commutative law for the natural numbers and the complications that they involve. The visual method is initially complemented but then criticized for perhaps leaving us with niggling doubts when things get very large. The complication of the inductive method is its apparent abstractness and complexity (I see the two problems as related), moreover some people claim to have problems with the Peano axioms.

    Perhaps then, the proper thing to do, since no one is expressing doubts with the small examples that visualization handles so satisfactorily, is to find a way of understanding induction in a visual manner that isn’t vulnerable to the same objections as the previous visual method, but which at the same time shows the Peano axioms to be unobjectionable. (By unobjectionable here I am of course referring to sensible objections, no Pyrrhonian skepticism or postmodernism please dear readers).

    In order to do this, assuming it is even possible, we first need to understand what might be objectionable about Peano’s axioms.

    Well so as not to bore everyone to tears let us skip over the question of what “zero is in itself” and other such blights, I am assuming everyone reading this has sufficient grasp of what a small natural number is even if they are not confident about being able to express themselves regarding this matter.

    That just leaves us with the induction axiom. What might be objectionable about this then? Well I once spent an entire summer worrying about the foundations of mathematics myself some years ago and I went through a phase of questioning the Peano axioms for various reasons. If my own experience is anything to go by then it all comes down to this:

    ‘We are either been asked to take the notion of the “actual infinite” for granted, despite all those set paradox thingys that have caused problems in the past or we must imagine some kind of unending process involving counting, even though the number of objects in the universe is supposed to be finite, or we are replacing what common sense would regard as mathematics with some game involving meaningless symbols. Yet Mathematics is supposed to be crystal clear and very useful, that beautiful temple of human reason….etc…etc…etc’.

    This above is obviously just a crude summary of the kind of thinking involved when doubting such things as the Peano axioms, but I trust the gist is sufficient (if it isn’t then I recommend consulting the essays of the finitist mathematician Norman Wildberger – type his name into a search engine and go to his personal pages).

    So how does an OCD wreck like me recover from such delirium? Well, since we are trying to understand something that is supposed to be quite basic, it makes sense to survey the basic materials and tools that our mind has at its disposal. This is a long and rather tedious affair to try and state in a lot of detail so I will just skip to the end; we have our sense of (finite) spatial extension, our notion of (small) numbers, basic ideas like two things being the same or different, the notion of repetition, the law of non-contradiction, modal concepts like possibility and necessity etc. So the question then becomes how can we understand and justify the notion of induction using these tools?

    Well, let us state intuitively rather than abstractly what it is we are hoping to justify and how. We begin with some representation of small numbers starting with unity (rather than zero just because that happens to be my personal preference); I , II , III , IIII , IIIII , IIIIII , IIIIIII , IIIIIIII , and we seek to destroy any sensible doubts about the validity of attaching those charming traditional three dots … , moreover we wish to do so using an intuitive method.

    If we can do this then we can move on to the question of whether our proposed method allows us to at least treat some of the pedagogical war wounds that Professor Cameron has complained of regarding justifying commutativity using induction.

    Well I have previously stated the notion of “Russian doll rectangles” in my initial response to Professor Cameron and I believe I have adequately responded to the first of his objections, however I will elaborate on a point that I should have included the first time round regarding his second objection, but didn’t (slapping own wrist right now…ouch). Above I made a point of saying that our mind is ‘equipped’ with ideas regarding modal concepts such as ‘possibility’.

    This is a point of vital importance and whether one accepts it or not is what determines whether one thinks that the induction axiom is well grounded in intuition or if one thinks it is just a plausible suggestion that we have to take on trust.

    What does it mean to say that something is “possible even if it is never made actual in the real world”? Covering all the ground regarding this question would be unduly long if we took it on as a full blown philosophical project, but I do not believe that such efforts are needed for the issues we are concerned with here. Instead I will use an analogy: we remember (rightly or wrongly) that certain events happened in the past, but in so doing we do not infer that we are actually engaging in time travel. So in other words we can *conceive* of the past without the past actually existing (apologies for lack of detail here but I trust it is sufficient). Similarly we can be said to conceive of a state of affairs as being possible without supposing that it can be physically ‘actualized’ (for lack of a better word).

    If one accepts this (I would be most interested in speaking with someone who didn’t) then the physics objection raised by Professor Cameron would seem to have no force.

    Let us move on to the pedagogical question then. That is to say, does the “Russian doll rectangles” idea make the appreciation of a proof by induction easier in either reducing its complexity or its abstractness? Well I would submit that since it is grounded in intuition far more easily than the ‘ZF and Peano speak’ that burdens undergraduate encounters with foundations, I don’t see how it could fail to be less abstract. So we are left with the question of whether it reduces the complexity.

    Well, complexity of an argument is a matter of how long an argument is and how difficult it is to follow. I don’t think the length can be significantly altered, so I admit defeat on that one, but if the principle of induction is ‘humanized’ by grounding it in intuition before it is widely applied then I would submit it as plausible that the apparent difficulty of some of the proofs utilizing it should decrease.

    [Please note that I am likely to preoccupied with revising for my postgraduate mathematics exams taking place on Oct 10th, for the next two weeks, so any response from me to another reply may or may not be slow to arrive. However I promise to respond to any and all replies on October 11th /12th if not before.]

    Best wishes to all and good luck to teaching your next batch of undergrads Professor Cameron.

  8. Ralph says:

    I don’t think it makes sense to try to “prove” commutativity. And why worry about multiplication? Addition is, in a way, worse, because there are no rectangles or any other complicating distractions. And why even get as far as addition? What we really have to ask is whether we believe that in some sense we can count objects — whether abstract or real — and always expect to get the same answer every time we do it with tge same objects. But everyone who has ever lived on this planet knows that in practice one very often does not get the same answer. The constancy of numbers can never stand up as an experimental fact, because there will always be some counterexamples popping up that we will have to ghostbust. And that kind of work is probably not very interesting if you just like playing around with equations and diagrams and symbols and such. Yet, I suppose it’s a living. Now tomorrow we have a Miss Mary Gardner calling to discuss some concerns she has about the foundations of mathematics which she began looking into when she observed that she could never count a group of sewing needles and get the same answer. Later today we will be payingr a visit to straighten out some of her axioms.

  9. Did I do such a bad job of explaining things in my post? At least I get the opportunity to put the record straight…

    I will just make two comments. Firstly, why the commutative law for multiplication, rather than something simpler? As I tried to explain, one of the absolutely crucial principles involved in the proof in ZFC is that, if you count a finite set in two different ways, you must get the same answer. I did say that this principle is a theorem in ZFC (the standard foundation for mathematics). So if, for example, you wished to define m×n to be the number of dots in a rectangle of the appropriate size, then in ZFC there would be no ambiguity.

    Second, I want to stress again that while the principle of induction is an infinite principle, it is “not very infinite”. Here is my standard explanation (which I certainly did not invent!) Suppose that you have a line of dominoes labelled by natural numbers (starting with 0). Assume that the dominoes are arranged in such a way that, if the domino labelled n falls, then it inevitably knocks over domino number n+1. Now focus your attention on any particular domino (number n, say), while your assistant pushes domino number 0 over. Then it is guaranteed that the domino you are watching will eventually fall. We don’t require that there are infinitely many dominoes here. That is the principle of induction.

    What is going on here is nothing but counting. The principle is that, for any natural number n, it is in principle possible to start at 0 and count up to n, however impractical it might be in practice.

    I can’t resist re-telling a story from my friend Jack van Lint, giving his view of the foundations of mathematics. There was an old castle, with strong walls seeral metres thick. In the dungeon was a tribe of spiders who spent their time spinning webs, filling the dungeon with their constructions. Once a year, a castle flunkey was sent down to the dungeon to clear away the cobwebs. When this happened, the spiders cowered into the corners, convinced that without the support of the cobwebs the castle would collapse.

  10. I just learned that Ed Nelson claims to have proved that Peano arithmetic is inconsistent. To read more about this rumour, see http://rjlipton.wordpress.com/2011/10/01/what-if-peano-is-inconsistent/

  11. Ross Templeman says:

    I thank Professor Cameron for his response. Alas I must disagree with some of what he has said.

    As it happens I fondly remember the dominoes example from my undergraduate days at Queen Mary, I believe it is used in the first year course on introductory discrete mathematics. For such a course it serves a purpose, but for a discussion of foundations it is not quite adequate because it obscures certain important subtleties.

    Professor Cameron writes “,… if the domino labeled n falls, then it inevitably knocks over domino number n+1………We don’t require that there are infinitely many dominoes here. That is the principle of induction”.

    The problem I have here is that the use of the variable n requires that we assign a meaning to this variable. What is that meaning, what does the symbol stand for? The answer is obviously ‘possible natural numbers’. How many possible natural numbers are there? I am brought back to a problem I mentioned in my previous post; it looks as if we are committed to;

    1) endorsing the notion of actual infinity despite previous aches and pains

    2) or trying to make sense of unending counting in a universe of finite resources,

    3) or reinterpreting mathematics so that the variable n has no quantitative meaning after all (in which case a ‘formal’ statement of induction is part of a ‘formal definition’ of N).

    One’s attitudes to these options partly determine how one views mathematical induction.

    Finitists would reject all three. Some mathematicians seem to write as if they endorse both 1) and 3) simultaneously. Intuitionists try their hand at 2) in rather implausible ways and with peculiar consequences regarding the law of excluded middle. I believe that Henri Poincare showed that position 3) is incoherent. Some pure mathematicians seem to take option 1) but attach a fallibility clause due to Gödel’s incompleteness theorem (or something along these lines), Henri Poincare also criticized views such as this in his book ‘Science and Method’.

    If understanding induction properly is essentially about grasping the dominoes metaphor or some other common metaphorical illustration and knowing how to write down the formal statement of the principle, then it is difficult to understand how such intelligent philosophical disagreement actually arises.

    (I do like the spiders story though).

    Kind regards to all.

    • I’ll be brief. I think the difficulty lies within logic. The logical principle of Generalisation allows us to go from the statement P(n) for one (fixed but arbitrary) value of n, to the statement “for all n, P(n)”. In the dominoes example, the statement that domino number n (the one you are watching) falls is the first, the statement that all dominoes fall is the second. I believe that this is where some people baulk.

  12. Ralph Dratman says:

    To Ross Templeman, I am not using a pseudonym. My real name is Ralph Dratman. Why do you write that my comment was a “wind up” or that I have lost my marbles?

    I confess that I wrote casually, and that alone may have merited your elaborate disdain. Perhaps I should apologize for flippancy.

    Nevertheless, the paragraph you quoted was serious:

    “But if the commutativity of multiplication is viewed as not depending on the physical world as we happen to find it, then, in that sense, there are no “unimaginably large numbers of dots,” because we are letting our axioms represent us in the world of that particular type of imagination. If the axioms cannot even stand in for us in such simple situations, we might as well not have them at all.”

    As we all know, results calculated in Euclid’s geometry turn out not to agree numerically with large-scale measurements made in our actual world. Likewise, in quantum mechanics, we are compelled to use a computation such as Feynman’s “sum over histories” to average over (the wave functions of) scenarios in which the number and type of particles varies.

    Let me put that another way. The simultaneous existence and non-existence of specific intermediate particles must sometimes be taken into account to make predictions about even a single event which both began and ended with one particle.

    Thus it is unambiguously the case that the ZFC axioms do not correspond with all the facts of our universe, at least when dealing with very small things. That the axioms might also not correspond with physical results in which large numbers of ordinary-sized objects participate is not only possible but, I think, likely.

  13. Ross Templeman says:

    I thank Professor Cameron and Mr.Dratman for their responses. I will try to post replies by the end of the week.

    Kind regards.

  14. Ross Templeman says:

    Okay, I have finished writing up my response to Mr. Dratman. However I think I should seek Professor Cameron’s consent before posting it, since it is about 2000 words in length and I am not aware either way of the existence of word limits etc.

    Regards

  15. I don’t think there is a specific word limit, but I would like to move this discussion somewhere else for convenience. I will set up a page (when I have a spare moment, maybe over the weekend) and suggest that you post there.

  16. I put up a page called “Foundations”. Please continue the discussion there.

  17. Ross Templeman says:

    Will do. Thank you.

  18. Pingback: Theorems From Physics? | Gödel's Lost Letter and P=NP

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s