Questions: Uncountable Sets and Cantor Diagonalization

Question 1

A mathematician claims: 'I have a method to list all real numbers between 0 and 1 — the list is infinite, just like the list of natural numbers.' What does Cantor's diagonal argument show about this claim?

• A. The claim is plausible — infinite lists can contain all reals if arranged with sufficient care
• B. Any such list must omit at least one constructible real number, so a complete enumeration is impossible
• C. The reals between 0 and 1 are countable, but the full real line is not
• D. The diagonal argument only defeats specific badly-ordered lists, not all possible listings

Answer: (B)

The diagonal argument defeats *every* proposed enumeration, not just badly constructed ones. Given any list r₁, r₂, r₃, … — no matter how cleverly arranged — Cantor constructs a specific real d by differing from r₁ in position 1, from r₂ in position 2, from r₃ in position 3, and so on. This d cannot appear anywhere on the list, because it differs from every entry at a specific position. The assumption that a complete list exists leads to a contradition: d is a real in (0,1) not on the list. The reals are therefore uncountable.

Question 2

Cantor proved that for any set A, the power set P(A) is strictly larger than A. What does this imply about the integers ℤ?

• A. P(ℤ) is countably infinite, the same size as ℤ itself
• B. P(ℤ) is uncountable — there is no bijection between P(ℤ) and ℤ
• C. P(ℤ) has the same cardinality as the rational numbers ℚ
• D. The integers have no well-defined power set because they are infinite

Answer: (B)

ℤ is countably infinite (|ℤ| = ℵ₀). Cantor's theorem states |P(A)| > |A| for any set A, so |P(ℤ)| > ℵ₀. Since ℵ₀ is the cardinality of countable infinity, P(ℤ) must be uncountably infinite. In fact, P(ℤ) has the same cardinality as ℝ (the continuum 𝔠 = 2^ℵ₀). This shows uncountability is not a quirk of the real numbers alone — it arises whenever you take the power set of any infinite set.

Question 3

The diagonal argument produces a specific, constructible real number that cannot appear anywhere in any proposed enumeration of the reals — making it a constructive proof, not merely an existence argument.

• T. True
• F. False

Answer: True

The diagonal argument is explicitly constructive. Given any proposed list r₁, r₂, r₃, …, Cantor's procedure produces a specific real d: go to position n in rₙ's decimal expansion and choose a different digit. The number d is fully determined by the list itself. This is stronger than an existence proof — it tells you exactly what the missing real is and how to find it. This constructive character is also what makes the technique generalizable: the same diagonal strategy proves Cantor's theorem (|P(A)| > |A|) and the undecidability of the Halting Problem.

Question 4

Uncountable infinity is simply a 'larger' version of countable infinity in the same way that 1,000,000 is larger than 10 — both are the same type of thing, just different sizes.

• T. True
• F. False

Answer: False

Uncountable and countable infinity are fundamentally different kinds of infinite, not just different sizes of the same kind. A countably infinite set can be exhausted by a process that eventually reaches every element (list the naturals: 1, 2, 3, …). An uncountable set cannot — no enumeration reaches all its elements, and the diagonal argument shows exactly why. The cardinality ℵ₀ (countable) and 𝔠 (continuum, uncountable) are distinct cardinal numbers with no bijection between the sets they measure. This is not like the difference between large and larger finite numbers; it is a difference in the mathematical structure of infinity itself.

Question 5

Explain in your own words how the diagonal argument defeats any proposed enumeration of the reals — not just specific badly-arranged lists, but every possible list.

Model answer: Suppose someone claims to have a complete list r₁, r₂, r₃, … of all reals in (0,1). Cantor's diagonal procedure reads the list itself and constructs a real d: look at the nth decimal digit of rₙ for each n, and choose a different digit (e.g., if the digit is 5, write 6; otherwise write 5). Now d differs from r₁ in position 1, from r₂ in position 2, from r₃ in position 3, and so on for every n. Therefore d ≠ rₙ for all n — d is not on the list anywhere. But d is a perfectly valid real number in (0,1). The list claimed to be complete but omits d. This argument works against any possible list, because the construction uses the list itself to produce the missing element — there is no way to arrange the list to escape it.

The key insight is that the argument is adversarial against the list: whatever list you propose, the diagonal construction reads it and produces a specific omission. There is no defensive arrangement that works, because the construction adapts to every list. This is why uncountability is a theorem, not just a practical difficulty of listing real numbers.