Logical Labyrinths

By using some interesting and amusing logical puzzles, starting with the logic of lying and truth-telling, the author introduces the language and symbols of propositional logic, beginning with the logical connectives and their truth tables, and then using them to verify some tautologies which are immediately applied to analyze some of the puzzles previously discussed. The first 10 chapters, about 80 pages, make a delightful introduction to the analysis of reasoning, a friendly introduction to propositional logic.

The next three chapters get a little more serious, introducing the tableaux method to prove a formula by analyzing its sub-formulas, giving some rules to construct tableaux and illustrating the method with several examples. Next come the quantifiers, and in addition to the classical examples of syllogisms (“All men are mortal. Socrates is a man. Therefore Socrates is mortal.”) we get some entertaining variations of the puzzles of the previous chapters involving now the notions of all and some. Then we are ready for the universal and existential quantifiers, their interdependence, the definition of the class of first-order formulas starting with atomic formulas, and the tableaux for first-order logic, all of these illustrated revisiting, for example, the knights and knaves problems (a natural reference to Lewis Carroll, of course).

The next part of the book deals with the nature of infinity, recalling some well-known troubles with this notion in the form of problems or paradoxes, and again the chapter is filled with examples to get the reader acquainted with the various sizes of sets (finite, infinite, denumerable, uncountable). After a few more excursions to the motivating puzzles, and almost without noticing, we reach some fundamental results in first-order logic, including the Löwenheim-Skolem theorem (if a formula is satisfiable, then it is satisfiable in a denumerable domain), completeness (every valid formula is provable by the tableau method) and compactness (if all finite subsets of a denumerable set are satisfiable then the whole set is also satisfiable).

The last part of the book, starts with a general discussion of the axiomatic method to introduce axiom systems for first-order logic, and ends with a discussion of Gödel’s incompleteness theorem.

With the various bridge courses springing around campuses, this book could be used for a first glimpse into mathematical logic. The author has reached a delicate balance between simple fun with the various puzzles that fill the book and the formality of an introductory course on mathematical logic as in his more standard text First-order logic (First edition: Springer, 1968, Second Corrected Edition: Dover, 1995), a strategy already used by the same author in Forever Undecided: A Puzzle Guide to Gödel (Knopf, 1987) which can be read as an introduction to the more formal approach of his monograph: Gödel’s Incompleteness Theorems (Oxford, 1992).

Felipe Zaldivar is Professor of Mathematics at the Universidad Autonoma Metropolitana-I, in Mexico City. His e-mail address is fzc@oso.izt.uam.mx