You are here

What is Mathematical Logic?

J. N. Crossley, C. J. Ash, C. J. Brickhill, J. C. Stillwell, and N. H. Williams
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

The title of this book (a Dover reprint of a book first published in 1972) is somewhat misleading. The titular question “What is Mathematical Logic?” makes this sound like a “logic for poets” book, an attempt to make logic understandable to laymen — on the order, say, of Nagel and Newman’s Gödel’s Proof. That is, at least, what I was expecting when I started the book, and it is also the way the book is advertised: a statement on the back cover says that “[n]on-mathematicians can read the book as a general survey”. Likewise, the preface states that the intended readership consists of “those with no mathematical training.”

If this actually was the intent of the authors, then they have not succeeded. For one thing, I doubt that very many lay readers would really be interested in the subjects discussed in this book — after all, how many non-mathematicians know, or want to know, anything about forcing in set theory? Moreover, the level of exposition here is quite sophisticated; so sophisticated, in fact, that I am convinced that few (if any) people with no mathematical training could understand this book.

Already on page 3, for example, the authors give a definition of “rational number” and then immediately write “as you know the rational numbers lie densely on the line”. I think most people “with no mathematical training” would not, in fact, know this fact, particularly if they needed to see a definition of the rational numbers in the first place. Likewise, some familiarity with the propositional calculus seems to be assumed from the outset, as does an ability to follow detailed mathematical reasoning. Since most people without mathematical training probably don’t even know precisely when the statement “P implies Q” is true or false, it seems hard to believe that they could possibly comprehend any of the more intricate arguments made in this book.

What is Mathematical Logic? is based on lectures given by the five authors at Monash University and the University of Melbourne in 1971, presumably to mathematics students. The six chapters do, in fact, read like transcripts of lectures, complete with frequent use of first-person terminology (e.g., “I will now explain…”).

The book is quite short, less than 80 pages of textual material, and so is necessarily much more succinct than full-length books on the subject such as Enderton’s A Mathematical Introduction to Logic, yet the authors do not merely discuss the topics of this book in broad, general terms but actually give considerable technical detail. This, I think, is the major problem with the book: once a decision has been made to go beyond intuitive generalities and actually provide mathematical arguments, it takes a certain amount of space to make that detail comprehensible. Trying to cover a lot of difficult mathematics, at a level comprehensible to people with no mathematical training, in 80 pages, seems like an impossible task.

Chapter 1 is largely expository, constituting a quick and rather selective historical overview of logic, treating the subject as running through two strands: the “deductive” strand and the analysis strand with emphasis on set theory. The authors discuss how the two streams start to converge in the mid-1800s and also discuss in broad terms a host of other topics, including: the countability of the rationals and the uncountability of the reals, the Russell paradox, the completeness of the predicate calculus and the incompleteness of arithmetic, the Lowenheim-Skolem theorem and the associated Skolem paradox, recursive functions, the Axiom of Choice and the Continuum Hypothesis.

Subsequent chapters elaborate on these ideas, at least to the extent that one can do so in a book of this very short length. The second chapter introduces the predicate calculus (or a simplified version thereof, with only one predicate symbol and one rule of inference, modus ponens) and then sketches a proof of the completeness of this system. The concept of a model is also introduced in this chapter, and discussed in yet more detail in the next (“Model Theory”), which also discusses predicate calculus with identity, the Compactness theorem and the Löwenheim-Skolem-Tarski theorem on models of infinite cardinality. A few illustrations of the Compactness theorem are given, one of them to nonstandard models.

The fourth chapter provides an overview of recursive functions and Turing machines. There is a curious omission here: although the authors allude to the generally held belief that Turing machines can perform all computations, they never once use the phrase “Church’s Thesis” in connection with that idea. In fact the name “Church” does not appear in the index, or, as far as I could see, anywhere else in the book.

The book contains errors of commission as well as errors of omission. As an example of the former, page 22 offers a list of first-order statements involving a predicate P(x, y), which, when this is interpreted to mean x < y, allegedly characterize the “less than” relationship on the set of natural numbers. However, one of these statements (the second from the last) is not, as written, even true in this interpretation. (It takes some rearrangement of parentheses to make it true and to give it the meaning ascribed to it by the authors.)

