Injections, Surjections, Bijections

⚗ Dr. Möbius, from the lab

Not all functions are created equal, and the bastards that are equal are about to get a rigorous classification. Some functions never collide — different inputs, guaranteed different outputs. Some hit everything in the codomain, not a single element left as an orphan. And the rare, gorgeous ones do both at once: a perfect pairing between two sets, matched up partner-for-partner with nobody doubled and nobody left over. These three words — injective, surjective, bijective — are the gateway to inverses, to cardinality, to counting infinity itself. Learn to prove them cold, because you will use them for the rest of your mathematical life.

THE BIG IDEA

Injective means different inputs give different outputs; surjective means every codomain element is hit; bijective is both — a perfect pairing.

Injective: no two inputs collide

Last node, we noted functions may send two inputs to the same output ( $x^2$ sends $2$ and $-2$ both to $4$ ). A function that never does this is injective (one-to-one). Formally:

$f \text{ injective} \quad \iff \quad \forall a, b \in A,\ \big(f(a) = f(b) \implies a = b\big).$

Read it as: if two outputs are equal, the inputs were already equal. Different inputs are guaranteed different outputs — no collisions. The contrapositive says the same thing forward: $a \ne b \implies f(a) \ne f(b)$ .

How you prove it. Assume $f(a) = f(b)$ , then grind algebra until you've forced $a = b$ . That's the whole template — memorize it, love it, use it. If instead you can find two different inputs with the same output, you've proven NOT injective with a single counterexample. Proving requires generality; disproving needs one example. One. That's all. One beautiful collision and the injectivity claim is dead.

Surjective: nothing in the codomain is missed

Recall codomain (declared) versus image (earned). A function is surjective (onto) when the image fills the entire codomain — every declared possible output actually gets hit:

$f \text{ surjective} \quad \iff \quad \forall y \in B,\ \exists x \in A\ \text{with}\ f(x) = y.$

Equivalently, $\operatorname{im}(f) = B$ — no gap between what's promised and what's delivered.

How you prove it. Take an arbitrary $y$ in the codomain, then solve $f(x) = y$ for $x$ and check your $x$ is a legal input. If you can always produce a preimage, it's surjective. To disprove, exhibit one $y \in B$ with no solution — one orphan in the codomain.

Crucial: surjectivity depends on what codomain you declared. The exact same formula is surjective or not depending on whether you aimed it at $\mathbb{R}$ or at $[0, \infty)$ . The choice of codomain is part of the function.

Bijective: the perfect pairing

A function that is both injective and surjective is bijective — a one-to-one correspondence. Every element of $A$ pairs with exactly one element of $B$ and vice versa: no collisions (injective) and no orphans (surjective). It's a perfect matching, partner for partner, nothing doubled and nothing left over.

Bijections are the crown jewels. They're exactly the functions that have inverses (next lesson), and they're the tool Cantor uses to count infinity (the stratum boss fight, and it is spectacular). A bijection between $A$ and $B$ says, with total precision, "these two sets are the same size" — even when both are infinite, even when that sounds insane. Hold that thought; the reactor is warming up.

Worked proof: f(x) = 3x + 1 on ℝ is bijective

Let $f : \mathbb{R} \to \mathbb{R}$ , $f(x) = 3x + 1$ . Claim: bijective. Prove both halves.

Injective. Assume $f(a) = f(b)$ : $3a + 1 = 3b + 1 \implies 3a = 3b \implies a = b.$ Equal outputs forced equal inputs. Injective. ✓

Surjective. Take an arbitrary $y \in \mathbb{R}$ . Solve $3x + 1 = y$ : $x = \frac{y - 1}{3}.$ This $x$ is a real number (legal input), and $f\!\left(\tfrac{y-1}{3}\right) = 3 \cdot \tfrac{y-1}{3} + 1 = (y - 1) + 1 = y$ . So every $y$ has a preimage. Surjective. ✓

Both hold, so $f$ is bijective. Every nonzero-slope line $f(x) = mx + b$ is bijective on $\mathbb{R}$ by the same argument — and that formula $x = (y-1)/3$ you just solved for? That's secretly the inverse function, which we'll name and weaponize next lesson.

