Functions: injections, surjections, bijections - Discrete Math

SECTION 1

Historical Context & Motivation

The modern notion of a function as a well-defined mapping between sets did not arrive fully formed; it crystallized over several centuries of mathematical evolution. Early mathematicians such as Leibniz and Euler thought of functions primarily as algebraic expressions or analytic formulas, with little attention paid to the sets upon which they operated. It was only when nineteenth-century analysts encountered pathological counterexamples—continuous curves that are nowhere differentiable, space-filling curves, and paradoxes of infinity—that the community was forced to make the concept of mapping precise. The resulting set-theoretic framework, championed by Dedekind, Cantor, and later Bourbaki, gave rise to the classification of functions as injections, surjections, and bijections—a taxonomy that is now indispensable in algebra, analysis, topology, and computer science.

1694 • Leibniz coins 'functio'

Gottfried Wilhelm Leibniz introduces the Latin word functio to describe quantities that depend on a variable—an informal precursor to the modern concept.

1837 • Dirichlet's arbitrary correspondence

Peter Gustav Lejeune Dirichlet proposes that a function need not be given by an algebraic formula; any rule assigning each input a unique output qualifies, paving the way for the set-theoretic viewpoint.

1888 • Dedekind formalizes injections

Richard Dedekind defines ähnliche Abbildungen (similar mappings)—what we now call injections—and uses them to characterize infinite sets in his monograph Was sind und was sollen die Zahlen?.

1895 • Cantor's set theory & cardinality

Georg Cantor publishes his landmark papers on set theory, using bijections to define when two sets have the same cardinality and proving the uncountability of the reals.

1939 • Bourbaki standardizes terminology

The Bourbaki collective introduces the French terms injection, surjection, and bijection in Éléments de mathématique, cementing the vocabulary used worldwide today.

The central question this classification addresses is deceptively simple: given a function f : A → B, how does the mapping relate the sizes and structures of A and B? Does every element of A get its own private image? Does every element of B get "hit" by at least one arrow? Answering these questions leads directly to the three categories that organize the rest of this lesson, and understanding them is essential before tackling proofs about cardinality, inverse functions, and the counting techniques that underpin combinatorics.

SECTION 2

Core Definitions & Principles

Before classifying functions, we must be precise about what a function is in the set-theoretic sense. A function f : A → B is a relation from a set A (the domain) to a set B (the codomain) satisfying two requirements: every element of A is paired with some element of B, and each element of A is paired with exactly one element of B. The set of elements in B that actually appear as outputs is called the image (or range) of f, denoted f(A) or im(f). With this foundation, we can state the three key properties.

Injection (One-to-One)

A function f : A → B is injective if distinct elements of A always map to distinct elements of B. Formally: for all a₁, a₂ ∈ A, f(a₁) = f(a₂) implies a₁ = a₂. No two arrows share the same target.

Surjection (Onto)

A function f : A → B is surjective if every element of the codomain B is the image of at least one element in A. Formally: for every b ∈ B, there exists a ∈ A such that f(a) = b. Every target is hit.

Bijection (One-to-One and Onto)

A function f : A → B is bijective if it is both injective and surjective: every element of B is hit by exactly one arrow from A. Bijections establish a perfect pairing and are precisely the functions that have two-sided inverses.

Neither Injective nor Surjective

Many functions fail both properties. For instance, a constant function f : ℝ → ℝ defined by f(x) = 5 maps every real number to 5, so multiple inputs share one output (not injective) and most of ℝ is missed (not surjective).

✦

KEY TAKEAWAY

Think of a function f : A → B as a telephone directory that assigns each person in A exactly one phone number in B. An injection means no two people share a phone number; a surjection means every phone number in the directory is assigned to somebody; and a bijection means there is a perfect one-to-one correspondence—every person has a unique number, and every number belongs to exactly one person. This is the intuition behind why bijections are the gold standard for 'counting equivalence' between two sets.

SECTION 3

Visual Explanation: Arrow Diagrams

The most intuitive way to visualize these three properties is through arrow (mapping) diagrams, sometimes called "blob diagrams" or "egg diagrams." In each diagram the domain A appears on the left and the codomain B on the right, with arrows showing which element maps where. Observe the patterns: in an injection, arrows never converge on the same codomain element; in a surjection, no codomain element is left without an incoming arrow; and in a bijection, every arrow is a one-to-one pairing with nothing left over on either side.

Three arrow diagrams contrasting the three function types. Left: an injection from {1, 2, 3} to {a, b, c, d}—no two arrows land on the same target, but element c is unhit. Center: a surjection from {1, 2, 3, 4} to {a, b, c}—every target is hit, but elements 1 and 2 both map to a. Right: a bijection from {1, 2, 3} to {a, b, c}—each element pairs uniquely.

