This page is meant to help students preparing for the Logic Group's foundations prelim. The books listed have been helpful to prelim-takers of the past, and we hope they help you. All standard disclaimers apply: this is not necessarily a complete list, just reading the books will not be enough, etc.
Official information
The Logic Group's website has information on the foundations prelim here, and there are old exams here.
Suggested texts
The texts listed below contain a superset of the material you should know for the prelim. In each section, the most complete reference(s) is (are) indicated with an asterisk. The others have useful features, but they should probably be considered as supplementary.
General Mathematical Logic
- Boolos, Burgess, and Jeffrey, Computability and Logic
-
- Enderton, A Mathematical Introduction to Logic
-
Model Theory
- *Chang and Keisler, Model Theory
- Chapters 1-3 (1970s editions).
- Wilfrid Hodges, A Shorter Model Theory
- Chapters 1, 2, 3.1-2, 4.1-3; 5.1, 5.2, 5.6, 6.2-3, 7.3.
- Marker, Model Theory: An Introduction
- This book contains some very useful information on quantifier elimination.
- Poizat, A Course in Model Theory
- Chapters 1-5 cover basic model theory topics like compactness and Lowenheim-Skolem, Chapter 6 contains examples and some quantifier-elimination proofs, and Chapters 9-10 cover the more advanced model theory prelim topics, like saturation, countable categoricity, and omitting types.
- Justin Bledin, An Even Shorter Model Theory (Fall 2006)
- Justin posted some of his notes from 225A on his website. He says that edits and comments are welcome!
- Shelah, Classification Theory
- Just kidding. The only reason to open it before your prelim is to make the other books you're working from seem much kinder and gentler afterwards.
Recursion Theory
- *Robert Soare, Recursively Enumerable Sets and Degrees
- Chapters 1-4 are all you need, but it would be a good idea to read the parts of Chapter 5 that go through the construction of a simple set.
- He's working on a new edition, and there is a preliminary version of the first few new chapters in circulation at Berkeley. It seems that some material has been added to the first four new chapters that has not historically been on the prelim (such as games).
- Cutland, Computability: An Introduction to Recursive Function Theory
Peano Arithmetic and the Incompleteness Theorems
- *Richard Kaye, Models of Peano Arithmetic
- The whole book is useful, but take a careful look at the technique for encoding subsets of N using nonstandard elements as products of primes (Chapter 1) and its discussion of overspill.
- *Barwise (ed.), Handbook of Mathematical Logic, D.1., "The Incompleteness Theorems" by Smorynski (pp. 821-865)
- This article provides a metamathematical overview of the incompleteness theorems.
- Judah and Goldstern, The Incompleteness Phenomenon
- This book provides technical proofs of the incompleteness theorems.
- Smullyan, Godel's Incompleteness Theorems
- This book provides technical proofs of the incompleteness theorems.
Undecidability
- Tarski, Mostowski, and Robinson, Undecidable Theories
- Chapters to follow.
- Schoenfield, Mathematical Logic
- Chapter 6. Pay particular attention to the exercises!
- Enderton, A Mathematical Introduction to Logic
- There is a short section that discusses whether certain reducts of PA are decidable, finitely axiomatizable, definability, etc. (p. 250, 1972 edition).
Set Theory
There isn't any set theory on the prelim, but if you feel that you need a crash course in it, the following might be useful:
- Kunen, Set Theory
- Chapter 1.
- Levy, Basic Set Theory
- How much?