Tuesday, November 1, 2011

How multiplication is really defined in Peano arithmetic

A familiar joke in mathematical logic (the field I worked in for the first twenty years of my career) is the following hypothetical entry in a mathematical dictionary:

Recursion
See “Recursion”.

Though recursion is ubiquitous in modern mathematics, even at the most basic level of the analysis of the arithmetic of natural numbers, it is a subtle concept, easily misunderstood. At its heart is the always problematic step from the finite to the infinite. Having taught set theory and the foundations of mathematics for many years at various universities, I long ago learned that many students never do fully grasp it.


Many sources gloss over it. For example, the Wikipedia entry for the Peano Axioms for the natural numbers, which on the whole is pretty good, refers to “recursionto justify its definitions of addition and multiplication on the natural numbers, but the Wikipedia page it links to punts when it comes to properly explaining the all important Recursion Principle, let alone proving it (the set-theoretic Recursion Theorem), giving a sketch proof of uniqueness (easy) but not the crucial existence part (which many people find tricky). [My comments refer to the pages when I accessed them on October 31, 2011.]


The widespread lack of appreciation for the Recursion Principle (it’s a principle you use when you are developing Peano arithmetic, a theorem you prove when you are doing set theory) lay behind many of the erroneous comments I received in response to my series of articles on multiplication not being repeated addition (not even on the natural numbers). Those articles appeared on MAA Online in June 2008, July-August 2008, September 2008, and January 2011.

If you really understand the Recursion Principle, which is what is required in order to construct addition from the successor function and to define multiplication from addition, then you will know that addition is not repeated successor (though oddly, no one ever claimed that to be the case) and multiplication is not repeated addition.

ASIDE: This is not an article about mathematics education. How teachers introduce addition and multiplication is another issue. I am not, repeat not, suggesting we teach recursion in the K-12 system. My complaint throughout that previous exchange was that, whatever and however we teach in our schools, we should not be stating things that are flat wrong. In this column I want to explain the recursion principle, its importance, its power, its need in mathematics, and how it is used, so you too will know why it is flat wrong to tell kids that multiplication is repeated addition. Remember, even if you don’t see the purpose of all the mathematical navel-inspection that led to the formulation of the principle, some of the students in your class may well find themselves wanting or needing to understand it in a few years time. While it is often pedagogically wise to say less than the whole truth, we should not lie to our students.

Okay, I’m back off my pulpit. The Recursion Principle is a rabbit-out-of-the-hat existence assertion. When used to construct addition from the successor function in Peano arithmetic, it tells you that there is a function from NxN to N that, lo-and-behold, can in any specific instance (i.e., for any pair of specific natural number arguments) be calculated by repeatedly applying the successor function a fixed number of times. Likewise, when the recursion principle is used to construct multiplication from addition in Peano arithmetic, it tells you that there is a function from NxN to N that, again wonder-of-wonders, can in any specific instance (i.e., for any pair of specific natural number arguments) be calculated by repeatedly adding a fixed number of times.

You need to invoke the Recursion Principle in order to obtain addition and multiplication because without it you just don’t get those functions. Period.

Let’s see how the Wikipedia entry I referred to earlier handles the Peano constructions of addition and multiplication.

(click image for full size)

If you read that Wikipedia account carefully, you will see that it does not actually tell you how to define addition or multiplication. Rather it tells you the properties those functions will have once they have been defined. The closest you get to an indication of how the two functions are defined is that word “recursively”, which as I noted earlier, links to another Wikipedia page that also does not tell you how the function is defined.

The definition is actually not difficult, provided you are used to working in abstract set theory. But since most people are not, authors typically leave it out, an instance where saying less than the whole truth is, in my view, justifiable. (Though I think they should explicitly note that what is being missed out is fundamental and important.)

Let’s re-write the Wikipedia definitions of addition and multiplication in standard functional notation. Thus, addition is a function P:NxN -> N such that for all numbers a, b,

1. P(a,0) = a

2. P(a,S(b)) = S(P(a,b))

and multiplication is a function M:NxN -> N such that

1. M(a,0) = 0

2. M(a,S(b)) = P(a,M(a,b))