Notice the relationship between the sizes of A and B in these finite examples. When f is injective, |A| ≤ |B| because each domain element needs its own exclusive target. When f is surjective, |A| ≥ |B| because there must be enough arrows to cover every codomain element. A bijection requires |A| = |B|—the sets match perfectly. These size constraints are a powerful counting tool: they underlie the Pigeonhole Principle and form the basis for comparing the sizes of infinite sets.

SECTION 4

Mathematical Framework

In formal mathematics, the three properties are stated using first-order logic quantifiers. The following definitions apply to any function f : A → B where A and B may be finite or infinite.

INJECTION (ONE-TO-ONE)

∀ a₁, a₂ ∈ A : f(a₁) = f(a₂) ⟹ a₁ = a₂

Equivalently (by contrapositive): a₁ ≠ a₂ ⟹ f(a₁) ≠ f(a₂). To prove injectivity, assume f(a₁) = f(a₂) and derive a₁ = a₂. To disprove it, exhibit a concrete pair a₁ ≠ a₂ with f(a₁) = f(a₂).

SURJECTION (ONTO)

∀ b ∈ B, ∃ a ∈ A : f(a) = b

To prove surjectivity, let b be an arbitrary element of B and construct an a ∈ A with f(a) = b. To disprove it, find a specific b ∈ B for which no preimage exists.

BIJECTION

f is bijective ⟺ f is injective ∧ f is surjective

An equivalent characterization: f is bijective if and only if there exists a function g : B → A such that g ∘ f = id_A and f ∘ g = id_B. Such a g is the two-sided inverse of f, usually written f⁻¹.

CARDINALITY CONNECTION (FINITE SETS)

Injection ⟹ |A| ≤ |B| Surjection ⟹ |A| ≥ |B| Bijection ⟹ |A| = |B|

For finite sets these implications also hold in reverse (a consequence of the Pigeonhole Principle). For infinite sets, only the forward implications hold in general; showing |A| = |B| requires the Cantor–Bernstein–Schröder theorem when you have injections in both directions.

ℹ

Left and Right Inverses

A function f : A → B has a left inverse (a function g : B → A with g ∘ f = id_A) if and only if f is injective (assuming A ≠ ∅). It has a right inverse (a function h : B → A with f ∘ h = id_B) if and only if f is surjective (this direction uses the Axiom of Choice). When both exist, they coincide and give the unique two-sided inverse f⁻¹.

SECTION 5

Classification & Composition

Understanding how the three properties interact under composition is essential for building larger proofs in algebra and analysis. If f : A → B and g : B → C, the composition g ∘ f : A → C is defined by (g ∘ f)(a) = g(f(a)). The following rules describe how injectivity and surjectivity propagate through compositions.

Property of f	Property of g	Property of g ∘ f	Explanation
Injective	Injective	Injective	Distinct inputs in A yield distinct outputs in B (by f), then distinct outputs in C (by g).
Surjective	Surjective	Surjective	Every c ∈ C has a preimage b under g, and that b has a preimage a under f.
Bijective	Bijective	Bijective	Composition of bijections is a bijection; the inverse is f⁻¹ ∘ g⁻¹.
Any	Any	g ∘ f injective ⟹ f injective	If the composition doesn't merge inputs, then f alone cannot merge them.
Any	Any	g ∘ f surjective ⟹ g surjective	If the composition covers all of C, then g must cover all of C.

Composition rules for injections, surjections, and bijections

Composition of two injections f : A → B and g : B → C. The solid arrows show f (amber) and g (green) individually. The dashed pink curves trace the composite g ∘ f. Because f preserves distinctness and g preserves it again, the composite is also injective.

An important consequence of the last two rows of the table above is a useful proof technique. If you can show that a composition g ∘ f is injective, you automatically know that f is injective—even without analyzing f in isolation. Similarly, if g ∘ f is surjective, then g must be surjective. These facts are frequently exploited in algebra when one needs to establish injectivity or surjectivity of a difficult map by embedding it in a composition with a known map.

SECTION 6

Worked Example

Let us classify the function f : ℤ → ℤ defined by f(n) = 2n + 1 as injective, surjective, both, or neither.

Classify f(n) = 2n + 1 on ℤ → ℤ

1
Step 1 — State the Domain and Codomain

We are given f : ℤ → ℤ, so both the domain and codomain are the set of all integers. The formula is f(n) = 2n + 1, which maps every integer n to an odd integer.
2
Step 2 — Test Injectivity

Assume f(n₁) = f(n₂). Then 2n₁ + 1 = 2n₂ + 1. Subtracting 1 from both sides gives 2n₁ = 2n₂, and dividing by 2 yields n₁ = n₂. Since the assumption f(n₁) = f(n₂) forces n₁ = n₂, the function is injective.

