It’s always interesting to find a text that reimagines, and offers a novel approach to, a fairly standard subject. This book does that for logic. In its typical incarnation as an undergraduate course, the topics covered generally focus on the propositional and first order predicate calculus, with perhaps (depending on time and class quality) some attention paid to more sophisticated topics such as Gödel’s Incompleteness Theorem. This book, however, envisions a different kind of course.
The novel feature of this text, one that genuinely distinguishes it from competing books at this level, is that it is interdisciplinary. Not only is it intended for students in different college departments, it is actually written by people from these different departments. Loveland is a computer scientist, Hodel a mathematician, and Sterrett a philosopher. Each of these three authors has written one part (three or four chapters each) of the text, emphasizing the relationship of logic to their specialty. Although one can occasionally detect a mild difference in writing style (Sterrett, for example, is much fonder of footnotes than are her co-authors), the three parts fit together seamlessly; they reference, and complement, each other nicely. In addition, the three parts of the book are not rigidly compartmentalized; as will be seen shortly, for example, there were times when Loveland’s part read like it was written by and for mathematicians and Hodel’s read like it was intended for computer science students. This is, of course, all to the good; it offers a more uniform approach to the subject.
Part 1 of the text is authored by Loveland and is concerned with proof theory. It begins with the propositional calculus and discusses it both semantically (the truth or falsity of a statement) and syntactically (logical deduction; done here using resolution, an approach that is related to the programming language Prolog and which is, therefore, of interest to computer science students). The semantic and syntactic points of view are related by the soundness and completeness theorems, which, taken together, essentially say that a statement is a tautology if and only if it is a theorem; full proofs of these theorems are given. Next up is the predicate calculus, also discussed both semantically and syntactically, but here not all the proof details are provided. A third chapter in this part then addresses the relationship between resolution and Prolog.
The author of Part 2 is Hodel, the mathematician in the triumvirate of authors, but his topic (computability theory) is one that is of intrinsic interest not only to mathematics and computer science students but also philosophers as well, in that the discussion reflects the limitations of mathematical reasoning. (This part of the book is a shorter but similar version of the last several chapters of Hodel’s earlier, more traditional, text An Introduction to Mathematical Logic.) Specifically, Hodel discusses the concept of an algorithm and also (in an informal way) computable functions, decidable relations and semi-decidable relations. Register machines and the Church-Turing thesis are discussed, and all of this machinery is applied to the study of four classical problems (Hilbert’s tenth problem on an explicit algorithm for generating solutions to a Diophantine equation, the Halting problem, Hilbert’s decision problem, Thue’s word problem). The unsolvability of the last three problems are established or at least outlined; the reasoning behind the unsolvability of Hilbert’s Tenth Problem is given, but the difficult theorem on which this result is based is not proved in this text, but a reference to the proof in Hodel’s earlier text is given. A special case of Gödel’s Incompleteness Theorem is established, but the result itself is not discussed in the same depth as it is in Hodel’s older textbook. The discussion throughout this part of the book is sometimes algorithm-heavy, but is written so as not to require any programming or computer experience.
The final part of the text is by Sterrett, but these chapters bear no resemblance at all to the logic course that was offered by the philosophy department of my undergraduate institution, and taken by me some 40+ years ago. As I (dimly) recall, that course began with truth tables but quickly segued into fallacies of argumentation and other fairly non-mathematical topics. Sterrett, by contrast, discusses a kind of propositional logic that is entirely different than the classical version discussed in part 1 of the book. This is relevance logic, which arises from the observation that some correct deductions in the classical propositional calculus may nevertheless not seem to accord with the way people ordinarily think. Consider, for example, the statement “If Paris is the capital of France, then either the Collatz conjecture is true or it is not”. As a statement in the classical propositional calculus, this statement is, of course, true, yet the logical implication seems odd; the “if” clause really has no relevance to the concluding “then” clause. In relevance logic, both the semantics and syntax of the logic are altered so as to make some implications false that would be true in classical logic. The author describes an approach to the syntax of the logic that is based on an alternative deductive system for classical propositional logic called Fitch’s natural deduction system, which she describes in some detail and then modifies for relevance logic. In another chapter she describes a semantic approach that, instead of the usual classical two-valued (true or false) approach, is four-valued.
The material in this part of the book, we are told, is largely drawn from Anderson and Belnap’s Entailment, which I have heard described as excellent but very technical and difficult; Sterrett has done a good job of making this material accessible to undergraduates.
There is, to my knowledge, no other undergraduate-level account of all of the material that is discussed in this text. Of the handful of textbooks that I am familiar with that are suitable for undergraduate-level mathematics courses, Schechter’s Classical and Nonclassical Logic is the only one I know of that discusses a number of non-classical logics, but that book also omits a number of other topics that are covered in this text, including the predicate calculus and the material on computability.
This book is written so as to require relatively minimal prerequisites on the part of the reader. Since propositional and predicate logic are developed from scratch, no prior knowledge in logic is assumed, but some background in mathematical reasoning is certainly necessary. (A prior course in proof-based mathematics, such as an “introduction to proofs” course or abstract algebra, should suffice.)
Because of the interesting and fairly nonstandard selection of topics, instructors may notice that some of their favorite topics are not covered. The compactness theorem is perhaps the most glaring example of this; other topics in model theory such as the Löwenheim-Skolem theorem (and the related Skolem’s paradox) are also not here. And, as I noted earlier, Gödel’s Incompleteness Theorem, although mentioned in the book, is discussed in more detail elsewhere. Likewise, second-order logic, covered in some standard texts like Enderton’s A Mathematical Introduction to Logic and (fairly briefly) van Dalen’s Logic and Structure, is not discussed here at all. (I wonder, though, how many undergraduate courses in logic actually cover this last topic.)
In conclusion, this is not your parents’ logic text. An instructor of a logic course offered by a mathematics department who is interested in some experimentation will undoubtedly find this book quite rewarding. (It might not be easy, however, to cover the entire book in a single semester.) Even an instructor who is not planning to teach a course along these lines, but who is interested in the subject, will want to look at this text; there is a lot of interesting and well-presented material found here that cannot be easily found elsewhere in a book at this level.
Mark Hunacek (firstname.lastname@example.org) teaches mathematics at Iowa State University.