Page 163 - Discrete Mathematics and Its Applications

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

a 1
b 2

c 3
d 4

5
FIGURE 3 A One-to-One Function.

Note that a function f is one-to-one if and only if f(a) = f(b) whenever a = b. This way
of expressing that f is one-to-one is obtained by taking the contrapositive of the implication in
the definition.

Remark: Wecanexpressthatf isone-to-oneusingquantifiersas∀a∀b(f (a) = f(b) → a = b)
or equivalently ∀a∀b(a = b → f(a) = f(b)), where the universe of discourse is the domain
of the function.

We illustrate this concept by giving examples of functions that are one-to-one and other
functions that are not one-to-one.

EXAMPLE 8 Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f(a) = 4, f(b) = 5,
f(c) = 1, and f(d) = 3 is one-to-one.

Solution: The function f is one-to-one because f takes on different values at the four elements
of its domain. This is illustrated in Figure 3. ▲

2
EXAMPLE 9 Determine whether the function f(x) = x from the set of integers to the set of integers is
one-to-one.

2
Solution: The function f(x) = x is not one-to-one because, for instance, f(1) = f(−1) = 1,
but 1 =−1.
2
+
Note that the function f(x) = x with its domain restricted to Z is one-to-one. (Techni-
cally, when we restrict the domain of a function, we obtain a new function whose values agree
with those of the original function for the elements of the restricted domain. The restricted
function is not defined for elements of the original domain outside of the restricted domain.) ▲

EXAMPLE 10 Determine whether the function f(x) = x + 1 from the set of real numbers to itself is one-to-
one.

Solution: The function f(x) = x + 1 is a one-to-one function. To demonstrate this, note that
x + 1 = y + 1 when x = y. ▲

EXAMPLE 11 Suppose that each worker in a group of employees is assigned a job from a set of possible
jobs, each to be done by a single worker. In this situation, the function f that assigns a job
to each worker is one-to-one. To see this, note that if x and y are two different workers, then
f(x) = f(y) because the two workers x and y must be assigned different jobs. ▲

We now give some conditions that guarantee that a function is one-to-one.