World class bullshit

I've just heard that I have been awarded an AHRC Research Leave grant (so together with a university sabbatical that means I'll be on leave from January to the end of September next year). Which is quite a surprise: I was rather expecting that my proximity to retirement would rule me out. So all credit to the AHRC panel for lack of ageism!

I was much amused, though, to find that my research proposal was "an outstanding proposal meeting world-class standards of scholarship, originality, quality and significance". Which is very flattering of them, of course, but plain bonkers. I said I'd like more leave to help to finish a reasonably short accessible book doing for Gentzen's proof(s) of the consistency of arithmetic what my Gödel book tries to do for incompleteness proofs -- i.e. explain clearly and make a few philosophical comments along the way. Mildly useful, I hope: but world-class significance? I think not.

I assume the AHRC are bullshitting for their political masters ("we need the money to fund oodles of world-class research, you know!"), just as we bullshit to the AHRC to get the grants. But it is all more than a bit ludicrous.

Time-travelling with Google maps

Late last night, I walked down the street where I lived from the age of four until I was fourteen. A virtual walk, using Street View in Google maps. A rather sad experience though. For what a visual mess so much of the English urban landscape has become!

When I lived there -- we are talking about the outer London suburbs in Surrey -- the streets were quietly respectable, each house (built in the 30s, I think) separated from the road by a small front garden, neatly enclosed in privet hedges, with the obligatory flowerbeds and small patch of lawn. The houses along the road were identical apart from the colours of the front door. No one could call them particularly elegant. But there was a quiet uniformity; and the trees along the grass verges to the road, together with the hedges and front gardens, softened the rather dour drabness of the brick houses, so the overall effect was pleasing enough. As home-owning (as opposed to renting) became more common among the middle middle classes after the war, it was just the kind to street people aspired to live in.

Now, of course, the hedges and front lawns and hollyhocks have nearly all gone: where there were gardens, there is concrete and asphalt and paving stones, so cars can be parked two abreast with their noses up against the front windows. The long green verges to the road have been paved over too, so people can drive their cars across, with the few remaining trees isolated on little patches. The houses themselves have suffered from scattered cheap replacement windows, a new porch here, a differently tiled roof there. It all looks more than a bit scruffy: there is nothing along the road to soothe the eye, no riots of flowers to cheer the heart. I can't imagine anyone positively aspiring to live there.

Yet the houses now change hands for a third of a million pounds.

Twitter is sometimes not entirely frivolous

I was amused by the kids twittering away at the Joint Session (like third-formers passing notes in the back row) -- some very good pics too. Mildly fun to see what I was missing. If not exactly useful.

However, a recent tweet from Robbie Williams did very interestingly point out that the first vol. of Saul Kripke's papers has been announced. I'll believe it, though, when I see it.

Gödel sorted ... until the next time

Well, I've just this morning sent off the PDF for the next reprinting of my Gödel book: it should be available mid-August. I've eliminated quite a few more typos (thanks to everyone who let me know of errors in the earlier printings), made a scattered selection of small clarifications/stylistic improvements, and corrected the major errors that were still lurking even in the first corrected reprint. The biggest change is the one I mentioned a couple of posts ago, concerning Rosser's Theorem.

Being a reprint though, I couldn't change the "extent" of the book, the number of sheets that need printing. (Fortunately, the previous version finished on a recto page, so I had the verso to play with, and needed the extra side to correct the treatment of Rosser's Theorems). But given a new edition, I'd like another dozen or fifteen pages. First, I'd give a nicer proof that Robinson Arithmetic can capture all p.r. functions. Second, I'd fill in all the details of the proof that Prf(m, n) is p.r. (the final stages of which are just sketched). Third, I'd fill out the proof of the derivability conditions for theories with a smidgin of induction (again, I give an arm-waving sketch). As to the second and third, I originally didn't worry about giving sketches, as filling out the details is pretty tedious and unexciting (what you surely want to get across are the proof-ideas: and I referred masochists and completists to places where they can get the full gory story). But a number of readers have thought I should have gone the extra mile and risen to the challenge of giving full, though still maximally accessible, proofs. OK: if there's a second edition with a slightly longer page budget I'll have a bash ... But that will have to wait a bit.

Apple Preview: fail

This might just save a few Mac-based LaTeX users some grief. Suppose you use TeXShop to typeset

