Logic III Phil 3321 Course Description

Jim Garson Office hrs 2-3 MWF and by appointment. 502 AH x 3205

The main goal of this course is to prove the three most important theorems in the foundations of mathematics. These are Turing's Theorem (There is no method to determine whether a computer program will halt.), Church's Theorem (Predicate Logic has no decision procedure.), and Goedel's Theorem (Arithmetic is Incomplete). We will also prove the adequacy (soundness and completeness) of Predicate Logic. The course will begin with an exploration of Turing machines, and then apply lessons learned there to predicate logic and then arithmetic. There will be numerous exercises. After each theorem is proven we will briefly explore its implications in the philosophy of mathematics.

Our Text (abbrevated: C&L):

Boolos, G. Burgess, and Jeffrey, Computability and Logic (4^th or 5^th editions)

See http://www.princeton.edu/~jburgess/addenda.htm for errata and exercise hints for the fifth edition. IT IS IMPORTANT TO MAKE CORRECTIONS FOR THE ERRATA IN YOUR COPY OF THE BOOK. IT CAN BE VERY CONFUSING IF YOU DON'T.

There will be two in class Quizzes and a Final.

Quiz 1 covers C&L Chs. 1-4.1, and 5 Feb. 18

Quiz 2 covers C&L Chs. 9-11.1 and 14.1-2 April 1

The Final covers all the above material and C&L Chs. 16.2-18 May 3, 11:00-2:00

(This schedule is tentative. It may be revised as the course develops.)

I will attempt to simplify material in the book as much as possible. This means we may deviate from the book, especially in the latter half of the course. To help record what goes on in class, notes will occasionally be handed out. Exercises either from the book or invented by me will be often given in class. LATE EXERCISES WILL RECEIVE AT MOST ½ CREDIT. For these and other reasons class attendance is crucial. Let me know if you must be absent, otherwise I may drop you.

Your grades will be calculated as follows:

Quiz #1 20%

Quiz #2 20%

Homework 25% FAILURE TO DO HOMEWORK WILL BE COSTLY TO YOUR GRADE

Final 35%