A recursive tale

When the natural numbers are introduced from first principles, there’s a sort of standard narrative given for how addition, multiplication, and exponentiation work. Some of my mathier readers will probably recognize it instantly when I present it.

In my considered opinion, this narrative is bullshit.

It’s still a nice story, though. Very  engaging, even very instructive in some ways. So here’s what I’ll do: I’ll tell you the story. At the end of the story, I’ll tell you why it’s bullshit.

The line of succession

One useful property of the natural numbers is that you can always find a bigger one. In fact, there’s a method for doing so: take the number itself and tack it onto the set.

  • Taking 0 = {}, and moving 0 inside the set, gives {0} or 1.
  • Taking 6 = {0,1,2,3,4,5}, and putting 6 inside the set, gives {0,1,2,3,4,5,6} or 7.
  • Taking 4343 = {0,1,2,….,4342}, and putting 4343 inside the set, gives {0,1,2,….,4343} or 4344.

The number you get by doing this to n is called the successor of n. The notation for the successor operation isn’t really standardized, so we’ll just pick one: next(n) means the successor of n.

This actually reflects the structure of finite sets: no matter how big a finite set you have, you can get a bigger one just by finding something not in the set, and tacking it on. Even better, the cardinality (size) of that bigger set will be next(|S|), where S is the smaller set and |S| is its cardinality.

A minor addition

This really simple operation of succession is actually enough to define all the other operations I have in mind for today. This is because of one more neat little fact: because of how they’re built, every natural number except 0 is the successor of something. If I start at 0, and apply next to it enough times, I can reach any natural number I like.

With that in mind, let’s look at how we add numbers. Suppose I ask you something like, “What’s two plus three?”
If you are in the (quite excellent) habit of giving straight answers to these sorts of questions, you’ll probably say, “Five.”
And suppose I ask you, “How did you figure that out?”
Well, probably you didn’t figure it out, at least not right at that moment—you only remembered the answer. But if you had temporarily forgotten, you could have figured it out, by thinking to yourself something along the lines of, “Two—next comes three—then four—then five.”

What’s going on here? You’re applying the successor repeatedly. Somehow you’re translating “2 + 3” to “next(next(next(2))).”

Now imagine I’m an idiot (“This should be easy,” I hear my friends saying) trying to add two numbers together. I don’t really know what numbers are, but I do have this next operation at hand, and I know I have to apply it multiple times. How do I know when to stop? We can’t say, “after you have three of them,” because if I knew what that meant I wouldn’t need directions to begin with.

It often helps, when you’re trying to solve a complicated problem, to solve a simpler one first. In this case, let’s stop asking “How do you add three?” and instead ask, “How do you add zero?”

Well, that’s easy. Just don’t do anything. Two plus zero is two. Ten plus zero is ten. Twelve plus zero is twelve. n plus zero is n.

“How do you add one?”

Just take a successor. 2+1 is next(2), or 3. 12+1 is next(12), or 13.

“How do you add two?”

This is the first hard one, but there’s an answer: add one, then take the successor. 2+2 is next(2+1), or 4. 12+2 is next(12+1), or 14.

“How do you add three?”

Once you’ve figured out two, three is easy. Add two, then take the successor. 2+3 is next(2+2), or 5. 12+3 is next(12+2), or 15.

All of this adds up (sorry) to the recursive definition of addition:

  • n+0 = n.
  • n+next(m) = next(n+m).

Recursive means that we figure out the sum of two numbers by first finding the sum of two smaller numbers, then messing with that somehow to get the answer. For example, to find 2+3, you first must know 2+2. And in order to know 2+2, you must know 2+1. And in order to know 2+1, you must know 2+0, which is just 2. Because of the way the natural numbers are constructed, this process will always end.

This is what working out an addition directly from this definition looks like:

2+3 = 2+next(2)
    = next(2+2)
    = next(2+next(1))
    = next(next(2+1))
    = next(next(2+next(0))))
    = next(next(next(2+0)))
    = next(next(next(2)))
    = next(next(3))
    = next(4)
    = 5

Yeah…. there’s a reason we memorize answers to this sort of thing. I don’t recommend you do this every time you want to add two numbers together.

But you could, if you wanted to or had to for some reason. That’s good to know.

Be fruitful and multiply

We can apply basically the same recursion trick to get multiplication out of addition:

  • n⋅0 = 0
  • nnext(m) = n + (nm)

Or, rewritten in English:

  • If you want n times zero, it’s just zero.
  • If you want n times next(m), first find n times m. Then add it to n, and there’s your answer.

