176 6 Functions

Proposition 6.1.11. Let f : R → R be defined by f (x) = (x − 1)2 and let g : R → R

be defined by g(x) = x2 − 2x + 1. Prove that f = g.
Proof. Let f : R → R and g : R → R be defined as stated in the proposition. Let
x ∈ R. We prove that f (x) = g(x) as follows:

f (x) = (x − 1)2 by the definition of f

= x2 − 2x + 1 by algebra
= g(x) by definition of g.

Therefore, f = g. 


Proposition 6.1.12. Let f : R → R and g : R → R be functions. Define s : R → R

and t : R → R by
s(x) = f (x) · g(x) for all x ∈ R (6.8)
t(x) = g(x) · f (x) for all x ∈ R. (6.9)
Then s = t.
Proof. Let f : R → R and g : R → R be functions and let s : R → R and t : R → R
be defined by (6.8) and (6.9). Let x be a real number. We shall prove that s(x) = t(x)
as follows:
s(x) = f (x) · g(x) by (6.8)

= g(x) · f (x) by the commutative law of multiplication

= t(x) by (6.9).
Therefore, s = t. 

Remark 6.1.13. Given functions f : A → B and g : A → B, to show that f = g you
must find at least one element x ∈ A and show that f (x) = g(x).

Exercises 6.1

1. Let f : Z → Z be defined by f (n) = 4n + 1. Determine the range of f .

2. Let f : R → R be defined by f (x) = −x2 + 4x. Determine the range of f .
−1 2
3. Consider the functions f : R+ → R and g : R+ → R defined by f (x) = 16x
4x+1
and g(x) = 4x − 1 for all x ∈ R+ . Prove that f = g.
4. Let f : R → R and g : R → R be functions. Define s : R → R and t : R → R by

s(x) = 2 f (x) + 3g(x) for all x ∈ R (6.10)

t(x) = 6 f (x) − g(x) for all x ∈ R. (6.11)

Prove that if s = t, then f = g.

6.2 One-to-One, Onto, and Inverse Functions 177

5. Consider the purported function f : Q → R defined by f ( mn ) = 2m 3n where

m, n ∈ Z and n = 0. Show that f is not well defined.
2
6. Consider the purported function f : Q → Q defined by f ( ij ) = i j+i
j2
whenever
i, j ∈ Z and j = 0. After reviewing Remark 6.1.6, prove that f is well-defined.
7. Consider the purported functions f : Q → Q and g : Q → Z defined by
i+ j
(a) f ( ij ) = j2
(b) g( ij ) = 6i − j
where i, j ∈ Z and j = 0. Are f and g functions? Provide a proof, or give a
counterexample, to verify your answers. (Review Remark 6.1.6.)
8. Consider the purported function g : N → N defined by g(n) = i if and only if
n = ik for some k ∈ N. Show that g is not a function.
9. Consider the purported function f : (0, 1) → {0, 1, 2, . . ., 9} defined by
f (x) = x3 where x = 0. x1 x2 x3 · · · is an infinite decimal expansion of x.
Show that f is not a function. Now read Remark 4.6.3 and then change the
definition of f , slightly, so that your new definition will produce a function.

6.2 One-to-One, Onto, and Inverse Functions

In this section, we will examine two of the most useful properties that a function
may have; namely, the property of being one-to-one and the property of being
onto. Roughly speaking, a function is one-to-one if it has no repeated values, and
a function is onto when every element in its co-domain is a value of the function.
We will present formal mathematical definitions and proof strategies that deal with
these important concepts. A function that is both one-to-one and onto will allow us
to construct a new function, called the inverse function.

6.2.1 One-to-One Functions

Some functions (see Fig. 6.3a, b) may have two inputs that are assigned to the
same output and thus, such functions have a repeated value. When a function never
produces a repeated value, then we will say that the function is one-to-one. For
example, it is easy to see that the function in Fig. 6.4 is one-to-one. Unfortunately,
the vast majority of mathematical functions cannot be represented by an arrow
diagram. Without an arrow diagram, it is more difficult to determine whether or
6.2 One-to-One, Onto, and Inverse Functions 183

