Injective, surjective and bijective mappings

One assigned locker is a function; two further questions remain

Label three cards 0, 1 and 2, and three lockers 10, 11 and 12. Assign card 0 to locker 10, card 1 to locker 11 and card 2 to locker 12. Every card has exactly one assigned locker. No two cards share a locker, and every declared locker is used.

Now declare a fourth locker, 13, without changing any assignment. The rule still gives every card one locker, and different cards still have different lockers. It no longer uses every declared locker. Alternatively, sending both 0 and 1 to locker 10 still defines a function, but now their outputs collide.

These are different questions: is there one permitted output per input, are outputs shared by different inputs, and does every target get an input? A bijection answers all three positively in the appropriate sense: it is a function with no collision and no unused target.

Prepare the notation and follow one complete arrow table

Functions, domains and ranges supplies the one-output-per-input condition and the difference between a stated target and actual outputs. Composition and inverse functions supplies inside-first evaluation and reversal on the actual range. Examples, explanations and counterexamples supports proving a general claim or refuting it with an allowed case. Symbols, definitions and mathematical language supports giving symbols meanings and stating their scope.

Here a ∈ A means a is a member of A. The statement S ⊆ B means every member of S belongs to B. The product A × B consists of the ordered pairs (a, b) with a ∈ A and b ∈ B. A relation from A to B is any subset of A × B. We define the additional function conditions next, so an earlier set lesson is not needed just to read the arrow diagram.

On a first reading, follow the three-card assignment, the collision and unused-locker examples, and one reversed table. Return to the finite counting proofs, the two composition proofs and the arbitrary-real examples once you can state the domain, codomain and range of one complete finite map.

A function covers every input and chooses exactly one output

A function f : A → B is a relation contained in A × B such that for each a ∈ A there is exactly one b ∈ B with f(a) = b. The set A is its domain and B is its declared codomain. A formula is one way to specify assignments, but a complete finite table can specify them without a formula.

There are two input checks. Coverage requires at least one output for every a ∈ A. Uniqueness requires at most one output for each a. Omitting the arrow from card 2 fails coverage on {0, 1, 2}. Giving card 1 arrows to both 11 and 12 fails uniqueness. Two different cards sharing one locker does neither of those things: each card can still have exactly one output.

The allowed carriers come first. A pair (2, 99) is not in {0, 1, 2} × {10, 11, 12}, so it does not define a permitted assignment to that codomain. A repeated written copy of (1, 11) is still the same mathematical pair, not two different outputs.

This lesson retains the declared type A → B when making property and inverse claims. Changing B changes what an onto claim must reach, even when the graph of assigned pairs is unchanged. Merely saying that two arrow lists agree does not supply the target of a surjectivity claim.

The actual range is the part of the codomain that receives arrows

For a function f : A → B, its range is f(A) = {f(a) : a ∈ A}. This is a subset of B. The domain names all permitted inputs, the codomain names the declared targets, and the range names only targets actually attained.

In the four-locker version, A = {0, 1, 2}, B = {10, 11, 12, 13}, and f(A) = {10, 11, 12}. Locker 13 is an allowed target with no assigned card. It does not become an output merely because it is in B.

We can replace the declared codomain B by the exact range f(A), keeping the same domain and every assignment. This is called corestricting the function to its range. It always makes the resulting function onto that new target, and it does not remove an existing collision. Do not delete outputs to force a smaller codomain that fails to contain the range.

Injectivity compares two permitted inputs

The function f : A → B is injective, or one-to-one, if for every a, a′ ∈ A, f(a) = f(a′) implies a = a′. Equivalently, distinct permitted inputs always give distinct outputs. The original function condition gives one output per input; injectivity adds at most one input per output.

A single collision refutes injectivity: a ≠ a′ but f(a) = f(a′). Sending cards 0 and 1 to 10 is such a witness. An unused target does not refute injectivity; the four-locker assignment still has no collision.

In a complete finite diagram, every target has at most one incoming arrow exactly when the function is injective. For an infinite domain, a few arrows or sample values cannot prove the universal condition. Start with arbitrary permitted a and a′, suppose their outputs agree, and use the rule to establish that the inputs agree.

