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:
RecursionSee “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 “recursion” to 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.
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.