INTERMEDIATE LOGIC

Overview

This is not so much a course in logic as it is a course about logic: We shall be largely concerned with working our way through proofs of the fundamental metatheorems of standard (truth-functional) first-order predicate logic. In doing this, we shall make use of some notions from set theory and from elementary computability theory that are to be introduced during the first half of the course. The goal is finally to get to the point where the metalogical results (completeness, compactness, undecidability) begin to become philosophically interesting, a point from which we can at least intelligently discuss the most significant metalogical result of the 20^th Century -- namely, Gödel's first incompleteness theorem, which is often taken to show that truth and theoremhood, or provability, are in no sense the same thing.

Text (available at the campus bookstore)

George S. Boolos and Richard C. Jeffrey, Computability and Logic, 3^rd edition (Cambridge, 1989).

Books on Reserve

I have also put a few ancillary works on reserve at the Central Library for those of you who are especially interested in a topic.

Course Organization

Chapter 1 -- Enumerability

Chapter 2 -- Diagonalization

Chapter 3 -- Turing machines

Chapter 4 -- Uncomputability via the busy beaver problem

Chapter 5 -- Uncomputability via diagonalization

Chapter 6 -- Abacus computable functions are Turing computable

Chapter 7 -- Recursive function are abacus computable

Chapter 8 -- Turing computable functions are recursive

Chapter 9 -- First-order logic revisited

Chapter 10 -- First-order logic is undecidable

Chapter 11 -- First-order logic formalized: derivations and soundness

Chapter 12 -- Completeness of the formalization; compactness

(Chapter 13 -- The Skolem-Löwenheim theorem)

(Chapter 14 -- Representability in Q)

(Chapter 15 -- Undecidability, indefinability and incompleteness)

Evaluation of Students' Performance

Semester grades will be determined on the basis of the average of your performance on a series of take-home assignments. Specifically, letter grades (and not points) for each assignment will be recorded and averaged to obtain 50% of your overall semester grade. Each assignment will be weighted equally.

In doing the take-home assignments, you may make use of "outside" help. For example, you may work in groups. You make also look up the answer in other logic texts or articles. (You may not look at the solutions to the exercises in our book in attempting to work any of those exercises if they have been assigned.) If you do make use of any outside help, you may do so only during the figuring-out-the-answer phase not during the writing-up-the-answer phase. Discuss this with me, if you are not clear about the distinction I have in mind here. You are responsible for understanding the difference. And making use of outside help during the writing-up-the-answer phase will be considered plagiarism.

The other half of your semester grade will be based on attendance. Much of our in-class time will be spent as a group in working through on the board the various metalogical results discussed in the book. You can't work through this material with us if you are not there! Contrary to my usual practice in upper-division philosophy courses, I will be taking attendance daily. You will begin with an 'A' in attendance and lose one-third of a letter grade for every day you miss. The resulting grade will account for the other 50% of your overall semester grade.