• In this section, we will look at three special
classes of functions and see how their properties
lead us to the theory of counting.
• So far, we have the general notion of a function
f: X → Y, but in terms of the comparative sizes
of the three sets involved (X, Y and f ), all we
can say is that f  = X.
• In this section, we compare X with Y.
Oneto one Functions
• Definition: A onetoone (injective) function f
from set X to set Y is a function such that each
x in X is related to a different y in Y .
• More formally, we can restate this definition as
either:
f :X → Y is 11 provided
f(x_{1}) = f(x_{1}) implies x_{1} = x_{2},
or f :
X → Y is 11 provided
x_{1} ≠ x_{2} implies f(x_{1}) ≠ f(x_{2}).
Illustrative Examples
• The function be low is 11:
This function is not:
Proving Functions Are 11
• If f: R→ R is given by f (x) = 3x + 7, prove it is
onetoone.
• Proof: As sume f (a) = f (b). Show a = b.
Now f (a) = f (b) means 3a + 7 = 3b + 7, so
3a = 3b, therefore a = b.
• Why is f: R → R given by f (x) = x^{2} not 11?
• Since 9 = f(3) = f(3), but 3 ≠ 3, the definition is
violated.
Onto Functions
• Definition: A function f: X → Y is said to be onto
(surjective) if for every y in Y, there is an x in X
such that f (x) = y.
• This can be restated as: A function is onto when
its image equals its range, i.e. f (X) = Y.
• Examples:
ONTO

NOT ONTO

Testing Onto For Infinite Functions
• Show that f: R → R given by f (x) = 5x  7 is onto.
• Let y be in R. Then (y + 7) and (y + 7)/5 are also
real numbers .
Now f( (y + 7)/5 ) = 5[(y + 7)/5]  7 = y, hence
if y is in R, there exists an x in R such that
f (x) = y.
• Is f: R→ R given by f (x) = 1/x onto?
• No! There is no x in R that has output = 0.
Onetoone Correspondences
• Definition: A function is called a onetoone
correspondence (bijection) if it is onetoone and
onto.
• Onetoone correspondences define the theory of
counting. Why?
• If f: X → Y is onetoone, then X ≤ Y, and if f
is onto, then X≥ Y, so if f is both, X = Y.
• Hence, to count the elements of an unknown set ,
we create a 11 correspondence between the set
and a set of known size. Simple !
Inverse Functions
• Recall that the inverse relation is created by
inverting all the ordered pairs that comprise the
original relation.
• When is the inverse of a function itself a
function?
not onto
(f ^{1} not def.) 
onto
not 11
(f ^{1} not welldef.) 
both
(f ^{1} is a function) 
Finding Inverse Functions
• Theorem: If f: X → Y is a onetoone and onto,
then f ^{1} is a onetoone and onto function.
• Given f , how do we find f ^{1}?
• Let f: R → R be given by f (x) = 4x  1 = y. Now,
swap x and y and solve for y :
• Thus f ^{1 } (x) = (x + 1)/4.