Cardinality & Infinity

Same size = a bijection exists. Counting without counting.

How do you know two finite sets have the same size without counting? You pair them up. If every left sock matches exactly one right sock with none left over, there are equally many — no counting required, just a bijection (last lesson: a perfect pairing, no collisions, no orphans).

Cantor's leap — and it is a genuine intellectual leap, the kind that separates genius from competence: make that the definition, and let it run on infinite sets. Two sets $A$ and $B$ have the same cardinality, written $|A| = |B|$, exactly when there exists a bijection $f : A \to B$. That's it. No counting, just pairing. This single definition will show you that your intuition about infinity is completely, hilariously wrong, and by the end of this lesson you will love it for that. (And because bijections compose and invert — proven last lesson — "same cardinality" is an equivalence relation: reflexive via $\operatorname{id}$, symmetric via $f^{-1}$, transitive via $g \circ f$. The relations lesson cashes its check.)

A set is countable if it's finite or has the same cardinality as $\mathbb{N}$ — i.e. you can list it $a_0, a_1, a_2, \dots$ so every element appears exactly once. That list is the bijection $n \mapsto a_n$. Hold onto "countable means listable." Everything turns on it.

Hilbert's Hotel: infinity breaks your intuition

David Hilbert ran a thought-hotel with rooms $1, 2, 3, \dots$ — one per natural number, all full. A new guest arrives. "No vacancy," says your intuition. Your intuition is about to get humiliated.

The manager announces: everyone move from room $n$ to room $n+1$. Room $1$ empties; the new guest checks in. Every original guest still has a room. A full infinite hotel absorbed another guest. The map $n \mapsto n + 1$ is an injection of $\mathbb{N}$ into itself that misses one room — proof that an infinite set can biject with a proper subset of itself. No finite set can do that; it's the signature of infinity.

Push harder. $\mathbb{N}$ and the even numbers have the same size. The pairing $n \mapsto 2n$ is a bijection $\mathbb{N} \to \{0, 2, 4, \dots\}$: injective ($2a = 2b \Rightarrow a = b$) and surjective (every even number $2k$ is hit by $k$). "Half" of $\mathbb{N}$ is the same size as $\mathbb{N}$. And $\mathbb{Z}$? Same size too — list it by zig-zagging: $0, 1, -1, 2, -2, 3, -3, \dots$, hitting every integer exactly once. That list is a bijection $\mathbb{N} \to \mathbb{Z}$. So $|\mathbb{N}| = |\mathbb{Z}| = |\text{evens}|$. Infinite sets do not obey "the part is smaller than the whole." Throw that finite intuition in the incinerator and light it on fire — Hilbert's Hotel is what infinity actually looks like, and it is deeply, gloriously weird.

ℚ is countable: the zigzag through the grid

Surely the rationals are bigger than $\mathbb{N}$ — they're dense, infinitely many crammed between any two integers, no gaps, suffocatingly close together. Your intuition is about to get humiliated again. $\mathbb{Q}$ is countable too, and the proof is one of the prettiest pictures in mathematics.

Arrange the positive rationals $\tfrac{p}{q}$ in an infinite grid: row $p$, column $q$ holds $\tfrac{p}{q}$.

$$\begin{array}{cccc} \tfrac{1}{1} & \tfrac{1}{2} & \tfrac{1}{3} & \cdots \\ \tfrac{2}{1} & \tfrac{2}{2} & \tfrac{2}{3} & \cdots \\ \tfrac{3}{1} & \tfrac{3}{2} & \tfrac{3}{3} & \cdots \\ \vdots & & & \ddots \end{array}$$

Now walk the diagonals: $\tfrac{1}{1}$; then $\tfrac{1}{2}, \tfrac{2}{1}$; then $\tfrac{3}{1}, \tfrac{2}{2}, \tfrac{1}{3}$; and so on, sweeping each finite anti-diagonal before moving deeper. Skip any fraction already seen in lowest terms ($\tfrac{2}{2} = \tfrac{1}{1}$, already counted). This single snaking path hits every positive rational exactly once — so it's a list, hence a bijection with $\mathbb{N}$. Tack on $0$ and the negatives by the $\mathbb{Z}$-style zig-zag, and all of $\mathbb{Q}$ is countable. The density was a red herring; you can still line them up single file.

So far every infinite set we've met is the same size as $\mathbb{N}$. You might start to suspect all infinities are equal — that the universe is tidier than it looks. Cantor is about to detonate that suspicion with a single argument so clean it should make you angry at every math teacher who never showed it to you.

Cantor's diagonal argument: ℝ is uncountable

