This excellent introductory textbook of mathematical logic is based on lecture notes at the École Normale Superieure for a number of years. It is addressed to “students who feel curious about this field but have no intent to specialize in it”. The authors “treat logic on an equal footing to any other topic in the mathematical curriculum”. They “consider exercises as an essential component of the book, and [they] encourage the reader to work them out thoroughly”. But many of them are quite challenging; for the ‘normaliens’ they may be appropriate. But for students of normal, not so superior schools? Some routine exercises, like giving formal proofs and checking sets of natural numbers if they are recursive, etc, may improve the usefulness of the book.
Here are chapter headings and comments on their contents.
Chapter 1, Counting to infinity, is about naive set theory. The authors start from the standard material, like ordinals, cardinals, their arithmetic including the exponentiation, and Cantor’s normal form. The Cantor-Bernstein theorem, as well as König’s and Hessenberger’s theorems about sums and products of cardinals are proved. In connection with the continuum hypothesis, they present a proof that the continuum is not equal to \(\aleph_\omega\) hy considering cofinality. By means of ultrafilters, Hindman’s theorem is proved (let \(f\) be a function from the positive integers to \(\{1,2,\dots,n\}\), then there is an infinite set \(B\) of positive integers such that \(f\) is constant on the set of all finite sums of distinct members of \(B\)).
In exercises, one encounters some sophisticated topics, including Goodstein sequences and their termination in finite steps; Ulam’s theorem (any sigma-additive measure on \(\aleph\), is trivial); Solovay’s theorem about CLUB (any stationary set in an uncountable, regular cardinal \(\kappa\) is a disjoint union of \(\kappa\) stationary sets); and Cantor’s theorem on the cardinality of any closed subset of \(\mathbb{R}\), (the cardinality is either countable or that of the continuum); and, König’s lemma about trees and the existence of an Aronszajn tree.
Chapter 2, First-order logic, starts with the very beginning: explanation of what symbols to be used, etc. After explanations of formal proofs and models and the like, it ends with a Henkin-style proof of the Gödel completeness theorem.
Exercises include Ramsey’s theorem, the interpolation and the definability theorems, Herbrand normal forms, and the omitting types theorem.
In Chapter 3, First steps in model theory, first the compactness theorem is proved, followed by the diagram method and a topology on the set of theories. The Löwenheim-Skolem theorems are proved, and expansion by definition is introduced. A big portion is spent on the elimination of quantifiers, and its applications to algebraically closed fields. They include: the Chevalley-Tarski’s theorem on quantifier elimination and Hilbert’s Nullstellensatz, and the Lefshetz principle. Using results about unions of chains (the Chang-Łos-Susko theorem), the authors prove Ax’s theorem (a polynomial mapping from \(\mathbb{C}\) to \(\mathbb{C}\) is surjective if it is injective).
Exercises include the ultraproduct construction, Łos’s theorem, and a direct proof of compactness. In dense linear orders, quantifiers are eliminable, but not in discrete linear orders. However, if one adds the successor function, the answer changes to ‘yes’. The last excise is about Mostowski-Ehernfeuch’s indiscernible sequences.
The standard material in Chapter 4, Recursive functions, is: primitive, total, and partial recursive functions; the Ackermann function; Turing machines and computability; and how they are related. The authors introduce universal functions, the \(s\)-\(m\)-\(n\) theorem, Kleene’s fixed point theorem, and Rice’s theorem. As to r.e. sets: their definition, equivalent conditions, the halting problem are treated in this section. Using Gödel’s \(\beta\)-function and total \(\mu\)-operator, the authors show that the recursion scheme can be eliminated.
In Exercises, one encounters Kalmár elementary functions, two r.e. sets that are not separable recursively, and a primitive recursive bijection whose inverse is not primitive recursive.
In Chapter 5, Models of arithmetic and limitation theorems, the authors first treat decidability of theories of algebraically closed fields and of the ordered field of real numbers. Then, PA and its subtheory \(\mathrm{PA}_0\) (which is PA minus the induction scheme and is a definitional extension for ‘less-than’ of Robinson’s \(Q)\) are introduced. After the diagonal argument and the fixed point theorem, undefinability of truth (Tarski) and the essential undecidability of \(Q\) (Church) are proved. Gödel’s first incompleteness theorem follows as a corollary of Church’s theorem (although these theorems were proved in the other order historically, of course). Rosser’s extension is shown with the original proof. As a preliminary step for a proof of Gödel’s second incompleteness theorem, the authors prove the definability of satisfaction of \(\Sigma_1\)-formulas in PA. (Here, \(Q\) is not powerful enough.) Then the famous theorem is proved along the line of provability logic, using Löb’s theorem. As a result, it is shown that PA can not prove \(\lnot Pr(\varphi)\) for any sentence \(\varphi\), not just ‘\(0=1\)’. In connection with formulas, any total recursive function is represented by a \(\Sigma_1\)-formula in \(Q\), and an r.e. set is definable in \(\mathbb{N}\) by a \(\Sigma_1\)-formula.
Exercises include Presburger arithmetic, the existence of total recursive functions which are not provably total \(\Sigma_1\), end extensions of models (MacDowell & Specker), and Tenenbaum’s theorem (There is no recursive non-standard model of PA).
Chapter 6, Axiomatic set theory, begins with a description of ZF axioms. After explanations of transfinite induction and recursion, the aleph-, beth-, and the von Neumann-\(V\)-hierarchies are introduced. This \(V\) is shown to satisfy the axioms of replacement and of foundation. Skolem’s paradox is explained and the axiom of choice is introduced. ZFC indicates its addition and \(\mathrm{ZFC}^-\) the removal of the axiom of foundation. \(\mathrm{ZF}^-\) is essentially incomplete; namely any consistent recursive extension of it can not prove its own consistency; but it can prove Con(PA). The relativization technique is applied to \(V\) to show such theorems as: ZFC+ (existence of an inaccessible cardinal) proves Con(ZFC). In the last section, the authors mention big results without proofs. They include Gödel’s and Cohen’s work on the axiom of choice and the continuum hypothesis, and Solovay’s theorem (if ZFC is consistent, so is ZF+ (the dependent choice) + (every subset of \(\mathbb{R}\) is Lebesgue measurable)) in contrast to the fact that ZFC proves the existence of non-measurable sets.
Exercises include the Mostowski collapse, Fraenkel-Mostowski permutation models, the reflection principle, the HOD formula, and various consistency and independence results. The non-finite axiomatizability of ZF is also there.
The authors state in the introduction that they have chosen “to deliver a slim text which provides direct routes to some significant results of general interest” “to present a broad panorama of mathematical logic.” They succeeded admirably in their endeavor in this small book of less than 200 pages! It is very precise and concise; the reader must work hard. The reviewer dares to say that some students who started with no intention to major in this area change their minds before they finish.