Questions: Injective, Surjective, and Bijective Functions

Question 1

The function f: ℕ → ℤ defined by f(n) = n is injective but not surjective (negative integers have no preimage). What does this tell us about the cardinality of ℕ compared to ℤ?

• A. |ℕ| < |ℤ|, because f doesn't cover all of ℤ, proving ℤ is strictly larger
• B. |ℕ| ≤ |ℤ|, but this injection alone doesn't establish whether |ℕ| = |ℤ| or |ℕ| < |ℤ|
• C. |ℕ| = |ℤ|, because both sets are countably infinite
• D. No cardinality comparison is possible from a single function

Answer: (B)

An injection f: A → B witnesses |A| ≤ |B| — A fits inside B without collisions, but B may have leftover elements. To establish |ℕ| = |ℤ|, you need a bijection. In fact such a bijection does exist (e.g., map 0 ↦ 0, 1 ↦ 1, 2 ↦ −1, 3 ↦ 2, 4 ↦ −2, ...), and this is the standard proof that ℕ and ℤ are equinumerous. The injective f here tells you |ℕ| ≤ |ℤ|; you need additional structure to conclude equality.

Question 2

A function f: A → B has a right inverse g: B → A, meaning f(g(b)) = b for all b ∈ B. What does this tell you about f?

• A. f is injective
• B. f is bijective
• C. f is surjective
• D. f is neither injective nor surjective in general

Answer: (C)

A right inverse g means every b ∈ B is the image of g(b) under f, so every element of B has at least one preimage — exactly the definition of surjectivity. A right inverse does not require f to be injective: g simply picks one preimage for each b, but f might send multiple elements to the same b. Injectivity corresponds to a left inverse (g such that g(f(a)) = a for all a ∈ A). A full two-sided inverse requires bijectivity.

Question 3

If f: A → B is injective, then f has an inverse function f⁻¹: B → A.

• T. True
• F. False

Answer: False

An injection guarantees a left inverse — a function g: B → A with g(f(a)) = a for all a ∈ A — but not a full inverse on all of B. The inverse f⁻¹ must be defined on every element of B, and for elements of B outside the image f(A), there is no preimage to assign. A full two-sided inverse requires bijectivity: injectivity ensures each b in f(A) has a unique preimage, and surjectivity ensures every b is in f(A). Without surjectivity, the inverse is only partial.

Question 4

Two sets have the same cardinality if and only if there exists a bijection between them.

• T. True
• F. False

Answer: True

This is the definition of cardinality equality for sets of any size — finite or infinite. For finite sets it coincides with equal counts. For infinite sets it becomes the only coherent definition: ℕ and ℤ have the same cardinality because a bijection between them exists, even though ℤ 'contains' ℕ as a proper subset. This bijection-based definition, due to Cantor, revealed that not all infinite sets are the same size — ℝ has strictly greater cardinality than ℕ, as Cantor's diagonal argument shows.

Question 5

Why is the Schröder-Bernstein theorem remarkable, and how does it let you prove two sets have the same cardinality without constructing an explicit bijection?

Model answer: Schröder-Bernstein states: if injections exist in both directions (f: A → B and g: B → A), then |A| = |B|. Its power is that constructing two injections is often much easier than constructing a bijection directly. For example, to show |(0,1)| = |ℝ|, you can exhibit an injection from (0,1) into ℝ (the inclusion map) and an injection from ℝ into (0,1) (any sigmoid function). The theorem then guarantees a bijection exists, even though writing one explicitly is cumbersome. You prove cardinality equality by finding two injections rather than one bijection.

The theorem is remarkable because it converts a hard problem (construct an explicit bijection) into an easier one (construct two injections, possibly in totally different ways). The proof of the theorem itself is non-trivial — it requires constructing a bijection from two injections — but once proved, it becomes a general tool. The Schröder-Bernstein theorem is the foundational result that makes cardinality comparison via injections rigorous and useful throughout set theory.