Monday, 3 October 2011

The (in)consistency of PA and consensus in mathematics

(Cross-posted at NewAPPS)

Last week, the foundations of mathematics community was shaken by yet another claim of the inconsistency of Peano Arithmetic (PA). This time, it was put forward by Edward Nelson, professor of mathematics in Princeton, who claimed to have found a proof of the inconsistency of PA. A few months ago, quite some stir had been caused when Fields medalist V. Voevodsky seemed to be saying that the consistency of PA was an open question; but Nelson’s claim was much more radical; he claimed to have proved that PA was outright inconsistent! (Here is a great post by Jeff Ketland with a crash-course on PA and a discussion of ways in which it might be inconsistent.)

Nelson announced his results on the FOM mailing list on September 26th 2011, providing links to two formulations of the proof: one in book form and one in short-summary form. Very quickly, a few math-oriented blogs had posts up on the topic; we all wanted to understand the outlines of Nelson’s purported proof, and most of us bet all our money on the possibility that there must be a mistake in the proof. External evidence strongly suggests that PA is consistent, in particular in that so many robust mathematical results would have to be revised if PA were inconsistent (not to mention several proofs of the consistency of arithmetic in alternative systems, such as Gentzen’s proofs -- see here).

Indeed, it did not take long for someone to find an apparent loophole in Nelson’s purported proof, and not just someone: math prodigy and Fields medalist Terence Tao (UCLA), who is considered by many as the most brilliant mathematician currently in activity. The venue in which Tao first formulated his reservations was somewhat original: on the G+ thread opened by John Baez on the topic. (So those who dismiss social networks as a pure waste of time have at least one occurrence of actual top-notch science being done in a social network to worry about!) At the same time, Daniel Tausk, a professor of mathematics at the University of São Paulo, had identified the same mistake in Nelson’s argument, and alerted Nelson of the problem in private communication. Judging from his replies (which can be read in the FOM archive as well as in The n-Category Café post), Nelson did not immediately understand the objection, but within a few days consensus had emerged that the mistake identified by Tao and Tausk was irreparable. Then, on October 1st, Nelson graciously acknowledged the correctness of the objections and withdrew the claim of having a proof of the inconsistency of PA. As has been remarked by many commentators, it is certainly a sign of mathematical greatness to acknowledge one’s own mistakes so promptly!

While it must have taken true mathematical insight to see what was wrong with the purported proof, once the mistake was spotted, it was actually not overly difficult to understand – if not in all its technical details, which presuppose a good understanding of Chaitin’s theorem, at least in its basic idea: it was based on the unwarranted assumption that the hierarchy of sub-theories built for the proof is going to map neatly into the hierarchy of the Kolmogorov complexity of each of these sub-theories. In the game of mathematics, tacitly relying on assumptions is not a good move, even less so when it turns out that the assumption is false.

From the point of view of the social practice of mathematics, this episode raises a number of interesting questions, which can be framed from the point of view of Jody Azzouni’s insightful analysis of how and why mathematics is unique as a social practice. Azzouni argues that mathematics is one of the most homogeneous groups of human practices around, and in particular one which seems particularly favorable for the emergence of consensus. Indeed, mathematicians virtually always agree on whether a purported proof is or is not a valid mathematical proof; it may take a while for enough members of the community to understand its details (as with Deolalikar’s purported proof of $P \not= NP$ last year, but this was mostly because the latter was rather poorly formulated), but past this initial period, consensus virtually always emerges. (To be clear, there can be disagreement on whether a proof is elegant, interesting etc., but not as to its correctness and incorrectness.) This remains a very puzzling feature of mathematical practice, which at least to some people suggests that Platonism is the only plausible philosophical account of mathematical truth.

The swiftness with which consensus emerged as to what was wrong with Nelson’s purported proof is yet another example of the strong tendency towards consensus in mathematical practice – and arguably, it cannot be fully explained as a merely socially imposed kind of consensus, due to homogeneous ‘indoctrination’ by means of mathematical education. That it only took a few days for consensus to emerge naturally also depends crucially on the technologies of information dissemination currently at our disposal – mailing lists, home-pages, blogs, social networks; but more generally, the episode has been a dramatic but classical occurrence of a well known pattern in mathematics as a social practice.