The Recursion Principle guarantees that such functions exist. In general form, the principle says (and this is the version for binary functions over N):

Given a function H:NxN -> N and a number c, there is a function F:NxN -> N such that

1. F(a,0) = c

2. F(a,S(b)) = H(a,F(a,b))


In words, 2 says that for any given first argument a, the value of F where the second argument is the successor of b is defined in terms of the value of F where it is b. The function H tells you precisely how those two values are related.

Actually, the Recursion Principle also guarantees that the function F is unique. But that part is easy to prove from the two conditions, using induction. (Wikipedia sketches the proof.)

There are variants of the principle for unary functions and for n-ary functions for all other n, as well as for other domains besides N.

Here is how the function F is defined within set theory. Remember, in set theory, a function from NxN to N can be defined as a set of ordered triples (x,y,z) of numbers such that for each pair x, y of numbers there is exactly one number z such that the triple (x,y,z) is in the set.

Let W be the family of all sets of ordered triples T of numbers such that

1. (a, 0, c) is in T, for all numbers a

2. if (a, x, y) is in T, then (a, S(x), H(a,y)) is in T.


Then let F be the intersection of the family W. It is a routine exercise in set theory to prove that F is the required function. (That last sentence means that a mathematician having some familiarity with set theory will find it routine. It is a typical early exercise in an undergraduate course in set theory.)

So now you know.

This may all seem like a great deal of fuss about nothing. But what is going on here is really very deep. Much of modern mathematics involves finding ways to handle the infinite - calculus exclusively and spectacularly so. Mathematicians learned over many years of painful lessons that the step from the finite to the infinite is a tricky one that requires considerable finesse. In particular, you have to exercise great care to set it up correctly and do it right. The Recursion Theorem is one of those crucial bridges that allow us to go beyond the finite to the infinite, to extend human intellect from its finite physical limitations to the infinite world beyond that our minds can construct. By getting the mathematics right, we can make that step with total confidence. Confidence both in that abstract world itself and in the concrete conclusions it allows us to reach about our lives, our science, and our technologies. That is huge for Humankind. To say “multiplication is repeated addition” is like saying “differentiation is division”; for both boil down to saying that the infinite is no big deal, little different from the finite. That’s not just a lie, it is to deny two thousand years of human progress.

16 comments:

jbdyer said...

I've thought about this topic deeply myself -- I have two blogs posts addressing your columns directly here and here, and last semester at a university I taught Mathematics for Elementary Educators, where I had them read your articles and included as one of my test questions to write a word problem where multiplication-as-repeated-addition is a bad way to think of the problem.

I don't think anything in the post above is wrong, but a few orthogonal comments:

1. It is possible (via an axiomization of Tarski) to start with the real numbers rather than the natural numbers. It's the mathematical equivalent of the Davydov curriculum. So I take any statement that an operation is absolutely defined one way with a grain of salt.

2. A lot of people arguing against you seemed to have a special notion of what "is" is. I consider the standpoint essentially philosophical (my second blog post has more on this).

3. Using a category theory approach addition and multiplication are clearly very different, but I don't know if you're capable of explaining it at an elementary level that educators could understand (I have tried to write such a post and failed).

4. That the recursive principle was a grand discovery reminds me that even that one can keep adding to get larger numbers can be elusive; some cultures never discovered this, and I have students -- high school -- who have argued there was, indeed, some largest number. (It was easy to clear up, but they clearly had this misconception prior to my bringing it up.)

profkeithdevlin said...

Indeed there are several ways to define multiplication. In my above column I focus on the standard definition in Peano arithmetic, taking as my text the current Wikipedia description.

The Peano arithmetic definition was the starting point for the most common argument with any substance that was presented to me as purportedly showing that multiplication *is* repeated addition, but in fact what those arguments really showed was that many people do not understand the Recursion Principle and its role in mathematics. And that of course was the real focus of my column.

I discussed the Davydov approach to arithmetic instruction (which I like) in another column http://www.maa.org/devlin/devlin_01_09.html.

What worries me from a K-8 educational perspective is not the formal definitions, which were developed for mathematical, not education purposes, but that children are led to develop an intuitive conception of the mental operation of multiplication as being "just repeated addition", when in fact it is something very different.

