Page 164 - Discrete Mathematics and Its Applications

2.3 Functions 143

a
b 1

c 2
d 3

FIGURE 4 An Onto Function.

DEFINITION 6 A function f whose domain and codomain are subsets of the set of real numbers is called
increasing if f(x) ≤ f(y), and strictly increasing if f (x)<f (y), whenever x< y and x
and y are in the domain of f. Similarly, f is called decreasing if f(x) ≥ f(y), and strictly
decreasing if f (x)>f (y), whenever x< y and x and y are in the domain of f. (The word
strictly in this definition indicates a strict inequality.)

Remark: A function f is increasing if ∀x∀y(x < y → f(x) ≤ f(y)), strictly increasing if
∀x∀y(x < y → f (x) < f (y)), decreasing if ∀x∀y(x < y → f(x) ≥ f(y)), and strictly de-
creasing if ∀x∀y(x < y → f (x) > f (y)), where the universe of discourse is the domain of f.

From these definitions, it can be shown (see Exercises 26 and 27) that a function that is
either strictly increasing or strictly decreasing must be one-to-one. However, a function that is
increasing, but not strictly increasing, or decreasing, but not strictly decreasing, is not one-to-one.
For some functions the range and the codomain are equal. That is, every member of the
codomain is the image of some element of the domain. Functions with this property are called
onto functions.

DEFINITION 7 A function f from A to B is called onto, or a surjection, if and only if for every element
b ∈ B there is an element a ∈ A with f(a) = b. A function f is called surjective if it is onto.

Remark: A function f is onto if ∀y∃x(f (x) = y), where the domain for x is the domain of the
function and the domain for y is the codomain of the function.

We now give examples of onto functions and functions that are not onto.

EXAMPLE 12 Let f be the function from {a, b, c, d} to {1, 2, 3} defined by f(a) = 3, f(b) = 2, f(c) = 1,
and f(d) = 3. Is f an onto function?

Solution: Because all three elements of the codomain are images of elements in the domain, we
see that f is onto. This is illustrated in Figure 4. Note that if the codomain were {1, 2, 3, 4},
then f would not be onto. ▲

2
EXAMPLE 13 Is the function f(x) = x from the set of integers to the set of integers onto?
2
Solution: The function f is not onto because there is no integer x with x =−1, for instance. ▲

EXAMPLE 14 Is the function f(x) = x + 1 from the set of integers to the set of integers onto?