7AAN2043 Mathematical Logic: Limitative Results
THIS MODULE IS NOT RUNNING IN 2017-18
Credit value: 20
Module tutor: Dr Nils Kürbis
- Formative assessment: regular logic exercises
- Summative assessment: one two-hour exam (100%) in May/June
Students are reassessed in the failed elements of assessment and by the same methods as the first attempt.
Teaching pattern: One two-hour weekly lecture and one one-hour weekly seminar over ten weeks.
Sample syllabus: 7AAN2043 module syllabus 2016-17
- This module will be taking more of a formal, technical approach to its material than a philosophical one. It is also largely designed as a continuation of 7AAN2015 First-Order Logic in the first semester, and students are very strongly discouraged from attempting this module unless they have already made their way through that one first (or at least taken something very similar elsewhere)
- The lectures/seminars will be shared with students taking 6AANB029 Mathematical Logic throughout both hours, although in other respects those students may be subject to different requirements
For deeper understanding of the nature of logic and philosophical questions in foundations of maths, a grasp of the famous limitative theorems is crucial: the undecidability of validity (Church); the downward Löwenheim-Skolem theorem; theundefinability of truth (Tarski) and Gödel’s underivability theorems on the incompleteness of interesting formal theories and the impossibility of internal consistency proofs for them. Students should acquire an understanding of these theorems and some acquaintance with proofs of all. They will also be provided with basic concepts and results from recursion theory used in the proofs.
- To introduce students to the important limitative results of Tarski, Goedel, Church, and Turing.
- To give students a hands-on understanding of the proofs of these results.
- To acquaint students with the notion of an axiomatic theory, recursion, theory, computability, and decidability.
- To make students aware of the far-reaching implications of Goedel's incompleteness results.
By the end of the module, the students will be able to demonstrate intellectual, transferable and practicable skills appropriate to a Level 7 module and in particular will be able to demonstrate:
- knowledge and understanding of the limitative theorems
- knowledge of the proofs of these results
- knowledge of the consequences of these results for the formalistic enterprise
- knowledge of the essential differences between first-order and higher-order logics
Course book: Enderton, H. A Mathematical Introduction to Logic 2nd edition. San Diego, Cal: Academic Press 2001.
Recommended additional texts:
- Devlin, K. 1992. Sets, Functions & Logic: an Introduction to Abstract Mathematics. 2nd ed. London: Chapman & Hall.
- Boolos, G. & Jeffrey, R. Computability and Logic. 3rd edition. Cambridge: Cambridge University Press 1989.
- Mendelson, E. Introduction to Mathematical Logic. 4th ed. London: Chapman & Hall 1997.
- Shoenfield, J. Mathematical Logic. Reading, Mass.: Addison-Wesley 1967.
- Bell, J. &Machover, M. A Course in Mathematical Logic. Amsterdam: North-Holland 1977
- Kleene, S. Introduction to Metamathematics. Amsterdam: North-Holland 1952.
The modules run in each academic year are subject to change in line with staff availability and student demand so there is no guarantee every module will run. Module descriptions and information may vary depending between years.