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

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: * BB B [1, 2], (c) * B = [2, f), B = {2}; BB 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.