KGFM 20, 21: Woodin on the transfinite, Wigderson on P vs NP

And so, finally, to the last two papers in KGFM. I can be brief, though the papers aren’t. The first is Hugh Woodin’s ‘The Transfinite Universe’. This inevitably mentions Gödel’s constructible universe L a few times, but otherwise the connection to the ostensible theme of this volume is frankly pretty tenuous. And for those who can’t already tell their Reinhardt cardinals from the supercompacts, I imagine this will be far too breathless a tour at too stratospheric a level to be at all useful. Set-theory enthusiasts will want to read this paper, Woodin being who he is, but this seems to be very much for a minority audience.

By contrast, the last paper does make a real effort both to elucidate what is going on in one corner of modern mathematics for a wider audience, and to connect it to Gödel. Avi Wigderson writes on computational complexity, the P ≠ NP conjecture and Gödel’s now well-known letter to von Neumann in 1956. This paper no doubt will be tougher for many than the author intends: but if you already know just a bit about P vs NP, this paper should be accessible and will show just how prescient Gödel’s insights here were. Which isn’t a bad note to end the volume on.

So how should I sum up these posts on KGFM? Life is short, and books are far too many. Readers, then, should be rather grateful when a reviewer can say “(mostly) don’t bother”. Do look at Feferman’s nice paper preprinted here. If you want to know about Gödel’s cosmological model (and already know a bit of relativity theory) then read Rindler’s paper. If you know just a little about computational complexity then try Wigderson’s piece for the Gödel connection. And perhaps I was earlier a bit harsh on Juliette Kennedy’s paper — it is on my short list of things to look at again before writing an official review for Phil. Math. But overall, this is indeed a pretty disappointing collection.

KGFM 19: Cohen’s interactions with Gödel

The next paper in KGFM is a short talk by the late Paul Cohen, ‘My Interaction with Kurt Gödel: The Man and His Work’. The title is full of promise, but there seems relatively little new here. For Cohen had previously written with great lucidity a quite fascinating paper ‘The Discovery of Forcing‘ and he already touches there on his interactions with Gödel:

A rumor had circulated, very well known in all circles of logicians, that Gödel had actually partially solved the [independence] problem, specifically as I heard it, for AC and only for the theory of types (years later, after my own proof of the independence of CH, AC, etc., I asked Gödel directly about this and he confirmed that he had found such a method, specifically contradicted the idea that type theory was involved, but would tell me absolutely nothing of what he had done). … It seems that from 1941 to 1946 he devoted himself to attempts to prove the independence [of AC and CH]. In 1967 in a letter he wrote that he had indeed obtained some results in 1942 but could only reconstruct the proof of the independence of the axiom of constructibility, not that of AC, and in type theory (contradicting what he had told me in 1966).

In this present paper, Cohen can shed no more real light on this unclear situation. But still,  what he writes is perhaps interesting enough to quote. So, Cohen first repeats again the basic story, though with a comment that chimes with other accounts of Gödel’s philosophical disposition:

I visited Princeton again for several months and had many meetings with Gödel. I brought up the question of whether, as rumor had it, he had proved the independence of the axiom of choice. He replied that he had, evidently by a method related to my own, but he gave me no precise idea or explanation of why his method evidently failed to succeed with the CH. His main interest seemed to lie in discussing the truth or falsity of these questions, not merely their undecidability. He struck me as having an almost unshakable belief in this realist position that I found difficult to share. His ideas were grounded in a deep philosophical belief as to what the human mind could achieve.

And then at the end of the talk, Cohen sums up his assessment like this:

Did Gödel have unpublished methods for the CH? This is a tantalizing question. Let me state some incontrovertible facts. First, much effort was spent analysing Gödel’s notes and papers, and no idea has emerged about what kinds of methods he might have used. Second, I did ask him point-blank whether he had proved the independence of CH, and he said no, but that he had had success with the axiom of choice. I asked him what his methods were, and he said only that they resembled my own; he seemed extremely reluctant to give any further information.

