Study Guide

Teach yourself logic, #4: Beginning set theory

Here, after rather a long gap, is another instalment in the “Teach Yourself Logic” series. For new readers: given the dire state of logic teaching in some grad schools in philosophy (especially in the UK), I’m trying to put together a helpfully annotated reading list. The aim is to give students needing to teach themselves some logic a Guide through the daunting yards of books that are (or ought to be) in their university library. The reading list might be helpful to some mathematicians too. What we’ve covered up to now falls into four sections:

  1. Back to the beginning
  2. Getting to grips with first-order logic
  3. Modal logic
  4. From first-order logic to model theory

And here’s an edited version of the list so far. But I’m next going to jump out of sequence to what is planned to be §9 of the Guide, covering set-theory, since that’s what I happen to be thinking about right now. So now read on …

Where to start?

  • Derek Goldrei, Classic Set Theory (Chapman & Hall/CRC 1996) is written by a lecturer at the Open University in the UK and has the subtitle ‘For guided independent study’. It is as you might expect extremely clear, and it is quite attractively written (as set theory books go!).
  • Winfried Just and Martin Weese, Discovering Modern Set Theory I: The Basics (American Mathematical Society, 1996). This covers overlapping ground, but perhaps more zestfully and with a little more discussion of conceptually interesting issues, though also it is at some places more challenging (the pace can be uneven). But this is evidently written by enthusiastic teachers, and the book is engaging.

My next suggestion some might find a bit surprising, as it is a blast from the past. However, both philosophers and mathematicians ought to appreciate the way it puts the development of our canonical ZFC set theory into some context, and also discusses alternative approaches:

  • Abraham Fraenkel, Yehoshua Bar-Hillel and Azriel Levy, Foundations of Set-Theory (North-Holland, 2nd edition 1973). This really is attractively readable, and should be very largely accessible at this early stage. I’m not an enthusiast for history for history’s sake: but it really is worth knowing the stories that unfold here.

One intriguing feature of that last book is that it nowhere mentions the idea of the ‘cumulative hierarchy’ — the picture of the universe of sets as built up in a hierarchy of  levels, each level containing all the sets at previous levels plus new ones (so the levels are cumulative). This picture — nowadays familiar to every beginner — comes to the foreground in

  • Michael Potter, Set Theory and Its Philosophy (OUP, 2004). For philosophers (and for mathematicians concerned with foundational issues) this is — at some stage —  a ‘must read’, a unique blend of mathematical exposition and conceptual commentary.  Potter is presenting not straight ZFC but a very attractive variant due to Dana Scott whose axioms more directly encapsulate the idea of the cumulative hierarchy of sets. However, it has to be said that there are passages which are pretty hard going — sometimes because of the philosophical ideas involved, but sometimes because of unnecessary expositional compression. In particular, at the key point at p.  41 where a trick is used to avoid treating the notion of a level (i.e. a level in the hierarchy) as a primitive, the definitions are presented too quickly, and I know that real beginners can get lost. However, if  you have read Just and Weese in particular, you should be able to work out what is going on and read on past this stumbling block.

The books mentioned so far don’t mention but don’t treat (1) independence and consistency results, and though Potter mentions (2) large cardinals, again this is without any development. For a first look at (1), a possibility is

  • Keith Devlin The Joy of Sets (Springer, 2nd end. 1993). This is again well written, but goes significantly faster than Goldrei or Just/Weese,  Chs 1–3 giving a fast track coverage of some of the material in those books. Later chapters in this compact book introduce more advanced material. In particular, Ch. 5 discusses Gödel’s notion of constructible sets, Ch. 6 uses “Boolean valued” sets to prove the independence of the Continuum Hypothesis, and Ch. 7 considers what happens if you allow non-well-founded sets (infinite downward membership chains). But all this is done pretty speedily, which may or may not appeal.

But you could well jump over Devlin and go straight to a more comprehensive treatment of independence proofs, the self-selecting

  • Kenneth Kunen Set Theory: An Introduction to Independence Proofs (North Holland, 1980), rewritten as his Set Theory* (College Publications, 2011). The first version is a modern classic, used in many university courses: the new version is a timely update and — on a fairly brief inspection — looks to have all the virtues of the earlier version, but acknowledging thirty years of progress.

And then of course — if you’ve got the set-theoretic bug — the modern bible awaits you in the form of the rather monumental

  • Thomas Jech, Set Theory: The Third Millenium Edition (Springer, 2003).

Which is more than enough to be getting on with!

However, as an afterthought in small print for the list, we might usefully add a handful of other books that seem to me of particular interest for one reason or another. These could all be read after Goldrei or Just/Weese before or alongside Kunen. In no special order

  • Thomas Forster, Set Theory with a Universal Set: Exploring an Untyped Universe (OUP, 2nd end. 1995). Focuses on Quine’s NF and related systems. It is worth knowing something about alternatives to ZFC.
  • Thomas Jech, The Axiom of Choice* (North-Holland, 1973: reprinted by Dover Books 2008). Readable, attractively short, and will tell you about a variety of constructions (including Fraenkel-Mostowski models and Cohen forcing).
  • Raymond Smullyan and Melvin Fitting, Set Theory and the Continuum Problem*  (OUP 1996, revised edition by Dover Books 2010). Famously lucid authors trying to make hard proofs accessible and doing a good job.
  • If you were intrigued by some of the historical material in Fraenkel/Bar-Hillel/Levy then you should enjoy José Ferreirós, Labyrinth of Thought: A History of Set Theory and its Role in Modern Mathematics (Birkäuser, 2007). This is slightly mistitled — it is the history of early set theory, stopping around Gödel’s relative consistency results. But a very interesting read.

