Course Overview

The fundamental theorems about the scope and limits of mathematical logic constitute some of the most beautiful intellectual work of the twentieth century, and in this course we will work through the proofs of a number of them. We will first show that first-order logic with identity is sound, complete, compact, and has the downward and upward Löwenheim-Skolem properties. We will then move on to the notion of computability and prove (on the assumption Church's thesis is true) that first-order logic is undecidable. At this point we will briefly examine the complexity of various decision problems (e.g., P-problems, NP-complete problems, NP-hard problems). We will then work through a proof of Gödel's first incompleteness theorem. Time permitting (which is unlikely) we will conclude with a hurried look at second-order logic and see why it lacks many of the metatheoretic properties (some pleasing for some purposes, not so pleasing for others) of first-order logic.

This year the course will differ a bit from previous years, with more emphasis on applications of logic (e.g., in cognitive science, philosophy, linguistics) and on the importance of a diversity of logical systems. The view of logic and inference as the extraction, processing and transformation of information will be also stressed. Among other things this will lead us to explore the idea of a function in intensional terms, as a rule or algorithm used to compute it, as well as the more traditional extensional picture in terms of sets. I haven't yet decided on the text for the course, but we will make some use of handouts, and the basic content will be the same, whatever book we use.

There is no way to learn this material except by getting your hands dirty with the formal mechanics, so there will be a good deal of homework in which you have to work problems and devise proofs of your own.