Questions: Uncountable Sets and Cantor's Diagonal Argument

Question 1

Cantor's diagonal argument begins by assuming that all real numbers in [0,1] can be listed as r₁, r₂, r₃, … . It then constructs a new real number d. What is d designed to do?

• A. Show that the list contains duplicates, contradicting the assumption that it is a proper enumeration
• B. Differ from every number on the list in at least one decimal position, so d cannot appear anywhere on the list
• C. Show that the list is finite, contradicting the infinitude of the reals
• D. Demonstrate that some real numbers cannot be written as infinite decimals

Answer: (B)

The diagonal number d is constructed so that it differs from rₙ in precisely the nth decimal place — from r₁ in position 1, from r₂ in position 2, and so on. This guarantees that d ≠ rₙ for every n, meaning d cannot be anywhere on the list. Since d is a well-defined real number in [0,1], the list failed to include it — contradicting the assumption that the list was complete. The argument does not find a duplicate or argue about finiteness; it constructs a witness to incompleteness.

Question 2

You use Cantor's diagonal argument on someone's proposed listing of all reals, constructing d that differs from rₙ in position n. Your opponent says: 'Fine, but just add d to the end of the list — then your argument fails.' What is the decisive response?

• A. The diagonal argument only works for the original list, not for extended lists
• B. d might already appear elsewhere on the extended list, so the extension doesn't help
• C. The argument applies to any list: given the new extended list, you can apply the diagonal procedure again to construct another real not on that list either
• D. There is no response — adding d to the list does defeat the argument

Answer: (C)

This is the key to understanding why the argument proves uncountability rather than just defeating one list. Given any complete list — including the extended list with d appended — you can apply the diagonal procedure again to construct yet another real not on the new list. The argument is not a one-time trick: it is a recipe that defeats every proposed listing, however constructed. No enumeration strategy can escape it.

Question 3

Cantor's diagonal argument works constructively: given any proposed list of reals, it produces a specific real number provably absent from that list.

• T. True
• F. False

Answer: True

The argument is constructive rather than merely existential. It doesn't just claim 'some real must be missing' — it gives you the missing real explicitly: take the nth decimal digit of rₙ and change it by a definite rule (e.g., replace 5 with 6, anything else with 5). This produces a concrete, computable real number d that is demonstrably not equal to any rₙ. The constructive character is what makes the argument so powerful: it defeats not just bad lists but every possible list.

Question 4

The diagonal argument proves that one particular listing strategy for the reals fails. A sufficiently clever listing strategy — one that doesn't go in a simple numerical order — could still succeed in enumerating most real numbers.

• T. True
• F. False

Answer: False

The argument makes no assumptions about how the list is constructed — it applies to any proposed bijection between ℕ and ℝ, regardless of the strategy used to build it. Given ANY list r₁, r₂, r₃, … (however cleverly ordered), the diagonal procedure constructs a real not on the list. There is no listing strategy that escapes this: the argument is universal, not specific to naive orderings. This is why the conclusion is that ℝ is uncountable — no bijection with ℕ exists at all.

Question 5

Why does Cantor's diagonal argument prove that ℝ is uncountable, rather than merely showing that one particular attempted enumeration fails?

Model answer: The argument does not assume any particular structure or ordering for the proposed list — it takes an arbitrary list r₁, r₂, r₃, … and constructs a specific real d that differs from rₙ in position n. Since the construction works for ANY list, regardless of how it was built, there is no possible bijection between ℕ and ℝ: every bijection attempt produces a list, and every list is provably incomplete by the diagonal procedure. The universality of the construction — not its application to one bad list — is what establishes uncountability.

The deeper point is that the argument generalizes: for any set S, the same diagonal logic shows that 𝒫(S) (the power set) has strictly greater cardinality than S. This creates a hierarchy of infinities with no top — each power set operation produces a strictly larger one. Cantor's argument is thus not just a theorem about ℝ but a general technique for producing cardinality inequalities, establishing that infinity is not a single level but an inexhaustible tower.