Solution Manual for Mathematical Proofs: A Transition to Advanced Mathematics, 4th Edition

Preview (16 of 224 Pages)

100%

Purchase to unlock

Loading page image...

Solutions ManualMathematical ProofsA Transition toAdvanced MathematicsFourth EditionGary ChartrandWestern Michigan UniversityAlbert D. PolimeniState University of New York at FredoniaPing ZhangWestern Michigan University

Loading page image...

iiiTable of Contents0.Communicating Mathematics0.1Learning Mathematics0.2What Others Have Said About Writing0.3Mathematical Writing0.4Using Symbols0.5Writing Mathematical Expressions0.6Common Words and Phrases in Mathematics0.7Some Closing Comments About Writing1.Sets1.1Describing a Set1.2Subsets1.3Set Operations1.4Indexed Collections of Sets1.5Partitions of Sets1.6Cartesian Products of SetsExercises for Chapter 12.Logic2.1Statements2.2Negations2.3Disjunctions and Conjunctions2.4Implications2.5More on Implications2.6Biconditionals2.7Tautologies and Contradictions2.8Logical Equivalence2.9Some Fundamental Properties of Logical Equivalence2.10Quantified Statements2.11CharacterizationsExercises for Chapter 23.Direct Proof and Proof by Contrapositive3.1Trivial and Vacuous Proofs3.2Direct Proofs3.3Proof by Contrapositive3.4Proof by Cases3.5Proof EvaluationsExercises for Chapter 34.More on Direct Proof and Proof by Contrapositive4.1Proofs Involving Divisibility of Integers4.2Proofs Involving Congruence of Integers4.3Proofs Involving Real Numbers4.4Proofs Involving Sets4.5Fundamental Properties of Set Operations4.6Proofs Involving Cartesian Products of SetsExercises for Chapter 45.Existence and Proof by Contradiction5.1Counterexamples5.2Proof by Contradiction

Loading page image...

iv5.3A Review of Three Proof Techniques5.4Existence Proofs5.5Disproving Existence StatementsExercises for Chapter 56.Mathematical Induction6.1The Principle of Mathematical Induction6.2A More General Principle of Mathematical Induction6.3The Strong Principle of Mathematical Induction6.4Proof by Minimum CounterexampleExercises for Chapter 67.Reviewing Proof Techniques7.1Reviewing Direct Proof and Proof by Contrapositive7.2Reviewing Proof by Contradiction and Existence Proofs7.3Reviewing Induction Proofs7.4Reviewing Evaluations of Proposed ProofsExercises for Chapter 78.Prove or Disprove8.1Conjectures in Mathematics8.2Revisiting Quantified Statements8.3Testing StatementsExercises for Chapter 89.Equivalence Relations9.1Relations9.2Properties of Relations9.3Equivalence Relations9.4Properties of Equivalence Classes9.5Congruence Modulon9.6The Integers ModulonExercises for Chapter 910.Functions10.1The Definition of Function10.2One-to-one and Onto Functions10.3Bijective Functions10.4Composition of Functions10.5Inverse FunctionsExercises for Chapter 1011.Cardinalities of Sets11.1Numerically Equivalent Sets11.2Denumerable Sets11.3Uncountable Sets11.4Comparing Cardinalities of Sets11.5The Schr¨oder-Bernstein TheoremExercises for Chapter 1112.Proofs in Number Theory12.1Divisibility Properties of Integers12.2The Division Algorithm12.3Greatest Common Divisors

Loading page image...

v12.4The Euclidean Algorithm12.5Relatively Prime Integers12.6The Fundamental Theorem of Arithmetic12.7Concepts Involving Sums of DivisorsExercises for Chapter 1213.Proofs in Combinatorics13.1The Multiplication and Addition Principles13.2The Principle of Inclusion-Exclusion13.3The Pigeonhole Principle13.4Permutations and Combinations13.5The Pascal Triangle13.6The Binomial Theorem13.7Permutations and Combinations with RepetitionExercises for Chapter 1314.Proofs in Calculus14.1Limits of Sequences14.2Infinite Series14.3Limits of Functions14.4Fundamental Properties of Limits of Functions14.5Continuity14.6DifferentiabilityExercises for Chapter 1415.Proofs in Group Theory15.1Binary Operations15.2Groups15.3Permutation Groups15.4Fundamental Properties of Groups15.5Subgroups15.6Isomorphic GroupsExercises for Chapter 15

