Instructor: Donald A. Martin; MS 7935 and Dodd 355; dam@math.ucla.edu.
Teaching Assistant: Assaf Shani; MS 2344.
Lectures: MWF 10:00-10:50; MS 5127.
Section: T 10:00-10:50; MS 5127.
Text:The text will be a set of notes made available here, gradually
over the quarter. Notes made available so far.
Martin Office Hours: In MS 7935; Monday 12-1,
Wednesday 11-12, and Fridays 1-2.
Grading:
Homework (10%); 2 Midterm Exams (50%); Final Exam (40%).
First midterm solutions.
Second midterm solutions.
Content:
First-order languages. Models, truth, and logical implication.
Formal deduction. Soundness and completeness theorems for the system of
formal deduction. Compactness and Loewenheim-Skolem theorems. Peano
Arithmetic. Incompleteness theorems.
Homework: Homework will be assigned here and will be collected
in class each Wednesday except the first one. No late homework will be
accepted, but the lowest homework score will be dropped.
- Exercises 1.1, 1.2, 1.3, and 1.4. Due April 11.
- Exercises 2.1, 2.2, 2.3, 2.4, and 2.5. Due April 18. For Exercise 2.1,
you may assume that if s and s' agree on all variables occuring
in a term t then the denotation of t in any model under the two assignments is the
same. (This can be proved by induction on length.)
- Exercises 2.6 (3), 2.6 (4), 3.5, and 3.6. Due April 25.
- Exercises 4.1 (assuming Extra Problem 1), 4.2, and 4.3. Due May 2.
- Exercises 4.4 and 4.7. Due May 9.
- Exercises 4.5, 4.6, and 4.8. Due May 16.
- Exercises 5.7, 5.8, and the parts of Exercise 6.1 that were not on
the 2nd midterm. Due May 30.
- Exercises 6.2 and 6.3. Due June 6.
Practice Problems
- Deduction: Exercises 3.1, 3.2, 3.3, and 3.4.
- Definitions: Exercise 2.7.
- Induction on length: Extra Problem 1.
- Solutions.
- For 2nd midterm: Exercises 5.1, 5.2, 5.3, 5.4.
- More for 2nd midterm.
Solutions.
- Solutions for Ex. 5.1 and 5.2.
- Solutions for Ex. 5.3, 5.4, 5.5, and 5.6.
- Solutions for Ex. 6.2, 6.3, 6.4, and 6.5.
- Solutions for Ex. 6.6, 6.7, and 6.8.