Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Book Review: Naïve Set Theory (MIRI course list)

31 Post author: So8res 30 September 2013 04:09PM

I'm reviewing the books on the MIRI course list. I followed Category Theory with Naïve Set Theory, by Paul R. Halmos.

Naïve Set Theory

Book cover

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

  1. The Axiom of Extension
  2. The Axiom of Specification
  3. Unordered Pairs
  4. Unions and Intersections
  5. Complements and Powers
  6. Ordered Pairs
  7. Relations
  8. Functions
  9. Families
  10. Inverses and Composites
  11. Numbers
  12. The Peano Axioms
  13. Arithmetic
  14. Order
  15. The Axiom of Choice
  16. Zorn's Lemma
  17. Well Ordering
  18. Transfinite Recursion
  19. Ordinal Numbers
  20. Sets of Ordinal Numbers
  21. Ordinal Arithmetic
  22. The Schröder—Bernstein Theorem
  23. Countable Sets
  24. Cardinal Arithmetic
  25. 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.

Comments (19)

Comment author: EvelynM 30 September 2013 05:13:19PM 7 points [-]

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

Comment author: lukeprog 30 September 2013 06:17:37PM 2 points [-]

Thanks for the recommendation! We'll check it out.

Comment author: robot-dreams 01 September 2014 06:16:18PM *  6 points [-]

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.
Comment author: lukeprog 30 September 2013 09:12:13PM 16 points [-]

These book reviews are badass.

That is all.

Comment author: cousin_it 30 September 2013 06:31:35PM *  5 points [-]

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.

Comment author: [deleted] 02 October 2013 05:20:42AM *  1 point [-]

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.

Comment author: Louie 03 October 2013 07:52:49PM 0 points [-]

Do you think Causality is a superior recommendation to Probabilistic Graphical Models?

Comment author: Alex_Altair 03 October 2013 08:16:54PM 1 point [-]

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.

Comment author: Louie 05 October 2013 08:36:42AM 1 point [-]

Thanks. That was what I thought, but I haven't read Causality yet.

Comment author: cousin_it 03 October 2013 07:57:27PM *  0 points [-]

I haven't read PGM. Maybe you could ask Ilya Shpitser, he knows this stuff much better than I do.

Comment author: Tyrrell_McAllister 30 September 2013 06:07:37PM *  5 points [-]

Not once did the authors write ∃ or ∀.

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.

Comment author: So8res 30 September 2013 06:45:47PM *  1 point [-]

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?

Comment author: Tyrrell_McAllister 30 September 2013 07:09:58PM 7 points [-]

As I understand the phrase, it wouldn't be "naive set theory" if they did that.

Comment author: So8res 30 September 2013 07:49:36PM 3 points [-]

Ah, I didn't know that that "naive" carried the connotation of "non-formal" in this context. This is good to know, thanks.

Comment author: Tyrrell_McAllister 30 September 2013 08:36:28PM *  8 points [-]

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).

Comment author: MrMind 01 October 2013 12:45:37PM *  3 points [-]

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

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.

Comment author: Protagoras 01 October 2013 02:20:57PM -1 points [-]

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!"

Comment author: nitrat665 08 April 2015 07:26:42PM 0 points [-]

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.

Comment author: [deleted] 07 October 2013 07:41:38AM 0 points [-]

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.