Loading page image...

Exercises for Chapter 1Exercises for Section 1.1: Describing a Set1.1 Only (d) and (e) are sets.1.2(a)A={1,2,3}={x∈S:x >0}.(b)B={0,1,2,3}={x∈S:x≥0}.(c)C={−2,−1}={x∈S:x <0}.(d)D={x∈S:|x| ≥2}.1.3 (a)|A|= 5.(b)|B|= 11.(c)|C|= 51. (d)|D|= 2.(e)|E|= 1.(f)|F|= 2.1.4(a)A={n∈Z:−4< n≤4}={−3,−2, . . . ,4}.(b)B={n∈Z:n2<5}={−2,−1,0,1,2}.(c)C={n∈N:n3<100}={1,2,3,4}.(d)D={x∈R:x2−x= 0}={0,1}.(e)E={x∈R:x2+ 1 = 0}={}=∅.1.5(a)A={−1,−2,−3, . . .}={x∈Z:x≤ −1}.(b)B={−3,−2, . . . ,3}={x∈Z:−3≤x≤3}={x∈Z:|x| ≤3}.(c)C={−2,−1,1,2}={x∈Z:−2≤x≤2, x= 0}={x∈Z:0<|x| ≤2}.1.6(a)A={2x+ 1 :x∈Z}={· · ·,−5,−3,−1,1,3,5,· · ·}.(b)B={4n:n∈Z}={· · ·,−8,−4,0,4,8,· · ·}.(c)C={3q+ 1 :q∈Z}={· · ·,−5,−2,1,4,7,· · ·}.1.7(a)A={· · ·,−4,−1,2,5,8,· · ·}={3x+ 2 :x∈Z}.(b)B={· · ·,−10,−5,0,5,10,· · ·}={5x:x∈Z}.(c)C={1,8,27,64,125,· · ·}={x3:x∈N}.1.8(a)A={n∈Z: 2≤ |n|<4}={−3,−2,2,3}.(b) 5/2, 7/2, 4.(c)C={x∈R:x2−(2 +√2)x+ 2√2 = 0}={x∈R: (x−2)(x− √2) = 0}={2,√2}.(d)D={x∈Q:x2−(2 +√2)x+ 2√2 = 0}={2}.(e)|A|= 4,|C|= 2,|D|= 1.1.9A={2,3,5,7,8,10,13}.B={x∈A:x=y+z,wherey, z∈A}={5,7,8,10,13}.C={r∈B:r+s∈Bfor somes∈B}={5,8}.1

Loading page image...

2Exercises for Section 1.2: Subsets1.10(a)A={1,2},B={1,2},C={1,2,3}.(b)A={1},B={{1},2}.C={{{1},2},1}.(c)A={1},B={{1},2},C={1,2}.1.11 Letr= min(c−a, b−c) and letI= (c−r, c+r). ThenIis centered atcandI⊆(a, b).1.12A=B=D=E={−1,0,1}andC={0,1}.1.13 See Figure 1.627UB85431A.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Figure 1: Answer for Exercise 1.131.14(a)P(A) ={∅,{1},{2},{1,2}};|P(A)|= 4.(b)P(A) ={∅,{∅},{1},{{a}},{∅,1},{∅,{a}},{1,{a}},{∅,1,{a}}};|P(A)|= 8.1.15P(A) ={∅,{0},{{0}}, A}.1.16P({1}) ={∅,{1}},P(P({1})) ={∅,{∅},{{1}},{∅,{1}}};|P(P({1}))|= 4.1.17P(A) ={∅,{0},{∅},{{∅}},{0,∅},{0,{∅}},{∅,{∅}}, A};|P(A)|= 8.1.18P({0}) ={∅,{0}}.A={x:x= 0 orx∈ P({0})}={0,∅,{0}}.P(A) ={∅,{0},{∅},{{0}},{0,∅},{0,{0}},{∅,{0}}, A}.1.19(a)S={∅,{1}}.(b)S={1}.(c)S={∅,{1},{2},{3},{4,5}}.(d)S={1,2,3,4,5}.1.20(a) False. For example, forA={1,{1}}, both 1∈Aand{1} ∈A.(b) BecauseP(B) is the set of all subsets of the setBandA⊂ P(B) with|A|= 2, it follows thatAis a proper subset ofP(B) consisting of exactly two elements ofP(B). ThusP(B) containsat least one element that is not inA. Suppose that|B|=n. Then|P(B)|= 2n. Since 2n>2,it follows thatn≥2 and|P(B)|= 2n≥4. BecauseP(B)⊂C, it is impossible that|C|= 4.Suppose thatA={{1},{2}},B={1,2}andC=P(B)∪ {3}. ThenA⊂ P(B)⊂C, where|A|= 2 and|C|= 5.

