Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

B.3 Functions

Given two sets A and B, a function f is a binary relation on A × B such that for all a ∈ A, there exists precisely one b ∈ B such that (a, b) ∈ f. The set A is called the domain of f, and the set B is called the codomain of f. We sometimes write 3.21), is the infinite sequence 〈0, 1, 1, 2, 3, 5, 8, 13, 21,...〉.

When the domain of a function f is a Cartesian product, we often omit the extra parentheses surrounding the argument of f. For example, if we had a function f : A₁ × A₂ × ··· × A_n → B, we would write b = f (a₁, a₂,..., a_n) instead of b = f ((a₁, a₂,..., a_n)). We also call each a_i an argument to the function f, though technically the (single) argument to f is the n-tuple (a₁, a₂,..., a_n).

If f : A → B is a function and b = f(a), then we sometimes say that b is the image of a under f. The image of a set A' ⊆ A under f is defined by

f(A') = {b ∈ B : b = f(a) for some a ∈ A'}.

The range of f is the image of its domain, that is, f(A). For example, the range of the function f : N → N defined by f(n) = 2n is f(N) = {m : m = 2n for some n ∈ N}.

A function is a surjection if its range is its codomain. For example, the function f(n) = ⌊n/2⌋ is a surjective function from N to N, since every element in N appears as the value of f for some argument. In contrast, the function f(n) = 2n is not a surjective function from N to N, since no argument to f can produce 3 as a value. The function f(n) = 2n is, however, a surjective function from the natural numbers to the even numbers. A surjection f : A → B is sometimes described as mapping A onto B. When we say that f is onto, we mean that it is surjective.

A function f : A → B is an injection if distinct arguments to f produce distinct values, that is, if a ≠ a' implies f(a) ≠ f(a'). For example, the function f(n) = 2n is an injective function from N to N, since each even number b is the image under f of at most one element of the domain, namely b/2. The function f(n) = ⌊n/2⌋ is not injective, since the value 1 is produced by two arguments: 2 and 3. An injection is sometimes called a one-to-one function.

A function f : A → B is a bijection if it is injective and surjective. For example, the function f(n) = (-1)ⁿ ⌈n/2⌉ is a bijection from N to Z:

The function is injective, since no element of Z is the image of more than one element of N. It is surjective, since every element of Z appears as the image of some element of N. Hence, the function is bijective. A bijection is sometimes called a one-to-one correspondence, since it pairs elements in the domain and codomain. A bijection from a set A to itself is sometimes called a permutation.

When a function f is bijective, its inverse f^-1 is defined as

f^-1(b) = a if and only if f(a) = b.

For example, the inverse of the function f(n) = (-1)ⁿ ⌈n/2⌉ is

Exercises B.3-1

Let A and B be finite sets, and let f : A → B be a function. Show that

1. 
   

   if f is injective, then |A| ≤ |B|;



2. 
   

   if f is surjective, then |A| ≥ |B|.

Exercises B.3-2

Is the function f(x) = x + 1 bijective when the domain and the codomain are N? Is it bijective when the domain and the codomain are Z?

Exercises B.3-3

Give a natural definition for the inverse of a binary relation such that if a relation is in fact a bijective function, its relational inverse is its functional inverse.

Exercises B.3-4: ★

Give a bijection from Z to Z × Z.