YIANNIS N. M OSCHOVAKIS, Notes on Set Theory, New York: SpringerVerlag, 1994. xiv + 272 pp. $39.00, ISBN 0-387-94180-0.
Reviewed by ACHILLE C. VARZI, Department of Philosophy, Columbia
University, New York NY 10027, USA(Published in History and Philosophy of Logic, 17:3 (1996), 172–175.)

This is an excellent introduction to axiomatic set theory, viewed both as afoundation of mathematics and as a branch of mathematics with its own subject matter, basic results, open problems. Written by one of the leading contributors to the field, it covers all the basic material, but with some novelties
that make it interesting also to the advanced reader.
The book begins with a couple of chapters devoted to the first, basic results of Cantorian set theory, including detailed accounts of Cantor’s diagonal arguments and of the Schroöder-Bernstein Theorem. While the style ofpresentation might strike some readers as rather demanding for a start (inspite of the useful figures accompanying the proofs), by the end of chapter 2
the effort is rewarded and the stage is set for appreciating the need for anaxiomatic framework. This is introduced in Chapter 3, which follows rather
faithfully Zermelo’s 1908 pragmatic approach vis-a-vis Russell’s paradox.
The author also follows Zermelo in allowing for Urelemente, which is motivated mostly by a desire to remain neutral with regard to the opposition between “the small view” (that the set theoretic universe consists exclusivelyof those objects whose existence is guaranteed by the axioms) and “thelarge view” (that the universe is closed under the axioms, but may contain allsorts of animals to begin with). This neutrality represents a philosophicalconstant in the book. Thus, while the author takes very seriously the idea thatevery mathematical object can be construed as (i.e., faithfully represented by)a set, he is also careful in emphasizing the modal dimension of this idea. For
instance, relations, functions, and the natural numbers can be represented bysets, but need not be.
The next two chapters introduce the basic material about the naturalnumbers (including induction and recursion) and cardinal arithmetic. By the1REVIEW OF YIANNIS N. MOSCHOVAKIS’ NOTES ON SET THEORY

end of Chapter 5, one can see how Zermelo’s system would allow one to goa long way in the reconstruction of elementary discrete mathematics, the rational numbers, the reals. The emphasis, however, is not on the details of thisdevelopment (which is left for the most part to the Problems or, as in the caseof the real numbers, postponed to a rich Appendix.) The emphasis is on thefact that all of this is attainable within the framework of Zermelo’s basic axioms. Indeed this is one of the main novelties of the book. Since Fraenkel’sAxiom of Replacement is not introduced until the end, neither is von Neumann’s theory of ordinals and cardinals. So N is not introduced as the set ofthe first ω ordinals, but as a structured set (unique up to isomorphism) satisfying Peano’s postulates. This approach has some cost, for certain developments would be much simpler (and in some places also more natural) if theordinals were brought in earlier. Yet the exercise is worthwile, for it shows
how far one can actually go without Replacement. (It is a common claim that
one can go as far as to develop 99% of modern mathematics, modulo theavailability of some Choice principle, but one hardly gets a clear picture ofwhat that really means unless one tries. Moreover, one learns that all the basic identities of cardinal arithmetic can be established as equinumerosities,
which is something a beginner might easily overlook. The only danger is that
if the book is used as a text, one may not be able to get far enough to see theordinals at all.)Beginning with Chapter 6, the material gets harder and the presentation
more compact. Chapter 6 is itself a novelty for an introductory book, as it iscentered around ideas and results in the context of the theory of partial orderings and partial functions. This leads to an elegant generalization of therecursion theorem which takes the form of a continuous fixed point theorem.
Apart from its intrinsic interest, this also represents an interesting point ofcontact between classical set theory and contemporary theoretical computerscience, as the author rightly emphasizes. (One could have taken this opportunity to mention other applications as well, e.g. partial semantics and revision theories.) The fixed point theorem in question is of course a special
case of Zermelo’s theorem, which is intimately related to the theory of wellorderings. This forms the topic of Chapter 7, which also deals with Transfinite Induction and Recursion. Coupled with Hartogs’ Theorem, this provides

2

REVIEW OF YIANNIS N. MOSCHOVAKIS’ NOTES ON SET THEORY

