Last week, the highly distinguished Princeton Professor Ed Nelson announced a proof that the Peano axioms for arithmetic are inconsistent — and hence so is arithmetic itself. If true, this would be much bigger news than faster-than-light neutrinos. It would be bigger news than a discovery that the South had won the American Civil War. It would be far, far bigger news than a discovery that all life on Earth was intelligently designed.
There are, after all, multiple proofs that Peano Arithmetic (that is, the fragment of arithmetic described by the Peano axioms) is consistent. Among those, the simplest and most convincing (to the overwhelming majority of mathematicians) is this: The axioms of Peano Arithmetic, and therefore the theorems of Peano Arithmetic, are all true statements about the natural numbers — and a set of true statements cannot contradict itself.
Ed Nelson rejects that argument because (exempting himself from that overwhelming majority) he doesn’t believe in the set of natural numbers — or perhaps even in individual numbers when those numbers are very large. (How do you know that 810000 exists? Have you ever counted to it?)
Needless to say, this announcement — and the announcement of a forthcoming book providing details — generated more than a flurry of excitement on the math blogs — including one of my very favorite blogs, the n-Category Cafe. After Fields Medalist Terry Tao raised a specific technical objection to Nelson’s argument, Nelson showed up in the comments section to defend himself — and then Tao showed up to expand on his objections. Nelson responded, Tao re-responded, and then Nelson posted:
You are quite right, and my original response was wrong. Thank you for spotting my error.
I withdraw my claim.
Just to be clear, here: That’s Ed Nelson cheerfully acknowledging that the book-length argument he’s been painstakingly constructing for (probably) years, and which was intended to shake the mathematical world to its foundations, doesn’t work. This says so many good things about the culture of mathematics, and so many good things about the Internet, and so many good things about the way they interact (see here and here for more examples), and it says those things so eloquently, that I see no further need for comment.
(On the other hand, if you’re hungry for additional comments, the philosopher Catarina Dutilh Novaes provides some good ones here.)
The Internet’s impact on mathematics is a huge huge thing. Not quite as huge as an inconsistency in Peano Arithmetic, but huge enough to count as a marvel.
Amazing…
… however, I still find your simple convincing argument simply unconvincing.
After all, imagine trying to explain to Bertrand Russell : “The axioms of Cantorian Set Theory, and therefore the theorems of Cantorian Set Theory, are all true statements about the sets — and a set of true statements cannot contradict itself”
Why do you think the argument works for the natural numbers, but not for set theory pre-ZF?
So, it seems like this whole affair was resolved fairly quickly, but even still… how were there no major articles about it? Everyone and their mother reported about the neutrino news and there were a bunch of “Was Einstein Wrong?” claims, but I didn’t hear about this until just now. I’d have to think that seeing “Is Math Wrong?” on a headline would help sell a few papers.
Doesn’t a Princeton professor have access to a lot of smart people that can vet his work before spending years on it and announcing he has changed the world?
And can you explain for the layperson how he can seriously argue that he doesn’t believe in the set of natural numbers?
@Andy: the SET of natural numbers is transfinite. A small number of mathematicians have always worried about such things. One of the axioms of ZF is that such a set exists. It is an AXIOM because it cannot be established otherwise, it must simply be believed.
Euclid’s parallel postulate also refers to something “at infinity.” There are good reasons the be a bit chary and tentative when talking about the infinite.
Steve says:
“This says so many good things about the culture of mathematics…”
What a contrast to the culture in Economics.
@Mike H: A nice point, but Russell had a convincing rejoinder. What purported contradiction has anyone produced for PA?
Not only had he a convincing rejoinder he could point out that the set theory of the ime was not in fact carefully axiomatized, so the list of purportedly “true” statements could not be easily checked. With PA the situation is very different.
Steve’s proof is in any event probably the best you can ever get. Godel’s theorem means you won’t get a nice finitary one from first order logic (you can get one from second order logic). So you will always have to rely on something like transfinite sets. Of these surely the set of natural numbers is the easiest to credit. It would be weird to demand a proof that N exists based on the assumption that R exists for example.
You don’t know that he was cheerful when he withdrew his claim. I wouldn’t have been.
How do you know that 810000 exists? Have you ever counted to it?
This seems related to the question of, “Why do we say that 2^43112609-1 is the largest known prime, but not that ‘the first prime after 2^43112609-1 is?” Scott Aaronson answers that question in his recent excellent paper on the relevance of computational complexity theory to philosophy (p. 9).
The answer is that we have a algorithm for enumerating 2^43112609-1 that is polynomial in the length of the number being enumerated, while we do not have one for “the first prime after 2^43112609-1”.
Likewise, we have a polynomial time algorithm for producing all the natural numbers that is polynomial in the size of the number.
Just to head off some potential navel-gazing…
Steve,
I think Terence Tao is a kind of a “World Heritage Person”(by UNESCO).
<>
Ugh… this always confuses me. I’m pretty sure I can prove that if you have a finite-length proof checker (that runs in finite time) for whatever logical system you’re using for, then you can write down an unprovable statement about integers. It shouldn’t matter if it’s FOL or SOL. Is this right?
Anyway, I think Silas raises a good point. Scott Aaronson’s paper was great, and it’s right up SL’s alley.
@Silas Barta: Call that number B. We have a quantifier free closed expression for B. For the next prime we have only a logical expression containing a quantifier. Isn’t that a sharper idea of “known”?
@Ken_B: Nah, I like the computational complexity approach better.
@Silas: NP
:>
Terry Tao has counted to infinity*…twice.
*cardinality of N at least
As revolutionary as the printing press, perhaps.
@KenB whether Russell had a convincing rejoinder or not is irrelevant. In fact, the “proof” that Cantorian set theory is consistent had problems after Russell came up with his rejoinder. Likewise, Steve’s “proof” that the Peano Axioms are consistent has problems, even though nobody has a convincing rejoinder at this time – after all, it has the same logical structure as the first one. The validity of a proof does not depend on the truth of the statement allegedly proven.
If he’s willing to spell it out in a sequence of logical steps, I’ll happily point out the first flaw. I’m hesitant to do this for his half-paragraph of prose.
Steve, Edward Nelson does believe in all the natural numbers, however large, at least in the sense:
1. He believes in 1.
2. If he believes in n, he believes in n+1
3. If he believes in m and n, he believes in m+n and mn.
But what he emphatically does *not* believe in is that m^n exists whenever m and n exist. Now you or I might prove this with induction, but he doesn’t believe in it for arbitrary formulas. He thinks of natural numbers as a potential infinity, not a pre-existing set that you can apply induction to.
To get a sense of where he’s coming from, and why he’s skeptical about whether exponentiation is total, you can read his paper here:
http://www.math.princeton.edu/~nelson/papers/e.pdf
(It’s 11 pages, but the heart of it is pages 4-6)
And if you’re really adventurous, you can try wading through his magnum opus, Predicative Arithmetic:
http://www.math.princeton.edu/~nelson/books/pa.pdf
Bottom line, he’s not quite Esesin-Volpin, who as far as I can tell literally believes that there are finitely many natural numbers.
Mike H: The difference between arithmetic and set theory is this: There is a preferred model of arithmetic (the “standard model”, i.e. the ordinary natural numbers) which pretty much everyone agrees it is possible to talk about. The situation in set theory is much murkier. If we can’t talk about the natural numbers, we pretty much might as well give up talking about mathematics. But set theoretic universes are far more difficult animals to grasp, and it’s far easier to imagine a world in which they don’t exist or can’t be talked about.
Keshav Srinivasan:
Yes, I’ve actually spent some time with Nelson’s book. It’s difficult, of course, to know how much precision is appropriate for an informal blogpost.
@Ken B
“NP”
Very funny!
@Steve – so your argument is that the “natural numbers” seem natural to us, but sets don’t, therefore the argument works for the Peano axioms but not Cantorian set theory?
How do you get from “The Peano axioms are true statements about the intuitions of Homo Sapiens” to “They can’t be contradictory” ???
Mike H:
so your argument is that the “natural numbers” seem natural to us, but sets don’t, therefore the argument works for the Peano axioms but not Cantorian set theory?
Yes.
How do you get from “The Peano axioms are true statements about the intuitions of Homo Sapiens” to “They can’t be contradictory” ???
I think it’s at least pretty easy to get as far as “If the Peano axioms are contradictory then the intuitions of Homo Sapiens are so far off base that Homo Sapiens shouldn’t be trying to think about math in the first place.”
@Silas Barta
Really? Polynomial time? That’s your dividing line? First of all, there’s a constant-time algorithm for finding the next prime. You just keep adding one until you get a prime. This algorithm terminates in exactly the same amount of steps each time. (n is a bound variable, so pfft.)
Secondly, according to your criterion, we “know” what the next perfect square after that number is. That’s a rather broad use of “know”.
Re : I think it’s at least pretty easy to get as far as “If the Peano axioms are contradictory then the intuitions of Homo Sapiens are so far off base that Homo Sapiens shouldn’t be trying to think about math in the first place.”
Well, terribly few of us do try to think about math. On the other hand, terribly few of us have intuitions that are on-base, even about propositional logic (eg, “there are four cards, showing 1, 2, E and K. Which cards must you turn over….”). Whether this means we “should” be trying to do math, well, that’s a question for ethicists or metaphysicians.
I don’t see any reason for confidence that we got it right with the Peano Axioms. We’ve been wrong before.
“There is a theory which states that if ever anyone discovers the foundations of mathematics to be contradictory, they will instantly disappear and be replaced with something even more bizarre and inexplicable. There is another theory which states that this has already happened”
Mike H:
I don’t see any reason for confidence that we got it right with the Peano Axioms. We’ve been wrong before.
Well, there are the millennia of work in mathematics that rely on our intuitions about the natural numbers and have not yet yielded a contradiction. There’s that.
@MikeH & Steve: Let me fill in a step or two in Steve’s argument. A theory is consistent if and only if there is a statement in it that cannot be proved. Steve’s argument is that in PA you cannot prove the statement 1 = 2. He bases this claim on the fact that PA has a pretty obvious model, the natural numbers. In that model it is false that 1= 2. All the axioms of PA are true in this model. The rules of inference prevent you from proving false conclusions from true premises. Hence you cannot prove using PA that 1 = 2.
Steve ALSO argues — and it’s quite a different point — that if PA is wrong/inconsistent then not only do you have to trash 2000 years of math and science, you probably cannot even formulate any sensible arguemtn about anything because the natural numbers will turn out to be required in your argument.
Ken B: Thanks for this excellent comment. It summarizes exactly what I’ve been trying to say, and does a better job than I did.
Just in case someone actually believes RF:
Really? Polynomial time? That’s your dividing line? First of all, there’s a constant-time algorithm for finding the next prime. You just keep adding one until you get a prime. This algorithm terminates in exactly the same amount of steps each time. (n is a bound variable, so pfft.)
No, there isn’t a constant time algorithm for finding the next prime, because the (average/worst-case) run-time depends on the size of the current prime.
Secondly, according to your criterion, we “know” what the next perfect square after that number is. That’s a rather broad use of “know”.
Well, since your previous claim doesn’t follow, neither dooes this one (about “my” criterion).
Hi Steven,
> “If the Peano axioms are contradictory then the intuitions of Homo Sapiens are so far off base that Homo Sapiens shouldn’t be trying to think about math in the first place.”
Couldn’t that mean that the intuition is so awesome that it can’t be fully expressed by the finitistic means? And we could still derive truths by using formalism, but we’d have to be careful.
“And we could still derive truths by using formalism, but we’d have to be careful.” This is an interesting comment because it exemplifies a common misunderstanding. Mathematicians do not “derive truths by using formalism”. Using formalism is how mathematicians “be careful.”
Mathematics is not “a game with marks.” The game with marks is what mathematicians try to reduce their work to when the creative core of the work is done because this lets them and others check it more carefully, and because it helps them find ways to generalize it or align it to other discoveries, and it allows them to more easily work in stages, building upon what came before. The formalism is a TOOL. It is a pervasive tool but it is no maore mathematics than ink is literature.
If mathematics really were a game with marks it would all look like Russell’s Principia. I have never met a mathematician who has ever even read all the Principia.
Ken B, I can’t agree more that the formalism is just a tool, and I like your comparision with ink in literature.
My point is, if this tool is ever found unsound that would not stop people from doing math. Moreover, it would not stop people from using the same (or modified) formalism as a tool in math.
What I meant by “careful” was “aware of potential unsoundness”.
It’s like using software that has bugs: we are still using it, with caution.
Ken B said:
“A theory is consistent if and only if there is a statement in it that cannot be proved.”
Only if you accept “(P and not P) implies Q”.
Silas Barta said:
“No, there isn’t a constant time algorithm for finding the next prime, because the (average/worst-case) run-time depends on the size of the current prime.”
I see you’re not grasping the concept of n being a bound variable. It makes no sense to speak of run-time “depending” on the size of the current prime, when the size of the current prime is fixed. Does the value of 2+2 depend on how big 2 is? Do we get different answers for different values of 2? If I write an algorithm for finding the next prime after 2^43112609-1, then, assuming it’s a deterministic algorithm, its run-time will be EXACTLY THE SAME each time I run it. There are NO FREE VARIABLES for its run-time to depend on.
The whole point of the distinction between polynomial and exponential time is that given ANY polynomial-time algorithm and ANY exponential-time algorithm, there is some point after which the polynomial-time algorithm is always faster. But with a fixed n, an “exponential” algorithm may very well be faster than a “polynomial” one. There is no such thing as an exponential-time batch file (just as there’s no such thing as “exponentially greater”).
“Well, since your previous claim doesn’t follow, neither dooes this one (about “my” criterion).”
This claim is completely independent of my previous one. There is an algorithm that, given arbitrary k, will find the next perfect square in polynomial time. Therefore, according to your criterion, given any k, we “know” what the next perfect square is.
@RF: I do accept that P and not P implies Q” however I don’t need to. “P & -P > Q” is a statement. If there is no unprovable statement then ex hypothesi I can *prove* “P & -P > Q”.
@Ken B
I’m not clear on what you’re saying. Yes, if there are no unprovable statements, AND if “P & -P > Q” is a statement that can be expressed in your theory (not a trivial assumption), then you can prove “P & -P > Q”. But how do you know that there are no unprovable statements? It follows from you biconditional, together with the hypothesis that the theory is inconsistent, but your biconditional is the very thing in question, a question that appears to be begged.
If your biconditional is true, then in any complete inconsistent theory you can prove “P & -P > Q”. And if “P & -P > Q”, then your biconditional is true. But I don’t see how any of that establishes that your biconditional is true. Furthermore, if you’re assuming that any statement can be expressed in your theory, there’s no need to go through the step of noting that “P & -P > Q” is a statement. “The theory is inconsistent” is a statement, so it’s provable under the assumption, so that proves right there that if there are no unprovable statements, then the theory is inconsistent. Of course, a similar proof also shows that the theory is consistent.
All right, since Steve endorsed KenB’s argument, let’s pull it apart. The basic problems are
* it’s circular,
* it depends too much on observations about life on earth.
Steve’s argument is that in PA you cannot prove the statement 1 = 2.
Ok, fine so far.
He bases this claim on the fact that PA has a pretty obvious model, the natural numbers. In that model it is false that 1= 2.
It is obvious that if PA has a model (ie, it is consistent), then the natural numbers do the job. However, we don’t yet know that PA is consistent – that’s what his argumnet is supposed to establish.
The rules of inference prevent you from proving false conclusions from true premises.
This is only true if PA is consistent, which is exactly what we are trying to prove.
Hence, this argument is essentially circular, with an appeal to the nobility and clarity of human intuition thrown in. I reject it.
@bbzippo : I wrote a blog post on a point quite similar to yours. Click on my name to see it.
@Silas,RF : FYI : PRIMES is in P, so that’s not it.
Mike H:
The rules of inference prevent you from proving false conclusions from true premises.
This is only true if PA is consistent, which is exactly what we are trying to prove.
No, this is true quite independent of whether PA is consistent.
Mike H (If you’re still reading this old thread):
I’m curious as to the following: Do you reject only this particular proof that PA is consistent or do you reject all the other known proofs as well? Do you reject Gentzen’s proof? Do you reject Harvey Friedman’s various arguments?
I’m curious also as to the following: Are you equally skeptical that there exists a physical universe outside your own mind, or that there are conscious minds other than your own? Do you object to the physicists and the psychologists proceeding on the basis of these assumptions?
Steve,
> No, this is true quite independent of whether PA is consistent.
Could you explain why? How do we know PA is sound? AFAIK, even consistency does not imply soundness. It only implies Pi-soundness. The weakest sufficient condition known to me that implies soundness is 1-consistency.
Mike H, do you mean the “collect all 12” thing? Nice, I’ll leave you a comment there.
bbzippo:
The statement was
The rules of inference prevent you from proving false conclusions from true premises.
This statement is true and has nothing to do with PA.
Steve,
I’m sorry, I read it out of context. I agree that is true.
However, I don’t understand why we need to invoke this argument after we have claimed that N is a model of PA? If we agree that a model exists that should be the end of discussion, even for an ultrafinitist, I assume.
But is N a model of PA? We believe yes, based on a lot of evidence. But we don’t have any proof. “The axioms are true in N” is not a proof. We don’t know if induction is true for _all_ formulas.
@bzippo, I meant the Hitch-Hiker’s Guide thing…
@Steve : The rules of inference prevent you from proving false conclusions from true premises.
This is only true if PA is consistent,
Your criticism of this is correct, I guess I meant “The rules of inferences prevent you from proving the opposites of true statements from true premises”
However, you didn’t address the other critique of your simple proof. Only one valid critique is necessary to dismantle it.
Mike H (If you’re still reading this old thread):
I still check in from time to time
I’m curious as to the following: Do you reject only this particular proof that PA is consistent
This one. It’s circular, and appeals too much to human rationality.
or do you reject all the other known proofs as well? Do you reject Gentzen’s proof? Do you reject Harvey Friedman’s various arguments?
I’m not familiar with the details of Gentzen’s proof, so I have no reason to reject it. Clearly other people have accepted it. Note that he didn’t prove “PA are consistent”, rather “Assuming primitive recursive arithmetic with transfinite induction, then PA are consistent”. That’s fine by me, but (from a purely logical perspective) begs the question somewhat.
I’m not at all familiar with Friedman’s arguments.
I’m curious also as to the following: Are you equally skeptical that there exists a physical universe outside your own mind, or that there are conscious minds other than your own?
Note that I’m not actually skeptical that PA are consistent. I just don’t believe your proof, and with regard to other proofs, I like to know the foundations on which my logic rests. Likewise, I’m not skeptical about there being a physical universe or other minds etc etc. I believe all these things are true, and act as if they were. I entertain the logical possibility that they might be false, and I’m aware you can’t prove any of them 100% conclusively, but (like most people) I don’t let that bother me. The alternative is not particularly practical.
Do you object to the physicists and the psychologists proceeding on the basis of these assumptions?
Not in the least :-)
Mike H: I posted this higher up but am reposting because I think you’re more likely to see it here:
I’m curious as to the following: Do you reject only this particular proof that PA is consistent or do you reject all the other known proofs as well? Do you reject Gentzen’s proof? Do you reject Harvey Friedman’s various arguments?
I’m curious also as to the following: Are you equally skeptical that there exists a physical universe outside your own mind, or that there are conscious minds other than your own? Do you object to the physicists and the psychologists proceeding on the basis of these assumptions?
Apparently, I was answering while you were moving your question. See my response just above it..
Do you object to the physicists and the psychologists proceeding on the basis of these assumptions?
On the other hand, if I did regard the physical universe or other minds to be fictional or at least unknown, such an objection wouldn’t make much sense… :-)
@RF: The size of the given prime is the free variable. The relevant question is about an algorithm that takes as input a prime number (your free variable) and finds the next. You have to compare to the class of inputs to the problem, not just define the problem with respect to a fixed value.
You’re not familiar with how computational complexity problems work, are you?
If the Riemann Hypothesis is true, and if Cramer’s conjecture[1] is also true, then the problem “find the next prime after N” can be solved in polynomial time in ln(N).
However, supposing these conjectures are proven. I don’t think this means we’d want to say “the first prime after 2^43112609-1” is the largest known prime.
So I don’t think statements like “X is known” have anything to do with polynomial-time computability of X.
More evidence : we say we “know” an upper bound for Graham’s problem, even if that bound is Graham’s number, f^{64}(4), where f(N)=3^^^… N times … ^^3, which (by any reasonable definition of polynomial time in this context) can’t be computed in “polynomial time”.
References : [1] http://en.wikipedia.org/wiki/Prime_gaps#Conjectures_about_gaps_between_primes
Some more thoughts on the matter : http://www.xkcd.com/704/
Silas Barta said:
“The size of the given prime is the free variable.”
No, the size of the given prime is fixed.
“The relevant question is about an algorithm that takes as input a prime number (your free variable) and finds the next.”
We aren’t dealing with prime numbers in general; we’re dealing with a particular prime number.
“You have to compare to the class of inputs to the problem, not just define the problem with respect to a fixed value.”
The class of inputs is a singleton set. Simply because you can identify, /post hoc/, a larger class that it belongs to, doesn’t mean that you get to demand that an algorithm be supplied for that class. If I ask you whether it’s computationally feasible to factor 10, or to find a Hamiltonian path in a 4-node graph, you would look rather foolish if you were to reply that it’s not, because those problems belong to a larger classes of problem that cannot be solved in polynomial time.
“You’re not familiar with how computational complexity problems work, are you?”
You have purported to have a valid distinguishing criterion, and, as far as I can tell, you have failed to adequately define what it is. If this is what you mean by “computational complexity”, then no, I’m not familiar with how it works. It’s possible that there is in fact some valid, well-defined test that can be applied to determine whether something is “known”, and it’s possible that what you’ve posted is derived from that criterion, and it’s possible that if I were more knowledgeable and/or more intelligent, I would be able to extrapolate from what you have posted to the underlying concept that you are trying to get at, but it’s also possible that, like IDers blathering on about “specified complexity”, you have simply fooled yourself into thinking that there is a solid foundation beneath all the hand-waving.