You are here

Logic and Structure

Dirk van Dalen
Publication Date: 
Number of Pages: 
[Reviewed by
Mark Hunacek
, on

This is the fifth edition of van Dalen’s respected and enduring logic textbook, first published in 1980. It differs from the fourth edition primarily in the inclusion of a fairly lengthy section on filters and ultraproducts, with applications to logic and algebra.

Intended as a text for an undergraduate course in logic, this text contains considerably more material than can be covered in one semester. It starts with a two and a half page introduction that is itself quite interesting: it is pointed out, for example, that any subset of a group that is closed under the basic operations is a subgroup, whereas a subset of an algebraically closed field that is closed under the four operations of addition, subtraction, multiplication and division need not be an algebraically closed field. The difference in behavior between these two theories is, the author tells us, due to the fact that the theory of groups can be described by universal (“for all”) axioms, but the theory of algebraically closed fields cannot. This is the Los-Tarski theorem of logic, and is offered in the introduction (without proof, of course) as an example of the power of mathematical logic, and a taste of things to come.

The study of logic begins in earnest in chapter 2, which talks about the propositional calculus, both from a semantic and syntactic point of view. In the former, the propositional calculus is studied by means of truth tables. In the latter, the author studies the nature of valid deductions, and Van Dalen was one of the first logic textbook writers to use the proof technique of Gentzen natural deduction to do so, rather than the kind of axiomatic approach employed by Hilbert.

Gentzen natural deduction, which many believe comes closest to the actual method of reasoning used by people, creates derivations by a process of introduction and elimination, pursuant to specific rules. For example, given that both \(A\) and \(A \longrightarrow B\) are true, we can deduce \(B\) as a conclusion; i.e., we have eliminated the connective \(\longrightarrow\). Likewise, if we know that A and B are true, we can deduce the conjunctive \(A\wedge B\); i.e., we have introduced the connective \(\wedge\). This kind of deduction lends itself naturally to the use of tree diagrams, with the root of the tree being the result to be proved.

Having discussed both the semantic and syntactic points of view, the author then connects these by proving the completeness theorem for the propositional calculus, which states that a statement in that language is a tautology if and only if it is provable.

Because the language of the propositional calculus is not sufficiently rich to describe most mathematical theories of interest, the author then introduces, in chapter 3, the predicate calculus. This language is, like the propositional calculus, studied from both the semantic and syntactic points of view, again using Gentzen’s natural deduction. As with the propositional calculus, there is a completeness theorem here, which is proved in the next chapter along with other famous model-theoretic results such as the compactness theorem and the theorems of Skolem-Löwenheim on the size of models. Applications include non-standard models of arithmetic (pages 114–115) and non-standard analysis (pages 115–117). The chapter closes with the newly added section on filters.

These four chapters contain at least enough material for a one-semester course in mathematical logic, but the book contains much more. The next chapter, which is only about ten pages long, is devoted to second-order logic, in which we allow quantification not just over elements of a first-order structure but also, for example, over subsets of such a structure (and Cartesian products). After all, to quote an example provided by the author, the construction of the real numbers from the rationals by the use of Dedekind cuts requires quantification not just over rational numbers but over sets of rational numbers.

This is followed by two chapters on topics which, I suspect, are not often taught to undergraduates. The first is on intuitionistic logic, which is the logic associated with the constructive approach to mathematics advocated by Brouwer. For example, the familiar principle of reduction ad absurdum, the basis for proof by contradiction, is no longer applicable, since it asserts the existence of something without providing a constructive method of finding it. (This means, of course, that the law of the excluded middle must also go.) The next chapter is on normalization; the idea here is that, in both classical and intuitionistic logic, derivations in natural deduction can be streamlined and made more efficient by eliminating certain steps. This chapter makes these ideas precise.

A final chapter states and proves Gödel’s famous incompleteness theorem. This fairly lengthy (almost fifty pages) chapter also serves as an introduction to recursive function theory and Peano arithmetic. As best as I could tell, this chapter does not depend on chapters 5 through 7 and could therefore be covered much earlier in a course.

There is no denying that mathematical logic is a very technical subject, and people attempting to read about it run a significant risk of getting lost in a blizzard of symbols. The author, however, has made a real effort to make this book as accessible to undergraduates as precision and rigor allow; it is not by happenstance that this book has been in print, in one edition or another, for almost 35 years. There are lots of examples and many expository paragraphs attempting to explain what’s really going on. There is also a wide assortment of exercises.

I would say that this text makes somewhat more demands of the reader than, say, a principal competitor like Enderton’s A Mathematical Introduction to Logic. Enderton, for example, contains an introductory chapter on set theory, while this book assumes a rudimentary knowledge of the subject, including the basics of cardinal numbers. I also think most students might find Enderton a bit easier to read. Nonetheless, this is quite a good book and is certainly a very serious contender as a text for an undergraduate course, and should be carefully looked at by anybody teaching such a course.

Mark Hunacek ( teaches mathematics at Iowa State University.