Surjectivity starts with an arbitrary declared target

The function f : A → B is surjective, or onto B, if for every b ∈ B there exists an a ∈ A with f(a) = b. The chosen input may depend on b. This is equivalent to f(A) = B. It is not the claim that one input gives every output.

An unused permitted target refutes surjectivity: find b ∈ B that no allowed input produces. Locker 13 witnesses failure in the four-locker assignment. Collisions do not refute surjectivity if all targets are still reached: four cards can cover three lockers while two cards share one of them.

A function is bijective when it is both injective and surjective. Equivalently, each b ∈ B has exactly one preimage in A: surjectivity supplies existence and injectivity supplies uniqueness. The set of preimages of b consists of all a ∈ A with f(a) = b; it may be empty, a singleton or have several members.

Empty carriers must still satisfy the declared function condition

For any B, there is exactly one function ∅ → B: the empty relation. There is no domain member requiring an output, so its function condition and injectivity hold vacuously. Its range is ∅. It is surjective exactly when B = ∅, because a nonempty B contains a target that has no preimage.

There is no function from a nonempty A to ∅. Every a ∈ A would need an output in a codomain with no members. The empty relation is still a relation in A × ∅, but it fails the required input coverage. Do not label this nonfunction injective or surjective.

The empty function ∅ → ∅ is bijective. Its converse and inverse are both the empty function, and both inverse identities hold on empty carriers. An empty diagram represents this precise case; it does not contain an invented placeholder input or target.

Finite counts constrain the arrows without classifying every rule

Let A and B be finite and let f : A → B actually be a function. Write |A| = n and |B| = m for their numbers of members. If f is injective, its n inputs produce n distinct targets within B, so n ≤ m. If n > m, no such function can be injective: at least two inputs must share an output.

If f is surjective, the preimage sets of the m targets are nonempty, disjoint, and together contain all n inputs. Adding their finite sizes gives n as a sum of m positive integers, so n ≥ m. If n < m, no function A → B can hit every target.

When n = m, an injective function uses n distinct targets, hence all m targets, so it is surjective. Conversely, if a surjective function had a collision, its n inputs would produce at most n − 1 distinct targets, contradicting the m = n targets that must be reached. Thus, for functions between finite sets of equal size, injective, surjective and bijective are equivalent.

The count inequalities are necessary conditions, not a classification of a particular function. Three inputs and three targets allow a bijection, but the constant assignment is neither injective nor surjective when there are three targets. These arguments include n = m = 0 once the empty function has been established. The case n > 0 and m = 0 has no function in the first place.

Do not transfer the equal-size finite conclusion to infinite carriers. On ℕ₀ = {0, 1, 2, …}, the map n ↦ n + 1 has the same domain and codomain, is injective, and misses 0. Its proof uses n + 1 = n′ + 1 to obtain n = n′; its missed target is explicit.

Reversed arrows form a function on B exactly for a bijection

The converse relation reverses every pair: from (a, b) to (b, a). It is always a relation contained in B × A, but may not be a function B → A. A missed target in the original becomes a reversed input with no output. A collision becomes a reversed input with two different outputs.

Original function on its declared codomain

Does the relation define the declared function?

Yes

Every pair reversed on the entire original codomain

Does the relation define the declared function?

No

This relation fails the declared function condition. Injectivity, surjectivity, range and inverse-function claims are held here; the related-output and related-input tables still show the exact relation.

The original function is not bijective onto its declared codomain, so this converse is not an inverse function on that whole codomain.

The same assignments with the codomain changed to the actual range

Does the relation define the declared function?

Yes

Reversed pairs after corestriction

Does the relation define the declared function?

Yes

The corestricted function is bijective; its reverse is an inverse with domain equal to the original range.

If f : A → B is bijective, each b ∈ B has exactly one original input a. Define k(b) to be that unique a. Then k : B → A is a function, k(f(a)) = a for every a ∈ A, and f(k(b)) = b for every b ∈ B. It is the inverse function f⁻¹. The exponent −1 here denotes reversal, not the reciprocal 1/f(a).

