Discrete Mathematics for Computer Science

Basic Definitions 231

(c) For x E IR, let Sqrt(x) be the non-negative square root of x. Then, Sqrt is a partial

function, since Sqrt(x) is undefined for x < 0. The domain of definition of Sqrt is iR,

and its codomain is R. The range of Sqrt is [0, oo).

Let G be a subset of R. G is the graph of a partial function if, whenever x0 E X,

the vertical line x = xo intersects G in at most one point. We call this the vertical line

test for a partial function. Figure 4.8 shows a subset of R x R that is not a function,

because the vertical line x = -1 does not cross the graph. Sqrt is a partial function,

since no vertical line defined by an element of its domain crosses the graph more than

once.

y

2.5

2

1.5

0.5

-2 2 4 6!^8

Figure 4.8 Graph of partial function Sqrt.

Whether a partial function is a total function depends on what the domain of definition
is defined to be. For example, it was noted that Sqrt is a partial function from JR to IR. If we
declare the domain of definition to be just the set [0, co), then Sqrt is a total function.

4.1.8 1-1 and Onto Functions

Several special types of functions have turned out to be especially important. For exam-
ple, the intuitive notion of counting will be formalized using the properties of functions
introduced in this section.

Definition 6. Let F : X -- Y be a function. F is 1-1 if, for each y E Y, there is, at most,
one x E X such that F(x) = y.

Example 16.

(a) Let F :R -- R be a function defined as F(x) = 2x. F is 1-1.

(b) Let G N -- N be a function defined as G(n) = 2n^2 + 1. G is not 1-1.

Solution.

(a) Since F(xl) = F(x 2 ) means 2xl = 2x2, it follows that xl = X2 and F is 1-1.

(b) Since G(2) = G(-2), the function G is not 1-1. U