% Mathematical Logic
% Mort Yao
% 2017-10-20
*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.
# Classical Logic
Textbook:
* Herbert B. Enderton.
***A Mathematical Introduction to Logic, 2nd edition.***
* [Author's commentary](http://web.archive.org/web/20150712180839/http://www.math.ucla.edu/~hbe/amil/) (Internet Archive)
* [Solutions](http://dbfin.com/logic/enderton/)
* [Book notes by Peter Smith](http://www.logicmatters.net/tyl/booknotes/enderton/)
Supplementary reading:
* Elliott Mendelson.
***Introduction to Mathematical Logic, 4th edition.***
* [Book notes by Peter Smith](http://www.logicmatters.net/tyl/booknotes/mendelson/)
* Stephen Cole Kleene.
***Introduction to Metamathematics.***
* [Book notes by Peter Smith](http://www.logicmatters.net/tyl/booknotes/kleene-metamath/)
* Stephen Cole Kleene.
***Mathematical Logic.***
* [Book notes by Peter Smith](http://www.logicmatters.net/tyl/booknotes/kleene_ml/)
* Raymond M. Smullyan.
***First-Order Logic.***
* Robert S. Wolf.
***A Tour Through Mathematical Logic.***
#. Propositional logic
#. First-order logic
* [First-order languages](fol/languages/)
* [Structures](fol/structures/)
* [Definability and homomorphisms](fol/definability/)
* [Formal deductions](fol/deductions/)
* [Some metatheorems of deduction](fol/metatheorems/)
* [Soundness](fol/soundness/)
* [Completeness](fol/completeness/)
* [Compactness](fol/compactness/)
#. Second-order logic
#. Modal logic
# Axiomatic Set Theory
Reading:
* 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](http://www.logicmatters.net/tyl/set_theory/) (also includes set theories other than ZFC, such as NBG)
# Model Theory
Reading:
* Maria Manzano.
***Model Theory.***
* C.C. Chang, H.J. Keisler.
***Model Theory, 3rd edition.***
#. Kripke semantics
#. Algebraic logic
# Computability and Recursion 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.***
#. Number theory
* Presburger arithmetic
* Peano arithmetic
#. Undecidability and Gödel's incompleteness theorems
# Proof Theory
Reading:
* Sara Negri, Jan von Plato and Aarne Ranta.
***Structural Proof Theory.***
#. Structural proof theory
* Deep inference and cirquent calculi
#. Ordinal analysis
#. Provability logic
#. Reverse mathematics
# 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.***
#. Intuitionistic logic
* Intermediate logics
* Minimal logic
#. Substructural logic and paraconsistent logic
* Linear logic
* Relevant logic
#. Many-valued logic
* Fuzzy logic
* Probability logic
#. Non-reflexive logic