Which function establishes that the set of even natural numbers E = {0, 2, 4, 6, ...} has the same cardinality as the natural numbers ℕ = {0, 1, 2, 3, ...}?
Af(n) = n + 2, which shifts each natural number up by 2
Bf(n) = 2n, which maps every natural number to a distinct even number and covers all of E
CNo such function can exist because E is a proper subset of ℕ and must therefore be smaller
Df(n) = n², because squares grow fast enough to reach all even numbers
f(n) = 2n is injective (if 2m = 2n then m = n, so no two inputs share an output) and surjective onto E (every even number 2k is the image of k). Together these make it a bijection from ℕ to E, proving |ℕ| = |E|. Option C is the central misconception: for infinite sets, a proper subset CAN have the same cardinality as the whole. This is Dedekind's definition of an infinite set. Option D — f(n) = n² — is injective but not surjective onto E (for example, 6 is not a perfect square).
Question 2 Multiple Choice
A student argues that the integers ℤ must have larger cardinality than the natural numbers ℕ, because ℤ contains all of ℕ plus all negative integers. What is wrong with this reasoning?
ANothing — ℤ does have strictly larger cardinality than ℕ by Cantor's theorem
BThe student is confusing subset containment with cardinality; a bijection from ℕ to ℤ can be constructed, showing they are equinumerous
CThe reasoning is correct for finite sets but the conclusion happens to be wrong for infinite sets for unrelated reasons
Dℤ is actually smaller than ℕ because the negative integers cancel out the positive ones
The bijection from ℕ to ℤ interleaves positives and negatives: 0↦0, 1↦1, 2↦−1, 3↦2, 4↦−2, ... This mapping is injective and surjective, so |ℕ| = |ℤ|. The student's error is assuming that 'contains more elements' translates to 'has larger cardinality' for infinite sets — an intuition that holds for finite sets but breaks down for infinite ones. Cardinality is defined exclusively by bijection existence, not by subset relationships.
Question 3 True / False
If set A is a proper subset of set B (meaning A ⊂ B and A ≠ B), then A typically has strictly smaller cardinality than B.
TTrue
FFalse
Answer: False
This is true for finite sets but false for infinite sets. The set of even natural numbers is a proper subset of ℕ, yet the bijection f(n) = 2n shows they have equal cardinality. More strikingly, this property — being equinumerous with a proper subset — is Dedekind's definition of an infinite set. The failure of the 'proper subset means smaller' intuition for infinite sets is not a flaw in the mathematics; it is precisely what distinguishes infinite cardinality from finite cardinality.
Question 4 True / False
A bijection between two sets A and B is a function that is both injective (one-to-one) and surjective (onto).
TTrue
FFalse
Answer: True
Injectivity ensures no two elements of A map to the same element of B (nothing in B is 'hit twice'). Surjectivity ensures every element of B is mapped to by at least one element of A (nothing in B is 'left out'). Together they guarantee a perfect pairing: each element of A is paired with exactly one element of B and vice versa. Bijections are also exactly the functions that have a two-sided inverse. If either condition fails — an injection that misses some elements of B, or a surjection with collisions — you cannot form a perfect pairing and cardinality equality is not established.
Question 5 Short Answer
Why is the existence of a bijection the right definition of 'same cardinality,' and what makes this definition more powerful than simply counting elements when dealing with infinite sets?
Think about your answer, then reveal below.
Model answer: Counting works for finite sets by assigning consecutive natural numbers 1, 2, 3, ... to elements. But 'counting' an infinite set would never terminate — you can never finish and declare a final tally. The bijection definition sidesteps counting entirely: instead of counting each set separately and comparing totals, you directly exhibit a perfect correspondence between the two sets. If every element of A is paired with exactly one element of B, and every element of B is covered, the sets are 'the same size' by definition — regardless of whether they are finite or infinite. This definition also extends naturally to comparing different sizes of infinity: ℕ and ℝ cannot be put in bijection (Cantor's diagonal argument), so they have different cardinalities, which is a meaningful mathematical fact that the 'just count them' approach cannot express.
The power of this definition also comes from being an equivalence relation: reflexive (every set bijects with itself via the identity), symmetric (bijections are invertible), and transitive (compositions of bijections are bijections). This partitions all sets into cardinality classes and enables rigorous comparison of all sets, finite and infinite.