4 SET THEORY [CHAP.1 However,if A and B are two arbitrary sets,it is possible that some objects are in A but not in B,some are in B but not in A,some are in both A and B,and some are in neither A nor B;hence in general we represent A and B as in Fig.1-1(c). Arguments and Venn Diagrams Many verbal statements are essentially statements about sets and can therefore be described by Venn diagrams. Hence Venn diagrams can sometimes be used to determine whether or not an argument is valid. EXAMPLE 1.3 Show that the following argument (adapted from a book on logic by Lewis Carroll,the author of Alice in Wonderland)is valid: S:All my tin objects are saucepans. S2:I find all your presents very useful. S3:None of my saucepans is of the slightest use. S:Your presents to me are not made of tin. The statements S1,S2,and S3 above the horizontal line denote the assumptions,and the statement S below the line denotes the conclusion.The argument is valid if the conclusion S follows logically from the assumptions S1,S2,and S3. By SI the tin objects are contained in the set of saucepans,and by S3 the set of saucepans and the set of useful things are disjoint.Furthermore,by S2 the set of"your presents"is a subset of the set of useful things. Accordingly,we can draw the Venn diagram in Fig.1-2. The conclusion is clearly valid by the Venn diagram because the set of"your presents"is disjoint from the set of tin objects. tin objects your presents sauscpans useful things Fig.1-2 1.4 SET OPERATIONS This section introduces a number of set operations,including the basic operations of union,intersection,and complement. Union and Intersection The union of two sets A and B,denoted by A U B,is the set of all elements which belong to A or to B; that is, AUB={xIx∈Aorx∈B} Here"or"is used in the sense of and/or.Figure 1-3(a)is a Venn diagram in which AU B is shaded. The intersection of two sets A and B,denoted by An B,is the set of elements which belong to both A and B:that is, AnB={xlx∈A andx∈B) Figure 1-3(b)is a Venn diagram in which An B is shaded
4 SET THEORY [CHAP. 1 However, if A and B are two arbitrary sets, it is possible that some objects are in A but not in B, some are in B but not in A, some are in both A and B, and some are in neither A nor B; hence in general we represent A and B as in Fig. 1-1(c). Arguments and Venn Diagrams Many verbal statements are essentially statements about sets and can therefore be described by Venn diagrams. Hence Venn diagrams can sometimes be used to determine whether or not an argument is valid. EXAMPLE 1.3 Show that the following argument (adapted from a book on logic by Lewis Carroll, the author of Alice in Wonderland) is valid: S1: All my tin objects are saucepans. S2: I find all your presents very useful. S3: None of my saucepans is of the slightest use. S : Your presents to me are not made of tin. The statements S1, S2, and S3 above the horizontal line denote the assumptions, and the statement S below the line denotes the conclusion. The argument is valid if the conclusion S follows logically from the assumptions S1, S2, and S3. By S1 the tin objects are contained in the set of saucepans, and by S3 the set of saucepans and the set of useful things are disjoint. Furthermore, by S2 the set of “your presents” is a subset of the set of useful things. Accordingly, we can draw the Venn diagram in Fig. 1-2. The conclusion is clearly valid by the Venn diagram because the set of “your presents” is disjoint from the set of tin objects. Fig. 1-2 1.4 SET OPERATIONS This section introduces a number of set operations, including the basic operations of union, intersection, and complement. Union and Intersection The union of two sets A and B, denoted by A ∪ B, is the set of all elements which belong to A or to B; that is, A ∪ B = {x | x ∈ A or x ∈ B} Here “or” is used in the sense of and/or. Figure 1-3(a) is a Venn diagram in which A ∪ B is shaded. The intersection of two sets A and B, denoted by A ∩ B, is the set of elements which belong to both A and B; that is, A ∩ B = {x | x ∈ A and x ∈ B} Figure 1-3(b) is a Venn diagram in which A ∩ B is shaded
CHAP.1] SET THEORY 5 (a)A U B is shaded (b)A∩B is shaded Fig.1-3 Recall that sets A and B are said to be disjoint or nonintersecting if they have no elements in common or, using the definition of intersection,if AnB=0,the empty set.Suppose S=AUB and A∩B=O Then S is called the disjoint union of A and B. EXAMPLE 1.4 (a)LetA={1,2,3,4},B={3,4,5,6,7},C={2,3,8,9}.Then AUB={1,2,3,4,5,6,7},AUC={1,2,3,4,8,91,BUC={2,3,4,5,6.7,891, A∩B={3,4}, A∩C={2,3}, B∩C={3. (b)Let U be the set of students at a university,and let M denote the set of male students and let F denote the set of female students.The U is the disjoint union of M of F:that is. U=MU F and MnF=0 This comes from the fact that every student in U is either in M or in F,and clearly no student belongs to both M and F,that is,M and F are disjoint. The following properties of union and intersection should be noted. Property 1:Every element x in An B belongs to both A and B;hence x belongs to A and x belongs to B.Thus An B is a subset of A and of B;namely AnB≤A and AnB≤B Property 2:An element x belongs to the union AUB ifx belongs to A orx belongs to B:hence every element in A belongs to AU B,and every element in B belongs to AU B.That is, A≤AUB and B≤AUB We state the above results formally: Theorem 1.3:For any sets A and B,we have: (①AnB≤A≤AU B and(ii)A∩B≤B≤AUB. The operation of set inclusion is closely related to the operations of union and intersection,as shown by the following theorem. Theorem 1.4:The following are equivalent:A C B,AnB =A,AU B =B. This theorem is proved in Problem 1.8.Other equivalent conditions to are given in Problem 1.31
CHAP. 1] SET THEORY 5 Fig. 1-3 Recall that sets A and B are said to be disjoint or nonintersecting if they have no elements in common or, using the definition of intersection, if A ∩ B = ∅, the empty set. Suppose S = A ∪ B and A ∩ B = ∅ Then S is called the disjoint union of A and B. EXAMPLE 1.4 (a) Let A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 8, 9}. Then A ∪ B = {1, 2, 3, 4, 5, 6, 7}, A ∪ C = {1, 2, 3, 4, 8, 9}, B ∪ C = {2, 3, 4, 5, 6, 7, 8, 9}, A ∩ B = {3, 4}, A ∩ C = {2, 3}, B ∩ C = {3}. (b) Let U be the set of students at a university, and let M denote the set of male students and let F denote the set of female students. The U is the disjoint union of M of F; that is, U = M ∪ F and M ∩ F = ∅ This comes from the fact that every student in U is either in M or in F, and clearly no student belongs to both M and F, that is, M and F are disjoint. The following properties of union and intersection should be noted. Property 1: Every element x in A ∩B belongs to both A and B; hence x belongs to A and x belongs to B. Thus A ∩ B is a subset of A and of B; namely A ∩ B ⊆ A and A ∩ B ⊆ B Property 2: An element x belongs to the union A ∪ B if x belongs to A or x belongs to B; hence every element in A belongs to A ∪ B, and every element in B belongs to A ∪ B. That is, A ⊆ A ∪ B and B ⊆ A ∪ B We state the above results formally: Theorem 1.3: For any sets A and B, we have: (i) A ∩ B ⊆ A ⊆ A ∪ B and (ii) A ∩ B ⊆ B ⊆ A ∪ B. The operation of set inclusion is closely related to the operations of union and intersection, as shown by the following theorem. Theorem 1.4: The following are equivalent: A ⊆ B, A ∩ B = A, A ∪ B = B. This theorem is proved in Problem 1.8. Other equivalent conditions to are given in Problem 1.31
6 SET THEORY [CHAP.1 (a)Cis shaded (b)A\B is shaded (c)A⊕B is shaded Fig.1-4 Complements,Differences,Symmetric Differences Recall that all sets under consideration at a particular time are subsets of a fixed universal set U.The absolute complement or,simply,complement of a set A,denoted by AC,is the set of elements which belong to U but which do not belong to A.That is, AC={x|x∈U,x车A} Some texts denote the complement of A by A'or A.Fig.1-4(a)is a Venn diagram in which AC is shaded. The relative complement of a set B with respect to a set A or,simply,the difference of A and B,denoted by A B,is the set of elements which belong to A but which do not belong to B;that is A八B={x|x∈A,x年B) The set A B is read"A minus B."Many texts denote A B by A-B or A B.Fig.1-4(b)is a Venn diagram in which A B is shaded. The symmetric difference of sets A and B,denoted by A B,consists of those elements which belong to A or B but not to both.That is. A⊕B=(AUB)八(A∩B)orA⊕B=(A\B)U(B\A) Figure 1-4(c)is a Venn diagram in which AB is shaded. EXAMPLE 1.5 Suppose U=N=(1,2,3,...)is the universal set.Let A={1,2,3,41,B={3,4,5,6,71,C={2,3,8,91,E={2.4,6.} (Here E is the set of even integers.)Then: AC={5,6,7,,BC={1,2,8,9,10,,EC={1,3,5,7,.J That is,EC is the set of odd positive integers.Also: A\B={1,2,A\C={1,4,B\C={4,5,6,7,A\E={1,3, B\A={5,6,7),C\A={8,9,C\B={2,8,9},E\A={6,8,10,12,. Furthermore: A⊕B=(A\B)U(B\A)={1,2,5,6,7},B⊕C={2,4,5,6,7,8,9, A⊕C=(A\C)U(B\C)=1,4,8,9},A⊕E=1,36,8,10,.. Fundamental Products Consider n distinct sets A1,A2.....An.Afundamental product of the sets is a set of the form AinA2n...nA where A=A or A=AC
6 SET THEORY [CHAP. 1 Fig. 1-4 Complements, Differences, Symmetric Differences Recall that all sets under consideration at a particular time are subsets of a fixed universal set U. The absolute complement or, simply, complement of a set A, denoted by AC, is the set of elements which belong to U but which do not belong to A. That is, AC = {x | x ∈ U,x /∈ A} Some texts denote the complement of A by A or A¯. Fig. 1-4(a) is a Venn diagram in which AC is shaded. The relative complement of a set B with respect to a set A or, simply, the difference of A and B, denoted by A\B, is the set of elements which belong to A but which do not belong to B; that is A\B = {x | x ∈ A, x /∈ B} The set A\B is read “A minus B.” Many texts denote A\B by A − B or A ∼ B. Fig. 1-4(b) is a Venn diagram in which A\B is shaded. The symmetric difference of sets A and B, denoted by A ⊕ B, consists of those elements which belong to A or B but not to both. That is, A ⊕ B = (A ∪ B)\(A ∩ B) or A ⊕ B = (A\B) ∪ (B\A) Figure 1-4(c) is a Venn diagram in which A ⊕ B is shaded. EXAMPLE 1.5 Suppose U = N = {1, 2, 3,...} is the universal set. Let A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 8, 9}, E = {2, 4, 6,...} (Here E is the set of even integers.) Then: AC = {5, 6, 7,...}, BC = {1, 2, 8, 9, 10,...}, EC = {1, 3, 5, 7,...} That is, EC is the set of odd positive integers. Also: A\B = {1, 2}, A\C = {1, 4}, B\C = {4, 5, 6, 7}, A\E = {1, 3}, B\A = {5, 6, 7}, C\A = {8, 9}, C\B = {2, 8, 9}, E\A = {6, 8, 10, 12,...}. Furthermore: A ⊕ B = (A\B) ∪ (B\A) = {1, 2, 5, 6, 7}, B ⊕ C = {2, 4, 5, 6, 7, 8, 9}, A ⊕ C = (A\C) ∪ (B\C) = {1, 4, 8, 9}, A ⊕ E = {1, 3, 6, 8, 10,...}. Fundamental Products Consider n distinct sets A1, A2, …, An. A fundamental product of the sets is a set of the form A∗ 1 ∩ A∗ 2 ∩ ... ∩ A∗ n where A∗ i = A or A∗ i = AC
CHAP.1] SET THEORY 7 We note that: (i)There are m =2"such fundamental products. (ii)Any two such fundamental products are disjoint (iii)The universal set U is the union of all fundamental products. Thus U is the disjoint union of the fundamental products(Problem 1.60).There is a geometrical description of these sets which is illustrated below. EXAMPLE 1.6 Figure 1-5(a)is the Venn diagram of three sets A,B,C.The following lists the m =23 =8 fundamental products of the sets A,B,C: P1=AnBOC,P3=AnBCnC,P5=ACnBOC,P7=ACnBCnC. P2=AnBnCC,P4=AnBCnCC,P6=ACnBnCC.Ps=ACnBCnCC. The eight products correspond precisely to the eight disjoint regions in the Venn diagram of sets A,B,C as indicated by the labeling of the regions in Fig.1-5(b). B (a) (b) Fig.1-5 1.5 ALGEBRA OF SETS,DUALITY Sets under the operations of union,intersection,and complement satisfy various laws (identities)which are listed in Table 1-1.In fact,we formally state this as: Theorem 1.5:Sets satisfy the laws in Table 1-1. Table 1-1 Laws of the algebra of sets Idempotent laws: (la)AUA=A (1b)AnA=A Associative laws: (2a)(AUB)UC=AU(BUC) (2b)(AnB)∩C=An(BnC) Commutative laws: (3a)AUB=BUA (3b)AnB=B∩A Distributive laws: (4a)AU(BnC)=(AUB)n(AUC) (4b)An(BUC)=(AnB)U(AnC) Identity laws: (5a)AU0=A (5b)AnU=A (6a)AUU=U (6b)An0=0 Involution laws: (7)(AC)C=A (8a)AUAC=U (8b)AnAc=0 Complement laws: (9a)UC=0 (9b)0C=U DeMorgan's laws: (10a)(AUB)C=AcnBC (10b)(A∩B)C=ACUBC
CHAP. 1] SET THEORY 7 We note that: (i) There are m = 2n such fundamental products. (ii) Any two such fundamental products are disjoint. (iii) The universal set U is the union of all fundamental products. Thus U is the disjoint union of the fundamental products (Problem 1.60). There is a geometrical description of these sets which is illustrated below. EXAMPLE 1.6 Figure 1-5(a) is the Venn diagram of three sets A, B, C. The following lists the m = 23 = 8 fundamental products of the sets A, B, C: P1 = A ∩ B ∩ C, P3 = A ∩ BC ∩ C, P5 = AC ∩ B ∩ C, P7 = AC ∩ BC ∩ C, P2 = A ∩ B ∩ CC, P4 = A ∩ BC ∩ CC, P6 = AC ∩ B ∩ CC, P8 = AC ∩ BC ∩ CC. The eight products correspond precisely to the eight disjoint regions in the Venn diagram of sets A, B, C as indicated by the labeling of the regions in Fig. 1-5(b). Fig. 1-5 1.5 ALGEBRA OF SETS, DUALITY Sets under the operations of union, intersection, and complement satisfy various laws (identities) which are listed in Table 1-1. In fact, we formally state this as: Theorem 1.5: Sets satisfy the laws in Table 1-1. Table 1-1 Laws of the algebra of sets Idempotent laws: (1a) A ∪ A = A (1b) A ∩ A = A Associative laws: (2a) (A ∪ B) ∪ C = A ∪ (B ∪ C) (2b) (A ∩ B) ∩ C = A ∩ (B ∩ C) Commutative laws: (3a) A ∪ B = B ∪ A (3b) A ∩ B = B ∩ A Distributive laws: (4a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (4b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Identity laws: (5a) A ∪∅= A (5b) A ∩ U = A (6a) A ∪ U = U (6b) A ∩∅=∅ Involution laws: (7) (AC)C = A Complement laws: (8a) A ∪ AC = U (8b) A ∩ AC = ∅ (9a) UC = ∅ (9b) ∅C = U DeMorgan’s laws: (10a) (A ∪ B)C = AC ∩ BC (10b) (A ∩ B)C = AC ∪ BC
8 SET THEORY [CHAP.1 Remark:Each law in Table 1-1 follows from an equivalent logical law.Consider,for example,the proof of DeMorgan's Law 10(a): (AUB)C={xlx华(AorB)月={xIx年A andx年B)=AcOBC Here we use the equivalent(DeMorgan's)logical law: 一(pVq)=-p∧g where-means“not,”v means“or,”and means“and.”(Sometimes Venn diagrams are used to illustrate the laws in Table 1-1 as in Problem 1.17.) Duality The identities in Table 1-1 are arranged in pairs,as,for example,(2a)and(2b).We now consider the principle behind this arrangement.Suppose E is an equation of set algebra.The dual E*of E is the equation obtained by replacing each occurrence of U,n.U and 0 in E by n,U,0,and U,respectively.For example,the dual of (U∩A)U(B∩A)=Ais(GUA)∩(BUA)=A Observe that the pairs of laws in Table 1-1 are duals of each other.It is a fact of set algebra,called the principle of duality,that if any equation E is an identity then its dual E*is also an identity. 1.6 FINITE SETS,COUNTING PRINCIPLE Sets can be finite or infinite.A set S is said to be finite if S is empty or if S contains exactly m elements where m is a positive integer;otherwise S is infinite. EXAMPLE 1.7 (a)The set A of the letters of the English alphabet and the set D of the days of the week are finite sets.Specifically, A has 26 elements and D has 7 elements. (b)Let E be the set of even positive integers,and let I be the unit interval,that is, E={2,4,6,.}andI=[0,1]={xl0≤x≤1} Then both E and I are infinite. A set S is countable if S is finite or if the elements of S can be arranged as a sequence,in which case S is said to be countably infinite;otherwise S is said to be uncountable.The above set E of even integers is countably infinite,whereas one can prove that the unit interval I =[0,1]is uncountable. Counting Elements in Finite Sets The notation n(S)or S will denote the number of elements in a set S.(Some texts use #(S)or card(S) instead of n(S).)Thus n(A)=26,where A is the letters in the English alphabet,and n(D)=7,where D is the days of the week.Also n(0)=0 since the empty set has no elements. The following lemma applies. Lemma 1.6:Suppose A and B are finite disjoint sets.Then AU B is finite and n(AUB)=n(A)+n(B) This lemma may be restated as follows: Lemma 1.6:Suppose S is the disjoint union of finite sets A and B.Then S is finite and n(S)=n(A)+n(B)
8 SET THEORY [CHAP. 1 Remark: Each law in Table 1-1 follows from an equivalent logical law. Consider, for example, the proof of DeMorgan’s Law 10(a): (A ∪ B)C = {x | x /∈ (A or B)}={x | x /∈ A and x /∈ B} = AC ∩ BC Here we use the equivalent (DeMorgan’s) logical law: ¬(p ∨ q) = ¬p ∧ ¬q where ¬ means “not,” ∨ means “or,” and ∧ means “and.” (Sometimes Venn diagrams are used to illustrate the laws in Table 1-1 as in Problem 1.17.) Duality The identities in Table 1-1 are arranged in pairs, as, for example, (2a) and (2b). We now consider the principle behind this arrangement. Suppose E is an equation of set algebra. The dual E∗ of E is the equation obtained by replacing each occurrence of ∪, ∩, U and ∅ in E by ∩, ∪, ∅, and U, respectively. For example, the dual of (U ∩ A) ∪ (B ∩ A) = A is (∅ ∪ A) ∩ (B ∪ A) = A Observe that the pairs of laws in Table 1-1 are duals of each other. It is a fact of set algebra, called the principle of duality, that if any equation E is an identity then its dual E∗ is also an identity. 1.6 FINITE SETS, COUNTING PRINCIPLE Sets can be finite or infinite. A set S is said to be finite if S is empty or if S contains exactly m elements where m is a positive integer; otherwise S is infinite. EXAMPLE 1.7 (a) The set A of the letters of the English alphabet and the set D of the days of the week are finite sets. Specifically, A has 26 elements and D has 7 elements. (b) Let E be the set of even positive integers, and let I be the unit interval, that is, E = {2, 4, 6,...} and I = [0, 1]={x | 0 ≤ x ≤ 1} Then both E and I are infinite. A set S is countable if S is finite or if the elements of S can be arranged as a sequence, in which case S is said to be countably infinite; otherwise S is said to be uncountable. The above set E of even integers is countably infinite, whereas one can prove that the unit interval I = [0, 1] is uncountable. Counting Elements in Finite Sets The notation n(S) or |S| will denote the number of elements in a set S. (Some texts use #(S) or card(S) instead of n(S).) Thus n(A) = 26, where A is the letters in the English alphabet, and n(D) = 7, where D is the days of the week. Also n(∅) = 0 since the empty set has no elements. The following lemma applies. Lemma 1.6: Suppose A and B are finite disjoint sets. Then A ∪ B is finite and n(A ∪ B) = n(A) + n(B) This lemma may be restated as follows: Lemma 1.6: Suppose S is the disjoint union of finite sets A and B. Then S is finite and n(S) = n(A) + n(B)