xR z, so R is transitive.
We’ve now shown that R is reflexive, symmetric and transitive, so it is an
equivalence relation.
The completes the first part of the problem. Now we move on the second part.
To find the equivalence classes, first note that
[0] = {x ∈ Z : xR0} = {x ∈ Z : 3x − 5 · 0 is even} = {x ∈ Z : 3x is even} = {x ∈ Z : x is even}.
Thus the equivalence class [0] consists of all even integers. Next, note that
[1] = {x ∈ Z : xR1} = {x ∈ Z : 3x − 5 · 1
ª
is even} = {x ∈ Z : 3x − 5 is even} = ©x ∈ Z : x is odd .
Thus the equivalence class [1] consists of all odd integers.
Consequently there are just two equivalence classes {. . . , −4, −2, 0, 2, 4, . . .} and
{. . . , −3,−1,1,3,5, .. .}.
9. Define a relation R on Z as xR y if and only if 4 | (x + 3y). Prove R is an
equivalence relation. Describe its equivalence classes.
This is reflexive, because for any x ∈ Z we have 4 | (x + 3x), so xR x.
To prove that R is symmetric, suppose xR y. Then 4 | (x + 3 y), so x + 3 y = 4a
for some integer a. Multiplying by 3, we get 3x + 9 y = 12a, which becomes
y + 3x = 12a − 8y. Then y + 3x = 4(3a − 2y), so 4 | (y + 3x), hence yRx. Thus we’ve
shown xR y implies yR x, so R is symmetric.
To prove transitivity, suppose xR y and yR z. Then 4|(x + 3 y) and 4|( y + 3z), so
x+3y = 4a and y+3z = 4b for some integers a and b. Adding these two equations
produces x + 4 y + 3z = 4a + 4b, or x + 3z = 4a + 4b − 4 y = 4(a + b − y). Consequently
4|(x + 3z), so xRz, and R is transitive.
As R is reflexive, symmetric and transitive, it is an equivalence relation.
Now let’s compute its equivalence classes.
[0] = {x ∈ Z : xR0} = {x ∈ Z : 4 | (x + 3 · 0)} = {x ∈ Z : 4 | x} =
{. . . − 4,0,4,8,12,16...}
[1] = {x ∈ Z : xR1} = {x ∈ Z : 4 | (x + 3 · 1)} = {x ∈ Z : 4 | (x + 3)} = {... − 3,1,5,9,13,17...}
[2] = {x ∈ Z : xR2} = {x ∈ Z : 4 | (x + 3 · 2)} = {x ∈ Z : 4 | (x + 6)} = {... − 2,2,6,10,14,18...}
[3] = {x ∈ Z : xR3} = {x ∈ Z : 4 | (x + 3 · 3)} = {x ∈ Z : 4 | (x + 9)} = {... − 1,3,7,11,15,19...}
11. Prove or disprove: If R is an equivalence relation on an infinite set A, then R
has infinitely many equivalence classes.
This is False. Counterexample: consider the relation of congruence modulo 2.
It is a relation on the infinite set Z, but it has only two equivalence classes.
13. Answer: m|A|
15. Answer: 15
289
Section 11.3 Exercises
1. List all the partitions of the set A = {a, b}. Compare your answer to the answer
to Exercise 5 of Section 11.2.
There are just two partitions {{a} , {b}} and {{a, b}}. These correspond to the two
equivalence relations R1 = {(a, a), (b, b)} and R2 = {(a, a), (a, b), (b, a), (b, b)}, respec-
tively, on A.
3. Describe the partition of Z resulting from the equivalence relation ≡ (mod 4).
Answer: The partition is {[0], [1], [2], [3]} =
© {...,−4,0,4,8,12,...},{...,−3,1,5,9,13,...}, {...,−2,2,4,6,10,14,...}, {...,−1,3,7,11,15,...}ª
5. Answer: Congruence modulo 2, or “same parity.”
Section 11.4 Exercises
1. Write the addition and multiplication tables for Z2.
+
[0]
[1]
·
[0]
[1]
[0]
[0]
[1]
[0]
[0]
[0]
[1]
[1]
[0]
[1]
[0]
[1]
3. Write the addition and multiplication tables for Z4.
+
[0]
[1]
[2]
[3]
·
[0]
[1]
[2]
[3]
[0]
[0]
[1]
[2]
[3]
[0]
[0]
[0]
[0]
[0]
[1]
[1]
[2]
[3]
[0]
[1]
[0]
[1]
[2]
[3]
[2]
[2]
[3]
[0]
[1]
[2]
[0]
[2]
[0]
[2]
[3]
[3]
[0]
[1]
[2]
[3]
[0]
[3]
[2]
[1]
5. Suppose [a],[b] ∈ Z5 and [a] · [b] = [0]. Is it necessarily true that either [a] = [0]
or [b] = [0]?
The multiplication table for Z5 is shown in Section 11.4. In the body of that
table, the only place that [0] occurs is in the first row or the first column. That
row and column are both headed by [0]. It follows that if [a] · [b] = [0], then
either [a] or [b] must be [0].
7. Do the following calculations in Z9, in each case expressing your answer as [a]
with 0 ≤ a ≤ 8.
(a) [8] + [8] = [7]
(b) [24] + [11] = [8]
(c) [21] · [15] = [0]
(d) [8] · [8] = [1]
290
Solutions
Chapter 12 Exercises
Section 12.1 Exercises
1. Suppose A = {0,1,2,3,4}, B = {2,3,4,5} and f = {(0,3),(1,3),(2,4),(3,2),(4,2)}. State
the domain and range of f . Find f (2) and f (1).
Domain is A; Range is {2, 3, 4}; f (2) = 4; f (1) = 3.
3. There are four different functions f : {a, b} → {0,1}. List them all. Diagrams will
suffice.
f1 = {(a,0),(b,0)} f2 = {(a,1),(b,0)}, f3 = {(a,0),(b,1)} f4 = {(a,1),(b,1)}
5. Give an example of a relation from {a, b, c, d} to {d, e} that is not a function.
One example is {(a, d), (a, e), (b, d), (c, d), (d, d)}.
7. Consider the set f = {(x, y) ∈ Z × Z : 3x + y = 4}. Is this a function from Z to Z?
Explain.
Yes, since 3x + y = 4 if and only if y = 4 − 3x, this is the function f : Z → Z defined
as f (x) = 4 − 3x.
9. Consider the set f = ©(x2, x) : x ∈ Rª. Is this a function from R to R? Explain.
No. This is not a function. Observe that f contains the ordered pairs (4, 2) and
(4, −2). Thus the real number 4 occurs as the first coordinate of more than one
element of f .
11. Is the set θ = {(X ,|X |) : X ⊆ Z5} a function? If so, what is its domain and range?
Yes, this is a function. The domain is P(Z5). The range is {0, 1, 2, 3, 4, 5}.
Section 12.2 Exercises
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.
Consider f = {(1, a), (2, a), (3, a), (4, a)}.
Then f is not injective because f (1) = f (2).
Also f is not surjective because it sends no element of A to the element c ∈ B.
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]?
The function cos : R → R is not injective because, for example, cos(0) = cos(2 π). It
is not surjective because if b = 5 ∈ R (for example), there is no real number for
; which cos(x) = b. The function cos : R → [−1, 1] is surjective. but not injective.
5. A function f : Z → Z is defined as f (n) = 2n + 1. Verify whether this function is
injective and whether it is surjective.
This function is injective. To see this, suppose m, n ∈ Z and f (m) = f (n).
This means 2m + 1 = 2n + 1, from which we get 2m = 2n, and then m = n.
Thus f is injective.
This function is not surjective. To see this notice that f (n) is odd for all
n ∈ Z. So given the (even) number 2 in the codomain Z, there is no n with
f (n) = 2.
291
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.
This is not injective because (0, 2) 6= (−1, 0), yet f ((0, 2)) = f ((−1, 0)) = 4. This is
not surjective because f ((m, n)) = 2n − 4m = 2(n − 2m) is always even. If b ∈ Z
is odd, then f ((m, n)) 6= b, for all (m, n) ∈ Z × Z.
9. Prove that the function f : R − {2} → R − {5} defined by f (x) = 5x+1
x−2 is bijective.
Proof. First, let’s check that f is injective. Suppose f (x) = f (y). Then
5x + 1
5 y + 1
=
x − 2
y − 2
(5x + 1)(y − 2) = (5y + 1)(x − 2)
5x y − 10x + y − 2 = 5yx − 10y + x − 2
−10x + y
=
−10y + x
11 y
=
11x
y
=
x.
Since f (x) = f ( y) implies x = y, it follows that f is injective.
Next, let’s check that f is surjective. For this, take an arbitrary element
b ∈ R − {5}
5x+1
. We want to see if there is an x ∈ R − {2} for which f (x) = b, or x−2 = b.
Solving this for x, we get:
5x + 1 =
b(x − 2)
5x + 1 =
bx − 2b
5x − xb
=
−2b − 1
x(5 − b) = −2b − 1.
Since we have assumed b ∈ R − {5}, the term (5 − b) is not zero, and we can
−2b − 1
divide with impunity to get x =
. This is an x for which f (x) = b, so f is
5 − b
surjective.
Since f is both injective and surjective, it is bijective.
■
11. Consider the function θ : {0,1} × N → Z defined as θ(a, b) = (−1)ab. Is θ injective?
Is it surjective? Explain.
First we show that θ is injective. Suppose θ(a, b) = θ(c, d). Then (−1)a b = (−1)c d.
As b and d are both in N, they are both positive. Then because (−1)a b = (−1)c d,
it follows that (−1)a and (−1)c have the same sign. Since each of (−1)a and (−1)c
equals ±1, we have (−1)a = (−1)c, so then (−1)a b = (−1)c d implies b = d. But also
(−1)a = (−1)c means a and c have the same parity, and because a, c ∈ {0,1}, it
follows a = c. Thus (a, b) = (c, d), so θ is injective.
Next note that θ is not surjective because θ(a, b) = (−1)a b is either positive or
negative, but never zero. Therefore there exist no element (a, b) ∈ {0, 1} × N for
which θ(a, b) = 0 ∈ Z.
292
Solutions
13. Consider the function f : R2 → R2 defined by the formula f (x, y) = (xy, x3). Is f
injective? Is it surjective?
Notice that f (0, 1) = (0, 0) and f (0, 0) = (0, 0), so f is not injective. To show that f
is also not surjective, we will show that it’s impossible to find an ordered pair
(x, y) with f (x, y) = (1,0). If there were such a pair, then f (x, y) = (xy, x3) = (1,0),
which yields x y = 1 and x3 = 0. From x3 = 0 we get x = 0, so x y = 0, a contradiction.
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?
Function f can described as a list ( f (A), f (B), f (C), f (D), f (E), f (F), f (G)), where
there are seven choices for each entry. By the multiplication principle, the total
number of functions f is 77 = 823543.
If f is injective, then this list can’t have any repetition, so there are 7! = 5040
injective functions. Since any injective function sends the seven elements of the
domain to seven distinct elements of the codomain, all of the injective functions
are surjective, and vice versa. Thus there are 5040 surjective functions and
5040 bijective functions.
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?
Function f can described as a list ( f (A), f (B), f (C), f (D), f (E), f (F), f (G)), where
there are two choices for each entry. Therefore the total number of functions
is 27 = 128. It is impossible for any function to send all seven elements of
{A, B, C, D, E, F, G} to seven distinct elements of {1,2}, so none of these 128
functions is injective, hence none are bijective.
How many are surjective? Only two of the 128 functions are not surjective, and
they are the “constant” functions {(A, 1), (B, 1), (C, 1), (D, 1), (E, 1), (F, 1), (G, 1)} and
{(A, 2), (B, 2), (C, 2), (D, 2), (E, 2), (F, 2), (G, 2)}. So there are 126 surjective functions.
Section 12.3 Exercises
1. If 6 integers are chosen at random, at least two will have the same remainder
when divided by 5.
Proof. Write Z as follows: Z = S4 {5k
j
+ j : k ∈ Z}.
=0
This is a partition of Z into 5
sets. If six integers are picked at random, by the pigeonhole principle, at least
two will be in the same set. However, each set corresponds to the remainder
of a number after being divided by 5 (for example, {5k + 1 : k ∈ Z} are all those
integers that leave a remainder of 1 after being divided by 5).
■
3. Given any six positive integers, there are two for which their sum or difference
is divisible by 9.
Proof. If for two of the integers n, m we had n ≡ m (mod 9), then n−m ≡ 0 (mod 9),
and we would be done. Thus assume this is not the case. Observe that the
293
only two element subsets of positive integers that sum to 9 are {1, 8}, {2, 7}, {3, 6},
and {4, 5}. However, since at least five of the six integers must have distinct
remainders from 1, 2, ..., 8 it follows from the pigeonhole principle that two
integers n, m are in the same set. Hence n + m ≡ 0 (mod 9) as desired.
■
5. Prove that any set of 7 distinct natural numbers contains a pair of numbers
whose sum or difference is divisible by 10.
Proof. Let S = {a1, a2, a3, a4, a5, a6, a7} be any set of 7 natural numbers. Let’s say
that a1 < a2 < a3 < · · · < a7. Consider the set
A
=
{a1 − a2, a1 − a3, a1 − a4, a1 − a5, a1 − a6, a1 − a7,
a1 + a2, a1 + a3, a1 + a4, a1 + a5, a1 + a6, a1 + a7}
Thus |A| = 12. Now let B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, so |B| = 10. Let f : A → B be the
function for which f (n) equals the last digit of n. (That is f (97) = 7, f (12) = 2,
f (230)
= 0, etc.) Then, since |A| > |B|, the pigeonhole principle guarantees that
f is not injective. Thus A contains elements a1 ± ai and a1 ± a j for which
f (a1 ± ai) = f (a1 ± a j). This means the last digit of a1 ± ai is the same as the last
digit of a1 ± a j. Thus the last digit of the difference (a1 ± ai) − (a1 ± a j) = ±ai ± a j
is 0. Hence ±ai ± a j is a sum or difference of elements of S that is divisible by
10.
■
Section 12.4 Exercises
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 .
g ◦ f = {(5,1),(6,1),(8,1)}
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.
g ◦ f = {(1,1),(2,1),(3,3)}; f ◦ g = {(1,1),(2,2),(3,2)}.
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.
p
3
g ◦ f (x) = x + 1; f ◦ g (x) =
x3 + 1
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.
Note g ◦ f (m, n) = g( f (m, n)) = g(mn, m2) = (mn + 1, mn + m2).
Thus g ◦ f (m, n) = (mn + 1, mn + m2).
Note f ◦ g (m, n) = f (g(m, n)) = f (m + 1, m + n) = ((m + 1)(m + n), (m + 1)2).
Thus f ◦ g (m, n) = (m2 + mn + m + n, m2 + 2m + 1).
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.
g ◦ f (m, n) = (m + n, m + n)
f ◦ g(m) = 2m
294
Solutions
Section 12.5 Exercises
1. Check that the function f : Z → Z defined by f (n) = 6 − n is bijective. Then
compute f −1.
It is injective as follows. Suppose f (m) = f (n). Then 6 − m = 6 − n, which reduces
to m = n.
It is surjective as follows. If b ∈ Z, then f (6 − b) = 6 − (6 − b) = b.
Inverse: f −1(n) = 6 − n.
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.
It is injective as follows. Suppose f (m) = f (n), which means 2m = 2n. Taking
log2 of both sides gives log2(2m) = log2(2n), which simplifies to m = n.
The function f is surjective as follows. Suppose b ∈ B. By definition of B this
means b = 2n for some n ∈ Z. Then f (n) = 2n = b.
Book of Proof Page 42