I could go on! Should I have mentioned Moschovakis’s nice Notes on Set Theory earlier on in the main list? Added Bell on Boolean-Valued Models to the small print?? Even added Halbeisen’s interesting new book on Combinatorial Set Theory??? But let me pause here.

Suggestions please!

Added later I surely should have mentioned at the outset Enderton’s book Elements of Set Theory (what a pity it isn’t available as a cheap Dover reprint!). And I am beginning to wonder about splitting this burgeoning section of the Guide into two sections — ‘Beginning Set Theory’ and ‘Continuing Set Theory”.

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:

  1. 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:

  1. 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.
  2. 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:

  1. 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?

Teach yourself logic, #2: Modal logic

An expanded, improved, version of the full Guide to teaching yourself various areas of logic is now here.

So let’s move on to looking at books to read on modal logic.

The ordering of some of the instalments here is necessarily going to be a little bit arbitrary. But I’m putting this one next for two reasons. First, the basics of modal logic don’t involve anything mathematically more sophisticated than the elementary first-order logic covered in the first instalment. Second, and more much importantly, philosophers working in many areas surely ought to know a little modal logic, even if they can stop their logical education and manage without knowing too much about some of the fancier areas of logic we are going to be looking at later.

Again, the plan is to offer a list of books of increasing range and difficulty, choosing those which look most promising for do-it-yourself study. The place to start is clear, I think:

  1. Rod Girle, Modal Logics and Philosophy (Acumen 2000, 2009). Girle’s logic courses in Auckland, his enthusiasm and abilities as a teacher, are justly famous. Part I of this book provides a particularly lucid introduction, which in 136 pages explains the basics, covering both trees and natural deduction for some propositional modal logics, and extending to the beginnings of quantified modal logic.

Also pretty introductory, though perhaps rather brisker than Girle at the outset, is

  1. Graham Priest, An Introduction to Non-Classical Logic (CUP, much expanded 2nd edition 2008): read Chs 2–4, 14–18. This book — which is a terrific achievement and enviably clear and well-organized — systematically explores logics of a wide variety of kinds, always using trees in a way that can be very illuminating.

If you start with Priest’s book, then  at some point you will need to supplement it by looking at a treatment of natural deduction proof systems for modal logics. A possible way in would be via the opening chapters of

  1. James Garson, Modal Logic for Philosophers (CUP, 2006). This again is intended as a gentle introductory book: it deals with both ND and semantic tableaux (trees). But — on an admittedly rather more superficial acquaintance —  this doesn’t strike me as being as approachable or as successful.

We now go a step up in sophistication:

  1. Melvin Fitting and Richard L. Mendelsohn, First-Order Modal Logic (Kluwer 1998): also starts from scratch. But — while it should be accessible to anyone who can manage e.g. the Hodges overview article on first-order logics that I mentioned before — this goes quite a bit more snappily, with mathematical elegance. But it still also includes a good amount of philosophically interesting material. Recommended.

Getting as far as Fitting and Mendelsohn will give most philosophers a good enough grounding. Where, if anywhere, you go next in modal logic, broadly construed, would depend on your own further concerns (e.g. you might want to investigate provability logics, or temporal logics).  But if  you want to learn more about mainstream modal logic, here are some suggestions (skipping past older texts like the estimable Hughes and Cresswell, which now rather too much show their age). Though note, further technical developments do tend to take you rather quickly away from what is likely to be philosophically interesting territory.

  1. Sally Popkorn, First Steps in Modal Logic (CUP, 1994). The author is, at least in this possible world, identical with the mathematician Harold Simmons. This book, entirely on propositional modal logics, is written for computer scientists. The Introduction rather boldly says ‘There are few books on this subject and even fewer books worth looking at. None of these give an acceptable mathematically correct account of the subject. This book is a first attempt to fill that gap.’ This perhaps oversells the case: but the result is still  illuminating and readable — though its concerns are not especially those of philosophers.
  2. Going further is Patrick Blackburn, Maarten de Ricke and Yde Venema, Modal Logic (CUP, 2001). One of the Cambridge Tracts in Theoretical Computer Science. But don’t let that put you off. This text on propositional modal logics is (relatively) accessibly and agreeably written, with a lot of signposting to the reader of possible routes through the book, and interesting historical notes. I think it works pretty well. However, again this isn’t directed to philosophers.
  3. Alexander Chagrov and Michael Zakharyaschev’s Modal Logic (OUP, 1997) is a volume in the Oxford Logic Guides series and also concentrates on propositional modal logics. This one is probably for real enthusiasts: it tackles things in an unusual order, starting with a discussion of intuitionistic logic, and is pretty demanding of the reader.  Still, a philosopher who already knows just a little about intuitionism might well find the opening chapters illuminating.
  4. Nino B. Cocchiarella and Max A. Freund, Modal Logic: An Introduction to its Syntax and Semantics (OUP, 2008). The blurb announces that ‘a variety of modal logics at the sentential, first-order, and second-order levels are developed with clarity, precision and philosophical insight’. That sounds hopeful, and the authors are right about the unusually wide range. As noted, the previous three books only deal with propositional logics, while many of the more challenging philosophical issues about modality tangle with quantified modal logic. So the promised coverage makes the book potentially of particular interest to philosophers. However, when I looked at this book with an eye to using it for a graduate seminar, I didn’t find it appealing: I suspect that many readers will indeed find the treatments in this book uncomfortably terse and rather relentlessly hard going.
  5. Finally, in the pretty unlikely event that you want to follow up even more, there’s the giant Handbook of Modal Logic, ed van Bentham et al., (Elsevier, 2005). You can get an idea of what’s in the volume by looking at the opening pages of entries available online here.

Scroll to Top