My conclusion is that Gödel did not complete any serious work on this topic that he thought was correct. In our discussions, the word model almost never occurred. Therefore I assume that he was looking for a syntactical analysis that was in the spirit of his definition of constructibility. His total lack of interest in a model-theoretic approach quite astounded me. Thus, when I mentioned to him my discovery of the minimal model also found by John Shepherdson, he indicated that this was clear and, indirectly, that he knew of it. However, he did not mention the implication that no purely inner model could be found. Given that I also believe he was strongly wedded to the syntactical approach, this would have been of great interest. My conclusion, perhaps uncharitable, is that he totally ignored questions of models and was perhaps only subconsciously aware of the minimal model.

That hints at an interesting diagnosis of Gödel’s failure to prove the independence results he wanted.

KGFM 17, 18: Kohlenbach and Friedman

Next up in Kurt Gödel and the Foundations of Mathematics is Ulrich Kohlenbach, writing on ‘Gödel’s Functional Interpretation and Its Use in Current Mathematics’. This rachets up the technical level radically, and will be pretty inaccessible to most readers (certainly, to most philosophers). The author has done significant work in this area: but as an effort towards making this available and/or explaining its importance to a slightly wider readership than researchers in one corner of proof theory, this over-brisk paper surely quite misses the mark. (I guess enthusiasts who want to know more about recent developments will just have to go for the long haul and try Kohlenbach’s 2008 book on Applied Proof Theory, but that too is very hard going.)

Then, for the eighteenth paper, we have Harvey Friedman, aiming to discuss a ‘sample of research progjects that are suggested by some of Gödel’s most famous contributions’ — a prospectus that immediately alerts the reader to the likelihood that the paper will cover too much too fast. The piece has the remarkably self-regarding title ‘My Forty Years on His Shoulders’ and ends with the usual Friedmanesque announcements of results about the equivalence of the provability-in-various-arithmetics of certain combinatorial claims with the consistency of certain set theories with large cardinals. The style and content will be very familiar to readers of the FOM list, and probably pretty baffling to others.
One place where Friedman’s paper goes a bit slower is in discussing the Second Incompleteness Theorem, and there are intimations by the author that he has found a neater, more insightful way of developing the result. But with his customary academic incivility, Friedman doesn’t bother to explain this in accordance with the normal standards of exchange between colleagues, but refers to online unpublications … where things remain equally unexplained. This is, to put it mildly, irritating: and I know I’m not the only person who has long since lost patience with this mode of proceding. Humphhhh!

KGFM 16: Penrose on minds and computers

Stewart Shapiro has had two shots at exploring the troubles with Lucas/Penrose-style arguments, first in his well-known paper ‘Incompleteness, Mechanism and Optimism’ Bull. Symb. Logic (1998), and then — expanding his treatment of Penrose’s efforts in Shadows of the Mind (1994) — in ‘Mechanism, Truth, and Penrose’s New Argument’ Jnl. of Philosophical Logic (2003). As you’d predict, Shapiro’s discussions are eminently lucid and very sharp; and his treatment of the Penrose argument in particular is extraordinarily patient and constructive, trying to get something out of the argument, and finding some interesting lines (though nothing that gives Penrose what he wants). He concludes with a

challenge to the anti-mechanist to articulate the new Penrose argument in a way that blocks the Gödel–Kreisel–Benacerraf ploy [i.e. the move of saying that perhaps we can be simulated by a computer but if so we can’t, with mathematical certainty, know which] but does not invoke unrestricted truth and knowability predicates [as apparently, but problematically, required by the Penrose argument, when the wraps are off].

If you don’t know the papers, they are terrific. And Shapiro’s insightful exploration surely has become the necessary starting point for any subsequent discussion here.

It is disappointing to have to report, then, that Penrose’s contribution to KGFM is written as if Shapiro had never made the effort to try to sort things out.

