PY4612: Advanced Logic

January 2024

at the University of St Andrews

py4612: Advanced Logic applies the tools of formal logic to make logic itself the object of study. We will explore the power and limits of logical tools and techniques. The main goals of the module will be to come to grips with some standard ‘metatheoretical’ results about logic: (1) the Soundness and Completeness Theorems, which together show that proofs and models can be used analyse the same consequence relation in two very different ways. (2) The Compactness Theorem and the Löwenheim–Skolem Theorems, which explore some of the limits of first-order classical predicate logic for classifying infinite structures. (3) The contrast between first-order predicate logic and second-order logic. Finally (4), we will work through Gödel’s celebrated Incompleteness Theorems and come to grips with what they mean. Along the way, there will be some preparatory discussion of elementary set theory, proof theory, model theory, and recursion theory.