Surjective Function — Onto Function, Proof, Examples
Book A Free Math Class
Surjective Function — Onto Function, Proof, Examples
TL;DR
A surjective function, also called an onto function, is one where every element of the codomain is hit by at least one input — nothing in the target set is left out. This article covers the formal definition, how to prove a function is surjective, the difference from injective and bijective functions, the codomain-versus-range distinction, and six worked examples.
What Is a Surjective Function?
A surjective function f:A→B is one where every element of the codomain B has at least one preimage in the domain A. Formally: for every y∈B, there exists at least one x∈A such that f(x)=y. The everyday name is an onto function — the function maps onto all of B, not just part of it.
There's no uniqueness requirement. Two or more inputs are allowed to land on the same output; what's forbidden is leaving any output unreached. That's the mirror image of the one to one (injective) function, which forbids two inputs sharing an output but allows outputs to go unused.
The one-line test: a function is surjective exactly when its range equals its codomain. If the outputs you actually produce fill the entire target set, it's onto.
What Is the Difference Between Codomain and Range?
This single distinction settles most surjectivity questions, so it's worth pinning down.
- Codomain — the set you declare as the target when you write f:A→B. It's a choice.
- Range (or image) — the set of outputs the function actually produces.
The range is always a subset of the codomain. Surjective means the two are equal. Consider f(x)=x² written as f:R→R. The codomain is all real numbers, but the range is only [0,∞) — no negative number is ever an output. So it's not surjective. Rewrite the same formula as f:R→[0,∞) and now range equals codomain — it is surjective. Surjectivity depends on the declared codomain, not just the formula.
How Do You Prove a Function Is Surjective?
The standard proof works backwards from an arbitrary output:
- Take an arbitrary element y in the codomain.
- Solve the equation f(x)=y for x.
- Show that the solution x actually lies in the domain.
If you can always find such an x, every output is reachable, and the function is onto.
Worked once: is f(x)=2x+1, with f:R→R, surjective? Pick any real y and solve 2x+1=y: [ x = \frac{y - 1}{2}. ] For every real y, this x is a real number — so it's in the domain. Every output is hit.
It is surjective. This solve-for-x method is the backbone of every onto proof.
What Is the Difference Between Surjective, Injective, and Bijective?
These three describe how a function's inputs and outputs line up, and they get mixed up constantly.
| Type | Rule | Outputs |
|---|---|---|
| Injective | distinct inputs give distinct outputs | no output used twice; some may be unused |
| Surjective | every codomain element is hit | every output used; some may be hit twice |
| Bijective | one-to-one and onto | perfect pairing — every output hit exactly once |
A bijective function is the gold standard: both injective and surjective, so each output comes from exactly one input. Bijections are precisely the functions with a true two-way inverse, which links straight back to why injectivity governs inverses.
How Many Surjective Functions Are There? (The Counting Question)
A question the SERP and forums raise often: from a set of m elements onto a set of n elements, how many onto functions exist? The answer uses inclusion-exclusion:
[ \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} (n - k)^{m}. ]
The idea: count all n^m functions, then subtract the ones that miss at least one target, adding back the over-subtracted overlaps. For m=3 inputs onto n=2 outputs, the formula gives 2^3−2⋅1^3=8−2=6 surjective functions — the same 6 you'd get by listing them. This counting result connects surjections to Stirling numbers of the second kind.
Examples of Surjective Function
The examples build from a finite-set check, through the most common codomain mistake, to proofs and the counting formula.
Example 1
Is f={(1,a),(2,b),(3,b)} from {1,2,3} to {a,b} surjective?
Check the codomain {a,b}. Is a hit? Yes, by 1. Is b hit? Yes, by 2 and 3. Every codomain element has at least one preimage.
Final answer: yes, it's surjective. The fact that b is hit twice doesn't matter — surjectivity only cares that nothing is missed.
Example 2
A common slip — is f(x)=x², written f:R→R, surjective?
Wrong attempt. A student reasons: "x² produces every non-negative number, and you can square-root any output to find an input, so every value is reachable — it's surjective."
Test it against a specific output. Is there a real x with f(x)=−4? That needs x²=−4, which has no real solution. So the output −4, which sits in the declared codomain R, is never produced.
Correct. The range is [0,∞), but the codomain is all of R. Range ≠ codomain.
Final answer: no, f:R→R with f(x)=x² is not surjective. The negative reals in the codomain are never reached.
Example 3
Is f(x)=x³, with f:R→R, surjective?
Take any real y and solve x³=y: the cube root x=³√y is a real number for every y, positive, negative, or zero.
Final answer: yes, it's surjective — and since cubing is also one-to-one, it's bijective.
Example 4
Is f(x)=1+x², with f:R→R, surjective?
The smallest value of x² is 0, so the smallest output is 1. The range is [1,∞), but the codomain is R.
Final answer: no. No output is ever less than 1, so every number below 1 in the codomain is left out.
Example 5
Make f(x)=x² surjective by choosing the right codomain.
The formula's actual outputs fill [0,∞). Declare that set as the codomain: f:R→[0,∞). Now every target value y≥0 has a preimage x=√y.
Final answer: f:R→[0,∞) is surjective. Same formula, smarter codomain — surjectivity is a statement about the function and its declared target.
Example 6
Count the onto functions from a 3-element set to a 2-element set.
Use the inclusion-exclusion formula with m=3, n=2:
[ 2^3−\binom{2}{1}1^3=8−2=6. ]
Final answer: 6 surjective functions. The 2 subtracted are the two functions that send all three inputs to a single output (missing the other), leaving 6 that cover both targets.
Where Surjective Functions Earn Their Place
"Is every outcome actually reachable?"
The words surjection, injection, and bijection were coined by the French mathematical collective writing as Nicolas Bourbaki in the mid-20th century, who built much of modern mathematics on the precise language of sets and maps. "Onto" had been used informally for decades; Bourbaki gave it an exact, language-independent name so a proof would read identically in Paris, Tokyo, or São Paulo.
Where the idea does real work:
- Coding and compression. A surjective encoding can produce every possible codeword — important when you need full coverage of an output space. Hash functions are deliberately surjective onto their output range so every bucket can be reached.
- Counting and combinatorics. "How many ways can n jobs be distributed so every worker gets at least one?" is an onto-function count.
- Solving equations. Asking "does f(x)=y always have a solution?" is asking whether f is surjective onto the set of y you care about. Existence of solutions is surjectivity in disguise.
Where Students Trip Up on Surjective Functions
Mistake 1: Ignoring the codomain
Where it slips in: Deciding surjectivity from the formula alone, without checking what codomain was declared.
Don't do this: Say f(x)=x² "is surjective because it makes lots of outputs" without asking which set those outputs must fill.
The correct way: Compare range to codomain. Surjective means they're equal. The same formula can be onto with one declared codomain and not onto with another.
Mistake 2: Confusing surjective with injective
Where it slips in: Reading "every element is hit" and picturing the one-to-one rule instead.
Don't do this: Require that each output be hit exactly once. That's injective (and, combined with onto, bijective) — not surjective.
The correct way: Surjective only requires at least one preimage per output. Outputs hit twice are perfectly allowed.
Mistake 3: Assuming a non-surjective function can't be made surjective
Where it slips in: Concluding a formula "isn't onto" and stopping there.
Don't do this: Treat surjectivity as a fixed property of the rule.
The correct way: Shrinking the codomain to match the range makes any function surjective. Surjectivity is a property of the function together with its declared codomain.
Key Takeaways
- A surjective function (onto function) reaches every element of its codomain: for every y there's at least one x with f(x)=y.
- The one-line test is range = codomain; the proof method is to solve f(x)=y and show the solution lies in the domain.
- Surjective differs from injective (uniqueness) and from bijective (both at once); only bijections have a two-way inverse.
- The most common mistake is ignoring the codomain.
- Onto functions underpin counting problems, hashing coverage, and the question of whether an equation always has a solution.