Since its first edition (1964, D. Van Nostrand), this fine book has been a text of choice for a beginner's course on mathematical logic. The first two chapters give a gently paced introduction to propositional calculus and first order theories, including a proof of the Gödel's completeness theorem (in any first-order predicate calculus, the theorems are the logically valid well-formed formulas) essentially following Henkin (1949) and Hasenjaeger (1953). Chapter two includes the rudiments of model theory: Elementary equivalence and extensions, ultraproducts and ultrapowers. These notions and results are then used to introduce the elements of nonstandard analysis.
The third chapter introduces a first order system S based on Peano’s axioms for the natural numbers. This formalization of the arithmetic is necessary to study recursive functions and prove that every recursive function is representable in the system, and finally to state and prove Gödel incompleteness theorem (if the system S is consistent, there is a well-formed formula not provable in it). All the details of this celebrated theorem are in the third chapter of Mendelson’s text. The proof of the incompleteness theorem is based upon a diagonalization lemma and a fixed-point theorem. These three chapters, with some choices, e.g., omitting the last few sections of chapter two, can be covered in a one semester introductory course on mathematical logic with plenty of exercises for the students (there is even a final section with answers and hints for selected exercises).
The second half of the book has two chapters. Chapter four is devoted to axiomatic set theory. The author starts by recalling that one of the main reasons for the rebirth of logic at the end of the 19th century and the beginning of the 20th was the discovery of the paradoxes of set theory as initially developed by Cantor. Russell’s paradox (1902) is an example: If we define A to be the set of all sets M such that M is not a member of M, then A is a member of itself if and only if A is not a member of itself. Mendelson formulates and studies a first-order theory, essentially due to von Neumann, Robinson, Bernays and Gödel, that axiomatizes set theory. This approach allows the author to introduce the notions of ordinal numbers, transfinite induction, equinumerosity, finite and denumerable sets and prove, for example, Hartog’s theorem (for any set A, there is an ordinal that is not equinumerous with any subset of A). In addition, there is a discussion of the Axiom of Choice, one of the most controversial axioms of set theory, but essential in many branches of mathematics, from algebra (to prove, for example, that every proper ideal of a ring is contained in a maximal ideal, or that every field has an algebraic closure) to topology (to prove Tychonoff’s theorem, for example) usually in the equivalent formulation by Zorn (any nonempty partially ordered set in which every chain has an upper bound, has a maximal element). The equivalence of the axiom of choice with Zorn’s lemma and various other formulations is proved in this chapter, which ends with a discussion of other axiomatizations of set theory, in particular the Zermelo-Fraenkel axiom system.
The fifth and last chapter of the book is devoted to effective computability. This chapter formalizes the notion of algorithm following Turing’s ideas. We find here the notions of Turing machines, partial recursive functions, Markov algorithms and decision problems. This chapter should appeal to the computer-science oriented reader since the standard computer model in computability theory is a Turing machine. I only wish it had been expanded to include, for example, an introduction to the P versus NP problem, but the interested reader will be well prepared to study this and other computer-science related problems after reading this chapter.
There are two appendices in the book, the first one on second-order logic showing, for example, the limitations of the first-order languages: First-order theories allow quantifiers to apply to individuals, but not to properties of individuals, i.e., first-order logic allows expressions of the form “f(x) for all x ”, but “f(x) for all f ” is not allowed. New to the fifth edition is the second appendix on modal propositional logic, especially interesting for its applications to provability logic.
There are many fine books on mathematical logic, but Mendelson's textbook remains a sure choice for a first course for its clear explanations and organization: definitions, examples and results fit together in a harmonic way, making the book a pleasure to read. The book is especially suitable for self-study, with a wealth of exercises to test the reader's understanding.
Felipe Zaldivar is Professor of Mathematics at the Universidad Autonoma Metropolitana-I, in Mexico City. His e-mail address is firstname.lastname@example.org.