\documentclass[11pt,a4paper]{article}
\begin{document}
$\{0\} \to \{y = 0\}$
\end{document}

The result looks just fine in the TeXShop preview window onscreen (which calls on the Mac pdf Preview engine). But print it out and the spacing after the arrow is wrong. You get

{0} →{ y = 0}

Use Adobe Reader to print the pdf and all is well:

{0} → {y = 0}

The problem seems to be that the use of '}' as a printing character before a binary operator can mess up the printing though not the viewing of a pdf by Preview. Very, very odd. But apparently there are other known issues with Preview printing pdfs and missing/misplacing symbols. So the moral is: when it matters, print using Adobe Reader.

Stumbling over the bug caused me some hours of annoyed and mystified head-scratching. The invaluable comp.text.tex newsgroup helped me find a minimal example and pin the blame on Preview rather than on my (occasionally ropey) LaTeX coding.

Rum and reason

Long time readers will remember I used to link to The Daughter's cooking blog, BakeMeHappy (that's still on line, full of good things, and beautifully written -- but apart from a little late flurry, it really came to a halt a year ago). She's now left Italy, and is cooking up a storm in the Bahamas: and to go with that move, there's a new blog, Rum & Reason, promising more great food and another good read. Enjoy!

Rosser's Theorem

Wolfgang Rautenberg's very nice A Concise Introduction to Mathematical Logic states Gödel's first theorem in the usual sort of way. Roughly: given a suitably axiomatized omega-consistent theory T containing enough arithmetic, there's a Pi_1 undecidable sentence. He proves this by appeal to the diagonalization lemma applied to the predicate not-Prov (where Prov suitably expresses provability in T). A fixed point G for this is neither provable nor disprovable. And being equivalent to not-Prov('G') that's undecidable too. But not-Prov by construction is Pi_1, so that gives us a Pi_1 undecidable sentence.

So far, so very familiar! He then goes on to say (p. 195) that the assumption of omega-consistency in Gödel's theorem can be weakened to that of consistency. And he gives the usual Rosser construction. Define a Rosser proof-predicate RProv (defined from the usual Sigma_1 proof-relation Prf, so it is satisfied by the Gödel number for a wff if the wff has a proof, and there is no "smaller" proof of its negation). Then, just on the assumption of consistency, a fixed point R for not-RProv is neither provable nor disprovable. Great.

But oops, that isn't quite enough to prove the weakening of Gödel's theorem as stated. For Rautenberg hasn't checked that there's a Pi_1 undecidable sentence that you can get in this way. And note that not-RProv (as he defines it, Sigma_1 Prf) from the isn't explicitly Pi_1, so the argument from before doesn't carry over. So there's a gap in the proof here: some more work needs to be done.

There's the same gap it seems in Per Lindström's Aspects of Incompleteness (p. 26). He just cheerfully starts off, in effect, "Let R be a Pi_1 fixed point of not-RProv." Why should there be one? He doesn't explain.

At least one book, though, does worse. That is to say, it notes the need for an argument that there is a Pi_1 undecidable sentence that you can get from Rosser's kind of construction. But then it proceeds to give a bad argument, claiming not-RProv can be manipulated into an equivalent Pi_1 formula, but giving an evidently hopeless "proof" for that claim. Oh dear.

And the culprit was me. So I'm very grateful to Adil Sanaulla for alerting me to the fact that something is badly amiss in An Introduction to Gödel's Theorems at the foot of p. 178. So I've needed to go back to the drawing board.

In fact, sorting out things out took just a bit of thought. To recap, the sort of argument that I use in the book (and that e.g. Rautenberg uses) to get an undecidable sentence just assuming consistency relies on proving that a fixed point for not-RProv is undecidable. But that doesn't immediately give us the result that there's a Pi_1 undecidable sentence. On the other hand, e.g. Raymond Smullyan in Chap. VI of his wonderful Gödel's Incompleteness Theorems uses a slightly different construction that does get us a Pi_1 undecidable sentence: it is perhaps closer to Rosser's original, but it doesn't use the now standard Rosserized proof predicate. The two arguments are evidently very closely related, however. But exactly how?

