A Mathematical Introduction to Logic

Citation

Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). Harcourt/Academic Press.

Chapter Summary

The second edition is a compact text of about 300 pages. After a preface and an introduction it has five chapters, numbered from zero, followed by suggestions for further reading, a list of symbols and an index. The publisher describes it as written for a reader who has not studied logic before but has some experience in mathematical reasoning, and as offering more flexibility in how a course can use the material than the first edition. It adds material on computer science issues such as computational complexity and database queries, and additional coverage of introductory material on sets. The chapters are very unequal in length, which is a useful guide to where the substance lies.

Chapter 0: Useful Facts about Sets

A short chapter of ten pages gathering the set-theoretic background that the logic chapters rely on. It is a reference to consult when a notion is unfamiliar, not a course in set theory.

Chapter 1: Sentential Logic

Fifty-six pages on propositional logic, the first of the logical systems studied. The chapter's contents include truth assignments, a parsing algorithm for sentences, and compactness and effectiveness.

Chapter 2: First-Order Logic

The longest chapter, at 115 pages, covering first-order languages, truth and models. At more than a third of the text it is the centre of the book.

Chapter 3: Undecidability

One hundred pages under the heading of undecidability. Its closing sections include the second incompleteness theorem and the representation of exponentiation, so the chapter reaches the incompleteness results.

Chapter 4: Second-Order Logic

A short final chapter of 25 pages. Its contents include second-order languages, Skolem functions, many-sorted logic and general structures.

Key Concepts

Chapters 0–1: Sets and Sentential Logic

• Truth assignment: a way of assigning truth values to sentence symbols, used to define when a formula is true.
• Parsing algorithm: a procedure that decides whether a string is a well-formed sentence and recovers its structure.
• Compactness: a property relating the satisfiability of a set of sentences to that of its finite subsets.

Chapter 2: First-Order Logic

• First-order language: a formal language with quantifiers, in which statements about mathematical structures are written.
• Truth and models: the definition of when a sentence holds in a structure, and the notion of a model of a theory.

Chapters 3–4: Undecidability and Second-Order Logic

• Second incompleteness theorem: the limitation on proving a theory's own consistency, treated in Chapter 3.
• Skolem functions and many-sorted logic: devices that appear in the final chapter on second-order languages.

Critical Analysis

Strengths

• Directed at newcomers to logic. The publisher states that the book is for a reader who has not studied logic previously but has experience in mathematical reasoning, and the second edition is described as more accessible to today's undergraduate mathematics and philosophy students.
• Flexible use. The description emphasizes that the revised edition offers increased flexibility, with a choice in how to use the text in a course.
• Links to computer science. The publisher highlights material on computational complexity and database queries, which makes the book relevant to students of theoretical computer science as well as mathematics and philosophy.
• Compact and well proportioned. With 317 pages and five chapters, the book is short enough to read through, and the page counts make the weight of each chapter visible: first-order logic and undecidability take about two thirds of the text.

Limitations

• Five topics only. The contents are sets, sentential logic, first-order logic, undecidability and second-order logic. Readers who want model theory, set theory or computability as subjects in their own right will need further books, and the book's suggestions for further reading are the place to begin.
• Little hand-holding on proof technique. Because the book assumes some experience in mathematical reasoning, students who have not yet written proofs should read a proof-writing text first.

Where It Fits in the Course

Enderton is the formal logic text in this list, for students who can already write proofs. Hammack's Book of Proof and Velleman's How to Prove It teach the proof techniques and basic logic that it presupposes. Leary and Kristiansen's A Friendly Introduction to Mathematical Logic is an open textbook for a first course in mathematical logic at upper undergraduate level and is a gentler alternative or a companion if Enderton moves too fast.

The other books in the list, on pure mathematics, mathematical reasoning and numbers and proofs, cover wider ground than logic. Enderton is the one to choose when the goal is the formal study of languages, structures and proof, culminating in incompleteness and undecidability.

How to Use This Book

The publisher gives the readership as undergraduates and graduates in computer science, philosophy and mathematics. A reader should be comfortable with mathematical proofs; a basic acquaintance with sets helps, and Chapter 0 fills gaps.

• Core: Chapters 1 and 2 form a first course, about 170 pages together.
• Next: Chapter 3 for incompleteness and undecidability, which links to computability and is where the book reaches its most famous results.
• Optional: Chapter 4 on second-order logic, and Chapter 0 only as needed.

Plan reading time by page counts rather than chapter numbers, since Chapter 2 alone is longer than Chapters 0, 1 and 4 together. Practise by writing out the arguments about syntax and semantics rather than reading them passively. Use the suggestions for further reading at the end of the book for model theory, set theory and computability.