This course provides an introduction to mathematical logic. Topics include propositional and predicate logic, the compactness and completeness theorems, elementary model theory, Godel's Incompleteness Theorem, and Zermelo-Fraenkel set theory. There are no specific prerequisites, though students are expected to have a certain level of mathematical maturity.

Lecture: TR 2:30 - 4:00, in Room 4-159

Instructor: Eric Rosen, rosen (at) math (dot) mit (dot) edu

Office: 2-172

Office hours: Tue. 4 - 5, Fri. 1 - 2, and by appointment

Textbook: Mathematical Logic: A Course with Exercises, Parts I and II, by R. Cori & D. Lascar

Requirements: Problem sets will be given every two weeks. The first assignment will be due Sept. 21. There will be a midterm, on Oct. 19, and a final exam, on Dec. 18.

Grading: The course grade will be determined by the homework (40%), the midterm (20%), and the final exam (40%).

Final Exam: The final exam will take place on Monday December 18, from 1:30 to 4:30, in room 2-135.

Homework: Homework must be handed in by 6:00 pm, either in class or in Room 2-172, on the day that it is due. Students are permitted to work together, but must write up solutions in their own words.

• Homework 1 Problems 1 - 4 due Thursday 9/21. Problems 5, 6 due Tuesday 9/26.
  Solutions

• Homework 2 Due Thursday 10/5.
  Solutions

• Midterm review problems. Chapter 3, #4, 5, 8, 10(a): 1 - 8, 11.

• Homework 3 Due Thursday 10/26.

• Homework 4 Due Thursday 11/9.
  Solutions

• Homework 5 Due TUESDAY 11/21.
  Solutions

• Homework 6 (Due Thursday 12/7.) Extension until Friday 12/8 at 12:00 pm.
  Solutions

  Syllabus: (tentative)

  1. R 9/07: Introduction.
  2. T 9/12: Syntax of propositional logic. Section 1.1.
  3. R 9/14: Semantics of propositional logic. Section 1.2.
  4. T 9/19: Normal forms and complete sets of connectives. Section 1.3.
  5. R 9/21: The compactness theorem. Section 1.5.
  6. T 9/26: Syntax of first order logic. Section 3.1.
  7. R 9/28: Semantics of first order logic. Section 3.2.
  8. T 10/3: Satisfaction of formulas in structures. Section 3.3.
  9. R 10/5: Universal equivalence and semantic consequence. Prenex forms. Sections 3.4 and 3.5.1.
  10. R 10/12: Introduction to model theory. Section 3.6.
  11. T 10/17: Formal proofs. Section 4.1.
  12. R 10/19: MIDTERM.
  13. T 10/24: Henkin models. The completeness and compactness theorems. Section 4.2.
  14. T 10/31: Primitive recursive functions. Section 5.1.
  15. R 11/2: Recursive functions. Recursive and recursively enumerable sets. Brief introduction to Turing machines. Sections 5.2.2 and 5.4.1.
  16. T 11/7: (Formalization of arithmetic, Godel's theorems) Peano's axioms. Section 6.1.
  17. R 11/9: Representable functions. Section 6.2.
  18. T 11/14: Arithmetization of syntax. Godel numbering. Section 6.3.
  19. R 11/16: Godel's first incompleteness theorem. Section 6.4.
  20. T 11/21: Godel's second incompletenesss theorem. Section 6.5.
      R 11/23: THANKSGIVING HOLIDAY
  21. T 11/28: Set theory. The theories Z and ZF. Section 7.1.
  22. R 11/30: Ordinal numbers. Section 7.2.
  23. T 12/5: Inductive proofs and definitions. Section 7.3.
  24. R 12/7: Cardinal numbers. Section 7.4.
  25. T 12/12: The continuum hypothesis, large cardinals, independence results.