Well, that isn’t quite true: there’s a footnote which has a reference to Shapiro 2003. But otherwise, as far as I can see, Penrose just gives a (too brief to be useful) thumbnail sketch of his 1994 argument, and doesn’t address at all the technical problems that Shapiro explores. In so far as he does respond to critics, Penrose just offers some rather thin remarks about the sort of worries concerning idealization and vagueness that we noted that Putnam rehearses. But of course, the interesting thing about Shapiro’s discussion is that, for the sake of the argument, he gives the game to Penrose on those matters, allows Penrose’s anti-mechanist argument at least to get to the starting point, but then still finds trouble. Lots of trouble. And there’s nothing in Penrose’s paper here which offers any reponses. So I can’t say that this is a useful contribution to the debate on the impact of Gödelian arguments.

KGFM 15: Putnam on minds and computers

In his 1967 paper, ‘God, the Devil, and Gödel’, Paul Benacerraf famously gives a nice argument, going via Gödel’s Second Theorem, that proves that either my mathematical knowledge can’t be simulated by some computing machine (there is no particular Turing machine which enumerates what I know), or if it can be then I don’t know which machine does the trick. Benacerraf’s argument is perhaps not ideally presented, so for a crisper, streamlined, version see my Gödel book, §28.6: but the idea should be familiar.

Of course, how interesting you think this result is will depend on just how seriously you take the notion that there might such a determinate body of truths as my mathematical knowledge. For one thing, any real-world mathematician makes mistakes: what I know will be a subset of what I think I know, and I won’t in fact know which subset (so it’s no surprise if I wouldn’t recognize which Turing machine enumerates my actual knowledge). OK, it will be replied that the Benacerraf argument is supposed to apply to my idealized knowledge, prescinding from mistakes in performance etc. But how is that story supposed to work? And even if we can make the idea fly, and can sensibly idealize away from common-or-garden error, isn’t it going to be vague at the margins what I count as a proof? So isn’t it still going to be irredeemably vague what belongs to my idealized mathematical knowledge? If so, the question of simulating it with the crisply determinate output of a Turing doesn’t arise.

Similar worries about idealizing mathematicians and the vagueness of the informal notion of proof will beset other attempts to get sharp anti-computationalist conclusions about the mind from Gödelian considerations. And in the his quite brief paper, ‘The Gödel Theorem and Human Nature’, Hilary Putnam brings such worries to bear against Penrose in particular. Rather than pick holes again in the details of Penrose’s arguments (which have been chewed over enough in the literature, by Putnam among many others), he now stresses that the whole enterprise is misguided. “The very notion of an ideal mathematician is too problematic” to enable us to set up a contrast between what a suitably idealized version of us can do and what a naturalistically kosher mechanism can do. The complaint is quite a familiar one, but perhaps none the worse for that.

But interestingly, for all his worries about the pointfulness of such tricksy arguments, Putnam does return to explore a relation of Benacerraf’s argument, spelt out this time in terms of the notion of justified belief rather than knowledge.

The target is a (surely implausible!) Chomskian hypothesis to the effect that we have a ‘scientific faculty’ such that this faculty — in idealized form — can be simulated by some particular Turing machine T. In other words, (C) T enumerates (a coded version of) every true sentence of the form ‘we are justified in accepting p on evidence e‘. Then Putnam has an argument that either (C) isn’t true, or if it is we aren’t justified in believing it (I can’t have a justified belief about which machine does the simulation trick).

Oddly, however, Putnam doesn’t mention the analogous Benacerraf argument at all, so — if you are interested in this sort of thing — you’ll need to do your own “compare and constrast” exercise. And as with his predecessor’s argument, Putnam’s too isn’t ideally well presented and a bit of work needs to be done. Perhaps I’ll return to the exercise in a later posting, if it proves fun enough.