Well, this is hardly a deep expository problem! But I confess it did take me a while, after a false start, to make the obvious connection. The result is here: an updated section for the book (which will appear in the next revised printing). It still gives much the same original version which shows that a fixed point for not-RProv is undecidable, and then I hope smoothly segues into showing how to give what is in essence the original Rosser/Smullyan version that yields a Pi_1 undecidable sentence. Obvious when you see how, and I kick myself that this wasn't in the previous printings of the book.

Do please let me know if you still spot some errors!!!

Functions and gunctions

Tim Gowers has a very nice piece on his blog about functions, multivalued functions, relations and the like, called "Why aren't all functions well-defined?".

The book problem

So you start buying books -- I mean academic, work-related, books of one kind or another -- in your late teens. As retirement age looms you've been doing it for more than forty-five years. Suppose you average a couple of books a month. Not that very difficult to do! You buy a few current books on topics that you are working on; books for reference; books you feel you should read anyway, given the ripples they are producing; books for seminars or reading groups you belong to; books it is useful to have to hand for teaching (the textbooks the kids are reading, or just useful collections of articles, before the days when everything was online). It very soon mounts up. Add in a few review copies, freebies, books given by friends, serendipitous finds rescued from the back of obscure second-hand bookshops (I got a set of Principia Mathematica that way). Then without any effort at all your modest library is steadily growing at thirty books a year or more. But go figure: that's already around 1400 books as you get to the end of your career. I've been a bit more incontinent than some, but actually not a lot (especially as my interests have rather jumped about). Say I've acquired 1750 over the years. I've got rid of a few books from time to time, of course, though I've been absurdly reluctant to let them go: but overall, I've still probably got not far short of 1500. Which, I agree, is a stupid number to end up with -- but (as we've seen!) it's easy enough to end up there without a ridiculously self-indulgent rate of book-buying as you go along.

Soon enough, I'm going to lose an office; and we're trying to declutter at home anyway. So over the coming weeks and months I need to cut that number down. A lot. Near halving is the order of the day. What to do?

Most of the Great Dead Philosophers and the commentaries can go -- I can't see myself ever being overwhelmed by a desire to re-read Locke's Essay, for example (and anyway I can always get the text online). But that doesn't make much of a dent, as I was never much into the history of philosophy anyway. I can get rid of some of the books-for-teaching, and old collections of articles whose contents are now instantly available on Jstor. But that doesn't help particularly either. So now it gets difficult.

It could just be neurotic attachment of course! But I like to think that there is a bit more to it than that. I'm sure I'm never going to seriously work on chaos again, so -- though it was great fun at the time -- I guess I will let the chaotic dynamics books go fairly easily. I'm also pretty sure that I'm never going to seriously work on the philosophy of mind again, and I've never done anything in epistemology: but just axing the phil. mind and theory of knowledge books seems to go clean against how I think of philosophy, as the business of trying to understand “how things in the broadest possible sense of the term hang together in the broadest sense of the term” as Sellars puts it. And anyway, some of the issues I'd like to understand better in the philosophy of mathematics seem to hang together with broader issues about representation and about knowledge. So perhaps I need to hang on to all the mind and knowledge books after all ....?

No, no, that way madness lies (or at any rate, swamping by unnecessary books). After all, Cambridge is not exactly short of libraries, even if I do dump something I later find myself wanting to read again! So, I'm just going to have to be brutal. A few old friends apart, if I haven't opened it in twenty years, it can certainly go. If it is just too remote from broadly logicky/phil mathsy stuff, it really better go too. Sigh.

PS Before more readers write asking for books, I should say that I have charitable plans!

Gowers on Razborov's theorem about monotone circuit complexity

I mentioned before that I'd been to Tim Gowers's lectures on computational complexity. As I noted before, videos of his lectures are available here. But, as promised, he has also written up the proof which was the topic of the first part of the course, namely Razborov's demonstration that the monotone circuit complexity of the clique function is superpolynomial. You can read it here. Tim Gowers puts a lot of effort into making the ideas seem reasonably "natural". Enjoy! -- if you have a taste for this sort of thing.

It's tough (reprise)

I was on leave last Easter term, and so not examining. But the previous year I commented here, under the heading "It's tough being a philosophy student",