The plot twist: domain and codomain CHANGE the verdict

Here's the trap that humbles everyone without exception — I've watched brilliant people stumble on this — and the most important idea in the lesson. Whether a function is injective/surjective is not a property of the formula alone — it depends on the domain and codomain you declare. Same formula, completely different verdict. Changing the endpoints changes the function. Full stop.

Take squaring, $f(x) = x^2$ , and watch the verdict flip as we change the sets:

$f : \mathbb{R} \to \mathbb{R}$ . Not injective: $f(-2) = f(2) = 4$ (collision). Not surjective: $-1 \in \mathbb{R}$ has no preimage (nothing squares to a negative). Neither.
$f : [0, \infty) \to \mathbb{R}$ . Now restrict inputs to non-negatives. Injective: if $a, b \ge 0$ and $a^2 = b^2$ , then $a = b$ (no $\pm$ ambiguity once you drop negatives). Still not surjective ( $-1$ still orphaned). Injective only.
$f : [0, \infty) \to [0, \infty)$ . Restrict the codomain too. Now injective (as above) and surjective (every $y \ge 0$ has preimage $\sqrt{y} \ge 0$ ). Bijective!

Same rule " $x^2$ ", three different functions, three different verdicts — because a function is its formula plus its domain plus its codomain. Change any of those and you may change everything. This is why mathematicians are pedantic about writing $f : A \to B$ in full, and why students who skip that notation get burned constantly. The arrow's endpoints aren't decoration. They're half the definition.

The horizontal line test: injectivity, drawn

Last lesson the vertical line test pictured single-valuedness. Now the horizontal line test pictures injectivity: a function is injective iff every horizontal line hits the graph at most once.

Why? A horizontal line at height $y$ collects all inputs $x$ with $f(x) = y$ . Two hits means two different inputs sharing the output $y$ — a collision, i.e. NOT injective. So "at most one hit per horizontal line" is injectivity, drawn. Graph $x^2$ and slide a horizontal line: above the axis it hits twice (at $\pm\sqrt{y}$ ), exposing the collision — but restrict to $x \ge 0$ and each horizontal line hits once.

function grapher

x = 1.2x^2 → 1.44

Vertical test $\to$ "is it a function" (single-valued). Horizontal test $\to$ "is it injective" (no collisions). Two perpendicular tests, two perpendicular properties. Beautiful symmetry — and now you can read both straight off a graph.

🔬 SPECIMENS (worked examples)

Worked example 1 — prove injective, prove surjective▸

Let $f : \mathbb{R} \to \mathbb{R}$ , $f(x) = 5 - 2x$ . Prove it is injective and surjective.

Injective. Assume $f(a) = f(b)$ : $5 - 2a = 5 - 2b \implies -2a = -2b \implies a = b.$ Equal outputs forced equal inputs, so $f$ is injective. ✓

Surjective. Take an arbitrary $y \in \mathbb{R}$ and solve $5 - 2x = y$ : $-2x = y - 5 \implies x = \frac{5 - y}{2}.$ This is a real number, hence a legal input, and checking: $f\!\left(\tfrac{5-y}{2}\right) = 5 - 2\cdot\tfrac{5-y}{2} = 5 - (5 - y) = y$ . ✓ Every $y$ has a preimage, so $f$ is surjective.

Both hold, so $f$ is bijective — as every line with nonzero slope is. Notice the surjectivity proof handed us $x = (5-y)/2$ , the future inverse, for free.

Worked example 2 — disprove with counterexamples (one collision, one orphan, both dead)▸

Let $g : \mathbb{Z} \to \mathbb{Z}$ , $g(n) = n^2 - n$ . Show $g$ is neither injective nor surjective.

Disproving needs only one witness each.

Not injective. Find two different inputs with the same output. Try $n = 0$ and $n = 1$ : $g(0) = 0 - 0 = 0, \qquad g(1) = 1 - 1 = 0.$ $g(0) = g(1) = 0$ but $0 \ne 1$ — a collision. Not injective. ✓

