This course will cover topics from mathematical logic and the foundations of mathematics. The theme is the formalization of mathematics in logical systems, and what can or cannot be achieved. It's well known that Goedel proved that one cannot formalize the whole of mathematics in a complete way (such that every assertion can be proved or disproved). Equivalently, it is undecidable - there is no universal method for testing mathematical truth.

What's less widely known among those who haven't studied logic is that many commonly studied mathematical theories are decidable. For example, the theory of the real numbers is decidable. The proof is a combination of a general logical technique ("quantifier elimination") with some elegant theorems about R that should be better known. As a striking consequence, there is an algorithm that can infallibly decide the truth of statements of Euclidean geometry (which is therefore not subject to Goedel's incompleteness theorem).

After developing the necessary background from scratch, we'll explore the phenomena of decidability and undecidability in detail. Along the way, I hope to convince the students that mathematical logic has close ties to many other fields, contrary to the common perception that it is self-absorbed. In particular, without going very far out of our way, we'll see important applications to combinatorics and algebra.

For a brief introduction to a few of the ideas of the course, see these notes from a brief talk for undergraduates. This course will cover a broader range of topics and of course will go into greater depth, but the notes should give an idea of its flavor.

Math 583CA will require relatively little specific mathematical background, just a good feeling for rigorous, abstract mathematics. In particular, it should be accessible to advanced undergraduates. Some background from abstract algebra may be used in a few self-contained examples, but won't be needed for the principal content of the course.

The choice of material and perspective in this course do not closely fit any of the textbooks I know of, so we won't follow any of them.

I believe that looking through the original papers in some field of mathematics is a very useful and enlightening experience. Unfortunately, in most fields it is next to impossible for anyone but a historian. Logic is not ideal in this respect, but it is rather good: most of the important papers date from this century, they are often in English, and they don't depend on specialized background.

I'll hand out a selection of important papers by Goedel, Turing, Church, Rosser, Tarski, Seidenberg, Henkin, and others (English translations for the few papers in German), as well as some more recent surveys and expositions. I hope this helps give a better feeling for how mathematics develops than one can obtain by studying a textbook.