|Announcements |||Course information |||Important dates |||Assignments and tests |||Lecture notes|
29/08/2011 The first lecture is as scheduled, at 15:30 on Thursday, September 8th. Please email me if you would like to take this course, but have a scheduling conflict!
Lectures: 3:30-5pm Tuesdays and Thursdays in EN-1002
No textbook is required for the course. I will be posting lecture notes; you can check out the lecture notes for a similar course at the University of Toronto.
Description: What is solvable? What is provable? And what do we mean by being solvable and provable? These are fundamental philosophical questions, with a practical importance to match. In this course, we will study classical unprovability resuts such as Goedel Incompleteness Theorem, and relate them to unsolvability results such as the Halting problem undecidability. More specifically, we will cover general computability (recursive and primitiverecursive functions, undecidability, etc), propositional and predicate logic, theories of arithmetic with the emphasis on Peano arithmetic, and many beautiful theorems: Goedel completeness and incompleteness theorems, compactness theorem, Lowenheim-Skolem theorem, Paris-Harrington theorem about unprovability of a natural combinatorial statement in Peano arithmetic... Time permitting, we will also look at some modern proof complexity and bounded arithmetic.