Loading page image...

3(c) No. ForA=∅andB={1},|P(A)|= 1 and|P(B)|= 2.(d) Yes. There are only three distinct subsets of{1,2,3}with two elements.1.21B={1,4,5}.Exercises for Section 1.3: Set Operations1.22(a)A∪B={1,3,5,9,13,15}.(b)A∩B={9}.(c)A−B={1,5,13}.(d)B−A={3,15}.(e)A={3,7,11,15}.(f)A∩B={1,5,13}.1.23 LetA={1,2, . . . ,6}andB={4,5, . . . ,9}.ThenA−B={1,2,3},B−A={7,8,9}andA∩B={4,5,6}. Thus|A−B|=|A∩B|=|B−A|= 3. See Figure 2.B978654321A ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Figure 2: Answer for Exercise 1.231.24 LetA={1,2},B={1,3}andC={2,3}. ThenB=CbutB−A=C−A={3}.1.25(a)A={1},B={{1}},C={1,2}.(b)A={{1},1},B={1},C={1,2}.(c)A={1},B={{1}},C={{1},2}.1.26 (a) and (b) are the same, as are (c) and (d).1.27 LetU={1,2, . . . ,8}be a universal set,A={1,2,3,4}andB={3,4,5,6}. ThenA−B={1,2},B−A={5,6},A∩B={3,4}andA∪B={7,8}. See Figure 3.2AB786341U5..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Figure 3: Answer for Exercise 1.27

Loading page image...

4.................................................................................................................................................................................................................................................................................................................................................................................................ACBACB(C−B)∪AC∩(A−B)(a)(b)...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Figure 4: Answers for Exercise 1.281.28 See Figures 4(a) and 4(b).1.29(a) The sets∅and{∅}are elements ofA.(b)|A|= 3.(c) All of∅,{∅}and{∅,{∅}}are subsets ofA.(d)∅ ∩A=∅.(e){∅} ∩A={∅}.(f){∅,{∅}} ∩A={∅,{∅}}.(g)∅ ∪A=A.(h){∅} ∪A=A.(i){∅,{∅}} ∪A=A.1.30(a)A={x∈R:|x−1| ≤2}={x∈R:−2≤x−1≤2}={x∈R:−1≤x≤3}= [−1,3]B={x∈R:|x| ≥1}={x∈R:x≥1 orx≤ −1}= (−∞,−1]∪[1,∞)C={x∈R:|x+ 2| ≤3}={x∈R:−3≤x+ 2≤3}={x∈R:−5≤x≤1}= [−5,1](b)A∪B= (−∞,∞) =R,A∩B={−1} ∪[1,3],B∩C= [−5,−1]∪ {1},B−C= (−∞,−5)∪(1,∞).1.31A={1,2},B={2},C={1,2,3},D={2,3}.1.32A={1,2,3},B={1,2,4},C={1,3,4},D={2,3,4}.1.33A={1},B={2}.1.34A={1,2},B={2,3}.1.35 LetU={1,2, . . . ,8},A={1,2,3,5},B={1,2,4,6}andC={1,3,4,7}. See Figure 5.Exercises for Section 1.4: Indexed Collections of Sets1.36⋃α∈ASα=S1∪S3∪S4= [0,3]∪[2,5]∪[3,6] = [0,6].⋂α∈ASα=S1∩S3∩S4={3}.

Loading page image...

