Monday, November 06, 2006

On Opera

A number of collections of Bernard Williams's papers have been put together posthumously. But surely the best has to be the latest, the newly published On Opera which collects together a number of pieces he wrote for various scattered occasions. The four short pieces on Mozart, in particular, are simply wonderful: insightful, subtle, humane, passionate in their commitment to the idea that the best opera is worthy of our fullest engagement and of serious critical response. Read them.

Thursday, October 26, 2006

Back to work: SOSOA

I have been mightily distracted from this blog by, first, trying to get the Gödel book into a state where it could go to CUP's proof-reader and then, second, by the beginning of term. But the book is off, and life is settling into what passes for normality in term-time.

The high point so far is our new Mathematical Logic Reading Group (started by popular request). We are starting by working through the opening chapter of Simpson's Subsystems of Second Order Arithmetic. The trouble we are having--wearing our philosophical hats--is to get the five key subsystems that Simpson highlights aligned to clear philosophical motivations. We can do that for ACA0; but not, for example, for the base system RCA0 with its curious mismatch between its Delta1 comprehension axiom and Sigma1 induction. And it is worrying--isn't it?--that the chosen base system resists a clear conceptual defence. I'll report back if we come to any less inchoate conclusions.

Sunday, September 24, 2006

Indexing woes

Indexing a book is no fun. None at all. Yet it can be so annoying when a book has a perfunctory index that I feel compelled to try to do the job decently.

You can only work on so many pages at a stretch. Distractions are needed. One that works for me is opening up sci.logic in Google groups every so often and sounding off. Hence a rash of posts battering away at some of the dafter stuff there. Who knows if anyone appreciates it ... but it keeps me amused, and is one of the more harmless ways of wasting time on the web.

Tuesday, September 19, 2006

Coffee Time in Memphis

Passing the CUP bookshop, I couldn't resist picking up a copy of Béla Bollobás' brand new The Art of Mathematics: Coffee Time in Memphis -- no less than 157 mathematical problems and their solutions, problems (he says) of the kind that would have delighted Littlewood and Erdös.

Here's the very first in the book. A lion and a Christian in a closed circular Roman arena have equal maximum speeds. Must the Christian in the end be caught by the lion? Here's another later one: Is an infinite family of nested subsets of a countable set necessarily countable. (These are fun, because it is difficult to shake off the temptation to say that the answer in each case is "yes" when it is "no".) Hours of amusement to be had here.

But I suspect that there are two kinds of mathematicians, puzzle-setters and puzzle-solvers on the one hand, and (for want of a better word) more philosophically minded mathematics who want to see the deep interconnections between Big Ideas. Erdös vs. Gödel, perhaps. Once upon a time I used to be fairly good at the puzzling; but these days, it's Gödel for me.

Monday, September 18, 2006

Passing it on

I've just put another full draft of the Gödel book online. There's an amount of work still to be done (in particular, I've yet to take account of some comments I've had on the last chapter); but things are progressing towards a terminus. One task now, while I'm thinking about more substantive things as well, is to decide what kind of index or indexes to do. What a thrill.

I've been distracting myself a bit by dropping into the newsgroup sci.logic and posting in some of the threads. Which probably shows that I need to get a life. Yet I can't help finding it irritating (indeed offensive) when loud-mouthed ignorant blockheads are allowed to dominate a public forum which can occasionally can be very useful. So I've been diving in and trying to help sort things out here and there.

Two enthusiastic book recommendations, one logic-related, one not. First, I didn't know Piergorgio Odifreddi's Classical Recursion Theory before, but I've been quickly working through it and it is excellent -- I very much like the style and pace. In a way, I'm quite glad that I didn't read it before or I might have been tempted to follow some of his nice modes of presentation. As it turns out, the treatment in my book is nicely complementary at various points.

The other, my late-night book at the moment, is Alan Bennett's Untold Stories. Perhaps I should take the words at the end of his Introduction, which he quotes from his own play The History Boys, as the motto for the Gödel book: "Pass it on. Just pass it on." For that's exactly what I'm trying to do ...

Thursday, September 07, 2006

And another update

A revised version of Chapters 1 to 26 is now on-line. Next, the two chapters which probably need the most work/thought, so off to the Moore library again to minimize distractions.

Friday, September 01, 2006

Another Gödel update

I've been wrestling with that loose and baggy chapter which needed carving into two. Annoying that what should have been a simple task took so long, but I think I've cracked it. So the latest version of what are now the first 23 chapters of the book can be downloaded from the website.

Greg Restall has a link to a terrific Australian radio talk on 'they' as a singular pronoun. Which reminds me I'd better check through my book that I haven't, for example, called all logicians 'him'.

[Added] Damn. Heaven knows why, but I still find after all these years using computers that when I waste a tree and print out hard copy I immediately spot glaring errors that I hadn't noticed on-screen. Very odd. So there's now a better version of those first 23 chapters on-line.

