CHAP.1] SET THEORY 9 Proof.In counting the elements of AU B,first count those that are in A.There are n(A)of these.The only other elements of AU B are those that are in B but not in A.But since A and B are disjoint,no element of B is in A, so there are n(B)elements that are in B but not in A.Therefore,n(AU B)=n(A)+n(B). For any sets A and B,the set A is the disjoint union of A\B and An B.Thus Lemma 1.6 gives us the following useful result. Corollary 1.7:Let A and B be finite sets.Then n(A\B)=n(A)-n(A∩B) For example,suppose an art class A has 25 students and 10 of them are taking a biology class B.Then the number of students in class A which are not in class B is: n(A\B)=(A)-n(A∩B)=25-10=15 Given any set A,recall that the universal set U is the disjoint union of A and AC.Accordingly,Lemma 1.6 also gives the following result. Corollary 1.8:Let A be a subset of a finite universal set U.Then n(AC)=n(U)-n(A) For example,suppose a class U with 30 students has 18 full-time students.Then there are 30-18 =12 part-time students in the class U. Inclusion-Exclusion Principle There is a formula for n(A U B)even when they are not disjoint,called the Inclusion-Exclusion Principle. Namely: Theorem(Inclusion-Exclusion Principle)1.9:Suppose A and B are finite sets.Then A U B and A n B are finite and n(AUB)=n(A)+n(B)-n(AnB) That is,we find the number of elements in A or B (or both)by first adding n(A)and n(B)(inclusion)and then subtracting n(An B)(exclusion)since its elements were counted twice. We can apply this result to obtain a similar formula for three sets: 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(AnC)-n(B∩C)+n(A∩B∩C) Mathematical induction(Section 1.8)may be used to further generalize this result to any number of finite sets. EXAMPLE 1.8 Suppose a list A contains the 30 students in a mathematics class,and a list B contains the 35 students in an English class,and suppose there are 20 names on both lists.Find the number of students: (a)only on list A,(b)only on list B,(c)on list A or B (or both),(d)on exactly one list. (a)List A has 30 names and 20 are on list B;hence 30-20 10 names are only on list A. (b)Similarly,35-20=15 are only on list B. (c)We seek n(AU B).By inclusion-exclusion. n(AUB)=n(A)+n(B)-n(A∩B)=30+35-20=45, In other words,we combine the two lists and then cross out the 20 names which appear twice. (d)By (a)and (b),10+15 =25 names are only on one list;that is,n(A B)=25
CHAP. 1] SET THEORY 9 Proof. In counting the elements of A ∪ B, first count those that are in A. There are n(A) of these. The only other elements of A ∪ B are those that are in B but not in A. But since A and B are disjoint, no element of B is in A, so there are n(B) elements that are in B but not in A. Therefore, n(A ∪ B) = n(A) + n(B). For any sets A and B, the set A is the disjoint union of A\B and A ∩ B. Thus Lemma 1.6 gives us the following useful result. Corollary 1.7: Let A and B be finite sets. Then n(A\B) = n(A) − n(A ∩ B) For example, suppose an art class A has 25 students and 10 of them are taking a biology class B. Then the number of students in class A which are not in class B is: n(A\B) = n(A) − n(A ∩ B) = 25 − 10 = 15 Given any set A, recall that the universal set U is the disjoint union of A and AC. Accordingly, Lemma 1.6 also gives the following result. Corollary 1.8: Let A be a subset of a finite universal set U. Then n(AC) = n(U) − n(A) For example, suppose a class U with 30 students has 18 full-time students. Then there are 30−18 = 12 part-time students in the class U. Inclusion–Exclusion Principle There is a formula for n(A ∪ B) even when they are not disjoint, called the Inclusion–Exclusion Principle. Namely: Theorem (Inclusion–Exclusion Principle) 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) That is, we find the number of elements in A or B (or both) by first adding n(A) and n(B) (inclusion) and then subtracting n(A ∩ B) (exclusion) since its elements were counted twice. We can apply this result to obtain a similar formula for three sets: 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) Mathematical induction (Section 1.8) may be used to further generalize this result to any number of finite sets. EXAMPLE 1.8 Suppose a list A contains the 30 students in a mathematics class, and a list B contains the 35 students in an English class, and suppose there are 20 names on both lists. Find the number of students: (a) only on list A, (b) only on list B, (c) on list A or B (or both), (d) on exactly one list. (a) List A has 30 names and 20 are on list B; hence 30 − 20 = 10 names are only on list A. (b) Similarly, 35 − 20 = 15 are only on list B. (c) We seek n(A ∪ B). By inclusion–exclusion, n(A ∪ B) = n(A) + n(B) − n(A ∩ B) = 30 + 35 − 20 = 45. In other words, we combine the two lists and then cross out the 20 names which appear twice. (d) By (a) and (b), 10 + 15 = 25 names are only on one list; that is, n(A ⊕ B) = 25
10 SET THEORY [CHAP.1 1.7 CLASSES OF SETS,POWER SETS,PARTITIONS Given a set S,we might wish to talk about some of its subsets.Thus we would be considering a set of sets. Whenever such a situation occurs,to avoid confusion,we will speak of a class of sets or collection of sets rather than a set of sets.If we wish to consider some of the sets in a given class of sets,then we speak of subclass or subcollection. EXAMPLE 1.9 Suppose S=(1,2,3,4). (a)Let A be the class of subsets of S which contain exactly three elements of S.Then A=[{1,2,3},{1,2,4},{1,3,4,{2,3,4] That is,the elements of A are the sets (1,2,3,(1,2,4),(1,3,4),and (2,3,4). (b)Let B be the class of subsets of S,each which contains 2 and two other elements of S.Then B=[{1,2,3},{1,2,4},{2,3,4] The elements of B are the sets (1,2,3),(1,2,4),and (2,3,4).Thus B is a subclass of A,since every element of B is also an element of A.(To avoid confusion,we will sometimes enclose the sets of a class in brackets instead of braces.) Power Sets For a given set S,we may speak of the class of all subsets of S.This class is called the power set of S,and will be denoted by P(S).If S is finite,then so is P(S).In fact,the number of elements in P(S)is 2 raised to the power n(S).That is, n(P(S)=2n(9 (For this reason,the power set of S is sometimes denoted by 25.) EXAMPLE 1.10 Suppose S=(1,2,3).Then P(S)=[0,{1},{2},{3},{1,2,{1,3,{2,3,S Note that the empty set 0 belongs to P(S)since 0 is a subset of S.Similarly,S belongs to P(S).As expected from the above remark,P(S)has 23 =8 elements. Partitions Let S be a nonempty set.A partition of S is a subdivision of S into nonoverlapping,nonempty subsets. Precisely,a partition of S is a collection [Ai)of nonempty subsets of S such that: (i)Each a in S belongs to one of the Ai. (ii)The sets of (Ai}are mutually disjoint;that is,if Aj≠Ak then AjnAk= The subsets in a partition are called cells.Figure 1-6 is a Venn diagram of a partition of the rectangular set S of points into five cells,A1,A2,A3,A4,A5
10 SET THEORY [CHAP. 1 1.7 CLASSES OF SETS, POWER SETS, PARTITIONS Given a set S, we might wish to talk about some of its subsets. Thus we would be considering a set of sets. Whenever such a situation occurs, to avoid confusion, we will speak of a class of sets or collection of sets rather than a set of sets. If we wish to consider some of the sets in a given class of sets, then we speak of subclass or subcollection. EXAMPLE 1.9 Suppose S = {1, 2, 3, 4}. (a) Let A be the class of subsets of S which contain exactly three elements of S. Then A = [{1, 2, 3},{1, 2, 4},{1, 3, 4},{2, 3, 4}] That is, the elements of A are the sets {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. (b) Let B be the class of subsets of S, each which contains 2 and two other elements of S. Then B = [{1, 2, 3},{1, 2, 4},{2, 3, 4}] The elements of B are the sets {1, 2, 3}, {1, 2, 4}, and {2, 3, 4}. Thus B is a subclass of A, since every element of B is also an element of A. (To avoid confusion, we will sometimes enclose the sets of a class in brackets instead of braces.) Power Sets For a given set S , we may speak of the class of all subsets of S. This class is called the power set of S , and will be denoted by P(S). If S is finite, then so is P(S). In fact, the number of elements in P(S) is 2 raised to the power n(S). That is, n(P (S)) = 2n(S) (For this reason, the power set of S is sometimes denoted by 2S.) EXAMPLE 1.10 Suppose S = {1, 2, 3}. Then P (S) = [∅,{1},{2},{3},{1, 2},{1, 3},{2, 3}, S] Note that the empty set ∅ belongs to P(S) since ∅ is a subset of S. Similarly, S belongs to P(S). As expected from the above remark, P(S) has 23 = 8 elements. Partitions Let S be a nonempty set. A partition of S is a subdivision of S into nonoverlapping, nonempty subsets. Precisely, a partition of S is a collection {Ai} of nonempty subsets of S such that: (i) Each a in S belongs to one of the Ai. (ii) The sets of {Ai} are mutually disjoint; that is, if Aj = Ak then Aj ∩ Ak = ∅ The subsets in a partition are called cells. Figure 1-6 is a Venn diagram of a partition of the rectangular set S of points into five cells, A1, A2, A3, A4, A5.
CHAP.1] SET THEORY 11 A A2 Fig.1-6 EXAMPLE 1.11 Consider the following collections of subsets of S=(1,2,....8.9): ()[{1,3,5},{2,6},{4,8,9] (i)[{1,3,5,{2,4,68,{5,7,9] (i)[{1,3,5},{2,4,6,8},{7,9] Then (i)is not a partition of S since 7 in S does not belong to any of the subsets.Furthermore,(ii)is not a partition of S since (1,3,5)and (5,7,9)are not disjoint.On the other hand,(iii)is a partition of S. Generalized Set Operations The set operations of union and intersection were defined above for two sets.These operations can be extended to any number of sets,finite or infinite,as follows. Consider first a finite number of sets,say,A1,A2....,Am.The union and intersection of these sets are denoted and defined,respectively,by A1 U A2 U...UAm =UPIAi=xx E Ai for some Ai} A1nA2n..nAm=∩1Ai={rlx∈Ai for every Ai That is,the union consists of those elements which belong to at least one of the sets,and the intersection consists of those elements which belong to all the sets. Now let .o/be any collection of sets.The union and the intersection of the sets in the collection A is denoted and defined,respectively,by U(AlA∈)={xlx∈Ai for some Ai∈) ∩(AA∈)={xlx∈Ai for every A:∈) That is,the union consists of those elements which belong to at least one of the sets in the collection and the intersection consists of those elements which belong to every set in the collection A. EXAMPLE 1.12 Consider the sets A1={1,2,3,.}=N,A2={2,3,4,,A3={3,4,5,,Am={n,n+1,n+2,小 Then the union and intersection of the sets are as follows: U(AkIk∈N)=Nand∩(AkIk∈N)= DeMorgan's laws also hold for the above generalized operations.That is: Theorem 1.11:Let .o be a collection of sets.Then: )[U(A|A∈]'=∩(AC1A∈ ([∩(A1A∈)]C=U(ACIA∈4)
CHAP. 1] SET THEORY 11 Fig. 1-6 EXAMPLE 1.11 Consider the following collections of subsets of S = {1, 2, . . ., 8, 9}: (i) [{1, 3, 5}, {2, 6}, {4, 8, 9}] (ii) [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}] (iii) [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}] Then (i) is not a partition of S since 7 in S does not belong to any of the subsets. Furthermore, (ii) is not a partition of S since {1, 3, 5} and {5, 7, 9} are not disjoint. On the other hand, (iii) is a partition of S. Generalized Set Operations The set operations of union and intersection were defined above for two sets. These operations can be extended to any number of sets, finite or infinite, as follows. Consider first a finite number of sets, say, A1, A2, . . ., Am. The union and intersection of these sets are denoted and defined, respectively, by A1 ∪ A2 ∪ ... ∪ Am = m i=1 Ai = {x | x ∈ Ai for some Ai} A1 ∩ A2 ∩ ... ∩ Am = m i=1 Ai = {x | x ∈ Ai for every Ai} That is, the union consists of those elements which belong to at least one of the sets, and the intersection consists of those elements which belong to all the sets. Now let A be any collection of sets. The union and the intersection of the sets in the collection A is denoted and defined, respectively, by (A|A ∈ A ) = {x | x ∈ Ai for some Ai ∈ A } (A|A ∈ A ) = {x | x ∈ Ai for every Ai ∈ A } That is, the union consists of those elements which belong to at least one of the sets in the collection A and the intersection consists of those elements which belong to every set in the collection A. EXAMPLE 1.12 Consider the sets A1 = {1, 2, 3,...} = N, A2 = {2, 3, 4,...}, A3 = {3, 4, 5,...}, An = {n, n + 1, n + 2,...}. Then the union and intersection of the sets are as follows: (Ak | k ∈ N) = N and (Ak | k ∈ N) = ∅ DeMorgan’s laws also hold for the above generalized operations. That is: Theorem 1.11: Let A be a collection of sets. Then: (i) (A | A ∈ A ) C = (AC | A ∈ A ) (ii) (A | A ∈ A ) C = (AC | A ∈ A )
12 SET THEORY [CHAP.1 1.8 MATHEMATICAL INDUCTION An essential property of the set N={1,2,3,...]of positive integers follows: Principle of Mathematical Induction I:Let P be a proposition defined on the positive integers N;that is,P(n) is either true or false for each n EN.Suppose P has the following two properties: (i)P(1)is true. (ii)P(k+1)is true whenever P(k)is true. Then P is true for every positive integer n E N. We shall not prove this principle.In fact,this principle is usually given as one of the axioms when N is developed axiomatically. EXAMPLE 1.13 Let P be the proposition that the sum of the first n odd numbers is n2;that is, P(n):1+3+5+…+(2n-1)=n2 (The kth odd number is 2k-1,and the next odd number is 2k+1.)Observe that P(n)is true for n 1;namely, P(I)=12 Assuming P(k)is true,we add 2k+1 to both sides of P(k),obtaining 1+3+5+..+(2k-1)+(2k+1)-k2+(2k+1)=(k+1)2 which is P(k+1).In other words,P(k+1)is true whenever P(k)is true.By the principle of mathematical induction,P is true for all n. There is a form of the principle of mathematical induction which is sometimes more convenient to use. Although it appears different,it is really equivalent to the above principle of induction. Principle of Mathematical Induction II:Let P be a proposition defined on the positive integers N such that: (i)P(1)is true. (ii)P(k)is true whenever P(j)is true for all 1<j<k. Then P is true for every positive integer nE N. Remark:Sometimes one wants to prove that a proposition P is true for the set of integers {a,a+1,a+2,a+3,} where a is any integer,possibly zero.This can be done by simply replacing 1 by a in either of the above Principles of Mathematical Induction. Solved Problems SETS AND SUBSETS 1.1 Which of these sets are equal:(x,y,)(y,,x),[y,x,y,](y,z,x,y)? They are all equal.Order and repetition do not change a set. 1.2 List the elements of each set where N=(1,2,3,...). (a)A={x∈NI3<x<9} (b)B=xENx is even,x<11
12 SET THEORY [CHAP. 1 1.8 MATHEMATICAL INDUCTION An essential property of the set N = {1, 2, 3, …} of positive integers follows: Principle of Mathematical Induction I: Let P be a proposition defined on the positive integers N; that is, P(n) is either true or false for each n ∈ N. Suppose P has the following two properties: (i) P(1) is true. (ii) P (k + 1) is true whenever P (k) is true. Then P is true for every positive integer n ∈ N. We shall not prove this principle. In fact, this principle is usually given as one of the axioms when N is developed axiomatically. EXAMPLE 1.13 Let P be the proposition that the sum of the first n odd numbers is n2; that is, P (n) : 1 + 3 + 5 +···+ (2n − 1) = n2 (The kth odd number is 2k − 1, and the next odd number is 2k + 1.) Observe that P(n) is true for n = 1; namely, P (1) = 12 Assuming P(k) is true, we add 2k + 1 to both sides of P(k), obtaining 1 + 3 + 5 +···+ (2k − 1) + (2k + 1) − k2 + (2k + 1) = (k + 1) 2 which is P (k + 1). In other words, P (k + 1) is true whenever P (k) is true. By the principle of mathematical induction, P is true for all n. There is a form of the principle of mathematical induction which is sometimes more convenient to use. Although it appears different, it is really equivalent to the above principle of induction. Principle of Mathematical Induction II: Let P be a proposition defined on the positive integers N such that: (i) P (1) is true. (ii) P (k) is true whenever P (j ) is true for all 1 ≤ j<k. Then P is true for every positive integer n ∈ N. Remark: Sometimes one wants to prove that a proposition P is true for the set of integers {a, a + 1, a + 2, a + 3,...} where a is any integer, possibly zero. This can be done by simply replacing 1 by a in either of the above Principles of Mathematical Induction. Solved Problems SETS AND SUBSETS 1.1 Which of these sets are equal: {x, y, z}, {z, y, z, x}, {y, x, y, z}, {y, z, x, y}? They are all equal. Order and repetition do not change a set. 1.2 List the elements of each set where N = {1, 2, 3, …}. (a) A = {x ∈ N | 3 <x< 9} (b) B = {x ∈ N | x is even, x < 11}
CHAP.1] SET THEORY 13 (c)C={x∈N|4+x=3} (a)A consists of the positive integers between 3 and 9;hence A=(4.5,6.7.8). (b)B consists of the even positive integers less than 11:hence B=(2,4,6,8,10). (c)No positive integer satisfies 4+x=3;hence C=0,the empty set. 1.3LetA={2,3,4,5 (a)Show that A is not a subset of B =[x ENIx is even). (b)Show that A is a proper subset of C=(1,2,3,...,8,9). (a)It is necessary to show that at least one element in A does not belong to B.Now 3 A and,since B consists of even numbers,3 B;hence A is not a subset of B. (b)Each element of A belongs to C so A CC.On the other hand,1 C but 1A.Hence A C.Therefore A is a proper subset of C. SET OPERATIONS 1.4 Let U=(1,2,...,9)be the universal set,and let A={1,2,3,4,5,C={5,6,7,8,91,E={2,4,6,8}, B=4,5,6,71,D=1,3,5,7,91,F={1,5,9. Find:(a)AUB and An B;(b)AUC and An C;(c)DU F and DnF. Recall that the union XUY consists of those elements in either X or Y(or both),and that the intersection XnY consists of those elements in both X and Y. (a)AUB={1,2,3,4,5,6,7}and AnB={4,5 (b)AUC={1,2.3,4,5,6.7,8,9}=U and AnC={5) (c)DUF={l,3,5,7,9外=D and DnF=(1,5,9)=F Observe that F C D,so by Theorem 1.4 we must have DUF=D and DnF =F. 1.5 Consider the sets in the preceding Problem 1.4.Find: (a)AC,BC,DC,EC;(b)A\B,B\A,D\E;(c)A⊕B,C⊕D,E⊕F. Recall that: (1)The complements XC consists of those elements in U which do not belong to X. (2)The difference X\Y consists of the elements in X which do not belong to Y. (3)The symmetric difference X Y consists of the elements in X or in Y but not in both. Therefore: (@)AC={6,7,8.95;BC={1,2,3,8,9:DC={2,4,6n8}=E:EC={1,3,5,7,9}=D (b)A\B={1,2,3h:B\A={6,7:D八E={1,3,5,7,9}=D:F\D=0. (c)A⊕B={1,2,3,6,7:C⊕D={1,3,6,8:E⊕F={2,4,68.1,5,9=EUF 1.6 Show that we can have:(a)AnB=AnC without B C;(b)AUB=AUC without B =C. (a)Let A =(1,2),B =(2,3).C=(2.4).Then An B =(2)and AnC =(2);but B C. (b)Let A=(1,2),B=(1,3),C=(2,3).Then AUB=(1,2.3)and AUC=(1,2.3)but B#C. 1.7 Prove:B\A =BnAC.Thus,the set operation of difference can be written in terms of the operations of intersection and complement. B\A={x|x∈B,x年A}={x|x∈B,x∈AC=BnAC
CHAP. 1] SET THEORY 13 (c) C = {x ∈ N | 4 + x = 3} (a) A consists of the positive integers between 3 and 9; hence A = {4, 5, 6, 7, 8}. (b) B consists of the even positive integers less than 11; hence B = {2, 4, 6, 8, 10}. (c) No positive integer satisfies 4 + x = 3; hence C = ∅, the empty set. 1.3 Let A = {2, 3, 4, 5}. (a) Show that A is not a subset of B = {x ∈ N | x is even}. (b) Show that A is a proper subset of C = {1, 2, 3, . . ., 8, 9}. (a) It is necessary to show that at least one element in A does not belong to B. Now 3 ∈ A and, since B consists of even numbers, 3 ∈/ B; hence A is not a subset of B. (b) Each element of A belongs to C so A ⊆ C. On the other hand, 1 ∈ C but 1 ∈/ A. Hence A = C. Therefore A is a proper subset of C. SET OPERATIONS 1.4 Let U = {1,2, …, 9} be the universal set, and let A = {1, 2, 3, 4, 5}, C = {5, 6, 7, 8, 9}, E = {2, 4, 6, 8}, B = {4, 5, 6, 7}, D = {1, 3, 5, 7, 9}, F = {1, 5, 9}. Find: (a) A ∪ B and A ∩ B; (b) A ∪ C and A ∩ C; (c) D ∪ F and D ∩ F. Recall that the union X ∪Y consists of those elements in either X or Y (or both), and that the intersection X ∩Y consists of those elements in both X and Y . (a) A ∪ B = {1, 2, 3, 4, 5, 6, 7} and A ∩ B = {4, 5} (b) A ∪ C = {1, 2, 3, 4, 5, 6, 7, 8, 9} = U and A ∩ C = {5} (c) D ∪ F = {1, 3, 5, 7, 9} = D and D ∩ F = (1, 5, 9) = F Observe that F ⊆ D, so by Theorem 1.4 we must have D ∪ F = D and D ∩ F = F. 1.5 Consider the sets in the preceding Problem 1.4. Find: (a) AC, BC, DC, EC; (b) A\B,B\A, D\E; (c)A ⊕ B, C ⊕ D, E ⊕ F. Recall that: (1) The complements XC consists of those elements in U which do not belong to X. (2) The difference X\Y consists of the elements in X which do not belong to Y . (3) The symmetric difference X ⊕ Y consists of the elements in X or in Y but not in both. Therefore: (a) AC = {6, 7, 8, 9}; BC = {1, 2, 3, 8, 9}; DC = {2, 4, 6, 8} = E; EC = {1, 3, 5, 7, 9} = D. (b) A\B = {1, 2, 3}; B\A = {6, 7}; D\E = {1, 3, 5, 7, 9} = D; F\D = ∅. (c) A ⊕ B = {1, 2, 3, 6, 7}; C ⊕ D = {1, 3, 6, 8}; E ⊕ F = {2, 4, 6, 8, 1, 5, 9} = E ∪ F. 1.6 Show that we can have: (a) A ∩ B = A ∩ C without B = C; (b) A ∪ B = A ∪ C without B = C. (a) Let A = {1, 2}, B = {2, 3}, C = {2, 4}. Then A ∩ B = {2} and A ∩ C = {2}; but B = C. (b) Let A = {1, 2}, B = {1, 3}, C = {2, 3}. Then A ∪ B = {1, 2, 3} and A ∪ C = {1, 2, 3} but B = C. 1.7 Prove: B\A = B ∩ AC. Thus, the set operation of difference can be written in terms of the operations of intersection and complement. B\A = {x | x ∈ B, x /∈ A}={x | x ∈ B, x ∈ AC} = B ∩ AC.