What the mental concept of multiplication is (or should be) was the focus of another of my columns, earlier this year: http://www.maa.org/devlin/devlin_01_11.html.

Jason's blogs that he refers to provide some nice illustrations of these issues from the perspective of someone with far more active experience in K-8 education than I have. My expertise is on the mathematics itself, not how it is taught (as I have stressed to the point of likely boring my readers).

hilbertthm90 said...

I agree with jbdyer. The disagreement is a philosophical one that has to do with the use of the word "is". I address why multiplication is repeated addition here. Since it all still applies I'm not sure how to comment (by commenting I risk having people not read the post which is a much more thorough explanation...).

Here is the main problem. You define a function M that you want to call multiplication. Go ahead. No one is going to stop you. Let me define a function. I'll call it M : NxN -> N. My function is M(n,m)=5. I'll call it multiplication. Why shouldn't I do that? Remember, your explanation can't involve repeated addition (or some a priori notion of multiplication that you want your function to match).

If you say your M "is" by definition multiplication, then sure it isn't repeated addition, but that isn't what anyone means by multiplication. To take your own concrete example suppose you have a 5 cm elastic band and you stretch it to 10 cm. The new length is two times the old length.

You have to explain what you mean by "is two times the old length". What everyone (except apparently you) means by this is that if you add the old length to itself you get the new length. Your function M is meaningless in reality if you don't relate it somehow.

