Questions: Cardinality and Countability

Question 1

Which of the following sets has the same cardinality as the natural numbers ℕ?

• A. The real numbers ℝ
• B. The power set of ℕ
• C. The rational numbers ℚ
• D. The set of all infinite subsets of ℕ

Answer: (C)

ℚ is countably infinite — there is a bijection between ℚ and ℕ (e.g., via a diagonal enumeration of fractions). ℝ and the power set of ℕ are both uncountably infinite, with strictly larger cardinality than ℕ. This surprises students who expect ℚ to be 'larger' because it is dense on the number line.

Question 2

The set of even integers {0, 2, 4, 6, ...} has strictly smaller cardinality than the set of most natural numbers ℕ because it is primarily half as large.

• T. True
• F. False

Answer: False

Cardinality is determined by whether a bijection exists, not by 'how many' elements seem present intuitively. The function f(n) = 2n maps every natural number to a unique even integer and covers all even integers, so the two sets have equal cardinality. This is one of the defining — and counterintuitive — features of infinite sets.

Question 3

Describe the key idea behind Cantor's diagonalization argument and what it proves about ℝ.

Model answer: Cantor's diagonal argument shows that no list can enumerate all real numbers in [0,1]. Given any proposed list, you construct a new real number by changing the nth digit of the nth entry, guaranteeing it differs from every entry on the list. This proves ℝ is uncountable — its cardinality is strictly greater than that of ℕ.

The argument is a proof by contradiction: assume a bijection exists between ℕ and ℝ, then construct an element of ℝ not in the image of that bijection. The diagonal construction makes the contradiction concrete and irrefutable.