PHIL 3340
Symbolic Logic II

Curtis Brown
Spring, 2008

This course begins where Symbolic Logic I ends. Symbolic Logic I emphasizes learning to use a formal system to determine whether arguments are valid or not. Symbolic Logic II takes a more abstract view of formal systems, and focuses on metalogical results about them. For this offering of the course, we will use two texts. We will study Jose Zalabardo, Introduction to the Theory of Logic, for rigorous proofs of such properties of (some) formal systems as soundness, completeness, compactness, and the Löwenheim-Skolem Theorem. We will then turn to Peter Smith, An Introduction to Gödel's Theorems, to study the most famous metalogical result of the last hundred years, and to explore some connections with issues about the limits of computability.

Jose L. Zalabardo, Introduction to the Theory of Logic (Westview, 2000)

Peter Smith, An Introduction to Gödel's Theorems (Cambridge University Press, 2007)

TR 8:30 - 10:30; MW 4:00 - 5:00.

I am usually in my office during office hours, but occasionally a meeting or another commitment prevents this.  If you just drop by during office hours, you will probably find me in; if you want to see me at another time, or if you want to be certain I'll be in, we can set up an appointment.

Exams. There will be two in-class examinations, worth 20% each. The in-class exams are scheduled for Wednesday, February 20, and Monday, April 2. There will also be a final exam on Friday, May 9, at 2:00 PM. The final will count 20% of the final grade.

Homework. I will assign regular homework problems. Homework will count 15% of the final grade. Assignments are to be given to me at the beginning of the class period on the date due. No credit will be given for late assignments.

Paper/Project. I will require a 10-15 page paper, due Monday, April 28. I am open to alternative but equivalent projects, for example a software project with a separate written discussion of its significance and relevance to the course, or even an elaborately commented program (a "literate program"). Possible topics include: an in-depth discussion of an important theorem that we do not discuss, or discuss briefly, in class, or the philosophical significance of one of the results discussed in class. (I will be giving references to the philosophical literature as we go along.) A proposal for the paper is due by Wednesday, March 5. The paper will count 25% of the final grade.

This is just a rough sketch of topics and the order we will probably take them in. We'll have to feel our way into the pacing of the course, so a detailed schedule will be constructed only as we go along. With luck, we'll cover approximately half of each book. (The schedule below may be a little on the ambitious side.)

I. Introduction

Quick, informal review of first-order logic
Set theory and mathematical proof: Zalabardo, chapter 1

II. Propositional logic revisited: syntax and semantics

Zalabardo, chapter 2

III. First-order logic revisited: syntax and semantics

Zalabardo, chapter 3

IV. First-order logic revisited: Deduction

Zalabardo, chapter 4

V. Proving soundness and completeness

Zalabardo, chapter 5

VI. Proving the Löwenheim-Skolem Theorem

Zalabardo, chapter 7 (in part)

VII. Gödel's Incompleteness Theorems, first pass

Smith, chapters 1-7

VII. Gödel's Incompleteness Theorems, second pass

formalizing arithmetic: Smith, chapters 8-10
intro to recursive function theory: Smith, chapters 10-13
Gödel's first incompleteness theorem: Smith, chapters 14-18

IX. Connections between provability and computability

Smith, Chapters 29-35