Class Schedule (tentative):
Chapters are from Hinman's text. Supplementary material will be
indicated throughout the term.
Tues Feb 2: First class: Introduction to 4 main
topics; survey of applications
Thurs Feb 4:
Firstorder logic: syntax and semantics (Ch. 2.1, 2.2)
Tues Feb 9:
Firstorder logic: models and theories (Ch. 2.3, 2.4)
Thurs Feb 11:
Examples of theories; complete theories (Ch. 2.4)
Tues Feb 16: No class (Monday schedule, following Presidents Day)
Thurs Feb 18:
Back and forth constructions (Ch. 2.4);
compactness and completeness theorems (Ch. 3.1, 3.2);
Tues Feb 23:
EhrenfeuchtFraïssé games (Ch. 7.1);
applications of compactness (Ch. 3.5);
Ramsey's theorem (Suppl.)
(PSet 1 due)
Thurs Feb 25:
Zeroone laws;
Ax's theorem
(Suppl.)
Tues Mar 2:
Proof of compactness theorem (Ch. 3.2)
Thurs Mar 4:
Finish proof of compactness (Ch. 3.2); Primitive recursive functions (Ch. 4.2)
Tues Mar 9:
Partial computable functions (Ch. 4.2)
Thurs Mar 11:
Computably enumerable sets (Ch. 4.3, 5.4);
Manyone degrees (Ch. 8.1, 8.2)
Tues Mar 16:
Recursion theorem, Rice's theorem (Ch. 8.1)
Thurs Mar 18:
Turing degrees (Ch. 8.1, 8.2)
Tues Mar 23: No class (Spring Break)
Thurs Mar 25: No class (Spring Break)
Tues Mar 30:
Arithmetical Hierarchy (Ch. 5.1, 8.3)
Thurs Apr 1:
KleenePost and Ladner's theorems (Ch. 8.2, Suppl.);
FriedbergMuchnik theorem (Ch 8.2)
(PSet 2 due)
Tues Apr 6:
FriedbergMuchnik theorem cont'd (Ch 8.2);
Arithmetic and undecidability (Ch 2.5, 4.1)
Thurs Apr 8:
Gödel's first incompleteness theorem and Tarski's undefinability of truth (Ch. 4.1, 4.4)
Tues Apr 13:
Löb's theorem and Gödel's 2nd incompleteness theorem (Ch 5.3, Suppl.);
Turing, Church, and the Entscheidungsproblem (Ch. 5.2)
Hilbert's 10th problem (Ch. 5.1, Suppl.)
Thurs Apr 15:
Gödel's first incompleteness theorem cont'd (Ch. 4.5, 4.6)
(PSet 3 due);
(Topic approval due)
Tues Apr 20: No class (Patriots Day)
Thurs Apr 22:
Gödel's first incompleteness theorem completed (Ch. 4.5, 4.6);
SchröderBernstein theorem (Ch. 6.4)
Tues Apr 27:
Myhill's Isomorphism theorem, and the Isomorphism Conjecture (Suppl.);
ZermeloFraenkel Set Theory (Ch. 6.1)
Thurs Apr 29:
student presentation: Geneson
More ZermeloFraenkel Set Theory (Ch. 6.1, 6.2, 6.3)
(PSet 4 due)
Tues May 4:
student presentation: Chandrasekaran
Gödel's incompleteness via Kolmogorov complexity (Suppl.);
Σ_{1}soundness of PA_{ω} (Suppl.);
Thurs May 6:
student presentations: Bapat, Karaman
More ZermeloFraenkel Set Theory (Ch. 6.1, 6.2, 6.3)
Tues May 11:
student presentations: Clausen, Yanovich
Thurs May 13:
Last class:
student presentations: Nachlas, Oshman
(Written reports due)
