Questions: Cantor Pairing Functions and Product Countability

Question 1

A student argues: 'ℕ × ℕ must be uncountable because for every natural number n, there are infinitely many pairs (n, k), so there are infinitely many infinities stacked together.' What is the decisive flaw in this reasoning?

• A. The student is correct — ℕ × ℕ is indeed uncountable
• B. The argument confuses intuitive 'size' with cardinality; the Cantor diagonal enumeration provides an explicit bijection ℕ × ℕ → ℕ, proving it countable
• C. The student should apply Cantor's diagonal argument, which shows ℕ × ℕ is uncountable
• D. The argument is flawed because ℕ × ℕ is finite

Answer: (B)

The student's intuition — 'infinity times infinity must be bigger' — is wrong about countable infinity. Countability is about the existence of a bijection with ℕ, not about naive size. The Cantor pairing function provides an explicit bijection by enumerating pairs along successive diagonals (m+n = 0, then m+n = 1, etc.), covering every pair exactly once. The fact that the listing process is infinite doesn't make the set uncountable — ℕ itself is infinite. ℵ₀ × ℵ₀ = ℵ₀.

Question 2

Why does listing (0,0), (0,1), (0,2), (0,3), ... fail as a proof that ℕ × ℕ is countable?

• A. Because the pairs are listed in the wrong order — (0,0) should appear last
• B. Because this listing never reaches pairs like (1,0), (2,0), or (5,7) — it fails to be surjective onto all of ℕ × ℕ
• C. Because the function isn't injective — some pairs are counted twice
• D. Because ℕ × ℕ actually isn't countable, so no such listing can exist

Answer: (B)

The naive row-by-row listing exhausts the first row (0, k) for all k before moving to (1, 0). But the first row is already infinite, so (1, 0) never gets a natural number assigned. The listing maps {0,1,2,...} to {(0,0),(0,1),(0,2),...} — it's an injection into ℕ × ℕ but not a surjection. The diagonal enumeration solves this by only visiting a finite diagonal at each step, ensuring every pair is eventually reached.

Question 3

The fact that ℕ × ℕ is countable implies that the rational numbers ℚ are also countable.

• T. True
• F. False

Answer: True

Every rational number p/q (in lowest terms, q > 0) corresponds to a pair of integers (p, q). Since ℤ is countable (by the listing 0, 1, −1, 2, −2, ...) and ℤ × ℤ is countable (by applying the pairing function to two countable sets), ℚ injects into ℤ × ℤ. A subset of a countable set is countable. Therefore ℚ is countable — a result that surprises most people, since ℚ is dense in ℝ and seems 'almost as large' as the reals.

Question 4

The Cantor pairing function proves that most infinite sets are countable, since any infinite set can be mapped to ℕ × ℕ.

• T. True
• F. False

Answer: False

The pairing function proves that products of countable sets are countable — it says nothing about uncountable sets. Cantor's diagonal argument (a separate result) proves that ℝ is strictly larger than ℕ: no bijection between ℕ and ℝ can exist. The pairing function and the diagonal argument are complementary: together they show that countable products stay countable, but there are genuinely larger infinities that no amount of pairing can reach.

Question 5

Explain in your own words why enumerating ℕ × ℕ diagonally (by antidiagonals where m+n is constant) succeeds where row-by-row enumeration fails.

Model answer: Row-by-row enumeration gets stuck: the first row is infinite, so completing it before moving to the second row means no pair with first coordinate ≥ 1 ever receives a natural number. Diagonal enumeration avoids this by grouping pairs with a finite diagonal index (m+n = d has exactly d+1 pairs). Each diagonal is finite, so it can be fully listed before moving to the next. Because every pair (m, n) belongs to exactly one diagonal (the one with m+n = m+n), every pair is eventually assigned a unique natural number.

The key insight is that any enumeration of ℕ × ℕ must visit each pair after finitely many steps. Row-by-row violates this: pair (1,0) would only be reached after infinitely many steps (after all (0,k) pairs). Diagonal enumeration assigns each pair a specific, computable finite position — the formula π(m,n) = (m+n)(m+n+1)/2 + n gives the exact index. This makes the bijection not just existential but constructive.