Fixed point logics

At CUSPOMMS today, the audience was depressingly tiny, which was a great shame because Anuj Dawar gave a terrific introductory talk about the problems he is working on in finite model theory. In a particular, he said a little about the expressive power of logics which have a ‘least fixed point’ operator, and the relation of this to the question whether P = NP.

The topic of fixed point logics links up very closely with something I need to think about soon, for I’ve promised to put together a talk on Dan Isaacson’s Conjecture for a workshop next month (I mean the claim that, if we are to give a rationally compelling proof of any true sentence of the language of first-order 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). What’s the connection? Well, it is plausible that our understanding of arithmetic involves grasp of the ancestral of the successor relation (“the natural numbers are 0, the next number, the next one, the one after that, and so on, and nothing else”). So it is natural to think about theories of arithmetic which are embedded in stronger-then-first-order logics with a primitive ancestral-forming operator (i.e. a transitive closure operator, which is closely related to a least fixed point operator). We know that such arithmetics semantically entail more than PA but are unaxiomatizable. But what about partial axiomatizations of them? I know that the very natural partial axiomatization that goes back to Myhill gives us a theory which is in fact a conservative extension of PA (so that result is in harmony with Isaacson’s Conjecture: trying to pin down a concept arguably essential to our understanding of arithmetic which isn’t definable in the language of PA still doesn’t take us beyond PA). But I need to discover more about fixed point logics to see what else interesting is to be said here.

Anuj recommended Leonid Libkin’s Elements of Finite Model Theory as a good place to start finding out more. Great. I’ve ordered a copy.

Back to category theory

Back in August, I did a bit of reading on category theory. I’m now taking that up again with a group of graduate students. We’ve started working through Robert Goldblatt’s Topoi: The Categorical Analysis of Logic (an amazing bargain reprint from Dover). And this time I’m getting more of a feel for what is going on. Or at least, I have the comforting illusion of understanding — but it could all be shattered soon, when it is my turn to talk at the reading group next week, supposedly helping us through chapters 5 and 6.

Up to about half-way through chapter 3, Goldblatt proceeds at a pretty gentle pace; he then accelerates a bit alarmingly. Reading his first three chapters in parallel with the first six chapters of Steve Awodey’s Category Theory works well, however, if you have the time.

And is the effort worth it? Well, we’ll see (though my sense so far is that the answer should be very positive). But in the meantime, we’re certainly having fun …

Three cheers for Piers

It’s a familiar fact of academic life that you can go to hear a talk with great expectations of something arresting from someone who you have read with admiration, and then be bored or even irritated by a banal recycling of half-baked ideas. Equally, you can dutifully turn out to a unpromising-seeming seminar, apparently remote from your interests, feeling for some reason that you really ought to be there — and you find yourself riveted and enthused.

So three cheers for Piers Bursill-Hall, who was talking at the clumsily named CUSPOMMS last Friday. “Descartes’s Earlier Epistemology in Natural Philosophy” wasn’t exactly a title to set me alight. In the event, his talk was wonderfully entertaining but also a highly illuminating lightening tour through ancient and Renaissance takes on the problem of the unreasonable effectiveness of mathematics in its application to the material world, and Descartes’s attempt to resolve the problem without committing himself to the theologically dangerous idea of mathematics as a direct route to reading the mind of God. Enthusiasm is always engaging, and Piers has it in spades. (You can get a glimpse of his style here.)

Vice-chancellors, please note

Moscow university in the 1820s, a place of dissent and a reputed ‘hot-bed of depravity’. The Tsar appoints Prince Golitsyn Director to impose order. Herzen writes: ‘Golitsyn was an astonishing person. It was a long time before he could accustom himself to the irregularity of there being no lecture when a professor was ill; he thought that the next on the list ought to take his place, so that Father Ternovsky sometimes had to lecture in the clinic on women’s diseases and Richter, the gynaecologist, to discourse on the Immaculate Conception.’

Which no doubt improved classes no end. The university also had its own prison for recalitrant students. Models for us to emulate, surely.

So what’s it all about then?

The photographer Steven Pyke has produced another set of photos of great and not-so-great living philosophers. The style is, as with his earlier set published as a book, dramatically black-and-white, distinctly pretentious — and so, of course, in some cases the portraits are hardly recognizable.

Pyke asks his sitters to describe ‘in fifty words of so their own idea of what philosophy means’. So what’s it all about then? Ruth Millikan gives a favourite quotation of mine from Sellars: ”The aim of philosophy, abstractly formulated, is to understand how things in the broadest possible sense of the term hang together in the broadest possible sense of the term.” (I wonder how many students, at least this side of the Atlantic, read Sellars any more?)

Here are two other answers that chimed with me. David Papineau: “Some hold that the aim of philosophy is to construct theories that confirm everyday intuitions. What a dispiriting ambition. In my book, the best philosophy overturns common sense. Often, the impetus for change comes from outside philosophy, in the form of scientific or cultural innovation. The task of the philosopher is then to show how the new ideas reshape everyday thinking. Does this reduce philosophy to the status of a hand-maiden? Well, far better a hand-maiden of change than a lackey of the intellectual status quo.”

And Steve Stich: “The idea that philosophy could be kept apart from the sciences would have been dismissed out of hand by most of the great philosophers of the 17th and 18th centuries. But many contemporary philosophers believe they can practice their craft without knowing what is going on in the natural and social sciences. If facts are needed, they rely on their “intuition”, or they simply invent them. The results of philosophy done in this way are typically sterile and often silly. There are no proprietary philosophical questions that are worth answering, nor is there any productive philosophical method that does not engage the sciences. But there are lots of deeply important (and fascinating and frustrating) questions about minds, morals, language, culture and more. To make progress on them we need to use anything that science can tell us, and any method that works.”

