3TP3 "Truth and Provability" Fall 2012

Course times: Tuesdays, Wednesdays and Fridays, 12:30-13:30, HH217

Office hours: HH409, Wednesday 13:20-16:20 or by appointment.

Mailing list: If you're taking this course, please subscribe to the course mailing list, either by sending an email to 3tp32012-join@math.mcmaster.ca, or by using the web interface.

Final exam: Thu 6 Dec 12:30-15:30 HH/102.

Course outline

Information on the writing project

Assignments

Lecture notes

Introductory historical overview (source)

Originals:

• On Formally Undecidable Propositions of Principia Mathematica and Related Systems, by Kurt Gödel (English translation by B. Meltzer)
• Assorted works by Maurits Cornelis Escher
• A Musical Offering by Johann Sebastian Bach

Other relevant links:

• Godel Without (too many) Tears by Peter Smith.
• Foundations of Mathematics, lecture notes by Stephen Simpson.
• The Stanford Encyclopedia of Philosophy's entry on Hilbert's Programme.
• The Kurt Gödel Society website.
• Kurt Gödel's biography at the MacTutor History of Mathematics archive at St. Andrews University.
• A nice short article on quines: "It's Zip-files All The Way Down!".
• Latest success story of formalised mathematics: a formally checked version of the Feit-Thompson (a key component of the classification of finite simple groups).
• Turing completeness in surprising places (note that I haven't checked the veracity of the claims of the following pages, although Turing completeness of Conway's Game of Life is widely accepted)
  • A universal register machine in the cellular automaton Conway's Game of Life
  • Turing machines in the card game Magic: The Gathering.