Logic, Computability, and Incompleteness (Autumn 2025)
This course introduces central results about the nature, scope, and limitations of formal logic, mathematical proof, and algorithmic computability.
We begin with a review of propositional and predicate logic, including soundness and completeness proofs. We then take a brief look at axiomatic theories of arithmetic and set theory, before developing a rigorous concept of computability, first in terms of Turing machines, then in terms of $\mu$-recursive functions. Bringing the two strands together, we show that all computable functions are representable in certain axiomatic theories, from which it follows that these theories, if consistent, can't be complete, and that they can't prove their own consistency. These are Gödel's First and Second Incompleteness Theorem. We'll also cover related results such as Church's Theorem, Tarski's Theorem and Löb's Theorem.
No prior knowledge besides introductory logic is assumed, but the course is not a continuation of Logic 1. It is much harder.
Course organiser
Course Administrator
Classes
Friday 9:00-10:50, Dugald Stewart Building, room 1.17
Assessment
- Take-Home Test (20%), date TBC
- Final Exam (80\%), date and location TBC
Readings
Lecture notes for each week will appear in the syllabus below, and are the only required reading.
In addition, you are encouraged to work through one or more of the following textbooks:
- George Boolos & Richard Jeffrey, Computability and Logic, 3rd ed., 1989
- George Boolos, John Burgess & Richard Jeffrey, Computability and Logic, 5th ed., 2007
- Michael Hallet & Richard Zach, Intermediate Logic, 2021, freely available online at https://builds.openlogicproject.org/courses/intermediate-logic/
- Peter Smith, An Introduction to Gödel's Theorems, 2nd ed., 2013, freely available online at https://www.logicmatters.net/igt/
- Moshé Machover, Set Theory, Logic and Their Limitations, 1996