# PH340 - Logic III: Incompleteness & Undecidability

• Module code: PH340
• Module name: Logic III: Incompleteness & Undecidability
• Department: Philosophy
• Credit: 15

## Module content and teaching

###### Principal aims

The central topic of this module is a presentation of Gödel's first and second incompleteness theorems, first obtained in 1931. Gödel's theorems are commonly regarded as among the most important results of contemporary logic both because of the light they shed on the notions of truth and provability in mathematics and because of the techniques involved in their proofs. Roughly speaking, the first theorem states that any consistent formal mathematical theory which is capable of expressing basic facts about elementary arithmetic is incomplete in the sense that there are true arithmetical statements which it cannot prove. Again roughly, the second theorem states that any such theory is incapable of proving its own consistency. Although these results apply to a wide variety of axiomatic theories, they are commonly formulated with respect to a particular system known as first-order Peano Arithmetic [PA]. Accordingly, a large part of the module will be spent studying this theory. We will first study the technique known as arithmetization whereby it can be shown that syntactic notions like well-formedness and provability can be expressed using a purely arithmetic language. After proving Gödel's theorems themselves, we will then study the phenomena of self-reference more generally and derive several related results due to Tarski, Rosser and Löb. Time permitting, we will then cover additional material about computability theory, models of PA and the use of modal logic to reason about arithmetic provability.

###### Principal learning outcomes

By the end of the module the student should be able to: 1) demonstrate knowledge of Gödel's First and Second incompleteness Theorem‚ and related technical results and definitions (arithmetic representability, proof predicates, self-referential statements, decidable and undecidable theories); 2) understand the significance these concepts and results have for logic and mathematics; 3) use and define concepts with precision with precision, both within formal and discursive contexts..

###### Timetabled teaching activities

Teaching activites will normally comprise 3 hours of lectures and a one hour seminar per week attended by all students over the course of one term. The module runs in alternate years

###### Other essential notes

Please note that attendance at both lectures and seminars and completion of any unasssessed or required work is a requirement of this module

## Module assessment

Assessment group Assessment name Percentage
15 CATS (Module code: PH340-15)
D1 (Assessed/examined work) Assesed exercises 15%
2 hour examination (Summer) 85%
VA (Visiting students only) 100% assessed (visiting/part year) 100%

## Module availability

This module is available on the following courses:

N/A

###### Optional Core
• Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations (GV19) - Year 2
###### Optional
• Undergraduate Mathematics and Business Studies (with Intercalated Year) (G1N2) - Year 2
• Undergraduate Mathematics and Philosophy (GV17) - Year 2
• Undergraduate Mathematics and Philosophy (GV17) - Year 3
• Undergraduate Mathematics and Philosophy with Intercalated Year (GV18) - Year 2
• Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations (GV19) - Year 2
• Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations (GV19) - Year 3
• Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations (GV19) - Year 4
• Undergraduate Economics, Politics and International Studies (LM1D) - Year 3
• Undergraduate History and Philosophy (V1V5) - Year 2
• Undergraduate Philosophy (V700) - Year 2
• Undergraduate Philosophy (V700) - Year 3
• Undergraduate Philosophy (wiith Intercalated year) (V701) - Year 2
• Undergraduate Philosophy (wiith Intercalated year) (V701) - Year 4
• Undergraduate Philosophy, Politics and Economics (V7ML) - Year 2
• Undergraduate Philosophy, Politics and Economics (V7ML) - Year 3
• Undergraduate Philosophy, Politics and Economics (with Intercalated year) (V7MM) - Year 4
• Undergraduate Philosophy, Politics and Economics (V7MP) - Year 2
• Undergraduate Philosophy, Politics and Economics (V7MP) - Year 3
• Undergraduate Philosophy, Politics and Economics (with Intercalated year) (V7MQ) - Year 4
• Undergraduate Philosophy, Politics and Economics (V7MR) - Year 2
• Undergraduate Philosophy, Politics and Economics (V7MR) - Year 3
• Undergraduate Philosophy, Politics and Economics (V7MR) - Year 4
• Undergraduate Philosophy, Politics and Economics (with Intercalated year) (V7MS) - Year 4
• Undergraduate Philosophy with Classical Civilisation (V7Q8) - Year 2
• Undergraduate Philosophy with Classical Civilisation (V7Q8) - Year 3
• BA in Philosophy with Psychology (VL78) - Year 2
• BA in Philosophy with Psychology (VL78) - Year 3
• BA in Philosophy with Psychology (with Intercalated year) (VL79) - Year 4
• Undergraduate Philosophy and Literature (VQ72) - Year 2
• Undergraduate Philosophy and Literature (VQ72) - Year 3
• Undergraduate Philosophy and Literature with Intercalated Year (VQ73) - Year 2
• Undergraduate Philosophy and Literature with Intercalated Year (VQ73) - Year 4