Home Page for Math 3TP3

Truth and Provability: An Introduction to the Goedel Incompleteness Theorem

2014-15


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.

Textbook

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

Announcements

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

Instructor

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.

Assessment

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

Calendar

subject to revisions throughout the semester
Dates
 Reading assignment
 Topic Homework/comments
Week 0 Sept 4-5
Introduction
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