Further Reading: Sets

Annotated pointers for going deeper. Start with the textbook sections to shore up the basics, then branch toward whatever pulls you — the logic underneath set identities, the data-structure side in code, or the surprising foundations (Russell's paradox and the axioms that tame it).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §2.1–2.2 The market-standard treatment of set notation, subsets, power sets, Cartesian products, and the set operations, with a large, well-graded exercise bank and clear Venn-diagram coverage. If you want more drill than this chapter provides — especially on set identities — this is the place.

Epp, Discrete Mathematics with Applications (5th ed.), the sets chapter Unusually careful about proof technique for set identities: Epp drills the element method (the §8.5 skill) more explicitly than most books and is excellent on the empty-set and vacuous-truth subtleties that trip students in 8.1–8.2.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the sets chapter Freely available. A clean, readable open-source treatment with good exercises and a relaxed tone. A fine free companion if you want a second explanation of subsets, power sets, and Venn diagrams.

On the logic underneath set identities

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the sets material Freely available. The most CS-flavored presentation in print, and the closest in spirit to this chapter's "set theory is logic with a universe attached" framing (§8.3). Read it to see set operations and proofs developed hand-in-hand with the propositional logic of Part I.

Velleman, How to Prove It (3rd ed.), the chapters on sets and on quantified statements The gentlest careful treatment of proof-writing anywhere. Its sections on proving subset and set-equality claims pair perfectly with §8.5; if the form of an element-method proof still feels shaky, this is the standard recommendation.

On the foundations (Russell's paradox and the axioms)

Halmos, Naive Set Theory The classic, slim, readable introduction to the axiomatic underpinnings — what a set "really" is, how the axioms are stated, and why "the set of all sets" is not allowed. The natural next step after Exercise 8.29 (Russell's paradox); short enough to read in a weekend.

Enderton, Elements of Set Theory A more thorough, still-accessible axiomatic treatment for readers who want the full Zermelo–Fraenkel story behind the paradox, ordered pairs as sets, and the construction of the number systems from §8.1.

On sets in code

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the hashing chapter The canonical reference for why set membership is average $O(1)$: hash tables, hash functions, and collisions — the machinery §8.6 promised we would study later. Read it when you want the engineering behind the "fast membership" contract.

The Python documentation: "Set Types — set, frozenset" Free online. The authoritative reference for Python's set and frozenset, including the operator table (|, &, -, ^) used throughout this chapter and the hashability rules that force frozenset for sets of sets. Keep it open while doing the Part C exercises.

Suggested order

  1. Re-read §§8.1–8.5 here, then do Rosen §2.1–2.2 (and a few of Epp's element-method proofs) for drill on set identities.
  2. Read the MIT 6.042 sets material to reinforce the logic-and-sets connection from §8.3.
  3. Skim the Python set/frozenset docs before (or during) the Part C "implement it" exercises.
  4. Save Halmos's Naive Set Theory for after Exercise 8.29 — it answers "but what is a set, really?" and sets up the infinite-cardinality story you will meet a couple of chapters later.