Page 165 - Discrete Mathematics and Its Applications

144 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

(a) One-to-one, (b) Onto, (c) One-to-one, (d) Neither one-to-one (e) Not a function
not onto not one-to-one and onto nor onto
1 a a 1 a 1 1
a 1 a
2 b b 2 b 2 2
b 2 b
3 c c 3 c 3 3
c 3 c
4 d d 4 d 4 4

FIGURE 5 Examples of Different Types of Correspondences.

Solution: This function is onto, because for every integer y there is an integer x such that
f(x) = y. To see this, note that f(x) = y if and only if x + 1 = y, which holds if and only if
x = y − 1. ▲

EXAMPLE 15 Consider the function f in Example 11 that assigns jobs to workers. The function f is onto if
for every job there is a worker assigned this job. The function f is not onto when there is at
least one job that has no worker assigned it. ▲

DEFINITION 8 The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and
onto. We also say that such a function is bijective.

Examples 16 and 17 illustrate the concept of a bijection.

EXAMPLE 16 Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f(a) = 4, f(b) = 2, f(c) = 1, and
f(d) = 3. Is f a bijection?

Solution: The function f is one-to-one and onto. It is one-to-one because no two values in
the domain are assigned the same function value. It is onto because all four elements of the
codomain are images of elements in the domain. Hence, f is a bijection. ▲

Figure 5 displays four functions where the first is one-to-one but not onto, the second is onto
but not one-to-one, the third is both one-to-one and onto, and the fourth is neither one-to-one
nor onto. The fifth correspondence in Figure 5 is not a function, because it sends an element to
two different elements.
Suppose that f is a function from a set A to itself. If A is finite, then f is one-to-one if and
only if it is onto. (This follows from the result in Exercise 72.) This is not necessarily the case
if A is infinite (as will be shown in Section 2.5).

EXAMPLE 17 Let A be a set. The identity function on A is the function ι A : A → A, where

ι A (x) = x

for all x ∈ A. In other words, the identity function ι A is the function that assigns each element
to itself. The function ι A is one-to-one and onto, so it is a bijection. (Note that ι is the Greek
letter iota.) ▲

For future reference, we summarize what needs be to shown to establish whether a function
is one-to-one and whether it is onto. It is instructive to review Examples 8–17 in light of this
summary.