Thursday, August 24, 2006

Bad news for trees ...

... but very good news for me! CUP have just agreed definitely to publish my Gödel book, having had a very positive "clearance review" from an obviously Very Wise Reader with Impeccable Logical Judgement. It just remains to continue working away improving it here and there, and taking account of the very assorted but very useful comments I'm getting (including from the Very Wise Reader). The next major task: to disassemble the rather rambling Chapter 22 and put it back together as two chapters.

Meanwhile, the project of getting on top of category theory will inevitably have to be put on the back burner for a while.

Monday, August 21, 2006

Joined up thinking and noisy cafés

Jacob Plotkin has e-mailed to point out a stupid mistake just five pages into the previous version(s) of the Gödel book. I'd given a really, really bad reason for saying (what is true) that the incompleteness of arithmetic entails the incompleteness of the theory of rational fields. Of course, it's not enough for Gödelian incompleteness to carry over to a theory T that T can define 0, 1, 2 and so on (and knows about adding and multiplying these). T has got to be able to define a predicate Nat applying to the numbers so that T can replicate numerical quantifications. Only that way can T count as e.g. embracing Robinson arithmetic, and hence be incomplete-if-consistent for Gödelian reasons. Well, Q, the standard theory of rational fields, can define a suitable predicate Nat, so incompleteness does apply. But that is not at all obvious. In fact, defining Nat in Q was part of the work that Julia Robinson got her PhD for (see her JSL 1949 paper).

Now I kind of knew all that, but it didn't stop me writing something that completely ignored it. And it stayed in a number of successive drafts. These kinds of cognitive glitches -- these failures in joined up thinking -- are very odd, and maddeningly annoying when you succumb to them. (I once saw my wife, who'd spent some of the afternoon making a large pot of chicken stock, very attentively pouring the stock away down the sink, carefully saving the boiled bones and vegetables ...)

