Teaching‎ > ‎

Gödel's Incompleteness Theorems

Practical information

You can find the take-home exam here. Please submit your answers by email.

Thursdays, from 2pm to 4pm (s.t., includes practice sessions)
Office hours by appointment, in room 234, Ludwigstrasse 31, second floor

You can find the book here.
Here's a cool video. Very instructive! (Credits to Nico González Albornoz)


Course description

    The course consists in a detailed exposition of Gödel's first incompleteness theorem and its proof. The result establishes 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.  
    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 a modern version of Gödel's proof, followed by a reflection on the philosophical consequences of the incompleteness result. Students are introduced to Q's Sigma1-completeness, Gödel's coding technique and the arithmetisation of syntax, the diagonalisation lemmata, and Gödel sentences. 


Course material

Contents (preliminary)

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

2. Functions and Enumerations
19/4
Read: Smith's (2013), Chapter 2.
Exercises: about functions and enumerability (except exercise 5).

3. Effective Computability and Axiomatic Theories: Axiomatisability and Decidability
26/4
Read: Smith's (2013), Chapters 3 and 4.
Exercises: about effective computability (except exercise 5) and formal theories.

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

5. Subsystems of First-order Peano Arithmetic PA
17/5 - 7/6
Read: Smith's (2013), Chapters 9, 10, 11, 12, and 13.
Exercise: read and prepare a summary of chapters 6, 7, and 8 to briefly explain their content in class (note that there are two bank holidays). 
Exercises: about sufficiently expressive/strong theories, induction, and Robinson ArithmeticAlso, try to prove that BA captures the identity relation, that it is negation-complete, and principles O1-O9 from sec. 11.3 (this homework was given in class). Bonus: evaluate whether Q proves this formula.
Exercises: prove Theorems 11.6, 12.1, and 12.3. 

6. Primitive Recursive Functions
14/6 - 21/6
Read: Smith's (2013), Chapter 14.
Exercises: complete the proof of claims A-E in sec. 14.7, and (iv) examples 1-6 in sec. 14.8.

7. Capturing Primitive Recursive Functions
25/6
Read: Smith (2013), Chapters 15-17.

8. The Arithmetization of Syntax
28/6 - 5/7
Read: Smith (2013), Chapters 19 and 20.

9. Gödel's First Incompleteness Theorem
12/7
Read: Smith (2013), Chapters 21-24.


Preparing for the course
  • 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
  • A more formal introduction can be found here: Frazén's Gödel’s Theorem: An Incomplete Guide to its Use and Abuse
  • Here's a funny video (those versed in German turn the sound off)

Bibliography
  • Boolos, G., Burgess, J. & Jeffrey, R. (2007) Computability and Logic, Cambridge University Press, fifth edition.
  • Franzén, T. (2005) Gödel’s Theorem: An Incomplete Guide to its Use and AbuseA. K. Peters.

  • 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. (2013) An Introduction to Gödel's Theorems, second edition, Cambridge University Press.
Comments