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: (The first book also provides a basic introduction to sentential (propositional) logic; The second book, as a treatment of naive set theory, actually utilizes axioms.)

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

At a later point, our informal approaches to reasoning such as the induction principle, and the unrestricted use of “naive” sets will be properly justified and formalized by proof theory and axiomatic set theory. So these prerequisites are really just a minimal to bootstrap our study on logic.

1 Classical Logic


Supplementary reading:

  1. Propositional logic
  2. First-order logic
  3. Second-order logic
  4. Modal logic

2 Axiomatic Set Theory


  • Herbert B. Enderton. 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


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

4 Computability and Recursion Theory


  • 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 Proof Theory


  • Sara Negri, Jan von Plato and Aarne Ranta. Structural Proof Theory.
  1. Structural proof theory
    • Deep inference and cirquent calculi
  2. Ordinal analysis
  3. Provability logic
  4. Reverse mathematics

6 Non-Classical Logic


  • 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