Discrete Mathematics for Computer Science

254 CHAPTER 4 Functions

What can we conclude about the function that maps people to the cars in which they are

riding? Is it 1-1? Is it onto? How far is it from being 1-1? From being onto? A similar

question could be how many of the students in your class have a birthday on the same day

of the week this year. The results of this section will help you answer these and similar

questions as well as see applications of the results presented in other contexts.

For the remainder of this chapter, we will discuss only total functions.

4.6.1 k to 1 Functions

The first step in answering the questions posed at the beginning of this section is to deter-

mine if more than one element in a function's domain must be mapped to a single element

in the function's range.

Definition 1. Let F : X -+ Y be a function. Let k E N. F is k to^1 if, for each y E Y,

there are at most k different x's in X with F(x) = y. Alternatively, for each y E Y,

I {x e X : F(x)= y I <_k

Example 1.

(a) Let F : {0, 1, 2, 31 --* {a, b, c, d} be a function defined as

o

2

3 d

F

F is 2-1.

(b) Let F : (0, 1, 2, 3} -[ {a, b, c} be a function defined as

o

2.

3 d

F

F is 3-1. F is neither 2-1 nor 1-1.

It may seem strange that a 1-1 function is 58 to 1, but it certainly is by the definition.

If k elements are mapped to a given element, the function is not m to 1 for any m < k but,

rather, is m to 1 for any m > k. Definition 1 gives a way to talk about the more important

fact that is the smallest integer for which some element in the codomain has k preimages.

Theorem 1. Let F : X -+ Y is k to 1, and let I Y I be finite, with IYl = n. Then, X is

finite, and I X I < k n.

Proof For each of the n elements of Y, there are at most k elements of X mapped to each

element of Y. So, only k • n elements can be mapped to all the elements of Y. However,