|   Exams & solutions ⇣  |   Books ⇣

One hour after the exam.

Resources for the Foundations Prelim

Old exams and solutions

You can find an index of old prelim exams and various people’s solutions here. I've tried to make it easy for others to add their own solutions as well.

Books

Here are my suggestions for books that cover the prelim material. I started in the logic group with basically zero knowledge, and I don't learn very well from courses, so if you find yourself in a similar situation then perhaps my thoughts will be more relevant.

For model theory, my favourite is Dave Marker's. (The main alternatives are: Chang and Keisler, Hodges, Hodg, Sacks, and Poizat.) It also has lots of examples and do-able but still useful exercises, and the first five chapters cover everything you need. You should be aware, however, that there are lots of typos, but the most blatant ones are corrected in the errata on Prof. Marker's website. Also, most chapters and even many sections end with advanced topics that are interesting, but also quite technical and unnecessary for the prelim, so you should probably skip them.

I should also mention that Justin Bledin has a nice set of notes summarising (most of) the relevant material.

Edit: Alex Kruckman writes to me with the following: “You might add Ch. 1-4 of Tent and Ziegler to your list of model theory resources on the prelim page. The presentation there is very terse, so it's definitely not a good thing to jump into before reading some of Marker, but they summarize lots of important facts very neatly, there are good exercises, and there's an awesome section where they go through quantifier elimination and basic properties for all the important theories (Sets, DLO, Abelian groups, ACF, SCF, RCF, DCF) in the course of 10 pages.” (But then, what does Alex know?! (Answer: a lot.))

For recursion theory, the standard book is Soare's text. It is not very readable (heavy notation and random conventions, almost no motivation, and very dry and formal proofs), but there are few other texts that cover the material that you need (corresponding mostly to part A of the book). A nice gentle introduction is Cutland's book, but it doesn't go far enough. I'm aware of two books that do cover more material in a friendly way, namely Odifreddi's and Cooper's, but they are longish and it's not clear that it's worth wading through them to understand the fairly minimal core of the prelim material. One thing you could try is to read Cutland and then find an older student to walk you through the rest of what you need, or help you read Soare. Personally, I eventually got a handle on this stuff by reading Soare four or five times, straight through.

For set theory, Kunen (chapter 1 and parts of 3) is a readable and fairly elementary source, although if you've never seen any set theory before at all, it might be a little rough at the beginning. Jech (chapters 1-4, 6, and maybe bits and pieces of the rest of the first part) has a bare-bones summary with some good exercises. Those are the two main sources, but I think there are probably lots of elementary treatments of set theory out there.

For incompleteness, undecidability, and models of PA, things are murkier. Justin Bledin has a short note on the basic setup of incompleteness. There are some articles in the Handbook of Mathematical Logic edited by John Barwise, by Smorynski and Rabin, that sketch a picture of what's going on. Kaye has a treatment of models of PA, but it is a little long, and only partially covers the incompleteness theorems (in the exercises). There are various sources for in depth treatments of incompleteness (e.g. Peter Smith's notes, available online), but on the whole, it's not clear that the prelim material warrants this much work. It may be better to learn some basics (from the articles), and then pick up the recurring tricks used in the prelim problems.

Edit: I haven’t looked too closely, but at a glance, Peter Hinman’s new text, Fundamentals of Mathematical Logic, could be the holy grail: a readable text, with exercises and real explanations, that covers most or all of what you’d need for the prelim. As a result, it’s almost 900 pages, but that includes a lot of extra stuff that you won’t need.