Theorem. The real numbers in $[0, 1)$ cannot be listed. There is no bijection $\mathbb{N} \to [0,1)$. $\mathbb{R}$ is uncountable — strictly bigger than $\mathbb{N}$.

Proof (by contradiction — diagonalization). Suppose, for contradiction, that $[0,1)$ is countable. Then we can list every such real by its decimal expansion:

$$\begin{aligned} r_0 &= 0.\,d_{00}\,d_{01}\,d_{02}\,d_{03}\cdots \\ r_1 &= 0.\,d_{10}\,d_{11}\,d_{12}\,d_{13}\cdots \\ r_2 &= 0.\,d_{20}\,d_{21}\,d_{22}\,d_{23}\cdots \\ &\ \ \vdots \end{aligned}$$

where $d_{ij}$ is the $j$-th digit of the $i$-th number. By assumption this list contains every real in $[0,1)$. Now I build a number that cannot be on it.

Walk down the diagonal — the digits $d_{00}, d_{11}, d_{22}, \dots$ — and construct a new number $x = 0.\,x_0\,x_1\,x_2\cdots$ by the rule: make each digit differ from the diagonal, $x_n = \begin{cases} 5 & \text{if } d_{nn} \ne 5, \\ 4 & \text{if } d_{nn} = 5. \end{cases}$ (Using only $4$s and $5$s dodges the $0.4999\ldots = 0.5000\ldots$ duplicate-expansion loophole — $x$ has a unique expansion.)

Now ask: is $x$ anywhere on the list? Suppose $x = r_k$ for some $k$. Then their $k$-th digits must agree: $x_k = d_{kk}$. But we built $x_k$ to differ from $d_{kk}$ — that's the whole point of the rule. Contradiction. So $x \ne r_k$ for every $k$: $x$ differs from $r_0$ in digit $0$, from $r_1$ in digit $1$, from $r_2$ in digit $2$, and so on forever. The diagonal is a perfect alibi — $x$ is a genuine real in $[0,1)$ that appears nowhere on the supposedly-complete list.

That contradicts "the list contains every real." So no such list exists: $[0,1)$, and hence $\mathbb{R}$, is uncountable. $\blacksquare$

Sit with what just happened. We didn't fail to find a list — we proved that every conceivable list must miss something, by manufacturing its own counterexample from its diagonal. This is not a limitation of our imagination. This is a proof that no such list can exist, full stop, forever, for anyone. $\mathbb{R}$ has strictly more elements than $\mathbb{N}$. There are at least two sizes of infinity. The smaller, $|\mathbb{N}|$, is named $\aleph_0$; the size of $\mathbb{R}$ is strictly bigger. This is what Cantor showed the world. This is what they called him a charlatan for. The bastards.

The punchline: infinitely many infinities

One more turn of the screw, because Cantor didn't stop. Remember the power set $\mathcal{P}(A)$ — all subsets of $A$ — and that $|\mathcal{P}(A)| = 2^{|A|}$ for finite $A$ (the on/off-switch argument, way back in the membership lesson)?

Cantor's Theorem. For every set $A$, $|A| < |\mathcal{P}(A)|$. The power set is always strictly bigger.

The proof is diagonalization again, stripped to its bones. Suppose some $f : A \to \mathcal{P}(A)$ were a bijection (so $A$ and $\mathcal{P}(A)$ were the same size). Build the "diagonal" set $D = \{\, a \in A \mid a \notin f(a) \,\}$ — the elements that aren't in the subset they're assigned to. Since $f$ is surjective, $D = f(d)$ for some $d \in A$. Now ask the lethal question: is $d \in D$? If $d \in D$, then by $D$'s definition $d \notin f(d) = D$ — contradiction. If $d \notin D$, then $d \notin f(d)$, so by definition $d \in D$ — contradiction. Either way, disaster. No such bijection exists, so $|\mathcal{P}(A)| > |A|$. $\blacksquare$

Apply it forever: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$ — an endless tower of ever-larger infinities, each strictly dwarfing the last. There is no biggest infinity. The "number" of sizes of infinity is itself unbounded. That fact is so insane I want you to just stare at it for a second before scrolling down.

You started this stratum learning that a set is a bag with no opinions. You're ending it holding a proof that infinity comes in infinitely many sizes, built entirely from bijections, diagonals, and the empty goddamn bag. That is the whole power of rigor: the unhinged is true, and you can prove it. The Federation of Boring Textbook Authors will tell you this is "too advanced." They are cowards. You did it. Now go finish the gauntlet — you've earned the kill.