A Friendly Introduction to Mathematical Logic

Citation

Leary, C. C., & Kristiansen, L. (2015). A Friendly Introduction to Mathematical Logic (2nd ed.). Milne Library, SUNY Geneseo. Open textbook (CC BY-NC-SA).

Chapter Summary

The book has eight chapters, a short appendix, solutions to selected exercises (about 75 pages) and a bibliography, in roughly 365 pages. Most sections of the early chapters end with exercises, and each chapter closes with a "Summing Up, Looking Ahead" section that explains where the argument is going. The second edition expands Leary's 2000 first edition with a new chapter on computability and the solutions.

Chapter 1: Structures and Languages

Builds the vocabulary of first-order logic. First-order languages are defined as collections of symbols, then terms and formulas are defined inductively, and induction is generalised so that it can prove statements about terms and formulas. The language of number theory (with 0, successor, addition, multiplication, exponentiation and order) becomes the running example. The chapter then defines structures, variable assignments and truth in a structure, handles substitution and the problem of capturing variables under a quantifier, and ends with logical implication and validity.

Chapter 2: Deductions

Starts by asking what a proof is and then defines a formal deduction. The logical axioms (equality and quantifier axioms) and the rules of inference (propositional consequence and quantifier rules) are set out, and the chapter proves the Soundness Theorem and some properties of the system, including that equality is an equivalence relation and a form of the Deduction Theorem. It closes with nonlogical axioms, using vector spaces and a weak axiom set N for arithmetic.

Chapter 3: Completeness and Compactness

Proves the Completeness Theorem by the method of Henkin, extending a consistent set of sentences to a maximal consistent set and building a model from terms. Compactness follows and is used to construct nonstandard models of arithmetic and to show that no set of first-order sentences pins down the natural numbers. The chapter ends with substructures, elementary substructures and the downward and upward Löwenheim–Skolem theorems.

Chapter 4: Incompleteness from Two Points of View

Explains why a chapter on incompleteness follows one on completeness, defines complete sets of axioms and sets the goal of finding a true sentence that cannot be proved. It introduces the complexity of formulas through bounded and unbounded quantifiers, lays out a roadmap based on coding deductions as numbers, previews a second route through computable functions, and shows how to code a finite sequence of numbers as one number. The chapter ends by recalling the axioms N and their strength. After it the reader can choose Chapters 5 and 6 or jump to Chapter 7.

Chapter 5: Syntactic Incompleteness: Groundwork

The technical core of the formula-based route. It introduces representable sets and functions, relates them informally to computer programs and to the equivalent models of computation (recursive functions, Turing machines, the lambda calculus), and then builds the machinery of Gödel numbering. Step by step it shows that the coding of terms, formulas, the axioms and deductions can be represented in N, ending with a formula that holds exactly when a number codes a deduction of a given formula.

Chapter 6: The Incompleteness Theorems

Proves the Self-Reference Lemma and uses it to construct a sentence asserting its own unprovability. According to Peter Smith's review, the chapter then gives the First Incompleteness Theorem in semantic and syntactic forms, the undecidability of arithmetic, Tarski's theorem on truth, Rosser's improvement and a proof of incompleteness by Boolos based on the Berry paradox, and proves the Second Incompleteness Theorem on the assumption of the derivability conditions.

Chapter 7: Computability Theory

