60 FUNCTIONS AND ALGORITHMS [CHAP.

Solved Problems

FUNCTIONS
3.1. Let X = {1, 2, 3, 4}. Determine whether each relation on X is a function from X into X.
(a) f = {(2, 3), (1, 4), (2, 1), (3.2), (4, 4)}
(b) g = {(3, 1), (4, 2), (1, 1)}
(c) h = {(2, 1), (3, 4), (1, 4), (2, 1), (4, 4)}
Recall that a subset f of X × X is a function f : X → X if and only if each a ∈ X appears as the first coordinate
in exactly one ordered pair in f.
(a) No. Two different ordered pairs (2, 3) and (2, 1) in f have the same number 2 as their first coordinate.
(b) No. The element 2 ∈ X does not appear as the first coordinate in any ordered pair in g.
(c) Yes. Although 2 ∈ X appears as the first coordinate in two ordered pairs in h, these two ordered pairs are equal.

3.2. Sketch the graph of: (a) f (x) = x 2 + x − 6; (b) g(x) = x 3 − 3x 2 − x + 3.

Set up a table of values for x and then find the corresponding values of the function. Since the functions are polynomials,
plot the points in a coordinate diagram and then draw a smooth continuous curve through the points. See Fig. 3-8.

Fig. 3-8

3.3. Let A = {a, b, c}, B = {x, y, z}, C = {r, s, t}. Let f : A → B and g: B → C be defined by:

f = {(a, y)(b, x), (c, y)} and g = {(x, s), (y, t), (z, r)}.

Find: (a) composition function g◦f : A → C; (b) Im(f ), Im(g), Im(g◦f ).

(a) Use the definition of the composition function to compute:
(g◦f )(a) = g(f (a)) = g(y) = t
(g◦f )(b) = g(f (b)) = g(x) = s
(g◦f )(c) = g(f (c)) = g(y) = t
That is g◦f = {(a, t), (b, s), (c, t)}.
(b) Find the image points (or second coordinates):

Im(f ) = {x, y}, Im(g) = {r, s, t}, Im(g◦f ) = {s, t}

CHAP. 3] FUNCTIONS AND ALGORITHMS 61

3.4. Let f : R → R and g: R → R be defined by f (x) = 2x + 1 and g(x) = x 2 − 2. Find the formula for the
composition function g◦f .
Compute g◦f as follows: (g◦f )(x) = g(f (x)) = g(2x + 1) = (2x + 1)2 − 2 = 4x 2 + 4x − 1.
Observe that the same answer can be found by writing

y = f (x) = 2x + 1 and z = g(y) = y 2 − 2

and then eliminating y from both equations:

z = y 2 − 2 = (2x + 1)2 − 2 = 4x 2 + 4x − 1

ONE-TO-ONE, ONTO, AND INVERTIBLE FUNCTIONS

3.5. Let the functions f : A → B, g: B → C, h: C → D be defined by Fig. 3-9. Determine if each function is:
(a) onto, (b) one-to-one, (c) invertible.

Fig. 3-9

(a) The function f : A → B is not onto since 3 ∈ B is not the image of any element in A.
The function g: B → C is not onto since z ∈ C is not the image of any element in B.
The function h: C → D is onto since each element in D is the image of some element of C.
(b) The function f : A → B is not one-to-one since a and c have the same image 2.
The function g: B → C is one-to-one since 1, 2 and 3 have distinct images.
The function h: C → D is not one-to-one since x and z have the same image 4.
(c) No function is one-to-one and onto; hence no function is invertible.
   
1 2 3 4 5 6 1 2 3 4 5 6
3.6. Consider permutations σ = and τ = in S6 .
3 6 4 5 1 2 2 4 6 5 3 1
Find: (a) composition τ ◦σ ; (b) σ −1 .

