Concept 06 / 10Sets, Relations and Functions
One-One, Onto and Bijective Functions, and Counting Functions
Injective, surjective and bijective functions, how to test them algebraically, graphically and with derivatives, the finite-set equivalence of one-one and onto, and the formulas for counting all, one-one, onto and bijective maps between finite sets.
Functions are classified by two independent questions. Does ever merge two inputs into one output? Does use up the whole codomain?
One-one (injective): distinct inputs always give distinct outputs. Formally, , or equivalently . If some pair of distinct inputs shares an image, is many-one. Graphically, a function is one-one exactly when every horizontal line meets its graph at most once (the horizontal line test). A strictly monotonic function is always one-one, so for differentiable functions a quick sufficient test is that throughout (or throughout), with allowed only at isolated points. The converse fails for discontinuous functions: is one-one on but not monotonic there.
Onto (surjective): every element of the codomain is the image of at least one input, that is, range codomain. If some element of the codomain is left unused, is into. Onto-ness depends on the codomain you declare. The same rule is into as a map (negative numbers are unused) but onto as a map . To test onto-ness, compute the range and compare it with the stated codomain.
Bijective: both one-one and onto. A bijection pairs the domain and codomain perfectly, element for element, which is exactly the condition for an inverse function to exist. The diagram shows one example of each type: one-one but into, many-one but onto, and bijective.
Useful facts. For continuous functions on an interval, one-one is equivalent to strictly monotonic. A polynomial of even degree from to is never one-one and never onto: it tends to the same infinity at both ends, so it has a global maximum or minimum. A polynomial of odd degree from to is always onto (by the intermediate value theorem), and it is one-one exactly when it is monotonic, which can be checked with . Every periodic function on is many-one.
Finite sets. If with finite, then is one-one if and only if it is onto. If inputs give distinct outputs in an -element set, every output is used; conversely, if all outputs are used by inputs, no two inputs can share one. This pigeonhole argument fails for infinite sets, as Brain-Teaser 3 shows. More generally, a one-one map forces , and an onto map forces .
Counting functions from (with elements) to (with elements).
All functions: each of the inputs independently chooses one of outputs, giving . Note that this is , not : the base is the number of choices, the exponent is the number of choosers.
One-one functions (requires ): the first input has choices, the next , and so on, giving . If there are none.
Bijections (requires ): .
Onto functions (requires ): count all functions and subtract those that miss at least one output, using inclusion-exclusion over the missed outputs:
For this gives : every function except the two constant ones.
Into functions: total minus onto.
Key Takeaways:
- One-one: ; horizontal line test; strictly monotonic implies one-one.
- Onto: range codomain. Always compute the range and compare.
- Changing the codomain changes onto-ness; restricting the domain can create one-one-ness.
- Even-degree polynomials : neither one-one nor onto. Odd-degree: always onto.
- Finite , : one-one onto bijective.
- Counts: all ; one-one ; bijections ; onto .
- Onto maps from elements to elements: . Onto maps from elements to elements: .
- Pitfall: writing for the number of functions from to .
Brain-Teaser 1: Find the number of onto functions from a -element set to a -element set, and verify the answer by a direct count.
Solution: By inclusion-exclusion, . Direct check: an onto map splits the inputs into non-empty groups, then assigns the groups to the outputs. The group sizes are or . The number of ways to form groups of sizes is , and of sizes is , so there are ways to split. Assigning the groups to the outputs gives ways, and . Having two independent methods that agree is the best check you can have in the exam.
Brain-Teaser 2: Decide whether and , both as maps , are one-one, onto, or bijective.
Solution: Both are odd-degree polynomials, so both are onto. For one-one-ness, check monotonicity. for all , so is strictly increasing and therefore one-one; is a bijection. changes sign at , and indeed , three inputs with the same output, so is many-one and not a bijection. The small change from to creates a local maximum and minimum, and a turning point is what makes a continuous function fail the horizontal line test.
Brain-Teaser 3: Give a function that is one-one but not onto, and one that is onto but not one-one. Why doesn't this contradict the finite-set result?
Solution: is one-one ( forces ), but is never attained, so it is not onto. (so ) is onto, since , but , so it is not one-one. The finite result relied on counting: distinct images inside an -element set must fill it. An infinite set can be put in one-one correspondence with a proper subset of itself, as does with and , so the counting argument breaks. The equivalence 'one-one onto' is a genuinely finite phenomenon.
Practice this concept
Free · no account required · instant solutions