This gives us multiplication in terms of addition. And we have addition in terms of succession. So, in some sense, multiplication is really just succession repeated a whole, whole lot of times.

Just for fun, let’s figure out a simple multiplication problem.

2⋅2 = 2⋅next(1)
    = 2+(2⋅1)
    = 2+(2⋅next(0))
    = 2+(2+(2⋅0))
    = 2+(2+0)
    = 2+2
    = 4

(A sidenote: Some might say I’m taking a shortcut by jumping directly from 2+2 to 4, without actually applying the recursive definition. To which I say: I already demonstrated that 2+2 is 4, as an intermediate step in the last section! This sort of shortcut isn’t ‘cheating’—if anything, it’s a good habit.)

Exponential angst

Even the mighty exponential can be encompassed by this trick. In fact, the definition of exponentiation looks a lot like the definition of multiplication:

  • n0 = 1
  • nnext(m) = n⋅(nm)

I’m not even going to try and work out an example of this one. I guess something small, like 22, wouldn’t be so bad…. but anything much larger would quickly get unwieldy.

Again, this is exponentiation in terms of multiplication. And multiplication is defined in terms of addition. And addition is defined in terms of succession. You see where this is going.

…and beyond

At this point we have

  • addition as a recursive operation built on succession.
  • multiplication as a recursive operation built on addition.
  • exponentiation as a recursive operation built on multiplication.

Looking at the list above, I don’t see any obvious reason to stop there. What about a recursive operation built on exponentiation? It’s obvious how you would define such a creature: choose a symbol like ⇑ and then use a definition like this.

  • n⇑0 = 1
  • nnext(m) = nnm

This operation is sometimes called tetration. And, as you might suspect, it grows a bit faster than mere exponentiation. Here’s a short table of identities:

  • 3⇑1 = 31 = 3
  • 3⇑2 = 33 = 27
  • 3⇑3 = 327 = 7,625,597,484,987
  • 3⇑4 = 37,625,597,484,987 = way too big

Yikes, that is pretty fast.

But not quite as fast as pentation, or recursive tetration. I’ll leave writing the definition as an exercise. For an idea of how quickly it grows, consider that 3 pentated to 3 is the same thing as 3⇑7,625,597,484,987. And still there’s no reason we have to stop: we can just as easily define hexation to be repeated pentation, and so on. And yet all of these monsters are ultimately reducible to the dinky little next operator.

Why this is bullshit

Remember how we defined the natural numbers? We talked about sets as collections of objects, and how they have this property called “cardinality” or “size” that they can somehow share, and how natural numbers are a tool for capturing that property. The natural numbers are what they are because they reflect the structure of finite sets.

Remember how we defined the greater-than and less-than operations on the natural numbers? We talked about sets, and how they if they don’t share a cardinality, then one set can either be “too big” to fit inside the other, or “too small” to fit the other one inside. The natural numbers have the order they do because that order reflects the structure of finite sets.

Remember how we just defined addition? We invented a completely arbitrary recursive operation, defined in terms of another arbitrary operation called next. And then, to define multiplication, we did the same thing again, only in terms of the arbitrary + instead of directly in terms of the arbitrary next. And then we continued this game, endlessly tacking recursion on recursion with no end or goal in sight.

Does this strike you as kind of lame?

I mean, it works, I guess. It agrees with the sort of arithmetic we’ve all been doing since we were in primary school. But it doesn’t actually explain anything. Why these particular operations? Why not some others, just as easy (and possibly easier) to define? People don’t add and multiply numbers purely as a formal game (well, most don’t), they do it because they have questions to answer—and many of those questions are about collections of objects, a.k.a. sets!

So my goal in the next couple of posts will be to develop the arithmetic of natural numbers in another way—one that shows how it relates to the structure of finite sets. Stay tuned.


8 responses to “A recursive tale

  1. “Two plus zero is zero.”

  2. I look forward to your bullshit-free definitions of arithmetic! I’m really enjoying your blog so far.

    • Thanks! Do you mind if I ask how you found it? So far most of my (very few) readers have showed up through the xkcd forums, but I’ve noticed a few referrals from elsewhere too.

  3. sounds exciting. when you get the next post, or at some point, you should tell the math club list 😀

    • I’m mildly shy about self-promotion, especially where none of the students in the UMB math department really know who I am anymore, but if you think they’ll be interested you can always post a link.

  4. Pingback: Putting sets together | Irrational Inquiries

  5. Pingback: Commutativity and all that | Irrational Inquiries

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 )

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