Computability and Logic

Citation

Boolos, G. S., Burgess, J. P., & Jeffrey, R. C. (2007). Computability and Logic (5th ed.). Cambridge University Press.

Chapter Summary

The fifth edition runs to about 340 pages of text in 27 chapters, opened by a preface to the fifth edition and closed by a two-page annotated bibliography. The chapters fall into three overlapping strands: computability theory, the metatheory of first-order logic, and a set of further topics that build on both. The publisher states that a selection of exercises closes each chapter.

Chapters 1–2: Enumerability; Diagonalization

The book opens with two short chapters (pp. 3–22) on enumerability and diagonalization. They supply the counting and diagonal-argument techniques that the later limitative results depend on.

Chapters 3–5: Turing Computability; Uncomputability; Abacus Computability

These chapters (pp. 23–62) introduce two models of computation, Turing machines and abacus machines, and a chapter on what cannot be computed. The abacus-machine chapter is the longer of the two machine chapters.

Chapters 6–8: Recursive Functions; Recursive Sets and Relations; Equivalent Definitions of Computability

The recursive-function approach to computability is developed, then applied to sets and relations, and the final chapter of the strand brings the different definitions of computability together (pp. 63–98).

Chapters 9–10: A Précis of First-Order Logic: Syntax; A Précis of First-Order Logic: Semantics

A condensed review of the syntax and semantics of first-order logic (pp. 101–125). The word "précis" signals a refresher for readers who have already had a course in the subject, not a first introduction.

Chapter 11: The Undecidability of First-Order Logic

The first major payoff of the computability material: a result about first-order logic itself (pp. 126–136).

Chapters 12–14: Models; The Existence of Models; Proofs and Completeness

The model-theoretic and proof-theoretic core of the metatheory (pp. 137–186). The chapter titles point to the existence-of-models argument that leads into completeness.

Chapters 15–18: Arithmetization; Representability of Recursive Functions; Indefinability, Undecidability, Incompleteness; The Unprovability of Consistency

The incompleteness sequence (pp. 187–240). Arithmetization and representability prepare the ground, the next chapter treats indefinability, undecidability and incompleteness together, and the last turns to the unprovability of consistency. The publisher describes the treatment of representability in this edition as new and simpler than before.

Chapters 19–23: Normal Forms; The Craig Interpolation Theorem; Monadic and Dyadic Logic; Second-Order Logic; Arithmetical Definability

Further topics in logic proper (pp. 243–294), running from normal forms and the Craig interpolation theorem through monadic and dyadic logic and second-order logic to arithmetical definability.

Chapters 24–27: Decidability of Arithmetic without Multiplication; Nonstandard Models; Ramsey's Theorem; Modal Logic and Provability

The closing chapters (pp. 295–340) treat the decidability of arithmetic without multiplication, nonstandard models, Ramsey's theorem, and, last, modal logic and provability.

Key Concepts

Computability (Chapters 1–8)

• Enumerability and diagonalization: the opening techniques for comparing infinite collections and for showing that something cannot appear on a given list.
• Turing and abacus computability: two formal models of what an effective procedure can do.
• Recursive functions: a third characterization of computability, shown in Chapter 8 to be equivalent to the others.

First-order metalogic (Chapters 9–14)

• Syntax and semantics of first-order logic: the language, interpretations and truth that the metatheorems are about.
• Models and proofs: the link between truth in all models and derivability that the completeness theorem establishes.
• Undecidability of first-order logic: the limit on any general decision procedure for validity.

Incompleteness and further topics (Chapters 15–27)

• Arithmetization and representability: coding syntax by numbers and expressing computable functions inside arithmetic.
• Incompleteness and the unprovability of consistency: the limitative results the book builds toward.
• Interpolation, second-order logic, nonstandard models, Ramsey's theorem, modal logic and provability: topics named in the later chapter titles.

Critical Analysis

Strengths

• A wide menu of topics in one volume. The publisher describes the book as covering the staple topics of an intermediate logic course, including Gödel's incompleteness theorems, together with a large number of optional topics ranging from Turing's theory of computability to Ramsey's theorem. The table of contents bears this out: chapters 19–27 are titled as separate topics that follow the main line.
• Aimed at students without a mathematical background. The publisher presents accessibility to such students as the reason the book has become a classic, and the use of abacus machines alongside Turing machines is one visible expression of that aim.
• Exercises at the end of each chapter. According to the publisher, each chapter closes with a selection of exercises, adjusted for the fifth edition.
• A simplified route through representability. The edition's new treatment of the representability of recursive functions addresses what the publisher calls a traditional stumbling block on the way to the incompleteness theorems.

Limitations

• Condensed review of first-order logic. Chapters 9 and 10 are a précis, so the book assumes a prior course in first-order logic; readers who need a first presentation should begin elsewhere.
• Scope is fixed. The chapter titles show a book confined to computability, first-order metalogic and a list of extensions; readers wanting, for example, a full treatment of proof theory or set theory will need other texts.
• Choosing a route takes effort. With 27 chapters and many optional ones, an instructor or self-study reader must decide which to omit; the table of contents does not mark the core.

Where It Fits in the Course

Within the logic course list, this is the most demanding mathematical text. Forall x (Calgary) is a free introduction to truth-functional and first-order logic using Fitch-style natural deduction, and Copi's textbook covers informal reasoning, syllogisms and symbolic logic; both are first courses. Barker-Plummer, Barwise and Etchemendy's Language, Proof and Logic pairs a first-order logic textbook with software and reaches soundness, completeness and a sketch of Gödel's first theorem, so it already touches the territory this book treats in full. Theodore Sider's Logic for Philosophy is a second course for philosophy students that proves results about propositional and predicate logic and then moves to modal logic; it is the nearest alternative, and the two can be read side by side.

Computability and Logic is the natural next step after a first course in formal logic when the goal is to see Turing machines, undecidability and the incompleteness theorems proved in detail.

How to Use This Book

The book suits philosophy, mathematics and computer science students who have finished a first course in formal logic and want complete proofs of the limitative theorems. The publisher stresses that no mathematical background is required, but the book is a proof-based text, so patience with proofs is needed.

A practical plan: read Chapters 1–8 for computability; skim Chapters 9–10 as a refresher and return to them when a notion is needed; read Chapters 11–14 for undecidability, models and completeness; and read Chapters 15–18 as a unit for incompleteness. Chapters 19–27 are best chosen according to interest: Chapter 22 on second-order logic and Chapter 27 on modal logic and provability are natural for philosophy students, and Chapters 24–25 for those interested in arithmetic and its models. Work the exercises at the end of each chapter, since the proofs are easier to follow once their techniques have been used.