Example 2. One can show that the function f : R → R given by f (x) = (x − 4)3 + 2
is one-to-one and onto. Find a formula for the inverse function f −1 .
√
Solution. After solving the
√ equation (x−4)3 +2 = y for x, we obtain x = 4+ 3 y − 2.
Therefore, f −1 (y) = 4 + 3 y − 2 is the formula for the inverse function. One can now
show that f (x) = y if and only if f −1 (y) = x, for all x, y ∈ R. 
Unfortunately, the above procedure for finding a formula for an inverse function
can fail. For example, consider the one-to-one and onto function f : R → R defined
by f (x) = x5 + x3 . It is impossible, using radicals, to algebraically solve the equation
x5 + x2 = y for x and thus, there is no elementary formula for f −1 .
Theorem 6.2.14. Suppose f : A → B is one-to-one and onto. Let f −1 : B → A be
the inverse of f . Then f −1 is also one-to-one and onto.
Proof. Let f : A → B be one-to-one and onto. We first prove that f −1 : B → A is
one-to-one. Let b, b ∈ B. Assume f −1 (b) = f −1 (b ). Let a ∈ A be this common
value. Thus, f −1 (b) = a and f −1 (b ) = a. So f (a) = b and f (a) = b , by (6.12).
Since f is a function, we conclude that b = b . Hence, f −1 is one-to-one.
To prove that f −1 : B → A is onto, let a ∈ A. So there is a b ∈ B be such that
f (a) = b. By (6.12), f −1 (b) = a. Therefore, f −1 is onto. 


Exercises 6.2

1. Define f : Z → Z by f (n) = 3n + 2.
(a) Is f one-to-one? Prove it, or provide a counterexample.
(b) Is f onto? Prove it, or provide a counterexample.
2. Define f : R → R by f (x) = x2 .
(a) Is f one-to-one? Prove it, or provide a counterexample.
(b) Is f onto? Prove it, or provide a counterexample.
3. Define a function f : N → N that is one-to-one but not onto.
4. Define a function f : N → N that is onto but not one-to-one.
5. Let A = {x ∈ R : x = −1}. Define f : A → R by f (x) = x+1 2x
. Prove that f is
one-to-one.
6. Let A = {x ∈ R : x = 1}. Define f : A → R by f (x) = 2x−2 3x
. Prove f is not onto.
7. Define f : R → R by f (x) = x − x . Is f one-to-one? Is it onto?
3

8. Let A = {x ∈ R : x = 2} and let B = {y ∈ R : y = 4}. Define f : A → B by

f (x) = x−2
4x
. Prove that f is onto.
9. Let A = {x ∈ R : x = 2} and let B = {y ∈ R : y = 4}. Prove the function f : A → B
defined by f (x) = x−2
4x
is one-to-one.
10. Let a, b ∈ R with a = 0 and define the function f : R → R by f (x) = ax + b.
Given that f is one-to-one and onto, find a formula for f −1 : R → R.
184 6 Functions

11. Prove that the function f : R → R, defined below, is one-to-one and onto.

x2 , if x ≥ 0;
f (x) = (6.13)
−x2 , if x < 0.

12. Let f : R → R be the function defined by (6.13) in Exercise 11. Given that f is
one-to-one and onto, find a formula for the inverse function f −1 : R → R.
13. Suppose that f : R → R+ is one-to-one. Define g : R → R+ by g(x) = ( f (x))2 .
Prove that g is one-to-one.
14. Suppose that f : R → R+ is onto. Define g : R → R+ by g(x) = ( f (x))2 . Prove
that g is onto.
15. Suppose f : R → R is one-to-one and let a, b ∈ R where a = 0. Define g : R → R
by g(x) = a f (x) + b. Prove that g is one-to-one.
16. Suppose f : R → R is onto and let a, b ∈ R where a = 0. Define g : R → R by
g(x) = a f (x) + b. Prove that g is onto.
17. Define f : N × N → N by f (m, n) = 2m 3n . Prove that f is one-to-one.
18. Let f : R → R be as in Example 2. Prove that f is one-to-one and onto.

