There is no real syllabus at this point, just a list of things we are going
to be reading, or probably will be reading, and even that is not set in stone.
It is simply too hard to know, in advance, at what pace we will be able to work
through the various topics we shall be covering. So think of what follows as a
rough guide that will settle into place as we proceed. As we go, I will enter
approximate dates for the various readings.
Most of the readings are available in two forms: (i) a DjVu file and (ii) a PDF file. They are intended for different uses.
- If you want to print the article out, then you should download the DjVu file. These files have two printed pages per viewed page, just as if you were looking at a photocopy of the article or book, and they are therefore easiest to print and read. But note: When printing these files, make sure you print them in the correct mode, namely 'landscape'. You will get very small text and a lot of blank paper if you print them 'portrait'.
- If you are going to read the article on your computer, or on an e-book reader, then you should download the PDF file (if available). These are one printed page per scanned page, and where possible they have been optimized for on-screen reading.
There is another advantage to DjVu. Because DjVu is a file format specifically designed for scanned text, the DjVu encoder produces files that are typically much smaller than the corresponding PDFs, sometimes as much as 95% smaller.
To view the PDFs, you will of course need a PDF reader. For the DjVu files, you will need a DjVu reader. Free browser plugins for Windows and Mac OSX are available from Caminova; Linux users can likely just install the
djviewlibre package using their distro's package management system. Another option is Okular, which was originally written for Linux's KDE Desktop Environment but which can now be run, experimentally, on Windows and OSX, as well. A list of other DjVu resources is maintained at djvu.org.
The program I have used to convert PDFs to DjVu is a simple Bash script I wrote myself, pdf2djvu. It relies upon other programs to do the real work and should run on OSX as well as on Linux.
- 11-20 September
Richard Heck, "Formal Background for the Incompleteness and Undefinability Theorems" (PDF). This will be review for some, but for the rest it will get us a general sense for what Gödel's theorem says and how it is proved.
If you're having a hard time understanding the diagonal lemma, then read this informal account, as well.
- 25 September to 4 October
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) Note that only the odd pages are in the DJVU; the even pages from this edition are in German. There are also inexpensive books available that have this paper in them.
- 9 October to 23 October
Alfred Tarski, Andrzej Mostowski, and Raphael Robinson, Undecidable Theories, chapters I and II.
You can skip I.6 and II.6, if you wish, or just skim them.
- 23 October to 6 November
George Boolos, The Logic of Provability (Cambridge: Cambridge University Press, 1993, Ch. 2. (DJVU)
These two readings are optional:
I encourage everyone to read the former, which is not too difficult. The latter, however, is suggested only for those who are otherwise having an easy time with this material and are looking for a challenge.
- 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)
- 8 November to ???
Solomon Feferman, "Arithmetization of Metamathematics in a General Setting", Fundamenta Mathematicae 49 (1960), pp. 35-92. (PDF)
A poor quality PDF
is publicly available.
- 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)
- Pavel Pudlák, "Cuts, Consistency Statements and Interpretations", Journal of Symbolic Logic 50 (1985), pp. 423-41. (JSTOR, DJVU)
- Andrzej Grzegorczyk, "Undecidability Without Arithmetization", Studia Logica 79 (2005), pp. 163-230. (JSTOR, DJVU)
- Albert Visser, "Can We Make the Second Incompleteness Theorem Coordinate Free?" Journal of Logic and Computation 21 (2009), pp. 543-60. (Oxford Journals, DJVU)