Questions: Uncountability and the Diagonal Argument

Question 1

In Cantor's diagonal argument, how is the constructed real number x guaranteed not to appear on the supposed complete list of reals?

• A. By choosing x to be larger than every number on the list
• B. By ensuring x differs from the nth listed real in the nth decimal place, for every n
• C. By using a random construction that is statistically unlikely to match any listed number
• D. By showing x is irrational, while all listed numbers are assumed to be rational

Answer: (B)

The diagonal construction sets the nth digit of x to differ from the nth digit of the nth listed real rₙ. This means x ≠ r₁ (they differ in position 1), x ≠ r₂ (position 2), and x ≠ rₙ for every n. The guarantee is built into the definition — no exhaustive checking is needed. The self-referential use of the list against itself is what makes the argument watertight.

Question 2

After the diagonal argument produces a real x missing from the list, a skeptic says: 'Just insert x at position 1 and renumber — now the list is complete.' Why does this objection fail?

• A. You cannot insert elements into an already-infinite list
• B. Renumbering an infinite list changes the cardinality of the natural numbers
• C. Applying the diagonal argument to the new list produces a different real not on that list either
• D. x was only missing because of the specific digits chosen; a different choice would have found x on the original list

Answer: (C)

The diagonal argument is a procedure, not a one-time result. Inserting x and renumbering simply creates a new list — and applying the diagonal construction to that new list immediately produces a new real x' missing from it. No matter how many times you patch the enumeration, the diagonal argument always finds another gap. This is why the argument establishes that no complete list can exist, not merely that one particular list failed.

Question 3

The diagonal argument disproves only one specific attempted enumeration of the reals — a different enumeration might still work.

• T. True
• F. False

Answer: False

The diagonal argument works against *any* enumeration whatsoever. Given any list r₁, r₂, r₃, ..., the construction produces a real guaranteed to be missing from that specific list. The argument is universal: hand me any alleged complete enumeration and the diagonal procedure hands back a real it missed. This universality is what proves no bijection between ℕ and ℝ can exist.

Question 4

Cantor's diagonal argument establishes that the cardinality of the real numbers is strictly greater than the cardinality of the natural numbers.

• T. True
• F. False

Answer: True

The argument shows no surjection from ℕ to ℝ exists — no list covers all reals. Combined with the obvious injection ℕ ↪ ℝ, the Cantor-Bernstein-Schroeder theorem gives |ℕ| < |ℝ| strictly. The reals aren't merely 'not countable' in a vague sense — they constitute a genuinely larger infinite cardinality, demonstrating that infinity comes in different sizes.

Question 5

Why is it important that the diagonal construction modifies the nth digit of the nth listed number, rather than simply choosing a new real number not obviously on the list?

Model answer: A randomly chosen real might still coincidentally appear somewhere on the supposedly complete list — you would need to check all infinitely many entries to verify it's absent, which is impossible. The diagonal construction avoids this problem by building the escape from the list into the definition of x: by differing from rₙ in position n for every n simultaneously, x is guaranteed to differ from every entry without any checking. The argument works because local difference at each diagonal position is sufficient to ensure global absence from the entire list.

This is the clever self-referential move at the heart of the proof. The construction uses the structure of the enumeration itself to construct a counterexample that provably escapes it. No enumeration can anticipate a construction defined in terms of that enumeration — which is exactly what makes the argument generalize to any list, not just a particular one.