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

I’m re­view­ing the books on the MIRI course list. I fol­lowed Cat­e­gory The­ory with Naïve Set The­ory, by Paul R. Hal­mos.

Naïve Set Theory

Book cover

This book is tiny, con­tain­ing about 100 pages. It’s quite dense, but it’s not a difficult read. I’ll re­view the con­tent be­fore giv­ing my im­pres­sions.

Chap­ter List

  1. The Ax­iom of Extension

  2. The Ax­iom of Specification

  3. Unordered Pairs

  4. Unions and Intersections

  5. Com­ple­ments and Powers

  6. Ordered Pairs

  7. Relations

  8. Functions

  9. Families

  10. In­verses and Composites

  11. Numbers

  12. The Peano Axioms

  13. Arithmetic

  14. Order

  15. The Ax­iom of Choice

  16. Zorn’s Lemma

  17. Well Ordering

  18. Trans­finite Recursion

  19. Or­di­nal Numbers

  20. Sets of Or­di­nal Numbers

  21. Or­di­nal Arithmetic

  22. The Schröder—Bern­stein Theorem

  23. Countable Sets

  24. Car­di­nal Arithmetic

  25. Car­di­nal Numbers


Nor­mally I’d sum­ma­rize each chap­ter, but chap­ters were about four tiny pages each and the con­tent is mostly de­scribed by the chap­ter name. Zorn’s Lemma states that if all chains in a set have an up­per bound, then the set has a max­i­mal el­e­ment. (This fol­lows from the ax­iom of choice.) The Schröder-Bern­stein The­o­rem states that if X is equiv­a­lent to a sub­set of Y, and Y is equiv­a­lent to a sub­set of X, then X and Y are equiv­a­lent. The other chap­ter ti­tles are self-ev­i­dent.

Each chap­ter pre­sented the con­cepts in a con­cise man­ner, then worked through a few of the im­pli­ca­tions (with proofs), then pro­vided a few short ex­er­cises.

None of the con­cepts within were par­tic­u­larly sur­pris­ing, but it was good to play with them first-hand. Most use­ful was in­ter­act­ing with or­di­nal and car­di­nal num­bers. It was nice to ex­am­ine the ac­tual struc­ture of each type of num­ber (in set the­ory) and deepen my pre­vi­ously-su­perfi­cial knowl­edge of the dis­tinc­tion.

Discussion

Be­fore div­ing in to the re­view it’s im­por­tant to re­mem­ber that the use­ful­ness of a math text­book is heav­ily de­pen­dent upon your math back­ground. I have a mod­er­ately strong back­ground. Some spe­cific sub­jects (anal­y­sis, type the­ory, group the­ory, etc.) have given me a solid, if in­di­rect, foun­da­tion in set the­ory. This was the first time I stud­ied set the­ory di­rectly, but the con­cepts were hardly new.

Overview

I was pleased with this book. It is terse. It has ex­er­cises. It gives you in­for­ma­tion and gets out of your way, which is what I like in a text­book: It doesn’t waste your time. I’m about to harp on the book for a spell, but please keep in mind that my over­all feel­ing was pos­i­tive.

Please take these re­views with a grain of salt, as sam­ple size is 1 and I have not read any similar text­books.

Complaints

  • The book was writ­ten in 1960, and it shows. Set the­ory is more ma­ture now than it was then. The au­thors of­ten re­mark on syn­tax that was not yet stan­dard (which is now com­mon­place). The con­tinuum hy­poth­e­sis had not yet been proven un­prov­able in ZFC. The ax­iom of choice is em­braced whole­heart­edly with no dis­cus­sion of weaker var­i­ants. The style of proof differs from the mod­ern style. None of this is bad, per se. In fact, it’s quite a fas­ci­nat­ing time cap­sule: I en­joyed see­ing a slice of math­e­mat­ics from half a cen­tury past. How­ever, I be­lieve a more mod­ern in­tro­duc­tion to set the­ory could have taught me more per­ti­nent math­e­mat­ics in the same amount of time.

  • The no­ta­tion is in­con­sis­tent. I’ve long be­lieved that math is a poor and in­con­sis­tent lan­guage. This is ev­i­dent through­out set the­ory. To the au­thor’s credit, they point out many of the in­con­sis­ten­cies: f(A) can re­fer to both a func­tion or a re­stric­tion of a func­tion to the sub­set A of its do­main, 2^w can re­fer to ei­ther func­tions map­ping w onto 2 or a spe­cific or­di­nal num­ber, etc. I am per­son­ally of the opinion that in­tro­duc­tory text­books should en­force a pure & con­sis­tent syn­tax (which may be re­laxed in prac­tice). I was mildly an­noyed with how the au­thors ac­knowl­edged the in­con­sis­ten­cies and then em­braced them, thereby per­pet­u­at­ing a memetic tragedy of the com­mons. (I know that I shouldn’t ex­pect bet­ter, but one can dream.)

  • The proofs given were pri­mar­ily in en­glish. Not once did the au­thors write ∃ or ∀. They would re­sort to “for some” or “for any” in largely en­glish-lan­guage proofs. The proofs were rigor­ous (the au­thors tightly re­stricted their en­glish phrases), but I was some­what sur­prised to find the ax­ioms of set the­ory de­scribed in lin­gual (rather than sym­bolic) form.

  • Set the­ory is ax­iom soup. I do not view set the­ory as foun­da­tional. Is the ax­iom of choice true? The ques­tion is poorly formed. Ax­ioms are tools to con­strain what you’re talk­ing about. Bet­ter ques­tions are shaped like “does the ax­iom of choice ap­ply to this thing I’m work­ing with?”, or “how does the struc­ture change if we take this state­ment as an ax­iom?”. This sen­ti­ment seems fairly com­mon in mod­ern math­e­mat­ics, but it was lack­ing in Naïve Set The­ory. Ax­ioms were pre­sented as facts, not tools. There was lit­tle ex­plo­ra­tion of each ax­iom, what it cost and what it bought, and what al­ter­nate forms are available.

