Topics in Logic

Metalogic

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)

Schedule

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)

Assessment

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.

Readings

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.