A student argues: 'The integers ℤ must be strictly larger than the natural numbers ℕ, because ℤ contains all natural numbers plus all the negative integers.' How should this reasoning be evaluated?
ACorrect — ℤ contains ℕ as a proper subset, so by set inclusion ℤ is strictly larger
BIncorrect — the sequence 0, 1, −1, 2, −2, 3, −3, ... establishes a bijection between ℕ and ℤ, so they have the same cardinality
CCorrect for finite sets, but infinite sets cannot be meaningfully compared in size
DIncorrect — all infinite sets have the same cardinality by definition
For infinite sets, subset inclusion does not determine relative size. Cardinality is measured by bijections: two sets have the same cardinality if and only if there is a perfect one-to-one correspondence between them. The sequence 0, 1, −1, 2, −2, 3, −3, ... lists every integer exactly once and pairs each with a natural number, establishing a bijection ℕ → ℤ. Despite ℤ being a proper superset of ℕ, they are equicardinal. This counterintuitive result is one of the defining features of infinite set theory.
Question 2 Multiple Choice
Which of the following sets is NOT countable?
AThe integers ℤ
BThe rational numbers ℚ
CThe real numbers ℝ
DThe set of all finite strings over the alphabet {a, b}
ℤ is countable (alternating positive/negative enumeration). ℚ is countable (Cantor's grid-and-diagonal argument, skipping repeated fractions). Finite strings over {a, b} are countable (enumerate by length: ε, a, b, aa, ab, ba, bb, ...). But ℝ is uncountable — Cantor's diagonalization theorem proves no enumeration can list every real number. The reals represent a qualitatively larger infinity than any countable set.
Question 3 True / False
The set of all pairs of natural numbers ℕ × ℕ is countably infinite, even though it appears to be a 'two-dimensional' infinity.
TTrue
FFalse
Answer: True
Cantor's diagonal enumeration lists every pair: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), ... — traversing along diagonals where the indices sum to 0, 1, 2, 3, etc. Every pair (m, n) appears exactly once in this list, establishing a bijection with ℕ. This shows that the 'two-dimensional' intuition does not translate to larger cardinality. The Cartesian product of any two countable sets is countable.
Question 4 True / False
If an infinite set A contains the natural numbers ℕ as a proper subset, then A is expected to be uncountable.
TTrue
FFalse
Answer: False
ℤ is a counterexample: it contains ℕ as a proper subset (ℕ ⊂ ℤ) but is countable. So is ℚ. And any countable set that extends ℕ by finitely or countably many elements remains countable. Containment of ℕ as a proper subset says nothing about cardinality — it only guarantees the set is infinite. Uncountability requires a different argument (like Cantor diagonalization), not mere proper containment.
Question 5 Short Answer
What does it mean for a set to be 'countably infinite,' and why does the existence of a bijection with ℕ capture the right notion of 'same size' for infinite sets?
Think about your answer, then reveal below.
Model answer: A set is countably infinite if there exists a bijection between it and ℕ — that is, its elements can be arranged in an infinite sequence a₀, a₁, a₂, ... where every element appears exactly once. The bijection definition captures 'same size' for infinite sets because it is the natural generalization of counting: for finite sets, |A| = n means there is a bijection between A and {0, 1, ..., n−1}. Extending this to infinite sets, two sets are 'the same size' if and only if their elements can be paired one-to-one with no leftovers.
For finite sets, we say two sets have the same size if we can match their elements one-to-one — this is exactly what a bijection does. The same definition extends to infinite sets: ℤ and ℕ have the same cardinality because their elements can be paired perfectly, even though ℤ looks larger by containment. This definition resolves the apparent paradox: it is not strange that a proper subset of an infinite set can have the same cardinality — it is the defining characteristic of infinite sets, which Dedekind used as their very definition.