Exercise Notes: For Exercise 11, if x2 = y2 then |x| = |y|. For Exercise 17, let
m, n, i, j ∈ N. Assume f (m, n) = f (i, j). Prove m = i and n = j.

6.3 Composition of Functions

If the domain of a function equals the co-domain of another function, then we can
use these two functions to construct a new function called the composite function.
The composite function is defined by taking the output of one these functions and
using that as the input for the other function. The formal mathematical definition
appears below.
Definition 6.3.1. For functions g : A → B and f : B → C, one forms the composite
function ( f ◦ g) : A → C by defining ( f ◦ g)(x) = f (g(x)) for all x ∈ A.
For example, let g : A → B and f : B → C be the functions in Fig. 6.7. An arrow
diagram for the composite function ( f ◦ g) : A → C appears in Fig. 6.8.
Example 1. Let g : R → R and f : R → R be the functions defined by f (x) = x21+2
and g(x) = 2x − 1. Find formulas for ( f ◦ g)(x) and (g ◦ f )(x). Is f ◦ g = g ◦ f ?
Solution. Let x ∈ R. We evaluate the function ( f ◦ g)(x) as follows:

1
( f ◦ g)(x) = f (g(x)) = f (2x − 1) = .
(2x − 1)2 + 2
188 6 Functions

( f ◦ g)(x) = f (g(x)) by definition of composition

= f (y) because g(x) = y

=z because f (y) = z. 


Exercises 6.3

1. Let f : R → R be defined by f (x) = x2 − 1 and let g : R → R be defined by

g(x) = x3 + 1. Evaluate the values:
(a) ( f ◦ g)(1)
(b) (g ◦ f )(1)
(c) ( f ◦ f )(1)
(d) (g ◦ g)(1).
2. Let f : R → R be defined by f (x) = x2 − 1 and let g : R → R be defined by
g(x) = x3 + 1. Obtain formulas for the following compositions:
(a) ( f ◦ g)(x)
(b) (g ◦ f )(x)
(c) ( f ◦ f )(x)
(d) (g ◦ g)(x).
3. Let f : A → B and g : B → A be functions. Suppose that f (g(b)) = b for all
b ∈ B and g( f (a)) = a for all a ∈ A. Prove that f and g are one-to-one and onto.
4. For a, b ∈ R with a = 0, define the function Ta,b : R → R by Ta,b (x) = ax+ b. Let
G be the set of all such functions, that is, let G = {Ta,b : a, b ∈ R and a = 0}.
(a) Let Ta,b ∈ G and Tc,d ∈ G. Show that Ta,b ◦ Tc,d = Tac,ad+b .
(b) Let Ta,b ∈ G and Tc,d ∈ G. Show that (Ta,b ◦ Tc,d ) ∈ G.
(c) Let Ta,b ∈ G. Prove that Ta,b is one-to-one and onto.
(d) Let I : R → R be the identity function. Show that I ∈ G.
−1 −1
(e) Let Ta,b ∈ G. Show that Ta,b = T 1 ,− b and thus, Ta,b ∈ G.
a a
(f) Find a Ta,b ∈ G and Tc,d ∈ G so that (Ta,b ◦ Tc,d ) = (Tc,d ◦ Ta,b ).
5. Given a ∈ Q with a = 0 and b ∈ R, define Ta,b : R → R by Ta,b (x) = ax + b. Let
H = {Ta,b : a ∈ Q, b ∈ R and a = 0}.
(a) For any Ta,b ∈ H and Tc,d ∈ H, show that (Ta,b ◦ Tc,d ) ∈ H.
(b) Let I : R → R be the identity function. Show that I ∈ H.
−1
(c) Let Ta,b ∈ H. Show that Ta,b ∈ H.
6. Let g : A → B and f : B → C. Suppose that ( f ◦ g) : A → C is one-to-one. Prove
that g is one-to-one.
7. Let g : A → B and f : B → C. Suppose that ( f ◦ g) : A → C is one-to-one and g
is onto. Prove that f is one-to-one.
6.4 Functions Acting on Sets 189

