Teaching‎ > ‎

Gödel's Incompleteness Theorems

Practical information

Thursdays, from 2pm to 4pm
Office hours by appointment, in room 234, Ludwigstrasse 31, second floor

I erased one item in question 3 for being misleading and overly too complicated.

You can find the take-home exam here. The deadline is September 22nd, 2017. Please send me your answers per email. If something is unclear or you are having serious trouble with some of the exercises, drop me an email. The bonus question just counts if you answer it correctly.

You can find the text book here (credits to Marco). 

Here's another cool video. Very instructive! (Credits to Nico González Albornoz)



Lectures

1. Introduction: What Gödel's Theorems Say
27/4
Read: Smith's (2007), Chapter 1.

2. Decidability and Enumerability
27/4 - 4/5
Read: Smith's (2007), Chapter 2.
Exercises: about functions (all of them except 4), effective computability (all of them except exercise 5), and enumerability.

3. Axiomatised formal theories
11/5
Read: Smith's (2007), Chapter 3.
Exercises: about formal theories (in particular, exercises 1 and 4).

4. Expressing and Capturing Numerical Properties
18/5 
Read: Smith's (2007), Chapter 4: Capturing Numerical Properties.
Exercises: about the language of arithmetic.

5. Robinson Arithmetic Q
1/6 - 22/6
Read: Smith's (2007), Chapters 8 and 9.
Exercise
: read and understand chapters 5 and 6 to briefly explain their content in class

6. Robinson Arithmetic Q and Peano Arithmetic PA
29/6
Read: Smith's (2007), Chapter 10.
Exercises: about sufficiently expressive/strong theories and induction. Also, try to prove principles O1-O9 from sec. 9.4.

7. Primitive Recursive Functions
29/6 - 12/7
Read: Smith's (2007), Chapter 11.
Exercises: about Robinson Arithmetic (skip the ones about Baby Arithmetic, BA). Also, try to prove that (i) bounded minimisation and is pr when applied to a pr property, (ii) that definition by cases is pr when using pr functions and relations, (iii) propositions A-E from sec. 11.7, and (iv) propositions R1-R6 from sec. 11.8.

8. Capturing Primitive Recursive Functions
12/7 - 20/7
Read: Smith (2007), Chapters 12 and 13.

9. The Arithmetization of Syntax
20/7
Read: Smith (2007), Chapter 15.

10. Gödel's First Incompleteness Theorem
27/7
Read: Smith (2007), Chapters 16 and 17.


Course description

    The course consists in a detailed exposition of Gödel's first and second incompleteness theorems, and their respective proofs. The first result shows that any theory extending elementary arithmetic is incomplete, this is, there will always be a sentence in the language of the theory that the theory neither proves nor refutes. Gödel's second incompleteness result establishes that no consistent theory extending elementary arithmetic can prove its own consistency. 
    The exposition is carried out in two steps. First, an introduction to first-order arithmetic is given. Students are presented with the following: first-order axiomatic theories, the language of first-order arithmetic, L, first-order theories of arithmetic Q (Robinson Arithmetic) and PA (for "Peano Arithmetic"), the enumerability and denumerability of sets, the recursivity, semi-recursivity, definability in L, and representability in an axiomatic theory formulated in L, of a subset of natural numbers or a function from natural numbers to natural numbers, the standard model of L, arithmetical truth, the arithmetical hierarchy, and (primitive) recursive functions.
    The second half of the course consists of a presentation of modern versions of Gödel's proofs of both incompleteness results, followed by a reflection on their consequences. Students are introduced to Q's Sigma1-completeness, Gödel's coding technique and the arithmetisation of syntax, the diagonalisation lemmata, Gödel sentences, Löb's derivability conditions, and reflection principles. 


Course material
  • Lecture notes
  • Smith's An Introduction to Gödel's Theorems

Preparing for the course
  • Here's an informal introduction to Gödel's Incompleteness Theorems that could be useful to read before the before the course begins: Nagel & Newman's Gödel's Proof
  • Here's a funny video

Bibliography
  • Boolos, G., Burgess, J. & Jeffrey, R. (2007) Computability and Logic, Cambridge University Press, fifth edition.
  • Gödel, K. (1931) "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I" ("On Formally Undecidable Propositions of Principia Mathematica and Related Systems"), Monatshefte für Mathematik und Physik 38: 173–198. Reprinted in Gödel (1986), pp. 144–195.
  • ——(1986) Collected Works. I: Publications 1929–1936, S. Feferman, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort (eds.), Oxford University Press.
  • Nagel, E. & Newman, J. R. (2001) Gödel's Proof, New York University Press, revised edition.
  • Smith, P. (2007) An Introduction to Gödel's Theorems, Cambridge University Press.
Comments