Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 38 · Countable and Uncountable Sets

The Rationals Are Countable

Prove that N×N and the rational numbers are countable using the Cantor pairing function and the Calkin–Wilf sequence, with working Python code.

Between any two fractions there are infinitely many more fractions. So it feels as if the rational numbers must be a vastly larger collection than the whole numbers. Cantor's surprising discovery in 1873 is that they are not: the rationals can be listed in a single sequence, so |ℚ| = ℵ₀.

The proof has two steps. First show that pairs of natural numbers can be listed; then show that fractions are pairs.

Listing pairs: ℕ × ℕ

We want a bijection ℕ × ℕ → ℕ. Draw the pairs (a, b) in a grid and walk along the diagonals a + b = 0, a + b = 1, a + b = 2, and so on:

Text
(0,0)
(1,0) (0,1)
(2,0) (1,1) (0,2)
(3,0) (2,1) (1,2) (0,3)
...

Each diagonal is finite, so every pair is reached after finitely many steps. This is Cantor's pairing function:

Text
π(a, b) = (a + b)(a + b + 1) / 2 + b

The term (a + b)(a + b + 1)/2 is the number of pairs on earlier diagonals (the triangular number), and b is the position along the current one.

Python Cantor pairing function and its inverse

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

So ℕ × ℕ is countable, which proves ℵ₀ · ℵ₀ = ℵ₀. A useful consequence: a countable union of countable sets is countable, since the union is the image of a set of pairs (i, j) ("the j-th element of the i-th set"). A careful proof needs the axiom of choice to pick a listing for each set in advance, but for sets that come with explicit listings, no choice is needed.

From pairs to fractions

Every positive rational is p/q with p, q positive integers. So ℚ⁺ injects into ℕ × ℕ by p/q ↦ (p, q). Since ℕ × ℕ is countable, so is ℚ⁺. Then ℚ = ℚ⁺ ∪ {0} ∪ (negatives) is the union of three countable sets, so ℚ is countable. Since ℕ injects into ℚ, the cardinality is exactly ℵ₀.

The injection route does not produce a listing without repeats (1/2 and 2/4 both appear). That is fine for a proof, but it is nicer to have an actual list.

The Calkin–Wilf sequence: every fraction once

In 2000 Neil Calkin and Herbert Wilf described a sequence that lists every positive rational exactly once, already in lowest terms. Start with 1 and apply

Text
next(x) = 1 / (2·⌊x⌋ - x + 1)

where ⌊x⌋ is the integer part of x. The sequence begins 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, .... A neat side fact: the numerators form Stern's diatomic sequence, and each term's denominator is the next term's numerator. We only need that it lists every fraction once.

Python Generate every positive rational once

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because each positive rational appears at some finite position, you can read off an explicit position for any fraction. That is the bijection ℕ → ℚ⁺.

A listing of all rationals

Combine the Calkin–Wilf sequence with the integer trick from countable sets: list 0, then x₁, -x₁, x₂, -x₂, ..., where x₁, x₂, ... is the Calkin–Wilf sequence.

Python List all rationals, positive and negative

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Countable does not mean "easy to order by size". No listing of ℚ can follow the usual order, because between any two rationals there is another one. A list is an order of enumeration (a first, second, third...), not the order < on numbers.

Why this is surprising, and why it is true

Density suggests the rationals have "more" points than the integers, but density is about order, and cardinality is about matching. The rationals are dense in the number line and still match perfectly with the counting numbers. The same idea shows that the algebraic numbers (roots of integer polynomials) and the set of all finite strings over a finite alphabet are countable.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is π(1, 2) in Cantor's pairing function π(a, b) = (a+b)(a+b+1)/2 + b?

    a + b = 3, so (3·4)/2 + 2 = 6 + 2 = 8.
  2. 2. Why does a bijection ℕ × ℕ → ℕ prove ℵ₀ · ℵ₀ = ℵ₀?

    Cardinal multiplication is defined as the size of A × B, and a bijection to ℕ shows that size is ℵ₀.
  3. 3. What makes the Calkin–Wilf sequence special?

    Each positive rational appears exactly once and in lowest terms. It is not in increasing order.
  4. 4. Can the rationals be listed in increasing order, r₀ < r₁ < r₂ < ...?

    A listing is not an ordering by size. In the usual order, between any two rationals lies another, so no increasing list covers them.

Summary

  • The Cantor pairing function π(a, b) = (a+b)(a+b+1)/2 + b is a bijection ℕ × ℕ → ℕ, so ℵ₀ · ℵ₀ = ℵ₀.
  • Every rational is a pair of integers, so ℚ is countable.
  • The Calkin–Wilf sequence lists each positive rational exactly once.
  • A countable union of countable sets is countable (with choice, or with given listings).
  • Density does not imply a larger cardinality.

Next: Cantor's Diagonal Argument