8. Let f : B → C and g : A → B. Suppose that ( f ◦ g) : A → C is onto. Prove that f

is onto.
9. Let g : A → B and f : B → C. Suppose that ( f ◦ g) : A → C is onto and f is
one-to-one. Prove that g is onto.
10. Let h : A → B, g : B → C and f : C → D. Prove that ( f ◦ g) ◦ h = f ◦ (g ◦ h).
Exercise Notes: For Exercise 4(a), find a formula for Ta,b (Tc,d (x)). For Exercise 4(e),
−1
find a formula for Ta,b .

6.4 Functions Acting on Sets

There are times when we are more interested in what a function does to an entire
subset of its domain, rather than how it affects an individual element in the domain.
Understanding this behavior on sets can allow one to better understand the function
itself and can reveal some properties concerning its domain and range. The concept
of a function “acting on a set,” is one that appears in every branch of mathematics.
Definition 6.4.1 (Image of a Set). Let f : X → Y be a function. Let S ⊆ X. The set
f [S], called the image of S, is defined by

f [S] = { f (x) : x ∈ S} = {y ∈ Y : y = f (x) for some x ∈ S}.

Figure 6.9 illustrates Definition 6.4.1. The square S represents a subset of the
domain of the function f . The image f [S], represented by the rectangle, is the set of
all values of the function that are obtained from the inputs that are in the set S.
Example 1. Let f : R → R be defined by f (x) = |x| and S = {−12, −3, 2, 3}. Then
the image of S is f [S] = { f (x) : x ∈ S} = {|x| : x ∈ S} = {2, 3, 12}. Observe that
f (12) ∈ f [S] and yet 12 ∈
/ S.
Example 2. Let f : R → R be defined by f (x) = x2 and S = {−4, −3, 2, 3}. Then
the image of S is f [S] = { f (x) : x ∈ S} = {x2 : x ∈ S} = {16, 9, 4}. Let U be the
interval [−2, 3]. Then f [U] = { f (x) : x ∈ U} = {x2 : −2 ≤ x ≤ 3} = [0, 9].

f:X→Y
x

S y

f [S]

X Y

Fig. 6.9 Starting with S ⊆ X we can construct the image f [S] ⊆ Y

192 6 Functions

Therefore, f −1 [U] ∪ f −1 [V ] ⊆ f −1 [U ∪V ]. This completes the proof of (d). 


Theorem 6.4.6. Let f : X → Y be a function. Let C, D be subsets of X. If f is one-
to-one, then f [C ∩ D] = f [C] ∩ f [D].
Proof. Let f : X → Y be a function. Let C, D be subsets of X and assume that f is
one-to-one. We shall prove that f [C ∩ D] = f [C] ∩ f [D]. Theorem 6.4.5(a) implies
that f [C ∩D] ⊆ f [C]∩ f [D]. To show that f [C]∩ f [D] ⊆ f [C ∩D], let y ∈ f [C]∩ f [D].
We will prove that y ∈ f [C ∩ D]. Since y ∈ f [C] ∩ f [D], we see that y ∈ f [C] and
y ∈ f [D]. Because y ∈ f [C], there is a c ∈ C such that f (c) = y. Also, since y ∈ f [D],
there is a d ∈ D such that f (d) = y. Hence, y = f (c) = f (d). Since f is one-to-one,
we have c = d. Thus, c ∈ D. So c ∈ C ∩ D and therefore, y = f (c) ∈ f [C ∩ D]. We
conclude that f [C ∩ D] = f [C] ∩ f [D]. 


Exercises 6.4

