Serious set theory
The Teach Yourself Logic Guide gives suggestions for readings on the elements of set theory. By way of reminder, the core recommendations there are for:
- Herbert B. Enderton, The Elements of Set Theory (Academic Press, 1977),
- Derek Goldrei, Classic Set Theory (Chapman & Hall/CRC 1996),
as alternative entry-level books, to be followed by one of
- Karel Hrbacek and Thomas Jech, Introduction to Set Theory (Marcel Dekker, 3rd edition 1999),
- Yiannis Moschovakis, Notes on Set Theory (Springer, 2nd edition 2006).
And then for more historical/conceptual discussion
- Abraham Fraenkel, Yehoshua Bar-Hillel and Azriel Levy, Foundations of Set-Theory (North-Holland, 2nd edition 1973),
- Michael Potter, Set Theory and Its Philosophy (OUP, 2004).
These readings will introduce you to the standard set theory ZFC, and the iterative hierarchy which it is now standardly taken to seek to describe. The readings will also have explained how we can construct the real number system in set theoretic terms (so giving you a sense of what might be involved in saying that set theory can be used as a ‘foundation’ for another mathematical theory). They also tell you something about the role of the axiom of choice, and about arithmetic of infinite cardinal and ordinal numbers. You should also have noted by now that standard ZFC is not the only set theory on the market. This supplementary page now presses on to give some suggestions for the further exploration of set theory.
We’ll take things in three stages,
- First, we focus again on our canonical theory, ZFC (though this soon reaches into seriously hard mathematics).
- Then we’ll backtrack from those pointers towards the frontiers to consider the Axiom of Choice (as this is of particular conceptual interest).
- Then we will say something about non-standard set theories (again, the possibility of different accounts, with different degrees of departure from the canonical theory, is of considerable conceptual interest and you don’t need a huge mathematical background to understand some of the options).
ZFC, with all the bells and whistles
One option is immediately to go for broke and dive in to the modern bible,
- Thomas Jech, Set Theory, The Third Millennium Edition, Revised and Expanded (Springer, 2003). The book is in three parts: the first, Jech says, every student should know; the second part every budding set-theorist should master; and the third consists of various results reflecting ‘the state of the art of set theory at the turn of the new millennium’. Start at page 1 and keep going to page 705 (or until you feel glutted with set theory, whichever comes first). For this is indeed a masterly achievement by a great expositor. And if you’ve happily read e.g. the introductory books by Enderton and then Moschovakis mentioned the Guide, then you should be able to cope pretty well with Part I of the book while it pushes on the story a little with some material on small large cardinals and other topics. Part II of the book starts by telling you about independence proofs. The Axiom of Choice is consistent with ZF and the Continuum Hypothesis is consistent with ZFC, as proved by Gödel using the idea of ‘constructible’ sets. And the Axiom of Choice is independent of ZF, and the Continuum Hypothesis is independent with ZFC, as proved by Cohen using the much more tricky idea of ‘forcing’. The rest of Part II tells you more about large cardinals, and about descriptive set theory. Part III is indeed for enthusiasts.
Now, Jech’s book is wonderful, but let’s face it, the sheer size makes it a trifle daunting. It goes quite a bit further than many will need, and to get there it does speed along a bit faster than some will feel comfortable with. So what other options are there for taking things more slowly? Well, you could well profit from starting with some preliminary historical orientation. If you looked at the old book by Fraenkel/Bar-Hillel/Levy which was recommended in the Guide, then you will already know something of the early days. Alternatively, there is a nice very short introductory overview
- José Ferreirós, ‘The early development of set theory’, The Stanford Encycl. of Philosophy. (Ferreirós has written a terrific book Labyrinth of Thought: A History of Set Theory and its Role in Modern Mathematics (Birkhäuser 1999), which at some stage in the future you might well want to read.)
And then you could browse through the substantial
- Akhiro Kanomori, ‘The Mathematical Development of Set Theory from Cantor to Cohen’, The Bulletin of Symbolic Logic (1996) pp. 1-71, a revised version of which is downloadable here. (You will very probably need to skip chunks of this at a first pass: but even a partial grasp will help give you a good sense of the lie of the land.)
Then to start filling in details, an approachable and admired older book (not up-to-date of course, but still a fine first treatment of its topic) is
- Frank R. Drake, Set Theory: An Introduction to Large Cardinals (North-Holland, 1974), which – at a gentler pace? – overlaps with Part I of Jech’s bible, but also will tell you about Gödel’s Constructible Universe and some more about large cardinals.
But the crucial next step — that perhaps marks the point where set theory gets challenging — is to get your head around Cohen’s idea of forcing used in independence proofs. But there is not getting away from it, this is tough. In the admirable
- Timothy Y. Chow, ‘A beginner’s guide to forcing’, downloadable form the arXiv,
All mathematicians are familiar with the concept of an open research problem. I propose the less familiar concept of an open exposition problem. Solving an open exposition problem means explaining a mathematical subject in a way that renders it totally perspicuous. Every step should be motivated and clear; ideally, students should feel that they could have arrived at the results themselves. The proofs should be ‘natural’ …[i.e., lack] any ad hoc constructions or brilliancies. I believe that it is an open exposition problem to explain forcing.
In short: if you find that expositions of forcing tend to be hard going, then join the club. Here though is a very widely used and much reprinted textbook, which nicely complements Drake’s book and which has (inter alia) a pretty good presentation of forcing:
- Kenneth Kunen, Set Theory: An Introduction to Independence Proofs (North-Holland, 1980). Again, if you have read (some of) the introductory set theory books mentioned in the Guide, you should actually find much of this classic text now pretty accessible, and can speed through at least until you get to the penultimate chapter on forcing which you’ll need to take slowly and carefully. (Kunen has lately published another, totally rewritten, version of this book as Set Theory (College Publications, 2011). This later book is quite significantly longer, covering an amount of more difficult material that has come to prominence since 1980. Not just because of the additional material, my current sense is that the earlier book remains the slightly more approachable read. But you’ll probably want to tackle the later version at some point.)
Kunen’s classic text takes a ‘straight down the middle’ approach, starting with what is basically Cohen’s original treatment of forcing, though he does relate this to some variant approaches to forcing. Here are two of them:
- Raymond Smullyan and Melvin Fitting, Set Theory and the Continuum Problem (OUP 1996, Dover Publications 2010). This medium-sized book is divided into three parts. Part I is a nice introduction to axiomatic set theory. The shorter Part II concerns matters round and about Gödel’s consistency proofs via the idea of constructible sets. Part III gives a different take on forcing (a variant of the approach taken in Fitting’s earlier Intuitionistic Logic, Model Theory, and Forcing, North Holland, 1969). This is beautifully done, as you might expect from two writers with a quite enviable knack for wonderfully clear explanations and an eye for elegance.
- Keith Devlin, The Joy of Sets (Springer 1979, 2nd edn. 1993) Ch. 6 introduces the idea of Boolean-Valued Models and their use in independence proofs. The basic idea is fairly easily grasped, but details get hairy. For more on this theme, see John L. Bell’s classic Set Theory: Boolean-Valued Models and Independence Proofs (Oxford Logic Guides, OUP, 3rd edn. 2005). The relation between this approach and other approaches to forcing is discussed e.g. in Chow’s paper and the last chapter of Smullyan and Fitting.
And after those? It’s back to Jech’s bible and/or the more recent
- Lorenz J. Halbeisen, Combinatorial Set Theory, With a Gentle Introduction to Forcing (Springer 2011, with a late draft freely downloadable from the author’s website). This is particularly attractively written for a set theory book, and has been widely recommended.
And then – oh heavens! – there is another blockbuster awaiting you:
- Akihiro Kanamori, The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings (Springer, 1997, 2nd edn. 2003).
The Axiom of Choice
But leave the Higher Infinite and get back down to earth! In fact, to return to the beginning, we might wonder: is ZFC the ‘right’ set theory?
Start by thinking about the Axiom of Choice in particular. It is comforting to know from Gödel that AC is consistent with ZF (so adding it doesn’t lead to contradiction). But we also know from Cohen’s forcing argument that AC is independent with ZF (so accepting ZF doesn’t commit you to accepting AC too). So why buy AC? Is it an optional extra? Some of the readings already mentioned will have touched on the question of AC’s status and role. But for an overview/revision of some basics, see
- John L. Bell, ‘The Axiom of Choice’, The Stanford Encyclopedia of Philosophy.
For a very short book also explaining some of the consequences of AC (and some of the results that you need AC to prove), see e.g.
- Horst Herrlich, Axiom of Choice (Springer 2006), which has chapters rather tantalisingly entitled ‘Disasters without Choice’, ‘Disasters with Choice’ and ‘Disasters either way’.
That already probably tells you more than enough about the impact of AC: but there’s also a famous book by H. Rubin and J.E. Rubin, Equivalents of the Axiom of Choice (North-Holland 1963; 2nd edn. 1985) which gives over two hundred equivalents of AC! Then next there is the nice short classic
- Thomas Jech, The Axiom of Choice (North-Holland 1973, Dover Publications 2008). This proves the Gödel and Cohen consistency and independence results about AC (without bringing into play everything needed to prove the parallel results about the Continuum Hypothesis). In particular, there is a nice presentation of the so-called Fraenkel-Mostowski method of using ‘permutation models’. Then later parts of the book tell us something about what mathematics without choice, and about alternative axioms that are inconsistent with choice.
And for a more recent short book, taking you into new territories (e.g. making links with category theory), enthusiasts might enjoy
- John L. Bell, The Axiom of Choice (College Publications, 2009).
Other set theories?
From earlier reading you should have picked up the idea that, although ZFC is the canonical modern set theory, there are other theories on the market. I mention just a selection here (I’m not suggesting you follow up all these –the point is to stress that set theory is not quite the monolithic edifice that some introductory presentations might suggest).
NBG You will have come across mention of this already (e.g. even in the early pages of Enderton’s set theory book). And in fact – in many of the respects that matter – it isn’t really an ‘alternative’ set theory. So let’s get it out of the way first. We know that the universe of sets in ZFC is not itself a set. But we might think that this universe is a sort of big collection. Should we explicitly recognize, then, two sorts of collection, sets and (as they are called in the trade) proper classes which are too big to be sets? NBG (named for von Neumann, Bernays, Gödel: some say VBG) is one such theory of collections. So NBG in some sense recognizes proper classes, objects having members but that cannot be members of other entities. NBG’s principle of class comprehension is predicative; i.e. quantified variables in the defining formula can’t range over proper classes but range only over sets, and we get a conservative extension of ZFC (nothing in the language of sets can be proved in NBG which can’t already be proved in ZFC). See
- Michael Potter, Set Theory and Its Philosophy (OUP 2004) Appendix C, for more on NBG and on other theories with classes as well as sets.
- Elliott Mendelson, Introduction to Mathematical Logic (CRC, 4th edition 1997), Ch.4. is a classic and influential textbook presentation of set-theory via NBG.
SP This again is by way of reminder. Recall, earlier in the Guide, we very warmly recommended Michael Potter’s book which we just mentioned again. This presents a version of an axiomatization of set theory due to Dana Scott (hence ‘Scott-Potter set theory’). This axiomatization is consciously guided by the conception of the set theoretic universe as built up in levels (the conception that, supposedly, also warrants the axioms of ZF). What Potter’s book aims to reveal is that we can get a rich hierarchy of sets, more than enough for mathematical purposes, without committing ourselves to all of ZFC (whose extreme richness comes from the full Axiom of Replacement). If you haven’t read Potter’s book before, now is the time to look at it.
ZFA (i.e. ZF – AF + AFA) Here again is the now-familiar hierarchical conception of the set universe: We start with some non-sets (maybe zero of them in the case of pure set theory). We collect them into sets (as many different ways as we can). Now we collect what we’ve already formed into sets (as many as we can). Keep on going, as far as we can. On this ‘bottom-up’ picture, the Axiom of Foundation is compelling (any downward chain linked by set-membership will bottom out, and won’t go round in a circle). But now here’s another alternative conception of the set universe. Think of a set as a gadget that points you at some some things, its members. And those members, if sets, point to their members. And so on and so forth. On this ‘top-down’ picture, the Axiom of Foundation is not so compelling. As we follow the pointers, can’t we for example come back to where we started? It is well known that in much of the usual development of ZFC the Axiom of Foundation AF does little work. So what about considering a theory of sets which drops AF and instead has an Anti-Foundation Axiom (AFA), which allows self-membered sets?
- Lawrence S. Moss, ‘Non-wellfounded set theory’, The Stanford Encycl. of Philosophy:
- Peter Aczel, Non-well-founded sets, (CSLI Lecture Notes 1988), is a readable classic, and freely available here .
- Keith Devlin, The Joy of Sets (Springer, 2nd edn. 1993), Ch. 7. The last chapter of Devlin’s book, added to second edition of his book, starts with a very lucid introduction, and develops some of the theory.
- Luca Incurvati, ‘The graph conception of set’ Journal of Philosophical Logic (published online Dec 2012), very illuminatingly explores the motivation for such set theories.
NF Now for a much more radical departure from ZF. Standard set theory lacks a universal set because, together with other standard assumptions, the idea that there is a set of all sets leads to contradiction. But by tinkering with those other assumptions, there are coherent theories with universal sets. For very readable presentations concentrating on Quine’s NF (‘New Foundations’), and explaining motivations as well as technical details, see
- T. F. Forster, Set Theory with a Universal Set Oxford Logic Guides 31 (Clarendon Press, 2nd edn. 1995). A classic: very worth reading even if you are committed ZF-iste.
- M. Randall Holmes, Elementary Set Theory with a Universal Set** (Cahiers du Centre de Logique No. 10, Louvain, 1998). Now freely available here.
ETCS Famously, Zermelo constructed his theory of sets by gathering together some principles of set-theoretic reasoning that seemed actually to be used by working mathematicians (engaged in e.g. the rigorization of analysis or the development of point set topology), hoping to get a theory strong enough for mathematical use while weak enough to avoid paradox. But does he overshoot? We’ve already noted that SP is a weaker theory which may suffice. For a more radical approach, see
- Tom Leinster, ‘Rethinking set theory’, posted at the arXiv, gives an advertising pitch for the merits of Lawvere’s Elementary Theory of the Category of Sets, and …
- F. William Lawvere and Robert Rosebrugh, Sets for Mathematicians (CUP 2003) gives a very accessible presentation which in principle doesn’t require that you have already done any category theory.
But perhaps to fully appreciate what’s going on, you will have to go on to dabble in some more category theory.
IZF, CZF ZF/ZFC has a classical logic: what if we change the logic to inituitionistic logic? what if we have more general constructivist scruples? The place to start exploring is
- Laura Crosilla, ‘Set Theory: Constructive and Intuitionistic ZF’, The Stanford Encyclopedia of Philosophy.
Then for one interesting possibility, look at the version of constructive ZF in
- Peter Aczel and Michael Rathjen, Constructive Set Theory (Draft, 2010) .
IST Leibniz and Newton invented infinitesimal calculus in the 1660s: a century and a half later we learnt how to rigorize the calculus without invoking infinitely small quantities. Still, the idea of infinitesimals retains a certain intuitive appeal, and in the 1960s, Abraham Robinson created a theory of hyperreal numbers: this yields a rigorous formal treatment of infinitesimal calculus (you will have seen this mentioned in e.g. Enderton’s Mathematical Introduction to Logic, §2.8, or van Dalen’s Logic and Structure, p. 123). Later, a simpler and arguably more natural approach, based on so-called Internal Set Theory, was invented by Edward Nelson. As put it, ‘IST is an extension of Zermelo-Fraenkel set theory in that alongside the basic binary membership relation, it introduces a new unary predicate ‘standard’ which can be applied to elements of the mathematical universe together with some axioms for reasoning with this new predicate.’ Starting in this way we can recover features of Robinson’s theory in a simpler framework.
- Edward Nelson, ‘Internal set theory: a new approach to nonstandard analysis’ Bulletin of The American Mathematical Society 83 (1977), pp. 1165–1198. Now freely available here.
- Nader Vakin, Real Analysis through Modern Infinitesimals (CUP, 2011). A monograph developing Nelson’s ideas whose early chapters are quite approachable and may well appeal to some.
Yet more? Well yes, we can keep on going. Take a look, for example, at SEAR. But we must call a halt! For a brisk overview, putting many of these various set theories into some sort of order, and mentioning yet further alternatives, see
- M. Randall Holmes, ‘Alternative axiomatic set theories’, The Stanford Encyclopedia of Philosophy.
If that’s a bit too brisk, then (if you can get access to it) there’s what can be thought of as a bigger, better, version here:
- M. Randall Holmes, Thomas Forster and Thierry Libert. ‘Alternative Set Theories’. In Dov Gabbay, Akihiro Kanamori, and John Woods, eds. Handbook of the History of Logic, vol. 6, Sets and Extensions in the Twentieth Century, pp. 559-632. (Elsevier/North-Holland 2012).