A Friendly Introduction to Mathematical Logic

This book started out as an undergraduate-level text in mathematical logic written by the first author and published by Prentice-Hall in 2000. It died an untimely death some years later when the publisher allowed it to go out of print, but has now been resurrected as a second (paperback) edition by a different publisher, gaining in the process some 175 pages of text and a co-author.

The first edition was noteworthy in several respects. First of all, the title was not a lie: this book really was (and still is) quite reader-friendly, written in a conversational and inviting tone that students will enjoy reading. In addition, the choice of topics was a bit unusual for a first undergraduate introduction to logic: most books on the subject begin with the propositional calculus (the simplest language of logic, but one that is not sufficient to do mathematics with) and then proceed from there to discuss the first order predicate calculus, where quantifiers make an appearance. By contrast, the first edition of this text simply omitted the propositional calculus and proceeded directly to first-order languages. The idea was to get, in one semester, to a proof of Gödel’s First and Second Incompleteness Theorems, and the result was a short, concise (barely over 200 pages of text) book narrowly focused on that objective.

The original text started with a chapter on structures and languages, and then (chapter 2) introduced logical axioms and a system of deduction. Important theorems about the resulting system, including the Deduction theorem and soundness theorem, were proved. The next chapter addressed completeness and compactness and then detoured a bit to prove the Löwenheim-Skolem theorems, stating Skolem’s paradox but leaving its resolution as an exercise for the reader. The two final chapters, both of them fairly technical, proved Gödel’s theorems — chapter 4 setting the stage and discussing some preliminary ideas (e.g., Gödel numbers) and chapter 5 going through the details of the proof.

The new second edition differs from the first (apart from the usual local changes in exposition) in two primary respects. First, there is a lot of new content, primarily in regard to the subject of computability and its relationship to Gödel’s theorems. So, for example, chapter 4 is now entitled “Incompleteness, from Two Points of View” and acts as an introduction to the two different approaches that will be taken in the rest of the book. Chapter 5 (the most difficult chapter of the book, which the authors themselves describe as being “full of dense, technical arguments with imposing definition piled on imposing definition” then begins to lay the groundwork for a proof of Gödel’s theorems by introducing a suitably chosen axiom system and Gödel numbering. Chapter 6 proves Gödel’s theorems, using all the machinery that has been developed to date. (Again, I quote the book: “if 90% of the iceberg is under water, we’ve covered that. Now it is time to examine the glorious 10% that is left.”)

Then there is an entirely new chapter 7 on computability theory. It starts with a succinct but informative historical discussion, and then proceeds to some of the technical details of the subject. Gödel’s theorems are given a second proof, and other results are discussed, including (though without complete details of the proof) the negative solution to Hilbert’s Tenth Problem, which asked for an algorithm for determining whether a Diophantine equation with integer coefficients has a solution in nonnegative integers.

Finally, a new chapter 8, consisting almost entirely of exercises, serves as a review of what has come before, but in a new context, the language of bit strings.

Second, the new edition contains about 75 pages of solutions to (some, but not all of) the exercises, a feature that was missing in the first edition. I approach the inclusion of exercise solutions with mixed feelings. Having them available does make the book more useful for self-study, but on the other hand I think there is something pedagogically ill-advised about enabling the students to just flip to the back of the book rather than work on the problems themselves. And of course it goes without saying that the availability of solutions complicates life for instructors who utilize graded homework assignments.

Several things about the first edition have not changed. The authors’ writing style remains, in the language of the title, friendly. It emphasizes motivation, is chatty and conversational, and uses humor throughout. (In a nod to the fact that the new co-author teaches at the University of Oslo, one exercise in the text asks the student to prove a certain result and to “Translate this result into everyday English. Or Norwegian, if you prefer.” For some reason unknown to me, the first edition had offered students the option of translating into Swedish.) Another pedagogically valuable feature of the book that has been retained from the first edition is the inclusion of comments denoted “Chaff”, set off from the main body of the text by extra indentation. “They are designed to restate difficult points or emphasize certain things that may get lost along the way. Sometimes they are there just to break up the exposition. But these asides really are chaff, in the sense that if they were blown away in the wind, the mathematics that is left would be correct and secure.”

Another thing about the first edition that has not changed is the omission of a chapter on the propositional calculus. Depending on your viewpoint, this may or may not be a good thing. Although Leary’s desire to blaze a quick trail to Gödel was entirely reasonable, the omission of the propositional calculus was a substantial departure from the norm, and the book did not offer much in the way of flexibility for an instructor. It contained enough material for a one-semester course, but not enough material for an instructor to pick and choose. Thus, an instructor who was in agreement with Leary’s vision of what an introductory mathematical logic course should look like would certainly enjoy the clear and conversational writing of the author, but one who had other ideas about course content would likely look elsewhere, perhaps to more standard fare such as Enderton’s A Mathematical Introduction to Logic.

Now, however, it seems clear that there is more material in the text than can be covered in one semester. However, the current arrangement allows an instructor, in one semester, to choose one of two paths to Gödel’s theorem: from chapter 4, an instructor who wants to emphasize computability can go directly to chapter 7; one who wants a more “proof oriented” approach can do chapters 5 and 6. So, Leary’s original rationale for omitting a first chapter on the propositional calculus still exists — if, that is, you are determined to see the details of a proof of Gödel’s theorems. Nevertheless, I think the inclusion of a chapter on the propositional calculus would enhance the value of the book, in that it offers yet a third option, this one allowing instructors to start from scratch with the propositional calculus, discuss the basics of first order logic (including some fairly sophisticated results), and then to at least discuss the meaning and significance of Gödel’s theorem, without going through the details of a proof. Instructors choosing this option might also find time to give at least an overview of computability as well. Of course, this would result in the course ending with a certain amount of handwaving, but that is, of course, a time-honored tradition in the teaching of upper-level mathematics courses.

The inclusion of solutions to the exercises, and the omission of any discussion of the propositional calculus, are basically my only two cautionary notes about the suitability of this book as a text for an introductory course. In all other respects (except for one quibble discussed in the next paragraph), I think it would be a superb candidate. It is, as noted earlier, written in a very engaging and clear way. There are a lot of exercises covering a wide range of difficulty, and even to my non-expert eyes they seem to be quite useful in helping the student assimilate the material. The book is also, thanks to the fact that it is now published by what appears to be a university-related publishing company, very affordably priced: less than 34 dollars on amazon, as I write this. (Contrast with Enderton, which is selling now for more than a hundred dollars.)

The quibble I referred to above concerns the bibliography, which, in this second edition, is virtually unchanged from that of the first. The only difference I could see was the inclusion of Turing’s 1937 paper. In particular, the most recent entry in the bibliography is dated 1998, despite the fact that several useful textbooks (including Weber’s Computability Theory) have been published recently, and Enderton’s textbook has a more recent edition than the one cited here.

But this is, as I say, a quibble. To summarize and conclude: mathematical logic is a difficult, technical subject, and doing it right entails a certain amount of technical fussing. There’s no point pretending that the authors have written a book that reads like a novel. However, they have done about as good a job as I can imagine motivating these ideas and making them comprehensible to an undergraduate. If you are planning to teach a course in logic, and the concerns that I expressed above about the propositional calculus and exercise solutions don’t bother you greatly, you should certainly give this book a serious look.

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.