Basic topics include the compactness theorem, the Löwenheim-Skolem theorem, Ehrenfeucht-Fraïssé games, quantifier elimination, types, prime and saturated models, countably categorical models, and a brief introduction to omega-stable theories.

We will explore several applications to algebraic geometry, real algebraic geometry, combinatorics, and the computational complexity of decision procedures. We will also briefly examine nonstandard analysis and probability theory, and nonstandard models of arithmetic. Finally, infinitary logic and admissible sets provide a striking example of the connections between model theory, set theory, and computability theory.

There will be four problems sets, constituting 2/3 of the grade (see below). The remaining 1/3 will be determined by a 5-10 page written report (2/9) and 20 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 9) 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 14.

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.

PSet 1 (Due Thurs Feb 19): Section 1.4, #1, 2, 4, 9, *10 (see corrigenda), *11, *12, 15.

PSet 2 (Due Thurs Mar 12): Show that every infinite planar graph is 4-colorable (you may assume the finite 4-color theorem).
Section 2.5, #3, 5, 8, *11, 15 (a), *17 (see corrigenda), 28 (a), (b).

PSet 3 (Due Tues Apr 7): Section 4.5, #2, 5, 10, 15, 17.

PSet 4 (Due Thurs Apr 23): Section 4.5, #21, 24, 30, 46

Class Schedule:

Tues Feb 3: First class: Historical introduction; survey of applications

Thurs Feb 5: Languages, structures, and theories (Sections 1.1 and 1.2)

Tues Feb 10: Definable sets (Section 1.3)

Thurs Feb 12: Compactness theorem (Section 2.1)

Tues Feb 17: No class (Monday schedule, following Presidents Day)

Thurs Feb 19: Proof of the Completeness Theorem (PSet 1 due)

Tues Feb 24: Applications of compactness

Thurs Feb 26: Complete theories (Section 2.2) and Computable Completeness

Tues Mar 3: Lefschetz principle and Ax's Theorem; Examples of complete theories

Thurs Mar 5: Löwenheim-Skolem theorem (Section 2.3)

Tues Mar 10: Ehrenfeucht-Fraïssé games; Dense linear orderings. (Section 2.4)

Thurs Mar 12: More on EF games and infinitary logic; zero-one laws for graphs. (PSet 2 due)

Tues Mar 17: Types (Section 4.1)

Thurs Mar 19: Isolated types (Section 4.2)

Tues Mar 24: No class (Spring Break)

Tues Mar 26: No class (Spring Break)

Tues Mar 31: Omitting types (Section 4.2)

Thurs Apr 2: Prime and atomic models (Section 4.2)

Tues Apr 7: Homogeneous models (Section 4.2) (PSet 3 due)

Thurs Apr 9: \kappa-stable and saturated models (Section 4.3) (Topic approval due)

Tues Apr 14: More on saturated models (Section 4.3)

Thurs Apr 16: \kappa-universal models (Section 4.3)

Tues Apr 21: No class (Patriots Day)

Thurs Apr 23: Saturated and universal models (Section 4.3) (PSet 4 due)

Tues Apr 28: Automorphisms and types (Section 4.3)

Thurs Apr 30: Countably categorical models (Section 4.4)

Tues May 5: Ultraproducts and nonstandard analysis; student presentations: Javier, Daniel B. (computability prerequisites)

Thurs May 7: student presentations: Tamvana, Daniel B. (part 2)

Tues May 12: Last class: student presentations: Manuel, Dan R.

Thurs May 14: No class; (All written reports due — please submit by email to )