Or then again, perhaps I won’t … For in any case, the more interesting tack is to return to Penrose and ask whether he or a defender can sidestep the sort of general worry that Putnam has about arguments with a Lucas/Penrose flavour. Well, the next paper in KGFM is another shot by Penrose himself. So let’s turn to that.

KGFM 9, 10: Gödelian cosmology, Rindler and Svozil

The next piece is ‘Gödel, Einstein, Mach, Gamow, and Lanczos: Gödel’s Remarkable Excursion into Cosmology’ by Wolfgang Rindler.

Rindler’s books on Relativity are real classics of exposition, so I was hoping for good things from this paper. I wasn’t disappointed. As Rindler says, Gödel famously “invented a model universe that was consistent with general relativity but that nevertheless exhibited two startlingly disturbing features: bulk rotation (but with respect to what, as there is no absolute space in general relativity?) and travel routes into the past (enabling one to witness or even preventone’s own birth?)”. If you want to know what Gödel’s cosmological model looks like, and have a smidgin of knowledge about relativity theory, then this paper is a great place to start. There’s no philosophical discussion though about worries concerning the very idea of closed time loops: but that’s no complaint — the paper does beautifully what it does set out to do. Recommended!

The tenth paper — grouped with Rindler’s in a subsection called ‘Gödelian Cosmology’ — is Karl Svocil’s ‘Physical Unknowlables’. But this piece in fact doesn’t even mention Gödel’s model universe, but rambles about indeterminism, ‘intrinsic self-referential observers’, unpredictability, busy beavers, deterministic chaos, quantum issues, complementarity, and lots more. Hopelessly unfocused, I’d say. Not recommended!

[That finishes the first part of KGFM. There will now be a gap for ten days or so before I can return to the second part, as I’ve promised to give two different talks next week and need to work on them!]

KGFM 7, 8: Computers and computation, Papadimitriou and Copeland

Looking at the postings on KGFM, I’ve been pretty negative so far. Sorry! OK, Macintyre’s paper is indeed a tour de force but is for a pretty specialized reader. Otherwise I can only really recommend Feferman’s paper. Am I being captious? Well, collections like this one do tend to be very mixed blessings, don’t they? Blockbuster conferences invite the great and good who perhaps don’t always have much new left to say, and in any case interpret their briefs in very different ways, at different levels of sophistication; and the resulting edited volumes then bung more or less everything in with little editorial control (printing papers that wouldn’t make the cut in top journals). So you get collections like this one.

And now I fear I’m going to be pretty negative about (most of) the next two papers as well. I really am getting cranky in my old age. Sigh. But Christos H. Papadimitriou writes briefly on ‘Computation and Intractability’. He touches on Gödel’s 1956 letter to von Neumann and his prefiguring of something like the question whether P=NP which has been extensively discussed elsewhere (and there is nothing new here). And he adverts to a result about the intractability of finding Nash equilibria which is proved by a method of arithmetization inspired by Gödel: but you won’t learn how or why from this paper.

Next up is a much longer paper by Jack Copeland ‘From the Entscheidungsproblem to the Personal Computer – and Beyond’. Most of this is a story about the development of computing devices from Babbage to the Ferranti Mark I (complete with photos): interesting if you like that kind of thing, but utterly misplaced in this volume. But randomly tacked on is a final section which is germane: so after Feferman, you can start reading again here, with Copeland’s ‘Epilogue’, which is indeed worth looking at.

The issue here is Gödel’s 1970 note which attributes the view that “mental procedures cannot go beyond mechanical procedures” to Turing. Copeland responds not by worrying about Gödel’s anti-mechanism but with evidence that Turing shared it. He cites passages where Turing criticises what he calls an “extreme Hilbertian” view and  writes of mathematical intuition delivering judgements that go beyond this or that particular formal system. In fact,

Turing’s view … appears to have been that mathematicians achieve progressive approximations to truth via a nonmechanical process involving intuition. This picture, in which minds devise and adopt successive, increasingly powerful mechanical formalisms in their quest for truth, is consonant with Gödel’s view that “mind, in its use, is not static, but constantly developing.” These two great founders of the study of computability were perhaps not quite as philosophically distant on the mind-machine issue as Gödel supposed.

