Key Takeaways: Cardinality and Infinity
A one-page reference card. Reread it before an exam or before writing a countability/uncountability argument.
The core idea in one line
Size = matching, not counting. Two sets are the same size iff a bijection pairs their elements. This is the only notion of "size" that survives the jump to infinity.
Definitions at a glance
| Term | Definition | Witnessed by |
|---|---|---|
| $\lvert A\rvert = \lvert B\rvert$ (equinumerous) | same cardinality | a bijection $A \to B$ |
| $\lvert A\rvert \le \lvert B\rvert$ | $A$ fits inside $B$ | an injection $A \to B$ |
| $\lvert A\rvert < \lvert B\rvert$ | fits, but no bijection | injection exists, bijection does not |
| countably infinite | matches $\mathbb{N}$ | a list $s_0, s_1, s_2,\dots$ (no repeats, no omissions) |
| countable | finite or countably infinite | a (possibly finite) such list |
| uncountable | not countable | — (every list provably misses an element) |
| $\aleph_0$ | cardinality of a countably infinite set | the smallest infinity |
| continuum $\mathfrak{c}=2^{\aleph_0}$ | cardinality of $\mathbb{R}$ | infinite binary strings / $\mathcal{P}(\mathbb{N})$ |
$\mathbb{N}$ includes 0 in this book. "Countable" = "could be listed off $0,1,2,\dots$ and reach any element in finitely many steps" = enumerable (a generator).
Results proven this chapter
| Statement | Cardinality | Proof engine |
|---|---|---|
| Evens $E$, $\mathbb{N}$ | $\aleph_0$ | bijection $n \mapsto 2n$ |
| $\mathbb{Z}$ | $\aleph_0$ | zig-zag list $0,-1,1,-2,2,\dots$ |
| $\mathbb{N}\times\mathbb{N}$, $\mathbb{Q}$ | $\aleph_0$ | anti-diagonal grid sweep |
| Countable union of countable sets | $\aleph_0$ | grid sweep (rows = sets) |
| $\mathbb{R}$, $[0,1)$ | $\mathfrak{c} > \aleph_0$ | Cantor diagonalization |
| Functions $\mathbb{N}\to\{0,1\}$ = $\mathcal{P}(\mathbb{N})$ | $> \aleph_0$ | diagonal bit-flip $g(n)=1-f_n(n)$ |
| All programs | $\aleph_0$ | strings ordered by length, then alphabetically |
| All problems (decision functions) | $> \aleph_0$ | diagonalization |
| Uncomputable problems exist (almost all) | — | countable $<$ uncountable |
| $\lvert S\rvert < \lvert\mathcal{P}(S)\rvert$ (Cantor's theorem) | — | general diagonal argument |
The two diagonal moves — DO NOT confuse them
| Sweep along anti-diagonals | Walk down the diagonal, disagree |
|---|---|
| Gathers everything into one list | Builds an element on no list |
| Proves countability | Proves uncountability |
| $\mathbb{Q}$, $\mathbb{N}\times\mathbb{N}$, countable unions | $\mathbb{R}$, $\mathcal{P}(\mathbb{N})$, "more problems than programs" |
Decision aid: is set $S$ countable?
Is S finite?
├─ Yes → countable. Done.
└─ No → Can you LIST all of S as s0, s1, s2, ... (no repeats, no omissions)?
├─ Yes → countable (aleph_0). [bijection N -> S]
│ Tactics: zig-zag (two-way), grid sweep (pairs / unions),
│ order strings by length then alphabetically.
└─ Can you show EVERY proposed list misses an element (diagonalize)?
└─ Yes → UNCOUNTABLE. [build x with x_n != (n-th item)_n]
Rule of thumb: finite-alphabet finite-length descriptions ⇒ countable (strings, programs, formulas, proofs). Arbitrary infinite objects ⇒ usually uncountable (reals, subsets of $\mathbb{N}$, functions $\mathbb{N}\to\{0,1\}$, infinite bit-streams).
Cantor diagonalization — the template
- Assume the set is countable: list it $r_0, r_1, r_2, \dots$ (proof by contradiction).
- Write each $r_n$ as a sequence of symbols; look at the diagonal entry $(n,n)$.
- Build $x$ with $x_n \ne (\text{diagonal entry of } r_n)$ for every $n$ (digits: use $\{4,5\}$; bits: flip $1-f_n(n)$).
- $x$ differs from every $r_n$ ⇒ $x$ is on no list ⇒ contradiction ⇒ uncountable. $\blacksquare$
$\aleph_0$ arithmetic (mocks finite intuition)
$$\aleph_0 + 1 = \aleph_0, \qquad \aleph_0 + \aleph_0 = \aleph_0, \qquad \aleph_0 \cdot \aleph_0 = \aleph_0.$$ Absorbing a countable amount into a countable set changes nothing (Hilbert's Hotel). But $2^{\aleph_0} = \mathfrak{c} > \aleph_0$, and $\lvert S\rvert < \lvert\mathcal{P}(S)\rvert$ always — an endless tower of infinities, no largest one.
Common pitfalls
- "A proper subset is always smaller." False for infinite sets — $E \subset \mathbb{N}$ but $\lvert E\rvert = \lvert\mathbb{N}\rvert$. Trust the bijection, not the picture.
- "Just add the missing $x$ to the list." Re-diagonalizing the patched list yields a new escapee. The proof defeats all lists at once.
- "$\mathbb{Q}$ is dense, so it's bigger than $\mathbb{N}$." Density ≠ larger cardinality; $\mathbb{Q}$ is countable. A countable set can be dense in an uncountable one.
- Confusing the two diagonals (sweep-to-collect vs. walk-to-escape).
- Forgetting expansion uniqueness in the real proof (ban all-9s tails; keep $x$'s digits in $\{4,5\}$) — else "different digits" might not mean "different number."
Why a programmer cares
- Uncomputable problems exist (Ch. 36 halting problem) — programs countable, problems uncountable.
- Floating-point: $\sim 2^{64}$
doubles (countable) approximate uncountable $\mathbb{R}$ ⇒ rounding error is unavoidable. - Almost every real is undescribable — finite descriptions are countable.
- No language is universal over all functions $\mathbb{N}\to\mathbb{N}$ (uncountably many).
Toolkit addition
cardinality.py:
- cantor_pair(i, j) / cantor_unpair(n) — a bijection $\mathbb{N}\times\mathbb{N}
\leftrightarrow \mathbb{N}$ (engine of "$\mathbb{Q}$ is countable").
- diagonal_escape(rows) — a row differing from each input row on its diagonal (the literal kernel of
the Chapter 36 undecidability proof).