A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Cantor pairing function provides an explicit bijection between ℕ × ℕ and ℕ, showing the Cartesian product of countable sets is countable. This proves ℤ, ℚ, and finite Cartesian products of countable sets are all countable, establishing fundamental closure properties.
From your work on countable sets and enumeration, you know that a set is countable if there is an injective function from it into ℕ — equivalently, its elements can be listed as a (possibly infinite) sequence a₀, a₁, a₂, …. Individual countable sets like ℕ and ℤ are already familiar. But what about pairs? Is the set of all pairs of natural numbers ℕ × ℕ still countable, or does pairing two infinite sets together produce something larger?
The answer is yes, ℕ × ℕ is countable — but the proof requires an explicit pairing function, a bijection ℕ × ℕ → ℕ. The naive approach of listing (0,0), (0,1), (0,2), … fails because you'd never reach (1,0). The Cantor pairing function solves this by listing pairs along successive diagonals: first the diagonal where m+n = 0, giving (0,0); then m+n = 1, giving (0,1), (1,0); then m+n = 2, giving (0,2), (1,1), (2,0); and so on. The k-th diagonal has k+1 pairs, and after completing all diagonals up to d, we've listed 1 + 2 + ··· + (d+1) = (d+1)(d+2)/2 pairs. From this, one derives the explicit formula: π(m, n) = (m + n)(m + n + 1)/2 + n, a bijection from ℕ × ℕ to ℕ with a computable inverse.
Once we have a pairing function, a cascade of countability results follow immediately. ℤ is countable: list 0, 1, −1, 2, −2, … to get an explicit bijection with ℕ, or pair (sign, magnitude). ℚ is countable: every rational p/q (in lowest terms, q > 0) corresponds to a pair (p, q) of integers; since ℤ × ℤ is countable (it's a product of two countable sets), and ℚ injects into it, ℚ is countable. More generally, any finite Cartesian product of countable sets is countable: ℕ² is countable by the pairing function, ℕ³ = ℕ × ℕ² is countable by applying the pairing function again, and by induction ℕᵏ is countable for any fixed k.
The pairing function also has a critical role in computability theory. Because ℕ × ℕ is in bijection with ℕ, we can encode pairs of inputs as single numbers, enabling Turing machines to simulate multiple-tape behavior with a single tape, and allowing Gödel numbering to encode sequences of symbols as single natural numbers. The enumerability of ℕ* — all finite sequences of natural numbers — follows from iterated pairing, and this is what allows us to enumerate all Turing machine descriptions, all proofs in a formal system, and all computable functions.
The key conceptual point is that pairing reveals infinity's non-intuitive arithmetic: ℵ₀ × ℵ₀ = ℵ₀. Multiplying countable infinity by itself doesn't make it larger. This stands in sharp contrast with the real numbers: no pairing trick can enumerate ℝ, as Cantor's diagonal argument shows. The pairing function is therefore the bridge between countability results and their first uncountable limit — it exhausts what diagonalization can avoid before Cantor's theorem closes the door.