sense that f −1( f (x)) = x for every x in the domain. (For example, if f (x) = x3,
p
then f −1(x) = 3 x.) We now review these ideas. Our approach uses two
ingredients, outlined in the following definitions.
Definition 12.6
Given a set A, the identity function on A is the func-
tion i A : A → A defined as i A(x) = x for every x ∈ A.
Example: If A = ©1, 2, 3ª, then i A = ©(1, 1), (2, 2), (3, 3)ª. Also iZ = ©(n, n) : n ∈ Zª.
The identity function on a set is the function that sends any element of
the set to itself.
Notice that for any set A, the identity function i A is bijective: It is
injective because i A(x) = i A( y) immediately reduces to x = y. It is surjective
because if we take any element b in the codomain A, then b is also in the
domain A, and i A(b) = b.
Definition 12.7
Given a relation R from A to B, the inverse relation
of R is the relation from B to A defined as R−1 = ©(y, x) : (x, y) ∈ Rª. In other
words, the inverse of R is the relation R−1 obtained by interchanging the
elements in every ordered pair in R.
For example, let A = ©a, b, cª and B = ©1, 2, 3ª, and suppose f is the
relation f = ©(a, 2), (b, 3), (c, 1)ª from A to B. Then f −1 = ©(2, a), (3, b), (1, c)ª
and this is a relation from B to A. Notice that f is actually a function
from A to B, and f −1 is a function from B to A. These two relations are
drawn below. Notice the drawing for relation f −1 is just the drawing for f
with arrows reversed.
A
B
A
B
a
1
a
1
b
2
b
2
c
3
c
3
f = ©(a,2),(b,3),(c,1)ª
f −1 = ©(2, a),(3, b),(1, c)ª
For another example, let A and B be the same sets as above, but consider
the relation g = ©(a, 2), (b, 3), (c, 3)ª from A to B. Then g−1 = ©(2, a), (3, b), (3, c)ª
is a relation from B to A. These two relations are sketched below.
212
Functions
A
B
A
B
a
1
a
1
b
2
b
2
c
3
c
3
g = ©(a,2),(b,3),(c,3)ª
g−1 = ©(2, a),(3, b),(3, c)ª
This time, even though the relation g is a function, its inverse g−1 is
not a function because the element 3 occurs twice as a first coordinate of
an ordered pair in g−1.
In the above examples, relations f and g are both functions, and f −1 is
a function and g−1 is not. This raises a question: What properties does f
have and g lack that makes f −1 a function and g−1 not a function? The
answer is not hard to see. Function g is not injective because g(b) = g(c) = 3,
and thus (b, 3) and (c, 3) are both in g. This causes a problem with g−1
because it means (3, b) and (3, c) are both in g−1, so g−1 can’t be a function.
Thus, in order for g−1 to be a function, it would be necessary that g be
injective.
But that is not enough. Function g also fails to be surjective because
no element of A is sent to the element 1 ∈ B. This means g−1 contains no
ordered pair whose first coordinate is 1, so it can’t be a function from B to
A. If g−1 were to be a function it would be necessary that g be surjective.
The previous two paragraphs suggest that if g is a function, then it
must be bijective in order for its inverse relation g−1 to be a function.
Indeed, this is easy to verify. Conversely, if a function is bijective, then its
inverse relation is easily seen to be a function. We summarize this in the
following theorem.
Theorem 12.3
Let f : A → B be a function. Then f is bijective if and only
if the inverse relation f −1 is a function from B to A.
Suppose f : A → B is bijective, so according to the theorem f −1 is a
function. Observe that the relation f contains all the pairs (x, f (x)) for x ∈ A,
so f −1 contains all the pairs ( f (x), x). But ( f (x), x) ∈ f −1 means f −1( f (x)) = x.
Therefore f −1 ◦ f (x) = x for every x ∈ A. From this we get f −1 ◦ f = i A. Similar
reasoning produces f ◦ f −1 = iB. This leads to the following definitions.
Definition 12.8
If f : A → B is bijective then its inverse is the function
f −1 : B → A. Functions f and f −1 obey the equations f −1 ◦ f = i A and
f ◦ f −1 = iB.
Inverse Functions
213
You probably recall from algebra and calculus at least one technique
for computing the inverse of a bijective function f : to find f −1, start with
the equation y = f (x). Then interchange variables to get x = f ( y). Solving
this equation for y (if possible) produces y = f −1(x). The next two examples
illustrate this.
Example 12.12
The function f : R → R defined as f (x) = x3 + 1 is bijective.
Find its inverse.
We begin by writing y = x3 + 1. Now interchange variables to obtain
p
x = y3 + 1. Solving for y produces y = 3 x − 1. Thus
p
f −1(x)
3
=
x − 1.
(You can check your answer by computing
3
p
f −1( f (x)) = 3pf (x) − 1 =
x3 + 1 − 1 = x.
Therefore f −1( f (x)) = x. Any answer other than x indicates a mistake.)
We close with one final example. Example 12.5 showed that the function
g : Z × Z → Z × Z defined by the formula g(m, n) = (m + n, m + 2n) is bijective.
Let’s find its inverse. The approach outlined above should work, but we
need to be careful to keep track of coordinates in Z × Z. We begin by
writing (x, y) = g(m, n), then interchanging the variables (x, y) and (m, n) to
get (m, n) = g(x, y). This gives
(m, n) = (x + y, x + 2y),
from which we get the following system of equations:
x
+
y
= m
x
+ 2y = n.
Solving this system using techniques from algebra with which you are
familiar, we get
x
= 2m − n
y
=
n − m.
Then (x, y) = (2m − n, n − m), so g−1(m, n) = (2m − n, n − m).
214
Functions
We can check our work by confirming that g−1(g(m, n)) = (m, n). Doing
the math,
g−1(g(m, n))
=
g−1(m + n, m + 2n)
= ¡2(m + n) − (m + 2n), (m + 2n) − (m + n)¢
= (m, n).
Exercises for Section 12.5
1. Check that the function f : Z → Z defined by f (n) = 6 − n is bijective. Then
compute f −1.
2. In Exercise 9 of Section 12.2 you proved that f : R − ©2ª → R − ©5ª defined by
5x + 1
f (x) =
is bijective. Now find its inverse.
x − 2
3. Let B = ©2n : n ∈ Zª = ©..., 1 , 1 ,1,2,4,8,...ª
4 2
.
Show that the function f : Z → B
defined as f (n) = 2n is bijective. Then find f −1.
4. The function f : R → (0,∞) defined as f (x) = ex3+1 is bijective. Find its inverse.
5. The function f : R → R defined as f (x) = π x − e is bijective. Find its inverse.
6. The function f : Z × Z → Z × Z defined by the formula f (m, n) = (5m + 4n,4m + 3n)
is bijective. Find its inverse.
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.
8. Is the function θ : P(Z) → P(Z) defined as θ(X ) = X bijective? If so, what is its
inverse?
9. Consider the function f : R × N → N × R defined as f (x, y) = (y,3xy). Check that
this is bijective; find its inverse.
(−1)n(2n − 1) + 1
10. Consider f : N → Z defined as f (n) =
. This function is bijective
4
by Exercise 18 in Section 12.2. Find its inverse.
12.6 Image and Preimage
It is time to take up a matter of notation that you will encounter in future
mathematics classes. Suppose we have a function f : A → B. If X ⊆ A, the
©
expression f (X ) has a special meaning. It stands for the set
f (x) : x ∈ X ª.
Similarly, if Y ⊆ B then f −1(Y ) has a meaning even if f is not invertible.
©
The expression f −1(Y ) stands for the set
x ∈ A : f (x) ∈ Y ª. Here are the
precise definitions.
Image and Preimage
215
Definition 12.9
Suppose f : A → B is a function.
1. If X ⊆ A, the image of X is the set f (X ) = © f (x) : x ∈ X ª ⊆ B.
2. If Y ⊆ B, the preimage of Y is the set f −1(Y ) = ©x ∈ A : f (x) ∈ Y ª ⊆ A.
In words, the image f (X ) of X is the set of all things in B that f sends
elements of X to. (Roughly speaking, you might think of f (X ) as a kind of
distorted “copy” or “image” of X in B.) The preimage f −1(Y ) of Y is the set
of all things in A that f sends into Y .
Maybe you have already encountered these ideas in linear algebra, in
a setting involving a linear transformation T : V → W between two vector
spaces. If X ⊆ V is a subspace of V , then its image T(X ) is a subspace of W.
If Y ⊆ W is a subspace of W, then its preimage T−1(Y ) is a subspace of V .
(If this does not sound familiar, then ignore it.)
Example 12.13
Let f : ©s, t, u, v, w, x, y, zª → ©0, 1, 2, 3, 4, 5, 6, 7, 8, 9ª, where
f = ©(s,4),(t,8),(u,8),(v,1),(w,2),(x,4),(y,6),(z,4)ª.
Notice that f is neither injective nor surjective, so it certainly is not
invertible. Be sure you understand the following statements.
1. f ¡©s, t, u, zª¢ = ©8, 4ª
2. f ¡©s, x, zª¢ = ©4ª
3. f ¡©s, v, w, yª¢ = ©1, 2, 4, 6ª
4. f −1¡©4ª¢ = ©s, x, zª
5. f −1¡©4, 9ª¢ = ©s, x, zª
6. f −1¡©9ª¢ = ;
7. f −1¡©1, 4, 8ª¢ = ©s, t, u, v, x, zª
It is important to realize that the X and Y in Definition 12.9 are
subsets (not elements!) of A and B. Note that in the above example we
had f −1¡©4ª¢ = ©s, x, zª, while f −1(4) has absolutely no meaning because the
inverse function f −1 does not exist. Likewise, there is a subtle difference
between f ¡©sª¢ = ©4ª and f (s) = 4. Be careful.
Example 12.14
Consider the function f : R → R defined as f (x) = x2.
Note that f ¡©0, 1, 2ª¢ = ©0, 1, 4ª and f −1¡©0, 1, 4ª¢ = © − 2, −1, 0, 1, 2ª. This shows
f −1( f (X )) 6= X in general.
Using the same f , now check your understanding of the following
statements involving images and preimages of intervals: f ([−2, 3]) = [0, 9],
and f −1([0, 9]) = [−3, 3]. Also f (R) = [0, ∞) and f −1([−2, −1]) = ;.
216
Functions
If you continue with mathematics you are likely to encounter the
following results. For now, you are asked to prove them in the exercises.
Theorem 12.4
Suppose f : A → B is a function. Let W, X ⊆ A, and Y , Z ⊆ B.
Then:
1. f (W ∩ X ) ⊆ f (W) ∩ f (X )
2. f (W ∪ X ) = f (W) ∪ f (X )
3. f −1(Y ∩ Z) = f −1(Y ) ∩ f −1(Z)
4. f −1(Y ∪ Z) = f −1(Y ) ∪ f −1(Z)
5. X ⊆ f −1( f (X ))
6. f ( f −1(Y )) ⊆ Y .
Exercises for Section 12.6
1. Consider the function f : R → R defined as f (x) = x2 + 3. Find f ([−3,5]) and
f −1([12, 19]).
2. Consider the function f : ©1,2,3,4,5,6,7ª → ©0,1,2,3,4,5,6,7,8,9ª given as
f = ©(1,3),(2,8),(3,3),(4,1),(5,2),(6,4),(7,6)ª.
Find: f ¡©1, 2, 3ª¢, f ¡©4, 5, 6, 7ª¢, f (;), f −1¡©0, 5, 9ª¢ and f −1¡©0, 3, 5, 9ª¢.
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?
4. This problem concerns functions f : ©1,2,3,4,5,6,7,8ª → ©0,1,2,3,4,5,6ª. How
¯
many such functions have the property that ¯ f −1¡©2ª¢¯¯ = 4?
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.
6. Given a function f : A → B and a subset Y ⊆ B, is f (f −1(Y )) = Y always true?
Prove or give a counterexample.
7. Given a function f : A → B and subsets W, X ⊆ A, prove f (W ∩ X ) ⊆ f (W) ∩ f (X ).
8. Given a function f : A → B and subsets W, X ⊆ A, then f (W ∩ X ) = f (W) ∩ f (X ) is
false in general. Produce a counterexample.
9. Given a function f : A → B and subsets W, X ⊆ A, prove f (W ∪ X ) = f (W) ∪ f (X ).
10. Given f : A → B and subsets Y , Z ⊆ B, prove f −1(Y ∩ Z) = f −1(Y ) ∩ f −1(Z).
11. Given f : A → B and subsets Y , Z ⊆ B, prove f −1(Y ∪ Z) = f −1(Y ) ∪ f −1(Z).
12. Consider f : A → B. Prove that f is injective if and only if X = f −1(f (X )) for all
X ⊆ A. Prove that f is surjective if and only if f (f −1(Y )) = Y for all Y ⊆ B.
13. Let f : A → B be a function, and X ⊆ A. Prove or disprove: f ¡f −1(f (X ))¢ = f (X ).
14. Letf : A → B be a function, and Y ⊆ B. Prove or disprove: f −1¡f (f −1(Y ))¢ = f −1(Y ).
CHAPTER
13
Cardinality of Sets
his chapter is all about cardinality of sets. At first this looks like a
T very simple concept. To find the cardinality of a set, just count its
elements. If A = ©a, b, c, dª, then |A| = 4; if B = ©n ∈ Z : −5 ≤ n ≤ 5ª, then
|B| = 11. In this case |A| < |B|. What could be simpler than that?
Actually, the idea of cardinality becomes quite subtle when the sets
are infinite. The main point of this chapter is to explain how there are
numerous different kinds of infinity, and some infinities are bigger than
others. Two sets A and B can both have infinite cardinality, yet |A| < |B|.
13.1 Sets with Equal Cardinalities
We begin with a discussion of what it me
ans for two sets to have the
same cardinality. Up until this point we’ve said |A| = |B| if A and B have
the same number of elements: Count the elements of A, then count the
elements of B. If you get the same number, then |A| = |B|.
Although this is a fine strategy if the sets are finite (and not too big!),
it doesn’t apply to infinite sets because we’d never be done counting their
elements. We need a new approach that applies to both finite and infinite
sets. Here it is:
Definition 13.1
Two sets A and B have the same cardinality, written
|A| = |B|, if there exists a bijective function f : A → B. If no such bijective
function exists, then the sets have unequal cardinalities, that is, |A| 6= |B|.
A
B
f
a
0
b
1
c
2
d
3
e
4
The above picture illustrates our definition. There is a bijective function
f : A → B, so |A| = |B|. The function f matches up A with B. Think of f as
describing how to overlay A onto B so that they fit together perfectly.
218
Cardinality of Sets
On the other hand, if A and B are as indicated in either of the following
figures, then there can be no bijection f : A → B. (The best we can do is a
function that is either injective or surjective, but not both). Therefore the
definition says |A| 6= |B| in these cases.
A
B
A
B
f
f
a
0
a
0
b
1
b
1
c
2
c
2
d
3
d
3
4
e
Example 13.1
The sets A = ©n ∈ Z : 0 ≤ n ≤ 5ª and B = ©n ∈ Z : −5 ≤ n ≤ 0ª
have the same cardinality because there is a bijective function f : A → B
given by the rule f (n) = −n.
Several comments are in order. First, if |A| = |B|, there can be lots of
bijective functions from A to B. We only need to find one of them in order to
conclude |A| = |B|. Second, as bijective functions play such a big role here,
we use the word bijection to mean bijective function. Thus the function
f (n) = −n from Example 13.1 is a bijection. Also, an injective function is
called an injection and a surjective function is called a surjection.
We emphasize and reiterate that Definition 13.1 applies to finite as
well as infinite sets. If A and B are infinite, then |A| = |B| provided there
Book of Proof Page 30