Countable and Uncountable Sets

Are there different sizes of infinity? Until 1874, mathematicians implicitly treated "infinite" as a single, undifferentiated label — an infinite set was simply "not finite," with no further structure. Then Georg Cantor proved that the set of real numbers cannot be put in bijection with the natural numbers, no matter how clever the proposed listing. His proof — the diagonal argument — is one of the most influential ideas in modern mathematics. It splits infinity into a hierarchy: $\aleph_0$ for the countable infinities ($\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$) and strictly larger cardinalities for sets like $\mathbb{R}$ and $\mathcal{P}(\mathbb{N})$. The same diagonal trick later powered Russell's paradox, Gödel's incompleteness theorems, and Turing's undecidability of the halting problem — arguably the three deepest results of 20th-century logic.

$\mathbb{Q}$ is countable

The rationals are dense in $\mathbb{R}$ — between any two reals you can find infinitely many rationals — yet surprisingly they are still countable. The standard trick lists the positive rationals on a two-dimensional grid: cell $(m, n)$ holds $m/n$. Then we traverse the grid diagonally:

Skipping duplicates (e.g., $2/2 = 1/1$), we obtain an enumeration of $\mathbb{Q}^{+}$. Interleaving with negatives and zero gives an enumeration of $\mathbb{Q}$. Therefore $|\mathbb{Q}| = \aleph_0$.

Cantor's diagonal argument: $\mathbb{R}$ is uncountable

Theorem (Cantor, 1891). The open interval $(0, 1)$ is uncountable; consequently so is $\mathbb{R}$.

Proof. Suppose for contradiction that some function $f \colon \mathbb{N} \to (0, 1)$ is a surjection (enumerates every real in $(0, 1)$). Write each $f(n)$ in decimal:

(and so on, where $d_{ij}$ is a decimal digit). Now construct the number $x = 0.x_0 x_1 x_2 \ldots$ by the diagonal rule: pick $x_n$ to be any digit different from $d_{nn}$ — say $x_n = 5$ if $d_{nn} \neq 5$, otherwise $x_n = 6$ (this also avoids the $0.999\ldots = 1.000\ldots$ ambiguity).

Then $x \in (0, 1)$, but $x \neq f(n)$ for every $n$, because $x$ and $f(n)$ differ in the $n$-th decimal place. So $f$ cannot be surjective — contradiction. Therefore no such enumeration exists, and $(0, 1)$ is uncountable. $\blacksquare$

The cardinality of $\mathbb{R}$ is denoted $\mathfrak{c}$ ("the continuum") and we have just proved $\aleph_0 < \mathfrak{c}$. There is no biggest infinity either: Cantor's theorem says $|A| < |\mathcal{P}(A)|$ for every set $A$, so the chain $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$ never terminates.

Closure properties of countability

A handful of facts together justify nearly all countability proofs in practice:

• Every subset of a countable set is countable.
• A countable union of countable sets is countable (use the same diagonal trick on a list of lists).
• $\mathbb{N} \times \mathbb{N}$ is countable (Cantor's pairing function from the previous section).
• The set of finite strings over a finite alphabet is countable — the basis for "there are only countably many programs."
• The set of all infinite binary sequences ${0, 1}^{\mathbb{N}}$ is uncountable, by exactly the same diagonal argument.

Pause and think: The rationals $\mathbb{Q}$ are dense in $\mathbb{R}$ — between any two reals there are infinitely many rationals. Yet $|\mathbb{Q}| = \aleph_0 < \mathfrak{c} = |\mathbb{R}|$. How can a dense subset be strictly smaller? (Hint: "dense" is about topological distribution, not about cardinality. The set $\mathbb{Q}$ has plenty of "room" between every pair of reals, but it skips over uncountably many irrationals at every point.)

Try it

• Before reading further: a friend hands you the "list" $f(0) = 0.1234\ldots$, $f(1) = 0.5678\ldots$, $f(2) = 0.9012\ldots$. Construct a real in $(0, 1)$ not on the list by changing the diagonal digits. Then explain why your construction always works, no matter what list is presented.
• Predict first: is the set of algebraic real numbers (roots of polynomials with integer coefficients) countable or uncountable? Why?
• The set of all infinite binary sequences ${0, 1}^{\mathbb{N}}$ is uncountable. Adapt the diagonal argument from decimals to binary sequences.
• Prove that the irrationals are uncountable. (Hint: write $\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q})$ and use that a countable union of countable sets is countable.)
• The set of finite subsets of $\mathbb{N}$ is countable; the set of all subsets of $\mathbb{N}$ is uncountable. Where does the boundary lie? (Think about the difference between finite descriptions and infinite ones.)

A trap to watch for

Beginners often mentally translate "uncountable" as "really really big finite." That is wrong on two levels. First, an uncountable set is not finite at all — it has infinitely many elements. Second, "uncountable" is a specific structural claim: there is no surjection $\mathbb{N} \twoheadrightarrow A$ at all, no matter how the elements are arranged. It is not that the listing would be "too long"; it is that every listing must miss something (and Cantor's diagonal explicitly produces the missing element). The right mental model is not "more numerous" but "structurally beyond enumeration." This is also why $\mathbb{Q}$ being dense in $\mathbb{R}$ does not make $\mathbb{Q}$ uncountable: density is geometric, countability is combinatorial, and the two notions can disagree.

What you now know

You can prove $\mathbb{Q}$ countable by an explicit enumeration, prove $\mathbb{R}$ uncountable via Cantor's diagonal argument, and apply the closure facts (subsets and countable unions of countable sets remain countable; $\mathcal{P}(A)$ always strictly exceeds $A$). In the final section we get the most powerful tool for comparing infinite cardinalities — the Cantor-Schröder-Bernstein theorem — which lets us conclude $|A| = |B|$ from a pair of injections without ever constructing a bijection explicitly.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 8.
• Cantor, G. (1891). "Über eine elementare Frage der Mannigfaltigkeitslehre." Jahresbericht der Deutschen Mathematiker-Vereinigung, 1, 75–78.
• Halmos, P. R. (1960). Naive Set Theory. Springer.
• Jech, T. (2003). Set Theory: The Third Millennium Edition. Springer.
• Aigner, M., Ziegler, G. M. (2018). Proofs from THE BOOK (6th ed.). Springer (Cantor diagonal chapter).