Logic III: Incompleteness & Undecidability (PH340-15)

Timing & CATS

This module will be taught in the Spring Term of 2017-18 and is worth 15 CATS.

Module Description

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.

Learning Outcomes or Aims

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.

Contact Time

In this module students must attend 3 hours of lectures and 1 hour of seminars per week.

Lectures for 2017-18

Tuesday 11am to 1pm in R1.04 (Lecture)

Wednesday 12pm to 1pm in B2.02 (Soc Sci) (Lecture)

Wednesday 1pm to 2pm in S0.09 (Seminar)

Seminars for 2017-18

Seminars for this course start in week 2

There will be no seminars in reading week (week 6)

ASSESSMENT METHODS

This module is formally assessed in the following way:

• 15% assessed and 85% examined (2 hour exam)

The assessed component consists in fortnightly exercise sets, which are to be handed in directly to the module leader at the relevant lectures. Please find the schedule of deadlines for exercise sets on the relevant Moodle page. Marked exercise sets will also be returned to students at lectures.