Topics in Logic
Metalogic is the study of formal logical systems with the methods of mathematics. It asks what properties such systems have: Are they complete? Decidable? What is their expressive power? There has been extensive philosophical debate about what sort of lessons we should draw from certain metalogical results. In this course, we will focus on first-order predicate logic. The aim is to familiarize students with key concepts and results about first-order predicate logic, as well as to introduce them to some of the philosophical discussion of these results.
Intended Learning Outcomes
The course assumes that students are familiar with the language of first-order predicate logic, and have seen a proof system for that logic (e.g. natural deduction, tableaux, axiomatic calculus, etc.). By the end of the course, students will be able to
- state the definitions of central notions of model theory (model, truth in a model, validity, etc)
- explain in what sense first-order logic is complete, and sketch, in broad outline, a proof of its completeness
- critically discuss some limitations of first-order logic (e.g. the existence of unintended models of first-order theories, its undecidability)
19/11 09:30 -> 12:15: Introduction. Review of 1st-order Logic
20/11 09:30 -> 12:15: Model-theoretic semantics of 1st-order logic
21/11 09:30 -> 12:15: Proof of Completeness of First-Order Logic
26/11 09:30 -> 12:15: The Significance of the Completeness Theorem (Kreisel reading)
27/11 09:30 -> 12:15: The Löwenheim-Skolem Theorem
28/11 09:30 -> 12:15: Skolem’s Paradox and Putnam’s Model-theoretic Argument (Putnam reading)
03/12 09:30 -> 12:15: Gödel incompleteness and undecidability: limitative results explained
04/12 09:30 -> 12:15: Sketch of proof of Gödel incompleteness theorem
05/12 08:30 -> 13:00: Philosophical discussion of limitative results (Lucas reading)
The course will be assessed by a two-hour exam. There will be two sections, and you will answer one question from each section. The questions in section 1 will test the understanding of some of the technical concepts (no complex proofs expected!), while the questions in section 2 will ask for some philosophical discussion of some metalogical result.
Formative assessment (i.e. assessment that helps learning but does not directly feed into a final grade) will be by short problem sets. Students who consistently hand in problem sets will receive a final point for the exam.
Kreisel, Georg, “Informal Rigour and Completeness Proofs”, in Imre Lakatos (ed.), Problems in the Philosophy of Mathematics. North-Holland. pp. 138--157 (1967).
Lucas, J.R. Minds, “Machines and Godel”, Philosophy, XXXVI, 1961: 112-127.
Putnam, Hilary, “Models and Reality”, Journal of Symbolic Logic 45 (3), 1980: 464-482.