Conversely, suppose a function k : B → A satisfies both identities. If f(a) = f(a′), applying k gives a = a′, so f is injective. For any b ∈ B, the input k(b) belongs to A and produces b, so f is surjective. Therefore an inverse on all of the declared B exists if and only if f is bijective. It is unique, since every inverse must send b to its sole preimage.

An injective function that misses some of B has no inverse with domain all of B. After corestricting it to f(A), it is bijective and has an inverse f(A) → A. Corestricting a noninjective function makes it surjective, but its reversed collision remains; an inverse function still fails. No arbitrary choice of one among several preimages is used in these inverse proofs.

Compose compatible types and prove each closure property

Let f : A → B and g : B → C. Their composition g ∘ f : A → C sends a to g(f(a)): f acts first. Every intermediate f(a) lies in B, so g accepts it. More generally it is enough that f(A) lies in g’s domain, but our complete typed chains use the same declared middle set B.

The first stage swaps the two labelled assignments; the second sends its two middle members to two different targets.

The resulting function from A to C

Does the relation define the declared function?

Yes

If both f and g are injective, suppose g(f(a)) = g(f(a′)). Injectivity of g gives f(a) = f(a′), and injectivity of f gives a = a′. Thus g ∘ f is injective. Both no-collision reasons occur in the proof; injectivity of the inside function alone need not stop the outside function merging its outputs.

If both f and g are surjective, take any c ∈ C. Surjectivity of g supplies b ∈ B with g(b) = c; surjectivity of f supplies a ∈ A with f(a) = b. Hence g(f(a)) = c, proving that g ∘ f is surjective. Surjectivity of the outside function alone is insufficient if f never reaches the required middle input.

If both functions are bijective, both preceding proofs apply, so their composition is bijective. Its inverse is f⁻¹ ∘ g⁻¹: reverse the outside stage first, then the inside stage. The inverse has type C → A, and substitution in either direction cancels the two stages on their stated carriers.

A property of the composition forces only the correct stage

If g ∘ f is injective, then f is injective. Indeed f(a) = f(a′) implies g(f(a)) = g(f(a′)); injectivity of the composite gives a = a′. It need not make g injective on all of B, because f may never reach the middle members involved in g’s collision.

The first stage misses middle member 12. The second merges 11 and 12, but only 11 is reached by the first stage.

The resulting function from A to C

Does the relation define the declared function?

Yes

If g ∘ f is surjective onto C, then g is surjective onto C. Given c ∈ C, a composite preimage a provides the middle preimage f(a) ∈ B for g. It need not make f surjective onto B, because C can already be covered without using every middle member.

Use A = {0, 1}, B = {10, 11, 12}, C = {20, 21}. Set f(0) = 10 and f(1) = 11; set g(10) = 20, g(11) = 21 and g(12) = 21. The composite sends 0 to 20 and 1 to 21, so it is bijective. Yet f misses 12 and g collides at 11 and 12. Neither stage is bijective.

This one complete example refutes both incorrect reversals: an injective composite does not force g to be injective, and a surjective composite does not force f to be surjective. The valid consequences of a bijective composite are that f is injective and g is surjective. A later stage cannot undo an earlier collision; a first stage cannot reach a target that the last stage never reaches.

The same formula can change its classification when carriers change

Fix real constants α and β with α ≠ 0. The map f : ℝ → ℝ given by f(x) = αx + β is injective: αx + β = αx′ + β implies x = x′ after subtracting β and dividing by the permitted nonzero α. It is surjective: for any real y, the real input x = (y − β)/α produces y. Its inverse is y ↦ (y − β)/α on all real y.

These two diagrams are complete finite restrictions of the square rule. They display a signed-input collision and its removal by restricting the domain; the prose proves the separate claims on infinite real carriers.

Does the relation define the declared function?

Yes

For α = 2 and β = 1, the same formula viewed as ℤ → ℤ is injective but not surjective: it attains exactly the odd integers. Each odd y has integer preimage (y − 1)/2, but 0 has no integer preimage. Solving for an input is not enough; the input must belong to the stated carrier.