Two talks: Autonomy and positive sets

I went this week to the Moral Sciences Club for the first time in a while. I don’t entirely know why, but I don’t find the format or atmosphere of MSC meetings at all congenial. But the speaker this week was one of our own grad students, Ben Colburn, who put up a terrific performance talking about the value of autonomy and the role of the state in promoting the autonomy of its citizens. And that’s a theme that mattered rather a lot to one of my heroes, Alexander Herzen. As it happens, at the moment my late-night (re)reading is his great My Life and Thoughts. (I have the four-volume translation of the whole thing, all 1800 pages of it. It is indeed a loose and baggy monster, but a wonderful read. I see there is a more sensible sized abridged version available these days, which looks a bargain.)

Then today Thierry Libert gave an informal talk at CUSPOMMS on positive set theory. I confess this was all news to me. I’m not sure I have a real grasp on what the resulting ‘filled out’ universe of sets is like, but I got intriguing glimpses. Something else, then, to add to list of things to chase up, given world enough and time …

For Mac geeks …

I’ve just become a real convert to DevonThink, which seems to be by far the best solution for organizing a whole collection of downloaded PDFs of articles, stored emails, lecture notes and the like. I haven’t yet begun to explore its much-praised clever AI engine for e.g. finding other material related to some article. But even while I am just dumbly using it to search through a folder of PDFs and browse the results, I think it is going to earn its keep a dozen times over.

I wish I could find a use too for Scrivener which seems a great concept, beautifully implemented. But it just isn’t suitable for the way I write — everything I do these days seems to be symbol-laden, and is crying out to be done in LaTeX from the start. But if I ever write my great novel of the follies of academic life …

Gentzen, praise and regret

By popular request, I’m continuing an informal lunchtime Mathematical Logic Reading Group with a number of grad students. This term, the plan is to do a ‘slow read’ of Gentzen’s two great papers on the consistency of arithmetic. But we started today with the lecture he wrote between the two papers, ‘The concept of infinity in mathematics’. This is short, very accessible, and gives a great sense of the conceptual problems that Gentzen sees as shaping his work. It is also very clearly sets out the headline news about the structure of his (first) consistency proof and about its supposed finitist/constructivist credentials.

The lecture has its shortcomings — there’s a general murkiness about the notion of a ‘constructivist’ view of infinity (why should a constructivist view of sets in the sense of the paradox-busting idea of a hiearchy in which sets at higher levels are formed from sets already constructed at lower levels go along with a constructivist rejection of excluded middle at the level of classical analysis?). But still it is wonderful, thought-provoking stuff.

I was moved to try editing the piece on Gentzen on Wikipedia in very modest ways (e.g. adding that he was Hilbert’s assistant, which you might have thought was a rather central fact about his intellectual trajectory). But twice my efforts were removed. And I wonder if that was because I’d over-written the claim that he was imprisoned after the war “due to his Nazi loyalties” (I’d put something less specific, but more detailed, i.e. the story as told by Szabo in his introduction to the Collected Papers). Is it true about Gentzen having Nazi sympathies? Regrettably it seems so. Discovering this was really rather depressing, as I’ve belatedly become a great admirer of Gentzen.


One of my Christmas presents was Renée Fleming’s Homage: The Age of the Diva. It is luxurious, wonderful, singing, with some of the arias quite unknown to me (and I’d have thought to many opera fans). A few of Fleming’s interpretations are perhaps a bit over the top — there is a stunningly sustained note near the end of “Vissi d’arte” which is awesome but … Though it certainly does make the hairs stand up on the back of your neck, so let’s not get too purist!

The CD insert booklet has a little about Fleming’s great predecessors in this repertoire. One name stood out for me. For my mother has a copy of Kobbé’s Complete Opera Book, given her as a girl: the evocative black and white photographs include a publicity photo of the Moravian soprano Maria Jeritza in her costume as Turandot. That picture made a deep impression on me when I was small! Jeritza was one of Puccini’s favourite singers; but I’ve only ever heard short clips of her voice. I feel an internet search coming on …

Size matters

One thing that distracted me for a while was getting myself a new laptop, a 17″ MacBook Pro. Simply fantastic, of course. Huge and very bright sharp screen — I got a matte one — and fast. Oh, very fast. On my previous 1.5 Ghz 15″ PowerMac (a thing of beauty too), it took 28 seconds to typeset the Gödel book. Now the same LaTeX processing takes just over four seconds. And no, of course it isn’t that I really need all those saved twenty seconds in a day! But I don’t have to think any more about the business of refreshing the preview of the printed page — you just stop noticing the mechanics, so to speak, of using LaTeX.

I did think long and hard about whether to go for broke and get the big screen version. I’m glad I did. The laptop fits in the same bag I had before, and is not significantly heavier, so I don’t notice any real difference in the bother of carting it around. And after all, neither size MacBook Pro is the sort of thing you’d want to tote if you were really doing a lot of travelling (mmmm, the rumours of a really small laptop for 2008 are promising). So get the bigger one if you can: having the extra real estate again helps to make e.g. working with LaTeX (with TeXShop and BibDesk windows open, etc.) quite a lot more pleasant.

I’ve now just got to write another book to justify the expense …

Scroll to Top