What If Peano Is Inconsistent?
What can we learn from near-death experiences of theories?
Ed Nelson is a senior professor in mathematics at Princeton. Years ago he claimed, for a while, a proof that . Now he claims, as reported by John Baez, that Peano Arithmetic (PA) is inconsistent—see this.
Today I want to just give a pointer to John’s post on this topic.
As he says:
It’s a long shot, but I can’t resist saying a bit about it.
I will leave the discussion of the proof and whether it is correct to The -Category Café. Please go there for the thoughtful discussion of the main ideas, and great comments; or add your thoughts to the discussion there. It has raised, I believe, two issues that are independent—bad pun—of whether Nelson is right or not.
This is not the first time that a researcher has claimed that PA is inconsistent, nor do I expect it to be the last. But it is important, I believe, that people think about these hard questions. And I am happy to see a serious attempt, whether it succeeds or not.
I once was at a talk on a “proof” that even more than PA was inconsistent, even seemingly weaker theories. One question that occurred to me, which I decided not to ask the speaker out of politeness, was:
What theory do you use to prove that your theories are inconsistent?
It seemed like he was using PA to prove that these sub-theories were inconsistent. This did not seem right to me.
Suppose that is a mathematical theory. We know from Kurt Gödel’s famous Second Incompleteness Theorem that if is powerful enough, then the consistency of cannot be proved by . Note, even this simple statement must be treated carefully, since Gödel’s theorems depends on defining consistency in a reasonable manner. See this famous paper by Solomon Feferman, and more recently this MathOverflow item for a discussion of this delicate issue.
Now let be another theory. If is contained in , then of course cannot prove the consistency of . However, suppose that is contained in —it may be a weaker theory. Then consider this possibility:
The theory can prove the inconsistency of , but that proof is uninteresting.
The point is if is inconsistent, then it proves all statements, true or false ones. Thus, this proof says nothing about .
The point is that even if Nelson could show in PA that PA is inconsistent, I do not think that he can extend that to prove a weaker theory is also inconsistent. At least not in meaningful way.
Truth vs Proof
Suppose that Nelson is right. What does that say about the zillions of theorems that have been proved in PA? What will happen? Is it the end of mathematics?
My one point is that we need to make a distinction between a theorem being true and a theorem being proved. They are not the same.
Take Fermat’s Little Theorem: one of the basic results of number theory. Whether PA is correct or not, I believe this theorem is true.
There are several reasons why I believe that. Perhaps the strongest is that everyday millions of uses of this theorem happen, since it is used in cryptography by RSA, for example. If there were problems with the theorem, it seems plausible that the theorem would have failed by now, and that we would know about it. But it seems to be fine.
Terence Tao, as he has often done in the past and with the incisiveness of his wonderful blog, has articulated an evident conceptual flaw, here in comments in John Baez’ post. Nelson’s argument involves iterating through different sub-theories of PA, each purported to have Kolmogorov complexity bounded by . The problem is that there are only binary strings of length up to that could possibly serve as Kolmogorov descriptions of these theories. Hence even though all the theories are conceptually related and collectively have a description much smaller than , one individual theory by itself must have Kolmogorov complexity that is greater than . This is evidently enough to spoil the delicate reasoning in Nelson’s argument.
Is PA consistent? If it is not, how do we go and see which “theorems” are true and which are not?
If Nelson is right—or if his proof idea can be made to work for some other strong theory—this could be a huge undertaking that will keep us all busy for years.
If Nelson’s argument is un-fixably wrong, does it at least help us learn about new and interesting “paradoxes”? What does this tell us about the fine balance of proof and truth?