(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

Nelson announced his results on the FOM mailing list on September 26^{th} 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 ^{st}, 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.

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.

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

ReplyDelete@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.

ReplyDeleteI 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.

ReplyDeleteIt'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.

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

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

ReplyDeleteMaybe 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?

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

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

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

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

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

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.

ReplyDeleteTo 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.

@John,

ReplyDeleteIndeed, 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!

@David,

ReplyDeleteI 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! :)

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.

ReplyDeleteI'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?

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

ReplyDeleteSo, 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.

ReplyDeleteThat 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.

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.

ReplyDeleteOne 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...

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.

DeleteTrue. But the puzzling thing is precisely this bit:

Delete"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."

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

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.

ReplyDeleteIn 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.

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.

ReplyDeleteIt'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.

ReplyDeleteI 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.

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.

ReplyDeleteI 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'.

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 http://abstrusegoose.com/353), 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...

ReplyDeleteWilliam wrote:

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

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.

"hardly ever" -> "hardly ever see"

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

ReplyDeleteIf 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.)

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.

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

Great points, @david! I agree entirely.

ReplyDeleteDear David,

ReplyDeleteActually, Nelson's proof was relatively easy to understand, in part because he took the trouble to write out a short outline which make clear the general strategy of proof while omitting most of the technical details (though it was ambiguous at one very crucial juncture), and also because I had already previously thought about the surprise examination (or unexpected hanging) paradox and the Kritchman-Raz argument (see the last section of http://terrytao.wordpress.com/2011/05/19/epistemic-logic-temporal-epistemic-logic-and-the-blue-eyed-islander-puzzle-lower-bound/ ).

From the outline one could already see that the main idea was to adapt the Kritchman-Raz argument to the theory Q_0^*, which "almost" proved its own consistency in that it contained a hierarchy of theories Q_1, Q_2, Q_3, ..., each of which could prove the consistency of its predecessor.

Now, I did not at the time fully understand the definition of Q_0^*, nor was I fully aware of the Hilbert-Ackermann result which guaranteed this chain of consistency results, but I was willing to accept the existence of such a hierarchy of theories. (I've since read up a bit on these topics, though.) The question was then, given such an abstract hierarchy, whether one could use the arguments of Chaitin and Kritchman-Raz to establish the inconsistency of at least one of these theories.

These arguments were simple enough (they were basically formalisations of the Berry paradox and surprise examination paradox respectively) that I could then try to do that directly, without any further assistance from the outline. And, indeed, when I attempted to do this, I did at first seem to obtain a contradiction (much as paradoxes such as the Berry or surprise examination paradoxes also lead to absurdity if one reasons somewhat carelessly using informal naive argument). So I could see where Nelson was coming from; but then I spent some time trying to expand out my arguments in detail to find the error. The key, as I found out, was to specify exactly what proof verifier would be used for the Chaitin portion of the argument (this was an issue that was left ambiguous in Nelson's outline), and in particular whether it would accept proofs of unbounded complexity or not. Since Nelson wanted to keep all proofs at bounded complexity, I used a proof verifier that enforced such a bound, and eventually worked out that this could not be done while keeping the length of the Chaitin machine constant; this was the objection that I raised in my first few comments. However, after Nelson responded, it became clear that he was using an unrestricted proof verifier, and this led to a different problem, namely that the proofs produced by Chaitin's argument were of unbounded complexity. So there was not a single "flaw" in the argument, but rather there were two separate flaws, one of which was relevant to one interpretation of the argument, and the other of which was relevant to an alternate interpretation of the argument.

Aside from this one ambiguity, though, the outline was quite clear. Certainly there have been other manuscripts claiming major results that were much more difficult to adjudicate because they were written so badly that there were multiple ambiguities or inaccuracies in the exposition, and any high-level perspective on the argument was obscured.

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.

ReplyDeleteIn 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

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.

ReplyDeleteStill, 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.

Surely an 'in-built opponent' is a feature of all social communication? It weighs down most heavily where the cognitive cost of re-writing modules are high or the reward is miniscule? I suppose statements about fashion or syntax or what is considered politically correct, have this feature and thus in most social sub-sets there is going to be very quick recantation simply because the cost greatly outweighs any possible benefit.

At this point, I'd like to introduce a notion of ontologically dysphoria- the feeling of being in the wrong Universe, the intuition that the Cartesian duality of mind and body points to something more troubling, bizarre or tragic. It may be that there is a sort of genotypal canalisation towards a widespread feeling of this sort- perhaps, rather than a malaise attributable to the welgeist, ontological dysphoria is the driver for the necessary-but-not-too-much preference diversity needed to drive trade, but also communication and the elaboration of Knowledge systems.

It may make a sort of collocational sense for us to agree that Math represents a limit case of one sort and philosophy, with its distinctions without differences, as the limit case of its opposite.

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.