Module manager: Paul Shafer
Email: p.e.shafer@leeds.ac.uk
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2026/27
None
| MATH2140 | Introduction to Logic |
MATH3104 MATH5104M
This module is not approved as a discovery module
This module is an introduction to the theory of computation and to provability in formal systems. We develop mathematical models of computation and universal machines, then we analyze classic undecidable problems such as the famous halting problem. We then connect computation to provability in formal systems like Peano arithmetic. The module culminates with a version of Gödel's incompleteness theorem for Peano arithmetic: there is a true statement that the system cannot prove.
We introduce register machines and while programs as models of computation, argue that they are computationally equivalent, and compute some basic numerical functions in these models. We develop a universal machine that can simulate all others. Then we move on to the theory of non-computable functions. We show that the halting problem is undecidable, and we introduce computational reducibilities in order to compare non-computable sets and functions to each other. Then we connect computation and arithmetic by showing that computable functions can be represented by simple formulas in arithmetic. This leads to a proof that truth in arithmetic is undecidable. Next we introduce Peano arithmetic and discuss provability and non-provability in this system. Ultimately, we prove Gödel's first and second incompleteness theorems for Peano arithmetic. There is a true statement that Peano arithmetic does not prove. Moreover, the consistency of Peano arithmetic is such a statement.
On successful completion of the module students will have demonstrated the following learning outcomes relevant to the subject: 1. Compute basic numerical functions and sequence manipulation tasks with register machines and while programs. 2. Use techniques such as diagonalization and many-one reduction to show that certain sets and functions are not computable. 3. Determine the complexity of an arithmetical property in the arithmetical hierarchy. 4. Give proofs of basic numerical facts in Peano arithmetic. 5. Outline a proof of Gödel's incompleteness theorem. 6. Describe connections between incompleteness, consistency, computability and undecidability.
1. Register machines, while programs, computable functions, and universal machines 2. Non-computable sets and functions 3. Computably enumerable sets 4. Many-one reductions and relative computability 5. First-order arithmetic 6. The undecidability of truth 7. Hilbert systems and Peano arithmetic 8. The Gödel incompleteness theorems. Additional topics that build on those above may be covered as time allows.
| Delivery type | Number | Length hours | Student hours |
|---|---|---|---|
| Lecture | 44 | 1 | 44 |
| Private study hours | 156 | ||
| Total Contact hours | 44 | ||
| Total hours (100hr per 10 credits) | 200 | ||
Formative feedback will be provided on regular example sets or other similar learning activity
Check the module area in Minerva for your reading list
Last updated: 30/04/2026
Errors, omissions, failed links etc should be notified to the Catalogue Team