Logic Matters

My colleague Michael Potter organized a one-day workshop today focusing on issues arising out of Dan Isaacson’s paper, “Arithmetical truth and hidden higher-order concepts”, which appeared 20 years ago.

It’s quite difficult to tease out the full content of Dan’s claims about the status of first-order PA in his paper, but a core claim — I call it Isaacson’s Thesis — is surely this:

If we are to give a proof for any true sentence of the language of first-order PA which is independent of PA, then we will need to appeal to ideas that go beyond those that are required in understanding PA (and more generally, but more vaguely, beyond those that are required to understand the structure of the natural numbers and thus elementary pure arithmetic).

Dan wants to say more (though that’s where things get a bit murkier), but the core Thesis is reasonably clear and interesting in itself — and if not even that is true, then Dan’s stronger claims won’t be true. In my talk “Ancestral Arithmetic and Isaacson’s Thesis” (NB the link is to an unrevised version!), I suggested that we can construct a formalized arithmetic PA* with a primitive ancestral operator which in fact is within the conceptual grasp of someone who understands PA. If PA* enabled us to prove new theorems in the language of PA that would be a strike against the Thesis. But I outlined a proof that PA* is in fact conservative over PA, a result not just in harmony with the Thesis but giving it positive support. (The talk went pretty well, but I made a bit of a hash of the questions, but what’s new?)

The other talks were by Ben Colburn (on of our PhD students) and Hannes Leitgeb, who talked more about what we might reasonably mean by saying with Dan that PA is sound and complete for “arithmetical truth”. And Luca Incurvati (another of our students) and Dan Isaacson himself talked about analogues for set theory of Dan’s thesis for arithmetic. In a way, the day ended too soon, as the discussions after the final paper by Hannes were just seeming to get to the heart of issues about arithmetic when we broke up. But a very productive and enjoyable day all the same.

abebooks.com is a wonderful thing — you can so often find cheap copies of in-print books that you want, and (often not-so-cheap) copies of out-of-print books as well. The trouble is that booksellers can of course use the site too to find out what particular books in their stock are worth, and these days you rarely pick up real philosophical or logical bargains sold at silly prices because the seller has little clue of their value (I not so very long ago picked up a complete Principia in excellent condition for £30 — that sort of thing wouldn’t happen now).

But you still make serendipitous little finds. In the “all hardbacks 50p” bargain tray outside a little bookshop at a National Trust house, a copy of Bertrand Russell: Philosopher of the Century. Which is very much a period piece, reminding us how the reputations of philosophers can change so markedly. But there is an intriguing 72 page essay by Kreisel, ‘Mathematical logic: what has it done for the philosophy of mathematics’, which I confess I can’t recall reading more than a few pages of before. Like other Kreisel papers, you just wish it were written in a more conventional, less allusive (ok, more flat-footed) style. Just imagine what Kreisel’s reputation would be if he had been able to write with e.g. Putnam’s directness and lucidity (Putnam has a piece in the collection too). So often, he seems to have got there first, but we — well, most of us — can only really see it with hindsight.

There’s an afternoon planned soon to review the Faculty’s teaching, so it will be a good occasion to rethink some of our current arrangements for logic teaching. At the moment this looks to me to be about the right pattern, given the calibre of our students (good) and our resources (limited).

• First year, propositional and predicate logic by trees (up to and including completeness for propositional trees: this is in fact what we do at the moment, using my Introduction to Formal Logic). We should also perhaps have a few lectures on set notation etc. (again, something we do at the moment). That’s compulsory for all students.
• Second year, we could have five units corresponding roughly to the five main chapters of Logical Options by Bell, DeVidi and Solomon. So that’s a unit on other ways of doing logic, using propositional logic as the illustration — in particular, natural deduction. A unit treating the semantics for predicate logic more carefully, and an explanation of the completeness proof. Something on axiomatic systems built using a first-order logic. A unit introducing modal logic. And a unit on non-classical logics, in particular intuitionistic logic. (Again nearly all those are already on the syllabus, but we don’t teach them in a methodogical and integrated way. Using Logical Options as a course text could be a way of imposing order on the current slight mess. The book strikes me, having just got a copy for the first time, to be very good: it goes quite snappily and needs support from lectures, but it is the right kind of coverage and the right kind of level. This too is for a compulsory paper, though students can avoid answering too-technical questions by concentrating on some associated philosophical logic.)
• Third year, mathematical logic. This could remain pretty much as we do it at the moment. Some basic model theory, comparisons of first and second order logic, etc. Then Michael Potter’s course using his Set Theory and its Philosophy, and my course using An Introduction to Gödel’s Theorems. We could also make the technical parts of the current paper available as a graduate course for those who haven’t done enough logic when they come to us from elsewhere.

It is my impression is that even good and large departments elsewhere in the UK are dropping serious logic teaching (so that e.g. a Single Honours student may have access only to one optional honours module using Tomassi’s very, very elementary book). But before getting too upset about this and bemoaning the Dumbing Down of Courses and the general Decline of the West, I am minded to try to organize some kind of survey to find out the state of logic teaching in UK philosophy departments. I’ve put a message out on Philos-L to check that no-one else is in the middle of doing this (and check too that a survey hasn’t been done recently and I’ve just failed to notice!). Watch this space.

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.