A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The real numbers ℝ are uncountable, meaning no bijection with ℕ exists. Cantor's diagonal argument proves this: assume an enumeration of reals exists, then construct a new real (via the diagonal) that contradicts the enumeration. This technique generalizes to show the power set P(X) is always larger than X.
Work through the decimal-expansion version: list assumed sequence of reals as infinite decimals, modify the diagonal to create a real not on the list. Verify this works even with overcounting concerns (address the 0.999... = 1 subtlety).
You already know what it means for a set to be countable: there exists a bijection between it and the natural numbers ℕ. This means you can list every element in an infinite sequence — first, second, third, and so on — hitting every element eventually. The integers are countable. The rationals are countable (you learned the zig-zag enumeration). So is it possible that every infinite set is countable? Cantor's diagonal argument proves the answer is no — the real numbers ℝ cannot be listed, no matter how clever the listing.
The proof works by contradiction. Suppose someone claims they have listed every real number between 0 and 1: the first real is r₁ = 0.d₁₁d₁₂d₁₃..., the second is r₂ = 0.d₂₁d₂₂d₂₃..., and so on indefinitely. Now construct a new real number x by looking at the diagonal entries — the nth digit of rₙ — and changing each one. If the nth diagonal digit is 5, set the nth digit of x to 6; otherwise set it to 5. The resulting x = 0.x₁x₂x₃... differs from r₁ in the first decimal place, differs from r₂ in the second decimal place, and differs from every rₙ in the nth decimal place. So x is not on the list. But x is a real number between 0 and 1. This contradicts the assumption that the list was complete — so no such list can exist.
The construction is self-referential in a precise and deliberate way. It uses the assumed enumeration against itself, building a counterexample that is guaranteed to escape every entry in the list. Notice this has nothing to do with the specific reals on the supposed list — the diagonal construction works against any list, which is what makes it so powerful. The argument generalizes: given any set X, you can use the same diagonal idea to show that the power set P(X) — the set of all subsets of X — cannot be put in bijection with X. This is Cantor's theorem, your soft prerequisite. Diagonal arguments appear throughout logic and computability theory as a standard technique for proving impossibility results.
Two subtleties are worth addressing. First, the decimal representation of reals is not unique — 0.999... = 1.000... — so you need to choose digits (like 5 and 6) that avoid the boundary cases. This prevents the constructed x from being the other representation of some rₙ. Second, the diagonal argument shows no surjection from ℕ to ℝ exists, which establishes that ℝ is not countable. Showing that |ℕ| < |ℝ| in the strict cardinality sense additionally requires the Cantor-Bernstein-Schroeder theorem to confirm that ℕ and ℝ cannot be in bijection at all — the proof gives you non-surjectivity, and you combine it with the obvious injection ℕ ↪ ℝ to conclude ℝ is strictly larger.