Also on reserve are Mathematical Logic by Ebbinghaus, Flum, and Thomas, and A Concise Introduction to Mathematical Logic by Rautenberg, which you may find helpful as references, especially near the beginning of the term.

Additional supplemental references will be provided throughout the course.

The main topics are

• First-order Logic and Model Theory;
• Computability Theory and Complexity Theory;
• Incompleteness and Undecidability; and
• Set Theory.

Additional topics include

• applications of model theory to graph theory (Ramsey's theorem; zero-one laws), algebraic geometry (Ax's theorem; Nullstellensatz), and real algebraic geometry (Artin-Schreier; Hilbert's 17th problem);
• the computational complexity of decision procedures (Fischer-Rabin);
• results in computability theory and set theory that have analogues in complexity theory (Kleene-Post and Ladner's theorems; Schröder-Bernstein theorem, Myhill's Isomorphism theorem, and the Isomorphism Conjecture); and
• how certain incompleteness results can be viewed as informal paradoxes that were turned into mathematical theorems (Santa Claus paradox and Löb's theorem; Berry paradox and Gödel's incompleteness via Kolmogorov complexity; Yablo's paradox and Σ₁-soundness of PA_ω).

Homework:

Problems marked with a * are ones that either introduce important concepts not covered elsewhere in the text, or that I consider particularly interesting or significant. I strongly recommend that you look carefully at each such problem, and at least attempt a solution.

Problems are Exercises from Hinman's text, unless otherwise indicated.

PSet 1 (Due Tues Feb 23): Do 4/6: 2.3.64, 2.3.71, *2.3.81, *2.4.56, 3.1.23, 3.2.28.

PSet 2 (Due Thurs Apr 1): Do 5/8: *3.5.56, 3.5.57, 4.3.27.iii, 4.3.28, *5.1.32, *8.1.36, *8.1.42.i, and:

(de Bruijn-Erdős, 1951) If every finite subgraph of an infinite graph G can be k-colored, then G can be k-colored.

PSet 3 (Due Thurs Apr 15): Do 3/5: 4.4.23, 8.2.26, *8.2.27.i, 4.6.41, 4.6.42

PSet 4 (Due Thurs Apr 29): Do 4/7: 4.6.39, 4.6.45, 4.6.47, *5.3.7, 6.2.54.i,.iv, 6.3.32, *6.4.47

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: First-order logic: syntax and semantics (Ch. 2.1, 2.2)

Tues Feb 9: First-order 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: Ehrenfeucht-Fraïssé games (Ch. 7.1); applications of compactness (Ch. 3.5); Ramsey's theorem (Suppl.) (PSet 1 due)

Thurs Feb 25: Zero-one 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); Many-one 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: Kleene-Post and Ladner's theorems (Ch. 8.2, Suppl.); Friedberg-Muchnik theorem (Ch 8.2) (PSet 2 due)

Tues Apr 6: Friedberg-Muchnik 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öder-Bernstein theorem (Ch. 6.4)

Tues Apr 27: Myhill's Isomorphism theorem, and the Isomorphism Conjecture (Suppl.);
Zermelo-Fraenkel Set Theory (Ch. 6.1)

Thurs Apr 29: student presentation: Geneson
More Zermelo-Fraenkel 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.); Σ₁-soundness of PA_ω (Suppl.);

Thurs May 6: student presentations: Bapat, Karaman
More Zermelo-Fraenkel 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)