# PH340: Logic III Incompleteness & undecidabilty

##### Term 2 2015-2016, 15 CATS

Module tutor: Walter Dean (W dot H dot Dean at warwick dot ac dot uk)

Logicistics:

• Lecture 1: Tuesday 11:00-13:00 F1.11
• Lecture 2: Wednesday 12:00-13:00 S0.13
• Seminar: Wednesday 13:00-14:00 S2.04/5 (Science Concourse)
• Office hours: Monday 14:00-15:00

The first lecture will take on 12 January. Seminars will start in week 2 of term 2.

Related Module:

#### Problem sets

##### Description:

The focus of this module are the Incompleteness Theorems of Kurt Gödel, first obtained in 1931. The First Incompleteness Theorem states roughly that any consistent formal mathematical theory capable of expressing basic facts about arithmetic is incomplete in the sense that there are true arithmetical statements which it cannot prove. Again roughly, the Second Incompleteness Theorem states that any such theory is incapable of proving its own consistency. These results are often regarded as among the most important results in mathematical logic both because of the light they shed on the relationship between truth and provability in mathematics and also because of the techniques involved in their proofs.

Although the incompleteness theorems apply to a wide range of axiomatic theories, they are commonly formulated with respect to a particular system known as first-order Peano Arithmetic [PA]. Part of the module will accordingly be spent studying this and related arithmetical theories. We will first study the technique known as arithmetization whereby it is shown that syntactic notions like well-formedness and provability can be expressed within a purely arithmetical language. After proving Gödel’s theorems themselves, we will then study the phenomena of self-reference more generally and obtain several other limitative results due to Church, Rosser, Tarski, and Löb. Time permitting, we will then cover additional material about the model theory of arithmetic, reflection principles, and the use of modal logic to reason about provability as a sentential operator.