The theme of chapter five is the incompleteness theorems of Gödel. The chapter begins with a few paragraphs that attempt to provide an intuitive explanation of these results and how they are proved, but the bulk of the chapter is taken up with a rather technical discussion of the ideas of the proof. Axioms for arithmetic are given, Gödel numbers are defined, and it is explained at some length why there is a mechanical way of determining whether a given integer is the Gödel number of a numeral or formula.

The authors then consider “the formula which says that x is the Gödel number of a proof of the formula that you get when you put in for its free variable the numeral for its own Gödel number.” There may be people without mathematical training who can understand this, but I doubt there are very many. The authors do attempt to explain this on an intuitive level by drawing an analogy with the Cantor diagonalization procedure discussed earlier to prove the uncountability of the real numbers, which again made me wonder why the authors put in this kind of level of detail if they don’t have the space to really make it comprehensible. The chapter concludes with the creation of a statement with the property that neither it nor its negation is provable, followed by a two-page discussion of the consistency of arithmetic and why (this is Gödel’s second incompleteness theorem) that consistency cannot be established in the system of arithmetic itself.

The sixth and final chapter is on set theory. At twenty pages in length, it is the longest chapter in the book, but not long enough to explain clearly the array of sophisticated topics the authors set out to discuss: Russell’s paradox, the axioms of Zermelo-Fraenkel set theory, the axiom of choice (AC), ordinal and cardinal numbers, Cantor’s theorem (with proof) that the cardinality of the power set of a set exceeds the cardinality of the set, the consistency of the axiom of choice and constructible sets, the Continuum Hypothesis (CH) and Generalized Continuum Hypothesis (GCH), the independence of both AC and GCH from the other axioms, and Paul Cohen’s method of forcing.

Apart from the difficult technical details of the mathematics, several statements here are puzzling. When the authors state, for example, on page 61, that the elements of an arbitrary set x “must themselves be sets”, it seems less than clear just why this should be so, since the authors have not really made a point of previously emphasizing this fact. Likewise, on page 64, the authors attempt to explain why some mathematicians are dubious about AC by pointing out that, unlike AC, all the other axioms “give us a concrete construction for sets”, a statement which I do not think so clearly applies, for example, to the Comprehension Schema axiom, described by the authors as follows: “Given any set a, and given any formula ψ(x) in which x is a free variable… then there is a set b such that the members of b are exactly those members of a which have the property ψ”. If there is something about this axiom that gives a “concrete construction”, it is certainly not readily apparent to me.

One very nice thing about this book is its price: costing just under seven dollars, it is something that even a penurious grad student can afford as a way of becoming roughly familiar with the subject. Aside from this, however, I could not confidently recommend this book. As previously noted, I think it is not suitable for people without mathematical training, and anybody who does have that training, and is willing to tackle the details of this text, would probably, with very little extra effort, get more out of books like Enderton’s text or Wolf’s A Tour Through Mathematical Logic, both of which, though longer, are in my opinion easier to read (and of course anybody reading these two books who is not concerned with details could save a lot of time by skipping most or all of the technical points in the proofs).

Yet another alternative for a person wishing to get an overview of the subject would be to read some of the online lecture notes on logic; Stefan Bilaniuk of Trent University, for example, has made freely available at his modified Moore-method notes A Problem Course in Mathematical Logic, which covers many of the topics in this book; a reader of those notes can of course choose the amount of detail that he or she wishes to fill in. It may well be the case that in 1972, when this book was published, the textbook options for a course in logic were more limited, but now there are certainly enough clear and reasonably succinct books on logic available that this text is no longer an optimal choice.

Mark Hunacek ( teaches mathematics at Iowa State University.

1. Historical Survey
2. The Completeness of Predicate Calculus
3. Model Theory
4. Turing Machines and Recursive Functions
5. Gödel's Incompleteness Theorems
6. Set Theory
Some Suggestions for Further Reading