(a) Note that σ sends 1 into 3 and τ sends 3 into 6. So the composition τ ◦σ sends 1 into 6. I.e. (τ ◦σ )(1) = 6. Moreover,
τ ◦σ sends 2 into 6 into 1 that is, (τ ◦σ )(2) = 1, Similarly,

(τ ◦σ )(3) = 5, (τ ◦σ )(4) = 3, (τ ◦σ ) = 2, (τ ◦σ )(6) = 4

Thus  
1 2 3 4 5 6
τ ◦σ =
6 1 5 3 2 4

(b) Look for 1 in the second row of σ . Note σ sends 5 into 1. Hence σ −1 (1) = 5. Look for 2 in the second row of σ .
Note σ sends 6 into 2. Hence σ −1 (2) = 6. Similarly, σ −1 (3) = 1, σ −1 (4) = 3, σ −1 (5) = 4, σ −1 (6) = 2. Thus
 
1 2 3 4 5 6
σ −1 =
5 6 1 3 4 2
62 FUNCTIONS AND ALGORITHMS [CHAP. 3

3.7. Consider functions f : A → B and g: B → C. Prove the following:

(a) If f and g are one-to-one, then the composition function g◦f is one-to-one.
(b) If f and g are onto functions, then g◦f is an onto function.
(a) Suppose (g◦f )(x) = (g◦f )(y); then g(f (x)) = g(f (y)). Hence f (x) = f (y) because g is one-to-one. Further-
more, x = y since f is one-to-one. Accordingly g◦f is one-to-one.
(b) Let c be any arbitrary element of C. Since g is onto, there exists a b ∈ B such that g(b) = c. Since f is onto, there
exists an a ∈ A such that f (a) = b. But then
(g◦f )(a) = g(f (a)) = g(b) = c
Hence each c ∈ C is the image of some element a ∈ A. Accordingly, g◦f is an onto function.

3.8. Let f : R → R be defined by f (x) = 2x − 3. Now f is one-to-one and onto; hence f has an inverse function
f −1 . Find a formula for f −1 .
Let y be the image of x under the function f :
y = f (x) = 2x − 3
Consequently, x will be the image of y under the inverse function f −1 . Solve for x in terms of y in the above equation:
x = (y + 3)/2
Then f −1 (y) = (y + 3)/2. Replace y by x to obtain
x+3
f −1 (x) =
2
which is the formula for f −1 using the usual independent variable x.

3.9. Prove the following generalization of DeMorgan’s law: For any class of sets {Ai } we have
(∪i Ai )c = ∩i Aci
We have:
x ∈ (∪i Ai )c iff x ∈
/ ∪i Ai , iff ∀i ∈ I, x ∈ Ai , iff ∀i ∈ I, x ∈ Aci , iff x ∈ ∩i Aci
Therefore, (∪i Ai )c = ∩i Aci . (Here we have used the logical notations iff for “if and only” if and ∀ for “for all.”)

CARDINALITY
3.10. Find the cardinal number of each set:
(a) A = {a, b, c, . . . , y, z}, (c) C = {10, 20, 30, 40, . . .},
(b) B = {x | x ∈ N, x 2 = 5}, (d) D = {6, 7, 8, 9, . . .}.
(a) |A| = 26 since there are 26 letters in the English alphabet.
(b) |B| = 0 since there is no positive integer whose square is 5, that is, B is empty.
(c) |C| = ℵ0 because f : N → C, defined by f (n) = 10n , is a one-to-one correspondence between N and C.
(d) |D| = ℵ0 because g: N → D, defined by g(n) = n + 5 is a one-to-one correspondence between N and D.

3.11. Show that the set Z of integers has cardinality ℵ0 .

The following diagram shows a one-to-one correspondence between N and Z:
N= 1 2 3 4 5 6 7 8 ...
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ...
Z= 0 1 −1 2 −2 3 −3 4 ...
That is, the following function f : N → Z is one-to-one and onto:

n/2 if n is even
f (n) =
(1 − n)/2 if n is odd n/2
Accordingly, |Z| = |N| = ℵ0 .