Another psychological oddity: why do I often find it easier to read in my favourite noisy Italian café (Savino's, since you ask) with Italian radio blaring and a lot of comings and goings, than in a quiet library which can be all too conducive to sleepiness. I don't think it is just the supply of espresso. Presumably it is something to do with the noise and bustle keeping part your brain alert for signs of danger and threat in the background, and so stopping processing from shutting down ...

Tuesday, August 15, 2006

How to make life difficult for yourself

A posting on philos-l, on corner quotes:

Choose a common font such as Arial. You'll find a good enough corner there somewhere. Copy the symbol you want so you have it on the clipboard, then paste it into a Word document. THEN shrink it, adjust the baseline shift, etc., and you'll have as good a corner quote as any fancy font will get you.

So much easier than typing \ulcorner or \urcorner, eh?

I suspect that the reason we still see people talking about this sort of simply daft palaver with the awful Word has nothing much to do with some intrinsic difficulty in learning LaTeX (because basic mark-up is a piece of cake), but more to do with the off-putting look of the standard manuals which makes it seems that LaTeX is only for hard-core scientists and mathematicians, etc.

Partly that's because the manuals spend a lot of time on LaTeX's stunning maths typesetting capabilities, which is understandable. But also the tendency has been (especially in the Guide and the Companion) to write manuals that go absolutely clean against the LaTeX philosophy of separating structural mark-up from typographically fine tuning. So the manuals tell you e.g. both how to mark up a list and how to do all kinds of clever fine tuning in the same few pages, and hence they bury the terse headline news -- all you really need to know -- in a mess of unnecessary detail. I'm almost tempted to try my hand at writing a logically structured manual for non-scientists!

Greg Restall on arithmetic

Greg Restall has put a very nice paper online, called 'Anti-realist classical logic and realist mathematics'. I've always been tempted by logicism in the very broadest sense: but Greg's critics, of course, will say that he's just smuggled the rabbit into the hat before pulling it out again. Still, his piece is nicely thought-provoking.

Oddly, given his multiple-conclusion logical framework, Greg doesn't mention Shoesmith and Smiley's great book in his biblio. (Very regrettably, it had the bad luck to be published in 1978, around when a number of publishers used early computers to print books with what looked like typewritten pages. The first edition of Fogelin's fine book on Wittgenstein suffered the same fate. And in both cases, I think the repellent and amateurish look of the results was enough to put readers off and stop the books making the impact they deserved at the time. At least Fogelin got a properly printed second edition. But Shoesmith and Smiley has gone out of print, and seems widely forgotten.)

Sunday, August 13, 2006

Gödeling along again

I've just posted a "maintenance upgrade" of the first 14 chapters of An Introduction to Gödel's Theorems on the book's website (and, now I've got a bit of time, redone the site from scratch as well so it is a lot neater). As I work through the book again, I've not myself yet found anything that needed drastic emergency surgery, though the old Chapter 14 messed up at one point, conflating Frege and Russell. Oops. I've managed to delete a few distracting paragraphs and tidy some discussions enough to save four pages so far, which will gladden the publisher's heart.

About 500 people have now downloaded the book. I guess I don't really want 500 sets of comments at this stage in the game -- no chance of that, though! Still, it would be very good to get a few more than the very small handful I've had so far. Comments can be immensely helpful, often in unexpected ways. Keep them coming!

Friday, August 11, 2006

Categories: episode three

Kai von Fintel has just e-mailed, to send a link to the Good Math, Bad Math blog on category theory which is excellent -- a series of mini-essays on concepts of category theory with some very helpful introductory explanations of some of the Big Ideas. Worth checking out, so thanks Kai!

I've now read quite a lot of Steve Awodey's new book. Disappointing: or at least, it doesn't do quite what I was hoping it would do. Awodey's two papers in Philosophia Mathematica were among the pieces that got me interested in category theory in the first place (see his 'Structure in mathematics and logic: a categorical perspective', 1996, and his reply to Hellman, 2004). So I suppose I was hoping for a book that had more of the discursive, explanatory, commentary that Awodey is good at. But there's very little of that. And although Awodey says in the preface that, if Mac Lane's book is for mathematicians, his is for 'everyone else', in fact Category Theory is still pretty well orientated to maths students (for example, there is a telegraphic proof sketch of Cayley's Theorem that every group is isomorphic to a permutation group by pp. 11-12!). Of course, there are good things: for just one example it helped me understand better the general idea of limits and colimits. But I wouldn't really recommend this book to the non-mathematician.

So over the next week or two, I think it's Goldblatt's lucid Topoi, and Lawvere and Rosebrugh's Sets for Mathematics for me.

Wednesday, August 09, 2006

Slow work ...

It's slow work, going through my Gödel book a couple of chapters at a time checking for typos (down to the level of missing brackets or periods, 'x' for 'y', etc.), and looking for thinkos, sentences where the prose could be improved, passages where the book drags unnecessarily, paragraphs which could be deleted, cases where what happens in one chapter doesn't quite tally with what happens in another, and so on and so forth. Thankfully, I'm not finding too much that needs attention yet; but there is more than enough to make the exercise well worthwhile.

It's slow work too, getting into category theory. As I remember it, it was a lot easier mastering quite a bit of non-linear dynamics (when I was working on what became Explaining Chaos). I suppose that it could just be that I'm getting too old to readily learn new tricks. It could be that category theory's high level of abstraction makes it more difficult to get your head around. But I rather think that it's because I then had a whole stack of wonderfully clearly written, well-structured, zestful, example-packed, highly explanatory, dynamics books to lean on, while category theory seems not at all so well served.

But I'll press on, as the partially understood glimpses I'm getting are intriguing! Being in sight of retirement, with little prospect of promotion, at least has one very enjoyable advantage, which I might as well make the best of: I can cheerfully follow such interests wherever they happen to take me, without getting at all fussed about whether they will ever lead to publications that will "count".

Tuesday, August 08, 2006

Categories: episode two

A copy of Steve Awodey's new Category Theory (Oxford Logic Guides 49) has just been delivered. His preface starts

Why write a new textbook on Category Theory, when we already have Mac Lane's Categories for the Working Mathematician? Simply put, because Mac Lane's book is for the working (and aspiring) mathematician. What is needed now ... is a book for everyone else.

First impressions look very encouraging, though the book covers quite a lot in under 250 pages, judging from the table of contents, so the pace promises to be pretty speedy. (Grumble to OUP: given this is intended to be a textbook for a relatively wide audience, why exactly is it published only in hardback and at the extremely steep price of £65 pounds/$124.50?)

I've just noticed too that Robert Goldblatt's Topoi: The Categorical Analysis of Logic -- which has been out of print for ages -- has been republished by Dover (Amazon have it for £14.63/$19.77 which is a bargain for a book twice the length of Awodey's). I found before that Goldblatt's book starts pretty gently in a very helpful way, even though it seems to accelerate a bit alarmingly after the first three chapters. Anyway, my plan of action now is to parallel-process Goldblatt, Awodey, and Lawvere/Rosebrugh. Watch this space for further reports!

(Mmm, I hope that one or two greedy booksellers on who have been trying to sell on second-hand copies of Topoi for quite extortionate prices up to $500 have just found themselves stuck with now unwanted stock!)

Friday, August 04, 2006

Categories: episode one

I said I'd post occasional progress reports on getting to grips with Category Theory, to pass on recommendations about what I've found helpful, etc. (Perhaps I should explain that -- when trying to get into a new chunk of maths or math. logic -- I find it works best to dive in and read a number of books quite quickly, skipping and skimming when the mood takes me, rather than plod very carefully through one key text. Also, though I know a few bits and pieces, I thought I should start over again from the very beginning.)

Two frequent recommendations for entry points are Lawvere and Schanuel's Conceptual Mathematics (CUP, 1997), and Lawvere and Rosebrugh's Sets for Mathematicians (CUP, 2003). But I can only say, give the first book a miss. It's not very good: the authors seem to have no clear idea about their intended audience, so they veer between the irritatingly condescending/extremely laboured on the one hand, and sudden jumps in difficulty/sheer opaqueness on the other. For just one example, it is very difficult to believe that someone who needs a noddy explanation of why proving if p, q establishes if not-q, not-p is going to make anything at all of the sudden excursus on Gödel and Tarski at p. 307. But worse, you can get to the end of the book with no clear idea about what it is supposed to have achieved, or why it might matter. The second book is so far proving also a bit uneven but much better.

I'm dipping into various expository/philosophical articles as I go along. One I've just come across which I found prokoving and illuminating is Barry Mazur's 'When is one thing equal to some other thing?'. Recommended.

Wednesday, August 02, 2006

Getting categorical

For a bit of light relief from matters Gödelian, I'm hoping to spend the next couple of months getting more to grips with category theory (well, and why not? -- there are world-class category theorists just down the road at CMS, Martin Hyland and Peter Johnstone for a start, and it might be fun to be able to sit at the back of the category theory seminar and have some sense of what is going on). So I've gathered a somewhat daunting stack of books, and am plunging in ... I'll report progress!

Meanwhile, over 250 people have downloaded the Gödel book, and I've already had some very useful comments. In particular, Toby Ord has quite rightly taken me to task for getting a bit overexuberant in saying of Section 33.5 that it gives a proof that the Church-Turing Thesis entails the First Incompleteness Theorem. What the section does, in fact, is take the Kleene Normal Form Theorem and deduce incompleteness, assuming CTT along the way. But like any appeal to CTT in proving a formal result, that's a labour-saving device that is dispensable -- and if it weren't, we'd be able construct a related counter-example to CTT (as I'd already pointed out in Section 28.7). So really, I guess I should have said, less dramatically, that KNFT entails incompleteness. Still, it's a lovely argument if you don't know it: and the point remains that in thinking about CTT, and proving recursiveness is equivalent to Turing computability as a step in its support (and that equivalence yields KNFT very easily), then we get incompleteness almost immediately -- and that's surely a nice surprise!

Monday, July 31, 2006

Gödel at long last

Back from Tuscany, with -- at long last -- a complete draft of my book on Gödel's Theorems; if you are interested, do download a copy of the PDF, for all comments/suggestions will be very, very gratefully welcomed (I'd rather hear about gruesome mistakes now while there is a chance to change things!). I've just sent the PDF off to the publishers for a final review: it is late and over the originally contracted length, so fingers crossed. But I've already cut out an amount of stuff, and I don't see how to cut out more without spoiling things.

I was staying at my daughter's house at Certano near Siena. Sadly that was last time I'll be there as they are moving. I'll greatly miss the view from the kitchen table where I often wrote.

It's a strange feeling 'finishing' a book -- scare quotes, because I'll have to do an index and tidy some of the typography and read for typos and thinkos and respond to comments: it won't be finally gone for weeks. But there comes a point with any book where, although you know you must be able to improve it, you basically have to let it go. Which is both a relief and an anxiety.

Saturday, June 24, 2006

Thank goodness that's over

Examining over for another year. Thank goodness. I don't particularly mind the process of marking tripos papers itself (though there is that inevitably huge and always rather dispiriting gap between what you tried to put across and what comes back in the generality of scripts). But having to run the show has its tense moments. But justice, of course, was perfectly done to everyone, as we all retained our immutable grasp of the Platonic form of the first-class script and marked accordingly.

Off to London on Thursday to the annual meeting of the Analysis committee. It seems a very long time ago that I was editor, and I can't really recall why it then struck me as such a bright idea to spend twelve years at so time-consuming a job. But the journal continues to flourish, which is good. And there was time for a quick detour to visit my favourite Nereids nearby. So now, back -- at last -- to full-time Gödel!

Saturday, June 17, 2006

"The best and most general version"

I'm still half-buried under tripos marking, but the end is in sight. And I'm Chair of the Examining Board for Parts IB and II this year, which is also not exactly an anxiety-free job. But between times, I'm trying to reorganize and finish the chapters of my book on the Second Theorem. I'm stuck for the moment wondering what exactly to say about "the best and most general version of the unprovability of consistency in the same system" which Gödel so briefly alludes to in the first part of his 1972a note (which repeats a footnote from 1967). Feferman in his editor's introduction explains things by bringing to bear Jeroslow's 1973 result. But it isn't entirely clear to me that this rather esoteric result must be what Gödel had in mind.

Meanwhile, a nerdy footnote. There's an even better new version out of NoteBook just out (if you are a Mac user, it really is just indispensable, and the academic price is absurdly low).

Was Gödel right?

A coincidence. Rereading John Dawson's Gödel biography Logical Dilemmas, I've just got to the point where Dawson recounts how Gödel thought he'd discovered an inconsistency in the American Constitution, which would allow a dictatorship to arise (pp. 179-80). And then the same day I come across Elizabeth Drew's recent article in the New York Review of Books explaining some of the ways in which the Bush White House has grabbed powers to itself and undermined the constitutional settlement between the three branches of government. Perhaps Gödel's anxieties were well founded.

Tuesday, June 06, 2006

Gödeling along

I'm still working away on my draft book on the incompleteness theorems, in between the delights of marking tripos papers. I've just uploaded a new near-final(?) version of Chapters 1 to 22 -- the first two hunded pages -- to; all comments are still most welcome. Don't all rush at once ...

Sunday, May 28, 2006

It's that time of year again ...

... when I'm buried in tripos marking. Distractions between marking sessions are necessary. So I've just finished reading Margaret Atwood's The Penelopiad which made a wonderful diversion from the usual mixed bag of metaphysics scripts.

Incidentally, the white smoke has at long last gone up from the consistory chapel window, and the Knightbridge Professorship has been offered to X. But unlike popes, who don't get to negotiate their terms, potential professors do. So we'll have to wait and see if X indeed arrives. [Later breaking news, 11 June: X = Quassim Cassam, who is indeed coming to Cambridge from Oxford via UCL for January 2007.]

Tuesday, May 16, 2006

Libraries should be circular?

When I was in Aberystwyth, I had a decent sized room in the Hugh Owen Building which is halfway up Penglais, with panoramic views over Cardigan Bay. In Sheffield, I had a huge room on the 12th floor of the Arts Tower -- and while the daytime urban view wasn't exactly a delight, on winter evenings the transformation into a glittering landscape of lights was magical. These days I have a very small room in the Faculty, with a window into the grad. centre and otherwise tiny windows too high to look out of, which isn't as bad as it sounds, but equally isn't very enticing.

So I work a lot in the Moore Library. It took me a while to really "get it", but now it strikes me as in many ways a quite splendid building, and I love being there. The reading tables run around the perimeter, so you are looking out to trees and to the modern buildings of the rest of CMS; even when the library is busy, you can only really see a few people either side of you because of the curve of the building and the book shelves which are arranged as along the spokes of a wheel. And while the bookstacks in the UL seemingly run off to infinity (so you can feel lost in a Borgesian nightmare), there is a sense that here the readers are surrounding the mathematical knowledge shelved behind them. There is a rather calming feel to the place, which draws me back especially when things aren't going well with my book. So I should get down there now ...

Saturday, May 13, 2006

Tired of ontology?

It requires a certain kind of philosophical temperament -- which I seem to lack -- to get worked up by the question "But do numbers really exist?" and excitedly debate whether to be a fictionalist or a modal structuralist or some other -ist. As younger colleagues gambol around cheerfully chattering about these things, wondering whether to be hermeneutic or revolutionary, I find myself sitting on the side-lines, slightly grumpily muttering under my breath 'And who cares?'.

To exaggerate a bit, I guess there's a basic divide here between two camps. One camp is primarily interested in analytical metaphysics, or epistemology, or the philosophy of language, and sees mathematics as a test case for their preferred Quinean naturalist line (or whatever). The other camp is puzzled by some internal features of the practice of real mathematics and would like to have a story to tell about them.

Well, if you're tired of playing the ontology game with the first camp, then there's actually quite a bit of fun to be had in the second camp, and maybe more prospect of making some real progress. In the broadest brush terms, here are just a few of the questions that bug me (leaving aside Gödelian matters):

  1. How should we develop/improve/augment/replace Lakatos's model of how mathematics develops in his Proofs and Refutations?
  2. What makes a mathematical proof illuminating/explanatory? (And what are we to make of unsurveyable computer proofs?)
  3. Is there a single conceptual grounding for the standard axioms of set theory? (And what are we to make of the standing of various large cardinal axioms?)
  4. What is the significance of the reverse mathematics project? (Is it just a technical "accident" that RCA_0 is used a base theory in that project? Can some kind of conceptual grounding be given for that theory? Would it be more principled to pursue Feferman's predicative project?)
  5. Is there any sense in which category theory provides new foundations/suggests a new philosophical understanding for mathematics?
There's even a possibility that your local friendly mathematicians might be interested in talking about such things!

Sunday, May 07, 2006

Laws of nature

I'm giving just four second-year lectures on the philosophy of science this term, revisiting Lakatos (I'm a long-time fan). Last year I talked instead about laws of nature; rather to my surprise I found myself taking exactly the opposite line from that I used to take in supervisions, and warmed to a wild Humean subjectivism. Re-reading the notes from the lectures on laws they seemed at least provoking enough to be worth handing out again to this year's class. I don't promise that I believe any of this stuff: I was just interested to see if you can play the game the Humean way.

Ancestral logic

One of the many things I want to do once I've got my Gödel book finished is to slowly trawl through the first twenty years (say) of JSL to see what what our ancestors knew and we've forgotten.

I was put in mind of this project again by finding that John Myhill in JSL 1952 ('A derivation of number theory from ancestral theory') already had answers to some questions that came up in re-writing a section of the book last week.

As is entirely familiar, we can define the ancestral of a relation R using second-order ideas: but it doesn't follow from that that the idea of the ancestral is essentially second-order (as if the child who cottons on to the idea of someone's being one of her ancestors has to understand the idea of arbitrary sets of people etc.) Which in fact is another old point made by e.g. R. M. Martin in JSL 1949 in his 'Note on nominalism and recursive functions'. So there is some interest in considering what we get if we extend first-order logic with a primitive logical operator that forms the ancestral of a relation.

It's pretty obvious that the semantic consequence relation for such an 'ancestral logic' won't be compact, so the logic isn't axiomatizable. But we can still ask whether there is a natural partial axiomatization (compare the way we consider natural partial axiomatizations of second-order logic). And Myhill gives us one. Suppose R* is the ancestral of R, and H(F, R) is the first-order sentence which says that F is hereditary down an R-chain, i.e. AxAy((Fx & Rxy) --> Fy). Then, putting it in terms of rules, Myhill's formal system comes to this:

  • From Rab infer R*ab
  • From R*ab, Rbc infer R*ac
  • From H(F, R) infer H(F, R*)
where the last rule is equivalent to the elimination rule
  • From R*ab infer (Fa & H(F, R)) --> Fb
which is an generalized induction schema. Myhill shows that these rules added to some simple axioms for ordered pairs give us first-order Peano Arithmetic. But do they give us more?

Suppose PA* is first-order PA plus the ancestral operator plus the axiom
  • Ax(x = 0 v S*0x)
i.e. every number is zero or a successor of zero. Then -- if we treat the ancestral operator as a logical constant with a fixed interpretation -- this is a categorical theory whose only model is the intended one (up to isomorphism). But while semantically strong it is deductively weak. It is conservative over PA. To see this note that we can define in PA a proxy for R*ab by using a beta-function to handle the idea of a finite sequence of values that form an R-chain, and then Myhill's rules and the new axiom apply to this proxy too. And hence any proof in PA* can be mirrored by a proof in plain PA using this proxy. (Thanks to Andreas Blass and Aatu Koskensilta for that proof idea.)

So the situation is interesting. Arguably, PA doesn't reflect everything we understand in understanding school-room arithmetic: we pick up the idea that the numbers are the successors of zero and nothing else. In other words, we pick up the idea that the numbers all stand to zero in the ancestral of the successor relation. So arguably something like PA* does better at reflecting our elementary understanding of arithmetic. Yet this theory's extra content does nothing for us by way of giving us extra proofs of pure arithmetic sentences. Which is in harmony with Dan Isaacson's conjecture that if we are to give a rationally compelling proof of any true sentence of basic arithmetic which is independent of PA, then we will need to appeal to ideas that go beyond those which are constitutive of our understanding of basic arithmetic.

Saturday, April 29, 2006

Lighten up, Ludwig

Went to the one-day Tractatus workshop here in Cambridge (the last in a series that has mostly taken place in Stirling). I was there in my role as the village sceptic.

Julian Dodd and Michael Morris kicked off with a joint talk on Making sense of nonsense. What are we to make of the fact that Wittgenstein officially seems to think of his claims in the Tractatus as nonsense (yet in the Preface he says 'the truth of the thoughts communicated here seems to me to be unassailable and definitive')? One line is that claims of the Tractatus communicate truths that can be shown but not said (the 'truth-in-nonsense' view). Another line is that actually not all the claims are non-sensical (the 'not-all-nonsense' view). Julian and Michael think there is a third way. All of the claims of the Tractatus are nonsense and they don't communicate any genuine truths indirectly either (the 'no-truths-at-all-view'); the prefatory remark is just another bit of philosophical nonsense.

This was interestingly done, though they also seem to want to suggest that the movement of thought in Tractatus, read their way, naturally leads to its mystical conclusion. I just don't see that. Somewhere in the middle of the 6.somethings, sensible readers of the Tractatus can perfectly well think "Oh come off it, Ludwig, lighten up!". The mystical guff about feeling the "world as a limited whole" is no more an upshot of what's gone before than would be, say, something like Lichtenberg's wryly amused attitude to the scattered occasions of his life.

Next up, Fraser MacBride and Peter Sullivan talked about Ramsey, Wittgenstein, and in particular the argument about complex universals. Peter hinted at, but didn't in this talk really explore, an interesting thought. Ask: 'How much do the principles of logic reveal about the nature of things/the constitution of facts?' It seems Frege answers "a great deal" (logic reveals the deep distinctions between objects, properties, properties of properties etc.) while Ramsey answers "next to nothing" (e.g there isn't a deep object/universal distinction reflected in the logical subject/predicate form). Peter suggested that there is a lot in the Tractatus that comes from Frege and a lot that feeds into Ramsey's position. Which suggests that Wittgenstein's position might be an incoherent mixture.

Finally, Mike Beaney talked about the chronology of the interchanges between Frege and Wittgenstein. And Michael Potter talked more specifically about when W. might have learnt from F. to distinguish sharply complexes and facts (early, according to Michael).

Which was all mildly instructive, though the discussions sometimes became bogglingly theological, in the way that Wittgenstein-fests can do. It was occasionally like listening to rounds of 'Mornington Crescent' without the jokes (and no, I'm not going to explain!).

Wednesday, April 26, 2006

I leave it too long ...

I leave it too long between visits to the Fitzwilliam. But since the really excellent new café started up, I've been going rather more often. Take a book, read over a coffee, then take a break to look at just a few pictures (that is surely much the best way to "do" a gallery). I was very struck again today by The Holy Family by the seemingly rather unregarded Sassoferrato. I just wish I was clearer in my mind about how an unbeliever should regard religious art, without double-think or sentimentality.

Tuesday, April 18, 2006

Universities on the cheap

Reading the Guardian isn't always good for my blood pressure. Today there is an article under the name of Tony Blair, no less, saying how important it is that "we maintain and improve the high reputation of higher education in Britain" (note, it is the reputation that has to be improved). But not, of course, because education might be a good in itself; no, it's because we want to sell the product and make the most money possible out of overseas students.

But I wonder who is going to staff these high reputation universities? Some of our brightest and best might enjoy a year of graduate study; but even here in Cambridge they seem increasingly reluctant then to launch into a PhD. And who can blame them? It could be six years more before they are in the running for a permanent academic job. Getting one is a very chancy business (since employment numbers are kept down by ludicrous staff-student ratios). And the pay is then dreadful, at least compared with what they might hope to get elsewhere. Oh well ...

FOM for neurotic logicians

Maybe it is the advancing years, but occasionally there are those moments of panic. I think "Surely it must be the case that P", guess I can see how to prove it, check out an obvious source or two, google around, and then am perhaps a bit surprised not to come across a straight proof of P. And sometimes my nerve fails: just occasionally I've asked on FOM whether indeed P. I've invariably got helpful replies. A couple of days ago, I was asking -- in effect -- how far up the Friedman/Simpson hierarchy of second-order arithmetics we have to go before we can prove Goodstein's Theorem (something not mentioned in Simpson's wonderful book). Before the day was out, I got a couple of really useful private responses, and there are now two brief but equally helpful replies on the list from Dmytro Taranovsky and Ali Enayat. What a fantastic resource this is: I'm not sure how my current book project would be going if it weren't for FOM and its archives, and I'm immensely grateful.

Oh, and the answer to my question is that ATR_0 is enough. Which I should have got from Sec. V.6 of Simpson (which tells us that ATR_0 is good at handling countable well-orderings).

Saturday, April 15, 2006

Broad's advice for writers

I'm ploughing on as fast as I can to get my Gödel book finished. I try to keep in mind the good advice that C.D. Broad used to give. Leave your work at the end of the day in the middle of a paragraph which you know roughly how to finish. That way, you can pick up the threads the next morning and get straight down to writing again. So much better than starting the day with a dauntingly blank sheet of paper -- or now, a blank screen -- as you ponder how to kick off the next section or next chapter. Instead, with luck, you face that next hurdle while on a roll, with the ideas flowing.

Well, it works for me ...

Tuesday, April 11, 2006

Real Estate

I've been using my old desktop (well, under-the-desk) G4 Mac less and less recently, so I've reorganized things so that I can mainly use its fairly new and very nice LCD monitor with my laptop when I'm at home. Wonderful. I can have the TeXShop window with the PDF of the book I'm working on displayed on the external monitor (a full page at 150%), and the TeXShop drawer open too, with all the section hyperlinks: and then the source file of the current chapter and other stuff like BibDesk is on the PowerBook screen. Why on earth didn't I think of doing this before? It's LaTeX heaven!

So message to myself: no more lusting after 17" laptops -- keep to a 15" one for portability, and get the additional real estate when you need it by plugging an the external monitor.

It all seems a very long way from thinking that WordStar on an ACT Sirius was really, really neat ...

What is it like to be a blog?

A blog with that title just has to be worth a link! (It's by a group of University of Connecticut grad students -- interesting content, and there are some nice links out into the philosophical corner of the blogosphere.)

The world inhabited by the philosophy graduate student has been changing fast in the last few years (and in very good ways). Blogs, on-line forums, and the rest obviously can do a lot to counteract the depressing sense of isolation that used to bug people writing their PhD. If local experience is anything to go by, those of us involved in running grad programs need to be thinking more about how best to help students make use of the changing world. Though, on second thoughts, they seem -- as usual -- to be doing pretty well without us ...

Saturday, April 01, 2006


The Advanced Book Exchange is simply terrific, isn't it? Search over thirteen thousand second-hand book sellers, and -- more often than not, in my experience -- you can find what you are looking for, and frequently at a decent price.

Of course, there's a downside. Booksellers can now easily check on-line what is rare and what is not, and check what others are charging. It's not that many years since I picked up the complete Principia Mathematica for £30: I can't imagine a bookseller now being so ignorant of its true worth. Still, plenty of bargains are to be had: a copy of Wolfram Pohlers' Proof Theory has just dropped through the door. I paid all of $5.95 plus postage.

It's a bit disturbing, then, to read a paragraph in Private Eye which reports that abebooks have been hiking the commission they charge to booksellers and are about to add more charges. It would a great loss indeed if they price themselves out of having such a wide coverage of booksellers.

Monday, March 27, 2006

Edinburgh: Gödel, Raphael, ...

In a world of such ready e-communication, where people put work-in-progress online, where there are terrific discussion forums like FOM, not to mention blogs and the like, I do wonder about the value of so many conferences. I'm just back from one in Edinburgh on Truth and Proof: Gödel and the Foundations of Mathematics. The first conference I'd travelled to for some time, and to be honest I wasn't really very encouraged to repeat the experience soon, good though it was to put some faces to some familiar names. In the event, only two papers were directly on Gödel, one by Richard Zach (based on the draft paper which you can read here), the other by Panu Raatikainen (based on his paper which you can read here): both interesting pieces, particularly Richard's, but I had read them long since. Oh well, ...

But Edinburgh of course was quite wonderful, not least because I got to the National Gallery of Scotland more than once. (And a happy discovery since: you can get some impression of most of their major pictures on-line, as e.g. here or here.)

Saturday, March 18, 2006

A spell broken?

Out last night to hear Dan Dennett lecture, talking about his new book Breaking the Spell. A pretty terrific lecture. But the book is, in a word, disappointing. Which is not to deny that it's full of intriguing insights and illuminating suggestions about e.g. the possible evolutionary sources of dispositions to religious belief. But the structure of the book is surely a little too meandering (I found the first 100 pages dragged), the writing too allusive, to get through to the wide audience he is aiming for. I can see why Dennett often pulls his punches. Full frontal assaults on the frankly dotty aspects of mainstream religious belief-systems would just produce an unthinkingly hostile response, while the cumulative effect of jokes, analogies, biological speculation, just-so stories, reminders of what we all know (e.g. about the variability of religious beliefs), etc., might just get under the defences of some of those he wants to reach, and give them serious pause for thought. I hope so. But the pace isn't zestful enough, the points not pressed hard enough and clearly enough to really have the impact Dennett wants. In fact, I suspect he should have written two books: a punchier, shorter, less complex book for his desired wider audience and a more fact-strewn, more analytically complex book for those who want the whole story as Dennett currently sees it.

But we'll see. And certainly, I'm all for his spell-breaking project (the spell he wants to release us from is the idea that we shouldn't treat religion as a natural human phenomenon with its own biological rationale). Dennett is dead right that we can hardly overestimate the importance of understanding more about religion as a natural phenomenon.

Friday, March 10, 2006

To begin ... a Gödel talk at CUSPOMMS

To blog or not to blog? I'm in two minds. But why not just dive in and see how it goes?

Today was my second outing this academic year to talk to non-philosophers in Cambridge about Gödel, incompleteness and the like. The first time was at a meeting of the Trinity Math. Society. Rather staggeringly, there were more than eighty people there. Perhaps not a brilliantly judged talk, but I did have good fun e.g. telling them about Goodstein's Theorem. (Having a lot of bright mathmos getting the point and smiling at the cheek of the Goodstein proof made a nice change.)

Today's outing was to give a talk at CMS to the slightly unfortunately named CUSPOMMS. A very mixed audience, we meet there approximately fortnightly for talks on the philosophy of mathematics, broadly construed. Rather perversely, I suppose, there was less philosophy than in the Trinity talk. In the event, I was explaining one pretty way of proving (a version of) Gödel's First Theorem without explicitly constructing a Gödel sentence that codes up 'I am unprovable'. The point of doing this is to counteract that familiar tendency to think that the Gödelian result must be fishy because it depends on something too close to the Liar paradox for comfort.

Paul Erdös had the fantasy of a Book in which God records the smartest and most elegant proofs of mathematical results (have a look at the terrific Proofs from the Book by Aigner, Hofmann and Ziegler). So I was aiming to outline one Book proof: a version of the talk can be downloaded here