Book note: Westerståhl, Foundations of Logic, I & II

Dag Westerståhl’s Foundations of Logic: Completeness, Incompleteness, Computability is, by some margin, the most attractively written book at its level that I have newly encountered for some years.

The book is based on lecture courses give at Stockholm University and latterly at Tsinghua University, Beijing, and evidently reflects long teaching experience. Especially in the first two Parts of the book, the expositional choices are very well-judged, and the balance between motivational chat and worked-through formal details seems just right to me. Many student readers should find this book quite excellent for self-study. (Long-time readers of this blog will know that I’m not exactly over-quick to heap praise like this!)

The book was published by CSLI (distributed by the University of Chicago Press) in January 2024, ISBN 978-1684000005. You should certainly warmly recommend it to your local university or college library. For some reason, Amazon and others quite mis-report the page length as 80pp.: in fact it is xiv + 451 pages, so the printed paperback price (§45, £36 from Waterstones) is by current standards pretty reasonable. Though, as we will see, it is a great pity that the author seems not to have come to an arrangement which makes the PDF freely downloadable.

In just a little more detail, Part I (‘Background’, 78 pp.), introduces propositional and FOL languages, and the idea of interpretations and semantic consequences, and then gives both a natural deduction proof system (Gentzen-style) and a Hilbert proof system. Part II (‘Completeness’, 80 pp.) gives soundness and completeness theorems for propositional logic and FOL, and then there is a chapter on the L-S theorems, compactness, and a smidgin of model theory. Part III (‘Incompleteness’, 134 pp.) discusses primitive recursive functions and their representability, Peano arithmetic, arithmetization, and Gödel’s Theorems. Part IV (‘Computability’, 114 pp.) adds chapters on decidability, undecidability and a modest amount more computability theory. There is an Appendix (34 pp.) on sets and functions, etc., for those that need it.

So this is a very substantial book. But Parts I and II in particular strike me as admirably well-paced, to my mind neither over-packed with detail, nor tediously slow-moving.

In the rest of this post, I’ll say just a little more about Parts I and II. Then I’ll follow up with a later post on Parts III and IV.

After an inviting, reader-friendly, Introduction (Ch. 1), Part I has two substantial chapters, the first one (Ch. 2) introducing the syntax and semantics of propositional logic and then of FOL. This is done conventionally, in that we get the usual Tarski-style story, with the semantics done via assignments of objects to all variables at once in the usual way, interpreting wffs with free variables. So, in the usual way, we need slightly messy stories about allowable substitutions avoiding variable-capture, slightly messy notation for handling assignments to variables, etc. However, this is all expounded particularly clearly, with motivations at various points very well explained. (There’s perhaps just a hint in §3.2 that we could do things differently, in the way I myself would prefer, using a supply of constants-as-parameters, rather than making variables do double duty — and then we can assign parameters temporary interpretations one at a time, just on an as-needed basis. But I can of course see the virtues of sticking to the conventional Tarskian line.)

Then Ch. 3 introduces two proof systems, Gentzen-style natural deduction and a minimalist, two-connective, Hilbert-style system. I think I would probably have spent just two or three more pages giving more examples of Gentzen-style proofs, showing tactics for building up proof-trees in natural ways (to re-inforce the advertised claim that this really is a natural deduction system). But still, this is again all very well done, with possible stumbling blocks — e.g. the use of vacuous discharge — nicely elucidated. The chapter finishes particularly helpfully with an outline proof that the two proof systems march in step, warranting the same deductions.

Part II begins with a short chapter (Ch. 4) proving the completeness of the Hilbert proof system for propositional logic, using maximal consistent sets and Lindenbaum’s Lemma. As in previous (and future!) chapters, there are excellent exercises, including in this case ones exploring another completeness proof and presenting the interpolation lemma for PL. Then, closely following that chapter’s overall structure, we get a short chapter (Ch.5) proving the completeness theorem for FOL using Henkin’s method — very sensibly doing the proof for FOL without identity first, before in the final section of chapter complicating the story to handle identity. I wonder if that last section is just a bit denser than it needs to be — but overall, again, this seems quite excellently well done.

The rest of Part II concludes with a significantly longer chapter (Ch. 6) titled, simply, ‘Model theory’. The first eight sections introduce a handful of predictable entry-level topics: more ideas about structures, about isomorphisms between structures, notions of definability, the compactness theorem (as a corollary of completeness) and some of its applications, and the Löwenheim-Skolem theorems. The remaining sections are more challenging, and could well be skipped on a first reading. §6.9 reflects Westerstähl’s interest in generalized quantifiers and quantifiers in natural language. §6.10 is on Ehrenfeucht–Fraïssé games. §6.11, ambitiously, is on Lindström’s Theorem.

Suppose we stop before those last three sections (though take in the still-relevant end-of chapter exercises). Then what we have before us is a book-within-a-book, Westerståhl’s 150 page introduction to FOL that is, I think, particularly attractively written and accessible. It takes its place among the best options for self-study.

The post Book note: Westerståhl, Foundations of Logic, I & II appeared first on Logic Matters.