The comparison with another dramatic claim, put forward for the first time more than 80 years ago, may prove to be informative. Indeed, the reception of Gödel’s incompleteness results (which has been extensively studied by Dawson and Mancosu, among others) also illustrates the emergence of a consensus, but this time it favored the highly surprising claim being put forward; in last week’s episode, by contrast, the highly surprising claim has been refuted.

In September 1930, Gödel made the first public announcement of his incompleteness result. In first instance, he had proved only the first incompleteness theorem, and as is well known, from the first theorem the second incompleteness theorem was proved independently by Gödel himself and by John von Neumann. But von Neumann was one of the few who immediately understood the result (Bernays and Carnap seem to have struggled); in fact, he may have been the first to see the far-reaching consequences it had. In particular, while Gödel was still rather cautions regarding the impact of his results for Hilbert’s program, von Neumann immediately drew the right conclusions. However, quite a few mathematicians were so taken aback by Gödel’s results that they were convinced that there must have been a mistake somewhere in the proof; just as in last week’s episode, many of them set out to find out the ‘loophole’ in Gödel’s proof, but on that occasion to no avail. As narrated in this wonderful paper by P. Mancosu, the news of Gödel’s results quickly spread, but in the absence of the WWW or similar platforms, many people did not have immediate access to off-prints of the paper where the results were presented. For example, before seeing the actual results in detail, mathematician Leon Chwistek suspected that Gödel’s proof would be based on misunderstandings, but once he read the actual paper, he stood corrected:

In my last letter I have raised some doubts concerning Dr Gödel’ s work that have completely disappeared after a more attentive study of the problem. I had at first thought that there was a tacit introduction of non-predicative functions which makes the use of a rigorous symbolical procedure impossible and I even feared the possibility of an antinomy. Now I see that this is out of the question. The method is truly wonderful and it fits pure type theory thoroughly. (Letter to Kaufmann, in Mancosu 1999, 44)

