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.1 Introduction

1.2 Propositional Logic

1.3 First-Order Logic

1.4 * Second-Order Logic

2 Axiomatic Set Theory (ZFC)

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 readings on the set theory: Serious set theory (also includes alternative set theories like NBG)

3 Model Theory

Reading:

  • Maria Manzano. Model Theory.

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.

4.1 Peano Axioms

4.2 Gödel’s Incompleteness Theorems

5 Structural Proof Theory

5.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.

6.1 Intuitionistic Logic

6.2 Linear Logic and Relevant Logic

6.3 Probabilistic Logic

7 * Algebraic Logic