PH340-15 Logic III: Incompleteness & Undecidability
Introductory description
Developments in formal logic in the late 19th and early 20th century opened up the prospect of an entirely formalised mathematics, in which all mathematical statements could be expressed by sentences of a formal language, all proofs could be transformed into deductions in a logical system, and all basic mathematical principles could be codified as axioms. This naturally raised a question of completeness: given such a formal language, and an axiomatic theory T expressed in that language, could T either prove or refute every sentence in the formal language, and thus provide a solution (at least in principle) to every mathematical question expressible in that language? Gödel's incompleteness theorems showed that in general the answer is no: for any consistent axiomatic theory T containing a sufficient amount of arithmetic, there will be sentences in the language of T which T can neither prove nor refute (the first incompleteness theorem). Moreover, such a theory T cannot even prove its own consistency (the second incompleteness theorem). This demonstrates the limits of formalisation in mathematics: there can be no universal formal theory capable of answering all mathematical questions, and we can only prove the consistency of our theories by appealing to strictly stronger theories. In this module we will explore the incompleteness theorems: precisely what they say, and how they are proved. Along the way we will develop an understanding of formal theories of arithmetic and recursive functions.
Module aims
To expose students to Gödel's First and Second Incompleteness Theorems and their significance for the foundations of mathematics.
Outline syllabus
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
Week 1: First-order logic, the language of arithmetic, models of arithmetic
Week 2: Primitive recursive functions and relations
Week 3: Sequences, trees, general recursive functions
Week 4: Arithmetization of syntax
Week 5: Representability in Q (part 1)
Week 6: Reading week
Week 7: Representability in Q (part 2)
Week 8: The fixed-point lemma, the first incompleteness theorem
Week 9: The derivability conditions, the second incompleteness theorem
Week 10: Sigma_1 completeness and other topics
Learning outcomes
By the end of the module, students should be able to:
- demonstrate knowledge of Gödel’s First and Second incompleteness Theorems and related technical results and definitions (arithmetic representability, proof predicates, self-referential statements, decidable and undecidable theories)
- understand the significance these concepts and results have for logic and mathematics
Indicative reading list
Our primary text will be a version of the Open Logic text customised for PH340.
The same material is also covered in a number of other sources including:
Computability and Logic, 5th ed. by George Boolos, John Burgess, and Richard Jeffrey, Cambridge University Press, 2007
Subject specific skills
write precise mathematical proofs
Transferable skills
use and define concepts with precision, both within formal and discursive contexts
Study time
| Type | Required |
|---|---|
| Lectures | 9 sessions of 3 hours (18%) |
| Seminars | 9 sessions of 1 hour (6%) |
| Private study | 114 hours (76%) |
| Total | 150 hours |
Private study description
Private study and preparation for classes.
Costs
No further costs have been identified for this module.
You must pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
Assessment group B2
| Weighting | Study time | |
|---|---|---|
| In-person Examination | 100% | |
|
||
Feedback on assessment
Discussion and feedback on exercises during seminar.
Pre-requisites
Students are advised to take the module PH210 Logic II: Metatheory before taking the module. This module can be taken in the same academic year as PH210.
Courses
This module is Core optional for:
-
UMAA-GV17 Undergraduate Mathematics and Philosophy
- Year 2 of GV17 Mathematics and Philosophy
- Year 2 of GV17 Mathematics and Philosophy
- Year 2 of GV17 Mathematics and Philosophy
- Year 3 of GV17 Mathematics and Philosophy
- Year 3 of GV17 Mathematics and Philosophy
- Year 3 of GV17 Mathematics and Philosophy
-
UMAA-GV18 Undergraduate Mathematics and Philosophy with Intercalated Year
- Year 2 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 2 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 3 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 3 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 4 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 4 of GV18 Mathematics and Philosophy with Intercalated Year
This module is Optional for:
-
UPHA-VL78 BA in Philosophy with Psychology
- Year 2 of VL78 Philosophy with Psychology
- Year 3 of VL78 Philosophy with Psychology
-
UCSA-G500 Undergraduate Computer Science
- Year 2 of G500 Computer Science
- Year 2 of G500 Computer Science
- Year 3 of G500 Computer Science
- Year 3 of G500 Computer Science
-
UCSA-G503 Undergraduate Computer Science MEng
- Year 2 of G500 Computer Science
- Year 3 of G500 Computer Science
-
UMAA-G100 Undergraduate Mathematics (BSc)
- Year 2 of G100 Mathematics
- Year 2 of G100 Mathematics
- Year 2 of G100 Mathematics
- Year 3 of G100 Mathematics
- Year 3 of G100 Mathematics
- Year 3 of G100 Mathematics
-
UMAA-G103 Undergraduate Mathematics (MMath)
- Year 2 of G100 Mathematics
- Year 2 of G103 Mathematics (MMath)
- Year 2 of G103 Mathematics (MMath)
- Year 3 of G100 Mathematics
- Year 3 of G103 Mathematics (MMath)
- Year 3 of G103 Mathematics (MMath)
- Year 4 of G103 Mathematics (MMath)
- Year 4 of G103 Mathematics (MMath)
-
UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
- Year 3 of GV19 Mathematics and Philosophy with Specialism in Logic and Foundations
- Year 4 of GV19 Mathematics and Philosophy with Specialism in Logic and Foundations
-
UPHA-V700 Undergraduate Philosophy
- Year 2 of V700 Philosophy
- Year 2 of V700 Philosophy
- Year 3 of V700 Philosophy
- Year 3 of V700 Philosophy
-
UPHA-V7ML Undergraduate Philosophy, Politics and Economics
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)