Both the consensus that eventually emerged concerning the correctness of Gödel’s surprising results, and the consensus swiftly established as on what was wrong with Nelson’s purported proof last week are examples of the amazing and quite unique tendency to converge towards consensus in mathematical practice. In many senses, the most pressing task for the philosophy of mathematics, practice-based or otherwise, is to formulate a satisfactory account of this almost eerie fact about mathematics.


  1. It would be interesting to also contrast these two episodes with the recent P != NP "proof" that got some press...

  2. @Seamus, it would indeed, but I'm afraid it's not going to be done by me... I haven't followed the P != NP controversy from very close last year, and the topic is too far removed from the areas I feel confident I'll be saying something sensible on.

  3. I suspect that history (ie people) tend to remember episodes where the surprising suggestion turns out to be true better than when the surprising claim turns out to be false.

  4. It's amazing how someone can come along and in a matter of minutes falsify a proof which must have taken Nelson hundreds of man hours to construct.

    And should the original claim have been less bold and more carefully checked before publishing to avoid humiliation and publicity?

  5. Great post! As a mathematician, I find the relative ease of consensus wonderful and mysterious.

    Maybe I'm reading too much into your words, but it seems like you would argue that consensus in mathematics is both easier and swifter than consensus in other sciences like, say, physics. Yet the eventual arrival at consensus is an important feature of physics as well. (For the sake of argument, let's ignore those speculative parts of physics that haven't yet made contact with experiment, and focus on a subfield where theory and experiment see constant interplay, such as condensed matter.)

    It is understandable that consensus in physics would take longer than mathematics: it is an experimental science, and experiments take time. But are there any qualitative differences in consensus in physics, once it is reached, from consensus in mathematics?

  6. "who is considered by many as the most brilliant mathematician currently in activity."

    No serious professional mathematician would accept such a description of any mathematician.

  7. ""who is considered by many as the most brilliant mathematician currently in activity."

    No serious professional mathematician would accept such a description of any mathematician. "

    Funny. I thought Bernoulli believed such a thing about Newton.

  8. With regard to you final paragraph on the "most pressing task for the philosophy of mathematics", I can sympathise with that thought, and yet a huge amount of effort has already been devoted to it. Alongside the justification of formalisms by more orthodox philosophy of mathematics, on the practice-based side we have, say, Ken Manders on the control afforded by Euclidean diagrammatic reasoning in 'The Euclidean Diagram' (1995) and Colin McLarty in Voir Dire in the case of mathematical progress describing the advent of shared means of rigorous expression in the twentieth century.

    To my mind, an equally or more pressing task is to understand the kinds of slowly emerging consensus that occur as to what directions a field of mathematics should take. With the very light constraints afforded by logical correctness or empirical adequacy, there's some explaining to do.

  9. @John,
    Indeed, it seems to me that there is a stronger tendency towards consensus in math than in, say, physics, but that's ultimately an empirical claim of course (the 'sociology' of each of these fields). And it's precisely the fact that math is not an experimental science that makes consensus even more puzzling: there isn't anything like, you know, the physical world, to keep mathematical practice in check!

  10. @David,
    I guess I should have said "the most pressing task for the philosophy of mathematics ... REMAINS to formulate a satisfactory account...". You are absolutely right that there has been a lot of work on the topic, but to my mind it is still essentially an open question.

    The higher level question that you mention, i.e. the directions a field of mathematics should take, is definitely also very interesting, but certainly just as hard or even harder! :)

  11. What exactly is it that you find so mysterious about the strong tendency towards consensus? A naive answer might be that we have a clear notion of what a proof is, and therefore a watertight test that we can apply to claims of mathematical correctness. To the objection that fully detailed and rigorous proofs are never in practice written out, I would answer that mathematicians are trained to know how to take any part of a mathematical write-up and, if it is correct, expand it into something more formal and detailed -- a process that can be iterated if necessary. Experts in different areas get a feel for what is likely to be true in their area, so if an incorrect proof appears, and is of a sufficiently important result, they will usually (but not always) know which part needs to be clarified. Surprisingly often, the mistake is a simple unjustified assertion that the author mistakenly thinks is obvious and a more sceptical reader doesn't find obvious at all.

    I'm curious to have a more detailed formulation of what the real philosophical problem is here. What is unsatisfactory or incomplete about the account (or some modest expansion of it) that I've just given?

  12. What about the objection that the proof itself requires a proof and so on ad infinitum. Why is that objection not justified?

  13. So, accepting Tim Gowers' description of mathematical practice as I do, perhaps there's a question as to why it was possible for the various branches of mathematics to reach the condition he describes. The advent of today's standards of rigour came piecemeal, some branches taking much longer than others. And you can see reactions to the perceived threat of losing the control that it affords in Jaffe and Quinn's concerns about the influx of research by physicists such as Edward Witten.

    That ultimately just about all of mathematics can be rendered in a single and, so far as we can tell, consistent system, ZFC, must tell us something. But the kinds of ways of knowing that there's something fishy in a proposed proof operate at a higher level than that. You can find out quite a lot about this intuition from the Tricki. Category theory also provides a higher-level support.

  14. I sometimes say that philosophy is about 'questioning the obvious'. So while the phenomenon of consensus in mathematics may appear to be fairly unproblematic, especially for those who experience it from within (i.e. professional mathematicians), if you think about mathematics as a body of human practices, I'd say it's quite astonishing. As Azzouni argues in the paper I link to above, in terms of institutionalized human practices, mathematics is quite unique in terms of its tendency towards consensus.

    One can of course argue that this is a product of clear and precise standards, which are transmitted and perpetuated through education. But the comparison with other fields of scientific inquiry can be illuminating here. Take biology, for example: even though (almost) everybody agrees that evolution is the right framework, there is a lot of disagreement on the details: gradalism vs. non-gradalism, adaptationism vs. by-product accounts etc. It's not obvious in which ways education in biology would not be as conducive to consensus as education in math, and yet the situations seem very different.

    And to say that we have a clear, rigorous notion of what a proof is is only the beginning of an answer anyway. As suggested above by David, the emergence of the current standards of what counts as a correct, rigorous proof was a long and winding process. Moreover, while these standards seem widely and unanimously endorsed on the level of practices, i.e. tacitly, a theoretical/philosophical account of what a mathematical proof is is still largely an open question. Typically, a mathematician can tell whether a given purported proof is a 'good proof' or not (as in the case discussed above), but she or he would be hard-pressed to offer a definition of what a mathematical proof is ("I know one when I see one.")

    I realize that these questions may sound pedantic and unnecessary from the point of view of mathematical practice, but that's just philosophy, questioning the obvious...

    1. Catarina offers an interesting contrast between the achievement of consensus in mathematics and in empirical science, namely in biology and evolutionary theory. Education in biology and education in mathematics prepares both sets of researchers for speaking the same ‘language’, i.e., mastering the existing concepts and theories, and accepting the forms of argument, reasoning, experiment and proof in the respective discipline. However, at the last hurdle, in evaluating new alternative sub-theories, there are major differences in achieving consensus in the two fields. Why is this? Although there may be minor differences in educational style (mathematics assumes theory consensus, biology perhaps does not) is not the real difference in the disciplines themselves? Biology attempts to account for one world – the empirical world of living things we share. In other words, the truth test is fitting with this one world as best we can (subject to all the constraints indicated by Kuhn). Nevertheless, until theories are falsified or otherwise discarded they remain in contention. Mathematics develops theories based on ideas, concepts, assumptions, problems, etc., and ultimately there is no final competition between different theories. Provided they are consistent they may coexist. We have Euclidean and non-Euclidean geometries. There is no contradiction, no competition, no rivalry unless we apply them as applied theories to the empirical world. And then they are just another part of empirical science. The latter strives for an intended model. Mathematical theories only need to satisfy some particular model, out of the infinitely many possible. So consensus is easier to achieve in mathematics than biology. Which is not to say that the process of proving is easier in mathematics than that of conducting empirical tests in biology. It is just that if your derivation is agreed to be correct there is no further final test of truth, irrespective of the epistemological grounds of that agreement.

    2. True. But the puzzling thing is precisely this bit:


      That is, the consensus on proofs/derivations being correct.

  15. As pointed out earlier, consensus in mathematics is a relatively recent phenomenon, basically dating back to the foundational work in the early 20th century. Before then, one had debates about use of infinitesimals, implicit use of the axiom of choice (before this axiom was explicitly formulated), use of complex analytic methods instead of "elementary" methods, etc.

    In my view, one of the main reasons we were able to build such solid foundations to mathematics was that mathematics had been maturing for over 2000 years as a cumulatively developing subject, and that by the early 20th century we had finally reached the point where we could build proper foundations. There are other disciplines that are as old as mathematics (philosophy, for instance), but the cumulative development process started later. (Mathematics, for instance, still uses the classical theorems of Greek geometry, but much of Aristotlean physics or metaphysics has now been discarded by their modern counterparts.) Physics, for instance, has been developing more or less cumulatively since Galileo, and it is conceivable that in a century or two they may have a consensus foundation that is as solid as the foundations of mathematics are today. (They're not quite there yet, though.)

    So perhaps the deeper question is why mathematics started developing in a cumulative fashion much earlier than most other disciplines.

  16. here's a draft mini-paper on convergence in philosophy and why there isn't more of it, by comparison to mathematics, physics, and so on. there's also some data here. of course the foundations of mathematics is intermediate between regular mathematics and philosophy in some respects, so it's not surprising that convergence on the foundations of mathematics is slower than convergence on regular mathematics and faster than convergence in philosophy. it would be nice to pin down the relevant dimensions of difference.

  17. It's important to recognise that advances in mathematics are largely brought about by conceptual innovation rather than by grounding in some or other foundational language. Nineteenth century projective geometry texts may need a little tightening up in terms of rigour from our perspective, but far more importantly we don't need to stand in such awe of the fact that theorems and their proofs can be dualised by the simple expedient of exchanging a few terms, 'line' and 'point', 'passes through' and 'lies on', etc., once we understand the role of the outer automorphism of the group SL(3, R). To understand this we need to understand a range of conceptual advances by Felix Klein and others.

    I could go on and on here. It was a conceptual necessity for Poincaré to introduce early methods of algebraic topology in the 1890s. In doing so he shone a light on earlier work and transformed the mathematics of the twentieth century.

    This isn't to underplay the importance of foundational work, but innovations in the axiomatic method have been as important for allowing conceptual clarification and advance as for the provision of security. How mathematics affords the opportunity for radical changes in its conceptual outlook while preserving a tightly integrated network of theories is the interesting qustion for me.

  18. Good points, @Terry. They clearly illustrate my conviction that the philosophical discussion of these issues must be thoroughly historically-informed if it is to go anywhere.

    I would just like to clarify on what level I identify a tendency for overwhelming consensus in mathematics: it is mostly on the level of recognizing a given proof as correct or incorrect. Of course one can disagree on whether certain assumptions used along the proof are legitimate or not (e.g. the axiom of choice or what have you), but granting the assumptions, in most cases there seems to be consensus as to whether a proof is correct or not. As suggested by David Chalmers above, it is not so surprising that there should be more divergence of opinions in discussions on the foundations of mathematics, where certain assumptions may be questioned or accepted on grounds other than proofs, than in what he calls 'regular mathematics'.

  19. Well, I think the consensus amongst mathematicians is what we created mathematics for. most mathematicians I know have this craving for irrefutable arguments, for always wanting to dispute what has been said by others until no doubt remains (lovely put in cartoon form here, so in some ways is really not surprising that the consensus is there. sure, it relies on the cumulative nature of the subject. in fact, what is disturbing is when it is *not* there, as is the case of foundations, of the debate between constructive vs classical logic. the need for certainty has turned many mathematicians into constructivists, it seems to me...

  20. William wrote:


    No mathematicians believe that objection, so even if it were true, it wouldn't affect the way they arrive at a consensus. I.e., we hardly ever mathematicians object to someone's proof claiming the proof needs a proof... although I can imagine someone demanding program verification for a computer-based proof of the 4-color theorem.

  21. "hardly ever" -> "hardly ever see"

  22. I think Valeria hit the nail on the head: mathematicians crave consensus.

    If any sort of argument is of the sort that it only convinces 50% of mathematicians, we'll either say it's "not mathematics", or discuss, polish and/or demolish the argument until convinces either 99% of mathematicians or just 1%. (Example: Cantor's proofs.)

    If someone doesn't play the game according to the usual rules, we'll make up a new game and say they're playing that game instead, thus eliminating potential controversy. (Example: intuitionistic mathematics.)

    Finally, we reward people who quickly admit their errors, instead of fighting on endlessly. We say they're smart, not wimps. (Example: Edward Nelson.) People who fight on endlessly are labelled crackpots and excluded from the community. (Examples: too numerous to list here.)

  23. Well yes, mathematicians crave consensus, but then so do a lot of people. I crave consensus in philosophy (especially if it converges on my views), but I don't expect to find it. The question is why are mathematicians able to satisfy that craving. How have they been able to develop robustly stable practices? How is it possible to sense problems in a proof without dipping down to the machine code of its fully formal rendition.

    It would be fascinating to have a transcript of the thought processes which allowed Terry Tao to see the problem with Nelson's proof.

  24. Great points, @david! I agree entirely.

  25. Dear David,






  26. Dear Terry, thanks very much for that. For me it's intriguing how high-level perspectives, phrased in a natural mathematical language, can be sufficiently clear that they allow for the requisite checks to be made. I wonder if in the passage you describe in the second half of the penultimate paragraph, your reasoning is assisted by familiarity with similar potential problems, perhaps arising in very different parts of mathematics.

    In my book I discuss the claims that automated 'analogical' reasoning allowed the production of a proof of Heine-Borel in two dimensions, from a proof of the one-dimensional case. My point was that even in this simple case, the program, which is operating syntactically, requires a large amount of human assistance.

    Put in 'ordinary' language, one would suppose a closed interval with a cover and no finite subcover. Then take half of the interval which can't be finitely covered. Iterate this process. There is a point in the intersection of these nested intervals. It must belong to an element of the cover, and far enough along the sequence the nested intervals must be contained inside that element. Contradiction.

    The one worry for the human trying to extend this to two dimensions is to make sure that one can go far enough along the sequence so that each dimension of the nested rectangles fits inside the given element of the cover. The computer needs a big hand just here.

    Now some truly analogical reasoning would come into play if the human recognises from similar experience that an attempt to work an infinite-dimensional variant of the proof will not work as we cannot be assured that there's an upper bound to distances along the sequence for each of the dimensions to become small enough.

    Would I be right in thinking that

  27. In this specific case, all the mathematicians involved relied for their work on a specific highly developed theory- let me call it a module- and none was prepared to bear the cognitive cost of re-writing the entire module which is why there could be a quick resolution. Surely this happens all the time in other disciplines as well? Indeed the less 'rational' or alethic the subject area the lower the cognitive pay-off for rewriting entire modules so we might find even faster resolution, without even the pause for critical thought. A lesser mind might have taken much longer to concede the point.

    Still, suppose there was a big cognitive pay-off, currently available, for entirely rewriting the Chatin theorem 'module' or rethinking Kolmogorov complexity- it may be that some on or other of those involved might have taken that tack.




    Godel and Von Neumann, both Theists on their death beds, who agreed on so much in the way of mathematics yet had ontological dysphorias of opposite tropism. It may be that the latter type of 'madness'- or stark solipsistic discontinuity- is as important a driver for breakthroughs in Maths as the great powers of 'reason' both possessed which enabled the Von Neumann to grasp Godel's result, perhaps, more thoroughly and more quickly than he had done himself.

  28. (On rereading this post it seems overly long and maybe boring, especially in its central part "about mathematics". Let's hope someone will be interested. If you aren't, O reader, it's probably my fault rather than yours.)

    As a mathematician, but at a rather low level (retired teacher to junior high school, i.e. pupils 12 to 15 years of age), I believe that the ready obtainability of consensus is a defining characteristic of mathematics:

    Truth in the experimental sciences is defined by agreement with reality, and is always provisional, and subject to the precision of experimental measures.

    Truth in mathematics is defined by internal consistency, and the proof of a really fundamental contradiction (as in the "naïve" axiomatization of set theory, when it was shown that, obviously, "the set of all sets which are not members of themselves" is a member of itself if and only if it isn't) is cause for a serious overhaul of the theory in question (with ZF set theory and its family, but IIUC also with other axiomatizations, all making it so that it is not meaningful to talk about a "set of all sets which are not members of themselves". The solution I'm familiar with is Bourbaki's, who defines the notion of "collectivizability" ("nous disons qu'une relation R est collectivisante en une lettre x si (τ[x](R)|x)R est un théorème (Définition de "collectivisante"). De cette définition il découle immédiatement que la relation x∉x n'est pas collectivisante en x.) (Sorry, my mother language is French and I'm not sure I can provide an exactly faithful translation into mathematicians' English.) Another reformulation (IIUC what is vaguely mentioned about it in Hofstadter's /Gödel, Escher, Bach: an Eternal Golden Braid/) is the theory of types.

    As such, "truth" in mathematics is only relative to a certain choice of axioms: within a given theory (defined by its set of axioms), and if I accept Bourbaki's meaning of "true", then as long as the theory is consistent (which is not always easily provable) there are "true statements" (theorems), "false statements" (whose negation is a theorem), and usually "undecidable statements" (which are neither a theorem nor the contraposite of a theorem). Of course, if the theory is inconsistent, then everything it it is both true and false and _this particular choice of axioms_ loses all interest. Usually, however, for any theory which really interests mathematicians, and always AFAIK for any mathematical theory which interests physicists, engineers, etc., it is possible (not always easily) to find a reformulation of the set of axioms in a way which both avoids the inconsistency just discovered and preserves the already much-used results of the theory.

    Gödel's undecidability theorems establish the surprising (for his time) result that in any theory "powerful enough to develop number theory in it" there is at least one undecidable statement, and therefore an infinity.

    I might be tempted to say that philosophy is characterized by the fact that it is amenable neither to proof by experimentation nor to proof by consistency, and that yet (unlike most variants of theology) it is also not accessible to the argument of authority (i.e. the proof by "Ipse dixit" as the Latins said, or equivalently by "Αυτος εφη" as the Greeks said). But I'm not enough of a philosopher to be sure that this paragraph about the nature of philosophy is valid. (Every mathematician has, of course, to be /some/ of a philosopher, if only to discuss metamathematics and metalogics; but that isn't much as philosophers go.)

  29. Well post its give us good tips and tell us many technique and how to solve question with skills thanks for sharing college readmission letter .