It strikes me again while marking that it's quite tough being a philosophy student these days: the disputes you are supposed to get your head around have become so sophisticated, the to and fro of the dialectic often so intricate. An example. When I first started teaching, Donnellan's paper on 'Reference and Definite Descriptions' had quite recently been published -- it was state of the art. An undergraduate [indeed, a final year undergraduate] who could talk some sense about his distinction between referential and attributive uses of descriptions was thought to be doing really well. Just think what we'd expect a first class student to know about the Theory of Descriptions nowadays (for a start, Kripke's response to Donnellan [on our first year reading list!], problems with Kripke's Gricean manoeuvres, etc.). True there are textbooks, Stanford Encyclopedia articles, and the like to help the student through: but still, the level of sophistication we now expect from our best undergraduates is daunting.

The same basic point struck me just as forcibly this year. Except perhaps now I'd say that textbooks and the Stanford Encyclopedia in some ways make things even tougher for students. Here's a very good, well-briefed student: they've got their head round X's excellent text book presentation. They write four and a half crisp sides on topic, organizing the necessary points covered by X to answer the question set. Before the textbook appeared, we'd have been delighted with the answer. Now we read the same script and think, yeah, fine, a competent rehearsal of X's treatment -- so nothing outstanding. So how is the poor student to really impress? It gets harder.

Thank heavens that's over ...

I've been chair of the examining boards for Parts IB and II of the Philosophy Tripos (so that's the second and third [final] year exams here). The process is now over, reasonably painlessly for me.

But it's not so painless for a good handful of disappointed students. For we still have to do the increasingly pointless task of dividing performances into "first class", "upper second", etc. This was, of course, always an artificial business. But at least once upon a time the division at the top approximately corresponded to the distinction between the really outstanding and the rest (and very few expected/hoped for a first). Now, with grade inflation, a first is more in reach, with that first/upper second divide coming further down the rank order. But it typically seems to fall bang in the middle of a bunch of really pretty good if not quite outstanding students, some of whom were just that bit luckier with the way the exams went for them than the others. It makes no defensible sense.

Another very warm recommendation

Hard on the heels of Viktoria Mullova's re-recording of the Bach Partitas, and Angela Hewitt's re-recording of the Well-Tempered Clavier, Imogen Cooper is re-recording late Schubert. I love her earlier recordings on Ottavo; but this first disk in the projected new series is even better.

David Cairns in the Sunday Times gets it right: "The intervening years have seen a deepening understanding of this wonderful repertoire. The range of colour, the subtle details, the singing line, the freedom of tempo within the driving momentum, the haunting and haunted beauty, are greater than ever." Revelatory in fact. Getting off the marking treadmill and listening to this has made a wonderful pause.

Oh, and another musical delight. I just can't think what prompted me idly to visit the Wigmore Hall website again this afternoon (five minutes, in fact, after getting the cheering e-mail from CUP to say they were putting things right), but I was amazed to find that a little block of the very best seats for Viktoria Mullova's Bach recital in September had become available. So I was able to snap up a couple after all! I am thrilled to bits.

All's well that ends well

It was by the sheerest fluke that I discovered that there had been a third printing of my Gödel book. I was in Waterstone's in Bloomsbury with time to kill, looking through the maths books, and there were a couple of copies of my book. And (as you do!) I was flicking through it, and found that (a) there had been another reprint without checking with me to see if I wanted to correct anything, and (b) in fact the reprint reproduced the original version, not the corrected second printing. On the scale of world disasters, this perhaps doesn't register (I tell myself). But I was damned cross all the same.

I'm pleased to report, then, that CUP have been more than apologetic. They have hung, drawn and quartered the culprit; are changing procedures so it can't happen to anyone else's book; are going to withdraw all the copies and pulp them; and I'm going to get a fourth reprint with whatever further corrections I want to make. Which is, all-in-all, an excellent outcome. Though, as I said, all the result of a fluke discovery.

The Wisdom of Wikipedia

Ye gods. The Wikipedia entry for Definite Descriptions until a moment ago read:

Bertrand Russell ... proposed according to his 'theory of descriptions' that when we say "the present King of France is bald", we are making three separate assertions:
1. there is an x such that x is the present King of France.
2. for every x that is the present King of France and every y that is the present King of France, x equals y (i.e. there is at most one present King of France).
3. for every x that is the present King of France, x is bald.

So Russell solved a problem about a sentence with a non-denoting description by analysing it into a conjunction of three sentences with the very same non-denoting description. Terrific.

I thought about leaving it as a bear trap for unwary students cribbing essays. But I couldn't, and it's been minimally corrected. It will interesting to see how long that lasts before some idiot changes it back.