## 18.515: Mathematical Logic (Spring 2010)

### 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)