The course will meet Tuesday and Thursday at 10.30am, in Sayles Hall 200. It is my hope that there will be a good bit of discussion during these meetings. Sometimes, I will lecture, as there will be material in our readings I need to explain, and material not in our readings I'd like to introduce. But I may well try to experiment a bit with how we approach things. So it will be particularly important that everyone come to class prepared not just to listen but to participate, every time.
Formally speaking, Philosophy 0540 or 1630 is a prerequisite for this course. I will be presuming a familiarity with basic logical notation, with how it can be used to represent the `logical forms' of ordinary English statements and of mathematical claims, and with basic facts about validity, implication, and formal deduction. So you should understand what something like ∀x∃y(Fxy) might mean, and how it would differ from ∃y∀x(Fxy). And you should understand what it means to say that the latter implies the former, but not conversely, and how this could be shown.
Philosophy 1880 is not required. We will, however, be assuming some concepts from that course, which I will introduce at the beginning, and it might be a good idea to have a copy of the text from that course, Computability and Logic, to use as a reference for some of what we shall be reading. What will be most important, though, is that students should have a degree of mathematical sophistication. The course will be very mathematical in content. It is essential that students have a solid understanding of what it is to prove something mathematically.
We may do some philosophy in this course, as well, as there is quite a literature on the second incompleteness theorem and its significance. How much we do will depend, however, upon what kind of progress we make with the formal material, and upon how the interests of the class develop.
The only required book for the course is Undecidable Theories, by Tarski, Mostowski, and Robinson. I did not order it through the bookstore, as it is readily available from the usual outlets, such as ABE Books, Amazon, and Barnes and Noble. You may also wish to purchase a copy of The Undecidable, edited by Martin Davis (ABE Books, Amazon, Barnes and Noble). This has Gödel's paper in it, along with a couple other things we might read (and several other things you should read, whether we read them or not, such as Turing's original paper on computability). If you just want a copy of Gödel's paper, you can but it too from Amazon, Barnes and Noble, or ABE Books. Note that both of these books are Dover editions, so they are quite cheap.
Other readings will be distributed electronically. Many of these are available online, through Brown's digital journal holdings; others will be scans of articles, or chapters from books, that are not otherwise available digitally. The files are usually available in two forms: (i) a DjVu file and (ii) a PDF file. Why both forms? They are intended for different uses.
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.
Along the way, students will be required to do various exercises based upon our readings, e.g., filling in the details of proofs, or proving results related to ones we discuss in class. These will be presented on a fairly ad hoc basis, however, as we go. I do not have a collection of problems prepared in advance at this point.
There will be a final exam during the final exam period. The final grade will be determined by the grade on the final and performance on the exercises, with about half the grade depending upon each.