Intermediate Symbolic Logic
This course will be taught from Boolos, Burgess, and Jeffrey, Computability and Logic
My office hours are Thursday, 2-4 pm.
There will be weekly proofs to write up (listed below), and each student will present proofs in class approximately once a week. There will be no final exam.
The readings and topics we will cover are (in order) the following:
Chapter 1 - enumerability
Chapter 2 - uncountability
Chapter 9 - syntax of first-order logic
Chapter 10 - semantics of first-order logic
Chapter 6 - primitive recursive functions
Chapter 7 - recursive functions and relations
Chapter 15 - computability and logic
Chapter 16 - representation of recursive functions in logic
Chapter 17 - the first incompleteness theorem
If you want a second source on any of this material, ask me for other notes.
Written homework assignments:
All exercises are from the Boolos, Burgess, and Jeffrey book unless otherwise mentioned.
Tuesday, September 3: Exercise 1.4
Tuesday, September 17: Exercise 2.2
Tuesday, September 24: Exercise 2.11
Tuesday, October 1: Show that every term has a formation sequence in which only sub-terms of that term appear.
Tuesday, October 8: Exercises 10.2, 10.3
Tuesday, October 15: Exercises 1 and 2 from section 1.4 of the handout on deductions
Tuesday, October 22: The Negation Theorem, section 3.2.4 of the handout on deductions
Tuesday, October 29: Exercises 6.7, 6.8
Tuesday, November 6: Exercises 7.5, 7.6, 7.7
Tuesday, November 12 (no assignment)
Tuesday, November 19: Exercises 15.6, 15.7
Tuesday, November 26: Exercise 17.8
Solutions to exercises that have already been turned in.