5UB43127685CA........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Figure 5: Answer for Exercise 1.351.37⋃X∈SX=A∪B∪C={0,1,2, . . . ,5}and⋂X∈SX=A∩B∩C={2}.1.38(a)⋃α∈SAα=A1∪A2∪A4={1} ∪ {4} ∪ {16}={1,4,16}.⋂α∈SAα=A1∩A2∩A4=∅.(b)⋃α∈SBα=B1∪B2∪B4= [0,2]∪[1,3]∪[3,5] = [0,5].⋂α∈SBα=B1∩B2∩B4=∅.(c)⋃α∈SCα=C1∪C2∪C4= (1,∞)∪(2,∞)∪(4,∞) = (1,∞).⋂α∈SCα=C1∩C2∩C4= (4,∞).1.39 Since|A|= 26 and|Aα|= 3 for eachα∈A, we need to have at least nine sets of cardinality 3for their union to beA; that is, in order for⋃α∈SAα=A, we must have|S| ≥9. However, if weletS={a, d, g, j, m, p, s, v, y}, then⋃α∈SAα=A. Hence the smallest cardinality of a setSwith⋃α∈SAα=Ais 9.1.40(a)⋃5i=1A2i=A2∪A4∪A6∪A8∪A10={1,3} ∪ {3,5} ∪ {5,7} ∪ {7,9} ∪ {9,11}={1,3,5, . . . ,11}.(b)⋃5i=1(Ai∩Ai+1) =⋃5i=1({i−1, i+ 1} ∩ {i, i+ 2}) =⋃5i=1∅=∅.(c)⋃5i=1(A2i−1∩A2i+1) =⋃5i=1({2i−2,2i} ∩ {2i,2i+ 2}) =⋃5i=1{2i}={2,4,6,8,10}.1.41(a){An}n∈N, whereAn={x∈R: 0≤x≤1/n}= [0,1/n].(b){An}n∈N, whereAn={a∈Z:|a| ≤n}={−n,−(n−1), . . . ,(n−1), n}.1.42(a)An=[1,2 +1n),⋃n∈NAn= [1,3) and⋂n∈NAn= [1,2].(b)An=(−2n−1n,2n),⋃n∈NAn= (−2,∞) and⋂n∈NAn= (−1,2).1.43⋃r∈R+Ar=⋃r∈R+(−r, r) =R;⋂r∈R+Ar=⋂r∈R+(−r, r) ={0}.1.44 ForI={2,8},|⋃i∈IAi|= 8. Observe that there is no setIsuch that|⋃i∈IAi|= 10, for in thiscase, we must have either two 5-element subsets ofAor two 3-element subsets ofAand a 4-elementsubset ofA. In each case, not every two subsets are disjoint. Furthermore, there is no setIsuchthat|⋃i∈IAi|= 9, for in this case, one must either have a 5-element subset ofAand a 4-elementsubset ofA(which are not disjoint) or three 3-element subsets ofA.No 3-element subset ofAcontains 1 and only one such subset contains 2. Thus 4,5∈Ibut there is no third element forI.

Loading page image...

61.45⋃n∈NAn=⋃n∈N(−1n,2−1n) = (−1,2);⋂n∈NAn=⋂n∈N(−1n,2−1n) = [0,1].1.46 (a)∞⋃n=1(−1n ,1n)= (−1,1);∞⋂n=1(−1n ,1n)={0}(b)∞⋃n=1[n−1n,n+ 1n]= [0,2];∞⋂n=1[n−1n,n+ 1n]={1}1.47 (a)∞⋃n=1{sin2nπ2+ cos2nπ2}=∞⋂n=1{sin2nπ2+ cos2nπ2}={1}(b)∞⋃n=1{sinnπ2+ cosnπ2}={−1,1};∞⋂n=1{sinnπ2+ cosnπ2}=∅Exercises for Section 1.5: Partitions of Sets1.48(a)S1is a partition ofA.(b)S2is not a partition ofAbecausegbelongs to no element ofS2.(c)S3is a partition ofA.(d)S4is not a partition ofAbecause∅ ∈S4.(e)S5is not a partition ofAbecausebbelongs to two elements ofS5.1.49(a)S1is not a partition ofAsince 4 belongs to no element ofS1.(b)S2is a partition ofA.(c)S3is not a partition ofAbecause 2 belongs to two elements ofS3.(d)S4is not a partition ofAsinceS4is not a set of subsets ofA.1.50S={{1,2,3},{4,5},{6}};|S|= 3.1.51A={1,2,3,4}.S1={{1},{2},{3,4}}andS2={{1,2},{3},{4}}.1.52 LetS={A1, A2, A3}, whereA1={x∈N:x >5},A2={x∈N:x <5}andA3={5}.1.53 LetS={A1, A2, A3}, whereA1={x∈Q:x >1},A2={x∈Q:x <1}andA3={1}.1.54A={1,2,3,4},S1={{1},{2},{3,4}}andS2={{{1},{2}},{{3,4}}}.1.55 LetS={A1, A2, A3, A4}, whereA1={x∈Z:xis odd andxis positive},A2={x∈Z:xis odd andxis negative},A3={x∈Z:xis even andxis nonnegative},A4={x∈Z:xis even andxis negative}.

