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 
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 
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.
Downward Incompleteness
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 
Now let 
Theorem 1
The theorycan prove the inconsistency of
, but that proof is uninteresting.
The point is if
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.
Apparent Flaw
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 
Open Problems
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?
Trackbacks
- Things that are connected « Of One Piece
- What If Cantor’s Proof Is Wrong? « Gödel’s Lost Letter and P=NP
- A Really Scary Thought | Gödel's Lost Letter and P=NP
- Michael Cohen 1992-2017 and Vladimir Voevodsky 1966–2017 | Gödel's Lost Letter and P=NP
- Proving Peano Arithmetic Partially Consistent? | Gödel's Lost Letter and P=NP
In your discussion of “Downward Incompleteness” you seem to switch from the very real concerns about theories of various strengths being able to prove or not prove the consistency of other theories, to the non-problem of proving inconsistency. I’m probably missing something, but any theory can prove its own inconsistency simply by proving some statement and its negation. An inspection of which statements of the theory were needed to prove this contradiction shows which weaker theories are also inconsistent.
As for your question on what danger to mathematics this result poses – that is a very interesting question I think. I would venture to guess that even for people who are concerned with foundations (as opposed to the average working mathematician who can carry on their work regardless of PA’s existence) it would take a long time for anything to change. Wouldn’t we first throw away the theorems Nelson uses in his proof towards his contradiction? Even if we had a machine verified proof of a contradiction from axioms of PA, I would think we would use that as proof that the machine is broken rather than the axioms.
Nelson has withdrawn his claim in the comments to John Baez’s post:
http://golem.ph.utexas.edu/category/2011/09/the_inconsistency_of_arithmeti.html#c039590
I feel like I’ve seen an unwarranted amount of consideration of PA being inconsistent, so I felt the urge to get this off my chest. While the possibility of PA’s inconsistency is interesting to entertain, I also don’t think it warrants much serious discussion! Some things to consider:
Intuition: The axioms match our intuition of what properties natural numbers have.
Ordinal equivalence: Under the most rudimentary mathematical framework, PA’s consistency is equivalent to the well-foundedness of epsilon_0 (http://en.wikipedia.org/wiki/Epsilon_0). Epsilon_0 is not a particularly difficult ordering to grasp, it is easily expressed as an algorithm using Cantor normal form (http://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form). Personally, I found it pretty intuitive that epsilon_0 indeed does represent a well-ordering, even more intuitive than the PA axioms themselves.
It works: Lots of theorems can be proven with PA, and they hold true empirically. And some of the proofs are extremely long and complex: proofs that may be short in typical mathematical reasoning (say ZFC) can grow to extraordinary length when reduced to PA. As a software developer might say, we have an extraordinarily thorough test suite of the PA axioms!
Existence of stronger theories: Second order arithmetic, Kripke-Platek set theory, ZF(C), ZFC + numerous large cardinals. They all extend PA and prove it is consistent, and we haven’t found inconsistencies in these theories either (and people have tried!). One would think if PA is inconsistent, that inconsistency would quickly be “amplified” as we create stronger theories, making it easier to find any problem. But that hasn’t happened. (To me this is the most convincing argument)
All mathematical systems are inconsistent. Check here: http://kamouna.wordpress.com.
Best,
Rafee Kamouna.
Rafee Kamouna,
Your diagonal proof over looks a key issue, I believe. Let M(x,y) be the computation of the polynomial time program x on input y. You then use M(x,x) to get a diagonal argument. The trouble is that there is NO z so that M(z,x) = M(x,x). The point is that M(x,x) does not run in polynomial time. For each k there is a x so that M(x,x) takes more than
time.
Dear Prof Lipton,
I’m not considering any polynomial time computation. I constructed a contradiction in NP and not P. The Kleene-Rosser paradox can have two different encodings one used by Alice the other by Bob, and the result:
e(KR) in NP iff e(KR) not in NP
As Alice’s encoding is the diagonal and Bob’s is the complement of the diagnoal.
I’m working on the class NP, would please clarifiy your point about using P. The papers now have entered 20 months peer review.
Thanks a lot for your comment.
Best,
Rafee Kamouna.
Ed Nelson is well-known for his axiomatization of non-standard analysis by introducing the predicate st(X) – X is standard – into the usual axioms of set theory. I would have been thrilled by a proof of arithmetic being inconsistent – even more so than by a solution to the P?=NP problem. Of course in any case it’s not the end of mathematics. It reminds me of the so-called millennium bug that required modifying every single program that used a 6-digit date format. The whole computing world was supposed to collapse on 1/1/2000…
Inconsistency of arithmetic is quite related to the P?=NP problems. As a proof of P=NP can be followed by a correct proof of P not equal NP. Wishful thinking made many people avoid attempting this conjecture.
Without even supposing PA inconsistent, one could also try to transform – by means of the Curry-Howard isomorphism – any alleged proof that P!=NP into a program that solved SAT in polynomial time. 🙂
This is because the P/NP question is meta-mathematical. It asks something about itself, i.e. self-referential. The P/NP question is a question in NP.
Rafee,
The fact that there are many people who claim to have proved that P!=NP and many people who have claimed to have proved that P=NP is evidence that the Peano axioms are inconsistent or that something weird is going on with the P vs NP problem that doesn’t happen with other famous problems.
NP-complete problems don’t provide any information about their own difficulty and this lack of information is vital to the consistency of arithmetic. If these problems said more about themselves, it would yield both a polynomial-time algorithm to solve them and a proof that no such algorithm can exist. In other terms: “PA consistent” implies “P=NP undecidable”.
Serge,
Could you give me more information about what you are thinking? I very curious about this. Also, I found this interesting paper last night: http://www.comp.nus.edu.sg/~zirui/unlikely.pdf
Re: Truth vs. Proof: if PA is inconsistent, then theorems about the natural numbers (like Fermat’s little theorem) don’t even make sense: there is no such thing as the set of natural numbers (at least not the way we know it today). This is simply because the set of natural numbers, as we know it, forms a model for PA, so its existence proves CON(PA).
You asked, “What theory do you use to prove that your theories are inconsistent?” This is probably a misconception of what the speaker was doing (or attempting to do). Inconsistency proofs generally don’t proceed by trying prove the theorem “T is inconsistent” inside some fixed theory. Instead, they derive contradictions directly, using reasoning that can be seen to be formalized in T.
Most ordinary mathematical reasoning has the nice, flexible property that it can be formalized in a variety of different theories. That is probably why the speaker didn’t bother to state up front what theory he was working in. The reasoning he used, once understood, could probably be formalized in a variety of different theories, thereby simultaneously demonstrating that all of them are inconsistent. Another way to say it is that he’s teaching you an algorithm to generate contradictions in those theories. As long as you understand how to implement the algorithm, and you run the algorithm to get the contradictions explicitly, it doesn’t matter if you “thought” he was reasoning in some theory that is now known to be inconsistent. The explicit derivation of 1=0 from T is there for anybody to see on the computer printout.
In contrast, the approach of fixing a theory T1 and proving, on the basis of T1, the theorem “T2 is inconsistent,” doesn’t immediately yield any inconsistency statements unless you further assume that the axioms of T1 are true. For example, if while reasoning within PA, you derive the theorem “PA is inconsistent” (but don’t directly derive the theorem “1=0”), then this does not automatically lead to an explicit contradiction in PA. Indeed, by Goedel’s second incompleteness theorem, “PA is inconsistent” can be safely added to the axioms of PA without fear of generating a contradiction (unless PA itself already proves “0=1”).
“Is PA consistent? If it is not, how do we go and see which “theorems” are true and which are not?”
(i) For a finitary argument to the effect that PA is, indeed, consistent see Theorem 6 in:
http://alixcomsi.com/30_Finitary_Logic_PA_Update.pdf
(ii) For an argument that—contrary to accepted dogma—the standard interpretation of PA does not yield a model of PA, see Corollary 6 in the above ms.
(iii) For an argument that PA is not omega-consistent, see Corollary 5 in the above ms.
I suspect that Professor Nelson’s argument appeals to (or establishes) either (ii) or (iii) at some stage (it can be shown that the two are equivalent), from which he might—mistakenly but naturally—conclude that PA must be inconsistent since both (ii) and (iii) appear to be intuitively ‘true’.
For an argument that intuition may be deceiving us subtly, and that there is, indeed, a finitary interpretation of PA that establishes PA as categorical, see Corollary 3 in the above ms.
What most impressed me in this episode was Ed Nelson’s timely, polite, and graceful response to Terry Tao’s critique:
Twenty words that reflect every aspect of professionalism.
Dear Prof Lipton,
Why do you need polynomial time computations in my diagonal argumemt?
Craig,
NP-complete problems have the property of simulating in polynomial time any other problem in NP, but the price for such versatility is a total lack of information about their own complexity. At first sight the cases “P=NP” and “P!=NP” look rather symmetrical. As I’m found of the proof-program correspondence I wondered – like Rafee – if they’re not equivalent after all, and thus evidently false.
The paper you found last night is similar in spirit to the one by Ben-David and Halevi (see this: http://www.cs.uwaterloo.ca/~shai/P%20vs%20NP-2.ppt and this: http://www.cs.technion.ac.il/~shai/ph.ps.gz). In my opinion they don’t make it less likely for P=NP to be independent of ZFC, on the contrary. If there are infinitely close to polynomial-time algorithms for SAT, the length of such algorithms tends to infinity as they get closer to polynomial time. By passing to the limit, in a non-standard model of PA you can have an algorithm of infinite non-standard length that solves SAT in polynomial time.
And if there indeed is a symmetry between the two options, you can even imagine a non-standard infinite length proof that P!=NP. 🙂
Serge and Rafee,
Can you explain in “layman’s” terms what you mean? For instance, I don’t follow Serge’s statement that, “Without even supposing PA inconsistent, one could also try to transform – by means of the Curry-Howard isomorphism – any alleged proof that P!=NP into a program that solved SAT in polynomial time.”
It was intended as a joke based on intuition. Sometimes you can see things without being able to explain them technically. In case you’re curious about the Curry-Howard correspondence I suggest that you take a look at Jean-Louis Krivine’s page:
http://www.pps.jussieu.fr/~krivine/
I especially like the paper (in French): “A formal and intuitionistic proof of the completeness theorem of classical logic”. In it he shows how this theorem can been viewed as a kind of decompiler.
Like Rafee I believe Peano’s axioms are too weak to prove that P=NP is independent of them. Peano invented this simple tool for doing arithmetic, not for reasoning about the duration of computer processes. In view of the Curry-Howard correspondence such a purpose is self-referential and therefore clearly out of reach, as was the independence of the continuum hypothesis at the time of Cantor.
Dear Craig,
My proofs at http;//kamouna.wordpress.com are simple one-step arguments. If you don’t understand anything in the papers, please tell me and I shall try to clarify. In the above Prof Lipton asked why I didn’t consider polynomial time in my diagonal argument and I answered him.
Best,
Rafee Kamouna.
Rafee,
I didn’t understand your argument but I’d like to. Do you have an email address?
Yes, I have: rafee102000@yahoo.com
best,
Rafee
The Peano axioms are not only inconsistent, but badly flawed as well. Click here:
http://math.stackexchange.com/questions/186506/consistency-of-peano-axioms-hilberts-second-problem
and scroll down to my post. The result that you will find there is both simple and irrefutable.
Don Blazys.
I can’t find your name, but I assume you’re referring to the conclusion drawn from Stepien’s “proof” that Peano arithmetic is consistent in itself (and therefore inconsistent). But looking at the document, I saw that there isn’t any proof. It just says “elementary and combinatorial” with a reference to a book from 1931.
It seems your result is based on an urban legend.
Dear Collin237
I recommend you (and to Other Debaters here), to read the paper: T. J. Stępień, Ł. T. Stępień, “On the Consistency of the Arithmetic System”, Journal of Mathematics and System Science, vol. 7, 43 – 55 (2017), arXiv:1803.11072 .
Inconsistency of PA by proving both the Goldbach conjecture and its negation:
https://www.academia.edu/37705962/_pk_mk_qk_or_an_Unexpected_Inconsistency
The above result is based on this elementary argument:
We define the set S_g := { (pk, mk, qk) | k, m in N; p, q in P_3, p
Inconsistency of PA by proving both the Goldbach conjecture and its negation:
https://www.academia.edu/37705962/_pk_mk_qk_or_an_Unexpected_Inconsistency
The above result is based on this elementary argument:
We define the set S_g := { (pk, mk, qk) | k, m in N; p, q in P_3, p
The text in my post above has been truncated when uploading. I send it once again:
We define the set S_g := { (pk, mk, qk) | k, m in N; p, q in P_3, p
Once again, it appears truncated. Who is interested in that summary, may contact me by email. The email address is contained in the original document https://www.academia.edu/37705962/_pk_mk_qk_or_an_Unexpected_Inconsistency
Once again, the text appears truncated. Who is interested in that few lines summary, may contact me. The email address is contained in the original document
https://www.academia.edu/37705962/_pk_mk_qk_or_an_Unexpected_Inconsistency