Book Review: Naïve Set Theory (MIRI course list)
I’m reviewing the books on the MIRI course list. I followed Category Theory with Naïve Set Theory, by Paul R. Halmos.
This book is tiny, containing about 100 pages. It’s quite dense, but it’s not a difficult read. I’ll review the content before giving my impressions.
Chapter List
The Axiom of Extension
The Axiom of Specification
Unordered Pairs
Unions and Intersections
Complements and Powers
Ordered Pairs
Relations
Functions
Families
Inverses and Composites
Numbers
The Peano Axioms
Arithmetic
Order
The Axiom of Choice
Zorn’s Lemma
Well Ordering
Transfinite Recursion
Ordinal Numbers
Sets of Ordinal Numbers
Ordinal Arithmetic
The Schröder—Bernstein Theorem
Countable Sets
Cardinal Arithmetic
Cardinal Numbers
Normally I’d summarize each chapter, but chapters were about four tiny pages each and the content is mostly described by the chapter name. Zorn’s Lemma states that if all chains in a set have an upper bound, then the set has a maximal element. (This follows from the axiom of choice.) The Schröder-Bernstein Theorem states that if X is equivalent to a subset of Y, and Y is equivalent to a subset of X, then X and Y are equivalent. The other chapter titles are self-evident.
Each chapter presented the concepts in a concise manner, then worked through a few of the implications (with proofs), then provided a few short exercises.
None of the concepts within were particularly surprising, but it was good to play with them first-hand. Most useful was interacting with ordinal and cardinal numbers. It was nice to examine the actual structure of each type of number (in set theory) and deepen my previously-superficial knowledge of the distinction.
Discussion
Before diving in to the review it’s important to remember that the usefulness of a math textbook is heavily dependent upon your math background. I have a moderately strong background. Some specific subjects (analysis, type theory, group theory, etc.) have given me a solid, if indirect, foundation in set theory. This was the first time I studied set theory directly, but the concepts were hardly new.
Overview
I was pleased with this book. It is terse. It has exercises. It gives you information and gets out of your way, which is what I like in a textbook: It doesn’t waste your time. I’m about to harp on the book for a spell, but please keep in mind that my overall feeling was positive.
Please take these reviews with a grain of salt, as sample size is 1 and I have not read any similar textbooks.
Complaints
-
The book was written in 1960, and it shows. Set theory is more mature now than it was then. The authors often remark on syntax that was not yet standard (which is now commonplace). The continuum hypothesis had not yet been proven unprovable in ZFC. The axiom of choice is embraced wholeheartedly with no discussion of weaker variants. The style of proof differs from the modern style. None of this is bad, per se. In fact, it’s quite a fascinating time capsule: I enjoyed seeing a slice of mathematics from half a century past. However, I believe a more modern introduction to set theory could have taught me more pertinent mathematics in the same amount of time.
-
The notation is inconsistent. I’ve long believed that math is a poor and inconsistent language. This is evident throughout set theory. To the author’s credit, they point out many of the inconsistencies: f(A) can refer to both a function or a restriction of a function to the subset A of its domain, 2^w can refer to either functions mapping w onto 2 or a specific ordinal number, etc. I am personally of the opinion that introductory textbooks should enforce a pure & consistent syntax (which may be relaxed in practice). I was mildly annoyed with how the authors acknowledged the inconsistencies and then embraced them, thereby perpetuating a memetic tragedy of the commons. (I know that I shouldn’t expect better, but one can dream.)
-
The proofs given were primarily in english. Not once did the authors write ∃ or ∀. They would resort to “for some” or “for any” in largely english-language proofs. The proofs were rigorous (the authors tightly restricted their english phrases), but I was somewhat surprised to find the axioms of set theory described in lingual (rather than symbolic) form.
-
Set theory is axiom soup. I do not view set theory as foundational. Is the axiom of choice true? The question is poorly formed. Axioms are tools to constrain what you’re talking about. Better questions are shaped like “does the axiom of choice apply to this thing I’m working with?”, or “how does the structure change if we take this statement as an axiom?”. This sentiment seems fairly common in modern mathematics, but it was lacking in Naïve Set Theory. Axioms were presented as facts, not tools. There was little exploration of each axiom, what it cost and what it bought, and what alternate forms are available.
Most of these gripes are small compared to the amount of good data in the book. Remember that the book is titled Naïve Set Theory: a little naïvety is to be expected. The takeaway is that the book was good, but likely could have been better in light of modern mathematics. All in all, the book covers lot of ground at a fast clip, and was quite useful.
Should I learn set theory?
As always, it depends upon your goals. Set theory is everywhere in mathematics, and I personally appreciated shoring up my foundations. If you have similar goals, you can easily go through this book in a week if you think that learning set theory is worth your time.
I don’t particularly recommend set theory to armchair mathematicians. In my experience, other areas of mathematics are much more fun from a casual standpoint. (Group theory and information theory come to mind, if you’re looking for a good time.)
Should I read this book?
Maybe. I have no point of comparison here. My tentative suggestion is that you should find a more modern (but similarly terse) introductory textbook and read that instead. (If you have a good suggestion, you should leave it in the comments.)
I found this book to be rather basic. If you have a background similar to mine, I recommend something a little more advanced. (Unfortunately, I can make no recommendations. Again, comments are welcome.)
This book seems well-suited for a layperson interested in learning set theory. The 1960s feel is definitely fun. I would guess that the book is well-paced for someone who has done the standard college calculus courses but is unfamiliar with Set Theory subject matter.
What should I read?
If you’re going to read the book then I suggest reading the whole thing. It builds from first principles up to cardinality, and nothing along the way is unimportant. My only suggestion is that you swap chapter 25 and 24: they appear to have been ordered incorrectly for political reasons. (The derivation of cardinal numbers used in chapter 25 was, at the time, controversial, so the book presents cardinal arithmetic before cardinal numbers.) Other than that, the book was well structured.
Final Notes
If a comparably short-and-sweet textbook written in the last twenty years can be found, I recommend updating the suggestion on the MIRI course list. It’s not clear to me how much raw set theory is useful in modern AI research; my wild guess is that mathematical logic, model theory, and provability theory are more important. If that is the case, then I think the technical level of this book is appropriate for the course list: it’s sufficient to brush up on the basics, but it doesn’t send you deep into rabbit holes when there are more interesting topics on the horizon.
My next review will take more time than did the previous four. I have a number of loose ends to tie up before jumping in to Model Theory, and I have much less familiarity with the subject matter.
- The mechanics of my recent productivity by (9 Jan 2014 2:30 UTC; 200 points)
- Mental Context for Model Theory by (30 Oct 2013 6:35 UTC; 112 points)
- Set Up for Success: Insights from ‘Naïve Set Theory’ by (28 Feb 2018 2:01 UTC; 31 points)
- [Math] Towards Proof Writing as a Skill In Itself by (13 Jun 2018 4:39 UTC; 25 points)
- Book Review: Naive Set Theory (MIRI research guide) by (14 Aug 2015 22:08 UTC; 23 points)
- 's comment on What are you working on? October 2013 by (1 Oct 2013 22:31 UTC; 18 points)
- 's comment on Innate Mathematical Ability by (18 Feb 2015 20:06 UTC; 3 points)
These book reviews are badass.
That is all.
Thanks for the great review! Your tip to swap 24 and 25 was helpful, as was your warning about inconsistent notation. However, one benefit of “inconsistent notation” is that it really forces you to develop a clear understanding.
Anyway, I’ll add some additional thoughts.
Overall, I got a lot out of this. Naive Set Theory clarified a lot of foundational concepts I had previously taken for granted. It also made me crack up at times; for example:
The slight feeling of discomfort that the reader may experience in connection with the definition of natural numbers is quite common and in most cases temporary.
We want to be told that the successor of 7 is 8, but to be told that 7 is a subset of 8 or that 7 is an element of 8 is disturbing.
I personally found the trickiest part to be the proof of Zorn’s lemma. So for posterity, here’s a sketch of the proof that might be helpful for following the full proof given in the text:
Zorn’s lemma. Let X be a partially-ordered set such that every chain in X has an upper bound (in X); then X has a maximal element.
Proof sketch.
Let S be collection of weak initial segments of elements of X, ordered by set inclusion; show that if S has a maximal set, then X has a maximal element
Let C be the collection of all chains in X, ordered by set inclusion; show that if C has a maximal set, then S has a maximal set (the text uses a script X in place of C)
Use the axiom of choice to construct an “extension” function g on C that extends a non-maximal set by one element, and leaves a maximal set unchanged
Define a special kind of subset of C called a tower
The definition of a tower is incredibly clever, and it rigorously describes the intuitive idea of “keep adding elements until you get a maximal set”
Let t be the “smallest possible tower” (i.e. the intersection of all towers), and let A be the union of every set in t; show that g leaves A unchanged
Conclude that C has a maximal set (A); thus S has a maximal set; thus X has a maximal element
Finally, here’s the full list of ingredients in the axiom soup (note that the Peano “axioms” are actually proved, not taken as axioms):
Axiom of extension (page 2): Two sets are equal if and only if they have the same elements.
Axiom of specification (page 6): To every set A and to every condition S(x) there corresponds a set B whose elements are exactly those elements x of A for which S(x) holds.
Axiom of pairing (page 9): For any two sets there exists a set that they both belong to.
Axiom of unions (page 12): For every collection of sets there exists a set that contains all the elements that belong to at least one set of the given collection.
Axiom of powers (page 20): For each set there exists a collection of sets that contains among its elements all the subsets of the given set.
Axiom of infinity (page 44): There exists a set containing 0 and containing the successor of each of its elements.
Axiom of choice (page 59): The Cartesian product of a non-empty family of non-empty sets is non-empty.
Axiom of substitution (page 75): If S(a, b) is a sentence such that for each element a in the set A the set {b : S(a, b)} can be formed, then there exists a function F with domain A such that F(a) = {b : S(a, b)} for each a in A.
I used your axiom list and Zorn’s lemma proof sketch to make Mnemosyne cards. Thanks a bunch!
Thanks for the review.
A more recent book on Set Theory: Basic Set Theory—A. Shen, Independent University of Moscow, and N. K. Vereshchagin, Moscow State Lomonosov University—AMS, 2002, 116 pp., Softcover, ISBN-10: 0-8218-2731-6, ISBN-13: 978-0-8218-2731-4, List: US$24, All AMS Members: US$19.20, STML/17
I found it in the American Mathematical Society for Student’s series, which is highly recommended on mathoverflow.com: http://www.ams.org/bookstore/stmlseries
Thanks for the recommendation! We’ll check it out.
By the way, the Shen’s book takes a different route to the Zorn’s lemma: first he introduces well-ordered sets, then uses tranfinite recursion to prove Zermelo’s theorem (that any set can be well-ordered), then he uses Zermelo’s theorem and tranfinite recursion to prove Zorn’s lemma. Thus the proof of Zorn’s lemma is reduced from two pages to a few lines. I personally found it easier to follow and remember.
Use of these symbols is weakly discouraged in published mathematical writing, as is the use of logical connectives such as ∧,∨, and ⇒. The sentiment seems to be that you generally shouldn’t use symbols from formal logic unless you are actually writing out formulas within an explicitly established formal logical theory, with explicitly establish rules of syntax and inference.
In those terms, what surprised me was that the authors did not explicitly establish a formal logical theory of sets. (I also expected explicit syntax and inference in the proofs.) Is formal-logical set theory frowned upon as well?
As I understand the phrase, it wouldn’t be “naive set theory” if they did that.
Ah, I didn’t know that that “naive” carried the connotation of “non-formal” in this context. This is good to know, thanks.
In my experience, “We’re doing naive set theory” means something like, “We’ll assume, without further justification, that no Russell-style paradox applies to any predicate P where we will actually want to write {x : P(x)}. We’ll just assume the existence of a set answering to this description for any P that we need. We know that there are predicates for which this is not allowed, but we’ll just hope that everything works out okay in the cases where we do it.”
The phrase “naive set theory” also connotes a certain cavalierness about whether the elements in one’s sets are themselves constructed out of sets (as in ZF) or whether instead one is working with urelements (objects in sets that are not themselves sets).
I noticed that the course list doesn’t cover several topics that are popular on LW. Some suggestions:
Game theory—Fudenberg and Tirole
K-complexity—Li and Vitanyi
Causality—Pearl
And maybe something on cryptography, but I don’t know enough about it to recommend a good book.
Do you think Causality is a superior recommendation to Probabilistic Graphical Models?
The material covered in Causality is more like a subset of that in PGM. PGM is like an encyclopedia, and Causality is a comprehensive introduction to one application of PGMs.
Thanks. That was what I thought, but I haven’t read Causality yet.
I haven’t read PGM. Maybe you could ask Ilya Shpitser, he knows this stuff much better than I do.
For cryptography I would recommend Ferguson, Schneier, & Kohno’s Cryptography Engineering. It’s aimed at engineers so it’s not so much the math-oriented text that you might expect from a MIRI course list, but that’s very much on purpose by the authors and in my recommendation. The principle application of cryptography to friendly AI theory is the pragmatic discipline of designing and implementing secure protocols. Most of the lessons to be learned here is not in the math, but rather the right adversarial mindset for thinking about security problems—what Schneier calls “professional paranoia.” Imparting this mindset on new learners of the field was a driving factor for the authors in writing this textbook.
Besides, unless you are a professional cryptographer, you should not be designing your own crypto protocols. And unless you have significant peer review, you should not be using them. The key is to understand the basic fundamentals of the field, internalize the adversarial mindset, and then learn enough math (mostly group theory) to read the academic papers directly.
Actually that’s a quite widespread attitude in the set theory community, not only in that book. Just consider that Hamkins’ proposal of a multiverse (that is, a plurality of models for the axioms of set theory), is considered controversial. Maybe influential to this state of affairs was a more platonist approach of the founders, who regarded ZF(C) as a way to describe the intuititve concept of set instead of just another formal tool.
One of the reasons I think Carnap is underrated (though there’s a welcome revival of late); already way back in the 30s he was preaching “in logic there are no morals!”
Your reviews are fun to read, and as soon as I can get time between assignments and tests to get into a few of the MIRI books I will try to see if I can get through these as well. Thanks for making the effort to write about these.
Nice review! I am actually reading through this one now. I’ve always felt like set theory is one of those one-point wonders of science—digging in deeply doesn’t give you much benefit, but the basic stuff is the stuff you are going to run into pretty much everywhere. Guess I’ll have to see what I think after I read all the way through.