Mathematical Logic

Heinz-Dieter Ebbinghaus , Jörg Flum , Wolfgang Thomas

Publisher:

Springer

Publication Date:

2021

Number of Pages:

313

Format:

Hardcover

Edition:

Series:

Graduate Texts in Mathematics

Price:

79.99

ISBN:

978-3-030-73838-9

Category:

Textbook

BLL Rating:

BLL*

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

MAA Review
Table of Contents

[Reviewed by

Stephen Walk

, on

01/6/2023

]

As an introduction to its topic, Mathematical Logic by Heinz-Deiter Ebbinghaus, Jörg Flum, and Wolfgang Thomas, now in its third edition, is both deep and broad. First-order logic is the star: The authors provide a thorough examination of first-order logic, then engage in a frank discussion of its limitations and consider alternatives, and finally reveal why it deserves its central place in the realm of mathematical logic.

Part A, eight of the book’s thirteen chapters, opens with a look at the role and features of mathematical proof, then guides the reader through the basic details of the syntax and semantics of first-order languages. The authors establish useful qualities of first-order logic: completeness (which links syntax and semantics), compactness (which leads to interesting and sometimes surprising mathematical results), the Löwenheim-Skolem theorem (which says that a set of axioms with any infinite model must have models of all infinite cardinalities), and some normalization results for languages and symbolic formulas. Set theory as an axiomatic study is part of the discussion, as is basic model theory. It is in the closing chapters of Part A that the authors start to reveal weaknesses of first-order logic. It cannot adequately represent the classes of torsion groups or of fields of characteristic zero, for instance; it cannot characterize the arithmetic system of natural numbers up to isomorphism; and while there is a workaround for such deficiencies, it requires, the authors note, “an explicit use of set theory to an extent not usual in ordinary mathematical practice.”

Part B starts, then, with a look at extensions of first-order logic, with the aim of finding a suitable system with more expressive power. The authors continue to examine limitations of first-order logic—Gödel’s incompleteness theorems are a notable part of that exploration—but they also note similar flaws with the extended systems. Much of this work is done in the chapter on computability, where it is noted that the set of valid sentences of first-order logic is enumerable (listable) by an abstract computing machine but not decidable by one; that is, there is no single mechanical process that can determine validity or invalidity for every first-order sentence.

There is a brief detour into the applied topic of logic programming, connecting some recurring ideas: Horn formulas, the “sequent calculus” as the definition of logical derivation, computability. The authors then introduce the ideas of finite and partial isomorphisms, relating these to model theory and establishing two results on elementary equivalence (Fraïssé’s theorem and Ehrenfeucht’s theorem). That investigation is a bridge to the final chapter and its exploration of Lindström’s theorems, which say that of the useful qualities seen earlier—compactness, the Löwenheim-Skolem theorem, the normalization results, enumerability of the valid sentences—it is impossible to have all of those properties, or even to have certain subsets of them, with a system that has more expressive power than first-order logic. First-order logic isn’t perfect, but there isn’t and cannot be anything better, at least in the precise sense described by Lindström’s theorems. (Details await in Chapter XIII.)

The most conspicuous change in the third edition is the addition of two new sections to the computability chapter, demonstrating the decidability of two theories. Small improvements in readability and clarity have been made throughout the text. Gender-inclusive language has replaced most of the masculine pronouns of the previous edition. Some references in the computability chapter have been updated: The term recursion theory has been replaced by computability theory, Pascal has been replaced by C and Java on a list of programming languages, and the set of primes has been removed from a short list representing unknown “P versus NP” status. The axiom of foundation is included in the discussion of set theory after being absent in the previous edition. Eponyms have been given footnotes with full names and life dates. The bibliography has been expanded. There are four new exercises in Part B.

The exposition is dense but readable, requiring time, concentration, and perhaps a supply of strong coffee but rewarding the reader’s effort. Part of the book’s density comes from the authors’ (successful) efforts to make it self-contained: The needed notation and definitions for the logical concepts are all provided, and results are proved from first principles. The authors put a high priority on drawing connections, reminding the reader where the discussion has been and providing frequent glimpses of where it’s going. They also make a point of addressing fundamental questions such as why logic is worthwhile to study in the first place and why certain methods that seem like circular reasoning or utter paradoxes really aren’t. Those parts of the exposition are generally well written and cogently argued, serving both as a breather between the more strenuous logical excursions and a motivation for embarking on the next leg of the journey.

The notation can be daunting, particularly when the topic of substitution is first taken up, and a strong mathematics background, if not a background in logic particularly, appears to be a prerequisite. But the book seems reasonable for a determined and seasoned reader, and such a reader who also has an expert guide for the rough spots should be able to make good progress. This newest edition has been reclassified, fittingly, as a graduate text, and it is admirably suited to that role.

Those who are already well-versed in logic will find this text to be a valuable reference and a strong resource for teaching at the graduate level, while those who are new to the field will come to know not only how mathematical logic is studied but also, perhaps more importantly, why.

Stephen Walk teaches mathematics at St. Cloud State University in St. Cloud, Minnesota. He regularly teaches a transition-to-higher-mathematics course, introducing students to such topics as formal first-order logic, models of computation, and a glimpse of Gödel’s incompleteness theorems.

See the publisher's website.

Tags:

Mathematical Logic