You are here

Introduction to Mathematical Logic

Elliott Mendelson
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2009
Number of Pages: 
469
Format: 
Hardcover
Edition: 
5
Series: 
Discrete Mathematics and Its Applications
Price: 
89.95
ISBN: 
9781584888765
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Felipe Zaldivar
, on
12/14/2009
]

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 fzc@oso.izt.uam.mx.


The Propositional Calculus

Propositional Connectives. Truth Tables

Tautologies

Adequate Sets of Connectives

An Axiom System for the Propositional Calculus

Independence. Many-Valued Logics

Other Axiomatizations

First-Order Logic and Model Theory

Quantifiers

First-Order Languages and Their Interpretations. Satisfiability and Truth. Models

First-Order Theories

Properties of First-Order Theories

Additional Metatheorems and Derived Rules

Rule C

Completeness Theorems

First-Order Theories with Equality

Definitions of New Function Letters and Individual Constants

Prenex Normal Forms

Isomorphism of Interpretations. Categoricity of Theories

Generalized First-Order Theories. Completeness and Decidability

Elementary Equivalence. Elementary Extensions

Ultrapowers: Nonstandard Analysis

Semantic Trees

Quantification Theory Allowing Empty Domains

Formal Number Theory

An Axiom System

Number-Theoretic Functions and Relations

Primitive Recursive and Recursive Functions

Arithmetization. Gödel Numbers

The Fixed-Point Theorem. Gödel’s Incompleteness Theorem

Recursive Undecidability. Church’s Theorem

Nonstandard Models

Axiomatic Set Theory

An Axiom System

Ordinal Numbers

Equinumerosity. Finite and Denumerable Sets

Hartogs’ Theorem. Initial Ordinals. Ordinal Arithmetic

The Axiom of Choice. The Axiom of Regularity

Other Axiomatizations of Set Theory

Computability

Algorithms. Turing Machines

Diagrams

Partial Recursive Functions. Unsolvable Problems

The Kleene–Mostowski Hierarchy. Recursively Enumerable Sets

Other Notions of Computability

Decision Problems

Appendix A: Second-Order Logic

Appendix B: First Steps in Modal Propositional Logic

Answers to Selected Exercises

Bibliography

Notation

Index