CHAP.1] SET THEORY 19 SET OPERATIONS 1.29 Consider the universal set U=(1,2,3,....8.9)and sets A=(1,2,5,6),B=(2,5,7),C=(1,3,5,7,9).Find: (a)An B and AnC(c)AC and CC(e)A⊕B and A⊕C (b)AUB and BUC (d)A\B and A\C (f)(AUC)\B and (B C)\A 1.30 Let A and B be any sets.Prove: (a)A is the disjoint union of A\B and AnB. (b)AU B is the disjoint union of A\B,AnB,and B\A. 1.31 Prove the following: (a)A C B if and only if AnBC=(c)A C B if and only if BC AC (b)A C B if and only if ACUB=U (d)A C B if and only if A\B= (Compare the results with Theorem 1.4.) 1.32 Prove the Absorption Laws:(a)AU(An B)=A;(b)An(AU B)=A. 1.33 The formula A\B=AnBC defines the difference operation in terms of the operations of intersection and complement. Find a formula that defines the union A U B in terms of the operations of intersection and complement. VENN DIAGRAMS 1.34 The Venn diagram in Fig.1-5(a)shows sets A,B,C.Shade the following sets: (a)A\(BUC);(b)ACn(BUC):(c)ACn(C\B). 1.35 Use the Venn diagram in Fig.1-5(b)to write each set as the (disjoint)union of fundamental products: (a)An(BUC):(b)ACn(BUC):(c)AU(B\C). 1.36 Consider the following assumptions: S:All dictionaries are useful. S2:Mary owns only romance novels. S3:No romance novel is useful. Use a Venn diagram to determine the validity of each of the following conclusions: (a)Romance novels are not dictionaries. (b)Mary does not own a dictionary. (c)All useful books are dictionaries. ALGEBRA OF SETS AND DUALITY 1.37 Write the dual of each equation: (a)A=(BCnA)U(AnB) (b)(AnB)U(ACnB)U(AnBC)U(ACnBC)=U 1.38 Use the laws in Table 1-1 to prove each set identity: (a)(AnB)U(AnBC)=A (b)AUB=(AnBC)U(ACnB)U(AnB)
CHAP. 1] SET THEORY 19 SET OPERATIONS 1.29 Consider the universal set U = {1, 2, 3, …, 8, 9} and sets A = {1, 2, 5, 6}, B = {2, 5, 7}, C = {1, 3, 5, 7, 9}. Find: (a) A ∩ B and A ∩ C (c) AC and CC (e) A ⊕ B and A ⊕ C (b) A ∪ B and B ∪ C (d) A\B and A\C (f) (A ∪ C)\B and (B ⊕ C)\A 1.30 Let A and B be any sets. Prove: (a) A is the disjoint union of A\B and A ∩ B. (b) A ∪ B is the disjoint union of A\B, A ∩ B, and B\A. 1.31 Prove the following: (a) A ⊆ B if and only if A ∩ BC = ∅ (c) A ⊆ B if and only if BC ⊆ AC (b) A ⊆ B if and only if AC ∪ B = U (d) A ⊆ B if and only if A\B = ∅ (Compare the results with Theorem 1.4.) 1.32 Prove the Absorption Laws: (a) A ∪ (A ∩ B) = A; (b) A ∩ (A ∪ B) = A. 1.33 The formula A\B = A∩BC defines the difference operation in terms of the operations of intersection and complement. Find a formula that defines the union A ∪ B in terms of the operations of intersection and complement. VENN DIAGRAMS 1.34 The Venn diagram in Fig. 1-5(a) shows sets A, B, C. Shade the following sets: (a) A\(B ∪ C); (b) AC ∩ (B ∪ C); (c) AC ∩ (C\B). 1.35 Use the Venn diagram in Fig. 1-5(b) to write each set as the (disjoint) union of fundamental products: (a) A ∩ (B ∪ C); (b) AC ∩ (B ∪ C); (c) A ∪ (B\C). 1.36 Consider the following assumptions: S1: All dictionaries are useful. S2: Mary owns only romance novels. S3: No romance novel is useful. Use a Venn diagram to determine the validity of each of the following conclusions: (a) Romance novels are not dictionaries. (b) Mary does not own a dictionary. (c) All useful books are dictionaries. ALGEBRA OF SETS AND DUALITY 1.37 Write the dual of each equation: (a) A = (BC ∩ A) ∪ (A ∩ B) (b) (A ∩ B) ∪ (AC ∩ B) ∪ (A ∩ BC) ∪ (AC ∩ BC) = U 1.38 Use the laws in Table 1-1 to prove each set identity: (a) (A ∩ B) ∪ (A ∩ BC) = A (b) A ∪ B = (A ∩ BC) ∪ (AC ∩ B) ∪ (A ∩ B)
20 SET THEORY [CHAP.1 FINITE SETS AND THE COUNTING PRINCIPLE 1.39 Determine which of the following sets are finite: (a)Lines parallel to the x axis.(c)Integers which are multiples of 5. (b)Letters in the English alphabet.(d)Animals living on the earth. 1.40 Use Theorem 1.9 to prove Corollary 1.10:Suppose A,B,C are finite sets.Then AU BUC is finite and n(AUBUC)=n(A)+n(B)+n(C)-n(A∩B)-n(A∩C)-n(BnC)+n(A∩BnC) 1.41 A survey on a sample of 25 new cars being sold at a local auto dealer was conducted to see which of three popular options,air-conditioning (A),radio (R),and power windows(W),were already installed.The survey found: 15 had air-conditioning (A),5 had A and P, 12 had radio (R), 9 had A and R. 3 had all three options. 11 had power windows (W),4 had R and W, Findthenumberofcarsthat had:(a)only W;(b)only A:(c)only R;(d)Rand W but not A:(e)A and R but not W; (f)only one of the options;(g)at least one option;(h)none of the options. CLASSES OF SETS 1.42 Find the power set P(A)of A =(1,2,3,4,5). 1.43 Given A [a,b),(c),(d,e,f)l. (a)List the elements of A.(b)Find n(A).(c)Find the power set of A. 1.44 Suppose A is finite and n(A)=m.Prove the power set P(A)has 2m elements. PARTITIONS 1.45 Let S=(1.2,....8.9).Determine whether or not each of the following is a partition of S: (a)[{1,3,6},{2,8h,{5,7,9月(c)[{2.4,5,8,{1,9,{3,6.7] b)[{1,5,7,{2,4,8,91,{3,5,6l(d[{1,2,7.{3,5,{4,6,8.9,{3,5 1.46 Let S=(1,2,3,4,5,6).Determine whether or not each of the following is a partition of S: (a)=[{1,2.3,{1,4,5,6l(c)P3=[{1,3,5,{2,4,{6 (b)P2=[{1,2,{3,5,61 (dP4=[{1,3,51,{2,4,67] 1.47 Determine whether or not each of the following is a partition of the set N of positive integers: (a)[{nln>5,{nln<5h:b)[{nln>6},{1,3,5,{2,4h: (c)[{nln2>11,{nln2<111. 1.48 Let [A1,A2.....Am]and [B1.B2.....Bn]be partitions of a set S. Show that the following collection of sets is also a partition(called the cross partition)of S: P=[A:∩Bji=1,,m,j=1,,n]八0 Observe that we deleted the empty set 0. 1.49 Let S=(1,2,3.....8.9).Find the cross partition P of the following partitions of S: P=[{1,3.5,7,9,{2,4,6,8]andP=[{1,2,3,4},{5,7},{6.8,9]
20 SET THEORY [CHAP. 1 FINITE SETS AND THE COUNTING PRINCIPLE 1.39 Determine which of the following sets are finite: (a) Lines parallel to the x axis. (c) Integers which are multiples of 5. (b) Letters in the English alphabet. (d) Animals living on the earth. 1.40 Use Theorem 1.9 to prove Corollary 1.10: Suppose A, B, C are finite sets. Then A ∪ B ∪ C is finite and n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C) 1.41 A survey on a sample of 25 new cars being sold at a local auto dealer was conducted to see which of three popular options, air-conditioning (A), radio (R), and power windows (W ), were already installed. The survey found: 15 had air-conditioning (A), 5 had A and P, 12 had radio (R), 9 had A and R, 3 had all three options. 11 had power windows (W ), 4 had R and W, Find the number of cars that had: (a) onlyW; (b) onlyA; (c) onlyR; (d)R andW but notA; (e)AandR but notW; (f) only one of the options; (g) at least one option; (h) none of the options. CLASSES OF SETS 1.42 Find the power set P (A) of A = {1, 2, 3, 4, 5}. 1.43 Given A = [{a, b}, {c}, {d, e, f }]. (a) List the elements of A. (b) Find n(A). (c) Find the power set of A. 1.44 Suppose A is finite and n(A) = m. Prove the power set P (A) has 2m elements. PARTITIONS 1.45 Let S = {1, 2, …, 8, 9}. Determine whether or not each of the following is a partition of S : (a) [{1, 3, 6}, {2, 8}, {5, 7, 9}] (c) [{2, 4, 5, 8}, {1, 9}, {3, 6, 7}] (b) [{1, 5, 7}, {2, 4, 8, 9}, {3, 5, 6}] (d) [{1, 2, 7}, {3, 5}, {4, 6, 8, 9}, {3, 5}] 1.46 Let S = {1, 2, 3, 4, 5, 6}. Determine whether or not each of the following is a partition of S : (a) P1 = [{1, 2, 3}, {1, 4, 5, 6}] (c) P3 = [{1, 3, 5}, {2, 4}, {6}] (b) P2 = [{1, 2}, {3, 5, 6}] (d) P4 = [{1, 3, 5}, {2, 4, 6, 7}] 1.47 Determine whether or not each of the following is a partition of the set N of positive integers: (a) [{n | n > 5}, {n | n < 5}]; (b) [{n | n > 6}, {1, 3, 5}, {2, 4}]; (c) [{n | n2 > 11}, {n | n2 < 11}]. 1.48 Let [A1, A2, …, Am] and [B1, B2, …, Bn] be partitions of a set S. Show that the following collection of sets is also a partition (called the cross partition) of S : P = [Ai ∩ Bj |i = 1, . . . , m, j = 1,...,n]\∅ Observe that we deleted the empty set ∅. 1.49 Let S = {1, 2, 3, …, 8, 9}. Find the cross partition P of the following partitions of S : P1 = [{1, 3, 5, 7, 9},{2, 4, 6, 8}] and P2 = [{1, 2, 3, 4},{5, 7},{6, 8, 9}]
CHAP.1] SET THEORY 21 INDUCTION 150 Prove:2+4+6+..+2n=n(n+1) 1.51 Prove::1+4+7+.+3n-2=n3n- 152 Prove::12+22+32+…+n2=m+l2m+ 153 Prove::+分+女++2m-0m+可= 1.54Pove:六+动十市+…+4m-34m+可= 1.55 Prove 7n-2 is divisible by 5 for all nN 1.56 Prove n3-4n +6 is divisible by 3 for all n EN 1.57 Use the identity 1+2+3+...+n =n(n +1)/2 to prove that 13+23+33+…+n3=(1+2+3+…+n)2 Miscellaneous Problems 1.58 Suppose N=(1,2,3....)is the universal set,and A={nln≤6，B={n|4≤n≤9}，C={1,3,5,7,9}.D={2,3,5,7,8}. Find:(a)A⊕B:(b)B⊕C;(c)An(B⊕D:(d(AnB)⊕(AnD) 1.59 Prove the following properties of the symmetric difference: (a)(A⊕B)⊕C=A⊕(B⊕C)(Associative Law). (b)A⊕B=B⊕A(Commutative Law). (c)fA⊕B=A⊕C,then B=C(Cancellation Law). (d)An(B C)=(An B)(AnC)(Distributive Law). 1.60 Consider m nonempty distinct sets A1.A2.....Am in a universal set U.Prove: (a)There are 2fundamental products of the m sets. (b)Any two fundamental products are disjoint. (c)U is the union of all the fundamental products. Answers to Supplementary Problems 1.34 See Fig.1-10. 1.26 B=C=E=F,A=D=G=H. 1.35 (a)(AnBnC)U(AnBnCC)U(AnBCnC) 1.27 A (a,e,i,o,u),B D (l,i,t,e). (b)(ACnBnCC)U(ACnBnC)U(ACnBCnC) C=a,b,c,d,el. (c)(AnBnC)U(AnBnCC)U(AnBCnc) 1.28 (a)C and E;(b)D and E;(c)A,B,and D:(d)None. U(AcnBnCC)U(AnBCncC) 129(a)AnB={2,51,AnC={1,5: b)AUB=1,2,5,6,7,BUC={1,2,3,5,7,9%: 1.36 The three premises yield the Venn diagram in Fig.1-11(a).(a)and (b)are valid,but (c)is not valid. (c)AC={3.4.7,8,9},CC={2.4,6,8}: (dAB={1,6,AC={2,6: 1.37 (a)A=(BCUA)n(AUB) (e)A⊕B={1,6,7,A⊕C={2,3,6,7,9 (0(AUC)八B={1,3,6.91,(B⊕C)八A={3,9 (b)(AUB)n(ACUB)n(AUBC)n(ACUBC)=0 1.33 AUB (ACnBC)C. 1.39 (a)Infinite;(b)finite;(c)infinite;(d)finite
CHAP. 1] SET THEORY 21 INDUCTION 1.50 Prove: 2 + 4 + 6 +···+ 2n = n(n + 1) 1.51 Prove: 1 + 4 + 7 +···+ 3n − 2 = n(3n−1) 2 1.52 Prove: 12 + 22 + 32 +···+ n2 = n(n+1)(2n+1) 6 1.53 Prove: 1 1·3 + 1 3·5 + 1 5·7 +···+ 1 (2n−1)(2n+1) = n 2n+1 1.54 Prove: 1 1·5 + 1 5·9 + 1 9·13 +···+ 1 (4n−3)(4n+1) = n 4n+1 1.55 Prove 7n − 2n is divisible by 5 for all n ∈ N 1.56 Prove n3 − 4n + 6 is divisible by 3 for all n ∈ N 1.57 Use the identity 1 + 2 + 3 +···+ n = n(n + 1)/2 to prove that 13 + 23 + 33 +···+ n3 = (1 + 2 + 3 +···+ n)2 Miscellaneous Problems 1.58 Suppose N = {1, 2, 3, …} is the universal set, and A = {n | n ≤ 6}, B = {n | 4 ≤ n ≤ 9}, C = {1, 3, 5, 7, 9}, D = {2, 3, 5, 7, 8}. Find: (a) A ⊕ B; (b) B ⊕ C; (c) A ∩ (B ⊕ D); (d) (A ∩ B) ⊕ (A ∩ D). 1.59 Prove the following properties of the symmetric difference: (a) (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (Associative Law). (b) A ⊕ B = B ⊕ A (Commutative Law). (c) If A ⊕ B = A ⊕ C, then B = C (Cancellation Law). (d) A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C) (Distributive Law). 1.60 Consider m nonempty distinct sets A1, A2, …, Am in a universal set U. Prove: (a) There are 2m fundamental products of the m sets. (b) Any two fundamental products are disjoint. (c) U is the union of all the fundamental products. Answers to Supplementary Problems 1.26 B = C = E = F, A = D = G = H. 1.27 A = {a, e, i, o, u}, B = D = {l, i, t, e}, C = {a, b, c, d, e}. 1.28 (a) C and E; (b) D and E; (c) A, B, and D; (d) None. 1.29 (a) A ∩ B = {2, 5}, A ∩ C = {1, 5}; (b) A ∪ B = {1, 2, 5, 6, 7}, B ∪ C = {1, 2, 3, 5, 7, 9}; (c) AC = {3, 4, 7, 8, 9}, CC = {2, 4, 6, 8}; (d) A\B = {1, 6}, A\C = {2, 6}; (e) A ⊕ B = {1, 6, 7}, A ⊕ C = {2, 3, 6, 7, 9}; (f) (A ∪ C)\B = {1, 3, 6, 9}, (B ⊕ C)\A = {3, 9}. 1.33 A ∪ B = (AC ∩ BC)C. 1.34 See Fig. 1-10. 1.35 (a) (A ∩ B ∩ C) ∪ (A ∩ B ∩ CC) ∪ (A ∩ BC ∩ C) (b) (AC ∩B ∩CC)∪(AC ∩B ∩C)∪(AC ∩BC ∩C) (c) (A ∩ B ∩ C) ∪ (A ∩ B ∩ CC) ∪ (A ∩ BC ∩ C) ∪(AC ∩ B ∩ CC) ∪ (A ∩ BC ∩ CC) 1.36 The three premises yield the Venn diagram in Fig. 1-11(a). (a) and (b) are valid, but (c) is not valid. 1.37 (a) A = (BC ∪ A) ∩ (A ∪ B) (b) (A ∪B)∩(AC ∪B)∩(A ∪BC)∩(AC ∪BC) = ∅ 1.39 (a) Infinite; (b) finite; (c) infinite; (d) finite
22 SET THEORY [CHAP.1 B (a) (b) (c) Fig.1-10 R useful books romance novels dictionaries Mary's books) 2 (a) (b) Fig.1-11 1.41 Use the data to fill in the Venn diagram in Fig.1-11(b).1.44 Let X be an element in P(A).For each aA,either Then: a e X or a X.Since n(A)=m,there are 2m differ- (a)5:b)4:(c)2:(d1:(e)6:(①11；(g)23:(h)2. ent sets X.That is P(A)I=2m. 1.42 P(A)has 25 =32 elements as follows: 1.45 (a)No,(b)no,(c)yes,(d)yes. [0,{1,{2,{3,{4},{5,{1,2,{1,3,{1,4},{1, 5,{2,3,{2,4},{2,5,{3,4},{3,51,{4,5,{1,2, 146 (a)No,(b)no.(c)yes.(d)no. 3,{L,2.4h,{1,25,{23,41.{2,3.5.3451.1.47(aNo,(b)n0,(@yes. {1,3.4,{1,3,5,{1,4,5},{2.4,5},{1,2,3,4}, {1,2,3,5,{1,2,4,5,{1,3.4,5,{2,3,4,5,A] 1.49[{1,3,{2,4},{5,7,{9,{6,8] 1.43 (a)Three elements:[a,b].(c).and (d.e.f).(b)3. (c)P(A)has 23 =8 elements as follows: 1.55Hint:7k+1-2k+1=7k+1-72k)+7(2k)-2k+1= 7(7k-2k+(7-2)2k P(A)=(A,[a,b).(c)].[a,b),(d.e,f)]. 1.58(a){1,2,3.7,8.9:(b){1,3,4,6,8;(c)and [c).(d,e,f)].[a.b)].[c)].[d,e,f. (d){2,3,4,6
22 SET THEORY [CHAP. 1 Fig. 1-10 Fig. 1-11 1.41 Use the data to fill in the Venn diagram in Fig. 1-11(b). Then: (a) 5; (b) 4; (c) 2; (d) 1; (e) 6; (f) 11; (g) 23; (h) 2. 1.42 P (A) has 25 = 32 elements as follows: [∅, {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {2, 3, 4}, {2, 3, 5}, {3, 4, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 4, 5}, {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, A] 1.43 (a) Three elements: [a, b], (c), and {d, e, f }. (b) 3. (c) P (A) has 23 = 8 elements as follows: P (A) = {A, [{a, b},{c}], [{a, b},{d, e, f }], [{c},{d, e, f }], [{a, b}], [{c}], [{d, e, f }], ∅} 1.44 Let X be an element in P (A). For each a ∈ A, either a ∈ X or a /∈ X. Since n(A) = m, there are 2m different sets X. That is |P (A)| = 2m. 1.45 (a) No, (b) no, (c) yes, (d) yes. 1.46 (a) No, (b) no, (c) yes, (d) no. 1.47 (a) No, (b) no, (c) yes. 1.49 [{1,3}, {2,4}, {5,7}, {9}, {6,8}] 1.55 Hint: 7k+1 −2k+1 = 7k+1 −7(2k)+7(2k)−2k+1 = 7(7k − 2k) + (7 − 2)2k 1.58 (a) {1, 2, 3, 7, 8, 9}; (b) {1, 3, 4, 6, 8}; (c) and (d) {2, 3, 4, 6}
CHAPTER 2 Relations 2.1 INTRODUCTION The reader is familiar with many relations such as"less than,.”“is parallel to,.”“is a subset of,.”and so on. In a certain sense,these relations consider the existence or nonexistence of a certain connection between pairs of objects taken in a definite order.Formally,we define a relation in terms of these "ordered pairs." An ordered pair of elements a and b,where a is designated as the first element and b as the second element, is denoted by (a,b).In particular, (a,b)=(c,d) if and only if a =c and b =d.Thus (a,b)(b,a)unless a =b.This contrasts with sets where the order of elements is irrelevant;for example,(3,5)=(5,3). 2.2 PRODUCT SETS Consider two arbitrary sets A and B.The set of all ordered pairs (a,b)where aA and bB is called the product,or Cartesian product,of A and B.A short designation of this product is A x B,which is read “A cross B.”By definition, A×B={(a,b)la∈A and b∈B} One frequently writes A2 instead of A x A. EXAMPLE 2.1 R denotes the set of real numbers and so R2=R x R is the set of ordered pairs of real numbers. The reader is familiar with the geometrical representation of R2 as points in the plane as in Fig.2-1.Here each point P represents an ordered pair (a,b)of real numbers and vice versa;the vertical line through P meets the x-axis at a,and the horizontal line through P meets the y-axis at b.R2 is frequently called the Cartesian plane. EXAMPLE 2.2 Let A =(1,2)and B=(a,b,c).Then A×B={(1,a),(1,b)(1,c),(2,a),(2,b),(2,c)} B×A={(a,1),(b,1),(c1),(a,2),(b,2),(c,2) Als0,A×A={(1,1),(1,2),(2,1),(2,2)} 23 Copyright @2007,1997,1976 by The McGraw-Hill Companies,Inc.Click here for terms of use
CHAPTER 2 Relations 2.1 INTRODUCTION The reader is familiar with many relations such as “less than,” “is parallel to,” “is a subset of,” and so on. In a certain sense, these relations consider the existence or nonexistence of a certain connection between pairs of objects taken in a definite order. Formally, we define a relation in terms of these “ordered pairs.” An ordered pair of elements a and b, where a is designated as the first element and b as the second element, is denoted by (a, b). In particular, (a, b) = (c, d) if and only if a = c and b = d. Thus (a, b) = (b, a) unless a = b. This contrasts with sets where the order of elements is irrelevant; for example, {3, 5}={5, 3}. 2.2 PRODUCT SETS Consider two arbitrary sets A and B. The set of all ordered pairs (a, b) where a ∈ A and b ∈ B is called the product, or Cartesian product, of A and B. A short designation of this product is A × B, which is read “A cross B.” By definition, A × B = {(a, b)| a ∈ A and b ∈ B} One frequently writes A2 instead of A × A. EXAMPLE 2.1 R denotes the set of real numbers and so R2 = R×R is the set of ordered pairs of real numbers. The reader is familiar with the geometrical representation of R2 as points in the plane as in Fig. 2-1. Here each point P represents an ordered pair (a, b) of real numbers and vice versa; the vertical line through P meets the x-axis at a, and the horizontal line through P meets the y-axis at b. R2 is frequently called the Cartesian plane. EXAMPLE 2.2 Let A = {1, 2} and B = {a, b, c}. Then A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)} B × A = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)} Also, A × A = {(1, 1), (1, 2), (2, 1), (2, 2)} 23 Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.