# Solution Manual For Analysis with an Introduction to Proof, 5th Edition

Preview Extract

Section 2.1 x Basic Set Operations
This work is protected by United States copyright laws and is provided solely for
the use of instructors in teaching their courses and assessing student learning.
Dissemination or sale of any part of this work (including on the World Wide Web)
will destroy the integrity of the work and is not permitted. The work and materials
from it should never be made available to students except by instructors using
the accompanying text in their classes. All recipients of this work are expected to
abide by these restrictions and to honor the intended pedagogical purposes and
the needs of other instructors who rely on these materials.
Analysis
with an Introduction to Proof
5th Edition
by Steven R. Lay
[email protected]
Chapter 2 โ Sets and Functions
Solutions to Exercises
The following notations are used throughout this document:
= the set of natural numbers {1, 2, 3, 4, โฆ}
= the set of rational numbers
= the set of real numbers
= โfor everyโ
= โthere existsโ
ย = โsuch thatโ
Section 2.1 โ Basic Set Operations
1. (a) True: Definition 2.1.3.
(b) False: is the set of positive integers.
(c) True: Example 2.1.5.
(d) True: Theorem 2.1.7.
Copyright ยฉ 2014 Pearson Education, Inc.
12
Section 2.1 x Basic Set Operations
13
2. (a) False: A ย B = ย means A and B are disjoint.
(b) True: Definition 2.1.8.
(c) False: x ย AB means x ย A and x ย B.
(d) False: This is OK to use since S being nonempty is the only nontrivial case.
3. Answer in book: (a) True; (b) False; (c) True; (d) True; (e) False; (f ) False; (g) False; (h) True.
4. (a) {6, 8}; (b) {2, 4, 6, 8, 10};
(g) ย;
(h) {5, 7}.
(c) {2, 4};
(d) {6, 8};
(e) {10};
(f ) {5, 7, 10};
5. The answer to (a) is in the book. Part (b) is similar.
6. (a) U;
(b) ย;
(c) A ย B;
(d) A ย B;
(f ) A.
(e) A;
7. (a) The diagram is the same as (A ย B)(A ย B);
(b) ย;
8. (a) True. ย is a subset of every set.
(c) True. ย is an element of S, so {ย} ย S.
(c) A;
(d) U A.
(b) True. ย is an element of S.
(d) True. {ย} is an element of S.
9, 10, and 11 are routine.
12. Beginning sentence: โLet x ย Aโ or โSuppose x ย Aโ or โIf x ย Aโฆโ You would have to show that x ย B.
13. Beginning sentence: โLet x ย Aโ or โSuppose x ย Aโ or โIf x ย Aโฆโ You would have to show that x ย B.
14. a, b, d.
15. a, c.
16. b, d.
17. a, b, c, d.
18. This is routine.
19. Hint in book: Suppose that U = A ย B and A ย B = ย. To show A ย U B, let x ย A. Then x ย B. (Why?) Since
x is not in B, where is it?
On the other hand, to show U B ย A, suppose x ย U B. Expand what it means for x to be in U B, and
combine this with one of the original hypotheses to conclude that x ย A.
20. This is similar to Exercise 19.
21. True. Both are equal to A ย B. Here is one of the proofs: If x ย A ย B, then x ย A and x ย B. Thus x ย AB,
so x ย A(AB). Conversely, if x ย A(AB), then x ย A and x ย AB. If x ย B, then since x ย A, x ย AB,
a contradiction. Thus x ย B and so x ย A ย B.
22. False. The left side is A and the right side is B.
23 and 24 are routine.
25. (a) Answer in book: * BยB B [1, 2],
(c) * B = [2, f), B = {2};
BยB B {1};
(b) * B = (1, 2), B = ย;
(d) * B = [0, 5), B = [2, 3].
26 is routine.
Section 2.2 – Relations
1. (a) True: Theorem 2.2.2.
(b) False: โorderedโ subset is meaningless.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.2 x Relations
(c) True: Theorem 2.2.15.
(d) False: True for an equivalence relation, but not in general.
2. (a) False: It should be (a, b).
(b) True: Definition 2.2.9.
(c) False: {Ex : x ย S} determines the partition.
(d) True: Definition 2.2.12.
3. (a, a) = {{a}, {a, a}}, but {a, a} = {a}, so (a, a) = {{a}, {a}} = {{a}}.
4. {a} u {a} = {(x, y) : x ย {a} and y ย {a}} = {(a, a)}. But this is equal to {{{a}}} by Exercise 3.
5. (2, 3) ย (3, 2) = {{2,3}}.
6. A u B = ย.
7. ย, {(a, 1)}, {(a, 2)}, {(a, 3)}, {(a, 1), (a, 2)}, {(a, 1), (a, 3)}, {(a, 2), (a, 3)}, {(a, 1), (a, 2), (a, 3)}
8. (a) 4;
(b) 24 = 16;
(c) 29 = 512.
9. The answers are in the back of the book.
10. (a) False. Let A = {1} and B = {2}. Then A u B = {(1, 2)} and B u A = {(2, 1)}.
(b) True; (c) True; (d) False. See Practice 2.2.6 for a counterexample.
11. (a) Answer in book: reflexive, transitive
(b) reflexive and transitive
(c) reflexive (if everyone likes themselves)
(d) reflexive and transitive
(e) Answer in book: all three
(f ) symmetric
(g) symmetric and transitive
(h) reflexive and symmetric
12. Examples with the set S = {1, 2, 3}:
(a) reflexive only: {(1,1), (2,2), (3,3), (1,2), (2,3)}
(b) symmetric only: {(1,2), (2,1)}
(c) transitive only: {(1,2), (2,3), (1,3)}
(d) all but transitive: {(1,1), (2,2), (3,3), (1,2), (2,3), (2,1), (3,2)}
(e) all but symmetric: {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)}
(f ) all but reflexive: {(1,1), (2,2)} or ย
Examples from other sets:
(a) See Exercise 5(c).
(b) Perpendicular lines in the plane; numbers whose gcd is 1; x z y ; | x โ y | ! 1.
(c) x y
(d) | x โ y | 1
(e) x d y ; x divides y ; A ย B.
(f ) Let S = {2} and define x R y iff x y; let S = and R = {(1, 1), (2, 2), (3, 3)}.
13. Answer in book: E( a ,b ) is a vertical line through the point (a, b).
Copyright ยฉ 2014 Pearson Education, Inc.
14
Section 2.2 x Relations
15
14. Rewriting the equation as a โ b = c โ d makes it easier to verify the equivalence relation properties. E(7,3) is the line
x โ y = 4.
15. (a) The partition P is a family of parallel lines of the form x + 2y = k.
(b) E(5,3) is the line x + 2y = 11.
16. (a) The partition P is a family of parallel lines of the form y = 3x + k.
(b) E(2,5) is the line y = 3x โ 1.
17. R is an equivalence relation. P = {{1}, {2,3}}.
18. R is not symmetric.
19. Answer in book: R = {(a, a), (b, b), (c, c), (d, d), (b, c), (c, b)}.
20. R = {(a, a), (b, b), (c, c), (d, d ), (b, c), (c, b), (b, d ), (d, b), (c, d ), (d, c)}.
21. P = {{a, c}, {b}, {d}, {e}}.
22. P = {{a, b, d}, {c}, {e}}.
23. The verification that R is an equivalence relation is straightforward. E5 is the set of odd numbers. There are two
distinct classes.
24. The verification that R is an equivalence relation is straightforward. E5 is the set of integers of the form 3k + 2 for
some k ย ‘. There are 3 distinct classes.
25. It is an equivalence relation.
26. It is not reflexive and not transitive.
27. (a) is routine; (b) {(9,2), (2,9), (6,3), (3,6), (1,18), (18,1)};
(c) {(1,3), (3,1)}.
(d) {(1,4), (4,1), (2,2)} (e) {(1,8), (8,1), (2,4), (4,2). (f ) E(9, 2) is the hyperbola xy = 18.
28. (a) is routine; (b) E(9, 2) = {(3,4), (9,2), (81,1)};
(c) {(5,2), (25,1)};
(d) {(2,6), (4,3), (8,2), (64,1)}.
29. (a) ab = ba, so R is reflexive. If ay = bx, then xb = ya, so R is symmetric. For the transitive property, it is easier to
replace ay = bx with the equivalent condition a/b = x/y. Clearly, if a/b = x/y, and x/y = c/d, then a/b = c/d, so R
is transitive.
(b) Each equivalence class consists of ordered pairs of numbers where the ratio of the first number to the second
number is the same for all pairs in the class.
30. (a) R = {(1,1), (2,2), (3,3)}. There are three equivalence classes and P = {{1}, {2}, {3}}.
(b) R = {(1,1), (2,2), (3,3), (1,2), (2,1)}. There are two equivalence classes and P = {{1,2}, {3}}.
(c) R = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)}. There is one equivalence class and P = {{1,2,3}}.
31. (a) True: If R and S are reflexive, then x ย A, (x, x) ย R and (x, x) ย S. Hence (x, x) ย R ย S and R ย S is
reflexive.
(b) True: If either R or S is reflexive, then R ย S is reflexive. For example, if R is reflexive, then x ย A,
(x, x) ย R. But then (x, x) ย R ย S.
(c) Answer in book: If (x, y) ย R ย S, then (x, y) ย R and (x, y) ย S. Since R and S are symmetric, this implies
( y, x) ย R and ( y, x) ย S. Thus ( y, x) ย R ย S.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.2 x Relations
16
(d) True: If (x, y) ย R ย S, then (x, y) ย R or (x, y) ย S. If (x, y) ย R, then since R is symmetric, ( y, x) ย R. But
then ( y, x) ย R ย S. Similarly, if (x, y) ย S, then ( y, x) ย S and ( y, x) ย R ย S.
(e) True: Suppose (x, y) ย R ย S and ( y, z) ย R ย S. Then (x, y) ย R and ( y, z) ย R, so (x, z) ย R since R is
transitive. Similarly, (x, y) ย S and ( y, z) ย S, so (x, z) ย S since S is transitive. Thus (x, z) ย R ย S.
(f ) False: If (x, y) ย R ย S and ( y, z) ย R ย S, then it may be that (x, y) ย R and ( y, z) ย S. For example, let
A = {1, 2, 3} with R = {(1, 1), (2, 2), (3, 3), (1, 2),(2, 1)} and S = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}.
(g) True: This follows from parts (a), (c), and (e).
(h) False: The example given in (f ) also works here since R and S in that example are actually equivalence
relations.
32. Suppose R is an equivalence relation and suppose a R b and b R c. Since R is symmetric, c R b and b R a. Since R is
transitive, this implies c R a, and R is circular.
Conversely, suppose R is reflexive and circular. Suppose a R b. Since R is reflexive, b R b. Since R is circular
this implies b R a. Thus R is symmetric. Now suppose a R b and b R c. Since R is circular, then c R a. By the first
part, R is symmetric. Thus a R c, and R is transitive.
33. (a) Suppose (a, b, c) = (d, e, f ). Then ((a, b), c) = ((d, e), f ). Theorem 2.2.2 implies that (a, b) = (d, e) and c = f .
Applying Theorem 2.2.2 again to the pairs (a, b) and (d, e), we have a = d and b = e. The converse is trivial.
(b) (1, 1, 2) becomes {{1}, {1}, {1,2}} = {{1}, {1,2}} and (1, 2, 1) becomes {{1}, {1, 2}, {1, 2}} = {{1}, {1,2}}.
Section 2.3 – Functions
1. (a) False: We must also know that a ย A b ย B ย (a,b) ย f.
(b) True: See the comment after Definition 2.3.1.
(c) True: Definition 2.3.5.
(d) False: B is the codomain of f .
(e) False: rng f = B.
(f ) True: Definition 2.3.6.
2. (a) True: Definition 2.3.5.
(b) False: f must be bijective. If f is not 11, then f โ 1( y) is a subset of A, not an element in A.
(c) False: if f is not surjective, then f โ 1(D) may be empty.
(d) True: Theorem 2.3.19.
(e) True. See the comment after Definition 2.3.23.
(f ) False. The identity function maps onto by i(x) = x for all x ย .
3. (a) Answer in book: [2, f); (b) [4, f).
(c) Answer in book: f (x) = (x + 3)2 โ 5, so the range is [โ5, f);
(d) [โ5, 5].
4. (a) f = {(1, 5), (2, 5), (3, 5)} is the only possibility.
(b) f1 = {(4, 5)} and f2 = {(4, 6)} are the only possibilities.
(c) f1 = {(1,5), (2,5)}, f2 = {(1,6), (2,6)}, f3 = {(1,5), (2,6)}, f4 = {(1,6), (2,5)}
5. (a) Answer in book: There are nine different functions: six are injective and none are surjective.
(b) There are 8 different functions; none are injective and 6 are surjective.
(c) nm.
6. (a) A = [5, f) or A = (f, 5]
(b) A = [โ1/2, f) or A = (f, โ1/2]
(c) A = [โS/2, S/2] is a simple example.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.3 x Functions
17
7. (a) Answer in book: injective [Note that 2 has no pre-image.]
(b) bijective
(c) Answer in book: surjective [Note that f (0) = f (1).]
(d) bijective
(e) injective [Note that 3 has no pre-image.]
(f ) bijective
(g) injective [Note that 2/3 has no pre-image.]
8. (a) surjective only (assuming that a circle may have radius 0)
(b) both injective and surjective
9. (a) Answer in book: This proves the converse of the condition required for injective, so it is not a valid proof.
(b) It is not valid. The statement โsince x1 = x2โ should be โsince f (x1) = f (x2).โ
(c) This is valid since it is the contrapositive condition required for injective, but it is not very straightforward.
(d) This proves the inverse of the condition required for injective, so it is not a valid proof.
(e) This only proves one case, not the general rule, so it is not a valid proof.
(f ) This is valid and direct.
10. (a) Define f (1) = 1 and f ( n) = n โ 1 for n ! 1.
(b) Let f (n) = n + 1 or f (n) = n2.
(c) Let f (n) = 2 n.
(d) Let f (n) = n.
11. (a) Hint in book: Suppose f (a) = f (b) and apply f to both sides.
Proof: Suppose f (a) = f (b). Apply f to both sides to obtain ( f q f )(a) = ( f q f )(b). Since f q f is injective,
this implies a = b.
(b) Let y ย S. Since f q f is surjective, there exists x ย S such that ( f q f )(x) = y. That is, f ( f (x)) = y.
But f (x) ย S, so w = f (x) is an element of S such that f (w) = y. Hence f is surjective.
12. (a) Let f (x) = x and g(x) = โx. Then ( f + g)(x) = 0 for all x, which is neither injective nor surjective.
(b) Let f (x) = g(x) = x. Then ( f g)(x) = x2, which is neither injective nor surjective.
13. (a) {b, c, e}; (b) {1, 2}.
14. (a) {โ3, 3};
(b) (โ3, โ2] ย [2, 3);
(c) [โ3, 3].
15. These are routine.
(d) Hint in book: To prove f (C1 ย C 2) ย f (C1) ย f (C 2), let y ย f (C1 ย C 2). Then by the definition of
f (C1 ย C 2), there exists x in C1 ย C 2 such that f (x) = y. Use the fact that x ย C1 ย C 2 to show that
y ย [ f (C1) ย f (C 2)]. For the converse, begin with an element y in [ f (C1) ย f (C 2)]. Then expand what it
means for y to be in the union of two sets.
16. Define f : o by f (x) = x2.
(a) Let C = [0, 2]. Then f 1[ f (C )] = [2, 2].
(b) Let D = [1, 4]. Then f [ f 1(D)] = [0, 4].
(c) Let C1 = [2,1] and C2 = [1,2]. Then f (C1 ย C2) = ย and f (C1) ย f (C2) = [1,4].
17. (a) True. Let y ย f (S ). Then there exists x ย S such that f (x) = y. Since S ย T, we have x ย T. But then
y = f (x) ย f (T ).
(b) False. Define f : o by f (x) = x2. Let S = [โ1, 2] and T = [0, 2]. Then f (S ) = f (T ) = [0, 4], but S is not a
subset of T.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.3 x Functions
18
18. (a) Let x ย f 1[ f (C )]. Then f (x) ย f (C). Since f is injective, this implies x ย C. Thus f 1[ f (C )] ย C. The
reverse inclusion is Theorem 2.3.16(a).
(b) Let y ย D. Since f is surjective x in A ย f (x) = y. But then x ย f 1(D ) so that y = f (x) ย f [ f 1(D )]. Thus
D ย f [ f 1(D )]. The reverse inclusion is Theorem 2.3.16(b).
19. The proof is routine.
20. (a) True. The proof is routine.
(b) f must be bijective.
21. (a) Let f (x) = x2, A = B = , and C = [0, f). Then 2 ย AC, so 4 = f (2) ย f (AC ). But 2 ย C, so
4 = f (2) ย f (C ). Thus 4 ย f (A) f (C ).
(b) If y ย f (A) f (C ), then y ย f (A) and y ย f (C ). Since y ย f (A), x ย A ย f (x) = y. Since y ย f (C ), x ย C.
Thus x ย AC, and so y = f (x) ย f (AC ).
(c) Hint in book: If f is injective, then equality holds.
Proof: Let y ย f (AC ). Since f is injective a unique x in A ย f (x) = y. Now suppose y were in f (C ).
Then x ย C, since x is the only point in A that maps onto y. But y ย f (AC ), so we must also have x ย AC ;
whence x ย C. This contradiction means that y ย f (C ). Now x ย A, so y = f (x) ย f (A). Thus y ย f (A) f (C )
and f (AC ) ย f (A) f (C ). The reverse inclusion follows from part (b).
(d) If f is bijective, then equality holds. f injective implies f (AC ) = f (A) f (C ), and f surjective implies f (A) =
B.
22. (a) g 1 = {(1, a), (2, c), (3, b)} and rng g 1 = {a, b, c}.
(b) f q g = {(a, a), (b, a), (c, b)} and rng ( f q g) = {a, b}.
(c) g q f = {(1, 1), (2, 3), (3, 1)} and rng (g q f ) = {1, 3}.
(d) f q g q f = {(1, a), (2, a), (3, a)} and rng ( f q g q f ) = {a}.
23. Hint in book: We are asked to prove that f being equal to g (as sets of ordered pairs) is equivalent to the
condition that dom f = dom g and x ย dom f, f (x) = g (x).
Proof: Suppose that f = g (as sets of ordered pairs). That is, (x, y) ย f iff (x, y) ย g. Now,
dom f = {x : (x, y) ย f } = {x : (x, y) ย g} = dom g.
Furthermore, suppose x ย A = dom f . Then y in B (the codomain of f ) such that f (x) = y. This means that
(x, y) ย f and so (x, y) ย g. But then, g(x) = y so that f (x) = g (x).
Conversely, suppose that dom f = dom g = A and that f (x) = g (x) x ย A. If (x, y) ย f, then y = f (x). But
then y = g (x), so (x, y) ย g. Thus f ย g. Similarly, if (x, y) ย g, then y = g (x) = f (x), so (x, y) ย f. Hence g ย f ,
and we conclude that f = g.
24. For any x in A we have
[h q (g q f )](x) = h[(g q f )(x)] = h[g( f (x))], and also
[(h q g) q f ](x) = [h q g]( f (x)) = h[g( f (x))].
Since dom h q (g q f ) = dom (h q g) q f = A, we have h q (g q f ) = (h q g) q f by Exercise 23.
25. Hint in book: It is clear that g q f is a relation between A and C. To show it is a function from A to C , suppose
that (x, y) ย g q f and (x, yc) ย g q f . Then prove that y = yc.
Proof: Since (x, y) ย g q f , z in B ย (x, z) ย f and (z, y) ย g. Similarly, since (x, yc) ย g q f , z c in B ย (x, z c) ย f
and (z c, y c) ย g. Since f is a function we have z = z c. But then since g is a function, y = y c. Since dom f = A and
rng f ย dom g, it follows that dom (g q f ) = A, so that g q f : A o C.
26. Let A = [0, f), B = , and C = [0, f). Define f (x) = x and g (x) = x2. Then g q f is injective since dom g q f = [0,f),
but g is not injective since dom g = .
27. Same example as Exercise 26.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.3 x Functions
19
28. Define f : [0, f) o by f (x) = x and g: o [0, f) by g(x) = x2. Then f is not surjective and g is not injective,
but g q f is the identity, which is bijective.
29. (a) To see that f is surjective, let y ย B. Then y = iB( y) = ( f q g)( y) = f ( g ( y)). Thus g ( y) is an element of A
that f maps onto y, so rng f = B. To see that f is injective, suppose f (x) = f (x c). Then g ( f (x)) = g ( f (x c)).
But g q f = iA, so x = (g q f )(x) = (g q f )(x c) = x c.
(b) Hint in book: Use Exercise 23.
Proof: Since dom g = B = dom f 1, by Exercise 23 it remains to show that g( y) = f 1( y), y ย B.
Now y ย B we have
f 1( y) = f 1[iB( y)] = [f 1 q ( f q g)]( y) = [( f 1 q f ) q g]( y) = (iA q g)(y) = g (y),
where we have used the associative property of Exercise 24.
30. Let f = h 1 q g. Then x ย A, (h q f )(x) = h( f (x)) = h(h1( g (x))) = g (x), so h q f = g.
31. Suppose (c, a) ย f โ 1 q g 1. Then by the definition of composition, there exists b ย B such that (c, b) ย g 1 and
(b, a) ย f โ 1. The definition of inverse implies (b, c) ย g and (a, b) ย f. That is, g(b) = c and f (a) = b. Thus,
g( f (a)) = g(b) = c and (a, c) ย g q f . So, (c, a) ย (g q f ) 1, and ( f โ 1 q g 1) ย (g q f ) 1.
32. (a) Suppose f has a left inverse g. If f (x) = f ( y), then x = g [ f (x)] = g [ f ( y)] = y, so f is injective.
Conversely, suppose f is injective and let y ย B. If y ย rng f, then a unique x in A ย f (x) = y. In this
case define g ( y) = x. If y ย rng f , then choose any p ย A and define g ( y) = p. Then g ( y) is defined for all
y ย B and g : B o A is a function. Since g [ f (x)] = x x ย A, g is a left inverse for f.
(b) Suppose f has a right inverse g. If y ย B, then y = f [g ( y)], so y ย rng f. Thus f is surjective.
Conversely, suppose f is surjective and let y ย B. Then (at least one) x in A ย f (x) = y. Pick one such
x and define g ( y) = x. Then f [g ( y)] = f (x) = y so that g : B o A is a right inverse for f. (Note that this part of
the proof uses the Axiom of Choice.)
33. Hint in book: Suppose that S has at least two elements, say s1 and s2. Define two functions f : S o S and g : S o S
in such a way that f q g z g q f.
Proof: Suppose S has at least 2 elements, say s1 and s2. Define f (s) = s1 and g(s) = s2 s ย S. Then g q f (s1) = s2
and f q g (s1) = s1.
34. (a) This is routine.
(b) Let Ex ย E, where x ย A. Then g (x) = Ex, so g is surjective.
(c) Suppose h(Ex) = h(Ey). Then f (x) = f ( y), so x R y and Ex = Ey. Hence h is injective.
(d) Let x ย A. Then h (g (x)) = h(Ex) = f (x) by the definitions of g and h.
(e) g maps a given student s onto the set Es of all students who have the same age as s. h maps Es onto the
common age shared by all the students in Es.
Section 2.4 – Cardinality
1. (a) True: Definition 2.4.1.
(b) False: S might be ย.
(c) False: It is transfinite.
(d) False: The domain of the bijection should be .
(e) True: Theorem 2.4.9.
(f ) False: It could be finite.
2. (a) False: f : o S must be surjective.
(b) True: Example 2.4.11(c) and Definition 2.4.6.
(c) True: Theorem 2.4.10.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.4 x Cardinality
20
(d) False: is uncountable.
(e) True: Definition 2.4.14.
(f ) False: It says there is no cardinal number between ย0 and c.
3. (a) f (x) = 3x + 1 is one possibility.
(b) f (x) = 5x + 2 is one possibility.
(c) Answer in book: Let f (x) = 1/(n + 1) if n in ย x = 1/n, and f (x) = x otherwise.
(d) Let g (0) = 1/2 and g (x) = f (x) x ย (0, 1) where f is an in part (b).
(e) Let f (x) = x/(1 โ x) or let f (x) = (1/x) โ 1, or a similar function.
(f ) f (x) = tan (Sx โ S/2) is one possibility.
4. (a) f (x) = (n โ m)x + m
(b) Given intervals (m, n) and ( p, q), bijections f : (0, 1) o (m, n) and g : (0, 1) o (p, q). Then g q f 1 is a
bijection from (m, n) onto ( p, q).
5. Hint in book: Given a bijection f : S T o T S, define g (x) = f (x) if x ย S T and g (x) = x if x ย S ย T.
Proof: Since S = (S T ) ย (S ย T ), dom g = S. Likewise, since T = (T S) ย (S ย T ), g maps S onto T. Since (T S)
ย (S ย T) = ย, g is injective. Indeed, suppose g (x) = g ( y). If g (x), g ( y) ย T S, then x, y ย S T, so that g (x) = f (x)
and g ( y) = f ( y). But f is injective, so x = y. If g (x), g ( y) ย S ย T, then x = y by the defintion of g.
6. Let S be a finite set. If S = ย, then the only subset of S is ย, which is finite. Thus we assume S z ย and
conclude a bijection f : In o S for some n ย . If T ย S and T z ย, then let i1, i2, โฆ, im be the elements of
In = {1, 2, โฆ, n} that are in f (T). Define g : T o Im by g (t) = j, where f (t) = ij. It follows that g is bijective, so
T is finite.
7. n ย , let Sn = {k/n: k ย ‘}. Then each Sn ~ ‘, so each Sn is countable by Practice 2.4.8. Since _
Example 2.4.11(d) implies that is countable.
*fn 1 Sn ,
8. (a) Suppose S ย T. Then the identity map IS on S is an injection from S into T. That is, IS (x) = x, x ย S. Hence
| S | d | T |.
(b) Since S ย S, (b) follows form part (a).
(c) Suppose | S | d | T | and | T | d | U |. Then injections f : S o T and g : T o U. But then g q f : S o U is injective
by Theorem 2.3.18, so | S | d | U |.
(d) Since {1, 2, โฆ, m} ย {1, 2, โฆ, n} when m d n, (d) follows from part (a).
(e) Suppose S is a nonempty finite set. Then n ย and a bijection f : In o S. Then f 1 : S o is injective, so
| S | d ย0. Since is infinite and S is finite, | S | z ย0. Thus | S | | U |, a contradiction.
19. (a) If | S | d | T |, then an injection f : S o T. The function f also describes a mapping from P (S) to P (T) as
indicated in Notation 2.3.13. Since f : S o T is injective, f (x) ย f (A) iff x ย A. Thus if f (A) = f (B), then A =
B, and f : P (S) o P (T) is injective. Hence | P (S) | d | P (T) |.
(b) Follows directly from (a).
20. It is not possible. For every set S, we have ย ย S, so ย ย P (S) and P (S) is not the empty set.
21. C ย P (A ย B) iff C ย (A ย B) iff C ย A and C ย B iff C ย P (A) and C ย P (B) iff C ย P (A ย B).
22. If C ย [P (A) ย P (B)], then C ย A or C ย B. In either case, C ย (A ย B), so C ย P (A ย B). For a
counterexample, let A = {1, 2} and B = {3, 4}. Then C = {2, 3} ย P (A ย B), but C ย P (A) and C ย P (B),
so C ย P (A) ย P (B).
23. Counterexample: A = {1, 2, 3} and B = {3, 4, 5}, so that AB = {1, 2}. We have {2, 3} ย P (A)P (B), but {2, 3} ย
P (AB).
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.4 x Cardinality
22
24. (a) Suppose f (A) = f (B). Then n ย A iff an = 1 iff bn = 1 iff n ย B.
(b) If a b, then for r ย a r b, we have r ย f (b) but r ย f (a). Thus f (a) z f (b).
25. (a) Given bijections f : A o C and g : B o D, then f ย g : A ย B o C ย D is a bijection.
(b) Follows from the commutative and associative properties of union of sets.
(c) Suppose | A | = n and | B | = ย0 with A ย B = ย. Then A ย B is countable and certainly infinite since B is
infinite. Hence | A ย B | = ย0.
(d) Same as (c).
(e) Answer in book: Let S = ย (0,1). Since ย (0,1) = ย, | S | = ย0 + c. On the other hand, ~ (0,1) ย S
and S ~ S ย , so S ~ and | S | = c.
(f) Let S = (0, 1) ย (1, 2). Then | S | = c c. Since S ย , | S | d c. But ~ (0, 1) ย S, so c d | S |. Thus c c = | S |
= c.
26. (a) Given bijections f : A o C and g : B o D, define h : A u B o C u D by h(x, y) = ( f (x), g (y)). Then h is
bijective.
(b) The commutative and associative properties are straightforward. The distributive law follows from A u (B ย C )
= (A u B) ย (A u C) in Exercise 2.2.10(b).
(c) ย u A = ย, A.
(d) Suppose | A | = n and | B | = ย0. Then | A u B | is countable by Example 8.11(b) and clearly infinite.
(e) Same as (d).
(f) Each x ย (0, 1) can be represented as an infinite decimal. This representation is unique if we agree to select
repeating 0โs instead of 9โs. Define f : (0, 1) u (0, 1) o (0, 1) by f (0. x1 x2 x3 โฆ, 0. y1 y2 y3 โฆ) = 0. x1 y1 x2 y2 x3 y3 โฆ.
Then f is injective, so cc d c. The map g : (0, 1) o (0, 1) u (0, 1) given by g (x) = (1/2, x) is injective, so c d cc.
[Note that f is not surjective since 0.129292929″ has no pre-image.]
Section 2.5 โ Axioms for Set Theory
1. (a) True: comment just prior to the Zermelo-Fraenkel Axioms heading.
(b) False: there is no conflict because b is a subset of x.
2. (a) True: comment after Axiom 9.
(b) True: comment at the beginning of the subsection on the Banach-Tarski paradox.
3. Hint in book: Use Exercise 2.3.32.
Proof: Suppose | T | d | S |. Then an injection g : T o S. Exercise 2.3.32 implies that g has a left inverse f : S o T
such that f q g = iT. Since f has a right inverse, f is surjective.
Conversely, suppose f : S o T is surjective. Then by Exercise 2.3.32, f has a right inverse g : T o S such that
f q g = iT. But then g is injective, so that T is equinumerous with g (T ). But g (T ) ย S, so | T | = | g (T) | d | S |.
4. The set ย has no members and {ย} has oneโnamely, ย. Thus ย z {ย}. Now ย ย {ย} = {ย}, so we also have
ย z ย ย {ย}.
5. Hint in book: Let S = { y : x ย y} and let T = * { y : y ย S}. For any set W show that a set z ย w ย z and x ย z.
From this conclude that T is the โset of all sets.โ
Proof: Suppose S = { y : x ย y} is a set and let T = * { y : y ย S}. Given any set w, let z = x ย {w}. Then x ย z, so
z ย S. But w ย z, so w ย T. Thus T is the โset of all setsโ. Since S is a set, Axiom 4 implies that T is a set. This
contradicts Russellโs paradox.
6. If x ย {x} = x, then {x} ย x. But then x ย x, which contradicts the axiom of regularity.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.5 x Axioms for Set Theory
23
7. Hint in book: Apply the axiom of regularity to the set {x, y}.
Proof: Suppose x ย y and y ย x. Then x ย {x, y} ย y and y ย {x, y} ย x. By the axiom of regularity, z ย {x, y}
ย z ย {x, y} = ย. Since z ย {x, y}, either z = x or z = y. If z = x, then x ย {x, y} = ย, contradicting y ย {x, y} ย x.
Similarly, if z = y, then y ย {x, y} = ย, contradicting x ย {x, y} ย y. Since x ย y and y ย x leads to a contradiction,
we conclude that if x ย y then y ย x.
8. Suppose w ย x, x ย y and y ย w. Then by the axiom of regularity, z in {w, x, y} ย z ย {w, x, y} = ย. Now z = w,
z = x, or z = y, and each possibility leads to a contradiction. For example, if z = w, then w ย {w, x, y} = ย. But
y ย w and y ย {w, x, y}, so y ย w ย {w, x, y}.
9. (a) T = {b, c, d}
(b) Hint in book: Suppose g is such a function and that g( y) = T for some y ย S. Try to determine whether or not
y ย T.
Solution: It is not possible. If y ย T, then y ย g( y), so y ย T. Conversely, if y ย T, then y ย g( y), so y ย T.
10. 1 l S(ย) = ย ย {ย} = {ย} = {0}
2 l S(1) = 1 ย {1} = {0} ย {1} = {0, 1}
3 l S(2) = 2 ย {2} = {0, 1} ย {2} = {0, 1, 2}
4 l S(3) = 3 ย {3} = {0, 1, 2} ย {3} = {0, 1, 2, 3}
5 l S(4) = 4 ย {4} = {0, 1, 2, 3} ย {4} = {0, 1, 2, 3, 4}
11. Hint in the book: The mathematicianโs name was Samโshort for Samantha. Do you see why?
Hereโs why: If the barber were a man, then who would shave the barber? If he shaves himself, then he shouldnโt
have; if he doesnโt, then he should. Thus the barber must be a woman, and the barberโs name is Samโshort for
Samantha.
12. (a) The elements of u D ย {1, 2} SD are functions from {1,2} to S1 ย S2 such that f (1) ย S1 and f (2) ย S2. Thus with
each such function f we can associate the ordered pair ( f (1), f (2)), an element of S1 u S2. On the other hand,
given (a, b) ย S1 u S2, we obtain a corresponding function g defined by g (1) = a and g (2) = b.
(b) This is a difficult exercise. As a preliminary step it is helpful to prove the equivalence of the axiom of choice
and the following: Given any nonempty set x whose elements are nonempty sets, there exists a function f such
that f (a) ย a, a ย x. The details may be found in Hamilton (1982), pages 165 and 167.
13. (a) Let w be a member of the club.
(1) ยบ a committee C ย w ย C.
(3) ยบ a committee D ย C ย D = ย.
(4) ยบ x ย D. Since C ย D = ย, x z w.
(2) ยบ a committee E ย w, x ย E.
Now E z C, since E = C would imply x ย C ย D, a contradiction. Thus w is a member of two distinct
committees, C and E.
(b) Continue on from part (a).
(3) ยบ a committee F ย F ย E = ย.
Is w ย F ? No, because w ย E and E ย F = ย.
Is x ย F ? No, because x ย E and E ย F = ย.
(4) ยบ y ย F ย y z w and y z x.
Now F and C must contain some member in common, since F can only be disjoint from E. If there is not
a fourth member, then we must have y ย F ย C. Likewise, F and D are not disjoint. Their common member
cannot be w or x, since they are not in F. Suppose y ย F ย D. Then we have y ย C ย D, a contradiction. The
only possibility is the existence of a fourth distinct point z with z ย F ย D.
(c) From part (b) we have the club {w, x, y, z} with committees C = {w, y}, D = {x, z}, E = {w, x}, and F = { y, z}.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.5 x Axioms for Set Theory
24
14. (a) (1) ยบ a committee, call it S. (2) ยบ S has at least 3 members, say a, b and c.
(b) Continuing from part (a),
(5) ยบ there exists a member d such that d ย S. Thus a, b, c, and d are distinct.
(4) ยบ there exists a committee T such that a, d ย T. Since d ย S and d ย T, T z S.
(4) ยบ there exists a committee U such that b, d ย U. Since d ย S and d ย U, U z S. If U = T, then a, b ย T.
But a, b ย S and (4) would imply S = T, a contradiction. Thus U z T.
We now have three distinct committees, S, T, and U.
(c) Part (a) implies there exists another member, say y.
(4) ยบ x and y are in a committee, say C.
(5) ยบ there exists a member z such that z ย c.
(4) ยบ there exists a committee D such that y, z ย D. Now D z C, since z ย D and z ย C.
If x ย D, then x, y ย D and (3) ยบ D = C, a contradiction. Thus x ย D.
(d) Let x be a member of the club. Part (c) implies there exists a committee D such that x ย D.
(2) ยบ there exists distinct members a, b, and c in D.
(4) ยบ there exists a committee A such that x, a ย A. Since x ย D, A z D.
(4) ยบ there exists a committee B such that x, b ย B. Since x ย D, B z D.
Since a and b can only share committee D, B z A.
(4) ยบ there exists a committee C such that x, C ย B. Since x ย D, C z D.
Since a and C can only share committee D, C z A.
Since b and C can only share committee D, C z B.
Thus A, B, and C are 3 distinct committees that have x as a member.
(e) Continuing as in part (d), we have 4 distinct members (x, a, b, and c) and 4 distinct committees (A, B, C, and D).
(2) ยบ there exists a member w in A that is distinct from x and a. Now w z b since a and b are both in D and
D z A. And w z c since c and b are both in D and D z C.
(2) ยบ there exists a member y in B that is distinct from x and b. As before, y must be distinct from a and c.
Suppose y = w. Then A and B have w in common. But A and B can only have x in common, so y = w =
x. This contradicts w being distinct from x. Thus y z w.
(2) ยบ there exists a member z in C that is distinct from x and c. As before, z must be distinct from a and b.
Likewise, z is distinct from w and y.
We now have seven distinct people: a, b, c, w, x, y, and z.
(f ) Continuing as in part (e), we have 4 distinct committees with at least the following members:
A = {w, x, a, โฆ}
B = {x, y, b, โฆ}
C = {x, z, c, โฆ}
D = {a, b, c, โฆ}
(4) ยบ there exists a committee E such that {w, y} ย E.
If E = A, then A and B have both x and y in common, a contradiction. Thus E z A.
If E = B, then A and B have both x and y in common, a contradiction. Thus E z B.
If E = C, then A and C have both w and x in common, a contradiction. Thus E z C.
If E = D, then A and D have both w and a in common, a contradiction. Thus E z D.
(4) ยบ there exists a committee F such that {w, z} ย F.
As before, F is distinct from A, B, C, and D.
Suppose F = E. Then E = {w, y, z, โฆ}. In this case,
(4) ยบ there exists a committee G such that {w, b} ย G.
As before, G is distinct from A, B, C, and D.
If G = E, then E and B have both y and b in common, a contradiction. Thus G z E.
(4) ยบ there exists a committee H such that {w, c} ย G.
As before, H is distinct from A, B, C, and D.
If H = E, then E and C have both z and c in common, a contradiction. Thus H z E.
If H = G, then G and D have both b and c in common, a contradiction. Thus H z G.
In this case we have constructed seven distinct committees: A, B, C, D, E, G, and H.
Now suppose F z E. Then we have six distinct committees so far, with E = {w, y โฆ} and F = {w, z, โฆ}.
Copyright ยฉ 2014 Pearson Education, Inc.
Section 2.5 x Axioms for Set Theory
25
(4) ยบ there exists a committee G such that {y, z} ย G.
As before, G is distinct from A, B, C, and D.
If G = E, then E and F have both w and z in common, a contradiction. Thus G z E.
If G = F, then E and F have both w and y in common, a contradiction. Thus G z F.
In this case we have constructed seven distinct committees: A, B, C, D, E, F, and G.
(g) As in part (f ), let the members be a, b, c, w, x, y, and z. The first four committees are
A = {w, x, a}, B = {x, y, b}, C = {x, z, c}, and D = {a, b, c}.
The last three committees may be assigned additional members as follows:
E = {w, y, b}, F = {w, z, c}, and G = {y, z, a}.
15. (a) Let S = (1, f) and T = (2, f). Then S is congruent to T.
(b) Answer in book: Let S be the set of points with polar coordinates (1, n), where n = 0, 1, 2, โฆ . [Recall that
when (r,T ) is the polar coordinate of a point, then r is the distance from the origin and T is the radian measure
of the angle between the positive x-axis and the ray from the origin through the point (r,T ).] Then S is a subset
of the unit circle centered at the origin. The set T = S {(0,1)} is congruent to S, since a counterclockwise
rotation of S through 1 radian will make S coincide with T.
(c) See the article by Blumenthal (1940).
Copyright ยฉ 2014 Pearson Education, Inc.

## Document Preview (14 of 99 Pages)

You are viewing preview pages of the document. Purchase to get full access instantly.

-37%

### Solution Manual For Analysis with an Introduction to Proof, 5th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

24/7 Live Chat

Instant Download

100% Confidential

Store

##### Charlotte Martinez

0 (0 Reviews)

## Best Selling

The World Of Customer Service, 3rd Edition Test Bank

$18.99 ~~$29.99~~Save:$11.00(37%)

Chemistry: Principles And Reactions, 7th Edition Test Bank

$18.99 ~~$29.99~~Save:$11.00(37%)

Test Bank for Hospitality Facilities Management and Design, 4th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

Solution Manual for Designing the User Interface: Strategies for Effective Human-Computer Interaction, 6th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

Data Structures and Other Objects Using C++ 4th Edition Solution Manual

$18.99 ~~$29.99~~Save:$11.00(37%)

2023-2024 ATI Pediatrics Proctored Exam with Answers (139 Solved Questions)

$18.99 ~~$29.99~~Save:$11.00(37%)