Discrete Mathematics for Computer Science

248 CHAPTER 4 Functions

4.3.3 Other Operations on Functions

The reader is familiar with operations on polynomial functions. Consider polynomial

functions F, G : R --> R where F(x) = x2 and G(x) = 2x + 1. Then, (F + G)(x) is de-

fined as

(F + G)(x) = F(x) + G(x) = x2 + 2x + 1

This is a very different sort of operation on functions in that it uses the operation + on

1R, whereas composition and inversion operations make no reference to operations on the

codomain of the function.

Definition 3. Let F, G : X -R 1 be functions. The following are functions:

(F+G) : X--1R

x - F(x) + G(x)

(F -G): X R

x - F(x) • G(x)

IFl: X-R

x-÷ I F(x)l

Define the following partial function:

(F/G) : X --> R by the rule (F/G)(x) = F(x)/G(x)

The function F/G is total if and only if G(x) A 0 for all x E X.

Of course, the same definitions make sense if the codomain is Q, Z, or N. In general,

any operation on the codomain may be used to define an operation on functions.

Definitions such as Definition 3 create some very ambiguous notation. For x, a real

number, x-^1 denotes 1/x. So, F-l(x) should denote 1/F(x). The symbol F-^1 , how-

ever, also means the inverse function, which is not at all the same thing. The symbol F-1

usually-but not always-denotes the inverse function. In this book, we shall use F-1 only

to denote the inverse function.

Sequences and Subsequences

This section introduces functions defined on N and its subsets that we commonly refer to

as sequences. Subsequences are formed by using the operation of composition of functions

on subsets of N.

Intuitively, a sequence is a list of objects in order, such as

red, orange, yellow, green, blue, indigo, violet

where red is first, followed by orange ... followed by violet. Other sequences are the

prime numbers listed in increasing order:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,....

or the natural numbers in increasing order:

0, 1,2,3,4,5,6,7, 8,9, 10, 11, 12.