Loading page image...

71.56 LetS={{1},{2},{3,4,5,6},{7,8,9,10},{11,12}}andT={{1},{2},{3,4,5,6},{7,8,9,10}}.1.57|P1|= 2,|P2|= 3,|P3|= 5,|P4|= 8,|P5|= 13,|P6|= 21.1.58(a) Suppose that a collectionSof subsets ofAsatisfies Definition 1.Then every subset isnonempty.Every element ofAbelongs to a subset inS.If some elementa∈Abelongedto more than one subset, then the subsets inSwould not be pairwise disjoint. So the collec-tion satisfies Definition 2.(b) Suppose that a collectionSof subsets ofAsatisfies Definition 2. Then every subset is nonemptyand (1) in Definition 3 is satisfied. If two subsetsA1andA2inSwere neither equal nor disjoint,thenA1=A2and there is an elementa∈Asuch thata∈A1∩A2, which would not satisfyDefinition 2.So condition (2) in Definition 3 is satisfied.Since every element ofAbelongsto a (unique) subset inS, condition (3) in Definition 3 is satisfied. Thus Definition 3 itself issatisfied.(c) Suppose that a collectionSof subsets ofAsatisfies Definition 3.By condition (1) in Defi-nition 3, every subset is nonempty.By condition (2), the subsets are pairwise disjoint.Bycondition (3), every element ofAbelongs to a subset inS. So Definition 1 is satisfied.Exercises for Section 1.6: Cartesian Products of Sets1.59A×B={(x, x),(x, y),(y, x),(y, y),(z, x),(z, y)}.1.60A×A={(1, 1), (1,{1}), (1,{{1}}), ({1}, 1), ({1},{1}), ({1},{{1}}), ({{1}}, 1), ({{1}},{1}),({{1}},{{1}})}.1.61P(A) ={∅,{a},{b}, A},A× P(A) ={(a,∅),(a,{a}),(a,{b}),(a, A),(b,∅),(b,{a}),(b,{b}),(b, A)}.1.62P(A) ={∅,{∅},{{∅}}, A},A× P(A) ={(∅,∅),(∅,{∅}),(∅,{{∅}}),(∅, A),({∅},∅),({∅},{∅}),({∅},{{∅}}),({∅}, A)}.1.63P(A) ={∅,{1},{2}, A},P(B) ={∅, B},A×B={(1,∅),(2,∅)},P(A)× P(B) ={(∅,∅),(∅, B),({1},∅),({1}, B),({2},∅),({2}, B),(A,∅),(A, B)}.1.64{(x, y) :x2+y2= 4}, which is a circle centered at (0, 0) with radius 2.1.65S={(3,0),(2,1),(2,−1),(1,2),(1,−2),(0,3),(0,−3),(−3,0),(−2,1),(−2,−1),(−1,2),(−1,−2)}.See Figure 6.1.66A×B={(1,1),(2,1)},P(A×B) ={∅,{(1,1)},{(2,1)}, A×B}.1.67A={x∈R:|x−1| ≤2}={x∈R:−1≤x≤3}= [−1,3],B={y∈R:|y−4| ≤2}={y∈R: 2≤y≤6}= [2,6],A×B= [−1,3]×[2,6], which is the set of all points on and within the square bounded byx=−1,x= 3,y= 2 andy= 6.