Copeland’s evidence seems rather convincing.

KGFM 4, 5, 6: More history, from Sigmund, Kennedy, and Feferman

I should have explained that Kurt Gödel and the Foundations of Mathematics is divided into three main parts, ‘Historical Context’, ‘A Wider Vision: the Interdisciplinary, Philosophical and Theological Implications of Gödel’s Work’, and ‘New Frontiers: Beyond Gödel’s Work in Mathematics and Symbolic Logic’. There are no less than seven papers in the first part left to talk about, and I’m not really the best person to comment on their historical content. But on we go.

Next, then, is Karl Sigmund on “Gödel’s troubled relationship with the University of Vienna based on material from the archives as well as on private letters”. The bald outlines will be familiar e.g. from Dawson’s biography, but there’s a lot of new detail. This is a nicely readable paper about the facts of the case, but I don’t think that there’s anything here that sheds new light on Gödel’s intellectual progress.

The fifth paper is ‘Gödel’s Thesis: an Appreciation’ by Juliette Kennedy. This concentrates on the philosophical Introduction of Gödel’s 1929 thesis on completeness (the material which wasn’t included in the 1930 published version), and in particular on his remarks about whether consistency implies existence. So part of Kennedy’s paper is in effect an elaboration of what Dreben and van Heijenoort say on p. 49 of their intro in the Collected Works when they point out that Gödel’s remarks are a bit misleading. She goes on also to urge that that there is evidence that Gödel was already, in 1929, thinking about incompleteness for theories (also not really a new suggestion). Unless I’m missing something — and Kennedy isn’t ideally clear — this also doesn’t really add much to our understanding. [That’s too brisk — see the Comments.]

The following paper is a typically lucid piece by Solomon Feferman, on the Bernays/Gödel correspondence, and as always is well worth reading if you are interested in the history here. Feferman has already introduced the correspondence in the Collected Works: but this piece concentrates at greater length on the theme of ‘Gödel on Finitism, Constructivity, and Hilbert’s Program’. As he writes,

There are two main questions, both difficult: first, were Gödel’s views on the nature of finitism stable over time, or did they evolve or vacillate in some way? Second, how do Gödel’s concerns with the finitist and constructive consistency programs cohere with the Platonistic philosophy of mathematics that he supposedly held from his student days?

Re the first question, Feferman wrote in CW of Gödel’s ‘unsettled’ views on the upper bound of finitary reasoning. Tait has dissented. But in fact,

Tait says that the ascription of unsettled views to Gödel in the correspondence and later articles “is accurate only of his view of Hilbert’s finitism, and the instability centers around his view of whether or not there is or could be a precise analysis of what is ‘intuitive”’ (Tait, 2005, 94). So, if taken with that qualification, my ascription of unsettled views to Gödel is not mistaken. As to Gödel’s own conception of finitism, I think the evidence offered by Tait for its stability is quite slim …

On the second question, of why Gödel should have devoted so much time to thinking about a project with which he was deeply out of sympathy, Feferman writes

Let me venture a psychological explanation … : Gödel simply found it galling all through his life that he never received the recognition from Hilbert that he deserved. How could he get satisfaction? Well, just as (in the words of Bernays) “it became Hilbert’s goal to do battle with Kronecker with his own weapon of finiteness,” so it became Gödel’s goal to do battle with Hilbert with his own weapon of the consistency program. When engaged in that, he would have to do so –  as he did – with all seriousness. This explanation resonates with the view of the significance of Hilbert for Gödel advanced in chapter 3 of Takeuti (2003) who concludes that … [Gödel’s] “academic career was molded by the goal of exceeding Hilbert.”

Sounds plausible to me!

KGFM 2, 3: Kreisel and Grattan-Guinness

