Set Theory Notes PDF

LECTURE ONE SET THEORY Lecture Outlines 1.1 Introduction 1.2 Objectives 1.3 Definitions of Set Concepts 1.4 Set Operations and Set Algebra 1.5 Summary 1.1 Introduction Welcome to the F...

LECTURE ONE SET THEORY Lecture Outlines 1.1 Introduction 1.2 Objectives 1.3 Definitions of Set Concepts 1.4 Set Operations and Set Algebra 1.5 Summary 1.1 Introduction Welcome to the First Lecture in this course unit. In this lecture we are going to learn about set theory. The study of sets is important and thus popular in the business and economic world for three major reasons: - Basic understanding of concepts in sets and set algebra provides a form of logical language through which business specialists can communicate important concepts and ideas. - Set algebra is used in solving counting problems of a logical nature. - The study of set algebra provides a solid background to understanding of probability and statistics, which are important business decision-making tools. 1.2 Objectives At the end of this lecture you should be able to: 1. Define a set and set concepts. 2. Use venn diagrams to illustrate sets 3. Perform set operations 1.3 Definitions and Basic Concepts 1. Definition of a set: A set is a well-defined collection or group of objects. For instance, - Set of all courses offered at the School of Business, University of Nairobi. 1  - Set of all European manufactured Mobile Phones in Kenya. - Set of all female students pursuing a medical degree in Kenyan Universities. These objects are also referred to as members or elements of a set. Requirements of a set (i) A set must be well defined i.e. it must not leave any room for ambiguities e.g. Set of all students. This raises such questions as which students? Where are these students? What is the time frame, i.e. when? A well defined set could be a: Set of all female students pursuing a medical degree in Kenyan Universities in the year 2010. (ii) The elements of a given set must be distinct i.e. each object will appear once and once only. This means that an element must appear but only once. The following therefore does not qualify to be a set since the element 2 is repeated: {1, 2, 4, 2, 7}. The correct set is {1, 2, 4, 7} (iii) The order of presenting the elements of a set is immaterial. Thus the following four sets are the same: {1, 3, 2} = {1, 2, 3} = {3, 2, 1} = {2, 1, 3} 2. Specifying or naming of sets By convention, sets are specified (named) using a capital letter. Further, the elements of a set are designated by either listing all the elements or by using a descriptive characteristic or pattern. The elements of a set are enclosed using curly brackets. For example, consider the set of whole numbers from 0 to 6, inclusive. We can represent them in 3 ways as follows: - Listing of all elements A = {0, 1, 2, 3, 4, 5, 6} - Using a descriptive characteristic A = {X such that X is a positive integer from 0 to 6, inclusive} - Using a pattern 2  A = {0, 1, 2 - - - - - 6} 3. Set membership Set membership is expressed by using the Greek letter epsilon; є. Consider set A above (used to illustrate naming of sets) in which 3 is a member. This is expressed as: 3 є A This can also be used in a plural sense as follows: 0, 5, 1 є A (zero, five and one are members of set A) 4. Finite set This is a set that consists of a limited or countable number of elements e.g. set A above because it has 7 elements. An infinite set therefore consists of an unlimited or uncountable number of members, e.g. set of all odd numbers. 5. Subset Any set say S is a subset of set A above if all elements in S are members of A. It is denoted using the symbol;  E.g. S  A which is read as “Set S is a subset of set A” If S = {1, 5} then S  A. Recall A = {0, 1, 2, 3, 4, 5, 6} Equally, set A is said to be the superset to set S and is denoted using the symbol;  Hence, A  S 6. Equality of sets If all elements in set D1 are also in D2 and all elements in D2 are also in D1, then; sets D1 and D2 are equal, that is, D1 = D2 e.g. If D1 = { a, c, f } and D2 = {c, f, a } then D1 = D2 3 Further, D1  D2 and D2  D1, that is, each set is a subset and superset to itself. 7. Universal set. It is that set which contains all elements under consideration by the analyst or researcher and id denoted by the symbol; U For example if U = {all University of Nairobi students), we can have the following subsets: S1 = {students at Lower Kabete campus} S2 = {Male students} S3 = {Students studying Engineering} 8. Null or empty set This is a set with no elements. It is denoted by the notation; { } or  where  is the Greek letter phi. A good example would be a set of living human beings who are over 200 years old. Since we cannot find such a person, this is said to be an empty set. 9. Complement of a set If U  Universal set and A is a subset of the universal set, then, the complement of A, denoted AI or AC represents all elements in the universal set which are not members of set A. E.g If A = {whole numbers from 0 to 6} and U= {whole numbers from 0 to 10} then AI = {7, 8, 9, 10} 10. Sets are pictorially represented using Venn diagrams (so named after the 18th Century English logician, John Venn) Symbols Circle: (is used to represent an Ordinary set ((not a universal set) 4  Rectangle is used to represent the Universal set Example: Consider the previous universal set and set A U A 7 0 1 2 3 4 5 6 8 9 10 11. Singleton set This is a set with only 1 element, e.g. set of current Vice chancellors of University of Nairobi has only 1 member 12. Disjoint sets These are sets which have nothing in common, e.g. if X = {a b, c} and Y = {p, q, r, s} Then: x & y are disjoint sets x y a b pq c rs 1.4 Set Operations and Set Algebra These consist of ways or operations whereby sets are combined in order to obtain other sets of interest. This gives rise to set algebra. The operations are union, intersection, difference and symmetric difference. Basic set operations Let P = {1, 3, 2} Q = {1, 3, 5, 6} 5 1. Union of sets, denoted; U This consists of all elements in P or Q or both P and Q P U Q = {1, 3, 2, 5, 6} PUQ Note: The wanted region is the one that is shaded 2. Intersection of sets, denoted; ∩ This consists of elements in both sets P and Q (the common elements) P ∩ Q = {1, 3} P∩Q 3. Set Difference – Also known as set injunction, denoted (  ) i) P – Q Consists of elements in P but not Q P Q P – Q = {2} ii) Q – P Consists of elements in Q but not P. Q – P = {5, 6} P Q 4. Symmetric difference The symmetric difference between the two sets, P and Q consists of elements that are in P but not in Q or elements in Q but not in P denoted using the Greek letter delta, ∆. Hence P ∆ Q = {elements in P – Q or Q – P} 6  Note: P ∆ Q = (P U Q) – (P ∩ Q) In the illustration, P ∆ Q = {2, 5, 6} Venn diagram for P ∆ Q P ∆Q 1.5 Summary This chapter has introduced you to set concepts and their importance. We have also studied four mathematical operations which are permissible in set theory. In the next lecture, we will continue with the study of sets and in particular, their applications. 7  LECTURE TWO APPLICATION OF SET THEORY Lecture Outlines 2.1 Introduction 2.2 Objectives 2.3 Laws of Set Algebra 2.4 Counting Problems of A Logical Nature 2.5 Summary 2.1 Introduction Welcome to our Second Lecture. This is a continuation of the first lecture on sets. In particular, we will learn about the consequences of set operations and their business uses. Objectives 2.2 At the end of this lecture, you should be able to: 1. Explain the laws of set algebra. 2. Solve logical counting problems. Laws of Set Algebra Arising from the set operations we learned in lecture one, we have the following laws of sets: 1. Commutative laws For any two sets P and Q, i) PQ = Q  P The order in which sets are combined with union or intersection is irrelevant ii) P  Q = Q  P 2. Associative laws For any three sets P, Q and R, i) (P  Q)  R = P (Q  R) The selection of 3 or more sets for grouping in a union or intersection is immaterial. ii) P (Q  R) = (P Q) R 8 3. Distributive laws For any three sets P, Q and R, i) P (Q  R) = (P  Q)  (P  R) ii) P (Q  R) = (P  Q)  (P  R) 4. Idempotent laws For any set Q, i) Q  Q = Q The union or intersection of a set with itself does not change the set. ii) Q  Q = Q Other laws 5. P = P 6. P =  7. PU = U 8. PU = P 9. P  P’ =  10. P  P’ = U 11. De Morgan’s laws For any two sets Q and R, i) (Q  R)I = Q I  R I ii) (Q  R) I = Q I  R I Activity 2.1 1. Rewrite the following: i) (A I  B I) I ii) (A I  B I) I 2. Simplify the following: i) (A  B)  (A  B) ii) P  (P I  Q) 9 3. The sets L, M and N in a universal set consisting of the first 10 lower-case letters of the alphabet are L = {a, b, c} M = {b, c, a, e} N = {a, d, e, f} Required: Determine members of the following sets: i) M  N ii) LN iii) L’ iv) L  M  N’ v) (L M  N)’ vi) M N Solution  = {a, b, c, d, e, f, g, h, i, j} L M b, c a e d, f N i) M  N = {b, c, a, e}  { a, d, e, f} = {a, b, c, d, e, f} ii) L  N {a, b, c}  { a, d, e, f} = {a, b, c, d, e, f} iii) LI = {d, e, f, g, h, i, j} iv) L  M  NI = {b, c} v) (L  M  N)I = {g, h, i, j} 10 vi) M  N ={a, e } 2.4 Counting Problems of A Logical Nature Number of elements in a set Two sets For any set S, if S contains K elements, we show this as: n (S) = K, e.g. If S has the elements as follows: n = {10, 0, 17, 2, 12} n (S) = 5 Generally, given any 2 sets S1 and S2 1. n (S1  S2) = n (S1) + n (S2) – n (S1 S2). We have to subtract the number of elements in the intersection to avoid counting them twice. Note, however, that if S1 and S2 are disjoint sets, then: n (S1  S2) = n (S1) + n (S2) since n (S1 nS2 ) = 0 Since S1 n S1 = Ø S1 S2 2. For symmetric difference, n (S1 ∆ S2) = n (S1  S2) - n (S1  S2) Example In a recent survey of 400 students in a college, 100 were listed as studying typing (T) and 150 were listed as doing accountancy (A). 75 were registered for both courses. 11  Required: a) Find the number of students in the college who are not registered for either course. b) How many students were registered for typing only? Solution: n() = 400 A T n (u) = 400 n (T) = 100 75 75 25 n (A) = 150 n (TA) = 75 225 (a) Number of students not registered for either course are 225. (b) Number of students registered for typing only are 25. Three sets When solving logical counting problems involving 3 sets, it is conveniently done by use of a Venn diagram. Assign unknowns to all parts of the Venn diagram and using the known values, we can solve for the values of the unknowns in a series of linear equations. Example A survey was conducted on the newspaper readership of 3 dailies; the Mirror, the Citizen and the Times, M, C, T respectively and the following data was obtained: The number of people who read M, C & T was found to be 55, 45 and 39 respectively. The number that read M & T = 19 The number that read C & M = 15 The number that read C & T = 14 Those who read all the 3 were found to be 4 people only. Required: 12 Determine the number of people who: a) Read the Mirror only. b) Read Citizen or Times but not the Mirror c) The total number of people interviewed if 5 people read none of the papers. Solution: We use a Venn diagram to give symbols for the unknowns for all parts as follows:- Mirror Times Citizen From the information given, we find that: n(M) = b + c + d + e = 55……(1) n(C ) = c + e + h + g = 45 ……(2) n(T) = d + e + f + g = 39….. (3) Further, n(MnT) = d + e + = 19 ….(4) n(CnM) = c + e = 15 ……(5) n(CnT) = e + g = 14…..(6) n(MnCnT) = e = 4 Given that we know the value of e, we can solve for the following: d = 19 - 4 = 15…….using equation (4) c = 15 - 4 = 11….... “ “ (5) g = 14 - 4 = 10 …… “ “ (6) 13 Using equation (1), we find that : b = 55 - (11 + 15 + 4) = 15 Using equation (2): h = 45 - (11 + 4 + 10) = 20 Using equation (3): f = 39 - (15 + 4 + 10) = 10 If 5 people read none of the three dailies, then a = 5 Let us now answer specific questions asked: a) n(M only) = b = 5 b) n(C or T but not M) = 20 + 10 + 10 = 4 c) n(U) = 5 + 25 + 11 + 15 + 4 + 10 + 10 + 20 = 100 2.5 Summary This lecture has dealt with the postulates or laws of set theory. This arises from the permissible set operations. Also studied has been the application of set algebra to logical counting problems. Activity 2.2 Self Test One a) A company has a large of computer assistants, each of whom is competent in the use of at least one of 3 utility packages: Word processor (W) Database Management system (D) and a Spreadsheet (S). A survey shows that 30 can use a word processor, 25 can use a Database Management system and 28 are competent in the use of a Spreadsheet. Of the computer 14  facility assistants who can use a Database Management System, 14 can also use a word processor while 6 have no other skill. 6 of the computer assistants can use a word processor and spreadsheet but not a database system while 4 have all three skills. Required: Determine the number of computer facility assistants who are members of the following sets: i) W D S’ ii) (W S)’  S iii) DS iv) Universal set b) A sample of 100 Young Christian Union voters revealed the following concerning three candidates; Ali, Bungei and Chiru, who were running for the Y.C.S Party Chairman, Secretary and Treasurer respectively. 14 preferred booth Ali and Bungei 49 preferred Ali or Bungei but not Chiru 21 preferred Bungei but not Chiru or Ali 61 preferred Bungei or Chiru but not Ali 32 preferred Chiru but not Ali or Bungei 7 preferred Ali and Chiru but not Bungei. Required: i) With the aid of a Venn diagram, determine the number of voters that were in favor of all the three candidates. Assume that every member of Y.C.S voted for at least one candidate. Determine the candidate that went unopposed if a rule of 50% majority were used in such a decision. 15