68

At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say:

Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel axioms for set theory are necessarily even consistent. Indeed, we’re somewhat doubtful whether large natural numbers (like $80^{5000}$, or even $2^{200}$) exist in any very real sense, and we’re secretly hoping that Nelson will succeed in his program for proving that the usual axioms of arithmetic—and hence also of set theory—are inconsistent. (See Nelson [E. Nelson. Predicative Arithmetic. Princeton University Press, Princeton, 1986.].) All the more reason, then, for us to stick with methods which, because of their concrete, combinatorial nature, are likely to survive the possible collapse of set theory as we know it today.

Here are my questions:

What is the status of Nelson's program? Are there any obstruction to finding a relatively easy proof of the inconsistency of ZF? Is there anybody seriously working on this?

Kaveh
  • 5,362
Andreas Thom
  • 25,252
  • 9
    Note that on the first page footnotes, Doyle says about Conway $$ $$ But he has never approved of this exposition, which he regards as full of `fluff.' – Will Jagy Aug 25 '10 at 21:50
  • 22
    A central obstruction to finding an "easy" proof of the syntactic inconsistency of ZF is that nobody has managed to do it in 80+ years, and not for lack of trying. More recently, there was fear (or hope) that large cardinals might be useful for finding inconsistencies in ZF, but that idea hasn't panned out either. Arithmetic is even worse: there are multiple, unrelated consistency proofs for arithmetic, so it would be remarkable to find a syntactic inconsistency there. – Carl Mummert Aug 25 '10 at 21:55
  • 7
    This is not a disagreement with what Carl Mummert says but it is worth remembering that when Zermelo first proposed his axioms for set theory, there was considerable scepticism that they really would avoid contradictions. People like Bertrand Russell, Philip Jourdain and Henri Poincaré criticised his axioms. Russell wrote that "I suspect that his axioms will not really avoid contradictions, i.e., I suspect new contradictions could be manufactured specially designed to be consistent with his axioms." [quoted on p. 91 of Ebbinghaus's biography of Zermelo http://tinyurl.com/2fskff7 ] – Marko Amnell Aug 26 '10 at 07:50
  • 2
    http://www.math.princeton.edu/~nelson/papers.html – Kaveh Aug 26 '10 at 09:20
  • 8
    Note that the question states that Nelson's program is about the consistency of arithmetic. So there is even more than 80 years of work that did not come up with inconsistencies.

    The Russell quote by Marko Amnell is interesting. If you change "contradictions" to "undecidable statements" you get a prediction of the incompleteness theorems. And I would guess that the incompleteness phenomenon is something that Russell wouldn't have thought of at that time.

     – Stefan Geschke Aug 26 '10 at 10:41
  • I am a PhD student working in Computational Complexity Theory and Formal Languages. I come from a background in mathematical logic. I seriously work on this not because I want to prove that the first order system of Zermelo–Fraenkel Set Theory is inconsistent, but rather because I really value syntactic formulations of languages. One thing I investigate is self-referential properties of languages. – Michael Wehar Sep 14 '14 at 00:52
  • If anyone else is interested in working on this, please let me know. I personally feel that there is a lack of interest in studying syntactic properties of logic systems at the current moment. However, I think that there is a lot of progress to be made and there could be potential applications.

    Personally, I think that even if ZF were inconsistent and someone found a proof, it would be quite difficult to convince anyone else.

     – Michael Wehar Sep 14 '14 at 00:52
  • 2
    @MichaelWehar, what do you mean by "syntactic properties of logic systems?" I think there's a huge amount of interest in at least what I would mean by that. – Noah Schweber Sep 14 '14 at 08:19
  • Hi Noah, thanks for your reply. I would really like to discuss further with you and provide you with an appropriate response to your question. In stackexchange comments I am slightly limited so here is the short and vague version that you should be skeptical of. Answer: I am referring to the structure of terms/formulas, string manipulations, grammars, encodings, and complexity. Some relevant topics in logic: proof systems as grammars, computational problems with schema, proof lengths/weights/complexities, human usability with interactive systems, non-standard syntax, and self-reference. – Michael Wehar Sep 15 '14 at 02:21
  • I was under the impression that some of these topics are not too popular anymore, but if I am mistaken, please let me know. I'm looking to meet others to talk and collaborate with. :) – Michael Wehar Sep 15 '14 at 02:34
  • TBH I'm not sure how a finite set or a small natural number exists "in any very real sense". – sfmiller940 Jul 26 '19 at 22:12
  • @sfmiller940, do you agree that $5$ exists in a "more" real sense than $10^{800}$? – Andreas Thom Jul 29 '19 at 09:01
  • @AndreasThom Not really :) How about the empty set? Is the empty set "more" real than the natural numbers? – sfmiller940 Jul 29 '19 at 22:30
  • @sfmiller940 If there is no difference for you (which is fair enough), then there is indeed no point in this discussion. – Andreas Thom Jul 30 '19 at 11:08

4 Answers4

29

Edward Nelson passed away at age 82 on September 10, 2014. You can read a tribute to Nelson's illustrious career from Princeton University.

Although he worked on the inconsistency of PA until the end, there were no standing claims to a proof of the inconsistency of PA at the time of Nelson's unfortunate passing.

On September 30, 2015, Nelson's unfinished manuscripts titled Inconsistency of Primitive Recursive Arithmetic and Elements have been posted on the arXiv, with a foreword by Sarah Jones Nelson and an afterword by Sam Buss and Terry Tao.

François G. Dorais
  • 43,723
25

Nelson claimed to have succeeded just now.

http://www.math.princeton.edu/~nelson/papers/outline.pdf

I hope consensus about this forms soon, so I can know what to do with the rest of my life. If only I had been born a few years later, I wouldn't be put into the position of worrying that my chosen career path is doomed and I must go build houses or something.

Update:

As per Michael's comment, the claim has been withdrawn.

Logan
  • 103
Monroe Eskew
  • 18,133
  • See http://www.matthewbcrawford.com/ – Will Jagy Sep 27 '11 at 03:43
  • Also http://www.richardsennett.com/site/SENN/Templates/Home.aspx?pageid=1 – Will Jagy Sep 27 '11 at 03:45
  • 1
    Maybe I'm missing something but what do the above two links have to do with the topic? – Opt Sep 27 '11 at 04:07
  • 3
    @Sid: I think Will is, in his idiosyncratic way (no offence meant) riffing on the last sentence of mbsq. – Yemon Choi Sep 27 '11 at 04:59
  • Yemon, yes, I was going along with the comic element introduced by mbsq. Still, if I had felt that msbq were actually worried about the future, I would not have posted anything. Finally, the Crawford book is pretty good. – Will Jagy Sep 27 '11 at 06:50
  • 1
    Nelsons article links to a book he is currently writing on the topic: http://www.math.princeton.edu/~nelson/books/elem.pdf – Michael Bächtold Sep 27 '11 at 11:29
  • "The latter derives a contradiction from the consideration of proofs of an entirely unrestricted kind, whereas the former derives a contradiction from the consideration of proofs of quite specific kinds, of bounded complexity." I don't see why this is true. His proof depends on welding together 2^l proofs, to make one large proof. This cannot be done in bounded complexity. – Will Sawin Sep 28 '11 at 03:39
  • @Will Sawin: $l$ is supposed to be a fixed constant in the argument. Anyway, I came to the same conclusion as Terence Tao that Nelson’s proof is faulty, see http://golem.ph.utexas.edu/category/2011/09/the_inconsistency_of_arithmeti.html#c039553 . – Emil Jeřábek Sep 29 '11 at 13:17
  • 6
    It seems Nelson has withdrawn his claim. In any case I'd like to point out that the first section of chapter 1 of his (unfinished) book on the subject (math.princeton.edu/~nelson/books/elem.pdf, "Potential vs. actual infinity") still stands. I find it to be a great motivation for his search, regardless of the outcome. – godelian Oct 01 '11 at 15:40
  • 24
    the claim was withdrawn: http://golem.ph.utexas.edu/category/2011/09/the_inconsistency_of_arithmeti.html#c039590 – Michael Bächtold Oct 01 '11 at 15:41
17

This is perhaps an obvious remark, but it may be helpful for those who haven't yet gotten used to the fact that one must think about consistency questions slightly differently from how we think of "ordinary" mathematical questions. Namely, let us ask what an "obstruction to finding an inconsistency in ZF" might look like? The obvious "obstruction" would be a proof that ZF is consistent. But we can't expect to find such a thing, by Goedel's 2nd incompleteness theorem. Therefore, we cannot hope to find a mathematical obstruction in the usual sense.

Timothy Chow
  • 78,129
  • 2
    I do not think I properly understand this comment. By the 2nd IT you cannot expect to prove Con(ZFC), providing ZFC is consistent. But in case you do not believe in consistency of ZFC you are not forbidden (at least by 2nd IT) to hope to show that $ZFC\vdash Con(ZFC)$. (This is not that I do not believe in consistency of ZFC, I just do not understand the argument.) – Rafał Gruszczyński Jan 25 '13 at 15:07
  • 2
    If you show that ZF⊢Con(ZF) then it immediately follows that ZF is inconsistent, by Goedel's 2nd. That is, far from finding an obstruction to finding an inconsistency in ZF, you've actually found the exact opposite, namely an inconsistency in ZF. Probably you're so used to thinking that a proof of something in ZF tells you that it's true that you are misled into thinking that showing that ZF⊢Con(ZF) would show that ZF really is consistent. But in fact ZF⊢Con(ZF) shows exactly the opposite, that ZF is really inconsistent. – Timothy Chow Jan 25 '13 at 16:52
  • 1
    But this is exactly my point - if you want to prove inconsistency of some axiomatizable theory $T$ extending, say Peano Artihmetic, show $T\vdash Con(T)$ and apply Goedel's 2nd. And my point is that you cannot hope to prove such a thing ONLY IF you believe in consistency of $T$. Otherwise, why not to look for a proof of $Con(T)$ within $T$ itself to demonstrate $T$ is flawed. Actually, I do not believe that this would be the easiest way to prove $T$'s inconsistency, but at least a possible way. – Rafał Gruszczyński Jan 26 '13 at 08:19
  • O.K., I think I see your confusion. When I said "a proof that ZF is consistent," I meant an ordinary mathematical proof, of the type you read in journals and find yourself persuaded by. I did not mean a formal proof of Con(ZF) from the axioms of ZF. As you say, the latter is something that a skeptic about ZF might hope to discover. But neither the skeptic nor the believer can hope to find a proof that ZF is consistent in the sense that I intended it. – Timothy Chow Jan 27 '13 at 03:38
  • But you mean a proof like that by methods available in a theory not stronger that ZF(C)? – Rafał Gruszczyński Jan 28 '13 at 07:24
  • 1
    I mean a proof by whatever methods the skeptic accepts as establishing mathematical truths. – Timothy Chow Jan 28 '13 at 15:22
7

I cannot judge how serious these are, I just put Nelson predicative arithmetic in Google and came up with lots of stuff:

Link

"at the Nelson meeting in Vancouver in June 2004." http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.478 "This paper starts by discussing Nelson’s philosophy of mathematics, which is a blend of mathematical formalism and a radical constructivism. As such, it makes strong assertions about the foundations of mathematic and the reality of mathematical objects."

http://math.ucsd.edu/~sbuss/ResearchWeb/nelson/

http://www.illc.uva.nl/Publications/ResearchReports/X-1989-01.text.pdf

This one is skeptical: Link

Glorfindel
  • 2,743
Will Jagy
  • 25,349