This is mostly a story about limitations. In Logic I, we looked at things we can do by logical methods; notably, we can prove each valid sentence. Here, we'll look at things we can't do: we can't test whether a given is valid, and we can't prove every true sentence, even if we restrict our attention to true sentences about the natural numbers. We'll begin with an introduction to the theory of computability. The central idea of the theory is the Church-Turing thesis, which identifies the decidable sets of natural numbers -- that is, those sets of natural numbers for which there is a mechanical procedure for determining whether a given number is in the set -- with those sets of numbers that are definable by particularly simple formulas of the language of arithmetic. So we'll talk in some detail about how the language of arithmetic is constructed and how to express common mathematical ideas within it. This investigation of the language of arithmetic will lead directly to our central topic, which is Kurt Gödel's theorem that, for any system of true arithmetical statements we might propose as an axiomatic basis for proving truths of arithmetic, there will be some arithmetical statements that we can recognize as true even though they don't follow from the system of axioms. So the traditional ideas about how mathematics works, which is that mathematical reasoning consists in drawing out the consequences of a system of axioms, can't be all there is to the epistemology of mathematics. In my opinion, which is widely shared, Gödel's theorem is the most important single result in the entire history of logic, important not only on its own right but for the many applications of the technique by which it's proved. We'll discuss some of these applications, among them: Church and Turing's theorem that there is no algorithm for deciding when a formula is valid in the predicate calculus; Tarski's theorem that the set of true sentence of a language isn't definable within that language; and Gödel's second incompleteness theorem, which says that no consistent system of axioms can prove its own consistency. We'll conclude by looking at the second incompleteness theorem from the point of view of modal logic, interpreting the "It is necessary that" of modal logic as "It is provable that."
I plan to try to write up notes for the course and post them on the web, but I don't know how well I'll be able to keep up. A good resource will be The Logic of Provability by George Boolos.
Your grade for the course will be based on problem sets, which will come every week or two. There will be no final exam.