Book note: Smullyan’s Guide

Ten years ago, when already in his ninety-fifth year, Raymond Smullyan published A Beginner’s Guide to Mathematical Logic (Dover, 2014), followed three years later by a sequel A Beginner’s Further Guide to Mathematical Logic (World Scientific, 2017).

I’m a huge admirer of Smullyan’s classic books (I mean, in particular, First-Order Logic and the trilogy starting with Gödel’s Incompleteness Theorems). His famed puzzle books are mightily ingenious too,  though to be honest are not really so much to my own taste. Sometimes, as in his Logical Labyrinths, Smullyan mixes up the genres. But these late Guides are (relatively!) conventional in style, except for the way that significant problems (e.g. challenging you to prove theorems from hints) are scattered through the chapters, with detailed solutions at the end of chapters. The two books are aimed squarely at beginners, so should be most relevant to exactly those more elementary parts of my Beginning Mathematical Logic which most need revision. I didn’t say much about the books before, so I thought I should certainly take another more careful look, reminding myself what Smullyan covers and how.

Smullyan’s Beginner’s Guide is divided into four parts. Part I (57 pp.) is ‘General Background’ — something about sets, naively, but then pointers to the paradoxes; different infinite sizes of sets; mathematical induction; König’s Lemma; a generalized idea of compactness; and more. The sort of thing we want a beginning logician to know at some early stage; but these chapters are perhaps a little too idiosyncratic and uneven in level and coverage to be the recommended source.

Part II (68 pp.) is on ‘Propositional Logic’. Ch. 5 introduces truth-tables and tautologies in a gentle and elementary way. Ch. 6 is, by contrast, a rather fast-track introduction to propositional tableaux — in just twenty pages we get signed and unsigned tableau, Smullyan’s unified notation, soundness and completeness proofs, a compactness proof, and even dual tableaux. Ch. 7 introduces a familiar sort of system of axiomatic propositional logic K (closely akin to Kleene’s, with four built-in connectives taken as primitive). The chapter then takes an unusual turn:  it is shown that K is equivalent to a very unfamiliar axiomatic system U, and then that every propositional tableau proof can be turned into a U-proof, showing that K is complete for the usual two-valued semantics.

Part III is on ‘First-Order Logic’ (36 pp).  Ch. 8 introduces the language of FOL, syntax and semantics,  and an axiomatic system in just ten pages before the solutions to examples start — which will be surely too rushed for those who have not previous encountered a treatment. The brisk Ch. 9 is on tableaux for FOL, completeness, compactness, (downward) Löwenheim-Skolem, and more — again all very speedy. 

In sum, I think Parts II and III are too uneven and in places too rushed to make for a recommendable first introduction to PL and FOL. Chapters 6 and 9 could, though, make a usable introduction to the tableaux approach to those already familiar with other versions of PL/FOL — though I do think there are rather better options at different levels.

Part IV, however, strikes me as working very well, the high point of the book. The topic is ‘The Incompleteness Phenomenon’. The five chapters proceed from quite abstract versions of Gödel and Tarski — harking right back to Smullyan’s landmark 1959 paper ‘Languages in which self reference is possible’ — through to gradually more concrete semantic and syntactic versions of the first incompleteness theorems, reaching Peano Arithmetic in the penultimate chapter, with the second theorem and some related topics in the final chapter. 

This is all done with over half a century of polish, with Smullyan setting more or less teasing problems as he goes along. These outstanding chapters will indeed make a quite excellent counterpoint to the more conventional, concrete-first, treatments of Gödel and Tarski, and will certainly deepen understanding. To be warmly recommended.

(I’ll discuss the Further Guide in a later post.)

The post Book note: Smullyan’s Guide appeared first on Logic Matters.