Most of these gripes are small com­pared to the amount of good data in the book. Re­mem­ber that the book is ti­tled Naïve Set The­ory: a lit­tle naïvety is to be ex­pected. The take­away is that the book was good, but likely could have been bet­ter in light of mod­ern math­e­mat­ics. All in all, the book cov­ers lot of ground at a fast clip, and was quite use­ful.

Should I learn set the­ory?

As always, it de­pends upon your goals. Set the­ory is ev­ery­where in math­e­mat­ics, and I per­son­ally ap­pre­ci­ated shoring up my foun­da­tions. If you have similar goals, you can eas­ily go through this book in a week if you think that learn­ing set the­ory is worth your time.

I don’t par­tic­u­larly recom­mend set the­ory to arm­chair math­e­mat­i­ci­ans. In my ex­pe­rience, other ar­eas of math­e­mat­ics are much more fun from a ca­sual stand­point. (Group the­ory and in­for­ma­tion the­ory come to mind, if you’re look­ing for a good time.)

Should I read this book?

Maybe. I have no point of com­par­i­son here. My ten­ta­tive sug­ges­tion is that you should find a more mod­ern (but similarly terse) in­tro­duc­tory text­book and read that in­stead. (If you have a good sug­ges­tion, you should leave it in the com­ments.)

I found this book to be rather ba­sic. If you have a back­ground similar to mine, I recom­mend some­thing a lit­tle more ad­vanced. (Un­for­tu­nately, I can make no recom­men­da­tions. Again, com­ments are wel­come.)

This book seems well-suited for a layper­son in­ter­ested in learn­ing set the­ory. The 1960s feel is definitely fun. I would guess that the book is well-paced for some­one who has done the stan­dard col­lege calcu­lus courses but is un­fa­mil­iar with Set The­ory sub­ject mat­ter.

What should I read?

If you’re go­ing to read the book then I sug­gest read­ing the whole thing. It builds from first prin­ci­ples up to car­di­nal­ity, and noth­ing along the way is unim­por­tant. My only sug­ges­tion is that you swap chap­ter 25 and 24: they ap­pear to have been or­dered in­cor­rectly for poli­ti­cal rea­sons. (The deriva­tion of car­di­nal num­bers used in chap­ter 25 was, at the time, con­tro­ver­sial, so the book pre­sents car­di­nal ar­ith­metic be­fore car­di­nal num­bers.) Other than that, the book was well struc­tured.

Fi­nal Notes

If a com­pa­rably short-and-sweet text­book writ­ten in the last twenty years can be found, I recom­mend up­dat­ing the sug­ges­tion on the MIRI course list. It’s not clear to me how much raw set the­ory is use­ful in mod­ern AI re­search; my wild guess is that math­e­mat­i­cal logic, model the­ory, and prov­abil­ity the­ory are more im­por­tant. If that is the case, then I think the tech­ni­cal level of this book is ap­pro­pri­ate for the course list: it’s suffi­cient to brush up on the ba­sics, but it doesn’t send you deep into rab­bit holes when there are more in­ter­est­ing top­ics on the hori­zon.

My next re­view will take more time than did the pre­vi­ous four. I have a num­ber of loose ends to tie up be­fore jump­ing in to Model The­ory, and I have much less fa­mil­iar­ity with the sub­ject mat­ter.