Questions: Cardinality and Countability

Question 1

The set of even natural numbers {0, 2, 4, 6, ...} compared to the set of all natural numbers ℕ has:

• A. Smaller cardinality, since it is a proper subset
• B. The same cardinality, since the bijection n ↦ 2n maps ℕ onto the even numbers
• C. Larger cardinality, since even numbers grow faster
• D. Incomparable cardinality — they cannot be directly compared

Answer: (B)

The function n ↦ 2n is a bijection from ℕ to the even natural numbers: it is injective (different inputs give different outputs) and surjective (every even number is hit). Since a bijection exists, the two sets have the same cardinality — both are countably infinite (cardinality ℵ₀). This is one of the counterintuitive consequences of Cantor's definition: a proper subset of an infinite set can have the same cardinality as the whole set. Option A reflects the naive view that proper subsets must be smaller, which holds for finite sets but fails for infinite ones.

Question 2

Cantor's diagonal argument shows that the real numbers ℝ are uncountable. What is the key move that makes the proof work?

• A. It counts the number of real numbers and shows there are more than ℕ
• B. It assumes a complete list of reals exists and constructs a real number that differs from every entry on the list
• C. It shows that the rationals ℚ cannot be listed, so ℝ cannot be either
• D. It uses the fact that ℝ contains irrational numbers, which ℕ cannot index

Answer: (B)

The diagonal argument is a proof by contradiction. Assume you have a list r₁, r₂, r₃, ... that purportedly covers every real in [0,1]. Construct a new real by taking the nth decimal digit of rₙ and changing it. This new number differs from r₁ in the first digit, from r₂ in the second digit, and so on — it cannot be anywhere on the list. This contradicts the assumption that the list was complete. The proof doesn't count the reals; it shows that ANY list must be incomplete. Option C is wrong because ℚ is actually countable.

Question 3

The rational numbers ℚ are uncountable because they are densely packed between the integers.

• T. True
• F. False

Answer: False

This is a common misconception. Despite being dense (between any two rationals lies another), the rationals are countably infinite — the same cardinality as ℕ. Cantor's diagonal-grid argument shows this: arrange all fractions p/q in a 2D grid (rows indexed by numerator, columns by denominator), then trace a zigzag path through the grid. Every rational appears somewhere, so this path defines a bijection with ℕ. Density is not the same as uncountability — density is about ordering, cardinality is about size measured by bijection.

Question 4

The power set of any infinite set A has strictly greater cardinality than A itself.

• T. True
• F. False

Answer: True

This is Cantor's theorem, and it holds for any set — finite or infinite. The proof uses a diagonal argument: suppose a bijection f: A → P(A) exists. Define the set D = {x ∈ A : x ∉ f(x)}. Since f is a bijection, D = f(a) for some a. Is a ∈ D? If yes, then a ∉ f(a) = D — contradiction. If no, then a ∈ f(a) = D — contradiction. So no bijection can exist, meaning |P(A)| > |A|. This generates the infinite hierarchy ℵ₀ < c < |P(ℝ)| < ..., with no largest infinity.

Question 5

Explain the key step in Cantor's diagonal argument that makes it a proof that no list of real numbers can be complete.

Model answer: The key step is the construction of the 'diagonal number.' Given any purported list of reals, you build a new real number by examining the nth decimal digit of the nth entry and choosing a different digit for the nth position of your new number. This construction guarantees the new number differs from every entry on the list in at least one decimal place — it is not r₁ (differs in position 1), not r₂ (position 2), and so on. Because this procedure works for ANY list, no list can be complete. The brilliance is that the argument is constructive: it shows exactly how to find the missing element rather than just asserting one exists.

Students often misunderstand the diagonal argument as a counting proof. It is actually a constructive contradiction: it produces a specific missing element from any proposed list, making the incompleteness explicit rather than merely asserting it. The diagonal structure — using the nth entry to define the nth digit — is what ensures the new number is missed by every entry simultaneously.