Questions: Countable Sets and Enumeration

Question 1

The set of rational numbers ℚ is countably infinite. What does this mean precisely?

• A. ℚ has the same number of elements as every other infinite set
• B. There exists a bijection f : ℕ → ℚ — every rational can be listed at some finite position in a sequence
• C. ℚ is infinite but smaller than ℝ in the sense that it has fewer decimal expansions
• D. ℚ is countable because the rationals can be approximated by finite decimals

Answer: (B)

Countably infinite means equinumerous with ℕ via a bijection. The key content is that every element of ℚ appears at some *finite* position in a list — even though the list itself never terminates. Cantor's diagonal enumeration of fractions p/q constructs this bijection by zigzagging through an infinite grid of rationals. Option A is wrong because uncountable sets (like ℝ) are strictly larger. Options C and D describe properties of rationals but do not define or explain countability.

Question 2

Which of the following sets is NOT countably infinite?

• A. The set of all integers ℤ
• B. The set of all ordered pairs of natural numbers ℕ × ℕ
• C. The set of all real numbers in the interval [0, 1]
• D. The set of all finite strings over the alphabet {0, 1}

Answer: (C)

The real numbers in [0,1] are uncountable, as shown by Cantor's diagonal argument: any proposed listing of reals in [0,1] can be diagonalized to produce a real not in the list, contradicting the assumption that the list was complete. ℤ (option A) is countable via the listing 0, 1, −1, 2, −2, .... ℕ × ℕ (option B) is countable via the diagonal enumeration. Finite binary strings (option D) are countable because there are finitely many strings of each length, and countable unions of finite sets are countable.

Question 3

A countably infinite set is smaller than a finite set, since 'countable' implies a small, manageable quantity.

• T. True
• F. False

Answer: False

This is a direct conflation of 'countable' with 'small' — the most common misconception in this topic. A countably infinite set is still infinite; 'countable' only means it can be listed in a sequence indexed by ℕ. The integers, rationals, and all finite strings are countably infinite — they are each larger than any finite set. 'Countable' is a classification of the *kind* of infinity, not an indication that the set is small or finite. The contrast is with *uncountable* infinite sets, which are strictly larger than countably infinite sets.

Question 4

The set of integers ℤ is countably infinite, despite appearing 'larger' than ℕ because it includes negative numbers — a bijection with ℕ exists via the listing 0, 1, −1, 2, −2, 3, −3, ....

• T. True
• F. False

Answer: True

This illustrates the power and counterintuitiveness of the bijection-based definition of size. The listing 0, 1, −1, 2, −2, 3, −3, ... is an explicit bijection from ℕ to ℤ: every integer appears at exactly one position in the list, and every position contains exactly one integer. Our intuition that ℤ should be 'twice as large' as ℕ (it includes both positives and negatives) is an example of how finite-set intuitions fail for infinite sets. Cardinality theory, grounded in bijections, replaces this intuition with a precise and consistent account of infinite size.

Question 5

Why does Cantor's diagonal argument show the real numbers are uncountable? Describe the key construction and where the contradiction arises.

Model answer: Assume for contradiction that all reals in [0,1] can be listed as r₀, r₁, r₂, .... Construct a new real x by making x's n-th decimal digit differ from the n-th decimal digit of rₙ (e.g., if rₙ's n-th digit is 5, set x's n-th digit to 6; otherwise set it to 5). Then x differs from r₀ at the 0th digit, from r₁ at the 1st digit, from r₂ at the 2nd digit, and so on — x differs from every rₙ at the n-th position. So x is not in the list. But x is in [0,1], contradicting the assumption that the list was complete.

The diagonal argument works because the construction is guaranteed to produce something *not* in the list: by design, x disagrees with every listed real at at least one decimal place. No matter how cleverly you arrange the list, the diagonal construction finds an element that escapes it. This shows that no bijection from ℕ to [0,1] can exist — the reals are strictly more numerous than the naturals. The argument generalizes: the power set of any set is always strictly larger than the set itself (Cantor's theorem), implying there is a strict hierarchy of infinite cardinalities, not just one kind of infinity.