For finite sets, counting is easy. With infinite sets intuition stops working: are there more natural numbers than even numbers? More fractions than integers? The answer, given by Georg Cantor in the late nineteenth century, is surprising and has direct consequences for computing: there are infinities of different sizes, and this implies that there are problems no program can solve.
Comparing sets without counting them
Two sets have the same cardinality if there is a bijection between them, that is, a correspondence that pairs each element of the first with exactly one element of the second, and vice versa, leaving nobody out.
This is the most primitive way to compare quantities: to know whether a room has as many chairs as people you don't need to count them, just ask everyone to sit down and see whether chairs or people are left over. The definition works even when counting is impossible.
Surprises with countable infinities
A set is countable if it has the same cardinality as the natural numbers ℕ = {0, 1, 2, …}. In practice: if its elements can be arranged in an infinite list, first, second, third, in which every element eventually appears.
The even numbers
The function f(n) = 2n maps 0 → 0, 1 → 2, 2 → 4, and so on. It is a bijection between ℕ and the even numbers. So the evens are "as many as" the naturals, even though they are a proper subset. This is a distinguishing feature of infinite sets: they can have the same cardinality as a part of themselves.
The integers
ℤ can be listed by alternating signs: 0, 1, −1, 2, −2, 3, −3, … Every integer appears at a definite position, so ℤ is countable too.
The rationals
Here intuition resists, because between any two fractions there are infinitely many others. Yet ℚ is also countable. Arrange the positive fractions p/q in an infinite table, with p on the rows and q on the columns, and walk the diagonals: first those with p + q = 2, then p + q = 3, then p + q = 4, skipping unreduced fractions that represent values already seen.
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, …
Every positive fraction eventually appears, because it has a finite sum p + q. Adding zero and the negatives with the alternating trick gives a list of all rationals.
Finite strings
The set of all finite strings over a finite alphabet is countable as well: list those of length 0 first, then those of length 1 in alphabetical order, then those of length 2, and so on. Every computer program is a finite string, so the possible programs form a countable infinity.
The diagonal argument
The real numbers are not countable. It is enough to prove this for the reals between 0 and 1, and it is done by contradiction.
Suppose we have a complete list r₁, r₂, r₃, … of all reals in (0, 1), written in decimal form:
r₁ = 0. 5 1 4 0 …
r₂ = 0. 3 3 3 3 …
r₃ = 0. 7 1 8 2 …
r₄ = 0. 0 0 9 1 …
Build a number d by choosing its n-th digit to differ from the n-th digit of rₙ. For example: if the digit on the diagonal is 5, use 4; otherwise use 5. Here the diagonal is 5, 3, 8, 1, so d = 0.4555…
The number d differs from r₁ in the first digit, from r₂ in the second, from rₙ in the n-th. So it is none of the numbers on the list, which therefore was not complete. Contradiction. (Using only the digits 4 and 5 avoids the ambiguity of numbers such as 0.1999… = 0.2000….)
The same pattern proves a more general fact: for every set A, the power set 𝒫(A) has strictly greater cardinality than A. There is no largest infinity.
Why a computer scientist should care
The set of decision problems on the natural numbers corresponds to the set of subsets of ℕ, which is not countable. Programs, as we have seen, form only a countable infinity. So there are problems for which no program can give the answer: there are simply not enough programs to cover them all.
This argument does not say which problems they are; to find a concrete one, such as the halting problem, a version of the diagonal argument is applied to programs themselves. But the simple comparison of cardinalities already shows that the uncomputable is not an exception: it is the rule.
In short
- Two sets have the same cardinality if there is a bijection between them.
- Evens, integers, rationals and finite strings are all countable, that is, listable.
- The real numbers are not countable: the diagonal argument always builds a missing number.
- For every set, the power set is strictly larger.
- Programs are countable, problems are not: some problems cannot be solved by any program.
