## 18.515: Mathematical Logic (Spring 2010)

Meetings Tues. & Thurs. 2:30-4:00 in 2-142 Cameron Freer 2-308 Tues. & Thurs. 1:30-2:30, and by appointment The main course text is Peter Hinman's Fundamentals of Mathematical Logic, available in the Coop and on reserve. It is not strictly required, though it is recommended, and covers a large portion of the course material. 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. This course will provide a graduate-level introduction to mathematical logic, with a strong focus on several mathematical applications. No prior knowledge of mathematical logic is assumed, but some mathematical sophistication and knowledge of abstract algebra will be helpful. 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 Σ1-soundness of PAω). There will be four problems sets (see below), worth (in total) 2/3 of the grade (i.e., 1/6 each). The remaining 1/3 will be determined by a 5-10 page written report (2/9) and 30 minute class presentation (1/9) on an additional topic of your choice. As the course progresses, please consider which topic you'd like to investigate further (it could be some mathematical application or a basic theorem we won't cover), and meet with me (by April 8) to discuss it and for advice on helpful sources. Presentations will occur the during the final 5 classes; the report will be due on May 13.

### Homework:

You should hand in solutions to most of the problems, though you are not required to work on every single one. You are encouraged to work together on solving them (if you'd like), though please write up the solutions yourself and indicate the collaborators.

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.); Σ1-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)