The square map q : ℝ → ℝ, q(x) = x², is neither injective nor surjective. Inputs −1 and 1 collide, and target −1 is never reached. Corestricting to [0, ∞), the nonnegative reals, makes q surjective because each y ≥ 0 is attained at √y, but it still has that collision.

Restrict the domain as well: q₊ : [0, ∞) → [0, ∞), q₊(x) = x². If x² = x′² with x, x′ ≥ 0, then (x − x′)(x + x′) = 0. Either x = x′, or x + x′ = 0 forces both to be 0, again equal. It is surjective by x = √y, so it is bijective with inverse √y. The identity √(x²) = x holds on this nonnegative domain; on all of ℝ it equals |x| instead.

A finite square-arrow window can display exact collisions and examples, but cannot establish these claims on every real or integer input. The general proofs supply that scope. Corestriction changes the codomain; domain restriction changes the permitted inputs. They are different operations.

Predict the classification, then inspect complete finite evidence

In Function checks, predict whether the relation first defines a function on its exact A → B. Then inspect every output set and every target’s preimage set. The complete arrow diagram and tables distinguish a missing input, a split input, a collision, an unused target and all three empty-carrier cases.

In Reverse the arrows, compare the converse on all of B with the converse after changing B to the actual range. The input and output carriers swap. An empty preimage breaks coverage; two preimages break uniqueness. The table verifies both inverse identities only when an inverse function actually exists.

In Compose the stages, follow every a through its middle value f(a) to g(f(a)). Compare the three classifications separately. The bijective-composite counterexample uses a middle member that the first function never reaches; the last function’s collision involving that member does not create a composite collision.

These are complete finite models, not samples offered as infinite proofs. A good answer names the carriers, first establishes the function condition, and gives the appropriate arbitrary-input proof or exact failure witness. When changing a carrier, restate the target of every onto or inverse claim.

Worked examples

Try it yourself

1. Declare A = {0, 1, 2} and B = {10, 11, 12}. Compare the pairs (0, 10), (1, 11) with the pairs (0, 10), (1, 11), (1, 12), (2, 12). Do either define functions A → B?

   Show the answer and reasoning

   Neither. The first omits input 2; the second gives input 1 two different outputs.

   Input coverage and output uniqueness are both required. The classification as injective or surjective in this lesson is held until the declared relation is actually a function.

2. Let A = {0, 1, 2}, B = {10, 11}, and f(0) = f(1) = 10, f(2) = 11. Is it a function? Is it injective or surjective?

   Show the answer and reasoning

   It is a function and is surjective onto B, but is not injective.

   Each input has one output; sharing an output does not violate that condition. Every target is attained. The distinct inputs 0 and 1 give the collision that refutes injectivity.

3. Surjectivity says that every b ∈ B has some a ∈ A with f(a) = b. Does the same input a have to work for every b? Can two inputs share one target in a surjection?

   Show the answer and reasoning

   The input may depend on b. Two inputs may share a target, provided every target still has at least one preimage.

   The quantifier order is for every target, there exists an input; it does not say there exists one input for all targets. Injectivity, not surjectivity, rules out shared outputs from distinct inputs.

4. A function goes from a finite three-member A to a finite three-member B. If it is injective, must it be surjective? Do the equal counts alone prove it is bijective?

   Show the answer and reasoning

   Injectivity forces surjectivity in this finite equal-size case. Equal counts alone do not establish bijectivity.

   Three distinct outputs inside a three-member B use every target. A constant rule on that same type is a function but has a collision and two missed targets.

5. A and B are finite. Can a function with |A| = 5 and |B| = 3 be injective? Can one with |A| = 2 and |B| = 4 be surjective? Give a counting reason for each.

   Show the answer and reasoning

   No in both cases. Five distinct outputs cannot fit into three targets; two inputs cannot attain four distinct targets.

   Injectivity would require |A| ≤ |B|, and surjectivity would require |A| ≥ |B|. These are consequences for actual functions, not a substitute for checking input coverage and uniqueness.

