You are here

A First Journey Through Logic

Martin Hils and Francois Loeser
Publication Date: 
Number of Pages: 
Student Mathematical Library
[Reviewed by
Mark Hunacek
, on
There are some areas of mathematics, like abstract algebra, real and complex analysis, and point-set topology, that most mathematicians, regardless of their particular areas of expertise, have a basic knowledge of. These are subjects whose study is often required in college or graduate school, and for that reason alone most of us have at least some familiarity with them. Mathematical logic, however, is somewhat different. It is entirely possible to go all the way to a Ph.D. without ever taking a course in this subject, either at the undergraduate or graduate level. I know this for a fact, because I did it.
As a result, I would not be surprised at all if quite a few faculty members have little or no familiarity with the rudiments of this subject, beyond such trivialities as, say, truth tables. Somebody who really wants to learn about mathematical logic has, of course, any number of textbooks from which to choose (including, for example, Hodel’s An Introduction to Mathematical Logic  or Enderton’s A Mathematical Introduction to Logic, but getting through either of these books is a time-consuming enterprise. It is here that books like the one under review prove valuable.
This little book discusses, in six chapters totaling only about 170 pages of text, a number of facets of mathematical logic: set theory, the predicate calculus, model theory, recursive functions, Godel’s Incompleteness Theorems, etc. The text will not make anybody an expert in these issues, but will at least provide a decent acquaintance with the basics at a mathematically correct level. 
The book begins and ends with set theory: the first chapter is “naïve” and is basically devoted to a discussion of the main ideas behind cardinal and ordinal numbers. While most mathematicians are probably already reasonably familiar with this material, there are some interesting things here that may be new to some people, such as Hindman’s theorem. (One can think of this result as a statement about colorings of the nonnegative integers: if every such integer is assigned one of a finite number of colors, there is an infinite set of nonnegative integers all of whose finite sums have the same color.) The last chapter (chapter 6) addresses axiomatic set theory, formulated within the framework of first-order logic. The Zermelo-Frankel axioms are discussed in some length, as is the Axiom of Choice and some of its equivalents. The chapter also discusses set-theoretic analogs of Godel’s incompleteness theorems and relative consistency. The independence of the continuum hypothesis is discussed, but of course not proved. 
Chapter 2 is on first-order logic, up to and including Godel’s Completeness Theorem. The propositional calculus, which is usually the first topic covered in undergraduate mathematical logic textbooks (such as the two mentioned previously) is mentioned rapidly but is not the subject of a full-scale discussion. The next chapter introduces the reader to model theory; in addition to discussions of the basic theorems in the subject such as the compactness theorem and the Lowenheim-Skolem theorems (both the “downwards” and “upwards” versions), the chapter also includes serious applications to abstract algebra, including the Nullstellensatz and Ax’s theorem on polynomial mappings. 
Chapter 4 is a thirty-page introduction to recursive function theory, discussing such topics as Turing machines, recursively enumerable sets, and the Ackermann function. Then, in keeping with the theme of “what is provable?”, chapter 5 addresses “limitation theorems”, including statements -- and proofs-- of both the first and second Godel incompleteness theorems.
Its title notwithstanding, this is not a particularly simple introduction to the subject. As is often the case in books on mathematical logic, the notation can occasionally get rather dense. In addition, the exposition here is succinct, brisk and efficient; it covers a lot of ground in not very many pages. For example, Cantor’s theorem that a set has strictly smaller cardinality than its power set is proved in four lines; the proof of the Schroeder-Bernstein theorem takes only six.  Unfortunately, because the exposition is succinct, it may lack the kind of motivation that many undergraduates often need: the need for an axiomatic development of set theory is often motivated for undergraduates, for example, by discussing some of the paradoxes of naïve set theory, but no such introductory discussion appears here.  
Finally, many of the exercises are quite substantial; one, for example, asks the reader to prove the compactness theorem for the propositional calculus and some applications, including colorings of infinite graphs and Ramsey’s theorem. Sometimes material that is discussed in an exercise is then used later in the text; exercise 8 in chapter 1, for example, develops the theory of filters and ultrafilters, and is used a few pages later to prove, in an Appendix to that chapter, Hindman’s theorem.)
For these reasons, to really get maximum benefit from this book, one should come to it armed with substantial mathematical maturity as well as background in a number of areas: the authors state in the Introduction that in addition to a general background in mathematics and abstract reasoning, topology and abstract algebra, especially field theory, are occasionally used. Witness, for example, the algebraic applications of model theory that are discussed. Moreover, in addition to topology and algebra, some prior exposure to combinatorics would be helpful; the word “graph”, for example, is used in the book without prior definition.
Although the authors also say in the introduction that the book is intended for “advanced undergraduate students, graduate students at any stage, or working mathematicians”, I think a more realistic assessment is that the optimal audience consists mostly of people in the latter two groups. Most undergraduate students of my acquaintance will, I think, find this book too terse for easy understanding.  For a more advanced audience of graduate students and non-specialist faculty, however, the book has much to recommend it. It gives the reader an opportunity to, in a reasonable amount of time, become conversant with the main ideas of the subject, and also frequently goes beyond the basics to discuss interesting applications and side-issues. 


Mark Hunacek ([email protected]) teaches mathematics at Iowa State University.