## Chapter 4

## FUNCTIONS AND RECURSION

##### 4.1 FUNCTIONS

#### 4.1.1 Terminology

Let *X* and *Y* be two sets. A *partial function* from *X* to *Y* is a mapping of elements of *X* into elements of *Y* such that every element of *X* is mapped onto at the most one element of *Y*. A *total function* from *X* to *Y* is a mapping from *X* to *Y* in which every element of *X* is mapped onto exactly one element of *Y. X* is the *domain* of *f* and *Y* is its *range*. We shall use the notation

f:X→Y

to mean that *f* is a function (either partial or total) from *X* to *Y*. If *X* is the Cartesian product *X*_{1} × *X*_{2} × …. × *X _{n}*, then we shall often write

f:X_{1}×X_{2}× …. ×X→_{n}Y

instead of

f:X→Y

Similarly, if *x _{i}*. =

*T*, 1 ≤

*i*≤

*n*, we shall write

f:T″ →Y

In either case, *f* is an *n variable function*. For ...

Get *Discrete Mathematics* now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.