Discrete Mathematics for Computer Science

(^234) CHAPTER 4 Functions
The horizontal line test for 1-1 functions can be easily modified to check whether a func-
tion is onto by simply requiring that each horizontal line defined by a member of the
codomain meet the graph of the function at least once. In Figure 4.15, the horizontal line
y = -6 does not intersect the graph of G at any point. This property of the graph of the
function corresponds to the fact that there is no number x such that G (x) = -6. Therefore,
G is not onto. On the other hand, the function F(x) = x3, as shown in Figure 4.16, is onto,
since each horizontal line crosses the graph in at least one point.
y
10 __
7.5-
5-
2.5
-3 1 2 3
Figure 4.16 F(x) x^3.
Functions that are both 1-1 and onto play a special role in counting the elements of
a set. Because functions of this class have so many applications, they have been given a
special name.
Definition 8. Let F : X -- Y be a function. F is a 1-1 correspondence if F is both 1-1
and onto.
For example, the function SeatOf is a 1-1 correspondence if and only if each chair has
exactly one student sitting at it. The function F : R -- R defined by F(x) = x^3 , as shown
in Figure 4.16, is also a 1-1 correspondence. The function G(x) = x^2 , as shown in Figure
4.15, is neither 1-1 nor onto.
The function shown in Figure 4.17 is onto but not 1-1.
Y
10-.
7.5-
5-
2.5
-4--- X
-2 2 4 6 8 10
-2.5-
-5-
Figure 4.17 A function that is onto
but not 1-1.