f is injective ✓
3
Step 3 — Test Surjectivity

Let b ∈ ℤ be arbitrary. We need to find an n ∈ ℤ such that 2n + 1 = b, i.e., n = (b − 1)/2. For n to be an integer, b − 1 must be even, meaning b must be odd. Consider the codomain element b = 4 (an even integer): (4 − 1)/2 = 3/2, which is not an integer. Therefore no n ∈ ℤ maps to 4, and f is not surjective.

f is NOT surjective ✗ (even integers have no preimage)
4
Step 4 — Conclusion

The function f(n) = 2n + 1 from ℤ to ℤ is injective but not surjective. Its image is the set of all odd integers, im(f) = {…, −3, −1, 1, 3, 5, …} ⊊ ℤ. If we were to restrict the codomain to the odd integers—i.e., redefine f : ℤ → 2ℤ + 1—then f would become a bijection.

f is an injection (one-to-one) but not a surjection (onto); hence not a bijection.

SECTION 7

Comparison & Common Pitfalls

Students often confuse the three properties—particularly injective and surjective—because the definitions are similar in structure (both involve universal quantifiers and implications). The table below offers a side-by-side comparison that highlights the contrasts, and a list of frequent errors follows.

Feature	Injection	Surjection	Bijection
Informal slogan	"No collisions"	"Everything is hit"	"Perfect pairing"
Quantifier structure	∀ a₁, a₂ (universal over domain)	∀ b ∈ B, ∃ a ∈ A (universal over codomain)	Both quantifiers combined
Finite-set size	\|A\| ≤ \|B\|	\|A\| ≥ \|B\|	\|A\| = \|B\|
Inverse existence	Left inverse (g ∘ f = id)	Right inverse (f ∘ h = id)	Two-sided inverse f⁻¹
To disprove	Find a₁ ≠ a₂ with f(a₁) = f(a₂)	Find b ∈ B with no preimage	Disprove either property
Horizontal Line Test (ℝ → ℝ)	Every horizontal line hits the graph at most once	Every horizontal line hits the graph at least once	Every horizontal line hits the graph exactly once

Side-by-side comparison of injections, surjections, and bijections

⚠

COMMON PITFALLS

1. Confusing codomain with range. Surjectivity depends on the codomain, not the range. The function f(x) = x² is surjective onto [0, ∞) but not surjective onto ℝ. 2. Assuming finite-set intuition holds for infinite sets. A function from ℕ to ℕ can be injective but not surjective (e.g., f(n) = 2n), which is impossible for finite sets of equal size. 3. Forgetting the domain matters. The map f(x) = x² is injective on [0, ∞) but not on ℝ. Always state the domain and codomain.

SECTION 8

Connections to Advanced Theory

The injection–surjection–bijection framework is not merely a classification exercise; it is the scaffolding upon which several pillars of higher mathematics are built. In abstract algebra, a bijective homomorphism between groups (or rings, or vector spaces) is called an isomorphism, and establishing one is the gold standard for proving that two algebraic structures are "the same." The First Isomorphism Theorem, which states that every group homomorphism φ : G → H factors as a surjection onto the quotient G / ker(φ) followed by an injection into H, is a direct application of the concepts in this lesson.

This Lesson	Advanced Topic	Connection
Bijection ⟹ \|A\| = \|B\|	Set Theory / Cardinality	Cantor defined two sets as equinumerous iff a bijection exists. Countability (\|A\| = \|ℕ\|) and uncountability hinge on the (non-)existence of bijections.
Injection with left inverse	Category Theory	An injective morphism is called a monomorphism; a surjective one is an epimorphism. These are the categorical generalizations of our definitions.
Bijection ⟹ invertible	Linear Algebra	A linear map T : V → W is invertible iff it is a bijection. Rank-nullity theorem: dim(ker T) + dim(im T) = dim V connects injectivity (ker T = {0}) and surjectivity (im T = W).
Counting surjections	Combinatorics	The number of surjections from an n-set onto a k-set is k! × S(n, k), where S(n, k) is a Stirling number of the second kind—central to partition enumeration.
Bijection as 'relabeling'	Cryptography	A block cipher is a keyed bijection on the message space; bijectivity ensures decryption is possible (the inverse exists).

How injections, surjections, and bijections appear in advanced mathematics

As you advance through your studies, you will encounter these concepts in increasingly abstract settings—from topological homeomorphisms (bijections that are continuous in both directions) to database theory (where functional dependencies encode injective constraints). Mastering the basic definitions and proof techniques now will pay dividends across virtually every branch of mathematics and theoretical computer science.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why a bijection f : A → B guarantees the existence of an inverse function f⁻¹ : B → A, while a function that is only injective (but not surjective) does not have a two-sided inverse.

