Theory & Concept

A set is countably infinite if it has the same cardinality as ℕ (Chapter 14) — meaning its elements can be listed in a sequence, first, second, third, and so on, eventually reaching any given one. A set is countable if it's finite or countably infinite, and uncountable otherwise. What's surprising is how much survives being countable — but also that something doesn't.

countably infinite: |A| = |ℕ| = ℵ₀ (aleph-null)
countable: finite, or countably infinite

Definition — Surprising Countable Sets, and One Set That Isn't

ℤ is countable: zig-zag through 0,1,−1,2,−2,3,−3,… to list every integer exactly once. ℚ is countable too — a much less obvious fact, provable by arranging fractions in a grid and reading them diagonally.

ℝ, the real numbers, is not countable — proved below by Cantor's 1891 diagonal argument, the single most famous proof in set theory.

Diagram

Reading down the diagonal and changing every digit builds a number that differs from every r_n on the list.

Worked Example

Exhibit a bijection showing ℤ is countable.

Solution. Define f: ℕ → ℤ by alternating between non-negative and negative integers:

f(n) = n/2 if n is even f(n) = −(n+1)/2 if n is odd

This produces the sequence 0, −1, 1, −2, 2, −3, 3, … — every integer appears exactly once, so f is a bijection and ℤ is countable, despite naively "looking twice as big" as ℕ.

Proof

Claim (Cantor, 1891). The interval (0,1) of real numbers is uncountable.

Proof. By contradiction. Suppose (0,1) were countable. Then every real number in (0,1) could be listed as r₁, r₂, r₃, …, each written as an infinite decimal expansion.

Construct a new number x = 0.d₁d₂d₃… by choosing each digit d_n to differ from the n-th digit of r_n (e.g. d_n=5 if r_n's n-th digit isn't 5, otherwise d_n=4).
By construction, x ≠ r₁ (they differ in digit 1), x ≠ r₂ (digit 2), and in general x ≠ r_n for every n (they differ in digit n).
So x is a real number in (0,1) that is not equal to any r_n — meaning x does not appear anywhere in the supposedly complete list.

This contradicts the assumption that r₁, r₂, … listed every real number in (0,1). No such enumeration can exist, so (0,1) — and therefore ℝ itself — is uncountable.

∎