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.
The assumptions you leave unjustified towards the end :
“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” You seem to assume that this hope is not in vain. I disagree. Intuition is clearly fallible, and has no hope of picking out the honest N. In fact, most potential-true-N’s look much like each other to the intuitive beings I’ve met.
“unfathomably complex structure that was neither designed nor the product of evolution”
It’s fairly clear that N is not the product of evolution, but I haven’t seen any evidence presented that it wasn’t designed.
Have you read my blog post arguing that your idea, in absentia a “cosmic mathematician” to decide which bits of math become “real”, implies that everything (at least, everything imaginable and many not) must exist?
Anyway, your post here is very nice :-)
I agree with Mike, it would be nice to see evidence on why it wasn’t designed.
Mike H. If it could have been designed, why could it not have evolved? Allowing the possibility of design surely allows the possibility of an alternative design.
I think this has been reaised before, but your definition of exist as being able to have meaningful statements made about it is not quite the same as people usually think of existing.
Does a character in a novel exist? In one way it does, but in the usual way of thinking it does not.
“…the existence of an unfathomably complex structure that was neither designed … is a definitive counterexample both to the “intelligent design” argument that says a complex structure needs a designer”
Aren’t you begging the question by first stating it is not designed then saying that since it’s not designed yet is unfathomably complex it does not require a designer? I agree that it could not have evolved as evolution itself is a finite process. Yet in most spiritual systems, and certainly in mine, the supernatural Creator is as unfathomable as the natural numbers (if not more so), and is therefore the only logical source of logic itself. Like you say about the natural numbers, most people have an intuition about the supernatural, even if they can never fully fathom it.
“I take it that a thing exists if one can speak meaningfully about its properties.”
Out of curiosity, do you apply this statement to infinity?
Non-standard models exist in the mathematical sense, whatever that sense might imply. (That implication is the bone of contention.) I’d say you just made a very cogent argument that it doesn’t actually imply much.
Let’s look at a concrete case. Let’s look at all the creeping creatures that creep upon the ground. These are pretty complex but there were none to be found 3B years ago. Just like Dawkins says. Does saying ‘ah but the idea, the logic of them, the algorithm for their reproduction all this existed in its platonic perfection even then’ actaully have a meaning? Well it would if there were a thinking entity to think the thoughts. And whoops there we go back to St Anselm. It’s easier, more like Occam, to just say conclude mathematical ‘existence’ is an abstract idea in our minds and we cannot conclude from that very much.
@Harold, we’re talking about the natural numbers here – not our understanding of them, but the numbers themselves. Evolved?? You are positing some “ecosystem” of platonic mathematical entities implicit in the laws of logic and mathematics that undergird the universe, reproducing, competing and dying. Occam’s razor here rejects the idea that mathematics (understood platonically) “evolved”. You must choose between it being designed, it just being in and of itself, or actually not existing at all.
… although, of course, if you posit that mathematical entities all exist in and of themselves, that there’s no “cosmic mathematician” to decide which become real and which don’t, then of course such an ecosystem does in fact exist after all. Steve must agree with Harold’s proposition, IMHO.
@KenB this, of course, begs the question of why the universe exists and why (at least bits of it) behaves mathematical laws. If there was no mathematics 13B years ago (because there were no minds), why does the universe seem to have acted as if there was?
@Mike H: I readily concede I have no idea why the universe exists. I will take my queue here from Richard Feynman: it’s OK to say I don’t know. Sometimes we shouldn’t claim to know. I’ll let Bob Murphy get off at the Book of Genesis, and Steve get off at the Book of Dedekind, but I’ll stay on the trail for now.
“I take it that a thing exists if one can speak meaningfully about its properties.”
Dan asks about infinity. I can assure Dan Steve does mean infinity, lots of infinities. So let me ask about that greater than which nothing can be conceived.
A defining charactersitic of the medieval mind was the belief that if we can talk about it, it’s real. Steve’s idea is a refinement:
if we can talk about it with a certain set of formal rules (that excludes second order rules), then it exists.
@KenB :-)
Vaguely Wittgensteinian? In Tractatus Logico-Philosophicus (1921), Wittgenstein attempts to develop a language structure that would facilitate reasoning (and impede nonsense). Rejecting the conventional metaphysics that starts with focusing on objects, Wittgenstein focuses on facts (“die tatsache”) – that is, an actual or possible state of affairs (“bestehen von sachverhalten”). We cannot meaningfully discuss states of affair that are neither actual nor possible; whereof one cannot speak, one must be silent. (“Wovon man nicht sprechen kann, darüber muß man schweigen.”)
Wittgenstein and Tennenbaum seem like two peas in a pod. They both seem like eccentric geniuses that, for long stretches of their lives, were not employed in their field of expertise and often had difficulty getting along with others. For what it’s worth, Frank Ramsey was a Wittgenstein fan, writing an early review of Tractatus and eventually luring him to Cambridge. Initially Wittgenstein was not permitted to teach because he never completed an undergraduate degree. But a faculty committee awarded him a PhD based on the Tractatus.
I really enjoy Landsburg’s efforts to translate complex ideas into layman’s terms. And not merely to translate, but to convey the ideas in ways that a layman can appreciate some of the excitement in the ideas – the challenges, the conundrums, the contradictions.
And I remain on my Wittgensteinian quest to simplify ideas still further. Maybe too far. When I read, “the natural numbers exist because we can make meaningful statements about their properties, and that’s what existence consists of,” my ears (eyes?) perk up. Do we lose any meaning if I translate Landsburg’s post as follows?
I write as one who believes (like most mathematicians) that the system of natural numbers (including the operations of addition and multiplication) has properties we can discuss meaningfully. For example, we can discuss meaningfully 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….
So I contend that 1) we can make meaningful statements about the properties of natural numbers, and 2) we have no hope of pinning natural numbers 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 something with an unfathomably complex structure that was neither designed nor the product of evolution – something such as natural numbers – serves as 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 we can make meaningful statements about the physical Universe — once you’ve explained our ability to make meaningful statements about something as complex as the natural numbers, explaining our ability to make meaningful statements about something as relatively simple as the Universe becomes a mere exercise.
nobody.really: Your paraphrase seems exactly right.
Very sorry; it won’t happen again.
This reflects my understanding of Landsburg’s view as well. Shakespeare said, “What must be shall be.” Landsburg says, in essence, “What can be shall be – and, in fact, already is.”
For what it’s worth, I read that a branch of Hindu argues that Brahman (?) experiences not only the life we experience, but experiences every permutation of every possible life that anyone could possibly experience. In this sense, nothing we do is ultimately good or bad because we will ultimately commit every good and bad act that was ever within our possibility to commit. If I experience myself committing murder, what of it? It was merely one more permutation of behaviors I was destined to engage in.
So that Lúthien for a time should be. I mean, duh.
Since snark is a topic today, I liked this comment from Silas Barta to Steve, during an exuberantly snarky debate on one of those linked threads, referring to the Dawkins claim. Silas dismantles Steve’s argument, grinds it to bits, and dances on its grave: “In short, you took a statement referring to non-Platonic domains, and masterfully showed it to be false in Platonic domains.”
you and I, whose brains are computers, have no hope of really understanding those addition and multiplication rules.
Erk. That dependent clause brought me up short. Fortunately, I don’t think the reasoning or relevance of your post depends on it, but I call it out anyway.
There is very good evidence that our brains (and quite probably all brains of sentient beings) are NOT computers. At least, not computers in any sort of Turing or Von Neuman sense, which is what I think you’re referring to as you discuss computability.
It’s true that brain-as-computer analogies were quite popular in the latter half of the last century and these models gave us language to talk about brain function that we didn’t have before. But by the 1990s it was quite clear that brain-as-computer models were just as wrong as past centuries’ brain-as-water-pipes or brain-as-engine models.
I think that it’s probably still true that we cannot understand the math rules you describe, but I can’t prove it. At least, not yet. I have some hope that the upheavals of the past decade in discovering how signals are propagated in the brain will lend themselves to modeling in the coming decade and from those new models we might be able to say something about the computing power of the (human) brain.
“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”
Mike H at once, right, pounces on this: intuition is a thin reed with which to stake such a mighty claim.
I would add only this: ignore, for the moment, the question of “design.” What evidence do we have that the “intuitive” obviousness of the natural numbers is not simply an emergent phenomenon of the particular way in which our computational fat-sacks (commonly and somewhat optimistically known as the “human brain”) process their inputs? Many if not most other things we consider intuitive are, after all, precisely that.
(Arguing against myself, I tend to think that the fact that binary computers, you know, work is at least a strong sign that we’ve got our hands on something a little more solid than our shadows on the cave wall. But at a minimum I’d like to find out what some ETs think about arithmetic before we consider the question settled.)
Alan Wexelblat: Point well taken.
I’m still not sure I like the usage of the word “exists” here. Numbers are still quite different from the sorts of things we normally talk about existing: they have no physical location, nor do they have _specific_ identity (i.e. this “1” is different from this “1”: there is simply the concept of 1).
But I certainly agree that existing objects and numbers seem to properly belong in the same larger set of things. And if we want to call that set “things that exist” there’s no underlying reason why that’s wrong, it’s just going to be somewhat confusing given the sorts of things we normally mean when we talk about them existing. But that’s a quibble about the clearest strategy for common usage, not a substantive objection.
I think the strongest argument against the idea that natural numbers were “designed” is simply that I don’t think those would make this claim can in any way even describe what that actually MEANS: which is precisely what’s necessary to even float something as a possibility. If you can’t explain what it is that’s going on when a particular something is designed, then you really aren’t saying much of anything. If you can explain what things would be like if there were no natural numbers, and then what sort of thing was done to make there be natural numbers, then saying that they were designed is about as meaningful as saying that you put a dog leash on “justice” and took it for a walk in the park.
This is also why people who “explain” the existence of the universe by appealing to god often end up saying nothing more interesting than “an unknown, possibly unknowable, event occurred and I don’t know how.” Giving that sort of explanation-free explanation a name like “God” doesn’t make it any more interesting or meaningful.
Doctor Memory: ” intuition is a thin reed with which to stake such a mighty claim.”
Indeed. And there are even problems with which intuition. Take some unprovable conjecture in arithmetic. The only one I can think of off the top of my head is Goldbachs’s conjecture. Imagine someone proves it is unprovable. Would it be meaningful to say it’s true? Whose intuition would we trust here?
More to the point, where did that intuition come from? From the evolution by natural selection of that made-of-meat information processor between your ears. So I don’t see a good case for privileging an evolved artifact — intuition.
Kevin L: To say that the natural numbers and the rules of logic were designed is to say that they could have been designed differently. Do you believe this?
I disagree with “the natural numbers are unfathomably complicated in the sense that there is no hope of pinning them down by any sort of description”. The natural numbers do have that 2nd-order logic definition, and various other straightforward definitions. Those definitions serve well enough for mathematics, and are superior to just using our intuition.
Martin-2: ” To say that the natural numbers and the rules of logic were designed is to say that they could have been designed differently. Do you believe this?”
A nice point, but in fact there IS room for choice here, if you imagine a ‘designer’ and one true world. Take an unprovable conjecture of arithmetic (unprovable in PA or whatever system you choose). The designer can ‘choose’ to have it true or false, and then move on to the next such conjecture. This is part of what’s unwieldy with Steve’s idea: there are a lot of branch points! How does our intuition deal with it all?
Doctor Memory and others:
intuition is a thin reed with which to stake such a mighty claim.
But *all* of our knowledge is based on other knowledge, which is based on other knowledge, which is based …. ultimately on intuition. As far as I can see, there’s no other starting place. (Oh, there’s sensory data, but why should we trust those any more than we trust intuition?)
So I’d say this: Yes, my intuitive concept of the natural numbers is a mighty thin reed on which to hang all of my metaphysics. Also, my intuitive concept that you, like me, have thoughts and emotions, is a mighty thin reed on which to hang all of my psychology. But I’m not about to let that stop me from thinking about metaphysics or psychology.
Hey Steve,
I don’t quite understand what you mean when you say,
“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.”
Can you explain why it is a counterexample? I think I am missing something here. I read your previous posts a while ago so I’ll revisit them.
Ken B:
Take some unprovable conjecture in arithmetic. The only one I can think of off the top of my head is Goldbachs’s conjecture. Imagine someone proves it is unprovable. Would it be meaningful to say it’s true?
So someone proves it’s unprovable. That unprovability is a true statement in arithmetic. The conjecture itself might remain unprovable. All that means is that our current methods of proof can’t tell us whether it’s true or false. But surely it is either true or false. And there’d be nothing new here — we already know that arithmetic is full of true (and false) statements that are provably unprovable.
(For those trying to follow the discussion: Goldbach’s conjecture is the assertion that every even number is the sum of two primes; this conjecture is not currently known to be true, but it’s strongly suspected to be.)
Drew:
Numbers are still quite different from the sorts of things we normally talk about existing: they have no physical location,
The Universe has no physical location. Do you have trouble saying that the Universe exists?
Martin-2:
To say that the natural numbers and the rules of logic were designed is to say that they could have been designed differently. Do you believe this?
Yes, you beat me to this riposte. In my experience, most religious people, and most theologians, will conced that even God could not rewrite the rules of logic. Given that, it follows that those rules were not designed.
Roger:
The natural numbers do have that 2nd-order logic definition, and various other straightforward definitions. Those definitions serve well enough for mathematics, and are superior to just using our intuition.
My intuition for second order logic is, I am sure, far inferior to my intuition for the natural numbers.
Ken B:
Take an unprovable conjecture of arithmetic (unprovable in PA or whatever system you choose). The designer can ‘choose’ to have it true or false…
How do you know?
@Steve: I bet you can give a better definition of second order logic than you can of your intuition.
As for Goldbach, I think you’re not addressing my point, which is about why should we trust evolved intuition on such things.
Nonsense Landsburg.
It only means that God could not have designed it any better.
Because, if God is perfect, and everything He does is perfect, then He would design it perfectly according to His nature and leave no room for improvement.
Logic is immutable, and so is God, but it doesn’t follow that logic is therefore God.
@Steve: Well, I am not arguing there is a designer. I reject this whole Anselm-like argument from mathematical existence. But I am envisioning a way in which there could conceivably be one. So I *stipulated* that 1) there is a designer and 2) he must end up with one true universe — either Goldbach holds or not for example. Under your scheme I see no compelling reason why there aren’t 2 universes, Golbach-true and Goldbach-false. In fact of course WAY more universes! So the designer selects one to be the true universe, the one we inhabit. He can choose ex hypothesi. Then the next choice and so on. That seems like design to me: particular choices from the menu.
You don’t like that the designer can *choose*? What makes my assumption that he can reasonable? I’m just poking a hole in a claim. The claim is there is no room for a designer. My fantasy shows that claim seems to assume any designer cannot make choices this way. That’s an extra assumption you and Martin-2 have not justified. I don’t have to know the designer can choose; I just have to point out you need more than you have admitted to to preclude it.
Ken B – “Take an unprovable conjecture of arithmetic… The designer can ‘choose’ to have it true or false”
I don’t see why this would be the case. For one thing, doesn’t it follow from a conjecture being unprovable that our Designer doesn’t have the computational capacity to decide, know, or change whether it’s true or false?
@martin-2: I tried to address this in my comment to Steve. I think you have made extra assumptions.
Steve: “My intuition for second order logic is, I am sure, far inferior to my intuition for the natural numbers.”
Mathematical proof was invented so that truths can be established without having to rely on our fallible intuitions.
“Nonsense Landsburg.”
This sounds like some fun kind of hortatory name like “Praise-God Barebone” or his son “Nicholas If-Jesus-Christ-Had-Not-Died-For-Thee-Thou-Hadst-Been-Damned Barebon”, coincidentally also an economist.
Both real names btw.
Ken B – Ah I see. If I take your example using Goldbach’s conjecture then in one universe I would find a natural number that is not the sum of two primes, and that same number would be the sum of two primes in the other universe. Or it would be replaced by a different number. I think your example would be more powerful if you restricted the the Design aspect to unprovable and untestable statements.
Hmm. Is there any interesting theory on the nature of untestable arithmetic statements?
Philip C, I don’t follow you’re logic. If God “would design it perfectly according to His nature and leave no room for improvement.”, why would He have made mathematics incomplete? In my mind, an incomplete system is not perfect. And therefore, either there is no God, or not everything that God does is perfect.
Philip C – “It only means that God could not have designed it any better. Because, if God is perfect, and everything He does is perfect, then He would design it perfectly according to His nature and leave no room for improvement.”
So the notion of what system is better or worse is outside your god’s control? My god struggles to conceal his amusement.
Or the premise that everything God does is perfect is incorrect.
Al V.:
why would He have made mathematics incomplete?
What would it mean for mathematics to be “incomplete”?
I submit that your posts on the foundations of mathematics are the best written introductions for the layman, anywhere. More please!! (In fact, all your posts on mathematics are fantastic.)
Steve: that’s a good initial objection, but I’d argue that “the universe” is a pretty vague concept itself: the set of all things that physically exist (and the _context_ in which they exist and have locations relative to each other). But If natural numbers “exist,” though, then their existence is actually independent of the universe. And that, itself, is a quite different state of existence (whatever THAT is) than a specific rock on a specific beach. There’s nj clear sense in which you need a universe at all for natural numbers to be “real.” But that is something that’s necessary for, say, beaches or rocks. “Real/true” might be a better term for the superset in which both rocks and numbers reside. Though, of course, its easy to suggest that perceived rocks are an illusion of perception. No one has yet suggested how numbers could be phony or untrue. Again, in some ways, that makes mathematics even more reliable than physical existence. Which, again, suggests that they are not quite the same _sort_ of thing.
To be more clear, my initial point is that talking about the universe “existing” is basically like saying that this rock exists and this rock exists and this atom exists, and this proton exists so on and so on. The universe is a list of things, not necessarily a thing in and of itself, as if it were one concrete thing. There are theories of physics that might assume it to be so, and others that might not, but I don’t think we really have grounds to say much about it at present. Everything we see and do takes place in the presumed context of “existence”: we don’t have much justification, based on just that, to generalize those contextual principles to the context itself, anymore than we can apply the rules of, and lessons learned from, chess to the nature of game playing in toto. We don’t have any other universes to compare ours to, for greater context.
Drew:
We don’t have any other universes to compare ours to, for greater context.
Sure we do. The physics literature is full of solutions to Einstein’s equations. That (together perhaps with some gauge fields and other bells and whistles) is what a universe is.
Nick:
In fact, all your posts on mathematics are fantastic.
And what’s wrong with the other posts?!?!?!? (Smiley omitted but, I hope, clearly implied.)
I agree with Nick. I very excited when it’s a math post. I also can’t wait for more Stanley Tennenbaum stories.
@Steve “And what’s wrong with the other posts?!?!?!?”
The other posts are merely amazing.
@Steve, @Martin-2 “To say that the natural numbers and the rules of logic were designed is to say that they could have been designed differently. Do you believe this?”
Clearly they could have been designed differently. In fact, mere human mathematicians come up with other designs for arithmetic and logic as a matter of course. I can easily posit a system of “logic” where modus ponens doesn’t apply, or a system of “natural numbers” where not every number has a successor, or where zero is the successor of something, or where A x B is not B x A.
@Steve “most theologians will concede that even God could not rewrite the rules of logic.”
That’s because they haven’t studied enough mathematics. To take their statement as definitive would be as silly as, say, taking seriously what a mathematician has to say about theology. Oops! Um… except me, of course… er… *grin?*
Intuition is a poor guide to mathematical truth.
Take, for example, the question :
“Does there exist a set that is bigger than Z, but smaller than R?”
(NB: Z is the set of all integers, R the set of all reals, Q the set of all rationals).
I suspect most math students, before they meet Cantor’s arguments, will say either
“it’s intuitively obvious that the answer is “no”, since Z and R have the same size : infinity”
or
“it’s intuitively obvious that the answer is “yes”, since Z is smaller than Q and Q is smaller than R”
intuition has failed them. When Cantor’s argument is explained and understood, it produces a sense of wonder. Amazing! Z and Q have the same size, but R is strictly bigger!
The sense of wonder comes from the realisation that the truth is different from intuition. It’s a sense of wondrous surprise akin to an unexpectedly beautiful sunset or view, or the unexpected oxytocin rush that a new baby produces. The sense that the world – at least, the world you perceived – has changed.
Then, when one returns to the original question, (does there exist A such that |Z|<|A|<|R|), when one finally learns that this is undecideable under standard set theory, there may or may not be the same rush of wonder. If there is, it's rarely because one has formed an intuition about the cardinalities of infinite sets. Instead, it will be because one's intuitions about proveability have been shattered. You'll get less of a rush at this point if you've already met Godel's theorem.
Math is interesting because mathematical truths so often run counter to intuition. I wouldn’t trust intuition to tell me the truth one inch – not until I had fuelled it with a significant amount of data collection and careful logical thought. And even then, I would expect surprises – In fact, if all the surprises vanished away, and my intuition became a perfectly reliable discerner of mathematical truth, would I be able to remain interested in mathematics for long? I don’t know, but I *do* know this : in primary school, I would sometimes amuse myself by adding up large handfuls of multi-digit numbers. I don’t do that any longer though – there are no more surprises for me there.
Why are you obsessed with believing that you are smarter than God?
@Eliezer: He went to Chicago. Duh.
SL: “What would it mean for mathematics to be “incomplete”?”
I think the sense is,to make is ‘complete’ would be along the lines of making everything decidable and all functions recursive. Of course doing that is beyond god’s power.
Mike H:
Intuition is a poor guide to mathematical truth.
You seem to be missing the point that we have no alternative, as far as a starting point goes.
@martin-2: I think so. For example, Turing Machine with number X halts on input string with number Y. It’s easier if we get to transfinite numbers, and things like ‘inaccessible cardinals exist’ but I wanted to stick to simple arithmetic to avoid side issues.
Steve’s response to Drew, ” The physics literature is full of solutions to Einstein’s equations. That (together perhaps with some gauge fields and other bells and whistles) is what a universe is” begs the question. The whole debate is, is mathematical existence real existence.
“You seem to be missing the point that we have no alternative, as far as a starting point goes.”
Okay, but you seem to quite willingly leap from “we must start with intuition” to something like “intuition can decide problems logic cannot”. Pardon me if I’ve misunderstood, or if I have not misunderstood, pardon me for not leaping with you. :-)
Steve,
we already know that arithmetic is full of true (and false) statements that are provably unprovable.
I am truly puzzled by this statement. I haven’t studied advanced logic and really do not understand. I can believe that there are statements that cannot be proven to be true (by whatever method you mean by “proof”), but any false statement can be proven false by an example. For example, if I were to make the claim that all functions are continuous, it’s a straight forward task to provide a counter example, showing my claim to be false.
It seems to me we could define statements as true to be such statements that can be proven true and any statement for which a counter example cannot be constructed. So any statement we can’t prove to be true and haven’t found a counter example for, we have to be ambivalent about. Is it really true that there are statements which are false for which no counter example can ever be found?
Mike H,
Intuition is a poor guide to mathematical truth.
Is it? That intuition has lead some people on wild goose chases doesn’t mean that intuition hasn’t lead to some really fantastically beautiful and deep mathematical truth.
I don’t know about you, but my ability with math relies on my intuition. I can explain things and work with mathematical objects for which I have a mathematical intuition. I reached my mathematical limitations a few years ago and found myself unable to answer mathematical questions in grad school because I didn’t have enough intuition to even begin to search for an answer. For those things that I have no intuition, I have a hard time even answering basic questions, much less doing anything useful, like advance that math to find some mathematical truth.
I think this is why Erdos said some proofs were right “from the book”. Because not only were they true and simple, but deeply intuitive or used deeply intuitive notions as proof. Then there are other proofs for which you can see the logical chain, but the proof is unenlightening and very non-intuitive. Most of the time, these types of theorems or propositions are used as black boxes and used to further advance some other more “beautiful” type math proposition or theorem.
Descartes said “I think, therefore I am”. The only thing we can know absolutely is that we exist as some sort of thinking being. He then went on, using intuition, to derive many things, which were wrong. One of which was the necessity of the existence of God.
Intuition is the thin reed we have to use, because we have nothing else. It does not make our intuitive deductions right.
@Ken, yes, there are really unproveable statements. That’s one of the most amazing things about mathematical logic.
It is possible to write down explicit statements in mathematics, and then prove “neither this statement nor its opposite can be proved in axiomatic system X”. If X is a commonly used system, we usually say “this statement has is unproveable”.
The trick is that proofs themselves can be encoded as mathematical objects. Then, the traditional trick is to write down a statement P which means “P has no proof (in X)”.
Then if P could be proven, it would be false, and our axiomatic system has contradictions. If the axiomatic system has no contradictions, then P has no proof, [but|therefore] P is true.
@Harold “Intuition is the thin reed we have to use, because we have nothing else. It does not make our intuitive deductions right.” I fully agree.
@Ken “I don’t know about you, but my ability with math relies on my intuition”
Me too. However, in unfamiliar situations, intuition lets you down. Then, we need to go back to the book, and slog it out through the definitions and logic until an intuition begins to form
Mike H,
Ken, yes, there are really unproveable statements.
If a statement is false, like “X has property P”, then there exists an X that does not have P. If an X exists that doesn’t have P, then it can be found. This doesn’t mean that it will be found or is easy to find. If this isn’t “proof” of falsehood, then what is meant by “proof”?
Mike H,
Then, we need to go back to the book, and slog it out through the definitions
Where do you get definitions? The axioms and definitions used for say an ordered field and a continuous functions arose from what is intuitively meant by “ordered field” (like the real and rational numbers) and “continuous functions”.
Ken:
If this isn’t “proof” of falsehood, then what is meant by “proof”?
A proof is a sequence of formals statements, each of which is either an axiom or follows from previous statements by the laws of inference.
One can make real progress on some of these issues. Edward Nelson’s book Predicative Arithmetic is a great place to start:
http://www.math.princeton.edu/~nelson/books/pa.pdf
He writes:
“The reason for mistrusting the induction principle is that
it involves an impredicative concept of number. It is not correct to argue that induction only involves the numbers from 0 to n; then property of n being established may be a formula with bound variables that are thought of as ranging over all numbers. That is, the induction principle assumes that the natural number system is given. A number is conceived to be an object satisfying every inductive formula; for a particular inductive formula, therefore, the bound variables are conceived to range over objects satisfying every inductive formula,
including the one in question.”
and more shockingly, and here I paraphrase:
“Finitists believe that primitive recursions always terminate; for example, that applying the axioms of Peano arithmetic – minus mathematical induction – together with the definition of exponentiation ↑ and tetration or ‘supexponentiation’ ⇑ a sufficient number of times,
2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2
reduces to a numeral. But the putative number of times these rules must be applied can only be expressed by means of a superexponential expression — the argument is circular.”
Predicative arithmetic is a formalism that gets around this claimed problem, and he believes it should be acceptable to ‘ultrafinitist’ mathematicians who doubt the existence of enormous finite numbers like
2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2
It limits mathematical induction to predicative expressions. But another approach is Andrew Boucher’s book Arithmetic Without the Successor Axiom:
http://www.andrewboucher.com/papers/arith-succ.pdf
Steve,
Isn’t proof by counter example a sequence of formal statements?
John Baez: Nelson goes on to say that “It appears to be universally taken for granted by mathematicians, whatever their views on foundational questions may be, that the impredicativity inherent in the induction principle is harmless — that there is a concept of number given in advance of all mathematical constructions, that discourse within the domain of numbers is meaningful.”
I’m not sure the adjective “universally” is correct here, but it’s pretty close. I admit to the tiniest sliver of a qualm about this, but there is at least a tiny band of others who are more skeptical than I. Nelson, of course, is the (extremely rare) thoroughgoing skeptic who says “But numbers are symbolic constructions; a construction does not exist until it is made; when something new is made, it is something new and not a selection from a pre-existing collection. There is no map of the world because the world is coming into being.”
I’m strongly in favor of questioning all assumptions and seeing how far you can get when you assume less, which is what Nelson is up to. But it does seem to me that once you throw out the set of natural numbers (as a completed whole) you end up being forced to admit even more metaphysical baggage than you’ve thrown out. E.g.: I believe — on Max Tegmarkian grounds — that once you’ve got enough mathematics, you’ve got the physical universe for free. But Nelson needs to start with the construction process, which means he’s got to start with the existence of mathematicians, which means he’s got to start by positing the existence of the physical universe. That seems to me to be a *far* greater leap than positing the existence of the natural numbers.
On another note, having John Baez show up in the comments section has got to be one of the greatest rewards a blogger could hope for. Welcome.
Ken:
If a statement is false, like “X has property P”, then there exists an X that does not have P. If an X exists that doesn’t have P, then it can be found. This doesn’t mean that it will be found or is easy to find.
It also doesn’t mean it can be proved to have property P.
@Ken “If a statement is false, like “X has property P”, then there exists an X that does not have P. If an X exists that doesn’t have P, then it can be found.”
Your statement is intuitively obvious. It’s also an example of intuition letting you down. Our intuition says “truth may be derived from logic”, so we define logic according to our intuition, then (perhaps) define mathematical truth as provability.
Then, the collection of all mathematical statements becomes a well-defined set, we can define (quite easily) what a “proof” of x is, and we can define a property P(x) to be “x has a proof”, eg, P(x) ∃y:y is a proof of x.
Once this is done, it turns out to be possible to construct a statement S that says “~P(S)”.
Now, given the existence of S, why don’t you tell me whether or not you think S can be proven?
I can surely make general statements about dragons. “Dragons are large, scaly, flying creatures who can breathe fire”. (If you insist that I have only stated premises, and you want deductive statements, try something like “dragon breath is hot” (deduced from “dragons breathe fire” and “fire is hot”)).
I’m also reminded of the ontological argument. God exists because we can deduce that one of his properties is existence. The flaw in the argument can be phrased several ways, but I’d say that “X has property Y” is a shorthand for “if an X exists, then it has property Y” or “everything in the set X has property Y”. Trying to prove that something has the property of existence would prove nothing at all, since any statement about X having properties are implicitly conditioned on X’s existence in the first place.
In the case of numbers, I might also point out that all statements about natural numbers can be taken to be shorthand. “Numbers can be summed” really means “when I apply the abstraction ‘counting’ to separate groups of objects and apply the same abstraction to a combination of those groups of objects, the mapping of the former abstractions to the latter abstraction is my definition of ‘sum’.” “5” doesn’t exist; “5” is just something I write because I don’t want to constantly make ludicrously long statements about physical objects.
Tell me, does roundness exist? Does English exist? Does a building’s height exist (assuming that the building exists)? Does a proof for a mathematical theorem exist before anyone has actually found the proof?
Here’s another one: Does the parallel postulate exist? Since using it to do mathematics is not necessary. your argument for the existence of numbers doesn’t apply to it, yet it seems weird to say that 2, 3, and “prime” exist but the parallel postulate doesn’t.
Ken Arromdee:
Does the parallel postulate exist?
The parallel postuate is a (short) finite string of symbols. If you can’t believe in strings of symbols that can be written down in less than a minute, then I can’t imagine you’d be able to believe in anything at all.
Oh, come on now. I’m asking “does the parallel postulate exist in a similar sense to your claim that 2 exists?” You’re not saying that 2 exists because you can write it down.
I would also deny that the parallel postulate is a string of symbols. It’s a concept, though it can be *expressed* by a string of symbols. (I can express “triangle with four sides” as a string of symbols as well, but the concept it describes is incoherent and it is unclear that that concept exists.)
Ken Arromdee: The parallel postulate is an axiom of euclidean geometry. Axioms are strings of symbols.
SL:
Martin-2:
To say that the natural numbers and the rules of logic were designed is to say that they could have been designed differently. Do you believe this?
Yes, you beat me to this riposte. In my experience, most religious people, and most theologians, will conced that even God could not rewrite the rules of logic. Given that, it follows that those rules were not designed.
1. I don’t think it’s sufficient to use what most religious people and most theoligians believe as an assumption for a proof
2. If those rules would indeed have been designed differently perhaps that would just mean the Universe would be different.
I am still waiting for a proof that they were not designed…
I disagree that axioms are strings of symbols. Axioms are concepts; they can be expressed by strings of symbols.
And that’s still not the question I was asking, anyway. Does the parallel postulate exist in the way you believe the natural numbers exist?
On one hand, you can speak of its properties or describe a system which uses it, so technically it fits your definition. On the other hand, I really don’t think you’re saying that just any old properties or system count. My best guess as to what you mean is that the properties of the natural numbers cause them to “exist” because these properties are ones that we cannot avoid when doing math. The parallel postulate can be avoided.
David Hilbert writes: “Axioms are strings of symbols.”
Steve claims that statements about the natural numbers have meanings and are not just strings of words. Within this context (which I don’t think was the one Hilbert worked in), I deny that axioms are strings of symbols.
Concerning Edward Nelson, here is a quote from Predicative Arithmetic which I think demonstrates the character of his philosophy: “The intuition that the set of all subsets of a finite set is finite—or more generally, that if A and B are finite sets, then so is the set B^A of all functions from A to B—is a questionable intuition. Let A be the set of some 5000 spaces for symbols on a blank sheet of typewriter paper, and let B be the set of some 80 symbols of a typewriter; then perhaps B^A is infinite. Perhaps it is even incorrect to think of B^A as being a set. To do so is to postulate an entity, the set of all possible typewritten pages, and then to ascribe some kind of reality to this entity—for example, by asserting that one can in principle survey each possible typewritten page. But perhaps it is simply not so. Perhaps there is no such number as 80&500; perhaps it is always possible to write a new and different page.”
This should shed some light on what Nelson believes. When you first hear that he doesn’t think that numbers as large as 80^5000 exist, you may assume that this means that he only believes that there are finitely many natural numbers, putting him in the same category as Essenin-Volpin. But this is not the case: he believes that there are a (potential) infinity of natural numbers. When he says that 80^5000 does not exist, he means that he believes that it is infinitely large, meaning that there’s infinitely many numbers less than 80^5000. This seems incredibly counterintuitive, but it seems to be a coherent belief system.
You can even conceptualize it within standard mathematics: there are nonstandard models of Robinson Arithmetic (Q) in which exponentiation is not total, in the sense that if a and b are finite then it’s possible that a^b is infinite; Sheperdson’s computable nonstandard model of arithmetic has this property (nonstandard models of Q, unlike nonstandard models of PA, are allowed to be computable). And with minor modifications, you can take the field of fractions of the Sheperdson integers and you’ll get a real closed field, in which (definitionally) all the axioms of Euclidean geometry hold. If anyone is interested I can provide more details.
Ken Arromdee:
I deny that axioms are strings of symbols.
Feel free. You can also deny that whales are mammals and humans are apes. But that won’t change the facts.
You are failing to make proper distinctions between the *name* of a thing, the thing *itself*, and the *idea* of the thing.
I can write down the name of a horse, but I cannot write down a horse, and I cannot write down the idea of a horse.
I can write down the name of the number 2 (it’s the numeral 2, which is not the same thing as the number 2), but I cannot write down the number 2 itself, and I cannot write down the idea of the number 2.
When it comes to the parallel postulate, I can write down the name of the postulate (“the parallel postulate”. See! I just did it!). I can *also* write down the postulate itself, though I cannot of course write down the idea of the postulate.
Unlike horses and numbers, axioms can be written down. That’s an important distinction.
Don’t the reasons given above for doubting the existence of 2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2 also mean one should doubt the existence of 1 ?
Unlike horses and numbers, axioms can be written down. That’s an important distinction.
I can write down an axiom, but I can’t write down a number? How is that?
I mean, I understand that a number is an idea and I can’t write down an idea. And I understand (though not agree) that you can claim that “the axiom” is the string of symbols, and you can write the string of symbols down. But I don’t understand how you can claim both of these at the same time. They don’t seem consistent with each other. Either the real thing is the idea, and neither can be written, or the real thing is the string of symbols, and both can be written.
Ken Arromdee:
The logical consequence of this belief system is that there is some number X, which we would all agree is finite, where he would claim that X+1 is not finite.
This is or is not a logical consequence depending on your axiom system. It is not a logical consequence in Nelson’s system.
Ken Arromdee. You are extremely confused.
I understand that a number is an idea and I can’t write down an idea.
No. A number is not the same thing as the idea of a number.
And I understand (though not agree) that you can claim that “the axiom” is the string of symbols
You are “disagreeing” with a standard definition. This is like disagreeing that an elephant is a big gray animal with a trunk. You are choosing to use words in a completely nonstandard way and “disagreeing” with the standard usage. That’s nothing but a recipe for miscommunication.
Either the real thing is the idea, and neither can be written, or the real thing is the string of symbols, and both can be written.
A number and the idea of a number are different things. Neither can be written down. An axiom and the idea of an axiom are different things. The axiom can be written down, but the idea can’t be.
Again, any “disagreement” you might have is not over substance; it’s simply a refusal on your part to abide by standard definitions and an insistence on inventing your own private language. We’ll really get much further if we both use words to mean the same things, and the most convenient way to do that is to use those words the way everybody else does.
Mike H: You asked “Don’t the reasons given above for doubting the existence of 2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2⇑2 also mean one should doubt the existence of 1 ?” The answer is no in Edward Nelson’s Predicative Arithmetic. Edward Nelson believes all of the following:
1. 1 is a natural number.
2. If x is a natural number, x+1 is a natural number.
3. If x and y are natural numbers, x+y is a natural number.
4. If x and y are natural numbers, xy is a natural number.
But he does not believe that if x and y are natural numbers, then x^y must be a natural number. He thinks there are finite natural numbers x and y such that x^y is infinite!
Why does he treat exponentiation different from addition and multiplication? You can read his talk here:
http://www.math.princeton.edu/~nelson/papers/e.pdf
(It’s 11 pages, but the heart of it is pages 4-6)
Basically, it boils down to the fact that exponentiation is not associative, which prevents you from proving that x^y is finite if you are an extreme finitist like Nelson.
Keshav Srinivasan: Thanks for your last couple of comments, which have been exceptionally helpful and well-informed.
Ok, so his argument begins like this :
1) Start with the axioms
* “0 is a counting number”
* “if y is a counting number, so is Sy”
2) Given a putative proof that X is a counting number, reject it as circular if the proof has X steps or more
However, here’s where it all falls down. He immediately gives (and happily accepts) proofs with more than zero steps, but there’s no way in his system to prove (except circularly) that 1 is a counting number.
You might say “Well, he can modify his axioms to accept 1 also.”
However, then all numbers become counting numbers, including 2⇑2⇑5. If we accept, as axioms,
(A1) “1 is a counting number”
(A2) “if y is a counting number, so is Sy”
(A?) (maybe other axioms)
Then here’s a proof that 10 is a counting number :
(S1) by A1 and A2, 2 is a counting number
(S2) by S1 and A2, 3 is a counting number
(S3) by S2 and A2, 4 is a counting number
(S4) by S3 and A2, 5 is a counting number
(S5) by S4 and A2, 6 is a counting number
(S6) by S5 and A2, 7 is a counting number
(S7) by S6 and A2, 8 is a counting number
(S8) by S7 and A2, 9 is a counting number
(S9) by S8 and A2, 10 is a counting number
Note that this proof has only 9 steps, so it’s not circular. I have likewise found a wonderful proof that 2⇑2⇑5 is a counting number, using only 2⇑2⇑5-1 steps, but this comment form doesn’t have enough space to contain it.
If he accepts the axiom “1 is a counting number”, his statement “no one will ever prove that 2⇑2⇑5 is a counting number” is incorrect. If he rejects the axiom “1 is a counting number”, then he can’t prove that 1 is a counting number, and all proofs should be rejected except restatements of the axioms.
Mike H: I think you’re misunderstanding what he’s saying. He’s not saying “Given a putative proof that X is a counting number, reject it as circular if the proof has X steps or more.” It’s OK if a proof that X is a counting number contains more or the same number of lines as the size of X. He’s completely fine with a proof like this that 5 is a counting number (where A1 is changed back to the original axiom “0 is a counting number):
(S1) by A1 and A2, 1 is a counting number
(S2) by S1 and A2, 2 is a counting number
(S3) by S2 and A2, 3 is a counting number
(S4) by S3 and A2, 4 is a counting number
(S5) by S4 and A2, 5 is a counting number
What Nelson is really protesting is, when someone is challenged to prove that (say) 100 billion is a counting number, for them to just say “I don’t need to write down the proof, because obviously you just continue the proof above for a hundred billion lines and then you’ll certainly prove that 100 billion is a counting number.” He is refuting such an argument because it presupposes that you can have a “hundred billion lines”, which would only be possible if 100 billion is in fact a counting number, the very thing we were trying to prove. It would be like proving that infinity is a counting number by saying “Just write down a proof with infinitely many lines, and in the end of the proof you’ll prove that infinity is a counting number.”
If the same person actually sat down and wrote down the 100 billion-line proof, Nelson would have no objection, because the very fact that he was able to complete the 100 billion line proof means that 100 billion is finite, i.e. a counting number.
I hope this clarifies things.
Don’t tell the IRS! I invested in an Arabian stallion as a tax dodge; when he died, I took a complete write-down.
What about an axiom that cannot be written down? Say an axiom with w (omega) symbols?
If w exists, and functions exist, I don’t see why, if naming a thing conjures its existence, that w length strings don’t exist. So isn’t it a bit arbitrary to say they cannot be axioms or parts of proofs?
KenB:
What about an axiom that cannot be written down? Say an axiom with w (omega) symbols?
According to the usual definitions, an axiom is a finite string. If you’re going to step outside the usual definitions, I think you’ll have to do some hard work telling us which strings are eligible to be axioms (and then of course, if you want this to be interesting, you’ll have to do more hard work establishing the properties of your expanded class of formal theories).
@Steve: Well I’m just wondering why or if your argument keys on finitary axioms. Are you basing the existence of reality on the existence of people, or conscious minds? I am gonna go out on a limb and guess you are not. So then what makes the finitary system you talk about special? I mean things like, maybe in such a system math is SIMPLE or the natural numbers are easily identified, stuff like that.
Intuition is pffft I’d guess.
You draw conclusions from the use of finite methods. But in a discussion where you’re arguing this is the real stuff of the universe not a construct of minds, why is that perspective to be privileged?
Ken B: This may be interesting to you:
http://plato.stanford.edu/entries/logic-infinitary/
This is fascinating. Nelson believes that that the natural numbers may “run out” – is that anywhere near what he is saying? These huge numbers may not exist, or at least we can’t prove they exist? Excuse me if I have got this totally wrong.
Ken B: I have no idea what you’re talking about. Certain strings of symbols form sentences; these sentences (when interpreted in a model) can be assigned meanings. I have no idea how to assign a meaning to an infinite string of symbols. So I can’t imagine what program you’re proposing.
@Keshav: Mike H: I think you’re misunderstanding what he’s saying. He’s not saying “Given a putative proof that X is a counting number, reject it as circular if the proof has X steps or more.” It’s OK if a proof that X is a counting number contains more or the same number of lines as the size of X
And yet, starting at the end of page 4,
“Let us ask, given a specific number y defined by primitive recursion, … whether we can prove that it is a counting
number. Now to say that there is an obvious proof in y steps is circular, because steps are things that are counted, so we can only count the steps if y is indeed a counting number”
That’s what he says, but he ignores this injunction when it suits him (“small” y, like 1) and only applies it for “big” numbers (like 2⇑2⇑5). This is not logically consistent, nor is it consistent with his axioms.
Harold:”This is fascinating. Nelson believes that that the natural numbers may “run out” – is that anywhere near what he is saying? These huge numbers may not exist, or at least we can’t prove they exist? Excuse me if I have got this totally wrong.” Unfortunately, you have got this wrong. Nelson emphatically does NOT believe that there are only finitely many natural numbers, or that they will run out, or anything of the sort. Let me repeat, he believes in all of the following:
1. 1 is a natural number.
2. If x is a natural number, x+1 is a natural number.
3. If x and y are natural numbers, x+y is a natural number.
4. If x and y are natural numbers, xy is a natural number.
So he certainly believe that the sequence 1, 1+1, 1+1+1, 1+1+1+1, … goes on forever, and probably so. Where he differs from most people is that he does not believe that exponentiation is total: he thinks it is possible for x and y to be natural numbers and yet for x^y to be infinite. If this seems utterly absurd and indefensible to you, I suggest for starters that you read pages 4-6 of this talk by Nelson:
http://www.math.princeton.edu/~nelson/papers/e.pdf
Tell me if you’re still confused.
Personally, having identified the logical flaw in pages 4-6 of the document, I’m not confused at all. ;-)
I mean, can you really not see that the 1 step “proof”
(S1) by A1 and A2, 1 is a counting number
is circular? After all, steps are things that are counted, so we can only count the steps if 1 is indeed a counting number.
Mike H: The quote by Nelson you’re referring to does not mean what you think it means. He is NOT objecting to someone who proves that y is a counting number using a proof that is y steps long. Rather, he is objecting to someone who merely claims that there EXISTS a proof that is y steps long that y is a counter number. He is saying that such a claim is baseless if you haven’t actually written down the y lines-long proof, because otherwise you’re just presupposing that there can BE such a thing as a proof of length y, when you don’t even know yet that y is a counting number. Obviously, if you have actually written down a proof that is y lines long, then you know for sure that it is possible for there to be a proof to be of length y. and thus you know that y is a counting number. Does that make sense?
I assure you, Edward Nelson’s framework is neither trivial nor incoherent. You don’t have to take my word for it, you can read his magnum opus, Predicative Arithmetic:
https://web.math.princeton.edu/~nelson/books/pa.pdf
I don’t know how familiar you are with mathematical logic, but in case you are, Nelson’s notion of a predicative theory is a theory that is interpretable in Q (Robinson Arithmetic, i.e. Peano Arithmetic without induction). And if you work through the details, you will find that the totality of exponentiation is not provable in any theory interpretable in Q, but totality of addition and multiplication are, so within this framework Nelson is indeed justified in saying that x+y and x*y are counting numbers but x^y need not be a counting number.
Keshav Srinivasan: For the second time in this thread — thanks enormously for your extremely helpful explanations.
“Obviously, if you have actually written down a proof that is y lines long, then you know for sure that it is possible for there to be a proof to be of length y”
Then, are mathematical truths defined by human activity?
If I write down a proof that 1 is a counting number, using 1 step, you say that’s fine, because I wrote it down. However, the analogous proof that 1 billion is a counting number is not acceptable simple because nobody has the patience to write it? Would you accept a computer-derived proof, even though nobody would have the patience to check it?
Bringing a human into an axiomatic system surely makes it more complicated, no?
Mathematical logic was a field I was fascinated by during my undergraduate, and very interested in. I actually did my postgraduate studies and later research in abstract polytopes.
Nelson’s notion of a predicative theory is a theory that is interpretable in Q (Robinson Arithmetic, i.e. Peano Arithmetic without induction). And if you work through the details, you will find that the totality of exponentiation is not provable in any theory interpretable in Q, but totality of addition and multiplication are, so within this framework Nelson is indeed justified in saying that x+y and x*y are counting numbers but x^y need not be a counting number.
This makes perfect sense. The hand-wavy arguments that rely on what I “know” in order to test for circularity, by contrast, don’t seem that easy to swallow.
Mike H: “If I write down a proof that 1 is a counting number, using 1 step, you say that’s fine, because I wrote it down. However, the analogous proof that 1 billion is a counting number is not acceptable simple because nobody has the patience to write it? Would you accept a computer-derived proof, even though nobody would have the patience to check it?” It would be fine if you wrote down the proof or have a computer do it. The important thing is whether it CAN be done, not whether it HAS been done. That’s because if we know that the proof can be done in finitely many steps, then we know that the number of steps is a counting number. Again, what Nelson objects to is reasoning like this:
A. “Of course 2^X is a counting number. I don’t need to prove this, because obviously there exists a finite proof of this statement that is 2^X lines long.”
B. “Of course infinity is a counting number. I don’t need to prove this, because obviously there exists a finite proof of this statement that is infinity lines long.”
Presumably you also object to B, since before you can blindly assert, without writing it down, that there exists a finite proof that is infinity lines long (!), you need to first need to make sure that infinity is not infinitely large (!), i.e. you need to establish that it is a counting number first. So can’t you see his similar grounds for objecting to A?
Mike H: “The hand-wavy arguments that rely on what I “know” in order to test for circularity, by contrast, don’t seem that easy to swallow.” What Nelson is doing is perfectly rigorous. He is starting with Robinson’s Q and adding an undefined predicate N(x) meaning “x is a counting number”, along with the axioms N(0) and if N(c) then N(x+1). He is then trying to prove, given N(x) and N(y), that N(x+y) and N(xy), but he finds it impossible to prove N(x^y)? You may be asking, what is the point of N? It has to with how much mathematical induction you’re willing to accept. Nelson is willing to accept bounded induction, i.e. induction with respect to predicates like “For all x less than 1+1+1+1, x has property P.”. But he is not willing to accept induction with bounds like 2^billion, because he doesn’t know whether 2^billion is infinite, and thus the quantification would be unbounded. So he only accepts induction bounded either by explicit numerals like 1+1+1 or by terms like 2*4 which have been shown to be counting numbers. If you want to think in computer programming terms, Nelson does not like unbounded while-do loops, only bounded for-do loop with bounds that have been proven to be counting numbers. Does that make sense?
The important thing is whether it CAN be done, not whether it HAS been done
When he says “CAN be done”, does he mean that there needs to be a mathematician in the mix? If so, you have a ridiculously complicated (and probably inconsistent) system of axioms.
If he means “Can, in a theoretical sense”, well, you can’t say “1 is a counting number” and then say “but 2⇑2⇑5 is not”.
However, I can see how, without the inductive axiom, it might be unproveable that “∀X,2⇑2⇑X is a counting number”, even if we can individually prove each of :
* 2⇑2⇑1 is a counting number
* 2⇑2⇑2 is a counting number
* 2⇑2⇑3 is a counting number
* 2⇑2⇑4 is a counting number
* 2⇑2⇑5 is a counting number
* … etc
One could even include the axiom
* ∃X,2⇑2⇑X is not a counting number
and then prove
* but that X is not 1
* nor is it 2
* nor 3
* nor 4
* nor 5
(etc)
and have no contradiction. This would be an example of one of the “non-standard N” that Steve’s been blogging about lately.
I have no problems with that.
I suspect Nelson means you can’t prove “∀X,Y, X^Y is finite”, even though you can prove X^Y is finite for any particular X and Y. I sincerely hope that’s what he means, since rejecting a proof that 80^5000 is finite, but accepting the proof that 1 is finite, (simply because the former is outside human capacity and the latter is not) makes math too subject to human frailty.
Mike H: “When he says “CAN be done”, does he mean that there needs to be a mathematician in the mix? If so, you have a ridiculously complicated (and probably inconsistent) system of axioms.” No, a mathematician doesn’t need to be in the mix, it’s whether it’s doable in principle that matters.
“If he means “Can, in a theoretical sense”, well, you can’t say “1 is a counting number” and then say “but 2⇑2⇑5 is not”.” Yes, you can say exactly that. Tell me, what is your basis for saying that 2⇑2⇑5 can be shown to be a counting number (using Nelson’s axioms)? Surely it is because you believe that there is a proof of this fact that is 2⇑2⇑5 lines long, right? But the thing is, how do you know that there is such a thing as a proof that is 2⇑2⇑5 lines long if you don’t even know beforehand that 2⇑2⇑5 is finite?
“I suspect Nelson means you can’t prove “∀X,Y, X^Y is finite”, even though you can prove X^Y is finite for any particular X and Y. I sincerely hope that’s what he means, since rejecting a proof that 80^5000 is finite, but accepting the proof that 1 is finite, (simply because the former is outside human capacity and the latter is not) makes math too subject to human frailty.” I’m sorry, but he is indeed saying that there can be specific finite numbers X and Y such that X^Y is infinite. But he is not saying this simply on the basis of human frailty. Again, he is willing to accept that the sequence 1, 1+1, 1+1+1, 1+1+1+1, … goes on ad infinitum forever, meaning far beyond human lifetimes or capability to write down all the terms in that sequence. All he is saying is that it is not good enough to merely assert the finiteness of (say) 2⇑2⇑5 on the basis of a blind assertion that there exists a proof in 2⇑2⇑5 lines, because you don’t know that there exists a proof in 2⇑2⇑5 lines, because you don’t know whether 2⇑2⇑5 is finite. To do otherwise would be circular, wouldn’t it, unless you knew a priori that exponentiation is total?
“But the thing is, how do you know that there is such a thing as a proof that is 2⇑2⇑5 lines long if you don’t even know beforehand that 2⇑2⇑5 is finite”
Since you insist…. How do you know there is such a thing as a proof that is 1 line long if you don’t even know beforehand that 1 is finite?
…and :
it is not good enough to merely assert the finiteness of (say) 2⇑2⇑5 on the basis of a blind assertion that there exists a proof in 2⇑2⇑5 lines, because you don’t know that there exists a proof in 2⇑2⇑5 lines, because you don’t know whether 2⇑2⇑5 is finite. To do otherwise would be circular, wouldn’t it, unless you knew a priori that exponentiation is total?
likewise, it is not good enough to merely assert the finiteness of (say) 1 on the basis of the assertion that there is a proof written down in plain sight in 1 line, because you don’t know whether 1 is finite. To do otherwise would be circular, wouldn’t it, unless you knew a priori that there existed any nonzero finite numbers?
Mike H: We know that there can be one line proofs, because we can write them down. There are many natural numbers X and Y for which we can actually write down a proof with X^Y lines, so we know it’s a counting number. But if you cannot practically write down a proof with X^Y lines for some finite X and Y, then Nelson is saying that there’s no way to know for sure that there can BE a proof that is X^Y lines long, unless you have some independent means of knowing that X^Y is a counting number. On the other hand, if X+Y or X*Y are so big that you can’t write down a proof with that many lines, it turns out that there exists a proof in a relatively small number of lines, a proof you can actually write down, that X+Y and X*Y are counting numbers.
because we can write them down
I may be able to write it down, but why is this relevant? Is mathematical truth to be determined with reference to a particular species of mammal on a particular planet? If so, why us? This is too anthropocentric for my liking.
In any case, having written down a 1 line proof that it is finite, I still don’t know whether my proof is valid. It may be infinitely long.
But if you cannot practically write down a proof …. there’s no way to know for sure that there can BE a proof that is X^Y lines long
The statement “there’s no way for me to know” is very different from the statement “there’s no way to know”. Which is Nelson asserting about the finiteness of specific numbers of the form X^Y?
But he is not willing to accept induction with bounds like 2^billion, because he doesn’t know whether 2^billion is infinite, and thus the quantification would be unbounded. So he only accepts induction bounded either by explicit numerals like 1+1+1 or by terms like 2*4 which have been shown to be counting numbers.
Please answer this : How was 1 shown to be a counting number?
It can’t be proved within the axiomatic system
A1) 0 is finite
A2) if x is finite, Sx is finite
in a proveably finite number of steps. The shortest “proof” has 1 step, but 1 might be infinite. We can assume 1 is finite, or assume it is not, and the system is logically consistent either way. It’s an unproveable proposition.
If Nelson is using, instead, the following axioms :
A1) 0 is finite
A2) if x is finite, Sx is finite
A3..n) whatever else I, Nelson, intuit as obvious, without the need to state these in advance.
then anything goes.
Then, fine, I have no further comments, except to say that it would make it hard to either do mathematics logically or believe in its objective reality.
If Nelson is using
A1) 0 is finite
A2) if x is finite, Sx is finite
A3) 1 is also finite
then there exists a proof that 2^billion is finite.
Note that I am claiming that, within this system,
* There exists a proof that “2^billion is finite”.
I am not claiming that
* There exists a proof that “for all X and Y, X^Y is finite”,
Nor am I claiming that, within this system,
* There exists a proof that “There exists a proof that ‘2^billion is finite.'”
Mike H: “The statement “there’s no way for me to know” is very different from the statement “there’s no way to know”. Which is Nelson asserting about the finiteness of specific numbers of the form X^Y?” He’s merely saying that there is no practical way for HIM to know whether specific numbers of the form X^Y are finite when X and Y are large. It may of course be possible in principle to determine they’re finiteness. Again, Nelson is not the same kind of ultrafinitist as Esenin-Volpin, who believes that since there are finitely many natural numbers within the reach of human beings, that there must only BE finitely many natural numbers.
“Please answer this : How was 1 shown to be a counting number?
It can’t be proved within the axiomatic system
A1) 0 is finite
A2) if x is finite, Sx is finite
in a proveably finite number of steps. The shortest “proof” has 1 step, but 1 might be infinite. We can assume 1 is finite, or assume it is not, and the system is logically consistent either way. It’s an unproveable proposition.” We don’t need to prove things in a number of steps that is provably finite. We just need to prove things. After having established using our proof that 1 is indeed a finite number, we can of course (if we want) go back and prove that our proof was finite, but provably finite length is NOT a requirement that needs to be checked in order to verify the validity of a proof that we’ve done.
“Note that I am claiming that, within this system,
* There exists a proof that “2^billion is finite”.” What is your basis for this claim that there exists a proof of the finiteness of 2^billion? How can you refute Nelson’s view that there we can keep writing proofs, in order, that “1 is finite”, “1+1” is finite, “1+1+1 is finite”, etc., but in that infinite sequence we will never get to the statement “1+1+1+…+1 is finite” where you have 2^billion 1’s, because 2^billion is infinite? And whatever arguments you may give to refute Nelson on that point, why don’t those arguments work equally well to conclude that there exists a proof of the statement “1+1+1+…+1 is finite” where you have an INFINITE number of ones?
“I am not claiming that
* There exists a proof that “for all X and Y, X^Y is finite”” Good, you clearly can’t claim that, because it’s provable that there is no such proof.
“Nor am I claiming that, within this system,
* There exists a proof that “There exists a proof that ‘2^billion is finite.’”” Well then, if you can’t write down the proof (practically), and you can’t prove that there is such a proof, how do you know that there is such a proof?
On a side note, I think it might be worthwile wrestling with Nelson’s typewriter example I quoted earlier. How would you refute Nelson’s contention that you can have a typewriter with a finite symbol set writing on a finite piece of paper, and yet there being an infinite number of possible pages you can type? I find that point of view so shocking, so off the wall that I would love to come up with a good counter argument to it.
Mike H:
Is mathematical truth to be determined with reference to a particular species of mammal on a particular planet?
Nobody is remotely claiming this. We’re not arguing about mathematical truth; we are arguing about what we can prove. And of course the question of what we can prove is a question about what can be done with a particular collection of proof techniques that happen to be available to a particular species on a particular planet, because we are a particular species on a particular planet.
There exists a proof that “2^billion is finite”.”
What is your basis for this claim that there exists a proof of the finiteness of 2^billion? How can you refute Nelson’s view that there we can keep writing proofs, in order, that “1 is finite”, “1+1″ is finite, “1+1+1 is finite”, etc., but in that infinite sequence we will never get to the statement “1+1+1+…+1 is finite” where you have 2^billion 1’s, because 2^billion is infinite?
I can use the principle of induction. I know that the principle of induction is not in his list of axioms. However, I’m pretty sure that I can prove (using induction) that it holds in his system. You will (partially correctly) point out that this would be a circular proof. You are only partially correct, since I can choose to do these proofs using a different logical system, say, PA for example.
You may still insist this is circular, even if I don’t do the proof within Nelson’s system. However, it is no more circular than accepting a proof with 1 step to prove that 1 is finite in his system, surely? You accept it the proof only after accepting the finiteness of ‘1’, which you do for other reasons (either because you proved it in some other system, or because it’s “intuitively obvious”)
“How would you refute Nelson’s contention that you can have a typewriter with a finite symbol set writing on a finite piece of paper, and yet there being an infinite number of possible pages you can type? I find that point of view so shocking, so off the wall that I would love to come up with a good counter argument to it”
If the contention is that this can happen, I’d ask for a proof that it does, in fact, happen – that there does in fact exist X,Y such that X^Y is infinite. If possible, a constructive proof, please.
If the contention is merely that it cannot be proven one way or the other that X^Y is finite for all X and Y, I’d say “fine”. That’s a much weaker claim.
I’d also ask for their axioms. If they include
A1) 1 is finite
A0) if x is finite, so is Sx
then I’d complain that there is a proof that X^Y is finite, and show how to construct the proof. I’d perhaps even write the program for writing down the proof, and ask them to run the program and check the proof if they don’t believe me.
If the axioms are
A1) 0 is finite
A0) if x is finite, so is Sx
I’d ask how they know 1 is finite. If they write me down a 1 line proof and say it’s obviously a proof, I’d claim equal rights to use intuition, and prove that the axiom of induction holds, even if it’s unproveable. Or complain that if proofs become valid just because a mathematician says so, that a whole lot of rubbish suddenly becomes true, and could they please write down an axiomatic system describing the mathematician.
If they can’t either
* acknowledge the proof of 1’s finiteness is circular, and should be rejected along with my proof that induction holds, OR
* allow me to use induction, in exchange for me allowing them to do 1 line proofs, OR
* axiomatise the mathematician and his or her intuitions, OR
* acknowledge there’s no solid logical basis to the whole thing and it’s just fanciful,
then I know not to take them seriously.
Mike H:”However, it is no more circular than accepting a proof with 1 step to prove that 1 is finite in his system, surely? You accept it the proof only after accepting the finiteness of ‘1′, which you do for other reasons (either because you proved it in some other system, or because it’s “intuitively obvious”)” As I said before, Nelson does NOT believe that we need to prove things in a number of steps that is provably finite. After having established using a proof that a particular number is indeed finite, we can of course (if we want) go back and prove that our proof was finite, but provably finite length is NOT a requirement that needs to be checked in order to verify the validity of a proof that we’ve done. Instead, what he is saying that we cannot blindly assert the existence of a proof unless we have either done the proof or we can show that the number of lines in the proof is a counting number.
“If the contention is that this can happen, I’d ask for a proof that it does, in fact, happen – that there does in fact exist X,Y such that X^Y is infinite. If possible, a constructive proof, please.” If Nelson succeeded in showing in his system that X^Y is infinite even though X and Y are finite, then he would have proven that Peano arithmetic is inconsistent. Nelson is actually trying to do just that (he calls it his “Modified Hilbert Program”), because he DOES believe that exponentiation is not total, but so far he has been unsuccessful, despite the false alarm a few months ago.
“If the contention is merely that it cannot be proven one way or the other that X^Y is finite for all X and Y, I’d say “fine”. That’s a much weaker claim.” For better or worse, Nelson is indeed making the stronger claim.
“I’d also ask for their axioms. If they include
A1) 1 is finite
A0) if x is finite, so is Sx
then I’d complain that there is a proof that X^Y is finite, and show how to construct the proof. I’d perhaps even write the program for writing down the proof, and ask them to run the program and check the proof if they don’t believe me.” But the problem is, how do you know that your proposed program won’t go on an infinite loop forever?
“If the axioms are
A1) 0 is finite
A0) if x is finite, so is Sx
I’d ask how they know 1 is finite. If they write me down a 1 line proof and say it’s obviously a proof, I’d claim equal rights to use intuition, and prove that the axiom of induction holds, even if it’s unproveable.” They’re not claiming that the 1-line proof is a proof on the grounds of intuition. It is simply not the case that Nelson is insisting that proofs have to have a provably finite number of lines. But in any case, this is a side issue, so if you want to avoid getting distracted by the “1 is finite” question, then you can change the axioms to start from “1 is finite”, it really doesn’t make a difference for the purpose of Nelson’s logic. Nelson would still insist that you can’t just baselessly assert that there exists a 2^billion – 1 line proof that 2^billion is a counting number, because you would have to first show that 2^billion – 1 is a counting number.
And you can’t just say “The finiteness of 2^billion can be justified by the finiteness of 2^billion – 1, which can be justified by the finiteness of 2^billion – (1+1), which can be justified by the finiteness of 2^billion – (1+1+1), etc.” The problem with that is that perhaps there is an infinite sequence 2^billion, 2^billion – 1, 2^billion – (1+1), … that never reaches 1. Now you or I may find that absurd, because you can’t have an infinite descending chain of natural numbers, but if 2^billion were really infinite then the sequence wouldn’t be a descending chain of natural numbers.
You say “Nelson does NOT believe that we need to prove things in a number of steps that is provably finite”, yet I see a line expressing exactly that point in the paper you linked to “.
However, if you are correct, he surely has no objection to my 2^billion-1 line proof that 2^billion is finite?
Let’s call Nelson’s arithmetic NA. Let N(p) mean “statement p is proveable in NA”
I, who am happy to work in PA, can prove the following. Let P(x) be a proposition.
* If N(P(0)) and
* N(for all x, P(x) implies P(Sx)), then
* for all x, N(P(x))
So, in fact, induction holds in NA, even if we can’t actually prove this within NA.
Since I now know that the principal of induction holds in NA, I can use it to derive proveable statements in NA, without necessarily constructing the proofs. As an example, I could prove that N(2^billion is finite), since (you insist) I can prove that N(2^0 is finite), and in his talk he shows that N(2^x is finite implies 2^Sx is finite). Therefore, in fact, N(2^x is finite) for all x, even if not N(2^x is finite for all x).
…[I’d] ask them to run the program and check the proof if they don’t believe me.
But the problem is, how do you know that your proposed program won’t go on an infinite loop forever?
I’ve already presented a proof to them. I told him if he didn’t believe me he should run the program and he’ll see the proof. He just needs a powerful enough computer.
If he won’t accept my proof encoded as a computer program, why should I accept his alleged “proof” that 1 is finite encoded as smudges of ink on a piece of dead tree?
I hereby assert that 1 is infinite in NA, and his “proof” is infinitely long. I reject it. I’ll back down and concede the finiteness of 1 if he will concede the finiteness of 2^billion, which he can reasonably do in light of my inductive proof that induction holds in NA.
Mike H: “You say “Nelson does NOT believe that we need to prove things in a number of steps that is provably finite”, yet I see a line expressing exactly that point in the paper you linked to “.” Nelson does not believe that it is circular to prove that X is a counting number using a proof that is X lines long. He does, however, believe that it is circular to claim that X is a counting number based on an assertion that there exists a proof that is X lines long.
“However, if you are correct, he surely has no objection to my 2^billion-1 line proof that 2^billion is finite?” He would not have any objection to a 2^billion – 1 line proof if you actually wrote such a proof down. What he won’t accept is you just claiming that there exists such a proof, because how can you know that there exists such a proof unless you’ve either written it down or you know that 2^billion – 1 is a counting number?
“Since I now know that the principal of induction holds in NA, I can use it to derive proveable statements in NA, without necessarily constructing the proofs. As an example, I could prove that N(2^billion is finite), since (you insist) I can prove that N(2^0 is finite), and in his talk he shows that N(2^x is finite implies 2^Sx is finite). Therefore, in fact, N(2^x is finite) for all x, even if not N(2^x is finite for all x).” Right, if you work in PA you can easily show that exponentiation is total in Nelson’s system of predicative arithmetic. But the whole goal of Nelson’s work is to prove PA inconsistent, and thus prove that exponentiation is not total.
“I’ve already presented a proof to them. I told him if he didn’t believe me he should run the program and he’ll see the proof. He just needs a powerful enough computer.” The problem is, regardlesss of how powerful the computer is, for sufficiently large X and Y the program may run longer than a human lifetime, so you’ll never find out whether it terminates. So then in order to prove that X^Y is finite, you need some way to prove that the program will terminate in a finite amount of time. How will you do that?
“If he won’t accept my proof encoded as a computer program, why should I accept his alleged “proof” that 1 is finite encoded as smudges of ink on a piece of dead tree?” It doesn’t matter how the proof is written down. The proof can be written down on a computer or any other medium. What Nelson won’t accept is a mere algorithm which purports to write down the proof, without either seeing the algorithm terminate or having some way of knowing that the algorithm will terminate in a finite amount of time.
“I hereby assert that 1 is infinite in NA, and his “proof” is infinitely long. I reject it.” As I said, provable finiteness is not something that is needed to check the validity of a proof in Nelson’s view. So your bizarre assertion that a one-line proof is infinitely long doesn’t change anything.
“I’ll back down and concede the finiteness of 1 if he will concede the finiteness of 2^billion, which he can reasonably do in light of my inductive proof that induction holds in NA.” He cannot reasonably do so, because your proof that induction holds in his system is based on induction in PA, which he sees no reason to accept.
By the way, have you taken a look at the book by Nelson I linked to earlier, Predicative Arithmetic? You might find it interesting.
Right, if you work in PA you can easily show that exponentiation is total in Nelson’s system of predicative arithmetic. But the whole goal of Nelson’s work is to prove PA inconsistent, and thus prove that exponentiation is not total.
Best of luck to him :-) However, if he succeeds in showing, within NA, that PA is inconsistent, then
1) he could construct the same proof within PA, with equal validity and importance. Why, then, cripple himself from the outset with a weaker logical system, where (for example) induction holds but is unproveable?
2) his proof that PA is inconsistent might arise because of an inconsistence in NA. Granted, this would also imply that PA is really inconsistent, but it wouldn’t mean NA is the “correct” system to use.
“I’ve already presented a proof to them. I told him if he didn’t believe me he should run the program and he’ll see the proof. He just needs a powerful enough computer.”…. The problem is, regardlesss of how powerful the computer is, for sufficiently large X and Y the program may run longer than a human lifetime, so you’ll never find out whether it terminates. So then in order to prove that X^Y is finite, you need some way to prove that the program will terminate in a finite amount of time. How will you do that?
If I want to prove that for all X,Y, X^Y is finite, you are right. However, for any specific X,Y, there exists a computer that will run the program. That’s the computer he should use. If he run the program on the wrong computer, how is it my fault if it fails to terminate? How can it invalidate the proof?
He cannot reasonably do so, because your proof that induction holds in his system is based on induction in PA, which he sees no reason to accept
granted, he could add an “induction doesn’t hold” axiom to his system, and get an interesting system where, for example,
* “There exists a finite number that cannot be expressed as the sum of 4 or fewer squares”
* “0 is not that number”
* “1 is not that number”
* “2 is not that number”
* “3 is not that number”
* (etc)
are all true.
By the way, have you taken a look at the book by Nelson I linked to earlier, Predicative Arithmetic? You might find it interesting.
I believe I would find it interesting :-) However, I haven’t had time to look at it yet :-(
Mike H:”However, if he succeeds in showing, within NA, that PA is inconsistent, then
1) he could construct the same proof within PA, with equal validity and importance. Why, then, cripple himself from the outset with a weaker logical system, where (for example) induction holds but is unproveable?
2) his proof that PA is inconsistent might arise because of an inconsistence in NA. Granted, this would also imply that PA is really inconsistent, but it wouldn’t mean NA is the “correct” system to use.” He belives that NA is consistent but PA isn’t. So he wants to prove in NA that X^Y is infinite for some specific finite numbers X and Y, thereby proving PA to be inconsistent.
“If I want to prove that for all X,Y, X^Y is finite, you are right. However, for any specific X,Y, there exists a computer that will run the program. That’s the computer he should use. If he run the program on the wrong computer, how is it my fault if it fails to terminate? How can it invalidate the proof?” The problem is, for sufficiently large X and Y, X^Y may be too big for any computer that you can practically make to finish the proof that X^Y is finite within a human lifetime. So you’ll never know directly that the proof will terminate, unless you give a proof somehow.
“granted, he could add an “induction doesn’t hold” axiom to his system,” But he doesn’t want to add it an as axiom, he wants to prove it as a theorem, thereby invalidating PA.
He believes that NA is consistent but PA isn’t. So he wants to prove in NA that X^Y is infinite for some specific finite numbers X and Y, thereby proving PA to be inconsistent.
Any proof he could construct in NA could also be constructed in PA. (If this is not so, finding (for example) finite X and Y such that X^Y is infinite in NA does not provide a contradiction to PA.)
Therefore, he doesn’t need to bother working in NA to achieve his goal – he can work in PA instead. In fact, if PA is inconsistent, it might be that he must work in PA to prove it. It may be that the only “easy to find” statement P in PA for which both P and ~P are proveable in PA all suffer from the deficiency that neither P nor ~P is proveable in NA. Then his approach will fail.
The only advantage he might find in working in NA is that working with a restricted set of axioms refines his intuition. However, it’s not in the least a logical necessary, and has other disadvantages such as the one I mentioned.