Page 173 - Discrete Mathematics and Its Applications

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

Partial Functions

A program designed to evaluate a function may not produce the correct value of the function for
all elements in the domain of this function. For example, a program may not produce a correct
value because evaluating the function may lead to an infinite loop or an overflow. Similarly, in
abstract mathematics, we often want to discuss functions that are defined only for a subset of
√
the real numbers, such as 1/x, x, and arcsin (x). Also, we may want to use such notions as
the “youngest child” function, which is undefined for a couple having no children, or the “time
of sunrise,” which is undefined for some days above the Arctic Circle. To study such situations,
we use the concept of a partial function.

DEFINITION 13 A partial function f from a set A to a set B is an assignment to each element a in a subset
of A, called the domain of definition of f , of a unique element b in B. The sets A and B are
called the domain and codomain of f , respectively. We say that f is undefined for elements
in A that are not in the domain of definition of f . When the domain of definition of f equals
A, we say that f is a total function.

Remark: We write f : A → B to denote that f is a partial function from A to B. Note that
this is the same notation as is used for functions. The context in which the notation is used
determines whether f is a partial function or a total function.
√
EXAMPLE 32 The function f : Z → R where f (n) = n is a partial function from Z to R where the domain of
definition is the set of nonnegative integers. Note that f is undefined for negative integers. ▲

Exercises

1. Why is f not a function from R to R if 5. Find the domain and range of these functions. Note that
a) f(x) = 1/x? in each case, to find the domain, determine the set of
√
b) f(x) = x? elements assigned values by the function.

2
c) f(x) =± (x + 1)? a) the function that assigns to each bit string the number
of ones in the string minus the number of zeros in the
2. Determine whether f is a function from Z to R if
string
a) f (n) =±n.
√ b) the function that assigns to each bit string twice the
2
b) f (n) = n + 1.
2
c) f (n) = 1/(n − 4). number of zeros in that string
c) the function that assigns the number of bits left over
3. Determine whether f is a function from the set of all bit
when a bit string is split into bytes (which are blocks
strings to the set of integers if
of 8 bits)
a) f(S) is the position of a 0 bit in S.
b) f(S) is the number of 1 bits in S. d) the function that assigns to each positive integer the
c) f(S) is the smallest integer i such that the ith bit of largest perfect square not exceeding this integer
S is 1 and f(S) = 0 when S is the empty string, the 6. Find the domain and range of these functions.
string with no bits. a) the function that assigns to each pair of positive inte-
4. Find the domain and range of these functions. Note that gers the first integer of the pair
in each case, to find the domain, determine the set of b) the function that assigns to each positive integer its
elements assigned values by the function. largest decimal digit
a) the function that assigns to each nonnegative integer c) the function that assigns to a bit string the number of
its last digit
ones minus the number of zeros in the string
b) the function that assigns the next largest integer to a
positive integer d) the function that assigns to each positive integer the
largest integer not exceeding the square root of the
c) the function that assigns to a bit string the number of
integer
one bits in the string
d) the function that assigns to a bit string the number of e) the function that assigns to a bit string the longest
bits in the string string of ones in the string