1. Using Definitions 6.4.1 and 6.4.2, explain why items 1–4 of Remark 6.4.3 hold.
2. Prove Theorem 6.4.4.
3. Prove item (b) of Theorem 6.4.5.
4. Prove item (c) of Theorem 6.4.5.
5. Given a, b ∈ R with a > 0, define the function f : R → R by f (x) = ax + b. Let
U = [2, 3]. Using interval notation, evaluate f [U] and f −1 [U].
6. Define the function f : R → R by f (x) = x2 and let U = [−1, 4]. Show the
following:
(a) f [ f −1 [U]] = U.
(b) f −1 [ f [U]] = U.
(c) f [ f −1 [U]] = f −1 [ f [U]].
7. Let f : X → Y be a function and let A ⊆ X and B ⊆ X. Prove that if A ⊆ B, then
f [A] ⊆ f [B].
8. Let f : R → R be the function defined in Example 1 on page 189. Find A ⊆ R
and B ⊆ R such that f [A] ⊆ f [B] and A ⊆ B.
9. Suppose f : X → Y is a one-to-one function. Let A ⊆ X and B ⊆ X. Prove that
if f [A] ⊆ f [B], then A ⊆ B.
10. Let f : X → Y be a function and let C ⊆ Y and D ⊆ Y . Prove that if C ⊆ D, then
f −1 [C] ⊆ f −1 [D].
11. Let f : R → R be the function defined in Example 3. Find C ⊆ R and D ⊆ R
such that f −1 [C] ⊆ f −1 [D] and C ⊆ D.
12. Suppose f : X → Y is onto and let C ⊆ Y and D ⊆ Y . Prove if f −1 [C] ⊆ f −1 [D],
then C ⊆ D.
13. Let f : X → Y be a function. Let A be a subset of X. Prove that A ⊆ f −1 [ f [A]].
6.5 On the Size of Infinite Sets 193

14. Suppose f : X → Y is one-to-one. Let A ⊆ X and x ∈ X. Prove if f (x) ∈ f [A],

then x ∈ A.
15. Suppose that f : X → Y is one-to-one. Let A ⊆ X. Prove that A = f −1 [ f [A]].
16. Let f : X → Y . Suppose A = f −1 [ f [A]] for all finite subsets A of X. Prove f is
one-to-one.
17. Let f : X → Y be a function. Let C be a subset of Y . Prove that f [ f −1 [C]] ⊆ C.
18. Assume that f : X → Y is an onto function. Let C ⊆ Y . Prove that f [ f −1 [C]] = C.
19. Given a, b ∈ R with a > 0, define the function f : R → R by f (x) = ax + b.
Using Exercises 15 and 18, prove that f [ f −1 [U]] = f −1 [ f [U]] for every U ⊆ R.
20. Let f : X → Y be a function. Let{Ci : i∈ I} be an indexed family of sets where
 
Ci ⊆ X for all i ∈ I. Prove that f Ci = f [Ci ].
i∈I i∈I

Exercise Notes: Exercise 8 shows that the converse of Exercise 7 is not necessarily
true for all functions. Exercise 9, however, shows that this converse is true for all
one-to-one functions (review assumption strategy 6.2.4 on page 179). Similarly,
Exercise 11 shows that the converse of Exercise 10 is not true for all functions; but,
Exercise 12 shows that this converse is true for all functions that are onto (review
Assumption Strategy 6.2.10 on page 181).

6.5 On the Size of Infinite Sets

The size of a finite set can easily be measured; for example, the size of the set
A = {1, 2, 3, . . ., 50} is 50 because it has 50 elements, and the size of the sets
B = {π , 2, 30, −2} and C = {9, 11, −1, 5} is 4. Clearly, the size of A is bigger than
the size of B. In addition, the sets B and C have the same size. Can the idea of “size”
be extended to infinite sets? Georg Cantor was the first mathematician to seriously
address and answer this question. Cantor found a way to measure the size of any
infinite set. He first observed that two sets A and B have the same size if there is
a one-to-one correspondence between A and B; that is, there is a way of evenly
matching the elements in A with the elements in B. In other words, Cantor observed
that A and B have the same size, if there is a one-to-one and onto function f : A → B.
For example, the arrow diagram in Fig. 6.11 presents a function that is one-to-one
and onto. As a result, we can use this function to construct the following one-to-one
correspondence (6.14) between the sets A and B:

