You are here

An Introduction to Mathematical Logic

Richard E. Hodel
Dover Publications
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Mark Hunacek
, on

Once again, Dover Publications has done the mathematical community a considerable service by rescuing from extinction, and making available at a very reasonable price, an excellent textbook that had fallen out of print. This time the book is Hodel’s text on logic, first published in 1995 by PWS Publishing Company.

That this book actually did go out of print has always surprised me, since I had occasion to read parts of the original PWS edition quite a long time ago, and thought it was first-rate. Now that I have had the opportunity to re-acquaint myself with it, I see no reason to change this opinion. This is an excellent book, which compares favorably with major competitors like van Dalen’s Logic and Structure and Enderton’s A Mathematical Introduction to Logic.

The text addresses three major themes: the propositional calculus, the predicate calculus, and the general theory of computability and decidability. The book begins with an introductory chapter 1 discussing set theory and giving a fairly informal look at logic and issues relating to it, after which the propositional calculus is discussed in chapters 2 and 3. Chapter 2 is devoted to the semantics of this language (i.e., truth tables); in the next chapter, the syntax of this language (i.e., the question of deriving one statement from others) is discussed. In order to do this, it is necessary to establish rules of inference, and, as the author point out, there are several ways to do this. Hodel relies on an approach (for which he credits Shoenfield’s text Mathematical Logic) in which the basic connectives are “not” and “or” and there are four specified rules of inference.

The two approaches, semantic and syntactic, are linked by the completeness theorem, which asserts that a statement of the propositional calculus is a tautology if and only if it is a theorem — i.e., derivable from the axioms according to the allowed rules of reasoning. The author also mentions (and spends a section each discussing) two alternative syntactic approaches to the propositional calculus, namely the “Hilbert-style” approaches using modus ponens as the sole rule of derivation, and Gentzen natural deduction (which is what van Dalen relies on heavily in his text). These two sections are entirely optional, but do provide considerable flexibility for an instructor who may wish to discuss alternative approaches.

In chapters 4–6 Hodel develops the predicate or first-order calculus (i.e., quantifiers), using the same approaches (semantic and syntactical) as was used for the propositional calculus. The completeness theorem for this language is also proved, and the author then moves into some of the standard theorems of model theory: the compactness theorem, Skolem-Löwenheim, etc.

Chapter 7 begins the third major theme of the book: computability, decidability and incompleteness. A high point of chapter 7 is a statement and proof (modulo some technical details that are omitted) of Gödel’s First and Second Incompleteness Theorems, and related results and generalizations.

Another high point of this part of the book is chapter 10, which talks about a topic not often covered in undergraduate textbook literature, the negative solution to Hilbert’s Tenth Problem. This problem, one of the 23 famous problems posed by Hilbert at the turn of the 20th century, asked for an algorithm for determining whether a given polynomial Diophantine equation with integer coefficients has an integer solution. As a result of the combined work of Julia Robinson, Martin Davis, Hilary Putnam and Yuri Matiyasevich, it was ultimately proved that no such algorithm exists. This chapter contains the proof of that fact. What is particularly attractive about this chapter is that it is largely independent of much of the rest of the book; the author describes a path to it that involves just two sections from chapter 1 and a few sections from chapter 8. As a result, this book can be used not only as a text for an introductory logic course but also as the text for a brief course or senior seminar on Hilbert’s Tenth Problem. (In fact, this book seems to have been written with flexibility in mind. By proceeding directly to chapters 8–10 after part of chapter 1, one can use this book as a text for a full semester course on recursive functions.)

Since I mentioned Julia Robinson in the previous paragraph, let me digress now to point out that she was the sister of Constance Reid, the author of a number of mathematics-themed books, including biographies of Hilbert and Courant. Reid also wrote a biography, Julia: A Life in Mathematics, of her sister, which was very favorably reviewed in this column; conversations with Reid also formed a large part of an interesting documentary on Robinson, Julia Robinson and Hilbert’s Tenth Problem, the video of which was also reviewed in this column, and which has appeared on Iowa Public Television.

Throughout the book, the author’s writing style is clear and detailed; mathematical logic is, of course, a highly technical subject, but this book makes a real effort to make it understandable. There are lots of exercises, covering a wide spectrum of difficulty; solutions are not available in the book, which should please instructors who want to assign the exercises as homework (but which may not please people reading this book for self-study).

In short, I think that Hodel’s book is an excellent introduction to this area of mathematics. I would unhesitatingly recommend it as a text for an undergraduate course in mathematical logic for math majors even if it cost what an average math book costs these days, but the fact that it is (as of this writing, anyway) available for about 16 dollars on makes it, of course, even more attractive. This is a real bargain.

Mark Hunacek ( teaches mathematics at Iowa State University.

1. Background
2. Language and Semantics of Propositional Logic
3. Propositional Logic
4. First-Order Languages
5. First-Order Logic
6. Mathematics and Logic
7. Incompleteness, Undecidability and Indefinability
8. Recursive Functions
9. Compatability Theory
10. Hilbert's Tenth Problem
Appendix: Number Theory
References and recommended readings