JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Countable, Uncountable & Cantor's Diagonal

Some infinities are bigger than others. Use bijections to define countability, watch ℚ turn out countable, then meet Cantor's diagonal argument — the one-page proof that the real numbers cannot be listed.

What countable means

A set is [[countable-set|countable]] if it is finite or can be put in [[bijection|bijection]] with the natural numbers ℕ. Concretely, countable means listable: you can arrange the elements in a sequence a₀, a₁, a₂, … so that every element appears at some finite position. The naturals, the integers, and even the rationals are all countable — they have the same [[cardinality|cardinality]], written ℵ₀, despite the rationals being [[density-of-the-rationals|dense]] while the integers are spread out.

Why the rationals Q are countable: a snake through a grid.

List positive rationals p/q in a table, row p, column q:

        q=1    q=2    q=3    q=4   ...
  p=1   1/1    1/2    1/3    1/4
  p=2   2/1    2/2    2/3    2/4
  p=3   3/1    3/2    3/3    ...
  p=4   4/1    ...

Traverse it along finite diagonals (p+q = 2, then 3, then 4, ...):
  1/1 , 1/2 , 2/1 , 1/3 , 2/2 , 3/1 , 1/4 , ...
Skip any fraction not in lowest terms (2/2 already seen as 1/1).
Every positive rational sits on exactly one diagonal, so it
appears at some finite step. Interleave with 0 and negatives:
  0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, ...
That is an explicit listing of ALL of Q. Hence Q is countable.
Sweeping finite diagonals lists every rational, so the dense set ℚ is still only ℵ₀.

Cantor's diagonal argument

Now the turn. The real numbers are [[uncountable-set|uncountable]]: there is no list that catches them all. The proof is [[cantor-diagonal-argument|Cantor's diagonal argument]], and it is by contradiction. Suppose, for contradiction, that every real in [0, 1) could be listed as x₀, x₁, x₂, …. We will manufacture a real that is provably missing from your list, contradicting the assumption that the list was complete.

Cantor's diagonal argument (proof by contradiction).

Assume ALL reals in [0,1) are listed by their decimal digits:

   x0 = 0 . d00 d01 d02 d03 ...
   x1 = 0 . d10 d11 d12 d13 ...
   x2 = 0 . d20 d21 d22 d23 ...
   x3 = 0 . d30 d31 d32 d33 ...
             ^
   the diagonal digits are d00, d11, d22, d33, ...

Build a new number  y = 0 . e0 e1 e2 e3 ...  by the rule
   e_k = 5  if d_kk is not 5
   e_k = 4  if d_kk is 5
(any rule avoiding 0 and 9 dodges the 0.4999...=0.5000... issue).

Then y differs from x_k in its k-th digit, for EVERY k:
   e_k != d_kk  by construction.
So y is not x0, not x1, not x2, ... -- y is on NO row.
But y is a real in [0,1), so the list was not complete.
Contradiction. Therefore [0,1), and hence R, is uncountable.
Changing every diagonal digit builds a real that disagrees with each listed row — so no list is complete.

Pause on the elegance. The diagonal number y is engineered to disagree with row k at position k, so it cannot be any row. The conclusion is permanent: ℝ — [[the-continuum|the continuum]] — has a strictly larger cardinality than ℕ. There are genuinely more real numbers than rationals, even though both are infinite. This is the moment infinity stops being a single idea and becomes a hierarchy.