Course Schedule for Philosophy 0690

Philosophy 0690: Course Schedule

If you wish, you can download the syllabus as a PDF. Please note, however, that the course schedule is approximate. We will proceed at whatever pace works for this particular group, and if enough of us get interested in some topic not on the particular route we are taking, we may digress for a bit. The PDF version of the syllabus will probably not be kept up to date. You should check this website for updates as we proceed.

The forms in which the readings are available are explained elsewhere.

12 May
Introductory Meeting

14 May–4 June
Richard Kimberly Heck, "Formal Background for the Incompleteness and Undefinability Theorems" (PDF).
For now, you can skip all but the first definition in §5 and what follows proposition 6.9 in §6. You can also stop reading after the proof of Theorem 11.2. We'll return to the rest later.

If you're having a hard time understanding the diagonal lemma (as many people do!), then read this informal account, as well.

7 June–21 June
Kurt Gödel, "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I", in Collected Works v. 1, ed. S. Feferman, J. Dawson, and S. Kleene (Oxford: Oxford University Press, 1986), pp. 144-95. (DJVU)

Only the odd pages are in the DJVU; the even pages from this edition are in German. There are also inexpensive books that have this paper in them.

There are some reading notes to help you get through the first couple sections.

23 June–9 July
Alfred Tarski, Andrzej Mostowski, and Raphael Robinson, Undecidable Theories, chapters I and II.

For Chapter I, focus on sections I.4 and I.5. You will need to read the earlier sections for terminology, but you do not need to worry about all the details. We will not discuss section I.6, so you can skip or skim it, as you wish.
We will discuss most of Chapter II, but you can skip or skim section II.6.

Optional:

Julia Robinson, "General Recursive Functions", Proceedings of the American Mathematical Society 1 (1950), pp. 703-18 (AMS)
Julia Robinson was one of the great logicians of the mid-twentieth century. She made major contributions to the proof that Hilbert's Tenth Problem is unsolvable. She was also the first woman to be president of the American Mathematical Society. See this trailer for a film about her.
James P. Jones and John C. Shepardson, "Variants of Robinson's Essentially Undecidable Theory R", Archiv for mathematische Logik 23 (1983), pp. 61-4. (Springer)

12 July–19 July
George Boolos, The Logic of Provability (Cambridge: Cambridge University Press, 1993, Ch. 2. (DJVU, PDF)

Optional:

Martin Löb, "Solution of a Problem of Leon Henkin", Journal of Symbolic Logic 20 (1955), pp. 115-8. (JSTOR, DJVU)
Robert G. Jeroslow, "Redundancies in the Hilbert-Bernays Derivability Conditions for Gödel's Second Incompleteness Theorem", Journal of Symbolic Logic 38 (1973), pp. 359-67. (JSTOR, DJVU).

I encourage everyone to read the former paper, which is not too difficult. The latter is recommended only for those who are otherwise having an easy time with this material and are looking for a challenge.

21 July–End
Solomon Feferman, "Arithmetization of Metamathematics in a General Setting", Fundamenta Mathematicae 49 (1960), pp. 35-92. (PDF)

A poor quality PDF is available from the European Digital Mathematics Library. I've put a cleaned-up version of it (run through ScanTailor) here as a DjVu. The above PDF is much easier to read, though.

11 August, 12 noon
Final Exam Due

The following papers are ones we probably will not have time to read, but I will list them here for students who wish to pursue these issues on their own.

Alex Wilkie and Jeff Paris, "On the Scheme of Induction for Bounded Arithmetic Formulas", Annals of Pure and Applied Logic 35 (1987), pp. 261-302. (Science Direct, DJVU)

This paper shows how the second incompleteness theorem can be proved for very weak theories: theories that are interpretable in Q and so cannot prove that exponentiation is a total function. The proof does not work for Q itself, however.

Pavel Pudlák, "Cuts, Consistency Statements and Interpretations", Journal of Symbolic Logic 50 (1985), pp. 423-41. (JSTOR, DJVU)

This paper states and proves a very powerful form of the incompleteness theorem, one that has significant implications for weak theories.

Andrzej Grzegorczyk, "Undecidability Without Arithmetization", Studia Logica 79 (2005), pp. 163-230. (JSTOR, DJVU)

This paper shows how to prove the first incompleteness theorem directly for a theory of symbols, i.e., without making use of Gödel numbering.

Albert Visser, "Can We Make the Second Incompleteness Theorem Coordinate Free?" Journal of Logic and Computation 21 (2009), pp. 543-60. (Oxford Journals, PDF)

This paper explores many of the same questions Feferman does and suggests one way of saying precisely what a 'consistency statement' is. Indeed, many of Visser's papers explore such questions.

Richard Kimberly Heck, "Consistency and the Theory of Truth", Review of Symbolic Logic 8 (2015), pp. 424-66 (Cambridge Journals, PDF)

This paper explores connections between consistency statements and theories of truth and proves that, for finitely axiomatizable theories, 'adding a theory of truth' gets you a theory with the same strength as 'adding a consistency statement'.