Home Page for Math 3TP3

Truth and Provability: An Introduction to the Goedel Incompleteness Theorem


Course Content

The goal of the course is to understand the statement and proof of the Goedel incompleteness theorem. We will discuss the difference between truth in a formal system and provability in a formal system. Along the way, we will appreciate both the strength and the limitations of first-order logic and Peano Arithmetic.


Required: Peter Smith "An introduction to Goedel's Theorems", 2nd edition, Cambridge University Press
website: Peter Smith's logic matters website

Other recommended reading: Douglas Hofstadter "Goedel, Escher, Bach: an Eternal Golden Braid", Basic Books
Raymond Smullyan, "Goedel's incompleteness theorems", Oxford University Press


23 November 2014 Here is a nice article by Bjorn Poonen talking about undecidable problems http://www-math.mit.edu/~poonen/papers/sampler.pdf
I suggest you read sections 1, 2, 3, 4, 6, 8.

12 November 2014 Website explaining Goodstein sequences and the Kirby-Paris theorem: blog.kleinproject.org/?p=674
Reference for photocopy handed out today: John Dawson "Logical Dilemmas: the life and work of Kurt Goedel", AK Peters

6 November 2014 Schedule and reading assignment modified on the calendar below.

3 November 2014 Office hours this Tuesday, Nov 4, are cancelled.

9 October 2014: For a light read on the subject of the logical truth and the foundations of mathematics, you might want to check out "Logicomix: An epic search for truth" by Apostolos Doxiadis.  It is a graphic novel by Christos Papadimitriou, a logican and computer scientist at UC Berkeley.

24 Sept 2014: A small revision to Homework 2 is posted below.

                Chris created a document with the rules for Wff n Proof; it is here.

Other websites

Methods of proof

Course outline


Dr Deirdre Haskell, HH316, ext 27244, haskell@math.mcmaster.ca
       Office hours T 10:30--12:00, Th 10:30-11:30 or by appointment

Course Structure

Three lectures per week. Hopefully, a lot of this time will be spent discussing (and maybe playing the odd game), although I will also lecture when it seems appropriate. There will be six homework assignments, due every other week (dates on the calendar below). There will be a reading assignment every week. To encourage you to do the reading, you are required to send me a comment or question that you would like answered in class by Tuesday morning of each week. There will be one final exam.


10 % Class participation (send questions, answer questions, contribute to discussion )
40 % Homework assignments (posted on calendar below)
50 % Final exam


subject to revisions throughout the semester
Reading assignment
Topic Homework/comments
Week 0 Sept 4-5

Week 1 Sept 8-12
chapters 1-4 for Tuesday, Sept 9 effective computability, formal languages, Wff 'n' Proof
Week 2 Sept 15-19
chapters 4-5 for Tuesday, Sept 16 formal theories, negation completeness, capturing/expressing numerical properties
Homework 1 due Friday Sept 19
Homework 1 Solutions
Week 3 Sept 22-26
read again Ch. 5
chapter 6 (7-8) for Tuesday, Sept 23
sufficiently expressive, a first incompleteness theorem

Week 4 Sept 29 - Oct 3
chapters 7-8-9-10 for Tuesday, Sept 30
induction, baby arithmetic, Q
Homework 2 due Friday Oct 3
tex file for homework 2
Homework 2 solutions
Week 5 Oct 6-10
chapters 11-12 for Tuesday, Oct 7
bounded quantifiers, limited induction

Week 6 Oct 13-17
chapters 13-14 for Tuesday, Oct 14
Peano Arithmetic, primitive recursion
Thanksgiving Monday Oct 13
Homework 3 due Friday Oct 17
tex file for homework 3
Week 7 Oct 20-24
chapters 15-16 for Tuesday, Oct 21
expressing primitive recursive functions

Week 8 Oct 27-31
chapters 17, 19 for Tuesday, Oct 7 Q captures primitive recursive; godel numbering
Midterm recess Oct 30, 31
Homework 4 due Tuesday Nov 4 (but recommended for Oct 29)
tex file for homework 4
Week 9 Nov 3-7
chapters 20-21 for Tuesday, Nov 4
more on coding; incompleteness of Peano Arithmetic and the Goedel theorem!

Week 10 Nov 10-14
chapters 22-24 for Tuesday, Nov 11 read chs 22, 23, 30, browse for interesting topics
Goedel's theorem, diagonalisation
Goodstein's theorem is true but not provable
Homework 5 due Friday Nov 14
tex file for homework 5
Week 11 Nov 17-21
chapter 25 for Tuesday, Nov 18 read chs 30, 41 and 44
Rosser's theorem
Turing machines and Turing computability, mu-computability and equivalence with Turing computability

Week 12 Nov 24-28
chapter 31 for Tuesday, Nov 25 read ch 38, 42 examples of undecidable problems
Homework 6 due Wednesday Dec 3
tex file for homework 6
Week 13 Dec 2-3

Julia Robinson movie