Stanley Tennenbaum was an itinerant mathematician with, for much of his adult life, no fixed address and no permanent source of income. Sometimes he slept on park benches. He didn’t have a lot of teeth.
But if you were involved with mathematics in the second half of the twentieth century, sooner or later you were going to cross paths with Stanley, probably near the coffee machine in a math department. He’d proudly show you the little book he carried in his breast pocket, with the list of people to whom he owed money. Then he’d teach you something, or he’d tell you a good story.
Stanley had little tolerance for convention. His one permanent job, at the University of Rochester, came to an abrupt end during a faculty meeting where he spit on the shoes of the University president and walked out. Surely the same personality trait had something to do with his departure from the University of Chicago without a Ph.D., though the paper he wrote there (at age 22) has acquired fame and influence far beyond many of the doctoral theses of his more conventionally successful classmates. I’d like to tell you a little about that paper and what I think it means for the foundations of mathematics.
I write as one who believes (like most mathematicians) that the system of natural numbers (including the operations of addition and multiplication) exists in an objective sense. By that I mean precisely this: Statements about the set of natural numbers (such as “Every natural number is the sum of four squares”) have objective meanings; they are not just strings of words. I take it that a thing exists if one can speak meaningfully about its properties. The facts that every natural number is a sum of four squares, that every number can be factored into primes, and that an odd prime number is a sum of two squares if and only if it leaves a remainder of 1 when divided by 4, are all properties of the system of natural numbers. Because it has these properties, the natural number system exists.
It would be nice to give a succinct definition of the system of natural numbers. That turns out to be quite impossible. You can try writing down a list of axioms (Zero is a number; every number has a successor; no two numbers have the same successor; addition is commutative and associative and so forth), but it turns out that no matter what axioms you write down, there are always an infinite number of mathematical structures that satisfy those axioms but are not the natural numbers. Those structures — the ones that masquerade as the natural numbers by satisfying all the standard axioms, even though they behave very differently — are called nonstandard models of arithmetic.
This means, in effect, that there’s no way to uniquely specify the natural numbers. (Note to experts: You can of course uniquely specify the natural numbers if you’re willing to resort to a second-order theory, but that’s entirely unsatisfactory for reasons I’ve blogged about before.) Elsewhere, I’ve taken this remarkable fact as an indication of the natural numbers’ complexity — not only do they have no short description; they have no finite description at all.
Okay, then. What exactly are these non-standard models of arithmetic? What do they look like? What’s an example of a system that satisfies all the axioms of arithmetic but still isn’t ordinary arithmetic?
That’s where Tennebaum’s Theorem comes in. What Stanley proved (and of course I’m paraphrasing a bit here, because this is a nontechnical forum) is that in any nonstandard model of arithmetic, the rules of addition and multiplication are so complicated that no computer can be programmed to carry them out. In other words, you and I, whose brains are computers, have no hope of really understanding those addition and multiplication rules.
It’s been suggested that Tennenbaum’s Theorem creates a back door route to giving a precise and compact definition of the natural numbers. Namely: First we write down our axioms. Then we say, “Yes, I realize these axioms don’t nail down what I’m talking about — there are many different systems of `arithmetic’ that satisfy these axioms. But the one I have in mind is the one and only system of arithmetic that’s actually computable. That’s the natural numbers.”
Cute. But here’s why I’m quite sure it doesn’t work.
Here’s the problem. What does it mean to say that a computer can be programmed to add and multiply? It means that if I give that computer an arithmetic problem, it will return an answer in a finite amount of time. What does “in a finite amount of time” mean? It means “in a number of steps that corresponds to some natural number”. And what does that mean? Well, since my goal is to describe the natural numbers, I can’t just assume you already know what the natural numbers are. So it seems like my attempt at a description has come full circle right back to the beginning. Or to put this more succinctly, my attempt has failed.
I’ve been meaning to blog about this for ages, but have only just just discovered this paper by the philosophers Tim Button and Peter Smith that makes essentially the same point. They envision an interlocutor named Thoralf who is discomfited by the existence of non-standard models and worries that he has no idea which of these is the “true” set of natural numbers. We respond that it’s the one and only model where arithmetic problems can be solved by computation. Thoralf asks “What’s a computation?”. We reply that “A computation is a finite set of steps….”, whereupon Thoralf interrupts to ask “What does finite mean?”. We say “Something is finite if it can be measured by a standard natural number”. Thoralf asks: “And what are the standard natural numbers?”. And round and round we go.
Button and Smith conclude that “philosophical problems which are supposedly generated by mathematical results can rarely be tackled by offering more mathematics.”
It seems to me, then, that our only hope for picking out the honest natural numbers from among a sea of impostors is a direct appeal to intuition. Fortunately, almost all of us have that intuition. We’ve known what numbers are since we were three. We know what it means to say that every number is a sum of four squares. (Not all of us know how to prove this, but that’s beside the point. The point is that we all know what it means.)
So I contend that 1) the natural numbers exist because we can make meaningful statements about their properties, and that’s what existence consists of, and 2) the natural numbers are unfathomably complicated in the sense that there is no hope of pinning them down by any sort of description, even if we allow ourselves to incorporate sophisticated ideas like Tennenbaum’s into our description.
As many of you know, I’ve argued more than once (some of you might say more than necessary) that the existence of an unfathomably complex structure that was neither designed nor the product of evolution is a definitive counterexample both to the “intelligent design” argument that says a complex structure needs a designer and to Richard Dawkins’s position that all complexity is a product of evolution. It also settles (for me) the question of why the physical Universe exists — once you’ve explained the existence of something as complex as the natural numbers, explaining the existence of something as relatively simple as the Universe becomes a mere exercise.
Tennenbaum’s Theorem, on the face of it, presents a challenge to this way of thinking, but it is, I think, ultimately an unsuccessful challenge. It’s still a beautiful theorem, though. And Stanley was a beautiful guy. Sometime soon I’ll tell you more about him.