Mathematical Logic

Mort Yao

Prerequisites: Most content on this topic assumes some mathematical proof techniques (incl. mathematical induction) and basic knowledge of naive set theory. The following books might be a good refresher:

  • Daniel J. Velleman. How to Prove It: A Structured Approach.
  • Paul Halmos. Naive Set Theory.

The first book also provides a fair introduction to propositional (sentential) logic.


1 Classical logic

Textbook:

Supplementary reading:

  1. Introduction
  2. Propositional logic (sentential logic)
  3. First-order logic
  4. Second-order logic
  5. Modal logic

2 Axiomatic set theory

Reading:

  • Herbert B. Enderton. The Elements of Set Theory.
  • Raymond M. Smullyan and Melvin Fitting. Set Theory and the Continuum Problem.
  • Thomas Jech. Set Theory, 3rd millennium edition.

See also Peter Smith’s suggestions for reading on the set theory: Serious set theory (also includes set theories other than ZFC, such as NBG)

3 Model theory

Reading:

  • Maria Manzano. Model Theory.
  1. Kripke semantics
  2. Algebraic logic

4 Computability theory

Reading:

  • Peter Smith. An Introduction to Gödel’s Theorems.
  • Richard Epstein and Walter Carnielli. Computability: Computable Functions, Logic, and the Foundations of Mathematics.
  • George Boolos, John P. Burgess and Richard Jeffrey. Computability and Logic.
  1. Number theory
    • Presburger arithmetic
    • Peano arithmetic
  2. Undecidability and Gödel’s incompleteness theorems

5 Structural proof theory

Reading:

  • Sara Negri, Jan von Plato and Aarne Ranta. Structural Proof Theory.
  1. Deep inference and cirquent calculi

6 Non-classical logic

Reading:

  • Graham Priest. An Introduction to Non-Classical Logic: From If to Is, 2nd edition.
  • John L. Bell, David DeVidi and Graham Solomon. Logical Options: An Introduction to Classical and Alternative Logics.
  1. Intuitionistic logic
    • Intermediate logics
    • Minimal logic
  2. Substructural logic and paraconsistent logic
    • Linear logic
    • Relevant logic
  3. Many-valued logic
    • Fuzzy logic
    • Probability logic
  4. Non-reflexive logic