The set of even natural numbers 2ℕ = {0, 2, 4, 6, ...} is a proper subset of ℕ = {0, 1, 2, 3, ...}. What is the relationship between their cardinalities?
A|2ℕ| < |ℕ|, because 2ℕ is missing all the odd numbers
B|2ℕ| = |ℕ|, because f(n) = 2n is a bijection from ℕ to 2ℕ
C|2ℕ| = |ℕ|/2, since exactly half the natural numbers are even
D|2ℕ| < |ℕ|, because a proper subset always has strictly smaller cardinality
Cardinality is defined by bijections, not subset relationships. f(n) = 2n maps every natural number to a unique even number (injective) and hits every even (surjective), so it is a bijection — by definition |2ℕ| = |ℕ|. The finite intuition that a proper subset must be smaller fails for infinite sets. In fact, being bijectable with a proper subset is Dedekind's definition of an infinite set.
Question 2 Multiple Choice
To prove that the open interval (0,1) and all of ℝ have the same cardinality using Cantor-Schröder-Bernstein, which approach works?
AShow both are countably infinite — all countably infinite sets have equal cardinality
BConstruct an injection (0,1) → ℝ via the identity, and an injection ℝ → (0,1) via (arctan(x)/π + ½), then conclude |(0,1)| = |ℝ| by CSB
CShow a surjection ℝ → (0,1) and conclude the sets are equinumerous
DSince (0,1) ⊂ ℝ, they cannot have the same cardinality
Cantor-Schröder-Bernstein (CSB) states: if injections f: A → B and g: B → A both exist, then |A| = |B|. For (0,1) and ℝ: the identity is an injection (0,1) → ℝ; the function arctan(x)/π + ½ maps ℝ injectively into (0,1) (it's strictly increasing and lands in (0,1)). Both injections exist, so CSB guarantees a bijection. Option D repeats the finite misconception that subset implies smaller cardinality — exactly what cardinality theory overturns.
Question 3 True / False
The set of integers ℤ has strictly greater cardinality than ℕ, because ℤ contains most negative integers in addition to ℕ.
TTrue
FFalse
Answer: False
Despite containing infinitely many more elements, ℤ and ℕ are equinumerous. An explicit bijection: f(0)=0, f(1)=−1, f(2)=1, f(3)=−2, f(4)=2, ... — interleaving the negative and positive integers. Every integer is hit exactly once. The lesson: for infinite sets, 'proper subset' does not imply 'smaller cardinality.' Both ℕ and ℤ are countably infinite, meaning they have cardinality ℵ₀ (aleph-null).
Question 4 True / False
The Cantor-Schröder-Bernstein theorem states: if there is an injection A → B and an injection B → A, then there exists a bijection between A and B.
TTrue
FFalse
Answer: True
This is exactly CSB. An injection A → B establishes |A| ≤ |B|; an injection B → A establishes |B| ≤ |A|. CSB says these two inequalities together imply |A| = |B| — a bijection must exist, even though neither injection itself is the bijection. The theorem is non-trivial because constructing the bijection from two injections requires a careful set-theoretic argument. CSB makes cardinality comparison well-behaved: there are no two sets with |A| ≤ |B| and |B| ≤ |A| but |A| ≠ |B|.
Question 5 Short Answer
Why does the existence of a bijection — rather than a counting argument — define 'same cardinality' for infinite sets?
Think about your answer, then reveal below.
Model answer: For finite sets, counting works: two sets have the same cardinality iff both have the same natural number n of elements. But 'number of elements' doesn't generalize — you cannot point to a specific natural number as the 'count' of ℕ itself. Bijections generalize counting without needing a specific number: two sets are equinumerous iff their elements can be paired one-to-one with no leftovers. This works for finite sets (agreeing with ordinary counting) and extends to infinite sets, where it yields the surprising result that proper subsets can have equal cardinality to the whole.
Hilbert's Hotel illustrates the key point: an infinite hotel with all rooms occupied can accommodate a new guest by shifting everyone — room n → room n+1 — freeing room 1. The hotel is 'full' but not 'full' in the way a finite hotel is. Bijection-based cardinality captures this: |ℕ| = |ℕ ∪ {new guest}| because a bijection exists. This isn't a paradox — it's the defining property of infinite sets. The bijection definition is the mathematically correct way to compare sizes when counting by natural numbers breaks down.