Show answer

A bijection assigns each b ∈ B to exactly one a ∈ A (injectivity ensures at most one, surjectivity ensures at least one). Therefore we can define f⁻¹(b) = a unambiguously for every b ∈ B. If f is injective but not surjective, some elements of B have no preimage, so f⁻¹ is undefined on those elements, and no two-sided inverse from B to A can exist. We may still define a left inverse on the image of f, but it cannot be extended to all of B without making an arbitrary choice.

Question 2: BASIC CALCULATION

Let A = {1, 2, 3} and B = {a, b, c, d}. How many injective functions f : A → B exist? Justify your count.

Show answer

To build an injection, element 1 can be mapped to any of the 4 elements of B (4 choices). Element 2 must avoid the target already used by 1, leaving 3 choices. Element 3 must avoid both used targets, leaving 2 choices. The total number of injections is 4 × 3 × 2 = 24. This equals the falling factorial P(4, 3) = 4! / (4 − 3)! = 24. No surjection from A to B exists here because |A| = 3 < 4 = |B|.

Question 3: INTERMEDIATE

Define f : ℝ → ℝ by f(x) = x³ − 3x. Determine whether f is injective, surjective, both, or neither. Prove each claim.

Show answer

Surjectivity: since f is a polynomial of odd degree, lim f(x) as x → ∞ is +∞ and as x → −∞ is −∞. By the Intermediate Value Theorem, f attains every real value, so f is surjective. Injectivity: f′(x) = 3x² − 3 = 3(x − 1)(x + 1), which is zero at x = ±1. Computing f(−1) = 2 and f(1) = −2 shows f has a local max at x = −1 and a local min at x = 1. Because f changes direction, there exist distinct inputs with the same output (e.g., f(0) = 0 and f(−√3) = 0), so f is NOT injective. Conclusion: f is surjective but not injective.

Question 4: APPLIED

A hash function h maps a set of 2⁶⁴ possible input strings to a set of 2³² hash values. Explain, using the Pigeonhole Principle and the concepts from this lesson, why collisions (distinct inputs with the same hash) are inevitable. What does this say about the injectivity and surjectivity of h?

Show answer

The domain has |A| = 2⁶⁴ elements and the codomain has |B| = 2³² elements. Since |A| > |B|, the Pigeonhole Principle guarantees that at least two distinct inputs must map to the same hash value, meaning h cannot be injective. In fact, on average each hash value is shared by 2⁶⁴/2³² = 2³² inputs. Whether h is surjective depends on the specific function, but a well-designed hash function should be approximately surjective (covering all 2³² outputs). Nevertheless, no hash function from this domain to this codomain can be a bijection because the sets have different cardinalities.

Question 5: CRITICAL THINKING

Let f : A → B and g : B → C be functions. Prove that if g ∘ f is bijective, then f is injective and g is surjective. Provide a concrete example showing that, under these hypotheses, f need not be surjective and g need not be injective.

Show answer

Proof that f is injective: Suppose f(a₁) = f(a₂). Then g(f(a₁)) = g(f(a₂)), i.e., (g ∘ f)(a₁) = (g ∘ f)(a₂). Since g ∘ f is bijective (hence injective), a₁ = a₂. Proof that g is surjective: Let c ∈ C. Since g ∘ f is surjective, there exists a ∈ A with (g ∘ f)(a) = c. Setting b = f(a) ∈ B, we have g(b) = c, so c has a preimage under g. Counterexample: Let A = {1}, B = {a, b}, C = {α}. Define f(1) = a and g(a) = g(b) = α. Then g ∘ f : {1} → {α} maps 1 ↦ α, which is a bijection. But f is not surjective (b has no preimage) and g is not injective (g(a) = g(b)). This demonstrates that the composition can be bijective even when the individual components lack the other property.

SUMMARY

Summary

A function f : A → B assigns each element of the domain A to exactly one element of the codomain B. An injection (one-to-one function) guarantees that distinct inputs always produce distinct outputs—no two arrows share a target. A surjection (onto function) guarantees that every element of the codomain is hit by at least one arrow. A bijection combines both properties, establishing a perfect one-to-one correspondence between A and B and guaranteeing the existence of a two-sided inverse f⁻¹.

For finite sets, injectivity requires |A| ≤ |B|, surjectivity requires |A| ≥ |B|, and bijectivity requires |A| = |B|. These properties are preserved under composition: the composition of two injections is injective, of two surjections is surjective, and of two bijections is bijective. Beyond discrete math, this classification underpins cardinality theory, algebraic isomorphisms, the rank-nullity theorem in linear algebra, and even the design of cryptographic ciphers.