You are here

Introduction to Mathematical Logic

Michał Walicki
World Scientific
Publication Date: 
Number of Pages: 
[Reviewed by
Mark Hunacek
, on

The devil, according to the old saying, is in the details, and that expression came to mind several times as I read this undergraduate or early-graduate introduction to mathematical logic. In broad outline, this book covers topics (computability, propositional logic, first order logic) that one would expect to see in such a course, but the method of presentation is, in a number of respects, quite unusual.

This is apparent from the very start of the book, which begins with a fairly detailed look at the history of logic from Aristotle through the 20th century. This discussion, slightly more than 40 pages in length, also serves as a useful exposition of some ideas of the subject that are not developed in the main body of the text, such as the work of Gödel. People who share my view that a sense of history enhances a student’s understanding of mathematical ideas will find this introductory section to be very valuable, even if time constraints limit an instructor’s ability to present it in class.

The rest of the book is divided into four parts. Part I covers the rudiments of set theory and mathematical induction. The approach is informal rather than rigorously axiomatic, although Russell’s paradox is briefly mentioned as an example of how the “unrestricted use” of set-building can cause “severe problems”.

Part II, consisting of one short chapter, introduces Turing machines and the concepts of computability and decidability. This also struck me as an unusual feature, in that it precedes any discussion of propositional or first order logic; most of the elementary logic books with which I am familiar cover these topics first.

The propositional calculus is the subject of Part III of the book, and here again the details of presentation are unusual. Most undergraduate texts on this subject discuss the semantic aspects (e.g., truth tables) of the propositional calculus first, and then discuss the syntactic approach (i.e., axiomatically defining the rules of inference). These approaches are then tied together by the soundness and completeness theorems. These concepts are discussed here as well, but the author reverses the traditional approach of discussing semantics first and instead plunges directly into an axiomatic account of the propositional calculus. (In fact, several different axiom systems for the propositional calculus are given.) Some other unusual aspects of presentation in this chapter include a fairly extended (more than five pages long) discussion of Euclidean and non-Euclidean geometry as part of the author’s treatment of axiom systems (this topic had been alluded to before, in the historical section) and a chapter on the use of propositional statements and graph theory to analyze paradoxes.

This brings us to the final part of the book, on first order logic. With only about 80 pages of text left, there is not much space left to go into this subject in depth, but its syntactic and semantic aspects are discussed (in that order) and, again, soundness and completeness theorems are proved.

This is an interesting text with a distinctive approach to the subject matter. Is it one that students will enjoy reading? Mathematical logic is difficult, technical and notation-heavy, but the author does make an attempt to make things reasonably accessible, including the use of introductory motivational sections that begin most chapters. Despite these efforts, though, it seems to me that books like An Introduction to Mathematical Logic by Hodel and A Friendly Introduction to Mathematical Logic by Leary and Kristiansen are a bit more student-friendly. (The latter, however, omits the propositional calculus.)

The nonstandard features of this text that are discussed above may or may not be a good thing, depending on the preferences of individual instructors. Such instructors also may or may not like the author’s selection of topics: Gödel’s Incompleteness Theorem, for example, is mentioned in the historical survey but is not proved in the text; likewise for some results in model theory, such as the Löwenheim-Skolem theorem.

There is both a regular index and an index of symbols, but both struck me as being in need of improvement. The former, for example, does not list “Gödel” under “G”; however, looking up “theorem of—” under “T” will direct you to Gödel’s first and second incompleteness theorems, both of which are mentioned in the introductory historical section. In the latter, I couldn’t find the symbols \(\mathcal{H}\) and \(\mathcal{G}\) (for Hilbert’s and Gentzen’s axiomatic systems). In addition, there is no bibliography or list of references at all, which I view as a substantial deficiency in a textbook.

Finally, a word about the title, which describes this text as an “extended edition”. I have not seen the original edition, but, as best as I can tell from, it was published about five years ago, was about fifteen pages shorter, and did not contain the chapter on semantic paradoxes that now appears in Part III of the text. The back cover also indicates that the exercise sets have been expanded; there are now a reasonable, though not terribly large, number of them.

Conclusion: this text is certainly worth a look by any instructor of a mathematical logic course, and the introductory historical discussion is a very attractive feature of the text. That being said, I still view Hodel as the top choice for such a course.

Mark Hunacek ( teaches mathematics at Iowa State University. 

  • A History of Logic:
    • Patterns of Reasoning
    • A Language and Its Meaning
    • A Symbolic Language
    • 1850–1950 — Mathematical Logic
    • Modern Symbolic Logic
    • Summary
  • Elements of Set Theory:
    • Sets, Functions, Relations
    • Induction
  • Turing Machines:
    • Computability and Decidability
  • Propositional Logic:
    • Syntax and Proof Systems
    • Semantics of PL
    • Soundness and Completeness
    • Diagnosing Paradoxes
  • First Order Logic:
    • Syntax and Proof Systems of FOL
    • Semantics of FOL
    • More Semantics
    • Soundness and Completeness
  • Why is First Order Logic “First Order”?