PH340-15 Logic III: Incompleteness & Undecidability

Department: Philosophy
Level: Undergraduate Level 3
Module leader: Benedict Eastaugh
Credit value: 15
Module duration: 10 weeks
Assessment: 100% exam
Study location: University of Warwick main campus, Coventry

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 first-order 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: non-standard 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, 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 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
In-person Examination	100%
Answerbook Pink (12 page)

Feedback on assessment

Discussion and feedback on exercises during seminar.

Past exam papers for PH340

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:

Year 3 of UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Optional for:

Year 2 of UMAA-GV19 Undergraduate 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
Year 4 of UPHA-V701 Undergraduate Philosophy (wiith Intercalated year)
Year 4 of UPHA-V702 Undergraduate Philosophy (with Work Placement)
UPHA-VQ72 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:

UMAA-GV17 Undergraduate Mathematics and Philosophy
- Year 3 of GV17 Mathematics and Philosophy
- Year 3 of GV17 Mathematics and Philosophy
- Year 3 of GV17 Mathematics and Philosophy
Year 3 of UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Core option list B 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
UMAA-GV19 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 UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Option list A for:

UPHA-VL78 BA in Philosophy with Psychology
- Year 2 of VL78 Philosophy with Psychology
- Year 3 of VL78 Philosophy with Psychology
UMAA-GV17 Undergraduate 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-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

This module is Option list B for:

Year 2 of UHIA-V1V5 Undergraduate History and Philosophy
UMAA-G105 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
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-G106 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 UMAA-G1NC Undergraduate Mathematics and Business Studies
Year 2 of UMAA-GL11 Undergraduate Mathematics and Economics
Year 2 of UECA-GL12 Undergraduate Mathematics and Economics (with Intercalated Year)
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
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
UMAA-G101 Undergraduate Mathematics with Intercalated Year
- Year 2 of G101 Mathematics with Intercalated Year
- Year 4 of G101 Mathematics with Intercalated Year
UPHA-VQ72 Undergraduate Philosophy and Literature
- Year 2 of VQ72 Philosophy and Literature
- Year 3 of VQ72 Philosophy and Literature