46 FUNCTIONS AND ALGORITHMS [CHAP. 3
Consider any functionf:A→B. Thenf◦ (^1) A=f and 1B◦f=f
where 1Aand 1Bare the identity functions onAandB, respectively.
3.3One-to-One, Onto, and Invertible Functions
A functionf:A→Bis said to beone-to-one(written 1-1) if different elements in the domainAhave
distinct images. Another way of saying the same thing is thatfisone-to-oneiff(a)=f(a′)impliesa=a′.
A functionf:A→Bis said to be anontofunction if each element ofBis the image of some element ofA.
In other words,f:A→Bis onto if the image offis the entire codomain, i.e., iff (A)=B. In such a case we
say thatfis a function fromAontoBor thatfmapsAontoB.
A functionf:A→Bisinvertibleif its inverse relationf−^1 is a function fromBtoA. In general, the inverse
relationf−^1 may not be a function. The following theorem gives simple criteria which tells us when it is.
Theorem 3.1: A functionf:A→Bis invertible if and only iffis both one-to-one and onto.
Iff:A→Bis one-to-one and onto, thenfis called aone-to-one correspondencebetweenAandB. This
terminology comes from the fact that each element ofAwill then correspond to a unique element ofBand vice
versa.
Some texts use the termsinjectivefor a one-to-one function,surjectivefor an onto function, andbijectivefor
a one-to-one correspondence.
EXAMPLE 3.3 Consider the functionsf 1 :A→B,f 2 :B→C, f 3 :C→Dandf 4 :D→Edefined by the
diagram of Fig. 3-3. Nowf 1 is one-to-one since no element ofBis the image of more than one element ofA.
Similarly,f 2 is one-to-one. However, neitherf 3 norf 4 is one-to-one sincef 3 (r)=f 3 (u)andf 4 (v)=f 4 (w)
Fig. 3-3As far as being onto is concerned,f 2 andf 3 are both onto functions since every element ofCis the image
underf 2 of some element ofBand every element ofDis the image underf 3 of some element ofC,f 2 (B)=C
andf 3 (C)=D. On the other hand,f 1 is not onto since 3∈Bis not the image underf 4 of any element ofA.
andf 4 is not onto sincex∈Eis not the image underf 4 of any element ofD.
Thusf 1 is one-to-one but not onto,f 3 is onto but not one-to-one andf 4 is neither one-to-one nor onto.
However,f 2 is both one-to-one and onto, i.e., is a one-to-one correspondence betweenAandB. Hencef 2 is
invertible andf 2 −^1 is a function fromCtoB.
Geometrical Characterization of One-to-One and Onto Functions
Consider now functions of the formf: R → R. Since the graphs of such functions may be plot-
ted in the Cartesian planeR^2 and since functions may be identified with their graphs, we might wonder