Phil 152/252: Computability & Logic
[
Overview | Reading Material | Schedule | Grading | Notes/Handouts]
Quarter: Spring
Instructor: Eric Pacuit
Instructor's Office Location: Room 92B, Building 90
Office Hours: TBA
Meeting Times: Tuesday, Thursday 2:15PM - 3:30PM
First Class: Tuesday, March 31, 2009
Location: Building 200, Room 030
Final Exam
The final exam is due June 10 in Wes'
mailbox.
Wes Holliday
Email: wesholliday AT stanford DOT edu
Section Times: Monday 1:15PM - 2:05PM
Section Location: Building 60, Room 119
Office Hours: Wednesday 11:00AM - 12:00PM (and by appointment)
Office: Building 100 Room 102K
Course Description:
This course is a continuation of Phil 151/152 (First Order Logic). Specifically, we will study
Chapter 3 of A Mathematical Introduction to Logic by Herbert Enderton which focuses on two
famous theorems 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 cannot prove. We will prove the 1st and
2nd Incompleteness Theorems and survey their technical and philosophical repercussions.
In order to prove the Incompleteness Theorem(s), we will need to study the expressive power of
formal languages and axiomatic theories and also discuss different approaches to effective
computation: recursive functions, register machines, and Turing machines. We will discuss their
equivalence, Church's thesis and elementary recursion theory. Finally, we will discuss modal
provability logic.
Course Material: Topics to be covered include formal models of computation; Church's Thesis;
Godel's 1st and 2nd incompleteness theorems and their repercussions; Tarski's proof of the
undefinability of truth; Undecidability of the Halting Problem; Decidable subsystems of arithmetic;
provability logic (Kripke soundness and completeness, arithmetical soundness and completeness,
fixed-point theorems)
Prerequisites: The formal prerequisite is Philosophy 151/251, or consent of the instructor.
The course is based on the following textbook(s).
- (Required) H. Enderton, A Mathematical Introduction to Logic, Academic Press, 2nd
Edition, 2001
- This course will focus on Chapter 3.
- You can purchase the book at the book store or through
Amazon.
- You can find the errata for the book here.
- (Recommended) T. Franzen, Godel's Theorem: An Incomplete Guide to its Use and
Abuse, A K Peters, 2005
- This will be placed on reserve in Tanner Library.
- You can purchase through
Amazon.
- Additional material from a variety of sources on elementary recursion theory and
provability logic.
The following texts are recommended for additional reading. (We may also make use of material from
these texts, so they
will be placed on reserve in Tanner Library):
- G. Boolos, J. Burgess, and R. Jeffrey, Computability
and Logic, Cambridge, 5th Edition, 2007.
- G. Boolos, The
Logic of Provability, Cambridge, 1993.
- P. Smith, An Introduction to
Godel's Theorems, Cambridge, 2007.
The following are highly recommended for further investigation:
The following texts provide an historical perspective.
The following texts are recommended for background on elementary (first-order) logic
- H. Enderton, A
Mathematical Introduction to Logic, Academic Press, 2nd Edition, 2001 (Chapters
0 - 2).
- R. Smullyan, First-Order
Logic, Dover, 1995 (first edition: 1968).
- H.-D. Ebbinghaus, J. Flum, and W. Thomas, Mathematical
Logic, Springer, 1995.
Below is a schedule which will be updated as the course proceeds. The reading refers to sections
from A Mathematical Introduction to Logic by Herbert Enderton. We will cover most of Chapter
3 plus some additional material on Turing machines, implications of Godel's Theorem(s) and
provability logic.
Course Schedule (updated 3/2)
| Date |
Lecture Topic |
Reading |
Notes |
| 3/31 |
Introduction and Motivation |
|
|
| 4/2 |
Basic Concepts |
1.7, 2.6, 3.0 |
Also read Section 1.7 |
| 4/7 |
Natural numbers with successor |
3.1 |
|
| 4/9 |
Natural numbers with successor |
3.1 |
|
| 4/14 |
Natural numbers with successor and ordering |
3.2 |
Homework 1 |
| 4/16 |
Natural numbers with successor and ordering |
3.2 |
|
| 4/21 |
Natural Number with successor and ordering |
3.2 |
|
| 4/23 |
Natural numbers with S,+,*,E |
3.3 |
HW 1 Due |
| 4/28 |
Representability |
3.3 |
|
| 4/30 |
Representability in A_E |
3.3 & 3.4 |
|
| 5/5 |
Godel Numbering |
3.3 & 3.4 |
Homework 2 |
| 5/7 |
Godel Numbering |
3.3 & 3.4 |
|
| 5/12 |
Godel's Incompleteness Theorem |
3.5 |
|
| 5/14 |
Incompleteness and Undecidability |
3.5 |
HW 2 Due |
| 5/19 |
Incompleteness and Undecidability |
3.5 |
|
| 5/21 |
Recursive Functions |
3.6 |
Homework 3 |
| 5/26 |
Recursive Functions |
3.6 |
|
| 5/28 |
Godel's 2nd Incompleteness Theorem |
3.7 |
HW 3 Due |
| 6/2 |
Provability Logic |
|
Final Exam |
| 6/4 |
Provability Logic |
|
Review Session (not mandatory) |
There will be 3 homework assignments and a take-home final exam. Each homework assignment counts for
20% of the final grade and the
final exam counts for 40%. The solutions will be made available at Tanner Library.
For the final exam, you may NOT collaborate with others in any way. For the homework assignments,
you are encouraged to work in small groups. You may discuss the problems with one another or with
me. But you must always do the final write-up completely on you own. A good strategy when
working together is to use a blackboard and erase it completely before writing up your (separate)
answers. Please write the name of your discussion partners on the front page of your homework
assignments.
- Course Information (
pdf)
- Homework 1 (pdf)
The solutions are available in Tanner Library
- Homework 2 (pdf)
The solutions are available in Tanner Library
- Homework 3 (pdf)
- Final Exam (pdf)