Discrete Mathematics for Computer Science

232 CHAPTER^4 Functions

The function SeatOf (from Example 1(a) in Section 4.1) is 1-1 if and only if exactly

zero or one person is sitting at each chair (and every student is seated at exactly one chair).

Figure 4.9 1-1 Function SeatOf.

Figure 4.9 shows a 1-1 SeatOf function, and Figure 4.10 shows a similar function,

SeatOf 1, that is not 1-1.

Figure 4.10 Function SeatOfl.

The function H(x) = x^2 is not 1-1. This is shown in Figure 4.11. Let G be the graph of

a function with codomain Y C IR. G is the graph of a 1-1 function if, whenever yo e Y,

the line y = yo intersects G in, at most, one point. We call this the horizontal line test for

1-1 functions.

y

(-2, 4), (,4 X

-2 2

Figure 4.11 H(x) = x^2.

The horizontal line y = 4 crosses the graph in Figure 4.11 at more than one point.

Therefore, G is not 1-1. On the other hand, the function F(x) = x^3 , as shown in Figure

4.12, on next page, is 1-1, since each horizontal line crosses the graph in at most one point.

Definition 7. Let F : X - Y be a function. F is onto if, for each y E Y, there is at least

one x E X such that F(x) = y.

Another way to think of the definition of onto is that a function F : X --* Y is onto if

and only if range(F) = codomain(F). Whether a function is onto or not depends on what

the codomain is defined to be. For example, the function Sqrt : [0, oo) -+ R is not onto.

However, if Sqrt is defined to be Sqrt : [0, oo) -+ [0, cc), then Sqrt is onto.