# Solution Manual for A Transition to Advanced Mathematics, 7th Edition

Preview Extract
CONTENTS Chapter 1.1 Propositions and Connectives 1 1.2 Conditionals and Biconditionals 6 1.3 Quantifiers 13 1.4 Basic Proof Methods I 17 1.5 Basic Proof Methods II 22 1.6 Proofs Involving Quantifiers 26 1.7 Additional Examples of Proofs 29 Chapter 2.1 Basic Concepts of Set Theory 38 2.2 Set Operations 40 2.3 Extended Set Operations and Indexed Families of Sets 2.4 Mathematical Induction 49 2.5 Equivalent Forms of Induction 59 2.6 Principles of Counting 62 Chapter 3.1 Cartesian Products and Relations 3.2 Equivalence Relations 70 3.3 Partitions 75 3.4 Ordering Relations 78 3.5 Graphs 82 46 67 Chapter 4.1 Functions as Relations 85 4.2 Constructions of Functions 88 4.3 Functions That Are Onto; One-to-One Functions 92 4.4 One-to-One Correspondences and Inverse Functions 95 4.5 Images of Sets 199 4.6 Sequences 102 Chapter 5.1 Equivalent Sets; Finite Sets 105 5.2 Infinite Sets 108 5.3 Countable Sets 111 5.4 The Ordering of Cardinal Numbers 114 5.5 Comparability of Cardinal Numbers and the Axiom of Choice Chapter 6.1 Algebraic Structures 119 6.2 Groups 122 6.3 Subgroups 126 6.4 Operation Preserving Maps 6.5 Rings and Fields 131 128 Chapter 7.1 Completeness of the Real Numbers 133 7.2 The Heine-Borel Theorem 136 7.3 The Bolzano-Weierstrass Theorem 139 7.4 The Bounded Monotone Sequence Theorem 7.5 Equivalents of Completeness 143 140 117 1 Logic and Proofs 1.1 Propositions and Connectives 1. (a) true (e) false (b) false (f) false (c) true (g) false (d) false (h) false 2. (a) Not a proposition (b) False proposition (c) Not a proposition. It would be a proposition if a value for x had been assigned. (d) Not a proposition. It would be a proposition if values for x and y had been assigned. (e) False proposition (f) True proposition (g) False proposition (h) True proposition (i) False proposition (j) Not a proposition. It is neither true nor false. 3. (a) (b) (c) (d) (e) (f) P T F โผP F T Pโง โผ P T F P T F โผP F T Pโจ โผ P T T P T F T F Q T T F F โผQ F F T T Pโง โผ Q F F T F P T F T F Q T T F F โผQ F F T T Qโจ โผ Q T T T T P T F T F Q T T F F โผQ F F T T P โงQ T F F F P T F T F Q T T F F P โงQ T F F F P โง (Qโจ โผ Q) T F T F (P โง Q)โจ โผ Q T F T T โผ (P โง Q) F T T T 1 1 LOGIC AND PROOFS (g) (h) (i) (j) 4. 2 โผQ F F T T F F T T Pโจ โผ Q T F T T T F T T (P โจ โผ Q) โง R T F T T F F F F P T F T F T F T F Q T T F F T T F F R T T T T F F F F P T F T F Q T T F F โผP F T F T โผQ F F T T โผ Pโง โผ Q F F F T P T F T F T F T F Q T T F F T T F F R T T T T F F F F QโจR T T T T T T F F P โง (Q โจ R) T F T F T F F F P T F T F T F T F Q T T F F T T F F R T T T T F F F F P โงQ T F F F T F F F P โงR T F T F F F F F (a) false (e) false (i) true (b) true (f) false (j) true (P โง Q) โจ (P โง R) T F T F T F F F (c) true (g) false (k) false (d) true (h) false (1) false 5. (a) No solution. (b) P Q P โจQ QโจP T T T T F T T T T F T T F F F F Since the third and fourth columns are the same, the propositions are equivalent. 1 LOGIC AND PROOFS (c) (d) (e) (f) (g) 3 P Q P โงQ QโงP T T T T F T F F T F F F F F F F Since the third and fourth columns are the same, the propositions are equivalent. P Q R Q โจ R P โจ (Q โจ R) P โจ Q (P โจ Q) โจ R T T T T T T T F T T T T T T T F T T T T T F F T T T F T T T F T T T T F T F T T T T T F F F T T T F F F F F F F Since the ๏ฌfth and seventh columns are the same, the propositions are equivalent. P Q R Q โง R P โง (Q โง R) P โง Q (P โง Q) โง R T T T T T T T F T T T F F F T F T F F F F F F T F F F F T T F F F T F F T F F F F F T F F F F F F F F F F F F F Since the ๏ฌfth and seventh columns are the same, the propositions are equivalent. P Q R Q โจ R P โง (Q โจ R) P โง Q P โง R (P โง Q) โจ (P โง R) T T T T T T T T F T T T F F F F T F T T T F T T F F T T F F F F T T F T T T F T F T F T F F F F T F F F F F F F F F F F F F F F Since the ๏ฌfth and eighth columns are the same, the propositions are equivalent. P T F T F T F T F Q T T F F T T F F R T T T T F F F F QโงR T T F F F F F F P โจ (Q โง R) T T T F T F T F P โจQ T T T F T T T F P โจR T T T T T F T F (P โจ Q) โง (P โจ R) T T T F T F T F 1 LOGIC AND PROOFS 4 Since the ๏ฌfth and eighth columns are the same, the propositions are equivalent. (h) No solution. (i) P Q P โจ Q โผ (P โจ Q) โผ P โผ Q โผ P โง โผ Q T T T F F F F F T T F T F F T F T F F T F F F F T T T T Since the fourth and eighth columns are the same, the propositions are equivalent. 6. (a) equivalent (c) equivalent (e) equivalent (g) not equivalent (b) equivalent (d) equivalent (f) not equivalent (h) not equivalent 7. (a) โผ P , true (c) P Q, true (b) P โง Q, true (d) P โจ Q โจ R, true 8. (a) Since P is equivalent to Q, P has the same truth table as Q. Therefore, Q has the same truth table as P , so Q is equivalent to P . (b) Since P is equivalent to Q, P and Q have the same truth table. Since Q is equivalent to R, Q and R have the same truth table. Thus, P and R have the same truth table so P is equivalent to R. (c) Since P is equivalent to Q, P and Q have the same truth table. That is, the truth table for P has value true on exactly the same lines that the truth table for Q has value true. Therefore the truth table for โผ Q has value false on exactly the same lines that the truth table for โผ P has the value false. Thus โผ Q and โผ P have the same truth table. 9. (a) (P โง Q) โจ (โผ P โง โผ Q) is neither. P T F T F Q T T F F โผP F T F T โผQ F F T T P โงQ T F F F โผ Pโง โผ Q F F F T (P โง Q) โจ (โผ P โง โผ Q) T F F T (b) โผ (P โง โผ P ) is a tautology. P T F โผP F T Pโง โผ P F F โผ (P โง โผ P ) T T (c) (P โง Q) โจ (โผ P โจ โผ Q) is a tautology. P T F T F Q T T F F โผP F T F T โผQ F F T T P โงQ T F F F โผ Pโจ โผ Q F T T T (P โง Q) โจ (โผ P โจ โผ Q) T T T T (d) (A โง B) โจ (Aโง โผ B) โจ (โผ A โง B) โจ (โผ Aโง โผ B) is a tautology. 1 LOGIC AND PROOFS A T F T F B T T F F โผA F T F T โผB F F T T 5 AโงB T F F F Aโง โผ B F F T F โผAโงB F T F F โผ Aโง โผ B F F F T (A โง B) โจ (Aโง โผ B)โจ (โผ A โง B) โจ (โผ Aโง โผ B) T T T T (e) (Qโง โผ P )โง โผ (P โง R) is neither. P T F T F T F T F Q T T F F T T F F R T T T T F F F F โผP F T F T F T F T Qโง โผ P F T F F F T F F P โงR T F T F F F F F โผ (P โง R) F T F T T T T T (Qโง โผ P )โง โผ (P โง R) F T F F F T F F (f) P โจ [(โผ Q โง P ) โง (R โจ Q)] is neither. P T F T F T F T F 10. Q T T F F T T F F R T T T T F F F F โผQ F F T T F F T T โผQโงP F F T F F F T F (a) contradiction (c) tautology RโจQ T T T T T T F F [(โผ Q โง P ) โง (R โจ Q)] F F T F F F F F P โจ [(โผ Q โง P ) โง (R โจ Q)] T F T F T F T F (b) tautology (d) tautology 11. (a) x is not a positive integer. (b) Cleveland will lose the ๏ฌrst game and the second game. Or, Cleveland will lose both games. (c) 5 < 3 (d) 641,371 is not composite. Or 641,371 is prime. (e) Roses are not red or violets are not blue. (f) T is bounded and T is not compact. (g) M is not odd or M is not one-to-one. (h) The function.f does not have a positive ๏ฌrst derivative at x or does not have a positive second derivative at x. (i) The function g does not have a relative maximum at x = 2 (deleted comma) and does not have a relative maximum at x = 4, or else g does not have a relative minimum at x = 3. (j) z 4) โจ (n > 10) (i) (x is Cauchy) โ (x is convergent) (j) (limxโx0 f (x) = f (x0 )) โ (f is continuous at x0 ) (k) [(f is di๏ฌerentiable at x0 ) โง (f is strictly increasing at x0 )] โ (f (x0 )) 11. (a) Let S be โI go to the storeโ and R be โIt rains.โ The preferred translation: is โผ S โ R (or, equivalently, โผ R โ S). This could be read as โIf it doesnโt rain, then I go to the store.โ The speaker might mean โI go to the store if and only if it doesnโt rain (S โโผ R) or possibly โIf it rains, then I donโt go to the storeโ (R โโผ S). (b) There are three nonequivalent ways to translate the sentence, using the symbols D: โThe Dolphins make the playo๏ฌsโ and B: โThe Bears win all the rest of their games.โ The ๏ฌrst translation is preferred, but the speaker may have intended any of the three. โผ B โโผ D or, equivalently, D โ B โผ D โโผ B or, equivalently, B โ D โผ B โโผ D or, equivalently, B โ D (c) Let G be โYou can go to the gameโ and H be โYou do your homework ๏ฌrst.โ It is most likely that a student and parent both interpret this statement as a biconditional, G โ H. (d) Let W be โYou win the lotteryโ and T be โYou buy a ticket.โ Of the three common interpretations for the word โunless,โ only the form โผ T โโผ W (or, equivalently, W โ T ) makes sense here. 12. (a) (b) P Q R P โจ Q (P โจ Q) โ R โผ P โง โผ Q โผ R โ (โผ P โง โผ Q) T T T T T F T F T T T T F T T F T T T F T F F T F T T T T T F T F F F F T F T F F F T F F T F F F F F F F T T T Since the ๏ฌfth and seventh columns are the same, (P โจ Q) โ R and โผ R โ (โผ P โง โผ Q) are equivalent. P T F T F T F T F Q T T F F T T F F R T T T T F F F F P โงQ T F F F T F F F (P โง Q) โ R T T T T F T T T โผQ F F T T F F T T โผR F F F F T T T T Pโง โผ R F F F F T F T F (P โง โผ R) โโผ Q T T T T F T T T Since the ๏ฌfth and ninth columns are the same, the propositions (P โง Q) โ R and (P โง โผ R) โโผ Q are equivalent. 1 LOGIC AND PROOFS (c) (d) (e) (f) 12 P Q R Q โง R P โ (Q โง R) โผ Qโจ โผ R (โผ Qโจ โผ R) โโผ P T T T T T F T F T T T T F T T F T F F T F F F T F T T T T T F F F T F F T F F T T T T F F F F T F F F F F T T T Since the ๏ฌfth and seventh columns are the same, the propositions P โ (Q โง R) and (โผ Qโจ โผ R) โโผ P are equivalent. P Q R Q โจ R P โ (Q โจ R) P โง โผ R (P โง โผ R) โ Q T T T T T F T F T T T T F T T F T T T F T F F T T T F T T T F T T T T F T F T T F T T F F F F T F F F F F T F T Since the ๏ฌfth and seventh columns are the same, the propositions P โ (Q โจ R) and (P โง โผ R) โ Q are equivalent. P Q R P โ Q (P โ Q) โ R P โง โผ Q (P โง โผ Q) โจ R T T T T T F T F T T T T F T T F T F T T T F F T T T F T T T F T F F F F T F T F F F T F F F T T T F F F T F F F Since the ๏ฌfth and seventh columns are the same, the propositions (P โ Q) โ R and (P โง โผ Q) โจ R are equivalent. P Q P โ Q โผ P โจ Q โผ Q โจ P (โผ P โจ Q) โง (โผ Q โจ P ) T T T T T T F T F T F F T F F F T F F F T T T T Since the third and sixth columns are the same, the propositions P โ Q and (โผ P โจ Q) โง (โผ Q โจ P ) are equivalent. 13. (a) If 6 is an even integer, then 7 is an odd integer. (b) If 6 is an odd integer, then 7 is an odd integer. (c) This is not possible. (d) If 6 is an even integer, then 7 is an even integer. (Any true conditional statement will work here.) 14. (a) If 7 is an odd integer, then 6 is an odd integer. (b) This is not possible. 1 LOGIC AND PROOFS 13 (c) This is not possible. (d) If 7 is an odd integer, then 6 is an odd integer. (Any false conditional statement will work here.) 15. (a) Converse: If f (x0 ) = 0, then f has a relative minimum at x0 and is di๏ฌerentiable at x0 . False: f (x) = x3 has ๏ฌrst derivative 0 but no minimum at x0 = 0. Contrapositive: If f (x0 ) = 0, then f either has no relative minimum at x0 or is not di๏ฌerentiable at x0 . True. (b) Converse: If n = 2 or n is odd, then n is prime. False: 9 is odd but not prime. Contrapositive: If n is even and not equal to 2, then n is not prime. True. (c) Converse: If x is irrational, then x is real and not rational. True Contrapositive: If x is not irrational, then x is not real or x is rational. True (d) Converse: If |x| = 1, then x = 1 or x = โ1. True. Contrapositive: If |x| = 1, then x = 1 and x = โ1. True. 16. (a) tautology (d) neither (g) contradiction (j) neither 17. (a) (b) tautology (e) tautology (h) tautology (k) tautology (c) contradiction (f) neither (i) contradiction (l) neither P Q P โ Q โผ P โผ Q โผ P โโผ Q T T T F F T F T T T F F T F F F T T F F T T T T Comparison of the third and sixth columns of the truth table shows that P โ Q and โผ P โโผ Q are not equivalent. (b) We see from the truth table in part (a) that both propositions P โ Q and โผ P โโผ Q are true only when P and Q have the same truth value. (c) The converse of P โ Q is Q โ P . The contrapositive of the inverse of P โ Q is โผโผ Q โโผโผ P , so the converse and the contrapositive of the inverse are equivalent. The inverse of the contrapositive of P โ Q is also โผโผ Q โโผโผ P , so it too is equivalent to the converse. 1.3 Quanti๏ฌers 1. (a) โผ (โx)(x is preciousโ x is beautiful) or (โ x)(x is precious and x is not beautiful) (b) (โx)(x is preciousโ x is not beautiful) (c) (โ x)(x is isoscelesโงx is a right triangle) (d) (โx)(x is a right triangleโ x is not isosceles) or โผ (โ x)(x is a right triangleโงx is isosceles) (e) (โx)(x is honest)โจ โผ (โ x)(x is honest) (f) (โ x)(x is honest) โง (โ x)(x is not honest) (g) (โx)(x = 0 โ (x > 0 โจ x โ4 โจ x โ4 โจ x < 6)

## Document Preview (15 of 145 Pages)

User generated content is uploaded by users for the purposes of learning and should be used following SchloarOn's honor code & terms of service.
You are viewing preview pages of the document. Purchase to get full access instantly.
-37%

### Solution Manual for A Transition to Advanced Mathematics, 7th Edition

\$18.99 Save:\$11.00(37%)