The second paper in the collection is a seven-page ramble by Georg Kreisel, followed by twenty pages of mostly opaque endnotes. This reads in many places like a cruel parody of the later Kreisel’s oracular/allusive style. I lost patience very quickly, and got almost nothing from this. What were the editors doing, printing this paper as it is? (certainly no kindness to the author).

Something that struck me though, from the footnotes. Kreisel “saw a good deal of Bernays, who liked to remember Hilbert  …. According to Bernays … Hilbert was asked (before his stroke) if his claims for the ideal of consistency should be taken literally. In his (then) usual style, he laughed and quipped that the claims served only to attract the attention of mathematicians to the potential of proof theory” (pp. 42–43). And Kreisel goes on to say something about Hilbert wanting use consistency proofs to bypass “then popular (dramatized) foundational problems and get on with the job of doing mathematics”. Which chimes with Curtis Franks’s ‘naturalistic’ reading of Hilbert, which I discussed here.

The book’s next contribution couldn’t be more of a contrast, at least in terms of crisp clarity. Ivor Grattan-Guinness is his usual lucid and historically learned self when writing quite briefly about ‘The reception of Gödel’s 1931 incompletability theorems by mathematicians, and some logicians, to the early 1960s’. But in a different way I also got rather little out this paper. There are some interesting little anecdotes (e.g. Saunders Mac Lane studied under Bernays in Hilbert’s Göttingen in 1931 to 1933 — but writes that that he was not made aware of Gödel’s result). But the general theme that logicians got to know about incompleteness early (with some surprising little delays), and the word spread among the wider mathematical community much more slowly could hardly be said to be excitingly unexpected. Grattan-Guinness has J. R. Newman as a hero populariser (and indeed, I think I first heard of Gödel from his wonderful four-volume collection The World of Mathematics) — and Bourbaki is something of a anti-hero for not taking logic seriously. But, as they say, what’s new?

KGFM 1: Macintyre on the impact of incompleteness on maths

I’m going to be reviewing the recently published collection Kurt Gödel and the Foundations of Mathematics edited by Baaz, Papadimitriou, Putnam, Scott and Harper, for Philosophia Mathematica. This looks to a really pretty mixed bag, as is usual with volumes generated by block-buster conferences: but there are some promising names among the contributors, and a quick initial browse suggests that some of the papers should be very worth reading. So, as I go through the twenty one papers over the coming few weeks, I will intermittently blog about them here.

First up is Angus Macintyre, writing on ‘The impact of Gödel’s Incompleteness Theorems on Mathematics’. His title is pretty much the same as that of a short and very readable piece by Feferman in the Notices of the AMS and his conclusion is also much the same: the impact is small. To be sure, “Some of the techniques that originated in Gödel’s early work (and in the work of his contemporaries) remain central in logic and occasionally in work connecting logic and the rest of mathematics.” But “[a]s far as incompleteness is concerned, its remote presence has little effect on current mathematics.” For example, “The long-known connections between Diophantine equations, or combinatorics, and consistency statements in set theory seem to have little to do with major structural issues in arithmetic” (p. 14). And similarly elsewhere in maths.

There’s a lot of reference to mathematical results, and nearly all of the detailed discussion is well beyond my comfort zone (or that of most readers of this blog, I’d guess: try, e.g., “Étale cohomology of schemes can be used to prove the basic facts of the coefficients of zeta functions of abelian varieties over finite fields”). So I can’t very usefully comment here.

Probably the most exciting and novel thing in this piece is the substantial appendix which aims to give an outline justification for Macintyre’s view that we have “good reasons for believing that the current proof(s) of FLT [Fermat’s Last Theorem] can be modified, without abandoning the grand lines of such proofs, to proofs in PA.”  But again, I’m frankly outside my competence here, and I can only refer enthusiasts (or skeptics) about this project to the paper for the details, which look rather impressive to me.

A decidedly tough read for the opening piece!

Scroll to Top