The unit on sets, images and inverse images introduced images and inverse images of subsets. This unit concentrates on the behavior of a function as a whole: whether distinct inputs may share an output (injectivity), whether every element of the codomain is hit (surjectivity), and how these properties interact with composition. The main result is that a function has an inverse exactly when it is bijective, and that composition reverses the order of inverses. We use the proof techniques of units 1.1 and 1.2 and the set language of unit 2.1.
Definitions
Definition 2.4.1
(Function, injective, surjective, bijective)
A function assigns to each exactly one element ; is the domain and the codomain. The function is determined by the triple of , and the rule, so as a map and as a map are different functions.
- is injective if implies for all .
- is surjective if for every there is with , that is, .
- is bijective if it is both injective and surjective.
Definition 2.4.2
(Identity, composition and one-sided inverses)
The identity function on is . The composition of and is , . Composition is associative: , since both send to .
A function is a left inverse of if , a right inverse if , and an inverse if it is both.
Composition
Theorem 2.4.3
(Injectivity and surjectivity under composition)
Let and .
- If and are injective, then is injective.
- If and are surjective, then is surjective.
- If is injective, then is injective.
- If is surjective, then is surjective.
Proof
(Follow one element through both functions)
(1) If , injectivity of gives and injectivity of gives . (2) For choose with , then with ; then . (3) If , applying gives , so . (4) For there is with , so with .
Parts (3) and (4) cannot be strengthened to the other function: injective does not force to be injective, and surjective does not force to be surjective.
Counterexample mode
A surjective composite does not make the inner function surjective
Claim: if is surjective, then is surjective. On let and for , . Then , so is surjective. But is not surjective: would need , which no natural number satisfies. The repair is the true statement that must be surjective; nothing follows about . Likewise this is not injective, since , though is injective.
Inverses
Theorem 2.4.4
(A function has an inverse exactly when it is bijective)
A function has an inverse if and only if it is bijective. In that case the inverse is unique; it is denoted , and it is also bijective with .
Proof
(Define as the unique preimage)
Suppose is an inverse. If , then , so is injective. For , , so lies in the image and is surjective. Conversely, let be bijective. For each there is at least one with by surjectivity and at most one by injectivity; define to be this . Then , and because is the unique element mapping to . For uniqueness, if are both inverses, then . The last assertions follow from the symmetry of the definition.
Proof X-ray
Where each half of bijectivity is used
The two halves of the bijectivity hypothesis do separate jobs in the construction of . Surjectivity makes defined for every , since a preimage exists; injectivity makes well defined, since the preimage is unique. If either half is missing, the recipe breaks in a different place: a non-surjective leaves some undefined, and a non-injective offers several candidates. The two identities and are not symmetric consequences of the recipe. The second is immediate from the definition of , while the first uses uniqueness of the preimage. The uniqueness argument is a different kind of step: it does not use bijectivity at all, only the associativity of composition, so it shows that any two-sided inverse, however obtained, equals .
Theorem 2.4.5
(One-sided inverses)
(a) If has a left inverse, then is injective; if has a right inverse, then is surjective. (b) If is injective and , then has a left inverse.
Proof
(Reuse the composition theorem, then patch the complement)
(a) follows from parts (3) and (4) of the composition theorem with or , since identities are bijective. (b) Fix . For let be the unique with , and for set . Then for every .
Theorem 2.4.6
(Inverse of a composite)
If and are bijective, then is bijective and .
Proof
(Check the candidate on both sides)
Bijectivity follows from parts (1) and (2) of the composition theorem. Moreover , and similarly on the other side. By uniqueness of the inverse the claim follows.
Worked examples
Worked example 2.4.7
(Testing and inverting)
Let , .
Well-defined into : for , , so . Injective: if , cross-multiplying gives , so . Surjective: given , set . Then and . Hence is bijective with .
Worked example 2.4.8
(Composition with a lopsided pair)
Let , , , with , , and , , . Then sends , , so is bijective. By the composition theorem, is injective and is surjective. But is not surjective (nothing maps to ) and is not injective ().
Worked example 2.4.9
(The codomain matters)
The function , is neither injective () nor surjective ( is not a square). The function , is surjective but still not injective. The function , is bijective with inverse . The three are different functions despite the same formula.
Worked example 2.4.10
(A left inverse without a right inverse)
On let . It is injective but not surjective, since is not in the image. A left inverse is for and : indeed . There is no right inverse by the one-sided inverse theorem, because a right inverse would make surjective. The left inverse is not unique: setting gives another one.
Common mistakes and subtle points
Common mistake
(Confusing the inverse function with the inverse image)
The inverse image is defined for every function; the inverse function exists only for bijective . For on , the set makes sense although has no inverse function.
Common mistake
(Ignoring the codomain)
Surjectivity depends on . Always state the codomain together with the rule: is not surjective onto but is surjective onto .
Common mistake
(Reversing the order in the inverse of a composite)
The inverse of "first , then " is "first , then ", that is , not (which usually is not even defined).
Two further points. To prove injectivity one assumes for arbitrary and deduces ; to refute it, one exhibits one pair of distinct inputs with equal outputs, and examples alone never prove it. Every surjective function has a right inverse, but for infinite sets this requires choosing one preimage for each point; this unit does not need that fact.
Exercises
Quick check
(Let and . Prove that if is injective and is surjective, then is injective.)
Start from and use surjectivity of to pull back to .
Solution · Guided solution
Suppose . Since is surjective, choose with and . Then , and injectivity of gives . Hence .
Quick check
(Decide whether each function is injective, surjective, both or neither: (a) , ; (b) , .)
Look for a value hit twice and a value never hit.
Solution · Guided solution
(a) is surjective: for , . It is not injective: although . So it is surjective but not injective. (b) is injective: gives . It is not surjective: is not in the image. So it is injective but not surjective.
Quick check
(Show that , is bijective and find its inverse.)
Prove injectivity from strict monotonicity of cubing, and solve for surjectivity.
Solution · Guided solution
Injective: if then , and since is strictly increasing on (if then ), . Surjective: for the real number satisfies . So is bijective and . Check: .
Quick check
(Let , . Does have a right inverse? Does it have infinitely many left inverses?)
A right inverse would need to hit .
Solution · Guided solution
There is no right inverse: a right inverse would satisfy , but for every . Left inverses are the functions with for all and arbitrary. Each of the infinitely many choices with gives a different left inverse, so there are infinitely many.
Quick check
(Let and be bijections. Prove directly that is an inverse of .)
Compose on both sides and cancel the inner pair each time.
Solution · Guided solution
Let . For , . For , . So and , and is an inverse of .