Math 220B Fall 2010
Mathematical Logic and Set Theory

Room and Time

Instructor

Grading

Homework will be assigned on (almost every) Wednesday and will normally be due the next Wednesday by 5:00 PM. The homework assignments will be posted on this webpage. No late homework will be accepted, but one or even two missed homework assignments will not have a serious effect on the course grade.

Homework

  1. Prove parts 5, 8, and 11 of Lemma 1I.7. (You may, e.g., assume parts 1-4 in proving part 5.) Due Wednesday, January 13.
  2. Prove part (b) of Lemma 4A.3. Due Wednesday, January 20.
  3. Prove the primitive recursiveness of the set of all codes of instances of axiom schema 9 on page 42 or axiom schema 11 on the same page. (Take your choice between 9 and 11.) Also do Exercise 4B.2 (Lemma 4B.6) but only for atomic sentences and their negations.
  4. Show that if the graph of a function is expressible in Q then function is representable in Q. Due Wednesday, February 3.
  5. Exercises 4C.4, 4C.5, and 4C.6. Due Wednesday, February 10.
  6. Exercises 5A.6 and 5A.9. Due Wednesday, February 17.
  7. Exercises 5B.3, 5B.6, and 5B.7. Due Wednesday, February 24.
  8. Exercises 5C,1, 5C.2, and 5C.3. Due Wednesday, March 3.
  9. Exercises 5D.6, 5E.3, and 5E.6. Due Wednesday, March 10.

Final Exam

The Exam is due by Friday, March 19.

Text

The text for 220A and 220B is a small variant of a set of notes written by Yiannis Moschovakis. These notes will be distributed gradually over the course of the quarter. Here are links to the notes that have been distributed:

Content

Mathematics 220B is the second quarter of a three-quarter introduction to mathematical logic.

The first part of 220A was an be an introduction to first order logic: semantics, formal deduction, and relations between the two. This part of the course culminated with the fundamental Completeness, Compactness, and Skolem-Löwenheim Theorems. The latter part of the quarter was devoted to model theory. The part of the course notes covered was Chapter 1 and the first three sections of Chapter 2. 220B will be mainly devoted to incompleteness theorems and computability theory (formerly called recursion theory). In preparation for the first one or two lectures, students to might review Sections 1D and 1E of the notes.