6. Classify the empty relation for types ∅ → ∅, ∅ → {10}, and {0} → ∅. For which types is it a function, injective, surjective and bijective?

   Show the answer and reasoning

   ∅ → ∅ is a bijective function. ∅ → {10} is an injective function that is not surjective. The relation for {0} → ∅ is not a function.

   Empty domains impose no output requirement and no collision. Surjectivity onto {10} still needs a preimage of 10. The nonempty domain {0} requires an output in the empty codomain, which is impossible.

7. An injective function A → B has range S strictly smaller than B. Is its converse a function on B? What changes after corestriction to S?

   Show the answer and reasoning

   The converse is not a function on all of B because each member of B outside S has no output. After corestriction, the converse is the inverse function S → A.

   Injectivity supplies at most one preimage; surjectivity onto the inverse’s domain supplies at least one. Both are required for reversing the whole declared type.

8. A function maps both 0 and 1 to 10 and maps 2 to 11. Can corestricting its codomain to {10, 11} make it bijective?

   Show the answer and reasoning

   No. It becomes surjective onto {10, 11}, but the collision f(0) = f(1) = 10 remains.

   Corestriction keeps the domain and assignments. Its converse still gives the reversed input 10 two different outputs. Choosing only one would discard a forward pair and would not be a two-sided inverse.

9. Let f : A → B and g : B → C. What follows about the stages if g ∘ f is injective? What follows if it is surjective? Must both stages be bijective if the composition is bijective?

   Show the answer and reasoning

   An injective composite forces f to be injective. A surjective composite forces g to be surjective. A bijective composite need not have bijective stages.

   An f-collision passes through g to a composite collision; a composite preimage is also a g-preimage via its middle value. The complete A = {0, 1}, B = {10, 11, 12}, C = {20, 21} example has a bijective composite while f misses 12 and g merges 11 with 12.

10. Let f : {0} → {10, 11} send 0 to 10, and let g : {10, 11} → {20, 21} send 10 to 20 and 11 to 21. Is the surjectivity of g enough to make g ∘ f surjective?

    Show the answer and reasoning

    No. The composite sends its only input 0 to 20 and misses target 21.

    The only middle preimage of 21 is 11, but f never reaches 11. The proof of surjective composition needs both stages to be onto their stated targets.

11. Compare x² as ℝ → ℝ, ℝ → [0, ∞), and [0, ∞) → [0, ∞). Give the classification and a witness or proof for each.

    Show the answer and reasoning

    The first is neither injective nor surjective. The second is surjective but not injective. The third is bijective, with inverse √y on y ≥ 0.

    Inputs −1 and 1 collide in the first two domains, and target −1 is missed only when it belongs to the declared codomain ℝ. Every y ≥ 0 is attained at √y. On the nonnegative domain equal squares have equal inputs, so the last rule also has unique preimages.

12. On ℕ₀ = {0, 1, 2, …}, the map n ↦ n + 1 has the same domain and codomain. Is it bijective? Why does the finite equal-size rule not settle this example?

    Show the answer and reasoning

    It is injective but not surjective, because it misses 0. The equal-size equivalence of the three properties required finite sets.

    Adding 1 preserves inequality of distinct integer inputs, but no nonnegative integer becomes 0 after adding 1. A missing target can coexist with injectivity on an infinite carrier; the finite counting proof does not apply.

What to carry forward

• A function gives every declared input exactly one output in its codomain. Classify it only after that condition has been established.
• Injectivity prevents collisions; surjectivity reaches every declared target. Bijectivity gives each target exactly one preimage.
• Finite injections require |A| ≤ |B| and finite surjections require |A| ≥ |B|. Equal finite sizes make injectivity and surjectivity equivalent for an actual function.
• A two-sided inverse on all of B exists exactly when f : A → B is bijective. An injective non-surjection has an inverse on its actual range after corestriction.
• Compatible compositions preserve injectivity, surjectivity and bijectivity when both stages have the property. An injective composite forces only the inside stage to be injective; a surjective composite forces only the outside stage to be surjective.
• Domains and codomains affect the conclusion, including empty carriers and infinite formulas. A finite picture illustrates exact finite evidence rather than proving an infinite universal claim.