Revisiting Bell & Machover
I had on my desk — or rather, standing in a row under my desk so as not to topple over — a stack of books that I wanted to read/revisit before the end of September, as preparation for revising the Study Guide (particularly the chapter on FOL). There are two books from that stack which I haven’t mentioned yet. I really want to move on, so I’ll be brief and briefer than the books really deserve. But I don’t feel too bad about this because — in at least enough parts! — I can be quite positive.
So first, in this post, let me wind the clock right back and quickly revisit a classic book from another era, which oddly doesn’t feature either in the current version of the Study Guide or in its Appendix of book notes on major wide-ranging texts on mathematical logic.
Once upon a long time ago, John Bell and Moshé Machover ran a notable one-year masters-level programme on mathematical logic and the foundations of mathematics at London University. They then developed their lecture notes into A Course in Mathematical Logic published by North-Holland in 1977. This is a very substantial book of 599 pages, and a major achievement in its time, rightly well-regarded back in the day.
But, almost fifty years on, the question inevitably arises: what does it have to offer the reader today compared with more recent texts (in particular, how well is it likely to work for a student launching into a course of self-study?).
As the authors note, various parts of the Course had their origins in different lecture courses, and they can often be tackled independently of each other. For example, you don’t need to know the particular details of Bell and Machover’s account of FOL in order to cope with their later discussion of formal arithmetics. It is therefore quite reasonable to chunk up the book into discrete parts, and to assess these separately. So that’s what I’ll do.
Chs 1–3, Propositional and first-order logic (pp. 124). There is a lot to like about the first chapter here — in particular the way that both tableaux and axiomatic systems are introduced and interrelated. (Unsigned) tableaux are nicely motivated immediately after the truth-functional semantics for the basic connectives is defined (and we get a proof too that a version of excluded middle could be conservatively added as a tableaux rule). Soundness and a (weak) completeness theorem for tableaux are snappily proved. Then we meet a Hilbert-style proof system, and it is shown directly (i.e. by syntactic proof-manipulations) that this warrants the same deductions as the tableaux system, establishing that the new proof system is complete too. Then we get a direct proof of weak completeness for our Hilbert system by Kalmar’s method, and a direct proof of strong completeness by Zorn’s Lemma and the construction of maximal consistent sets. This could be very useful reading for many, drawing various ideas together and showing how they interrelate.
But I can’t in the same way recommend the similarly structured chapters on FOL. Although they start well enough, the semantic story about FOL — in particular when it comes to a laboured discussion of substitution — soon becomes rather too heavy-handed, and the version of a tableau system for FOL is far from the nicest.
Ch. 4, Boolean algebras (pp. 36) This is a nice stand-alone chapter, and it still makes a recommendable introductory account — especially §§1–5.
Ch. 5, Model theory (pp. 65) Somewhat action-packed, and lacking some of the helpful classroom asides we find in earlier chapters. There are now more accessible treatments of elementary model theory.
Chs 6–8, Recursion theory and arithmetic (pp. 174) Once upon a time, this group of chapters would have been particularly interesting in virtue of its early account of the then relatively-recent MRDP theorem and the use of that theorem in proving further key results. Still pretty readable, but this is a topic area with some wonderful alternative texts. Though for one alternative option on recursion theory and arithmetic, we should certainly note Machover’s more approachable reworking of some of the same material in his own later, shorter, book (though he doesn’t actually prove the MRDP theorem there, referring back to the details here).
Ch 9, Intuitionistic first-order logic (pp. 59). There is a useful initial motivating discussion in §§1-4. But we don’t get the clearest of accounts of how the Beth/Fitting tableaux system which is introduced next is supposed to work: de Swart in his chapter on intuitionism, for example, does better. And the rest of the chapter doesn’t give e.g. the nicest introduction to Kripke semantics either. So not the place to start.
Ch. 10, Set theory (pp. 72). After more routine introductory sections, the remaining sections — including §5 on reflection principles, §7 on absoluteness, §8 on constructible sets, §9 on the consistency of AC and GCH — could well still be useful supplementary reading for those who already know some elementary set theory. But of course there are many alternatives!
Ch. 11, Non-standard analysis (pp. 45). This chapter is a sophisticated but somewhat opaque treatment, a level or two up from most of what has gone before, and rather too remote from the accessible but intriguing entry-level considerations we usually meet in introductory accounts of Robinson-style constructions. Certainly not for the faint-hearted.
Summary verdict An exceptional book in its day, still worth revisiting in part.
The post Revisiting Bell & Machover appeared first on Logic Matters.
