Functions: Injective, Surjective & Bijective

Discrete Mathematics Fundamentals

Chapter 6 · Functions: Injective, Surjective & Bijective

Chapter 5 covered relations broadly. This chapter covers a specific, exceptionally important kind of relation: a function — and Chapter 1 already named its code equivalent directly: "a hash map is a function from keys to values."

What Makes a Relation a Function

A relation f from A to B is a function if every element of A maps to exactly one element of B — not zero, not more than one, exactly one. A relation that sends some input to two different outputs simply isn't a function at all.

This is exactly why a dict key can only hold one value

A Python dictionary structurally enforces the function property — it physically cannot represent a non-function relation. d[key] = value1 followed by d[key] = value2 doesn't create two mappings for the same key; it overwrites the first, because a dict is a direct implementation of "each key maps to exactly one value." You couldn't accidentally build a non-function with a dict even if you tried.

Domain, Codomain & Range

Three related but genuinely different sets, easy to mix up:

Term	Meaning
Domain	The full set of allowed inputs
Codomain	The set outputs are declared to come from
Range (image)	The set of outputs that actually occur — always a subset of the codomain, sometimes a smaller one

Example: f(x) = x² declared as a function from all integers to all integers has codomain = all integers, but its range is only the non-negative perfect squares (0, 1, 4, 9, 16, ...) — the codomain is bigger than what's actually produced. This gap between codomain and range is exactly what the next section formalizes.

Injective (One-to-One)

A function is injective when different inputs always produce different outputs — no two distinct inputs ever collide on the same output. Formally: ∀a₁ ∀a₂ (f(a₁) = f(a₂) → a₁ = a₂).

Surjective (Onto)

A function is surjective when every element of the codomain actually gets hit by something — the range equals the entire codomain, with nothing left over. Formally: ∀b ∈ B ∃a ∈ A (f(a) = b).

Three Small, Fully Verifiable Examples

Function	Injective?	Surjective?
A={1,2}, B={a,b,c}: f(1)=a, f(2)=b	Yes — 1 and 2 map to different outputs	No — c is never hit
A={1,2,3}, B={a,b}: f(1)=a, f(2)=a, f(3)=b	No — f(1)=f(2) but 1≠2	Yes — both a and b are hit
A={1,2,3}, B={x,y,z}: f(1)=x, f(2)=y, f(3)=z	Yes	Yes

Bijective — Both at Once

A function that's both injective and surjective is bijective — a perfect one-to-one correspondence between every element of A and every element of B, nothing left unmatched on either side. The third example above is bijective. A bijective function is exactly what "invertible" means: because every output came from exactly one input, you can always walk backward from output to input unambiguously.

Why this matters for encoding schemes

An encoding function where decode(encode(x)) always recovers the original x exactly requires encode to be injective at minimum — if two different inputs ever produced the same encoded output, decoding that output could never reliably tell you which original input it came from.

Why a Cardinality Mismatch Rules Out Some Functions Entirely

For finite sets, a bijection between A and B can only exist when |A| = |B| exactly. If |A| > |B|, no injective function from A to B can exist at all — this is the pigeonhole principle, formalized properly in Chapter 9.

This is exactly why hash collisions are mathematically unavoidable

A hash function maps an effectively unlimited number of possible input strings down to a fixed-size output — say, a 32-bit hash, which has exactly 2³² possible values. Since the set of possible inputs is vastly larger than 2³², no hash function from strings to 32-bit values can ever be injective, no matter how cleverly it's designed. Collisions aren't a flaw in a specific hash function's implementation — they're a direct, unavoidable consequence of mapping a larger set into a smaller one.

Hands-On Exercises

Exercise 1

For A = {1, 2, 3, 4} and B = {p, q}, with f(1)=p, f(2)=q, f(3)=p, f(4)=q, determine whether f is injective, surjective, both, or neither, and justify each part of your answer.

📄 View solution

Exercise 2

Consider two mappings on a set of users: (a) each user's unique employee ID maps to that user's record, and (b) each user's country of residence maps to that user's record. For each, state whether the mapping is injective, and explain the practical consequence for whether you could reliably look up "the" user just from the output alone.

📄 View solution

Exercise 3

A system needs to assign a unique 4-digit PIN (10,000 possible values) to each of 15,000 new users. Using this chapter's own cardinality reasoning, explain why no injective assignment of PINs to users is possible here, regardless of how the PINs are chosen.

📄 View solution

Chapter 6 Quick Reference

A function maps every input to exactly one output — a dict enforces this structurally, it can't represent anything else
Domain = allowed inputs, codomain = declared output set, range = outputs that actually occur (⊆ codomain)
Injective: different inputs always give different outputs — Surjective: every codomain element gets hit
Bijective = both at once = a perfect one-to-one correspondence = invertible
For finite sets, a bijection requires |A| = |B| exactly; |A| > |B| rules out any injective function — this is why fixed-size hash functions can never avoid collisions
Next chapter: Proof techniques — direct, contrapositive, and contradiction