m = k. Since m = k and n = `, it follows that (m, n) = (k, `). Therefore g is
injective.
204
Functions
To see that g is surjective, consider an arbitrary element (b, c) ∈ Z × Z.
We need to show that there is some (x, y) ∈ Z × Z for which g(x, y) = (b, c). To
find (x, y), note that g(x, y) = (b, c) means (x + y, x + 2 y) = (b, c). This leads to
the following system of equations:
x
+
y
=
b
x
+ 2y = c.
Solving gives x = 2b − c and y = c − b. Then (x, y) = (2b − c, c − b). We now
have g(2b − c, c − b) = (b, c), and it follows that g is surjective.
m
Example 12.6
Consider function h : Z × Z → Q defined as h(m, n) =
.
|n| + 1
Determine whether this is injective and whether it is surjective.
This function is not injective because of the unequal elements (1, 2) and
(1, −2) in Z×Z for which h(1,2) = h(1,−2) = 13. However, h is surjective: Take
any element b ∈ Q. Then b = cd for some c, d ∈ Z. Notice we may assume d is
positive by making c negative, if necessary. Then h(c, d −1) =
c
|d−1|+1 = c
d = b.
Exercises for Section 12.2
1. Let A = ©1,2,3,4ª and B = ©a, b, cª. Give an example of a function f : A → B that
is neither injective nor surjective.
2. Consider the logarithm function ln : (0,∞) → R. Decide whether this function is
injective and whether it is surjective.
3. Consider the cosine function cos : R → R. Decide whether this function is injective
and whether it is surjective. What if it had been defined as cos : R → [−1, 1]?
4. A function f : Z → Z × Z is defined as f (n) = (2n, n + 3). Verify whether this
function is injective and whether it is surjective.
5. A function f : Z → Z is defined as f (n) = 2n + 1. Verify whether this function is
injective and whether it is surjective.
6. A function f : Z × Z → Z is defined as f (m, n) = 3n − 4m. Verify whether this
function is injective and whether it is surjective.
7. A function f : Z × Z → Z is defined as f (m, n) = 2n − 4m. Verify whether this
function is injective and whether it is surjective.
8. A function f : Z × Z → Z × Z is defined as f (m, n) = (m + n,2m + n). Verify whether
this function is injective and whether it is surjective.
5x + 1
9. Prove that the function f : R − ©2ª → R − ©5ª defined by f (x) =
is bijective.
x − 2
µ x + 1 ¶3
10. Prove the function f : R − ©1ª → R − ©1ª defined by f (x) =
is bijective.
x − 1
11. Consider the function θ : ©0,1ª × N → Z defined as θ(a, b) = (−1)ab. Is θ injective?
Is it surjective? Bijective? Explain.
The Pigeonhole Principle
205
12. Consider the function θ : ©0,1ª×N → Z defined as θ(a, b) = a−2ab+b. Is θ injective?
Is it surjective? Bijective? Explain.
13. Consider the function f : R2 → R2 defined by the formula f (x, y) = (xy, x3). Is f
injective? Is it surjective? Bijective? Explain.
14. Consider the function θ : P(Z) → P(Z) defined as θ(X ) = X . Is θ injective? Is it surjective? Bijective? Explain.
15. This question concerns functions f : ©A, B, C, D, E, F,Gª → ©1,2,3,4,5,6,7ª. How
many such functions are there? How many of these functions are injective?
How many are surjective? How many are bijective?
16. This question concerns functions f : ©A, B, C, D, Eª → ©1,2,3,4,5,6,7ª. How many
such functions are there? How many of these functions are injective? How
many are surjective? How many are bijective?
17. This question concerns functions f : ©A, B, C, D, E, F,Gª → ©1,2ª. How many such
functions are there? How many of these functions are injective? How many
are surjective? How many are bijective?
(−1)n(2n − 1) + 1
18. Prove that the function f : N → Z defined as f (n) =
is bijective.
4
12.3 The Pigeonhole Principle
Here is a simple but useful idea. Imagine there is a set A of pigeons and
a set B of pigeon-holes, and all the pigeons fly into the pigeon-holes. You
can think of this as describing a function f : A → B, where pigeon X flies
into pigeon-hole f (X ). Figure 12.4 illustrates this.
Pigeons
Pigeon-holes
Pigeons
Pigeon-holes
f
f
(a)
(b)
Figure 12.4. The pigeonhole principle
In Figure 12.4(a) there are more pigeons than pigeon-holes, and it
is obvious that in such a case at least two pigeons have to fly into the
same pigeon-hole, meaning that f is not injective. In Figure 12.4(b) there
are fewer pigeons than pigeon-holes, so clearly at least one pigeon-hole
remains empty, meaning that f is not surjective.
206
Functions
Although the underlying idea expressed by these figures has little to
do with pigeons, it is nonetheless called the pigeonhole principle:
The Pigeonhole Principle
Suppose A and B are finite sets and f : A → B is any function. Then:
1. If |A| > |B|, then f is not injective.
2. If |A| < |B|, then f is not surjective.
Though the pigeonhole principle is obvious, it can be used to prove
some things that are not so obvious.
Example 12.7
Prove the following proposition.
Proposition
If A is any set of 10 integers between 1 and 100, then there
exist two different subsets X ⊆ A and Y ⊆ A for which the sum of elements
in X equals the sum of elements in Y .
To illustrate what this proposition is saying, consider the random set
A = ©5,7,12,11,17,50,51,80,90,100ª
of 10 integers between 1 and 100. Notice that A has subsets X = ©5, 80ª and
Y = ©7,11,17,50ª for which the sum of the elements in X equals the sum of
those in Y . If we tried to “mess up” A by changing the 5 to a 6, we get
A = ©6,7,12,11,17,50,51,80,90,100ª
which has subsets X = ©7, 12, 17, 50ª and Y = ©6, 80ª both of whose elements
add up to the same number (86). The proposition asserts that this is always
possible, no matter what A is. Here is a proof:
Proof. Suppose A ⊆ ©1,2,3,4,...,99,100ª and |A| = 10, as stated. Notice that
if X ⊆ A, then X has no more than 10 elements, each between 1 and 100,
and therefore the sum of all the elements of X is less than 100 · 10 = 1000.
Consider the function
f : P(A) → ©0,1,2,3,4,...,1000ª
where f (X ) is the sum of the elements in X . (Examples: f ¡©3, 7, 50ª¢ = 60;
f ¡©1, 70, 80, 95ª¢ = 246
©
.) As |P(A)| = 210 = 1024 > 1001 = ¯¯ 0, 1, 2, 3, . . . , 1000ª¯¯,
it follows from the pigeonhole principle that f is not injective. Therefore
there are two unequal sets X , Y ∈ P(A) for which f (X ) = f (Y ). In other
words, there are subsets X ⊆ A and Y ⊆ A for which the sum of elements
in X equals the sum of elements in Y .
■
The Pigeonhole Principle
207
Example 12.8
Prove the following proposition.
Proposition
There are at least two Texans with the same number of
hairs on their heads.
Proof. We will use two facts. First, the population of Texas is more than
twenty million. Second, it is a biological fact that every human head
has fewer than one million hairs. Let A be the set of all Texans, and
let B = ©0, 1, 2, 3, 4, . . . , 1000000ª. Let f : A → B be the function for which f (x)
equals the number of hairs on the head of x. Since |A| > |B|, the pigeonhole
principle asserts that f is not injective. Thus there are two Texans x and
y for whom f (x) = f (y), meaning that they have the same number of hairs
on their heads.
■
Proofs that use the pigeonhole principle tend to be inherently non-
constructive, in the sense discussed in Section 7.4. For example, the above
proof does not explicitly give us of two Texans with the same number of
hairs on their heads; it only shows that two such people exist. If we were
to make a constructive proof, we could find examples of two bald Texans.
Then they have the same number of head hairs, namely zero.
Exercises for Section 12.3
1. Prove that if six numbers are chosen at random, then at least two of them will
have the same remainder when divided by 5.
2. Prove that if a is a natural number, then there exist two unequal natural
numbers k and ` for which ak − a ` is divisible by 10.
3. Prove that if six natural numbers are chosen at random, then the sum or
difference of two of them is divisible by 9.
4. Consider a square whose side-length is one unit. Select any five points from
p2
inside this square. Prove that at least two of these points are within 2 units
of each other.
5. Prove that any set of seven distinct natural numbers contains a pair of numbers
whose sum or difference is divisible by 10.
6. Given a sphere S, a great circle of S is the intersection of S with a plane
through its center. Every great circle divides S into two parts. A hemisphere
is the union of the great circle and one of these two parts. Prove that if five
points are placed arbitrarily on S, then there is a hemisphere that contains
four of them.
7. Prove or disprove: Any subset X ⊆ ©1,2,3,...,2nª with |X | > n contains two
(unequal) elements a, b ∈ X for which a | b or b | a.
208
Functions
12.4 Composition
You should be familiar with the notion of function composition from algebra
and calculus.
Still, it is worthwhile to revisit it now with our more
sophisticated ideas about functions.
Definition 12.5
Suppose f : A → B and g : B → C are functions with the
property that the codomain of f equals the domain of g. The composition
of f with g is another function, denoted as g◦ f and defined as follows: If
x ∈ A, then g◦f (x) = g(f (x)). Therefore g◦f sends elements of A to elements
of C, so g◦ f : A → C.
The following figure illustrates the definition. Here f : A → B, g : B → C,
and g◦ f : A → C. We have, for example, g◦ f (0) = g( f (0)) = g(2) = 4. Be very
careful with the order of the symbols. Even though g comes first in the
symbol g◦ f , we work out g◦ f (x) as g( f (x)), with f acting on x first, followed
by g acting on f (x).
A
B
C
f
g
0
1
4
1
5
2
2
6
3
3
7
A
C
g ◦ f
0
4
1
5
2
6
3
7
Figure 12.5. Composition of two functions
Notice that the composition g ◦ f also makes sense if the range of f
is a subset of the domain of g. You should take note of this fact, but to
keep matters simple we will continue to emphasize situations where the
codomain of f equals the domain of g.
Example 12.9
Suppose A = ©a, b, cª, B = ©0, 1ª, C = ©1, 2, 3ª. Let f : A → B
be the function f = ©(a, 0), (b, 1), (c, 0)ª, and let g : B → C be the function
g = ©(0,3),(1,1)ª. Then g ◦ f = ©(a,3),(b,1),(c,3)ª.
Example 12.10
Suppose A = ©a, b, cª, B = ©0, 1ª, C = ©1, 2, 3ª. Let f : A → B
be the function f = ©(a, 0), (b, 1), (c, 0)ª, and let g : C → B be the function
g = ©(1,0),(2,1),(3,1)ª. In this situation the composition g ◦ f is not defined
because the codomain B of f is not the same set as the domain C of g.
Composition
209
Remember: In order for g ◦ f to make sense, the codomain of f must equal
the domain of g. (Or at least be a subset of it.)
Example 12.11
Let f : R → R be defined as f (x) = x2 + x, and g : R → R be
defined as g(x) = x + 1. Then g ◦ f : R → R is the function defined by the
formula g ◦ f (x) = g( f (x)) = g(x2 + x) = x2 + x + 1.
Since the domains and codomains of g and f are the same, we can in
this case do a composition in the other order. Note that f ◦ g : R → R is the
function defined as f ◦ g (x) = f (g(x)) = f (x + 1) = (x + 1)2 + (x + 1) = x2 + 3x + 2.
This example illustrates that even when g ◦ f and f ◦ g are both defined,
they are not necessarily equal. We can express this fact by saying function
composition is not commutative.
We close this section by proving several facts about function composition
that you are likely to encounter in your future study of mathematics. First,
we note that, although it is not commutative, function composition is
associative.
Theorem 12.1
Composition of functions is associative. That is if f : A → B,
g : B → C and h : C → D, then (h ◦ g) ◦ f = h ◦ (g ◦ f ).
Proof. Suppose f , g, h are as stated. It follows from Definition 12.5 that
both (h ◦ g) ◦ f and h ◦ (g ◦ f ) are functions from A to D. To show that they
are equal, we just need to show
³
´
³
´
(h ◦ g) ◦ f (x) = h ◦ (g ◦ f ) (x)
for every x ∈ A. Note that Definition 12.5 yields
³
´
(h ◦ g) ◦ f (x) = (h ◦ g)(f (x)) = h(g(f (x)).
Also
³
´
h ◦ (g ◦ f ) (x) = h(g ◦ f (x)) = h(g(f (x))).
Thus
³
´
³
´
(h ◦ g) ◦ f (x) = h ◦ (g ◦ f ) (x),
as both sides equal h(g( f (x))).
■
Theorem 12.2
Suppose f : A → B and g : B → C. If both f and g are
injective, then g ◦ f is injective. If both f and g are surjective, then g ◦ f is
surjective.
210
Functions
Proof. First suppose both f and g are injective. To see that g◦ f is injective,
&
nbsp; we must show that g ◦ f (x) = g ◦ f ( y) implies x = y. Suppose g ◦ f (x) = g ◦ f ( y).
This means g( f (x)) = g( f ( y)). It follows that f (x) = f ( y). (For otherwise g
wouldn’t be injective.) But since f (x) = f ( y) and f is injective, it must be
that x = y. Therefore g ◦ f is injective.
Next suppose both f and g are surjective. To see that g ◦ f is surjective,
we must show that for any element c ∈ C, there is a corresponding element
a ∈ A for which g ◦ f (a) = c. Thus consider an arbitrary c ∈ C. Because g
is surjective, there is an element b ∈ B for which g(b) = c. And because
f is surjective, there is an element a ∈ A for which f (a) = b. Therefore
g( f (a)) = g(b) = c, which means g ◦ f (a) = c. Thus g ◦ f is surjective.
■
Exercises for Section 12.4
1. Suppose A = ©5,6,8ª, B = ©0,1ª, C = ©1,2,3ª. Let f : A → B be the function f =
©(5,1),(6,0),(8,1)ª, and g : B → C be g = ©(0,1),(1,1)ª. Find g ◦ f .
2. Suppose A = ©1,2,3,4ª, B = ©0,1,2ª, C = ©1,2,3ª. Let f : A → B be
f = ©(1,0),(2,1),(3,2),(4,0)ª,
and g : B → C be g = ©(0, 1), (1, 1), (2, 3)ª. Find g ◦ f .
3. Suppose A = ©1,2,3ª. Let f : A → A be the function f = ©(1,2),(2,2),(3,1)ª, and let
g : A → A be the function g = ©(1,3),(2,1),(3,2)ª. Find g ◦ f and f ◦ g.
4. Suppose A = ©a, b, cª. Let f : A → A be the function f = ©(a, c),(b, c),(c, c)ª, and let
g : A → A be the function g = ©(a, a),(b, b),(c, a)ª. Find g ◦ f and f ◦ g.
p
5. Consider the functions f , g : R → R defined as f (x) = 3 x + 1 and g(x) = x3. Find
the formulas for g ◦ f and f ◦ g.
6. Consider the functions f , g : R → R defined as f (x) = 1
x2+1 and g(x) = 3x + 2. Find
the formulas for g ◦ f and f ◦ g.
7. Consider the functions f , g : Z × Z → Z × Z defined as f (m, n) = (mn, m2) and
g(m, n) = (m + 1, m + n). Find the formulas for g ◦ f and f ◦ g.
8. Consider the functions f , g : Z × Z → Z × Z defined as f (m, n) = (3m − 4n,2m + n)
and g(m, n) = (5m + n, m). Find the formulas for g ◦ f and f ◦ g.
9. Consider the functions f : Z × Z → Z defined as f (m, n) = m + n and g : Z → Z × Z
defined as g(m) = (m, m). Find the formulas for g ◦ f and f ◦ g.
10. Consider the function f : R2 → R2 defined by the formula f (x, y) = (xy, x3). Find
a formula for f ◦ f .
Inverse Functions
211
12.5 Inverse Functions
You may recall from calculus that if a function f is injective and surjective,
then it has an inverse function f −1 that “undoes” the effect of f in the
Book of Proof Page 29
