A student argues that the set of even natural numbers E = {0, 2, 4, 6, …} has 'half as many' elements as ℕ = {0, 1, 2, 3, …}, so |E| < |ℕ|. What is wrong with this reasoning?
AThe student is correct — E is a proper subset of ℕ so it must have strictly smaller cardinality
BThe bijection f(n) = 2n shows every natural number maps to a unique even number and vice versa, so |E| = |ℕ|
CE is finite (it lists every even number up to some bound) so the comparison doesn't apply
DCardinality is only defined for finite sets; infinite sets cannot be compared by size
The bijection f : ℕ → E defined by f(n) = 2n pairs every natural number with a unique even number and hits every even number exactly once. Since a bijection exists, |E| = |ℕ| by definition. The student's intuition — that a proper subset must be smaller — is correct for finite sets but fails for infinite ones. For infinite sets, a proper subset can be in bijection with the whole set. This is sometimes taken as the defining property of infinite sets (the Dedekind-infinite property). Cardinality for infinite sets is defined purely by bijection, not by 'how many' elements in the intuitive counting sense.
Question 2 Multiple Choice
Cantor's theorem states |A| < |P(A)| for every set A. What does this immediately imply about |ℝ| compared to |ℕ|?
ANothing — Cantor's theorem applies only to finite sets
Bℝ and ℕ have the same cardinality because both are infinite
C|ℝ| > |ℕ|, because |P(ℕ)| > |ℕ| and it can be shown that |ℝ| = |P(ℕ)|
D|ℝ| > |ℕ| by Cantor's theorem applied directly to ℕ ⊂ ℝ
By Cantor's theorem, |ℕ| < |P(ℕ)|. Separately, it can be shown that |ℝ| = |P(ℕ)| = 2^ℵ₀ (the reals are in bijection with the power set of ℕ, e.g., via binary expansions). Combining these: |ℕ| < |P(ℕ)| = |ℝ|, so the reals are strictly more numerous than the naturals. Option D sounds plausible (ℕ ⊂ ℝ) but is wrong: a proper subset relation does not imply strict cardinality inequality for infinite sets — ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ, yet |ℕ| = |ℤ| = |ℚ| < |ℝ|. The strictly greater cardinality of ℝ requires Cantor's diagonal argument, not just the subset relation.
Question 3 True / False
There exists a bijection between the natural numbers ℕ and the rational numbers ℚ, so they have the same cardinality ℵ₀.
TTrue
FFalse
Answer: True
This is one of the most surprising results in set theory. Cantor showed that ℚ is countably infinite by constructing an enumeration: list all fractions a/b (in lowest terms, a ∈ ℤ, b ∈ ℕ⁺) in a grid and traverse it diagonally, skipping duplicates. This visits every rational number exactly once, providing a bijection with ℕ. Intuitively, ℚ seems 'denser' than ℕ (between any two integers lie infinitely many rationals), yet they have the same cardinality. Density on the number line is a different concept from cardinality. Any set that can be listed in a sequence indexed by ℕ (even with a clever non-obvious ordering) is countably infinite.
Question 4 True / False
Since the set of integers ℤ contains the natural numbers ℕ as a proper subset, ℤ is expected to have strictly greater cardinality than ℕ.
TTrue
FFalse
Answer: False
This is the central misconception the topic addresses. For infinite sets, containing a set as a proper subset does NOT imply strictly greater cardinality. The bijection f : ℕ → ℤ defined by the interleaving 0 → 0, 1 → 1, 2 → −1, 3 → 2, 4 → −2, … pairs every natural number with a unique integer and covers all integers. Since a bijection exists, |ℕ| = |ℤ|, even though ℕ ⊊ ℤ. The property 'a proper subset can be in bijection with the whole set' is actually characteristic of infinite sets (Dedekind's definition of infinite). For finite sets, every proper subset does have strictly smaller cardinality.
Question 5 Short Answer
Explain what it means for two infinite sets to have the same cardinality, and give an example of two infinite sets with DIFFERENT cardinalities. Explain how we know they are different.
Think about your answer, then reveal below.
Model answer: Two sets have the same cardinality iff there exists a bijection between them — a function pairing every element of one with exactly one element of the other, with no elements left over on either side. ℕ and ℝ have different cardinalities: |ℕ| < |ℝ|. We know this because Cantor's diagonal argument proves no function ℕ → ℝ can be a surjection: for any proposed list of reals, you can construct a real number differing from the nth listed number in its nth decimal place, so it's not in the list.
The diagonal argument is the key tool for proving two sets have different infinite cardinalities. It shows that any attempt to list the reals in a sequence indexed by ℕ necessarily misses some real — the diagonal construction always finds one not in the list. This proves ℝ is uncountably infinite: it cannot be put in bijection with ℕ. The contrast with ℚ (countable) is striking: although ℚ is dense in ℝ (between any two reals lies a rational), ℚ can be enumerated (listed) while ℝ cannot. Density and cardinality are genuinely different properties.