Book note: Machover, Set theory, logic and their limitations
As I said, I’d like to put together a second edition of Beginning Mathematical Logic: A Study Guide. So to that end I’m planning to revisit some of the more introductory books that should (or maybe should not) get more attention in the Guide. I’ve stacked a pile of a dozen texts on my desk to browse through, which will keep me busy enough when in the mood over the next couple of months or more. I’ll occasionally add some more book notes here as I go along, mostly as aides memoires for myself, but some might find them of interest.
There are some dauntingly large (though potentially inviting) books in the pile. But after tackling Marker’s new heavy-duty text, I’m giving myself a much easier ride next, revisiting a relatively short and well-regarded introductory text from almost thirty years ago, which rather oddly isn’t even fleetingly mentioned in the current Guide …
Back in the day, Moshé Machover together with his colleague John Bell wrote a very substantial graduate-level text A Course in Mathematical Logic (North-Holland 1977). I’ll say something more about this in another post, though — spoiler alert! — I’m not sure there are now too many reasons to revisit this book almost fifty years on.
Machover’s later, and much shorter, Set Theory, Logic and their Limitations (CUP , 1996) gives us a significantly more reader-friendly introduction to some of the topics of the big book. It is based on his notes for courses given to undergraduate philosophers and mathematicians in the University of London. The style of presentation of the technical material is mathematical: but, as Machover says, “philosophical and methodological issues are often highlighted instead of being glossed over, as is quite common in texts addressed primarily to students of mathematics.” So this promises to offer an introductory text very much in the style that the Guide favours.
How does the story in the book unfold? Ch. 1 is a quick introduction (for those that need one) to arguments by mathematical induction. And yes, in the next edition of the Guide, I should probably better highlight the need for the less mathematical beginner to get familiar with such arguments — e.g. from Velleman’s How to Prove It, or indeed from Machover’s accessible short chapter here.
Chs 2 to 6 (92 pp.) then provide an introduction to semi-formal set theory, getting as far as equivalents of the Axiom of Choice and the arithmetic of the Alephs (it’s semi-formal in that we go beyond informal naive set theory, and are introduced to the ZFC axioms, but on the other hand we don’t yet have an official formal deductive system). This is all very clearly done, I think. But arguably, for many readers Machover’s treatment will fall between two stools. On the one hand, it goes further than explaining the basics of naive informal set theory taken for granted in many logic texts; on the other hand, if you are going to tackle as much material, the somewhat more expansive coverage in e.g. Enderton’s introductory book will probably engender more understanding.
Next, Chs 7 and 8 (93 pp.) are on propositional and first-order logic. Now, the proof systems here for PL and FOL are pretty conventional Hilbert-style. And the syntax and semantics for FOL is also conventional, so the same letters can occur as parameters and as parts of a quantifying operator, with the consequent need to fuss about free vs bound occurrences of variables, and fuss too about substitution, variable capture etc. (Interestingly, in the Introduction to their big book, Bell and Machover do note that these rebarbative complexities — their phrase! — could have been avoided by using different symbols for free and bound variables, and they offer what strike me as somewhat feeble reasons for sticking to the Tarskian line.)
There is quite a bit of careful commentary and explanation as we go through these chapters. But my sense is that as get on to the proof of completeness for FOL, for example, the presentation becomes a notch or two less beginner-friendly than some of the alternatives. But that‘s quite a close call: these chapters should probably get a friendly mention in the Guide when I return to compare them directly to the current recommendations.
Finally, Chs 9 and 10 (81 pp.) first give a quite informal introduction to the ideas of computable functions and computable enumerability (informal in the sense that we don’t get official accounts of Turing machines, register machines, partial recursive functions and the like). But it is shown — indeed as in the opening chapters of my IGT — that you can already establish a range of significant results. Then we meet the MRDP theorem, which isn’t proved though its content is clearly explained.
The final chapter then turns to formal theories of arithmetic (both a series of computably axiomatised theories and True Arithmetic). With the MRDP theorem taken for granted, it is shown e.g. that True Arithmetic is not computably axiomatizable, and ultimately we reach rather strong semantic and syntactic versions of the first incompleteness theorem. So Machover’s path through this material is not a usual one, and his discussion in the last two chapters is all the more illuminating for that. Definitely to be recommended, then, as supplementary reading on these topics.
I can’t explain why Set Theory, Logic and their Limitations, though sitting on my bookshelves, dropped below my radar when writing versions of what became the Guide. A strange omission, it now strikes me.
The post Book note: Machover, Set theory, logic and their limitations appeared first on Logic Matters.