the necessary machinery to apply recursive definitions and proofs by induction to situations far removed from the natural numbers.
Chapters 8 and 9 focus on the Axiom of Choice. There is a good blendof technical results and philosophical remarks in these chapters, although thestarting point is somewhat misleading. The author argues that, naively understood, AC is obvious in view of the Powerset Axiom: “When we grantsethood to the class {X | X ⊆ Α} of all subsets of A, we truly mean all subsets of A, including those for which the membership criterion is not determined by some explicit law but by free choice, by chance if you will” [120].
But of course the Powerset Axiom has nothing to do with this. ℘(A) consists of all subsets of A, but whether these include inter alia the range of achoice function for A is a totally independent question. (One should rather
put it thus: if there were no choice set for A, it would seem that the notion ofa subset includes some implicit restrictions which are not in the spirit ofZermelo’s “limitation of size” approach. For, after all, a choice set must bea subset.) Apart from this, these two chapters contain a lot of interesting data.
Particualry valuable is the inclusion of material concerning weaker versionsof AC, most notably the Axiom of Dependent Choices, which is enough tojustify all classical mathematics. Moreover, on the technical side, there aresome elegant applications of the material on fixed points introduced earlier.
(See for instance the nice proofs of the various equivalents to AC.) Thismeans that Chapter 6 is not skippable even if you are not interested in its
relevance to computer science; however the effort is quite worthwhile.
Chapter 10 on Baire space, on the other hand, is in principle skippable
without loss of continuity. It covers some results in the theory of pointsets
which are of special interest to analysts. Their relevance to the Continuum
Problem is also emphasized, though, so the non-analyst may use that as areading key for this chapter.
Finally, Chapters 11 and 12 introduce the Axiom of Replacement andeventually the von Neumann ordinals and cardinals. This is all pretty standard, as is the brief illustration of von Neumann’s picture of the set-theoreticuniverse (the cumulative hierachy of pure, well-founded sets). Still, it is niceto see at this point the further extension of the recursion principle allowed byReplacement. Indeed this gradual strengthening of the power of recursive

3

REVIEW OF YIANNIS N. MOSCHOVAKIS’ NOTES ON SET THEORY

definitions constitutes a valuable fil rouge through the book. By contrast, itwould have been nice to see here more indications of the deductive strengthof Replacement with respect to the overall axiomatic system. (The derivability of the Separation Axiom is only brought up in an exercise, and that ofPairing is not even mentioned.)Throughout the book, the technical presentation is accompanied by useful historical remarks, including some indications of the main consistency
and independence results about AC and CH (Gödel, Cohen, Solovay).
Moreover, there is a rich Appendix devoted to the study of various natural
set-theoretic models, including Rieger universes (which violate the Principleof Purity) and in particular Aczel’s antifounded universe (which features arich variety of non-well-founded sets). This is certainly admirable and confirms the recent change of attitude among set-theorists with regard to theaxiom of Foundation. (This is the second book on elementary set theory thatincludes a section on non-well-founded sets, after Keith Devlin’s The Joy ofSets, 1993.) Perhaps this is a place where the author could have been moregenerous with informal remarks and examples. Some decades ago, Fraenkeland Bar-Hillel argued that “one can accept [the Axiom of Foundation] notas an article of faith but as a convention for giving a more restricted meaning
to the word ‘set’, to be discarded once it turns out that it impedes significant
mathematical research” [Foundations of Set Theory, Second Revised Edition, p. 89]. Arguably, today there are indeed many interesting applicationsof non-well-founded sets apart from independence proofs—from the semantics of natural language and programming languages to knowledge representation and game theory. (Barwise and Moss’ 1996 book, Vicious Circles, gives an excellent overview of such a variety of applications.) There are
therefore good reasons for “discarding” Foundation from the axiomatic
foundations of set theory. This is the author’s own attitude. But he does little
to help the reader appreciate it.
It is also a pity that the author decided not to back up his presentation
with adequate bibliographic references: a generic reference to the Dover edition of Cantor’s Beiträge and to van Heijenoort’s collection of classics ishardly enough. Likewise, a more extensive index and a complete glossary ofsymbols would make the book more useful as a reference. As for the editing,

4

REVIEW OF YIANNIS N. MOSCHOVAKIS’ NOTES ON SET THEORY

there are unfortunately numerous errata which may be disturbing if the bookis used as a text (although spotting them is certainly good exercise for thereader). Some nasty ones: on p. 19, the quantifier in GCH should have‘ ℘(A)’ in place of ‘A’; on p. 21, first line, ‘G’ should be ‘C’; on p. 59, therange of the functions hy and ƒy should be E, not E × N, and the condition for
ƒy(n + 1) should refer to ƒy(n), not ƒ(n); on p. 69, first line, the second ‘N’should be ‘N × N’; on p. 95, just before (7.8), ‘x’ should read ‘y’ (twice);on p. 99, the formula following (7.13) should define σ t , not σ u (likewise, twolines above, ‘u = Sv’ should read ‘t = Sv’); on p. 107, line 3, ‘segV ’ shouldread ‘segU’, and on line 10, ‘<o ’ should read ‘< χ(A)’; on p. 121, line 11 frombottom, ‘A ≤/ c h(A)’ should read ‘h(A) ≤/ c A’; on p. 123, line 11 from bottom
should read ‘ƒ(0) = a’; on p. 139, last line of Lemma 9.20, ‘infc’ should
read ‘supc’; and on p. 200, second last line, “every von Neumann cardinal”
should read “every transfinite von Neumann cardinal” (similarly in exercise
12.21, p. 201).
Even with these limitations, which can easily be overcome in a secondedition, the book remains excellent and quite suitable as a textbook, ideal foradvanced undergraduate or beginning graduate students in mathematics,
philosophy, and computer science.

5