Further Reading: Cardinality and Infinity

Annotated pointers for going deeper. Start with the textbook sections to firm up the mechanics (bijections, countability, diagonalization), then follow whichever thread pulls you — the history of Cantor's ideas, the computability payoff, or the set-theoretic frontier (the Continuum Hypothesis).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §2.5 ("Cardinality of Sets") (Tier 1.) The standard reference for this chapter's material: equinumerosity via bijections, countable vs. uncountable, the countability of $\mathbb{Z}$ and $\mathbb{Q}$, and Cantor's diagonal argument for the reals. It also states the Cantor–Schröder–Bernstein theorem (if $\lvert A\rvert \le \lvert B\rvert$ and $\lvert B\rvert \le \lvert A\rvert$ then $\lvert A\rvert = \lvert B\rvert$), which the chapter's Deep Dive path asks you to apply. Use its large graded exercise bank if you want more bijection-building and diagonalization drill than this chapter provides.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), "Infinite Sets" chapter (Tier 1. Freely available.) The most CS-flavored treatment in print. It develops countability, diagonalization, and Cantor–Schröder–Bernstein with the same "this is why some problems have no program" spirit as §10.4, and its exercises lean toward the computational framing this book prefers. The natural companion to this chapter — read it for a second, independent pass over the same arguments.

Sipser, Introduction to the Theory of Computation (3rd ed.), §4.2 ("The Diagonalization Method") (Tier 1.) Reads §10.3 and §10.4 forward into Chapter 36: Sipser uses the very diagonal argument from this chapter to prove that some languages are not Turing-recognizable and that the halting problem is undecidable. This is the single highest-value follow-up — it shows you, concretely, the destination the chapter's "more problems than programs" argument was pointing at all along.

Velleman, How to Prove It (3rd ed.), the chapter on infinite sets (Tier 1.) The gentlest careful treatment of the proof-writing itself — how to set up a bijection cleanly, how to structure a diagonal contradiction so the "differs at digit $n$" step is airtight. If the form of these proofs (rather than the ideas) still feels shaky, this is the standard recommendation; its worked solutions model the rubric this chapter's exercises are graded against.

The countability and uncountability proofs, done slowly

Epp, Discrete Mathematics with Applications (5th ed.), the cardinality sections (Tier 1.) Unusually patient with the part-equals-whole surprise (§10.1) and the grid argument for $\mathbb{Q}$ (§10.2), with many fully worked small cases that hand-trace bijections one element at a time. Reach for this if §10.1's "an infinite set can match a proper subset of itself" still feels like a trick rather than Dedekind's definition.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the cardinality chapter (Tier 1. Freely available.) A free, readable open-source treatment with interactive-style exercises and a clean exposition of the diagonal argument. An excellent zero-cost second pass over countability — and, because it is open-licensed like this book, a good source to quote and remix in study notes.

The historical and conceptual story

Cantor's diagonal argument and the hierarchy of infinities — Stanford Encyclopedia of Philosophy, entries on "Set Theory" and "Continuum Hypothesis" (Tier 2.) Careful, citable scholarly accounts of why Cantor's results were revolutionary and contested, and of the precise status of the Continuum Hypothesis flagged in §10.5. Read for context, not for proof technique.

The independence of the Continuum Hypothesis — Gödel (1940) and Cohen (1963) (Tier 2; attributed.) The result, flagged in §10.5's "honest loose end" callout, that CH can be neither proved nor disproved from the standard axioms of set theory (ZFC). Cohen's forcing method earned the Fields Medal. Sipser and standard set-theory texts give accessible summaries; the original papers are for the determined.

Going deeper (the frontier)

Cantor's theorem, $\lvert S\rvert < \lvert \mathcal{P}(S)\rvert$ for every $S$ — any rigorous set theory text (e.g., Enderton, Elements of Set Theory) (Tier 2; attributed.) The general theorem behind §10.4's special case and Exercise 10.30: the power set is always strictly larger, so there is no largest infinity. The proof is the master diagonal argument of Exercise 10.28.

Aaronson, Quantum Computing Since Democritus, the early chapters on sets and infinities (Tier 2.) A witty, opinionated CS-theorist's tour through Cantor, diagonalization, and their consequences for computation — a lively complement that connects this chapter directly to the limits-of-computation arc.

Suggested order

  1. Re-read §§10.1–10.4 here, then do Rosen §2.5 exercises for drill on bijections and the diagonal argument.
  2. Read the MIT 6.042 "Infinite Sets" chapter for the CS framing and the union/Schröder–Bernstein results.
  3. Read Sipser §4.2 to see §10.3–10.4 turn into the Chapter 36 undecidability proof — this is the single highest-value follow-up.
  4. If the proofs' form is the sticking point, read the Velleman or Epp cardinality chapter alongside.
  5. Save the SEP "Continuum Hypothesis" entry and the Gödel–Cohen story for after the chapter, as orientation toward Part VI's incompleteness and undecidability themes.