14 SET THEORY [CHAP.1 1.8 Prove Theorem 1.4.The following are equivalent:A B,AnB =A.AU B=B. Suppose A∈B and let x∈A.Thenx∈B,hencex∈AnB and A∈AnB.By Theorem 1.3,(AnB)∈A.Therefore AnB=A.On the other hand,.suppose An B=A and let x∈A.Then x∈(AnB):hencex∈A and x∈B. Therefore,A C B.Both results show that A C B is equivalent to AnB =A. Suppose again that A B.Letx∈(AUB).Thenx∈Aorx∈B.fx∈A,thenx∈B because A C B.In either case,xE B.Therefore AUB C B.By Theorem 1.3,B CAU B.Therefore AUB=B.Now suppose AUB=B and letx A.Then x E A UB by definition of the union of sets.Hence x E B =AU B.Therefore A C B.Both results show that A C B is equivalent to AUB=B. Thus A C B,AUB A and AUB B are equivalent. VENN DIAGRAMS,ALGEBRA OF SETS,DUALITY 1.9 Illustrate DeMorgan's Law (A U B)C=ACn BC using Venn diagrams. Shade the area outside A U B in a Venn diagram of sets A and B.This is shown in Fig.1-7(a);hence the shaded area represents (A U B)C.Now shade the area outside A in a Venn diagram of A and B with strokes in one direction (/)and then shade the area outside B with strokes in another direction ()This is shown in Fig.1-7(b);hence the cross-hatched area(area where both lines are present)represents ACnBC.Both(AUB)C and ACnBC are represented by the same area;thus the Venn diagram indicates(AUB)C=ACBC.(We emphasize that a Venn diagram is not a formal proof,but it can indicate relationships between sets.) (a) (b) Fig.1-7 1.10 Prove the Distributive Law:An(BUC)=(AnB)U(AnC). An(BUC)={x|x∈A,x∈(BUC)} ={x|x∈A,x∈Borx∈A,x∈C}=(AnB)U(AnC) Here we use the analogous logical law pA (vr)=(pA)v(pAr)where denotes"and"and v denotes"or." 1.11 Write the dual of:(a)(UnA)U(BnA)=A;(b)(AnU)n(AC)=0. Interchange U and n and also U and in each set equation: (a)(0UA)n(BUA)=A;(b)(AU)U(UnAC)=U. 1.12 Prove:(AU B)\(AnB)=(A\B)U(B\A).(Thus either one may be used to define A B.) Using X\Y=XnYC and the laws in Table 1.1,including DeMorgan's Law,we obtain: (AUB)(AnB)=(AUB)(AnB)C=(AUB)n(ACUBC) =(AUAC)U(AnBC)U(BnAC)U(BnBC) =0U(AnBC)U(BnAC)U0 =(An BC)U(BnAC)=(A\B)U(B\A)
14 SET THEORY [CHAP. 1 1.8 Prove Theorem 1.4. The following are equivalent: A ⊆ B, A ∩ B = A, A ∪ B = B. Suppose A ⊆ B and let x ∈ A. Then x ∈ B, hence x ∈ A∩B and A ⊆ A∩B. By Theorem 1.3, (A∩B) ⊆ A. Therefore A ∩ B = A. On the other hand, suppose A ∩ B = A and let x ∈ A. Then x ∈ (A ∩ B); hence x ∈ A and x ∈ B. Therefore, A ⊆ B. Both results show that A ⊆ B is equivalent to A ∩ B = A. Suppose again that A ⊆ B. Let x ∈ (A ∪ B). Then x ∈ A or x ∈ B. If x ∈ A, then x ∈ B because A ⊆ B. In either case, x ∈ B. Therefore A ∪ B ⊆ B. By Theorem 1.3, B ⊆ A ∪ B. Therefore A ∪ B = B. Now suppose A ∪ B = B and let x ∈ A. Then x ∈ A ∪ B by definition of the union of sets. Hence x ∈ B = A ∪ B. Therefore A ⊆ B. Both results show that A ⊆ B is equivalent to A ∪ B = B. Thus A ⊆ B, A ∪ B = A and A ∪ B = B are equivalent. VENN DIAGRAMS, ALGEBRA OF SETS, DUALITY 1.9 Illustrate DeMorgan’s Law (A ∪ B)C = AC ∩ BC using Venn diagrams. Shade the area outside A ∪ B in a Venn diagram of sets A and B. This is shown in Fig. 1-7(a); hence the shaded area represents (A ∪ B)C. Now shade the area outside A in a Venn diagram of A and B with strokes in one direction (////), and then shade the area outside B with strokes in another direction (\\\\). This is shown in Fig. 1-7(b); hence the cross-hatched area (area where both lines are present) represents AC∩BC. Both (A∪B)C and AC∩BC are represented by the same area; thus the Venn diagram indicates (A ∪ B)C = AC ∩ BC. (We emphasize that a Venn diagram is not a formal proof, but it can indicate relationships between sets.) Fig. 1-7 1.10 Prove the Distributive Law: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). A ∩ (B ∪ C) = {x | x ∈ A, x ∈ (B ∪ C)} = {x | x ∈ A, x ∈ B or x ∈ A, x ∈ C} = (A ∩ B) ∪ (A ∩ C) Here we use the analogous logical law p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) where ∧ denotes “and” and ∨ denotes “or.” 1.11 Write the dual of: (a) (U ∩ A) ∪ (B ∩ A) = A; (b) (A ∩ U) ∩ (∅ ∪ AC) = ∅. Interchange ∪ and ∩ and also U and ∅ in each set equation: (a) (∅ ∪ A) ∩ (B ∪ A) = A; (b) (A ∪ ∅) ∪ (U ∩ AC) = U. 1.12 Prove: (A ∪ B)\(A ∩ B) = (A\B) ∪ (B\A). (Thus either one may be used to define A ⊕ B.) Using X\Y = X ∩ YC and the laws in Table 1.1, including DeMorgan’s Law, we obtain: (A ∪ B)\(A ∩ B) = (A ∪ B) ∩ (A ∩ B)C = (A ∪ B) ∩ (AC ∪ BC) = (A ∪ AC) ∪ (A ∩ BC) ∪ (B ∩ AC) ∪ (B ∩ BC) =∅∪ (A ∩ BC) ∪ (B ∩ AC) ∪ ∅ = (A ∩ BC) ∪ (B ∩ AC) = (A\B) ∪ (B\A)
CHAP.1] SET THEORY 15 1.13 Determine the validity of the following argument: S:All my friends are musicians. S2:John is my friend. S3:None of my neighbors are musicians. S:John is not my neighbor. The premises SI and S3 lead to the Venn diagram in Fig.1-8(a).By S2.John belongs to the set of friends which is disjoint from the set of neighbors.Thus S is a valid conclusion and so the argument is valid. A musicians neighbors 40 20 25 friends 55 (a) (b) Fig.1-8 FINITE SETS AND THE COUNTING PRINCIPLE 1.14 Each student in Liberal Arts at some college has a mathematics requirement A and a science requirement B. A poll of 140 sophomore students shows that: 60 completed A,45 completed B,20 completed both A and B. Use a Venn diagram to find the number of students who have completed: (a)At least one of A and B;(b)exactly one of A or B;(c)neither A nor B. Translating the above data into set notation yields: n(A)=60,n(B)=45,n(AnB)=20,n(U)=140 Draw a Venn diagram of sets A and B as in Fig.1-1(c).Then,as in Fig.1-8(b),assign numbers to the four regions as follows: 20 completed both A and B,so n(An B)=20. 60-20 =40 completed A but not B,so n(A\B)=40. 45-20 =25 completed B but not A,so n(B\A)=25. 140-20-40-25=55 completed neither A nor B. By the Venn diagram: (a)20+40+25=85 completed A or B.Alternately,by the Inclusion-Exclusion Principle: n(AUB)=n(A)+n(B)-n(AnB)=60+45-20=85 (b)40+25 =65 completed exactly one requirement.That is,n(A B)=65. (c)55 completed neither requirement,i.e.n(ACnBC)=n[(A UB)C]=140-85 =55. 1.15 In a survey of 120 people,it was found that: 65 read Newsweek magazine,20 read both Newsweek and Time, 45 read Time, 25 read both Newsweek and Fortune, 42 read Fortune, 15 read both Time and Fortune, 8 read all three magazines
CHAP. 1] SET THEORY 15 1.13 Determine the validity of the following argument: S1: All my friends are musicians. S2: John is my friend. S3: None of my neighbors are musicians. S : John is not my neighbor. The premises S1 and S3 lead to the Venn diagram in Fig. 1-8(a). By S2, John belongs to the set of friends which is disjoint from the set of neighbors. Thus S is a valid conclusion and so the argument is valid. Fig. 1-8 FINITE SETS AND THE COUNTING PRINCIPLE 1.14 Each student in Liberal Arts at some college has a mathematics requirement A and a science requirement B. A poll of 140 sophomore students shows that: 60 completed A, 45 completed B, 20 completed both A and B. Use a Venn diagram to find the number of students who have completed: (a) At least one of A and B; (b) exactly one of A or B; (c) neither A nor B. Translating the above data into set notation yields: n(A) = 60, n(B) = 45, n(A ∩ B) = 20, n(U) = 140 Draw a Venn diagram of sets A and B as in Fig. 1-1(c). Then, as in Fig. 1-8(b), assign numbers to the four regions as follows: 20 completed both A and B, so n(A ∩ B) = 20. 60 − 20 = 40 completed A but not B, so n(A\B) = 40. 45 − 20 = 25 completed B but not A, so n(B\A) = 25. 140 − 20 − 40 − 25 = 55 completed neither A nor B. By the Venn diagram: (a) 20 + 40 + 25 = 85 completed A or B. Alternately, by the Inclusion–Exclusion Principle: n(A ∪ B) = n(A) + n(B) − n(A ∩ B) = 60 + 45 − 20 = 85 (b) 40 + 25 = 65 completed exactly one requirement. That is, n(A ⊕ B) = 65. (c) 55 completed neither requirement, i.e. n(AC ∩ BC) = n[(A ∪ B)C] = 140 − 85 = 55. 1.15 In a survey of 120 people, it was found that: 65 read Newsweek magazine, 20 read both Newsweek and Time, 45 read Time, 25 read both Newsweek and Fortune, 42 read Fortune, 15 read both Time and Fortune, 8 read all three magazines
16 SET THEORY [CHAP.1 (a)Find the number of people who read at least one of the three magazines. (b)Fill in the correct number of people in each of the eight regions of the Venn diagram in Fig.1-9(a)where N,T,and F denote the set of people who read Newsweek,Time,and Fortune,respectively. (c)Find the number of people who read exactly one magazine. N 28 F 10 20 (a) (6) Fig.1-9 (a)We want to find n(N UTU F).By Corollary 1.10(Inclusion-Exclusion Principle). n(NUTU F)=n(N)+n(T)+n(F)-n(N OT)-n(NOF)-n(TnF)+n(NOTO F) =65+45+42-20-25-15+8=100 (b)The required Venn diagram in Fig.1-9(b)is obtained as follows: 8 read all three magazines, 20-8 =12 read Newsweek and Time but not all three magazines, 25-8 =17 read Newsweek and Fortune but not all three magazines, 15-8=7 read Time and Fortune but not all three magazines. 65-12-8-17 =28 read only Newsweek, 45-12-8-7 18 read only Time, 42-17-8-7=10 read only Fortune, 120-100 =20 read no magazine at all. (c)28+18+10 =56 read exactly one of the magazines. 1.16 Prove Theorem 1.9.Suppose A and B are finite sets.Then A U B and An B are finite and n(AUB)=n(A)+n(B)-n(AnB) If A and B are finite then,clearly,AU B and AnB are finite. Suppose we count the elements in A and then count the elements in B. Then every element in An B would be counted twice,once in A and once in B.Thus n(AUB)=n(A)+n(B)-n(AB)
16 SET THEORY [CHAP. 1 (a) Find the number of people who read at least one of the three magazines. (b) Fill in the correct number of people in each of the eight regions of the Venn diagram in Fig. 1-9(a) where N, T , and F denote the set of people who read Newsweek, Time, and Fortune, respectively. (c) Find the number of people who read exactly one magazine. Fig. 1-9 (a) We want to find n(N ∪ T ∪ F ). By Corollary 1.10 (Inclusion–Exclusion Principle), n(N ∪ T ∪ F )= n(N ) + n(T ) + n(F ) − n(N ∩ T ) − n(N ∩ F ) − n(T ∩ F ) + n(N ∩ T ∩ F ) = 65 + 45 + 42 − 20 − 25 − 15 + 8 = 100 (b) The required Venn diagram in Fig. 1-9(b) is obtained as follows: 8 read all three magazines, 20 − 8 = 12 read Newsweek and Time but not all three magazines, 25 − 8 = 17 read Newsweek and Fortune but not all three magazines, 15 − 8 = 7 read Time and Fortune but not all three magazines, 65 − 12 − 8 − 17 = 28 read only Newsweek, 45 − 12 − 8 − 7 = 18 read only Time, 42 − 17 − 8 − 7 = 10 read only Fortune, 120 − 100 = 20 read no magazine at all. (c) 28 + 18 + 10 = 56 read exactly one of the magazines. 1.16 Prove Theorem 1.9. Suppose A and B are finite sets. Then A ∪ B and A ∩ B are finite and n(A ∪ B) = n(A) + n(B) − n(A ∩ B) If A and B are finite then, clearly, A ∪ B and A ∩ B are finite. Suppose we count the elements in A and then count the elements in B. Then every element in A ∩ B would be counted twice, once in A and once in B. Thus n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
CHAP.1] SET THEORY 17 CLASSES OF SETS 1.17 Let A =[(1,2,3),(4,5),(6,7,8)].(a)List the elements of A;(b)Find n(A). (a)A has three elements,the sets (1.2,31,(4.51,and (6,7,81. (b)n(A)=3. 1.18 Determine the power set P(A)of A [a,b,c,d). The elements of P(A)are the subsets of A.Hence P(A)=[A,a,b,ch,la,b,d).a,c,d),(b,c,dl,ta,b),ta.ch.a,d),b.ch.b,d), {c,d,{a,{bh,{c,{d, As expected,P(A)has 24=16 elements. 1.19 Let S=(a,b,c,d,e,f,g).Determine which of the following are partitions of S: (a)P=[{a,c,eh,{b,{d,g}], (c)P3=[{a,b,e,g},{cl,{d,f]. (b)P2=[fa,e,g),(c,d),(b,e,f)],(d)P4=[a,b,c,d,e,f,g)]. (a)P is not a partition of S since fS does not belong to any of the cells. (b)P2 is not a partition of S sincee S belongs to two of the cells. (c)P3 is a partition of S since each element in S belongs to exactly one cell. (d)P4 is a partition of S into one cell,S itself. 1.20 Find all partitions of S=(a,b,c,d). Note first that each partition of S contains either 1,2,3,or 4 distinct cells.The partitions are as follows: (1)[{a,b,c,d] (2)[fa).(b,c,d)].[(b),(a,c,d)].[c),(a,b,d)l.[d),ta,b,c)l. [a,b).(c,d)l.[fa,c).(b,d)].a,d).(b,c] (3)[{ah,{b},{c,dl,[{a},{ch,{b,dl,[{a},{dh,{b,cl, [b),(c),(a,d)l,[b),(d),(a,c)],[c),d),ta,b)] (4)[{ah,{bh,{ch,{d] There are 15 different partitions of S. 1.21 Let N=(1,2,3,...}and,for each n EN,Let An (n,2n,3n,...).Find: (a)A3nAs;(b)A4nA5;(c)UieAi where =(2,3,5,7,11,...]is the set of prime numbers. (a)Those numbers which are multiples of both 3 and 5 are the multiples of 15;hence A3nA5 =A15. (b)The multiples of 12 and no other numbers belong to both A4 and A6,hence A40A6=A12. (c)Every positive integer except 1 is a multiple of at least one prime number;hence UA=2,34,=N ieo 1.22 Let (Aili I)be an indexed class of sets and let io I.Prove ∩Ai AioUA LetxE∩iel Ai then x∈Ai for every i∈I.In particular,x∈Aio-Hence∩liel Ai Ai-Now let y E Aio.Since io∈I,y∈∩ielAi.Hence Aio Uiel Ai
CHAP. 1] SET THEORY 17 CLASSES OF SETS 1.17 Let A = [{1, 2, 3}, {4, 5}, {6, 7, 8}]. (a) List the elements of A; (b) Find n(A). (a) A has three elements, the sets {1, 2, 3}, {4, 5}, and {6, 7, 8}. (b) n(A) = 3. 1.18 Determine the power set P (A) of A = {a, b, c, d}. The elements of P (A) are the subsets of A. Hence P (A) = [A,{a, b, c},{a, b, d},{a, c, d},{b, c, d},{a, b},{a, c},{a, d},{b, c},{b, d}, {c, d},{a},{b},{c},{d}, ∅] As expected, P (A) has 24 = 16 elements. 1.19 Let S = {a, b, c, d, e, f , g}. Determine which of the following are partitions of S: (a) P1 = [{a, c, e}, {b}, {d, g}], (c) P3 = [{a, b, e, g}, {c}, {d, f }], (b) P2 = [{a, e, g}, {c, d}, {b, e, f }], (d) P4 = [{a, b, c, d, e, f , g}]. (a) P1 is not a partition of S since f ∈ S does not belong to any of the cells. (b) P2 is not a partition of S since e ∈ S belongs to two of the cells. (c) P3 is a partition of S since each element in S belongs to exactly one cell. (d) P4 is a partition of S into one cell, S itself. 1.20 Find all partitions of S = {a, b, c, d}. Note first that each partition of S contains either 1, 2, 3, or 4 distinct cells. The partitions are as follows: (1) [{a, b, c, d}] (2) [{a}, {b, c, d}], [{b}, {a, c, d}], [{c}, {a, b, d}], [{d}, {a, b, c}], [{a, b}, {c, d}], [{a, c}, {b, d}], [{a, d}, {b, c}] (3) [{a}, {b}, {c, d}], [{a}, {c}, {b,d}], [{a}, {d}, {b, c}], [{b}, {c}, {a, d}], [{b}, {d}, {a, c}], [{c}, {d}, {a, b}] (4) [{a}, {b}, {c}, {d}] There are 15 different partitions of S. 1.21 Let N = {1, 2, 3,…} and, for each n ∈ N, Let An = {n, 2n, 3n,…}. Find: (a) A3 ∩ A5; (b) A4 ∩ A5; (c) i∈QAi where Q = {2, 3, 5, 7, 11, …} is the set of prime numbers. (a) Those numbers which are multiples of both 3 and 5 are the multiples of 15; hence A3 ∩ A5 = A15. (b) The multiples of 12 and no other numbers belong to both A4 and A6, hence A4 ∩ A6 = A12. (c) Every positive integer except 1 is a multiple of at least one prime number; hence i∈Q Ai = {2, 3, 4,...} = N\{1} 1.22 Let {Ai | i ∈ I } be an indexed class of sets and let i0 ∈ I . Prove i∈I Ai ⊆ Ai0 ⊆ i∈I Ai. Let x ∈ i∈I Ai then x ∈ Ai for every i ∈ I . In particular, x ∈ Ai0 . Hence i∈l Ai ⊆ Ai0 . Now let y ∈ Ai0 . Since i0 ∈ I , y ∈ i∈lAi. Hence Ai0 ⊆ i∈l Ai.
18 SET THEORY [CHAP.1 1.23 Prove (De Morgan's law):For any indexed class (Aili1).we have (UiAi)c=AC. Using the definitions of union and intersection of indexed classes of sets: Ai)c=xxA)=xx Ai for every i) =rlx∈A for every i=∩，A9 MATHEMATICAL INDUCTION 1.24 Prove the proposition P(n)that the sum of the first n positive integers is n(n+1);that is, P(n)=1+2+3+.+n=n(n+1) The proposition holds for n=1 since: P(1):1=5(1)1+1) Assuming P(k)is true,we add k+1 to both sides of P(k),obtaining 1+2+3+·+k+(k+1)=k(k+1)+(k+1) =[k(k+1)+2k+1)] =k+1)k+2] which is P(k+1).That is,P(+1)is true whenever P(k)is true.By the Principle of Induction,P is true for all n. 1.25 Prove the following proposition(for n>0): P(n):1+2+22+23+.+2"=2+1-1 P(0)is true since 1=21-1.Assuming P(k)is true,we add+to both sides of P(k).obtaining 1+2+22+23+.+2+2k+1=2k+1-1+2k+1=2(2k+-1=2k+2-1 which is P(k+1).That is,P(k+1)is true whenever P(k)is true.By the principle of induction,P(n)is true for all n. Supplementary Problems SETS AND SUBSETS 1.26 Which of the following sets are equal? A={x|x2-4x+3=0,C={xlx∈N,x<3, E={1.2}, G={3.1}, B={x|x2-3x+2=0,D={xlx∈N,x is odd.x<5,F={l,2,1,H={1,1,3. 1.27 List the elements of the following sets if the universal set is U=fa.b.c.....y.). Furthermore,identify which of the sets,if any,are equal. A ={xx is a vowel), C={xIx precedes fin the alphabet). B=xlx is a letter in the word "little").D={xx is a letter in the word"title"). 128LtA={1,2,,8.9,B={2.4,6,8},C={1,3,5,7,9h,D={3,4,5},E={3,5. Which of the these sets can equal a set X under each of the following conditions? (a)X and B are disjoint.(c)X C A but X C. (b)X C D but X B.(d)X CC but X A
18 SET THEORY [CHAP. 1 1.23 Prove (De Morgan’s law): For any indexed class {Ai | i ∈ I }, we have i Ai C = i AC i . Using the definitions of union and intersection of indexed classes of sets: i Ai C = {x | x /∈ i Ai}={x | x /∈ Ai for every i} = {x | x ∈ AC i for every i} = i AC i MATHEMATICAL INDUCTION 1.24 Prove the proposition P (n) that the sum of the first n positive integers is 1 2n(n + 1); that is, P (n) = 1 + 2 + 3 +···+ n = 1 2n(n + 1) The proposition holds for n = 1 since: P (1) : 1 = 1 2 (1)(1 + 1) Assuming P (k) is true, we add k + 1 to both sides of P (k), obtaining 1 + 2 + 3 +···+ k + (k + 1) = 1 2 k(k + 1) + (k + 1) = 1 2 [k(k + 1) + 2(k + 1)] = 1 2 [(k + 1)(k + 2)] which is P (k + 1). That is, P (k + 1) is true whenever P (k) is true. By the Principle of Induction, P is true for all n. 1.25 Prove the following proposition (for n ≥ 0): P (n): 1 + 2 + 22 + 23 +···+ 2n = 2n+1 − 1 P (0) is true since 1 = 21 − 1. Assuming P (k) is true, we add 2k+1 to both sides of P (k), obtaining 1 + 2 + 22 + 23 +···+ 2k + 2k+1 = 2k+1 − 1 + 2k+1 = 2(2k+1) − 1 = 2k+2 − 1 which is P (k + 1). That is, P (k + 1) is true whenever P (k) is true. By the principle of induction, P (n) is true for all n. Supplementary Problems SETS AND SUBSETS 1.26 Which of the following sets are equal? A = {x | x2 − 4x + 3 = 0}, C = {x | x ∈ N,x < 3}, E = {1, 2}, G = {3, 1}, B = {x | x2 − 3x + 2 = 0}, D = {x | x ∈ N, x is odd, x < 5}, F = {1, 2, 1}, H = {1, 1, 3}. 1.27 List the elements of the following sets if the universal set is U = {a, b, c, …, y, z}. Furthermore, identify which of the sets, if any, are equal. A = {x | x is a vowel}, C = {x | x precedes f in the alphabet}, B = {x | x is a letter in the word “little”}, D = {x | x is a letter in the word “title”}. 1.28 Let A = {1, 2, …, 8, 9}, B = {2, 4, 6, 8}, C = {1, 3, 5, 7, 9}, D = {3, 4, 5}, E = {3, 5}. Which of the these sets can equal a set X under each of the following conditions? (a) X and B are disjoint. (c) X ⊆ A but X ⊂ C. (b) X ⊆ D but X ⊂ B. (d) X ⊆ C but X ⊂ A.