Loading page image...

8(0,−3)(0,3)(3,0)(2,−1)(−1,2)(1,2)(−2,1)(2,1)(−3,0)(−2,−1)(−1,−2)(1,−2)...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Figure 6: Answer for Exercise 1.651.68A={a∈R:|a| ≤1}={a∈R:−1≤a≤1}= [−1,1],B={b∈R:|b|= 1}={−1,1},A×Bis the set of all points (x, y) on the linesy= 1 ory=−1 withx∈[−1,1], whileB×Ais theset of all points (x, y) on the linesx= 1 orx=−1 withy∈[−1,1]. Therefore, (A×B)∪(B×A)is the set of all points lying on (but not within) the square bounded byx= 1,x=−1,y= 1 andy=−1.1.69 (a)–(b)(A×B)∩(B×A) = (A∩B)×(B∩A) ={(2,2),(2,3),(3,2),(3,3)}.1.70 ForA={1,2},B={1,2,3},C={1,2,3,4}andD={2,3}, it follows that((A×B)∪(C×D))−(D×D) =R.1.71 Since⋃3i=1(Ai×Ai) ={(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3),(3,4),(4,3),(4,4)},it followsthat∣∣∪3i=1(Ai×Ai)∣∣= 10.1.72 The set{A×A, A×B, B×A, B×B}is a partition ofS×S.Chapter 1 Supplemental Exercises1.73(a)A={4k+ 3 :k∈Z}={. . . ,−5,−1,3,7,11, . . .}.(b)B={5k−1 :k∈Z}={. . . ,−6,−1,4,9,14, . . .}.1.74(a)A={x∈S:|x| ≥1}={x∈S:x= 0}.(b)B={x∈S:x≤0}.(c)C={x∈S:−5≤x≤7}={x∈S:|x−1| ≤6}.(d)D={x∈S:x= 5}.

Loading page image...

91.75 (a){0,2,−2}(b){ }(c){3,4,5}(d){1,2,3}(e){−2,2}(f){ }(g){−3,−2,−1,1,2,3}.1.76 (a)|A|= 6(b)|B|= 0(c)|C|= 3(d)|D|= 0(e)|E|= 10(f)|F|= 20.1.77A×B={(−1, x),(−1, y),(0, x),(0, y),(1, x),(1, y)}.1.78(a)(A∪B)−(B∩C) ={1,2,3} − {3}={1,2}.(b)A={3}.(c)B∪C={1,2,3}=∅.(d)A×B={(1,2),(1,3),(2,2),(2,3)}.1.79 LetS={{1},{2},{3,4}, A}and letB={3,4}.1.80P(A) ={∅,{1}},P(C) ={∅,{1},{2}, C}. LetB={∅,{1},{2}}.1.81 LetA={∅}andB=P(A) ={∅,{∅}}.1.82 OnlyB=C=∅andD=E.1.83U={1,2,3,5,7,8,9},A={1,2,5,7}andB={5,7,8}.1.84(a)Aris the set of all points in the plane lying on the circlex2+y2=r2.⋃r∈IAr=R×R(the plane) and⋂r∈IAr=∅.(b)Bris the set of all points lying on and inside the circlex2+y2=r2.⋃r∈IBr=R×Rand⋂r∈IBr={(0,0)}.(c)Cris the set of all points lying outside the circlex2+y2=r2.⋃r∈ICr=R×R− {(0,0)}and⋂r∈ICr=∅.1.85 LetA1={1,2,3,4},A2={3,5,6},A3={1,3},A4={1,2,4,5,6}. Then|A1∩A2|=|A2∩A3|=|A3∩A4|= 1,|A1∩A3|=|A2∩A4|= 2 and|A1∩A4|= 3.1.86(a)(i) Give an example of five setsAi(1≤i≤5) such that|Ai∩Aj|=|i−j|for every twointegersiandjwith 1≤i < j≤5.(ii) Determine the minimum positive integerksuch that there exist four setsAi(1≤i≤4)satisfying the conditions of Exercise 1.79 and|A1∪A2∪A3∪A4|=k.

