Teach yourself logic, #3: Beginning model theory

(For later, better, thoughts, see the most recent version of the TYL Guide.)

I have been working away on the second edition of my Gödel book. The current task: giving a more lucid proof showing Robinson arithmetic can represent all primitive recursive functions. In the first edition I cheated by taking a clever trick from Burgess, Boolos and Jeffrey. I do now regret that. But I can certainly sympathise with my earlier self for taking the easy way out!

By way of diversion, then, and as an exercise in constructive procrastination, here is the draft third instalment of my slowly developing ‘teach yourself logic’ guide. So far we’ve covered (1) standard first-order logic, at an introductory level, and (2) some basic modal logic. Today’s new list (3) looks at the path forward from what’s covered in a standard first-order logic course on towards full-blown model theory. [The ordering of the instalments here is going to be henceforth a bit arbitrary; but I hope a tolerably sensible structure will emerge in the final composite Guide!]

In fact, in reworking the first two instalments of the Guide — you can now download an expanded version of them here — I have rethought the division between what is to go in instalment (1) and this new one. So take the treatment of first-order logic in (1) now to get just as far the completeness proof but really no further (so, that’s pretty much the content of e.g. Chiswell and Hodges’s terrific Mathematical Logic).

So where next, if you want to move on from those first intimations of classical model theory in the completeness theorem to something of a grasp of the modern theory? There is a very short old book, the very first volume in the Oxford Logic Guides series, Jane Bridge Beginning Model Theory: The Completeness Theorem and Some Consequences (Clarendon Press, 1977) which takes on the story just a few steps pretty lucidly. But very sadly, the book was printed in that short period when publishers thought it a bright idea to save money by photographically printing  work produced on electric typewriters. So, used as we now are to mathematical texts beautifully LaTeXed, the look of the book is decidedly off-putting. So let’s set that aside (as the first recommendation covers much of the same ground anyway).

Here, then, are two natural and rather complementary places to start:

1. Dirk van Dalen Logic and Structure (Springer 4th edition 2004). In instalment (1) I warmly recommended reading this modern classic text up to and including Section 3.1, for coverage of basic first-order logic. Now read the whole of Chapter 3, for a bit of revision and then for the Löwenheim-Skolem theorems and some basic model theory.
2. Wilfrid Hodges’s `Elementary Predicate Logic’, in Handbook of Philosophical Logic, Vol. 1, ed. by D. Gabbay and F. Guenthner, (Reidel 2nd edition 2001). This is an expanded version of the essay in the first edition of the Handbook, written with Hodges’s usual enviable lucidity. Over a hundred pages long, this serves both as an insightful and fresh overview course on basic first-order logic (more revision!), and as an illuminating introduction to some ideas from model theory.

For a more expansive treatment (though not really increasing the level of difficulty, nor indeed covering everything touched on in Hodges’s essay) here is a still reasonably elementary textbook:

3. Maria Manzano, Model Theory (OUP, 1999). I seem to recall, from a reading group where we looked at this book, that the translation can leave something to be desired. However, the coverage as far as it goes is good, and the treatment accessible. I like the way it starts off by talking about relationships among structures in general before talking about structures-as-models-of-theories.

This might already be about as far as most philosophers will want to go. But if you do press on, the choice at the next level up is surely self-selecting:

4. Wilfrid Hodges A Shorter Model Theory (CUP, 1997). Deservedly a modern classic — under half the length of the encyclopedic original, but still full of good things, going a good way beyond Manzano. It gets tough as the book progresses, but the earlier chapters should be manageable.
5. Rather different in focus is another older book, which is particularly elegant (though perhaps you will need more mathematical background to really appreciate it) is J. L, Bell and A. B. Slomson’s Models and Ultraproducts (North-Holland 1969; Dover reprint 2006). As the title suggests, this focuses particularly on the ultra-product construction.

Finally, though probably this is looking over the horizon for most readers of this list, at a further notch up in difficulty and mathematical sophistication, there is another book which has also quickly become something of a standard text:

6. David Marker, Model Theory: An Introduction (Springer 2002). Rightly very highly regarded. (But it isn’t published in the series ‘Graduate Texts in Mathematics’ for nothing!)

So that is my main list. What have I missed out? Well, you could still get a lot out of C. Chang and H. J. Keisler’s classic Model Theory (North Holland, 2nd edition 1977). This is leisurely, very lucid and nicely constructed with different chapters on different methods of model-building. You could well look at quite a bit of this before or alongside reading Hodges’s book. There’s a short little book by Kees Doets Basic Model Theory (CSLI 1996), which concentrates on Ehrenfeucht games which could appeal to enthusiasts. And then, of course, many Big Books on Mathematical Logic have chapters on model theory: a good treatment of some central results seems to be that in Shawn Hedman, A First Course in Logic (OUP 2004), Chs 4–6 which could be perhaps read after (or instead of) Manzano.

Comments and suggestions?