Book note: Westerståhl, Foundations of Logic, III & IV

There are, of course, oodles of books introducing FOL (and maybe covering a lot more). However, for one reason or another, many respectable texts on FOL can be difficult to recommend very warmly for self-study (over-doing the “rigour”, under-doing the motivational chat, choosing a horrible deductive proof system, etc., etc.). Against this background, the first two parts of Foundations of Logic do seem to me to stand out as providing a particularly attractive option.

Again, there are many more books which introduce formal arithmetic, incompleteness, and some entry-level computability theory. But this time, we are already rather generously supplied with a number of particularly accessible and enjoyable options taking varying paths through the material; and I’m not sure that Parts III and IV of Westerstähl’s book trump the alternatives. Which is not to deny that the book continues to be very attractively written, well-organized with a lot of signposting. In particular, Westerståhl does a very good job in signalling what are the Big Ideas, and what is the hack work required to confirm that e.g. primitive recursive functions are representable in PA, or that syntax is sufficiently arithmetizable, etc. It then becomes a judgment call just how many of the tedious under-the-bonnet details you really need to go into.

In fact, the particular path to the incompleteness results that Westerståhl takes closely resembles the one in my own IGT  (which gets a friendly mention in his preface). But at various points he goes into more of the nitty-gritty detail than I do — more, obviously enough, than I judged was necessary. And, despite the signposting, I can well imagine some student readers losing orientation. So (what a surprise!) if you want to follow this path to Gödel’s Theorems — and there are alternatives — I’d still recommend starting with IGT  for self-study. Westerståhl’s Parts III and IV would then make for quite excellent follow-up reading to consolidate understanding.

In just a little more detail, Part III (‘Incompleteness’) comprises six chapters. Ch. 7 is a very nice chapter, outlining what is to come — and indeed could be read stand-alone for preliminary orientation on incompleteness and computability, whatever you go on to read as your main text(s). Ch. 8 is about primitive recursive functions. Ch. 9 introduces first-order Peano Arithmetic.  Ch. 10 establishes the representability of p.r. functions. Ch. 11 is on the arithmetization of syntax. So far so good, if sometimes unnecessarily detailed? Then, the target of this Part, Ch. 12 is a distinctly action-packed, indeed over-busy,  forty-page chapter on incompleteness (IGT takes over twice as many pages covering much of the same material as in this chapter, and I really think is all the better for it).

Part IV (‘Computability’) has three chapters. Ch. 13 is on Turing machines, recursive functions and decidability. Ch. 14 is on undecidability of extensions of PA, of FOL, of the halting problem (so these two chapters correspond to the much of final half-dozen chapters of IGT). And then Ch. 15 dips its toes into computability theory (occasionally going rather beyond anything in IGT, e.g. in introducing the s-m-n theorem, creative sets, etc.). All good stuff, and I should certainly note that the end-of-chapter Exercises — as earlier in the book — continue to be really excellent.

But, as I say, these Parts wouldn’t be my recommended first entry-point for self-study of this material. However, those who would prefer a somewhat faster trek along much the same path as IGT with a few extra sights along the way will find Westerståhl’s book a very admirable guide.

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