Skip to main content Skip to navigation

Module Catalogue

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

Download as PDF

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 Eligible for self-certification
In-person Examination 100% No
  • 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:

  • UPHA-L1CA Undergraduate Economics, Psychology and Philosophy
    • Year 2 of L1CA Economics, Psychology and Philosophy
    • Year 2 of L1CC Economics, Psychology and Philosophy (Behavioural Economics Pathway)
    • Year 2 of L1CD Economics, Psychology and Philosophy (Economics with Philosophy Pathway)
    • Year 2 of L1CE Economics, Psychology and Philosophy (Philosophy and Psychology Pathway)
    • Year 3 of L1CA Economics, Psychology and Philosophy
    • Year 3 of L1CC Economics, Psychology and Philosophy (Behavioural Economics Pathway)
    • Year 3 of L1CD Economics, Psychology and Philosophy (Economics with Philosophy Pathway)
    • Year 3 of L1CE Economics, Psychology and Philosophy (Philosophy and Psychology Pathway)
  • UPHA-L1CB Undergraduate Economics, Psychology and Philosophy (with Intercalated Year)
    • Year 4 of L1CG Economics, Psychology and Philosophy (Behavioural Economics Pathway) (with Intercalated Year)
    • Year 4 of L1CH Economics, Psychology and Philosophy (Economics with Philosophy Pathway) (with Intercalated Year)
    • Year 4 of L1CJ Economics, Psychology and Philosophy (Philosophy and Psychology Pathway) (with Intercalated Year)
    • Year 4 of L1CB Economics, Psychology and Philosophy (with Intercalated Year)
  • 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 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
  • Year 4 of UPHA-VL80 Undergraduate Philosophy with Psychology (with Work Placement)
  • UPHA-V7ML Undergraduate Philosophy, Politics and Economics
    • Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
    • Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
  • UPHA-V7MW Undergraduate Politics, Philosophy and Law
    • Year 2 of V7MW Politics, Philosophy and Law
    • Year 3 of V7MW Politics, Philosophy and Law
  • Year 4 of UPHA-V7MX Undergraduate Politics, Philosophy and Law (with Intercalated Year)

This module is Unusual option for:

  • UPHA-L1CA Undergraduate Economics, Psychology and Philosophy
    • Year 2 of L1CA Economics, Psychology and Philosophy
    • Year 2 of L1CC Economics, Psychology and Philosophy (Behavioural Economics Pathway)
    • Year 3 of L1CA Economics, Psychology and Philosophy
  • UPHA-V7ML Undergraduate Philosophy, Politics and Economics
    • Year 2 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
    • Year 2 of V7MP Philosophy, Politics and Economics (Bipartite)
    • Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
    • Year 3 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
    • Year 3 of V7MP Philosophy, Politics and Economics (Bipartite)
  • UPHA-V7MM Undergraduate Philosophy, Politics and Economics (with Intercalated year)
    • Year 4 of V7MS Philosophy, Politics and Economics (Bipartite with Economics Major) (with Intercalated Year)
    • Year 4 of V7MQ Philosophy, Politics and Economics (Bipartite) with Intercalated Year
    • Year 4 of V7MM Philosophy, Politics and Economics (Tripartite) (with Intercalated year)
  • UPHA-V7MW Undergraduate Politics, Philosophy and Law
    • Year 2 of V7MW Politics, Philosophy and Law
    • Year 3 of V7MW Politics, Philosophy and Law
  • Year 4 of UPHA-V7MX Undergraduate Politics, Philosophy and Law (with Intercalated Year)

This module is Core option list A for:

  • Year 3 of UMAA-GV17 Undergraduate 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:

  • Year 2 of UMAA-GV17 Undergraduate 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 Core option list F for:

  • Year 4 of UMAA-GV18 Undergraduate Mathematics and Philosophy with Intercalated Year

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
  • Year 3 of UMAA-GV17 Undergraduate 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
  • Year 5 of UMAA-G105 Undergraduate Master of Mathematics (with Intercalated Year)
  • Year 3 of UMAA-G100 Undergraduate Mathematics (BSc)
  • UMAA-G103 Undergraduate Mathematics (MMath)
    • Year 3 of G100 Mathematics
    • Year 3 of G103 Mathematics (MMath)
    • Year 4 of G103 Mathematics (MMath)
  • Year 4 of UMAA-G107 Undergraduate Mathematics (MMath) with Study Abroad
  • Year 3 of UMAA-G106 Undergraduate Mathematics (MMath) with Study in Europe
  • Year 2 of UMAA-GV17 Undergraduate Mathematics and Philosophy
  • Year 2 of UMAA-GV18 Undergraduate Mathematics and Philosophy with Intercalated Year
  • Year 4 of UMAA-G101 Undergraduate Mathematics with Intercalated Year
  • UPHA-VQ72 Undergraduate Philosophy and Literature
    • Year 2 of VQ72 Philosophy and Literature
    • Year 3 of VQ72 Philosophy and Literature
  • Year 2 of UPHA-VQ52 Undergraduate Philosophy, Literature and Classics
  • Year 2 of UPHA-V7ML Undergraduate Philosophy, Politics and Economics

This module is Option list C for:

  • UPHA-V7ML Undergraduate Philosophy, Politics and Economics
    • Year 3 of V7MP Philosophy, Politics and Economics (Bipartite)
    • Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
  • UPHA-V7MM Undergraduate Philosophy, Politics and Economics (with Intercalated year)
    • Year 4 of V7MS Philosophy, Politics and Economics (Bipartite with Economics Major) (with Intercalated Year)
    • Year 4 of V7MQ Philosophy, Politics and Economics (Bipartite) with Intercalated Year
    • Year 4 of V7MM Philosophy, Politics and Economics (Tripartite) (with Intercalated year)

This module is Option list D for:

  • UHIA-V1V5 Undergraduate History and Philosophy
    • Year 2 of V1V5 History and Philosophy
    • Year 3 of V1V5 History and Philosophy
  • Year 4 of UHIA-V1V8 Undergraduate History and Philosophy (with Year Abroad and a term in Venice)
  • Year 4 of UHIA-V1V6 Undergraduate History and Philosophy (with Year Abroad)
  • UHIA-V1V7 Undergraduate History and Philosophy (with a term in Venice)
    • Year 2 of V1V7 History and Philosophy (with a term in Venice)
    • Year 3 of V1V7 History and Philosophy (with a term in Venice)
  • UPHA-V7ML Undergraduate Philosophy, Politics and Economics
    • Year 2 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
    • Year 3 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)