Peter Smith's Blog, page 127

Tennenbaum's Theorem Workshop [updated]

Sean Walsh organized a one-day workshop on the philosophical significance of Tennenbaum's Theorem on Saturday. It kicked off with me presenting a short piece that Tim Button and I have forthcoming in Philosophia Mathematica: here's a preprint of our paper.

But for a quicker read, my overheads give the headline idea — that's there no implication about how we grasp the standard model to be got out of the elegant but non-trivial Tennenbaum's Theorem that you can't get out of the very easy theorem that every model of PA where every element has a finite number of predecessors is isomorphic to the standard model. Tennenbaum's Theorem has no extra oomph against the Skolemite sceptic. Indeed, appealing to either model theoretic result just doesn't touch the sceptic's worries. (The talk timed nicely, and having Tim there to help fend questions made giving it a lot more fun!)

The current temporal parts of Walter Dean and Leon Horsten were agreed, contra earlier parts, that Tennenbaum's Theorem cuts no ice against the model-theoretic sceptic (I wasn't so clear where Paula Quinlon now stands). But I think all three other speakers in different ways wanted to squeeze something philosophical out of Tennenbaum's Theorem. If/when published pieces emerge, I'll say why I wasn't so convinced. But a fun occasion (as such closely-focused workshops tend to be).

Santa's singleton

Here's a question which I'm sure bugs all my logical readers. Modern mathematics standardly recognises partial functions which can take something as input but deliver nothing as output (like the reciprocal function which isn't defined for zero). Do we also need to allow for co-partial functions which can take nothing as input but deliver something as output? Exciting eh?

Well, perhaps not so very thrilling. But for what it is worth, here's a version of a paper in dialogue form given to the Serious Metaphysics Group here in Cambridge this evening. Not exactly the talk as delivered (with help from Rob Trueman!): the discussion has led me to cut out a long passage which was getting too involved by half and to tinker elsewhere a small amount.

One comment: if/when I get round to further rewriting this a bit, I'd drop the 'Santa' example, as I don't want any noise coming in from issues about fiction. It would be better to use e.g. 'Vulcan' instead.

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!]

Stefan Collini on the very idea of a university.

I much admire Stefan Collini's writing on the current situation in UK universities (see here, for example). He has a book forthcoming next year What are Universities For? which should be a major event at least for academics struggling to find principled ways of thinking about and reacting to the battering. In the meantime, you might be interested in his recent Cambridge lecture on the very idea of a university, now online.

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 so far. Am I being captious? Well, collections like this one do tend to be unexciting, 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 pretty convincing, and his conclusion was news to me.

 

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 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 readable paper, but I don't think that there's anything 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. Kennedy 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 thought). But unless I'm missing something — and she isn't ideally clear — this doesn't really add much to our understanding.

The following paper is a typically lucid piece by Sol Feferman, on the Bernays/Gödel correspondence. He 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?

In CW, Feferman wrote 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!

Touched by greatness

A very moving concert last night. In the small Peterhouse Theatre (a lovely space for intimate music), Menahem Pressler played Beethoven's A-flat major sonata, Op. 110, Debussy's Estampes, and then Schubert's last piano sonata D. 960. He talked touchingly at the beginning of the evening, and this was evidently music that meant a great deal to him. Pressler's playing now is not the most technically secure, but his desire to communicate with his audience is undimmed.  The Schubert in particular was very affecting: in the second movement, the poignancy of an old man now 87 playing the searing music of a young man facing early death was almost too much to take. We will remember the occasion a long time.

It can be irritating though — can't it? — to hear tell of great concerts that you've now missed (and couldn't have got to anyhow). So let me mention something else which is quite wonderful in a different way, the Pavel Haas Quartet's Dvořák disk. Hardly a discovery by me! — it's the recently announced new Gramophone Recording of the Year. But it really is astonishing. I've always thought the old performance of the "American" quartet by the Hollywood Quartet was in a league of its own (one generation from the shtetl, is it fanciful to hear the tug of a vanished Europe in their playing?). But this new recording from the young Czech quartet is at least as great. I'm bowled over.

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 logic 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 comfort zone here, and I can only refer enthusiasts (or skeptics) about this project to the paper for the details, which look impressive to me.

A decidedly tough read for the opening piece!

Thanks to Orlando May

I'm getting back down to work on the second edition of An Introduction to Gödel's Theorems. One thing I plan to do is to put up some pages of exercises as I go along, which I've been meaning to do for ages, but takes a surprising amount of time. Watch this space.

Meanwhile, one interim thing I've just done is put online a major update to the corrections page for the latest printing(s) of the first edition. The corrections are almost all due to Orlando May, who has evidently been reading the book with a quite preternaturally accurate eye. I'm most grateful.

If anyone else has anything to add, large or small, about how to improve the book next time around, then of course I'll again be more than grateful!