Logic II : Metatheory (PH210-15)
TIMING & CATS
This module runs in the Autumn Term and is worth 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 and the expressive limitations of first-order logic.
LEARNING OUTCOMES OR AIMS
By the end of the module the student should be able to: 1) demonstrate knowledge of the Soundness and Completeness Theorems for propositional and first-order logic and related technical results and definitions; 2) understand the significance these concepts and results have for logic and mathematics; 3) use and define concepts with precision with precision, both within formal and discursive contexts.
For this module students must attend 3 hours of lectures and 1 hour of seminars per week
Lectures for 2012-13
Monday 11am-1pm in P5.21
Wednesday 11am-12pm in MS.04
There will be no lectures in reading week (week 6)
Seminars for 2012-13
Wednesday 12pm-1pm in MS.04
There will be no seminar in reading week (week 6)
This module can be assessed in the following ways:
- 100% examination only
BACKGROUND READING AND TEXTBOOKS
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
- 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.
Please be aware that these materials may not be relevant to the current version of this module; they are intended primarily for students who took the module in other years.