In the first half of the course we treat elementary topics from computability theory including Turing machines, recursive functions, arithmetization, Kleene's normal form theorem, the recursion theorem, simple sets, and the arithmetical hierarchy. Here we follow the syllabus (see below).
In the second half we treat elementary topics from proof theory. Basing our treatment mainly on Gentzen style proof systems, we will treat Gödels completeness and incompleteness theorems, cut-elimination, Herbrand's theorem, and provable and unprovable instances of transfinite induction. For this part we will use various book chapters and handouts.
Exercises for part 2 of the course (in postscript).
Course notes for part 2 of the course (in postscript).
There are 12 meetings. We meet every week on Thursday from 10 (sharp) till 13. (Two hours of lecturing and one exercise hour.) Place: Math building at the Uithof, room 611b. Start: September 21. End: December 14. There are no classes during week 45 (November 9). The exam will take place on Thursday February 1, from 10:00 - 13:00, room t.b.a.
The topics for the exam are the following.
For the first part of the course:
Chapters 1 - 4 of the syllabus, except section 3.4.
For the second part of the course:
From the syllabus section 7.1.
Buss: 1.2.1 - 1.2.9,
2.1.1 - 2.1.4,
2.3.1 - 2.3.7,
2.5.2,
Handout: preliminaries on ordinals,
Schwichtenberg section 2