Discrete Mathematics

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₁ × X₂ × …. × X_n, then we shall often write

f : X₁ × X₂ × …. × 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 ...