The new chapter of the second edition and about seventy pages long. A short historical section leads to the mu-recursive functions, the s-m-n theorem and Kleene's Normal Form Theorem, followed by the uncomputability of the set K. This is used for the undecidability of the Entscheidungsproblem, a second proof of incompleteness and Hilbert's Tenth Problem (Smith's review).

Chapter 8 and back matter

Chapter 8, "Summing Up, Looking Ahead", brings the strands together and points to further reading. The appendix "Just Enough Set Theory to Be Dangerous" is followed by solutions to selected exercises and the bibliography.

Key Concepts

Chapters 1–2: Languages, Structures, Deductions

• First-order language and structure: syntax of symbols and formulas on one side, mathematical models that interpret them on the other.
• Logical implication and validity: a formula follows from others when it is true in every structure and assignment satisfying them.
• Deduction: a finite sequence of formulas, each an axiom or obtained from earlier ones by a rule, which formalises a proof.
• Soundness: whatever can be deduced is true in all models.

Chapter 3: Completeness and Compactness

• Completeness Theorem: whatever follows logically from a set of axioms can be deduced from them.
• Compactness Theorem: a set of sentences has a model exactly when every finite subset does.
• Nonstandard model: a structure elementarily equivalent to the natural numbers but not isomorphic to them.
• Löwenheim–Skolem theorems: the existence of elementary substructures and extensions of other cardinalities.

Chapters 4–6: Incompleteness

• Complete set of axioms: one that proves or refutes every sentence of its language.
• Representable set or function: one that a formula of the theory defines in a way the theory can prove correct.
• Gödel numbering: assigning natural numbers to symbols, formulas and deductions so statements about proofs become statements about numbers.
• Self-Reference Lemma: for any formula there is a sentence that asserts the formula of itself.
• First and Second Incompleteness Theorems: no decidable, consistent, complete axiomatization of arithmetic exists, and sufficiently strong axioms cannot prove their own consistency.

Chapters 7–8: Computability

• Computable (mu-recursive) function: a function built from basic functions by composition, primitive recursion and minimisation.
• Normal Form Theorem: every computable function can be written using one fixed computable predicate and a single unbounded search.
• Entscheidungsproblem: the question of deciding validity in first-order logic, answered negatively.

Critical Analysis

Strengths

• A friendly, well-paced exposition. Peter Smith's review on Logic Matters likes the relaxed and inviting tone, judges the level of exposition well suited to an introductory course and calls the clarity exemplary. The "Chaff" asides, which the authors use to flag notation traps and give motivation (for example, separating the numeral 0 from the number 0), are a distinctive feature of the chapters.
• Two routes to the same goal. The authors split the path to the incompleteness theorems after Chapter 4: a formula-based route through Chapters 5 and 6, or a computation-based route through Chapter 7. This lets a course choose, and lets a reader see both approaches.
• Exercises and solutions. Exercises close most sections of the first six chapters, and the second edition adds about 75 pages of solutions. The Open Textbook Initiative lists the book as having solutions for many exercises; Smith says this makes it more suitable for self-study.
• A thorough demonstration of representability. Smith calls Chapter 5's treatment, which writes down defining formulas directly, one of the most user-friendly full demonstrations available, and notes that the second edition softens the proof of the Diagonalization Lemma.
• Free and compact. The text is open under a Creative Commons licence, and the authors aim to reach the incompleteness theorems within one semester.

Limitations

• A Hilbert-style system. The deductive system is an axiomatic one with few rules. Smith warns that readers who have not seen a formal system for first-order logic may find it dense at first, and that students used to trees or natural deduction might want an explanation of the choice.
• Chapter 5 is heavy going. The authors themselves describe the chapter as dense and technical, an unending stream of definitions. Plan time for it.
• Narrow scope. The book covers first-order logic up to the Löwenheim–Skolem theorems, the incompleteness theorems and some computability; further model theory and axiomatic set theory are outside it, and set theory appears only in a short appendix.
• Propositional logic is assumed. Propositional logic gets only a brief review in the chapter on rules of inference, so a reader without it needs another source first.
• The Second Incompleteness Theorem rests on assumed conditions. According to Smith, the derivability conditions are assumed rather than proved.

Where It Fits in the Course

Within the logic and set theory books on this site, Leary and Kristiansen is a first course in mathematical logic aimed at Gödel's theorems. It follows the proof-writing books: Hammack's free Book of Proof and Velleman's How to Prove It teach logic, sets and proof methods informally, which is the background this book formalises. The broader books on proof, sets and number systems by Liebeck, Eccles and Allenby are alternatives at that earlier stage.

The closest comparison is Enderton's A Mathematical Introduction to Logic, a rigorous treatment of propositional and first-order logic, formal theories and model theory with links to computability. Leary and Kristiansen is the more narrowly aimed and free choice, going directly toward the incompleteness theorems and spending less on model theory. Reading either one prepares for dedicated texts on model theory, set theory or computability.

How to Use This Book

The book is written for upper-level undergraduates, and the preface presents the two routes to incompleteness; it is also readable for philosophers who are comfortable with abstract argument, according to Smith. The site lists experience with proof-based mathematics as the prerequisite.

A suggested plan:

• Core: Chapters 1 to 4. Chapters 1 to 3 are a self-contained introduction to first-order logic through completeness and compactness; read the definitions in Chapters 1 and 2 slowly, since the later proofs depend on their exact form. Smith notes that Chapter 3 can stand alone for a reader who already knows structures and deductions.
• Choose a route to incompleteness: after Chapter 4, either Chapters 5 and 6 (formulas and Gödel numbering) or Chapter 7 (computability). A second reading can take the other.
• Optional: Chapter 8 and the appendix are brief and mainly orient the reader.
• Exercises: attempt those on explicit deductions and structures, and use the solutions to check your work.