A:ab c d e
 (6.14)
B:351 2 4
6.5 On the Size of Infinite Sets 205

(1;1)
1

(x; y)

S
I

z
0 1 0 1

Fig. 6.12 The unit square and the unit interval

and let y = 0.y1 y2 y3 . . . be infinite decimal expansions of x and y, where 0 ≤ xi ≤ 9

and 0 ≤ yi ≤ 9 for each i ∈ N. To eliminate any duplicate representations, we insist
that whenever x has two decimal representations, one ending with a string 0’s and
the other ending with a string of 9’s, we will choose the one ending with a string
0’s (see Remark 4.6.3 on page 130). Similarly, we will not use a decimal expansion
for y that ends in a string of 9’s. Define g(x, y) = 0. x1 y1 x2 y2 x3 y3 · · · . One can show
that g is one-to-one (see Exercise 3). Thus, |S| ≤ |I|. Theorem 6.5.31 now implies
that |S| = |I|. 


Exercises 6.5

1. Let A = {4, 8, 12, 16, . . .} and let B = {n ∈ Z : n < −25}.

(a) Define a one-to-one and onto function f : A → N.
(b) Define a one-to-one and onto function g : B → N.
2. Let A and B be as in Exercise 1. Define a one-to-one function h : A ∪ B → N.
3. Prove that the function g : S → I defined in the proof of Theorem 6.5.32 is one-
to-one.
4. Suppose that the set B is finite and A ⊆ B. Prove that A is finite.
5. Suppose that A and B are finite sets. Prove that A ∪ B is finite.
6. Suppose that A and B are finite sets. Prove that A × B is finite.
7. Let X, f and n be as in Definition 6.5.2. Prove that the function f is onto.
8. Using Definition 6.5.2, prove Theorem 6.5.3. (For the direction (⇐) use
Exercise 7.)
9. Using Definition 6.5.2, Exercise 7 and mathematical induction, prove that
|{1, 2, . . . , n}| = n for all natural numbers n.
10. Prove that for all n ∈ N there is no one-to-one function f : N → {1, 2, 3, . . . , n}.
Conclude that if g : N → A is one-to-one, then A is infinite.
206 6 Functions

11. Let A = {x ∈ R : 0 < x < 1} and B = {x ∈ R : 2 < x < 5}. Prove that |A| = |B|.
12. Prove that N × N is countable.
13. Let A and B be countable sets. Prove that A × B is countable.
14. Let A be uncountable. Prove that A × B is uncountable for any nonempty set B.
15. Prove that there exists a function f : N → N × N that is one-to-one and onto.
16. Let A be a set. Suppose that f : N → A is onto. Prove that A is countable.
17. Let A and B be sets. Suppose A is uncountable and B is countable. Prove that
A \ B is uncountable.
18. Prove that the set of irrational numbers is uncountable; that is, prove that R \ Q
is uncountable.
19. Let F be as in Theorem 6.5.21. Let () f1 , f2 , . . . , fn be a finite list of functions
in F . Using the argument in the proof of Theorem 6.5.21, define a new function
g ∈ F that is not in the list (). Therefore, F is infinite.
20. Let S = {a1 , a2 , . . . , ak  : a1 , a2 , . . . , ak ∈ N for some k ∈ N}, the set of all finite
sequences of elements from N. Prove that S is countable.
21. Let A and B be countably infinite sets. Prove that |A| = |B|.
22. Let A and B be sets. Prove that if |A| = |B|, then |B| = |A|.
23. Let A, B and C be sets. Prove that if |A| = |B| and |B| = |C|, then |A| = |C|.
24. Let A, B and C be sets. Prove that if |A| < |B| and |B| = |C|, then |A| < |C|.
25. Let A and B be sets. Suppose B is countable. Prove that if |A| ≤ |B|, then A is
also countable.
26. Let A, B and C be sets. Prove that if |A| < |B| and |B| < |C|, then |A| < |C|.
27. Prove that the set P(N) is uncountable.
28. Suppose someone asserts that the set of real numbers in the interval (0, 1) is
countable and that all of these real numbers can be enumerated as in (6.24),
where each such real number is represented by an infinite decimal expansion:

x1 = . 12345689234 · · ·
x2 = . 68729958219 · · ·
x3 = . 05050506620 · · ·
x4 = . 57591884622 · · · (6.24)
..
.
xi = . xi1 xi2 xi3 xi4 xi5 · · ·
..
.

You are to show that this assertion is false. Using Cantor’s diagonal argument,
define a decimal expansion for a real number b in (0, 1) that is not in the
list (6.24). Ensure that your decimal expansion b = .b1 b2 b3 . . . bi . . . contains
6.5 On the Size of Infinite Sets 207

neither of the digits 0 or 9.6 Then identify the first 4 decimal digits in the
decimal expansion of b and prove b = xn for all n ∈ N.
29. Let S = {q ∈ Q : 0 < q < 1}. Theorems 6.5.10 and 6.5.14 imply S is countable.
We can thus enumerate all of the elements in S in a list () q1 , q2 , q3 , . . . , by
Theorem 6.5.17. Since each of these rational numbers has an infinite decimal
expansion qi = .qi1 qi2 qi3 qi4 qi5 · · · , one can define a real number b ∈ (0, 1) that
is not in the list (), just as in Exercise 28. Is b a rational number? Justify your
answer.
30. Let A = {a, b, c, d, w, y, z} and let g : A → P(A) be the function given by

g(a) = {b, c, g}
g(b) = {a, b, c, w, z}
g(c) = {b, c}
g(d) = {d}
g(w) = A
g(y) = {a, b, c, d, w}
g(z) = ∅.

The function g is one-to-one. The proof of Theorem 6.5.29 shows that g is not
onto because the subset of A defined by X = {x ∈ A : x ∈ / g(x)} is not in the
range of g. Evaluate the set X.
Exercise Notes: For Exercise 3, use Exercise 2 on page 136. For Exercise 7, assume
that f is not onto. Let 1 ≤ i ≤ n be the largest such that i ∈ / ran( f ). If i = n then
get a contradiction. If i < n, let a ∈ X be such that f (a) = n. Define a one-to-one
function g : X → {1, 2, . . . , n − 1}. For Exercise 9, in the inductive step suppose that
|{1, 2, . . ., n, n + 1}| = k < n + 1. Let f : {1, 2, . . . , n, n + 1} → {1, 2, . . . , k} be one-
to-one and onto. Let 1 ≤ j ≤ k be such that f (n + 1) = j and let 1 ≤  ≤ n be such
that f () = k. Define a one-to-one function g : {1, 2, . . . , n} → {1, 2, . . ., k − 1}. For
Exercise 10, suppose that n ∈ N is the least such that there is a one-to-one function
f : N → {1, 2, . . . , n}. Show that 1 < n and show that f is onto. Let i ∈ N be such that
f (n) = i. Then h : N → N\ {i} defined by h(k) = i+ k is one-to-one. Define a one-to-
one function g : N → {1, 2, . . ., n − 1}. For Exercise 16, let Ia = {n ∈ N : f (n) = a}
for each a ∈ A. Since f is onto, each Ia is nonempty and has a least element. For
Exercise 20, define h : S → N by h(a1 , a2 , . . . , am ) = 2a1 · 3a2 · 5a3 · · · pamm where pm
is the m-th prime. For Exercise 28, review the proof of Theorem 6.5.21 and note that
the diagonal digit xii is in the i-th decimal place for each xi in (6.24); for example,
x22 = 8 and x44 = 9.

6 Sob will have a unique decimal representation. Thus, if the decimal expansions of b, x ∈ (0, 1)
have different digits in at least one decimal place, then b = x. See Remark 4.6.3 on page 130.