Loading page image...

10(b)(i)A1={1,2,3,4,7,8,9,10}A2={3,5,6,11,12,13}A3={1,3,14,15}A4={1,2,4,5,6,16}A5={7,8,9,10,11,12,13,14,15,16}.(ii) The minimum positive integerkis 5. The example below shows thatk≤5.LetA1={1,2,3,4},A2={1,5},A3={1,4},A4={1,2,3,5}.Ifk= 4, then since|A1∩A4|= 3,A1andA4have exactly three elements in common,say 1, 2, 3. So each ofA1andA4is either{1,2,3}or{1,2,3,4}. They cannot both be{1,2,3,4}. Also, they cannot both be{1,2,3}becauseA3would have to contain two of1, 2, 3 and so|A3∩A4| ≥2, which is not true. So we can assume thatA1={1,2,3,4}andA4={1,2,3}. However,A2must contain two of 1, 2, 3 and so|A1∩A2| ≥2, whichis impossible.1.87(a)|S|=|T|= 10.(b)|S|=|T|= 5.(c)|S|=|T|= 6.1.88 LetA={1,2,3,4},A1={1,2},A2={1,3},A3={3,4}. These examples show thatk≤4. Since|A1−A3|=|A3−A1|= 2, it follows thatA1contains two elements not inA3, whileA3contains twoelements not inA1. Thus|A| ≥4 and sok= 4 is the smallest positive integer with this property.1.89(a)S={(−3,4),(0,5),(3,4),(4,3)}.(b)C={a∈B: (a, b)∈S}={3,4}D={b∈A: (a, b)∈S}={3,4}C×D={(3,3),(3,4),(4,3),(4,3)}.1.90A={1,2,3},B={{1,2},{1,3},{2,3}},C={{1},{2},{3}},D=P(C) ={∅,{{1}},{{2}},{{3}},{{1},{2}},{{1},{3}},{{2},{3}}, C}.1.91S={x∈R:x2+ 2x−1 = 0}={−1 +√2,−1− √2}.A−1+√2={−1 +√2,√2},A−1−√2={−1− √2− √2}.(a)As=A−1−√2andAt=A−1+√2.As×At={(−1− √2,−1 +√2),(−1− √2,√2),(−√2,1 +√2),(−√2,√2)}.(b)C={ab: (a, b)∈B}={−1,−√2−2,√2−2,−2}. The sum of the elements inCis−7.1.92(a) For|A|= 2, the largest possible value of|A∩ P(A)|is 2.The setA={∅,{∅}}has this property.(b) For|A|= 3, the largest possible value of|A∩ P(A)|is 3.The setA={∅,{∅},{{∅}}}has this property.(c) For|A|= 4, the largest possible value of|A∩ P(A)|is 4.The setA={∅,{∅},{{∅}},{{{∅}}}}has this property.

Loading page image...

111.93∞⋃n=1Sn=∞⋂n=1Sn=[−√2,√2]. First, observe that∞⋂n=1Sn=S1={x+y:x, y∈R, x2+y2= 1}.Letf(x) =x+y, wherey=±√1−x2, sayy=√1−x2.Thenf(x) =x+√1−x2.Sincef′(x) = 1−x√1−x2, it follows thatf′(x) = 0 whenx=1√2and so the maximum value ofx+yis√2.Sincef(−1√2) = 0 andfis continuous on[−√2,√2], it follows thatftakes on all values of[0,√2].Ifx+y=r∈[0,√2], it follows that (−x) + (−y) =−r∈[−√2,0]. Hence,S1=[−√2,√2]. Ifa2+b2=rwhere 0< r <1, thena+b∈(−√2,√2)and so∞⋃n=1Sn=[−√2,√2]as well.1.94 (a)No. For example, the elements 1, 2 and 5 belong to more than one subset ofS.(b)Yes. (c)Yes.1.95 In order for|A×(B∪C)|=|A×B|+|A×C|, the setsBandCmust be disjoint.

Preview Mode

This document has 224 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

AP Calculus AB Unit 5 Progress Check Scoring Guide

Company

Explore

Study Tools