Not surjective. Find one codomain element with no preimage. Note $g(n) = n^2 - n = n(n-1)$ is a product of consecutive integers, hence always even (one of two consecutive integers is even). So $g(n)$ is never an odd number. Pick $y = 1$ : it's odd, so no $n$ gives $g(n) = 1$ . Not surjective. ✓

One collision kills injectivity; one orphan ( $1$ ) kills surjectivity. Disproofs are cheap — a single example each. (Proofs of the positive statements, by contrast, must handle every case.)

Worked example 3 — the twist: same formula, codomain changes everything▸

Consider $h(x) = x^2$ . Classify it as injective/surjective/bijective in three settings: (a) $\mathbb{R} \to \mathbb{R}$ , (b) $[0,\infty) \to \mathbb{R}$ , (c) $[0,\infty) \to [0,\infty)$ .

Same rule, three functions. Run injective and surjective each time.

(a) $\mathbb{R} \to \mathbb{R}$ .

Injective? $h(-3) = h(3) = 9$ , collision. No.
Surjective? Is $-4 \in \mathbb{R}$ hit? Nothing squares to a negative. No.
Verdict: neither.

(b) $[0,\infty) \to \mathbb{R}$ .

Injective? Now inputs are $\ge 0$ . If $a, b \ge 0$ and $a^2 = b^2$ , then $a = b$ (the negative twin is excluded from the domain). Yes.
Surjective? Codomain is still all of $\mathbb{R}$ ; $-4$ is still an orphan. No.
Verdict: injective only.

(c) $[0,\infty) \to [0,\infty)$ .

Injective? Same as (b), inputs $\ge 0$ . Yes.
Surjective? Take any $y \ge 0$ ; then $\sqrt{y} \ge 0$ is a legal input and $h(\sqrt{y}) = y$ . Yes.
Verdict: bijective!

The formula never changed. Shrinking the domain to $[0,\infty)$ bought injectivity (killed the $\pm$ collision); shrinking the codomain to $[0,\infty)$ bought surjectivity (deleted the orphans). A function is its rule plus its domain plus its codomain — change the endpoints, change the verdict.

☠ KNOWN HAZARDS

Confusing injective and surjective. Injective = no two inputs collide (about inputs). Surjective = nothing in the codomain is missed (about outputs). They're independent — a function can be one without the other. Getting these backwards is how you waste an entire proof.
Judging from the formula alone. $x^2$ is "neither" on $\mathbb{R}\to\mathbb{R}$ but "bijective" on $[0,\infty)\to[0,\infty)$ . Always pin down the domain and codomain before ruling. The formula is not the function.
Proving surjectivity by example. Showing $f(2) = 7$ proves only that $7$ is hit. Surjectivity needs an arbitrary $y$ to have a preimage — prove it for all, or you've proven nothing. One example is not a universal proof. Repeat this to yourself.
Forgetting the preimage must be a legal input. When solving $f(x) = y$ , your $x$ must lie in the domain. $\sqrt{y}$ as a preimage is only legal if $\sqrt{y}$ is actually in the domain. An out-of-domain preimage is no preimage at all.

TL;DR

▸
Injective (one-to-one): $f(a) = f(b) \implies a = b$ . Prove by assuming equal outputs and forcing equal inputs; disprove with one collision.
▸
Surjective (onto): every $y \in B$ has some $x$ with $f(x) = y$ , i.e. image $=$ codomain. Prove by solving $f(x) = y$ ; disprove with one orphan.
▸
Bijective: both — a perfect pairing. Exactly the functions with inverses, and the tool for comparing sizes of sets.
▸
A function's injectivity/surjectivity depends on its domain and codomain, not just the formula. $x^2$ flips from "neither" on $\mathbb{R}\to\mathbb{R}$ to "bijective" on $[0,\infty)\to[0,\infty)$ .
▸
Horizontal line test = injectivity drawn (each horizontal line hits at most once), just as the vertical test was single-valuedness drawn.

unlocks

Composition & Inverse Functions →