PH34015 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 elementary computability theory.
Module aims
To expose students to Gödel's First and Second Incompleteness Theorems and their significance for the foundations of mathematics. Related material about formal arithmetic and elementary computability theory will also be developed.
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: review of firstorder logic, the language of arithmetic, the standard model
Week 2: crash course in computability, representing numerical properties
Week 3: formal arithmetic theories
Week 4: primitive recursive functions and relations
Week 5: arithmetization of syntax, Gödel numbering
Week 7: the first incompleteness theorem
Week 8: the diagonal lemma, generalizations of the first theorem
Week 9: the second incompleteness theorem, the derivability conditions, Löb's theorem
Week 10: nonstandard models of PA, provability logic
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, selfreferential 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 do not need to pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
Assessment group B
Weighting  Study time  

Oncampus Examination  100%  

Feedback on assessment
Discussion and feedback on exercises during seminar.
Prerequisites
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:
 Year 3 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Optional for:
 Year 2 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

UPHAV700 Undergraduate Philosophy
 Year 2 of V700 Philosophy
 Year 3 of V700 Philosophy
 Year 4 of UPHAV701 Undergraduate Philosophy (wiith Intercalated year)
 Year 4 of UPHAV702 Undergraduate Philosophy (with Work Placement)

UPHAVQ72 Undergraduate Philosophy and Literature
 Year 2 of VQ72 Philosophy and Literature
 Year 3 of VQ72 Philosophy and Literature
This module is Core option list A for:
 Year 3 of UMAAGV17 Undergraduate Mathematics and Philosophy
 Year 3 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Core option list B for:
 Year 2 of UMAAGV17 Undergraduate Mathematics and Philosophy

UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
 Year 2 of GV19 Mathematics and Philosophy with Specialism in Logic and Foundations
 Year 4 of GV19 Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Core option list C for:
 Year 4 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Option list A for:

UPHAVL78 BA in Philosophy with Psychology
 Year 2 of VL78 Philosophy with Psychology
 Year 3 of VL78 Philosophy with Psychology
 Year 3 of UMAAGV17 Undergraduate Mathematics and Philosophy

UMAAGV19 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
 Year 2 of UPHAV7Q8 Undergraduate Philosophy with Classical Civilisation
This module is Option list B for:
 Year 2 of UHIAV1V5 Undergraduate History and Philosophy

UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)
 Year 2 of G105 Mathematics (MMath) with Intercalated Year
 Year 3 of G105 Mathematics (MMath) with Intercalated Year
 Year 5 of G105 Mathematics (MMath) with Intercalated Year

UMAAG100 Undergraduate Mathematics (BSc)
 Year 2 of G100 Mathematics
 Year 3 of G100 Mathematics

UMAAG103 Undergraduate Mathematics (MMath)
 Year 2 of G103 Mathematics (MMath)
 Year 3 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)

UMAAG106 Undergraduate Mathematics (MMath) with Study in Europe
 Year 2 of G106 Mathematics (MMath) with Study in Europe
 Year 3 of G106 Mathematics (MMath) with Study in Europe
 Year 4 of G106 Mathematics (MMath) with Study in Europe
 Year 2 of UMAAG1NC Undergraduate Mathematics and Business Studies
 Year 2 of UMAAGL11 Undergraduate Mathematics and Economics
 Year 2 of UECAGL12 Undergraduate Mathematics and Economics (with Intercalated Year)
 Year 2 of UMAAGV17 Undergraduate Mathematics and Philosophy
 Year 2 of UMAAGV18 Undergraduate Mathematics and Philosophy with Intercalated Year

UMAAG101 Undergraduate Mathematics with Intercalated Year
 Year 2 of G101 Mathematics with Intercalated Year
 Year 4 of G101 Mathematics with Intercalated Year

UPHAVQ72 Undergraduate Philosophy and Literature
 Year 2 of VQ72 Philosophy and Literature
 Year 3 of VQ72 Philosophy and Literature