1
Injective is about collisions
Two different inputs may never share an output. To refute it, name the two inputs; the contrapositive x ≠ y → f(x) ≠ f(y) says the same thing.
Lesson · Sets, Relations, and Functions · Functions
Injective, Surjective, Bijective
Injective means distinct inputs get distinct outputs; surjective means the image fills the codomain; bijective is both. On finite sets of equal size the two properties imply each other, and on infinite sets they do not.
injective f(x) = f(y) → x = y no two inputs collide
surjective ∀b ∈ B ∃a ∈ A. f(a) = b the image IS the codomain
bijective both a perfect pairing
|A| = |B| finite ⟹ injective ⟺ surjective
Two properties, four combinations
Core ideas
What this lesson establishes
Each property is a quantified sentence, and each is refuted by naming a specific collision or a specific gap.
2
Surjective is about coverage
Every element of the codomain must be hit. To refute it, name the element nothing maps to. It depends on the codomain, so it is not a property of the formula alone.
3
On finite equal-sized sets the two coincide
Injective and surjective imply each other when |A| = |B| is finite. On infinite sets they come apart, and that failure defines infinity.
The material
The three properties
Definitions, how to prove and refute each, and the finite/infinite split.
Definition · Injective
f : A → B is injective (one-to-one) when f(x) = f(y) ⟹ x = y for all x, y ∈ A. Equivalently, x ≠ y ⟹ f(x) ≠ f(y).
Definition · Surjective
f : A → B is surjective (onto) when for every b ∈ B there is some a ∈ A with f(a) = b — equivalently, when the image equals the codomain.
Definition · Bijective
f is bijective when it is both injective and surjective. A bijection pairs the elements of A with those of B so that nothing is left over on either side.
The two definitions are stated in the two directions that make them usable. Injectivity is proved by assuming f(x) = f(y) and deriving x = y — a direct proof. Surjectivity is proved by taking an arbitrary b and constructing an a that maps to it — an existence proof, and usually the harder of the two.
Example · The same rule, different verdicts
f : ℝ → ℝ, f(x) = x²: neither — f(2) = f(−2) breaks injectivity, and nothing maps to −1. f : [0,∞) → ℝ: injective, not surjective. f : ℝ → [0,∞): surjective, not injective. f : [0,∞) → [0,∞): bijective. The formula never changed.
Theorem · On finite sets of equal size, one implies the other
Let A and B be finite with |A| = |B|, and f : A → B. Then f is injective if and only if it is surjective.
If f is injective, its image has |A| distinct elements, all inside B. Since |B| = |A| and B is finite, the image is all of B, so f is surjective.
If f is surjective, every one of the |B| elements of B needs at least one preimage; with only |A| = |B| inputs available, each gets exactly one, so no two inputs collide and f is injective.
□
Theorem · The cardinality constraints
If f : A → B is injective then |A| ≤ |B|; if surjective then |A| ≥ |B|; if bijective then |A| = |B|. For finite sets these are the pigeonhole principle of “The Pigeonhole Principle”.
So the answer is sometimes settled before any function is examined. With |A| = 5 and |B| = 3 no injection exists, whatever the rule; with |A| = 3 and |B| = 5 no surjection does. The lab reports this before letting you hunt.
On infinite sets the equivalence fails, and the failure is the definition of infinity. f : ℕ → ℕ with f(n) = n + 1 is injective and not surjective — nothing maps to 0 — even though the domain and codomain are the same set. A set is infinite exactly when it admits an injection to a proper subset of itself.
Interactive
Injective, surjective, bijective
Built by hand, classified by counting
Method
Deciding the three properties
Check the sizes first; they often settle it.
1
Compare the cardinalities
|A| > |B| rules out injective; |A| < |B| rules out surjective. Both are free and both are conclusive.
2
For injectivity, assume f(x) = f(y)
Derive x = y by algebra. If the derivation needs a case split or fails, look for the collision instead.
3
For surjectivity, solve f(a) = b for a
Take an arbitrary b in the codomain and construct a preimage. If the construction leaves the domain, f is not surjective.
4
Name the witness when a property fails
The colliding pair, or the unhit element. "Not injective" without the pair is an assertion, not an answer.
Classification
Score 0 / 0Choose the answer you can justify.
Classify f : ℤ → ℤ, f(n) = 2n + 3
Both directions, written out.
INJECTIVE?
Suppose f(m) = f(n).
2m + 3 = 2n + 3 ⟹ 2m = 2n ⟹ m = n. YES
SURJECTIVE?
Take b ∈ ℤ. Solve 2a + 3 = b: a = (b − 3)/2.
For b = 0 this gives a = −3/2 ∉ ℤ. NO
Nothing maps to 0 — indeed the image is the ODD integers.
So f is injective, not surjective, and NOT bijective.
Change the codomain to the odd integers and it becomes a bijection.
Note that |ℤ| = |ℤ| here and injectivity still did not give surjectivity. The finite theorem above genuinely needs finiteness, and this is the counterexample.
Common mistakes
1
Deciding surjectivity without the codomainIt is not a property of the formula. x ↦ x² is surjective onto [0, ∞) and not onto ℝ, with no change to the rule.
2
Assuming injective implies surjectiveTrue for finite sets of equal size, false in general. n ↦ n + 1 on ℕ is the standard counterexample and is worth remembering.
3
Refuting a property without a witness"Not injective" needs the colliding pair; "not surjective" needs the unhit element. The witness is the proof.
Check your understanding
✓
Finish when you can produce a witness for every negative verdict.
Classify f : ℤ → ℤ with f(n) = n² − n, giving either a proof or a specific witness for each property. (f(0) = f(1) = 0, which settles one of them immediately.)
Note: The four combinations all occur, and it is worth having an example of each in mind: n ↦ 2n on ℤ (injective only), n ↦ ⌊n/2⌋ on ℤ (surjective only), n ↦ n + 1 on ℤ (bijective), and n ↦ n² on ℤ (neither).