Inverse: f −1(n) = log2(n).
5. The function f : R → R defined as f (x) = π x − e is bijective. Find its inverse.
x + e
Inverse: f −1(x) =
π .
7. Show that the function f : R2 → R2 defined by the formula f ((x, y) = ((x2 + 1)y, x3)
is bijective. Then find its inverse.
First we prove the function is injective.
Assume f (x1, y1) = f (x2, y2). Then
(x2
.
1 + 1) y1 = (x2
2 + 1) y2 and x3
1 = x3
2 Since the real-valued function f (x) = x3 is one-
to-one, it follows that x1 = x2. Since x1 = x2, and x21 + 1 > 0 we may divide both
sides of (x21 + 1)y1 = (x21 + 1)y2 by (x21 + 1) to get y1 = y2. Hence (x1, y1) = (x2, y2).
Now we prove the function is surjective. Let (a, b) ∈ R2. Set x = b1/3 and y =
a/(b2/3 + 1). Then f (x, y) = ((b2/3 + 1) a ,(b1/3)3) = (a, b).
b2/3
It now follows that f is
+1
bijective.
Finally, we compute the inverse. Write f (x, y) = (u, v). Interchange variables to
get (x, y) = f (u, v) = ((u2 + 1)v, u3). Thus x = (u2 + 1)v and y = u3. Hence u = y1/3 and
³
´
v =
x
.
y1/3,
x
.
y2/3
Therefore f −1(x, y) = (u, v) =
+1
y2/3+1
9. Consider the function f : R × N → N × R defined as f (x, y) = (y,3xy). Check that
this is bijective; find its inverse.
To see that this is injective, suppose f (a, b) = f (c, d). This means (b, 3ab) =
(d, 3cd). Since the first coordinates must be equal, we get b = d. As the second
coordinates are equal, we get 3ab = 3d c, which becomes 3ab = 3bc. Note that,
from the definition of f , b ∈ N, so b 6= 0. Thus we can divide both sides of
3ab = 3bc by the non-zero quantity 3b to get a = c. Now we have a = c and b = d,
so (a, b) = (c, d). It follows that f is injective.
Next we check that f is surjective. Given any (b, c) in the codomain N×R, notice
that ( c , b)
, b)
3b
belongs to the domain R × N, and f ( c
3b
= (b, c). Thus f is surjective.
As it is both injective and surjective, it is bijective; thus the inverse exists.
To find the inverse, recall that we obtained f ( c , b)
, b)
3b
= (b, c). Then f −1 f ( c
3b
=
f −1(b, c), which reduces to ( c , b)
3b
= f −1(b, c). Replacing b and c with x and y,
respectively, we get f −1(x, y) = ( y , x)
3x
.
295
Section 12.6 Exercises
1. Consider the function f : R → R defined as f (x) = x2 + 3. Find f ([−3,5]) and
f −1([12, 19]). Answers: f ([−3,5]) = [3,28]; f −1([12,19]) = [−4,−3] ∪ [3,4].
3. This problem concerns functions f : {1,2,3,4,5,6,7} → {0,1,2,3,4}. How many
¢
such functions have the property that | f −1({3})| = 3? Answer: 44 ¡ 73 .
5. Consider a function f : A → B and a subset X ⊆ A. We observed in Section 12.6
that f −1( f (X )) 6= X in general. However X ⊆ f −1( f (X )) is always true. Prove this.
Proof. Suppose a ∈ X . Thus f (a) ∈ {f (x) : x ∈ X } = f (X ), that is f (a) ∈ f (X ). Now,
by definition of preimage, we have f −1( f (X )) = {x ∈ A : f (x) ∈ f (X )}. Since a ∈ A
and f (a) ∈ f (X ), it follows that a ∈ f −1( f (X )). This proves X ⊆ f −1( f (X )).
■
7. Given a function f : A → B and subsets W, X ⊆ A, prove f (W ∩ X ) ⊆ f (W) ∩ f (X ).
Proof. Suppose b ∈ f (W ∩ X ). This means b ∈ {f (x) : x ∈ W ∩ X }, that is b = f (a)
for some a ∈ W ∩ X . Since a ∈ W we have b = f (a) ∈ { f (x) : x ∈ W} = f (W). Since
a ∈ X we have b = f (a) ∈ {f (x) : x ∈ X } = f (X ). Thus b is in both f (W) and f (X ), so
b ∈ f (W) ∩ f (X ). This completes the proof that f (W ∩ X ) ⊆ f (W) ∩ f (X ).
■
9. Given a function f : A → B and subsets W, X ⊆ A, prove f (W ∪ X ) = f (W) ∪ f (X ).
Proof. First we will show f (W ∪ X ) ⊆ f (W) ∪ f (X ). Suppose b ∈ f (W ∪ X ). This
means b ∈ { f (x) : x ∈ W ∪ X }, that is, b = f (a) for some a ∈ W ∪ X . Thus a ∈ W
or a ∈ X . If a ∈ W, then b = f (a) ∈ { f (x) : x ∈ W} = f (W). If a ∈ X , then b = f (a) ∈
{ f (x) : x ∈ X } = f (X ). Thus b is in f (W) or f (X ), so b ∈ f (W)∪ f (X ). This completes
the proof that f (W ∪ X ) ⊆ f (W) ∪ f (X ).
Next we will show f (W) ∪ f (X ) ⊆ f (W ∪ X ). Suppose b ∈ f (W) ∪ f (X ). This means
b ∈ f (W) or b ∈ f (X ). If b ∈ f (W), then b = f (a) for some a ∈ W. If b ∈ f (X ), then
b = f (a) for some a ∈ X . Either way, b = f (a) for some a that is in W or X . That
is, b = f (a) for some a ∈ W ∪ X . But this means b ∈ f (W ∪ X ). This completes the
proof that f (W) ∪ f (X ) ⊆ f (W ∪ X ).
The previous two paragraphs show f (W ∪ X ) = f (W) ∪ f (X ).
■
11. Given f : A → B and subsets Y , Z ⊆ B, prove f −1(Y ∪ Z) = f −1(Y ) ∪ f −1(Z).
Proof. First we will show f −1(Y ∪ Z) ⊆ f −1(Y ) ∪ f −1(Z). Suppose a ∈ f −1(Y ∪ Z).
By Definition 12.9, this means f (a) ∈ Y ∪ Z.
Thus, f (a) ∈ Y or f (a) ∈ Z.
If
f (a) ∈ Y , then a ∈ f −1(Y ), by Definition 12.9. Similarly, if f (a) ∈ Z, then a ∈
f −1(Z). Hence a ∈ f −1(Y ) or a ∈ f −1(Z), so a ∈ f −1(Y ) ∪ f −1(Z). Consequently
f −1(Y ∪ Z) ⊆ f −1(Y ) ∪ f −1(Z).
Next we show f −1(Y ) ∪ f −1(Z) ⊆ f −1(Y ∪ Z). Suppose a ∈ f −1(Y ) ∪ f −1(Z). This
means a ∈ f −1(Y ) or a ∈ f −1(Z). Hence, by Definition 12.9, f (a) ∈ Y or f (a) ∈ Z,
which means f (a) ∈ Y ∪Z. But by Definition 12.9, f (a) ∈ Y ∪Z means a ∈ f −1(Y ∪Z).
Consequently f −1(Y ) ∪ f −1(Z) ⊆ f −1(Y ∪ Z).
The previous two paragraphs show f −1(Y ∪ Z) = f −1(Y ) ∪ f −1(Z).
■
296
Solutions
13. Let f : A → B be a function, and X ⊆ A. Prove or disprove: f ¡f −1(f (X ))¢ = f (X ).
Proof. First we will show f ¡f −1(f (X ))¢ ⊆ f (X ). Suppose y ∈ f ¡f −1(f (X ))¢. By
definition of image, this means y = f (x) for some x ∈ f −1( f (X )). But by definition
of preimage, x ∈ f −1( f (X )) means f (x) ∈ f (X ). Thus we have y = f (x) ∈ f (X ), as
desired.
Next we show f (X ) ⊆ f ¡ f −1( f (X ))¢. Suppose y ∈ f (X ). This means y = f (x) for
some x ∈ X . Then f (x) = y ∈ f (X ), which means x ∈ f −1( f (X )). Then by definition
of image, f (x) ∈ f ( f −1( f (X ))). Now we have y = f (x) ∈ f ( f −1( f (X ))), as desired.
The previous two paragraphs show f ¡ f −1( f (X ))¢ = f (X ).
■
Chapter 13 Exercises
Section 13.1 Exercises
1. R and (0,∞)
Observe that the function f (x) = ex sends R to (0, ∞). It is injective because
f (x) = f (y) implies ex = ey, and taking ln of both sides gives x = y. It is surjective
because if b ∈ (0, ∞), then f (ln(b)) = b.
Therefor
e, because of the bijection
f : R → (0,∞), it follows that |R| = |(0,∞)|.
3. R and (0,1)
1
Observe that the function π f (x) = cot−1(x) sends R to (0,1). It is injective and
surjective by elementary trigonometry. Therefore, because of the bijection
f : R → (0,1), it follows that |R| = |(0,1)|.
5. A = {3k : k ∈ Z} and B = {7k : k ∈ Z}
Observe that the function f (x) = 7 x
3
sends A to B.
It is injective because
f (x) = f (y)
7
3
implies
x
y
3
= 73 , and multiplying both sides by 7 gives x = y. It is
surjective because if b ∈ B, then b = 7k for some integer k. Then 3k ∈ A, and
f (3k) = 7k = b. Therefore, because of the bijection f : A → B, it follows that
|A| = |B|.
7. Z and S = ©..., 1 , 1 , 1 ,1,2,4,8,16,...ª
8 4 2
Observe that the function f : Z → S defined as f (n) = 2n is bijective: It is injective
because f (m) = f (n) implies 2m = 2n, and taking log2 of both sides produces m = n.
It is surjective because any element b of S has form b = 2n for some integer n,
and therefore f (n) = 2n = b. Because of the bijection f : Z → S, it follows that
|Z| = |S|.
9. {0, 1} × N and N
Consider the function f : {0, 1}×N → N defined as f (a, n) = 2n − a. This is injective
because if f (a, n) = f (b, m), then 2n − a = 2m − b. Now if a were unequal to b, one
of a or b would be 0 and the other would be 1, and one side of 2n − a = 2m − b
would be odd and the other even, a contradiction. Therefore a = b. Then
2n − a = 2m − b becomes 2n − a = 2m − a; add a to both sides and divide by 2 to
get m = n. Thus we have a = b and m = n, so (a, n) = (b, m), so f is injective.
297
To see that f is surjective, take any b ∈ N. If b is even, then b = 2n for some
integer n, and f (0, n) = 2n − 0 = b. If b is odd, then b = 2n + 1 for some integer n.
Then f (1, n + 1) = 2(n + 1) − 1 = 2n + 1 = b. Therefore f is surjective. Then f is a
bijection, so |{0, 1} × N| = |N|.
11. [0, 1] and (0,1)
Proof. Consider the subset X = © 1 : n
n
∈ Nª ⊆ [0, 1]. Let f : [0,1] → [0,1) be defined
1
as f (x) = x if x ∈ [0, 1] − X and f ( 1 )
n =
1
n+1 for any n ∈ X . It is easy to check that
f is a bijection. Next let Y = ©1 − 1 : n
n
∈ Nª ⊆ [0, 1), and define g : [0,1) → (0,1) as
g(x) = x if x ∈ [0,1)−Y and g(1− 1 )
n = 1− 1
n+1 for any 1− 1
n ∈ Y . As in the case of f , it
is easy to check that g is a bijection. Therefore the composition g◦ f : [0, 1] → (0, 1)
is a bijection. (See Theorem 12.2.) We conclude that |[0, 1]| = |(0, 1)|.
■
13. P(N) and P(Z)
Outline: By Exercise 18 of Section 12.2, we have a bijection f : N → Z defined as
(−1)n(2n − 1) + 1
f (n) =
. Now define a function Φ : P(N) → P(Z) as Φ(X ) = { f (x) :
4
x ∈ X }. Check that Φ is a bijection.
15. Find a formula for the bijection f in Example 13.2.
Hint: Consider the function f from Exercise 18 of Section 12.2.
Section 13.2 Exercises
1. Prove that the set A = {ln(n) : n ∈ N} ⊆ R is countably infinite.
Just note that its elements can be written in infinite list form as ln(1), ln(2), ln(3), · · · .
Thus A is countably infinite.
3. Prove that the set A = {(5n,−3n) : n ∈ Z} is countably infinite.
Consider the function f : Z → A defined as f (n) = (5n, −3n).
This is clearly
surjective, and it is injective because f (n) = f (m) gives (5n, −3n) = (5m, −3m), so
5n = 5m, hence m = n. Thus, because f is surjective, |Z| = |A|, and |A| = |Z| = ℵ0.
Therefore A is countably infinite.
5. Prove or disprove: There exists a countably infinite subset of the set of irrational
numbers.
This is true.
Just consider the set consisting of the irrational numbers
π , π, π, π,
1 2 3 4 · · · .
7. Prove or disprove: The set Q100 is countably infinite.
This is true. Note Q100 = Q × Q × · · · × Q (100 times), and since Q is countably
infinite, it follows from the corollary of Theorem 13.5 that this product is
countably infinite.
9. Prove or disprove: The set {0,1} × N is countably infinite.
This is true. Note that {0, 1} × N can be written in infinite list form as
(0, 1), (1, 1), (0, 2), (1, 2), (0, 3), (1, 3), (0, 4), (1, 4), ···. Thus the set is countably infinite.
298
Solutions
11. Partition N into 8 countably infinite sets.
For each i ∈ {1, 2, 3, 4, 5, 6, 7, 8}, let X i be those natural numbers that are congruent
to i modulo 8, that is,
X1
=
{1, 9, 17, 25, 33, . . .}
X2
=
{2, 10, 18, 26, 34, . . .}
X3
=
{3, 11, 19, 27, 35, . . .}
X4
=
{4, 12, 20, 28, 36, . . .}
X5
=
{5, 13, 21, 29, 37, . . .}
X6
=
{6, 14, 22, 30, 38, . . .}
X7
=
{7, 15, 13, 31, 39, . . .}
X8
=
{8, 16, 24, 32, 40, . . .}
13. If A = {X ⊂ N : X is finite}, then |A| = ℵ0.
Proof. This is true. To show this we will describe how to arrange the items of
A in an infinite list X1, X2, X3, X4,....
For each natural number n, let pn be the nth prime number. Thus p1 = 2,
p2 = 3, p3 = 5, p4 = 7, p5 = 11, and so on. Now consider any element X ∈ A. If
X 6= ;, then X = {n1, n2, n3,..., nk}, where k = |X | and ni ∈ N for each 1 ≤ i ≤ k.
Define a function f : A → N ∪ {0} as follows: f ({n1, n2, n3, ..., nk}) = pn p
· · · p
1
n2
nk .
For example, f ({1, 2, 3}) = p1 p2 p3 = 2 · 3 · 5 = 30, and f ({3, 5}) = p3 p5 = 5 · 11 = 55, etc.
Also, we should not forget that ; ∈ A, and we define f (;) = 0.
Note that f : A → N ∪ {0} is an injection: Let X = {n1, n2, n3, ..., nk} and Y =
{m1, m2, m3, ..., m `}, and X 6= Y . Then there is an integer a that belongs to
one of X or Y but not the other. Then the prime factorization of one of the
numbers f (X ) and f (Y ) uses the prime number pa but the prime factorization
of the other does not use pa. It follows that f (X ) 6= f (Y ) by the fundamental
theorem of arithmetic. Thus f is injective.
So each set X ∈ A is associated with an integer f (X ) ≥ 0, and no two different
sets are associated with the same number. Thus we can list the elements in
X ∈ A in increasing order of the numbers f (X ). The list begins as
;, {1}, {2}, {3}, {1, 2}, {4}, {1, 3}, {5}, {6}, {1, 4}, {2, 3}, {7}, . . .
It follows that A is countably infinite.
■
15. Hint: Use the fundamental theorem of arithmetic.
Section 13.3 Exercises
1.
Suppose B is an uncountable set and A is a set. Given that there is a surjective
function f : A → B, what can be said about the cardinality of A?
299
The set A must be uncountable, as follows.
For each b ∈ B, let ab be an
element of A for which f (ab) = b. (Such an element must exist because f is
surjective.) Now form the set U = {ab : b ∈ B}. Then the function f : U → B is
bijective, by construction. Then since B is uncountable, so is U. Therefore U is
an uncountable subset of A, so A is uncountable by Theorem 13.9.
3. Prove or disprove: If A is uncountable, then |A| = |R|.
This is false. Let A = P(R). Then A is uncountable, and by Theorem 13.7,
|R| < |P(R)| = |A|.
5. Prove or disprove: The set {0,1} × R is uncountable.
This is true. To see why, first note that the function f : R → {0} × R defined as
f (x) = (0, x) is a bijection. Thus |R| = |{0} × R|, and since R is uncountable, so is
{0} × R. Then {0} × R is an uncountable subset of the set {0,1} × R, so {0,1} × R is
uncountable by Theorem 13.9.
7. Prove or disprove: If A ⊆ B and A is countably infinite and B is uncountable,
then B − A is uncountable.
This is true. To see why, suppose to the contrary that B − A is countably infinite.
Then B = A ∪ (B − A) is a union of countably infinite sets, and thus countable,
by Theorem 13.6. This contradicts the fact that B is uncountable.
Exercises for Section 13.4
1. Show that if A ⊆ B and there is an injection g : B → A, then |A| = |B|.
Just note that the map f : A → B defined as f (x) = x is an injection. Now apply
the Cantor-Bernstein-Schröeder theorem.
3. Let F be the set of all functions N → ©0,1}. Show that |R| = |F |.
Because |R| = |P(N)|, it suffices to show that |F | = |P(N)|. To do this, we will
exhibit a bijection f : F → P(N). Define f as follows. Given a function ϕ ∈ F ,
let f ( ϕ) = {n ∈ N : ϕ(n) = 1}. To see that f is injective, suppose f ( ϕ) = f ( θ). Then
{n ∈ N : ϕ(n) = 1} = {n ∈ N : θ(n) = 1}. Put X = {n ∈ N : ϕ(n) = 1}. Now we see that if
n ∈ X , then ϕ(n) = 1 = θ(n). And if n ∈ N − X , then ϕ(n) = 0 = θ(n). Consequently
ϕ(n) = θ(n) for any n ∈ N, so ϕ = θ. Thus f is injective. To see that f is surjective, take any X ∈ P(N). Consider the function ϕ ∈ F for which ϕ(n) = 1 if n ∈ X and
ϕ(n) = 0 if n ∉ X. Then f ( ϕ) = X, so f is surjective.
5. Consider the subset B = ©(x, y) : x2 + y2 ≤ 1ª ⊆ R2. Show that |B| = |R2|.
This will follow from the Cantor-Bernstein-Schröeder theorem provided that
Book of Proof Page 43