This is why you are backwards. You think that M just randomly happens to agree with repeated addition, when in fact the opposite is true. The useful notion "is" repeated addition (that's what I mean by "is") and it just happens to agree with your function and that's why we *define* your function to be multiplication and not the thing that returns 5 for every input.

profkeithdevlin said...

I don't think M randomly happens to agree with repeated addition. That outcome is transparentlybuilt into the recursive definition of M. (Hence my rhetorical irony.) But until you appeal to the recursion principle, you don't have a function. Repeating addition does not yield a function. It is an idea, not a sound definition. An idea that does not work in terms of defining a function.

This approach is indeed "backwards" from a historical perspective, and perhaps a cognitive one. But this is very common in mathematics. We discover that our intuitions are unreliable, and work around that problem by turning things around, so what was a conclusion now becomes the starting point.

BTW, this is not just my view; I'm just relaying the universally accepted mathematical definitions. As i mentioned in my original posting above, the infinite is at play here, and that is a tricky thing to handle correctly.

christopherdanielson said...

I'm ready to hear a principled argument that teaching multiplication as repeated addition is harmful. The case Prof. Devlin (and others) make seems to be based on what multiplication *is* in the sense of what it is defined to be in higher mathematics, and this definition is dependent on needing it to be robust enough to build other mathematics on top of. I get all of that. And I dig it.

But when we write curriculum, I'm not convinced that mathematical formalism trumps intuition and experience every time. Yet that seems to be the argument, right? We shouldn't work with a repeated addition interpretation of multiplication because that's not good enough for formalist mathematics.

So let's accept that premise. Then it's incumbent on the arguer to offer the replacement. And I understand that the replacement is "multiplication as one of two operations on real numbers (together with addition". Fair enough.

But then how do novices find products?

I asked via Twitter and the reply was, "by learning to multiply". This is tautological, isn't it (or maybe just recursive)? How should students learn to multiply? By learning to multiply.

So maybe Twitter is the wrong medium. Do I have it correct that children are to take the table of multiplication values as defined? That 3x4=12 because it is defined that way (rather than because 3 groups of 4 is 12)?

And then multidigit multiplication algorithms are (nearly) all dependent on the distributive property of multiplication over addition. Again, children are to accept that property as part of the definition of multiplication (as in, "we seek an operation such that a(b+c)=ab+ac, and we will call it multiplication"), rather than as a consequence of the definition of multiplication (as in, "since 12x5 is 12 fives, we can use two products we already know: 10 fives + 2 fives")? Do I have this right?

profkeithdevlin said...

If you really want to see the evidence on the problems caused by teaching multiplication as repeated addition, then be prepared for a long haul, for there is a lot of it. And it is by no means restricted to the fact that it is mathematically wrong. Much of it is based on pedagogic considerations. I cite some of the literature in my columns of September 2008 (www.maa.org/devlin/devlin_09_08.html) and January 2011 (www.maa.org/devlin/devlin_01_11.html)

The best way I know for a person to be able to multiply pairs of natural numbers efficiently in their head, or with paper and pencil, is to learn the basic multiplication facts (the multiplication tables in yesterday’s vernacular) and then use the standard Hindu-Arabic algorithms. So I answer “yes” when you ask “Do I have it correct that children are to take the table of multiplication values as defined?”

But that does not mean you can’t help them to understand where those table values come from. Indeed, I think you should. You write “That 3x4=12 because it is defined that way (rather than because 3 groups of 4 is 12)?” And there in your own parentheses is the answer to your own question. Your example is in terms of the mental concept of multiplication, not repeated addition! Taking 3 groups of 4 corresponds to multiplication. It is not the only operation that does; multiplication is multi-faceted (unlike addition). What 3 groups of 4 does not correspond to is repeated addition, though with such a simple example it is easy to confuse the two. See the Nunes-Bryant book I recommend in my September 2008 column for details on all of this.

Mike Wills said...

Hi Keith,

I am not sure if I ever really thought of multiplication as repeated addition. Certainly, once the concept of a ring was introduced me, I understood that the two concepts were distinct. Mind you, I can at least loosely be described as a mathematician so I suppose that it is not surprising that I am in agreement with you.

Some years ago, I taught a course in real analysis out of Rudin's `Principles of Mathematical Analysis'. Rudin starts off by assuming that Q exists and proceeds to construct R from there. I personally find this approach a bit unsatisfying; after all, where does Q come from? I'd live with it if my department had any course which really deals with the logical foundations of mathematics, but it doesn't. To fill in the gap, I wrote up a (long) handout on set theory and the constructions of various number systems.

Pedagogically, this may not have been a great plan. Certainly, Halmos turned in his grave. However, I at least learned a fair amount, although in some respects I feel that my understanding of what a number actually is has diminished.

Before you posted this column, my set theory handout glossed over the recursion principle. In fact, it still does, but at least I now state a version of said principle and include a somewhat vague explanation of why it is needed.

The handout is available on my website:
http://faculty.weber.edu/mwills/teaching/Weber/2009/Autumn/Math4210/Set%20Theory.pdf

It should be pointed out that any opinions given in the handout and in this post are my own, and do not necessarily reflect the views of my university nor my department.

Best
Mike

profkeithdevlin said...

Mike,

Thanks for writing. I agree with you that starting with Q to build R in unsatisfying. Especially since the real number system is grounded in our real world experiences every bit as much as the natural numbers -- analog measurement for the former, counting discrete collections for the latter. The Davydov (school) curriculum, which I described in my January 2009 Devlin's Angle, takes the real number system (along with the intuitions it builds upon) as the starting point and the natural numbers arise along the way as a special class of real numbers. See http://www.maa.org/devlin/devlin_01_09.html

James Swenson said...

Prof. Devlin --

You are making a common error: you're making absolute statements of fact without first agreeing with your audience on a set of axioms.

Mathematicians are easily tempted to do this, because we are accustomed to working in a context where certainty is available. However, it's not tenable in a discussion of mathematics education.

You seem to take the position that a student first learning to multiply should be prohibited from drawing connections to their prior knowledge of addition. I regard that as abusive. However, neither of us can honestly claim that he is certainly correct.

profkeithdevlin said...

James, my column is about how multiplication is defined in Peano arithmetic. That is what the title says! It doesn't get any clearer than that in terms of what the axioms are. In an italicized aside I emphasized that I was not focusing on mathematics education, where the issues are very different. You are attacking a straw man. I have expressed my views on mathematics education in other columns, and in none of them will you find that "abusive" claim you ascribe to me. On the contrary, you will find many statements about the importance of students connecting what they learn.

Anonymous said...

In what sense is recursion NOT to be understood as repeated application? Should we think of stretching rubber instead? The type of recursion used for Peano Arithmetic can be replaced by a simple bounded loop (see Hosfstader's BlooP (versus Floop) formulation for example.)
It's about as repeated as it gets.

Furthermore, regarding a prior comment of yours,
if the real number system is "grounded" in our experience, then why were Greeks were surprised at incommensurability? Why did Kronecker object to the very notion of the "most general real number" and why does he have professional (mathematician) sympathizers to this day? (See http://math.nyu.edu/faculty/edwardsd/athens.pdf) What is Gregory Chaitin getting at when he writes about "How real are real numbers?" (http://www.umcs.maine.edu/~chaitin/olympia.pdf) One could go on and on - the point is that our experience does not inevitably lead to the modern conception of "real number" at all - there are constructivist and finitist alternatives perfectly consonant with our experience of the real world (as opposed to the somewhat unreal real numbers.)

profkeithdevlin said...

Anonymous: Your first question is the heart of my column. Repeated addition is FINITE; you can repeat only a finite (albeit arbitrary) number of times. The Recursion Principle essentially extends that to the infinite. That is a highly nontrivial step. Not everything you can do for the finite can be done for the infinite. The infinite is not just a continuation of the finite. Recursion is not just “repeat infinitely many times.” It’s something very different. It requires axiomatic mathematics to move from the finite into the infinite.

Stretching is different; it is continuous, not repetitive. Your comment “as repeated as it gets” confuses repetition with recursion.

The problem the Greeks encountered, which you refer to, was that their two grounded notions of what-we-call-number did not hang together. They discovered that the numbers you obtain from counting (what we call natural numbers and positive rationals) were not adequate to capture the quantities that correspond to mensuration (what we call positive real numbers). It was precisely BECAUSE notions of length and volume are grounded in experience that their discovery came as such a shock. For many centuries after the ancient Greeks, mathematicians viewed quantities (measurement of length, etc.) as distinct from numbers. Only with the development of the real number system in the 19th century were the two finally reconciled.

It’s not that mensuration leads by some form of predestined logical process to the real numbers; rather the real numbers can be GROUNDED in our experiences (as are the natural numbers). There are, as you note, other notions we can develop. But that is a totally separate issue from the means available to a teacher to develop mathematical concepts by starting with, and drawing on, human intuitions.

anonymous said...

I'm not confused -- mutiplication of integers is primitive recursive - it can be defined via a bounded loop construct. (Again, look up Hofstadter's Bloop & Floop - multiplication is primitive recursive and only needs the power of Bloop or something equi-powerful, in order to defined in terms of addition & looping.) Of course you can use something strictly more powerful but it's not necessary. Peano wasn't forced to use general recursion because the nature of multiplication of integers required that much power. A bounded loop means repeat so-and-so (a finite - though variable) number of times. That was the point -- a bounded loop *is* simple repetition. And that's all that's needed for *this* particular job.

profkeithdevlin said...

No, what you are talking about is how to COMPUTE the product of any two natural numbers, which is not the same as DEFINING a function from NxN to N. The latter is of necessity an infinitary object, and to get those you need existence axioms.

Again, I should stress that this entire thread is about "How multiplication is really defined in Peano arithmetic," as the title states. It's not about how to teach multiplication, nor is it about how to compute it. Rather, my motivation is that, having taught this material to math majors for many years, I have seen how many fail to grasp just how crucial the Recursion Principle is. Some of those who have contributed to this thread, while clearly knowing a fair amount of advanced mathematics, seem to be unaware of its subtlety, and indeed it took a long time before the entire mathematical community realized the underlying difficulties and figured it out in the late 19th and early 20th centuries. (See the earlier comment by Mike.)

profkeithdevlin said...

Recent comments submitted (but not yet published) have attempted to move the discussion off topic to argue viewpoints on (1) how to teach K-8 mathematics and (2) the role and desirability of formalism and rigor in mathematics. Since both of those issues have already been raised by responses already published, I have asked the editor (it's not me) to close the comments thread. Thanks to all who have responded.

Bill Dubuque said...

An excellent reference on this and related matters is the award-winning exposition: On Mathematical Induction, by Leon Henkin, American Mathematical Monthly, Vol. 67, No. 4 (Apr., 1960), pp. 323-338.