PH210 Logic II: Metatheory 2011-2012
Term 1 2011-2012, 15 CATS
This module will develop the metatheory of propositional and first-order logic. The primary goal is to show that a proof system similar to that of Logic I is sound (i.e. proves only logically true sentences) and complete (proves all logically true sentences). In order to better understand how we prove things about (as opposed to within) a proof system, we will first study elementary set theory and inductive definitions. We will then consider Tarski's definitions of satisfaction and truth in a model and proceed to develop the Henkin completeness proof for first-order logic. Other topics covered along the way will include Russell's Paradox, countable versus uncountable sets, the compactness theorem, the expressive limitations of first-order logic and an overview of intuitionistic, modal, and second-order logic.
Our primary text will be
- Logic and Structure, 4th edition by Dirk van Dalen, Springer Verlag, 2004
in which we will cover most of chapters 1-3. The same material is also covered at a more elementary level in chapters 15-19 of
- Language, Proof and Logic, Jon Barwise and John Etchemendy, CSLI Publications, 2002.
Students lacking a background in elementary discrete maths (e.g. basic set theory and mathematical induction) are encouraged to obtain
- How to prove It: A Structured Approach, Daniel J. Velleman, Cambridge University Press, 2006.
Maths students considering taking further logic courses might consider getting a copy of
- The Mathematics of Logic, Richard Kaye, Cambridge University Press, 2007.