CSC 438F/2404F: Computability and Logic
Fall, 2005

The Undergrad Announcements (UGA) website contains announcements about things of importance to students, such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines. Lectures: MW 10 in BA 1240

Tutorial: F10 in BA 1240

Tutor: Phuong Nguyen

Instructor: Stephen Cook , email: sacook@cs, Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 3:10-4:00. Or make an appointment, or drop in, or send a question via email.

Text: None. See Lecture Notes below.

Marking Scheme:

• 5 assignments worth 10% each (Due at beginning of tutorial Sept 30, Oct 14, Nov 4, Nov 18, Dec 9)
• 2 closed-book tests worth 10% each (Oct 21, Nov 25)
• final exam worth 30%

Reference Link: Handbook of Proof Theory, Chapters I and II by Sam Buss

Other References:

• Herbert Enderton: A Mathematical Introduction to Logic . Academic Press, 1972.

• E. Mendelson: Introduction to Mathematical Logic . Wadsworth & Brooks/Cole, 1987

Lecture Notes (.ps files) These will be posted before each section of the course.

Thanks to 2404 student Paul Medvedev for pointing out errors in these notes.

Please send corrections and comments to the instructor.
(Thanks to Paul Medvedev for providing many such corrections.)

• Notes pp1-15: Propositional Calculus
• Notes pp16-28: Predicate Calculus
• Notes pp29-35 Completeness of LK
• Notes pp36-48 Herbrand Theorem, Equality, and Compactness
• Notes pp49-65 Computability Theory
• Notes pp66-77 Recursive and Recursively Enumerable Sets
• Notes pp78-90 Incompleteness Part I
• Notes pp91-103 Peano Arithmetic
• Notes pp104-107 Godel Incompleteness Theorems

• Problem Set 1 Due Sept 30, in tutorial

• Problem Set 2 Due Oct 14, in tutorial

• Problem Set 3 Due Nov 4, in tutorial

• Problem Set 4 Due Nov 18, in tutorial

• Problem Set 5 Due Dec 9, in tutorial