Tuesday, June 30, 2009

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!

Friday, June 26, 2009

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 from the Sigma_1 Prf) 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!!!

Monday, June 22, 2009

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

Sunday, June 21, 2009

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!

Saturday, June 20, 2009

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.

Friday, June 19, 2009

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.

Wednesday, June 03, 2009

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.