Logic III is an introduction to the incompleteness theorems and recursion theory. Official, printable outlines can be found at the end of this page.
Course Description
This course is a continuation of Phil 379 (Logic II). Specifically, we will focus on two famous theorems of symbolic logic due to Kurt Gödel: The Incompleteness Theorems. The first of these states, roughly, that every formal mathematical theory, provided it is sufficiently expressive and free from contradictions, is incomplete in the sense that there are always statements (in fact, true statements) in the language of the theory which the theory can’t prove.
In order to prove the Incompleteness Theorem, we’ll need to study the expressive power of formal languages and axiomatic theories—this is an important and exciting area in itself. This investigation will lead us naturally to a topic familiar from Logic II, i.e., computability. In Logic III, however, we’ll approach computability not via Turing machines, but via the notion of a recursive function. (We will prove, however, that both notions coincide.)
Prerequisites and Preparation
Logic II (PHIL 379) is a prerequisite for this course. It can’t hurt to review the material from PHIL 379, especially Chapters 1, 2, 9, 10, 12 of the textbook (Chapters 1, 2, 3, 9, 12, 13 of the 3rd edition).
Required Text
Peter Smith, An Introduction to Gödel’s Theorems, Cambridge University Press, 2007
Requirements and Evaluation
The course requirements are: A “diagnostic” homework assignment (5%), 4 homework assignments (60%—15% each), and a final project (30%—25% paper, 5% presentation).
You must submit all four assignments and the final project.
The final project will consist in a paper (approx. 2500 words) on a topic of your choice related to the material covered in the course. You will give an oral presentation of your paper in the final week of class.
Class participation counts for the remaining 5% of your grade. If you are shy and do not want to speak in class, 4 substantive, serious posts over the course of the term on the online discussion board will earn you an A for participation. Only posts made before the last day of class count. If all your posts are made within a 7-day period, you will receive a maximum credit of 2 grade points for them. On each problem on an assignment and on the paper and presentation parts of the final project you will receive a letter grade reflecting the level of mastery of the material shown by the work you submit.
Syllabus
This is a tentative syllabus to give you a rough idea what parts of the book we will cover when. Due dates are subject to change.
Week 1: Introduction, Review: Chapters 1–3
Learning goals: Understanding enumerability, effective enumerability, decidability;
axiomatic theories and their properties.
Week 2: Expressing and Capturing Numerical Properties :Chapters 4–6.
Learning goals: Understanding how properties and relations of numbers can be
expressed in the language of arithmetic, and how they can be captured by formal
theories. Understanding the connections between expressive power of theories
and decidability.
Diagnostic Assignment due (covers material from Phil 379).
Week 3: Formal Arithmetics: Chapters 8–10
Learning goals: Acquaintance with formal theories of arithmetic, facility with proving things in these theories. Understanding induction.
Week 4: Primitive Recursive Functions. Chapters 11–12.
Learning goals: Understanding primitive recursion, facility with defining primitive
recursive functions.
Assignment 1 due
Week 5: Capturing Primitive Recursive Functions Chapter 13
Learning goals: Understanding why all p.r. functions are 1, and why all 1 functions can be captured in Q.
Week 6: Arithmetization of Syntax: Chapter 15.
Learning goals: Understanding Gödel numbering and why syntactic properties are primitive recursive.
Assignment 2 due
Week 7: Incompleteness: Chapter 16, 17
Learning goals: Understanding and proving Gödel’s First Incompleteness Theorem.
Week 8: Diagonalization: Chapters 19–21
Learning goals: Generalizing the proof of the first incompleteness theorem; understanding and applying the diagonalization lemma to get Tarski’s Theorem about the undefinability of truth.
Week 9: Second-order Logic and Arithmetic: Chapter 22
Learning goals: Understanding quantification over sets; expressive power of 2nd order logic; understanding second-order arithmetic.
Assignment 3 due
Week 10: Provability Predicates and the Second Incompleteness Theorem: Chapters 24–27.
Learning goals: Understanding formalized consistency statements and provability conditions. The second incompleteness theorem. Reflection principles.
Week 11: Recursive Functions: Chapters 29, 30.
Learning goals: Understanding ?-recursive functions.
Week 12: Recursive Functions and Turing Machines: Chapter 31–34.
Assignment 4 due
Learning goals: Understanding why ?-recursive functions are Turing computable and vice versa. The Church-Turing Thesis.
Week 13: Student Presentations
Final project due