what are sets Functions and Relations

basic properties of sets and functions,sets relations and functions questions and answers, sets relations and functions aptitude questions,sets and functions symbols pdf free download
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Sets, Equivalence and Order With an Introduction to Sequences and Series Unit SF: Sets and Functions Edward A. Bender S. Gill Williamson c Edward A. Bender & S. Gill Williamson 2010. All rights reserved.Preface The material in this unit of study was, over several years, presented by the authors to lower division undergraduates in the Department of Mathematics and the Department of Computer Science and Engineering at the University of California, San Diego (UCSD). All material has been classroom tested by the authors and other faculty members at UCSD. The first course of a two quarter sequence was chosen from six units of study: Boolean Func- tions (Unit BF), Logic (Unit Lo), Number Theory and Cryptography (Unit NT), Sets and Functions (Unit SF), and Equivalence and Order (Unit EO), and Induction, Se- quences and Series (Unit IS). Thesecond course of the sequence was chosen from four unitsof study: Counting and Listing (Unit CL), Functions (Unit Fn), Decision Trees and Recursion (Unit DT), and Basic Concepts in Graph Theory (Unit GT). The order of presentation of units within the first six, as well as those within the second four, can be varied for students with a good high school background in mathematics. Discrete mathematics has become an essential tool in computer science, economics, biology, mathematics, chemistry, and engineering. Each area introduces its own special terms for shared concepts in discrete mathematics. The only way to keep from reinventing the wheel from area to area is to know the precise mathematical ideas behind the concepts being applied by these various fields. Our course material is dedicated to this task. At the end of each unit is a section of multiple choice questions: Multiple Choice Questions for Review. These questions should be read before reading the corresponding unit, and they should be referred to frequently as the units are read. We encouraged our students to be able to work these multiple choice questions and variations on them with ease and understanding. At the end of each section of the units are exercises that are suitable for written homework, exams, or class discussion. iiiivTable of Contents Unit SF: Sets and Functions Section 1: Sets...............................................................................................SF-1 intersection, union, difference, complement, symmetric difference, product, Cartesian prod-  n uct, binomial coefficients, C(n,k) = , algebraic rules, associative rule, distributive rule, k idempotent rule, DeMorgan’s rule, absorption rule, commutative rule, lexicographic order, power set, characteristic function, set partitions, Bell numbers, refinement Section 2: Functions....................................................................................SF-15 function, domain, range, codomain, image, relation, functional relation, one-line notation, surjection, onto, injection, one-to-one, bijection, permutation, two-line notation, composi- tion of functions, cycle form of permutation, image of function, inverse image, coimage, set partitions, Stirling numbers S(n,k), Bell numbers Multiple Choice Questions for Review........................................................SF-29 Notation Index................................................................................... SF-Index 1 Subject Index..................................................................................... SF-Index 3 A star in the text () indicates more difficult and/or specialized material. vviUnit SF Sets and Functions Section 1: Sets The basic concepts of sets and functions are topics covered in high school math courses and are thus familiar to most university students. We take the intuitive point of view that sets are unordered collections of objects. We first recall some standard terminology and notationassociatedwith sets. When we speakaboutsets, we usually have a “universalset” U in mind, to which the various sets of our discourse belong. Definition 1 (Set notation) A set is an unordered collection of distinct objects. We use the notation x ∈ S to mean “x is an element of S” and x ∈/ S to mean “x is not an element of S.” Given two subsets (subcollections) of U, X and Y, we say “X is a subset of Y,” written X ⊆ Y, if x∈ X implies that x∈ Y. Alternatively, we may say that “Y is a superset of X.” X ⊆ Y and Y ⊇ X mean the same thing. We say that two subsets X and Y of U are equal if X ⊆Y and Y ⊆X. We use braces to designate sets when we wish to specify or describe them in terms of their elements: A = a,b,c, B = 2,4,6,.... A set with k elements is called a k-set or set with cardinality k. The cardinality of a set A is denoted by A. Since a set is an unordered collection of distinct objects, the following all describe the same 3-element set a,b,c =b,a,c =c,b,a =a,b,b,c,b. The first three are simply listing the elements in a different order. The last happens to mention some elements more than once. But, since a set consists of distinct objects, the elements of the set are still just a, b, c. Another way to think of this is: Two sets A and B are equal if and only if every element of A is an element of B and every element of B is an element of A. Thus, with A =a,b,c and B =a,b,b,c,b, we can see that everything in A is in B and everything in B is in A. You might think “When we write a set, the elements are in the order written, so why do you say a set is not ordered?” When we write something down we’re stuck — we have to list themin some order. You can think of a set differently: Write each element on a separate slip of paper and put the slips in a paper bag. No matter how you shake the bag, it’s still the same set. If we are given that A is a set and no other information about A, then there is no ordering to the elements of A. Thus, we cannot speak of “the second element of the set A” unlesswe have specifiedanorderingofthe elementsofA. Ifwe wish toregardA asordered in some way, then we specify this fact explicitly: “The elements of A are ordered a, b, c,” or “A =(a,b,c).” The latter notation replaces the braces with parentheses and designates that A is ordered, left to right, as indicated. We call this an ordered set. An ordered set is also called a linear order. Various other names are also used: list, vector, string, word SF-1Sets and Functions 1 — all withno repeated elements. Of course, you’ve seen repeated elements in vectors, for example the point in the plane at the coordinates (1,1). That’s fine, it’s just not an ordered set. If there are k elements in the ordered set, it is referred to as a k-list, k-vector, etc., or as a list, vector, etc., of length k — all with no repeated elements because they are orderedsets. Sometimes we cannot list the elements of a set explicitly. What do we do if we want to describe the set of all real numbers greater than 1 without writing it out in words? We write xx∈R, x1 or xx1 or x:x 1. These are read“the set ofallx such that...” In thefirst example we mentioned thatx was a real number (x ∈ R). In the other two we didn’t because we assumed the reader knew from context that we were talking about real numbers. For the most part, we shall be dealing with finite sets. Let U be a set and let A and B be subsets of U. The sets A∩B =xx∈A and x∈B and A∪B =xx∈ A or x∈B are the intersection and union of A and B. The set A\B or A−B is the set difference c ′ of A and B (i.e., the set x x ∈ A,x ∈/ B). The set U \A (also A , A or ∼A) is the c complement of A (relative to U). Note that A−B = x x ∈ A,x ∈/ B = A∩B . The c c empty set, denoted by ∅, equals U . Also note that, for any set A ⊆ U, A∪A = U and c A∩A =∅. The set A⊕B = (A\B)∪(B\A) is the symmetric difference of A and B. We use A×B = (x,y) x ∈ A,y ∈ B to denote the product or Cartesian product of A and B. k If we want to consider the product of k sets, A ,...,A , this is denoted by × A . If we 1 k i i=1 k want to consider the product of a set A with itself k times, we write × A. Set Properties and Proofs The algebraic rules for operating with sets are also familiar to most beginning university students. Here is such a list of the basic rules. In each case the standard name of the rule is given first, followed by the rule as applied first to ∩ and then to∪. Theorem 1 (Algebraic rules for sets) The universal setU is notmentionedexplicitly but is implicit when we use the notation ∼X = U − X for the complement of X. An 1 Why is it okay to specify a set S =a,b,c,a where the element a has been repeated, but it is not okay to have repeated elements in an ordering of S? When we say S = a,b,c,a, we know that S contains just the three elements a, b and c. If we were to talk about the ordered set (a,b,c,a) it would not make sense because it would say that the element a is in two places at once: the first position and the last position. SF-2Section 1: Sets c alternative notation is X =∼X. Associative: (P ∩Q)∩R =P ∩(Q∩R) (P ∪Q)∪R =P ∪(Q∪R) Distributive: P ∩(Q∪R) = (P ∩Q)∪(P ∩R) P ∪(Q∩R) = (P ∪Q)∩(P ∪R) Idempotent: P ∩P =P P ∪P =P Double Negation: ∼∼P =P DeMorgan: ∼(P ∩Q) =∼P ∪∼Q ∼(P ∪Q) =∼P ∩∼Q Absorption: P ∪(P ∩Q) =P P ∩(P ∪Q) =P Commutative: P ∩Q =Q∩P P ∪Q =Q∪P These rulesare “algebraic”rules for working with∩,∪, and∼. You should memorize them as you use them. They are used just like rules in ordinary algebra: whenever you see an expression on one side of the equal sign, you can replace it by the expression on the other side. When we wrote “P ∩Q∩R” you may have wondered if we meant “(P ∩Q)∩R” or “P ∩(Q∩R).” The associative law says it doesn’t matter. That is why you will see the notation P ∩Q∩R or P ∪Q∪R without anyone getting excited about it. On the other hand P ∩(Q∪R) and (P ∩Q)∪R may not be equal, so we need parentheses here. The best way to “prove” the rules or to understand their validity is through the geometric device of a Venn diagram. Example 1 (Venn diagrams and proofs of set equations) Here is a Venn diagram for three sets, P, Q, and R, with universal set U: U 4 1 P 6 8 7 2 Q 5 R 3 The three oval regions labeled P, Q, and R represent the sets of those names. The rectan- gular region representsthe universal setU. There are eight subregions, labeled 1 through8 inthepicture. Region8representsthesubsetP∩Q∩R; region1representsU−(P∪Q∪R); region 2 represents the elements of Q−(P ∪R); and so on. Let’s use the above Venn diagram to verify that the distributive rule, P ∪(Q∩R) = (P∪Q)∩(P∪R),isvalid. TheideaistoreplacethesetsP,Q,andRbytheircorresponding sets of regions from the Venn diagram. Thus, Q is replaced by 2,5,6,8, P is replaced by 4,6,7,8, and R is replaced by 3,5,7,8. Even though the sets P, Q, and R are arbitrary, perhaps even infinite, the distributive rule reduces to verifying the same rule for these simplified sets:    4,6,7,8∪ 2,5,6,8∩3,5,7,8 = 4,6,7,8∪2,5,6,8 ∩ 4,6,7,8∪3,5,7,8 . SF-3Sets and Functions This identity is trivial to check directly: Both sides reduce to the set 4,5,6,7,8. This“Venndiagram”approachreducesasetidentitythatinvolvespotentiallyinfinitely many elementsto subsetsof a set of eight elements. It is fine for proofsand especiallygood for checking out “set identities” to see quickly if they are true or not. For example, is it true that Q−(P ∩R) = Q−(P ∩Q∩R)? Checking the Venn diagram shows that both sides correspond to the set of regions 2,5,6. The identity is true. You will get a chance to practice this technique in the exercises. There are, of course, other ways to verify set identities. One way is called the element method: Example 2 (The element method for proofs of set equations) To use thatmethod, you simply translate the identity X = Y into basic statements about what conditions a single element must satisfy to be (first) in the set on the left and then (second) in the set on the right. Thus, to show that X =Y, you assert that if x∈X then blah, blah, blah (a bunch of words that make sense) implies that x∈ Y. This shows that X ⊆ Y. Then, you reverse the argument and assert that if y∈Y then blah, blah, blah (a bunch of words that make sense) implies that y∈X. This shows that Y ⊆X. Thus X =Y. Here is an example. Show, by the element method that, for all subsets P, Q, and R of U, (P −Q)∩(R−Q) =(P ∩R)−Q. (1) If x∈ (P −Q)∩(R−Q) then (here comes the blah, blah, blah) x is in P but not in Q AND x is in R but not in Q. (2) Thus x is in P and R, but x is not in Q. (3) Thusx isin (P∩R)−Q. Thisshowsthat(P−Q)∩(R−Q)⊆ (P∩R)−Q. We leave it toyou tousetheelementmethodtoshowthereverse,(P−Q)∩(R−Q)⊇(P∩R)−Q, and hence that (P−Q)∩(R−Q) = (P∩R)−Q. You should start your argument by saying, “Suppose x∈(P ∩R)−Q.” A different sort of element approach looks at each element of the universal set U and asks which sets contain it. The result can be put in tabular form. When this is done, each row of the table correspondsto a region in the Venn diagram. The next example illustrates this tabular method. Example 3 (The tabular method for proofs of set equations) We redo the identity of the previous example: (P − Q)∩ (R−Q) = (P ∩ R)− Q. To do this we construct a table whose columns are labeled by various sets and whose entries answer the question “Is x in the set?” The first three columns in the following table are set up to allow all possible answers to the three questions “Is x in P?” “Is x in Q?” “Is x in R?” “Left” and “Right” refer to (P−Q)∩(R−Q) and (P∩R)−Q, the two sides of the equation we want to prove. “Venn” refers to the region in the Venn diagram of Example 1. Normally that column would not be in the table, but we’ve inserted it so that you can see how each row SF-4Section 1: Sets corresponds to a Venn diagram region. P Q R P −Q R−Q Left P ∩R Right Venn No No No No No No No No 1 No No Yes No Yes No No No 3 No Yes No No No No No No 2 No Yes Yes No No No No No 5 Yes No No Yes No No No No 4 Yes No Yes Yes Yes Yes Yes Yes 7 Yes Yes No No No No No No 6 Yes Yes Yes No No No Yes No 8 Since the answers are identical in the columns labeled “Left” and “Right,” the identity is proved. We can prove more from the table. For example, If P ⊆Q∪R, then P −Q= (P ∩R)−Q. How does the table prove this? Because of the condition P ⊆ Q∪R, the row that begins “YesNoNo”cannotoccur. Therefore,wethrowoutthatrowandcomparecolumns“P−Q” and “Right.” AnotherwaytoprovesetidentitiesistousethebasicalgebraicidentitiesofTheorem1. This is called the algebraic method. Example 4 (An algebraic proof) It is probably a good idea for you to label the steps with the appropriate rule (e.g., DeMorgan’s rule, associative rule, distributive rule, etc.) the first few times you do such a proof. Therefore, we’ll do that in this example. Mathematicians, however, would rarely bother to do it. A proof is accepted if others who know the basic rules of set theory can read it, understand it, and believe it is true. Let’s prove that Q−(P ∩R) =Q−(P ∩Q∩R). Here it is c c Q−(P ∩R) =Q∩(P ∩R) since A−B =A∩B c c =Q∩(P ∪R ) DeMorgan’s rule c c = (Q∩P )∪(Q∩R ) distributive rule c c = (Q∩P )∪∅∪(Q∩R ) since A∪∅ =A c c c c = (Q∩P )∪(Q∩Q )∪(Q∩R ) since Q∩Q =∅ c c c =Q∩(P ∪Q ∪R ) distributive rule c =Q∩(P ∩Q∩R) DeMorgan’s rule c =Q−(P ∩Q∩R) since A−B =A∩B Some steps in this proof are baffling. For example, why did we introduce ∅ in the fourth line? We knew where we were going because we worked from both “ends” of the proof. In other words, we came up with a proof that moved both ends toward the middle and then SF-5Sets and Functions rearranged the steps so that we could go from one end to the other. Unfortunately, proofs are often presented this way. Here’s another way to write the proof of Q−(P ∩R) = Q−(P ∩Q∩R) that shows more clearly how we got the proof. Note first that this identity is equivalent to showing that c c Q∩(P ∩R) =Q∩(P ∩Q∩R) c since A−B =A∩B . This is equivalent, by DeMorgan’s rules, to showing that c c c c c Q∩(P ∪R ) =Q∩(P ∪Q ∪R ). But       c c c c c c c c c c c Q∩(P ∪Q ∪R ) =Q∩ (P ∪R )∪Q = Q∩(P ∪R ) ∪ Q∩Q =Q∩(P ∪R ). c This latter identity follows from the fact that Q∩Q = ∅ and X ∪∅ = X for any set X. This completes the proof. How should you write an algebraic proof? You can use whichever method you prefer. The first approach can be read mechanically because of the way it’s laid out. However, if you use the first approach, you may sometimes need to use the second method for yourself first. Ordering Sets Incomputerprogramming,youwillstoreandcomputewithsetsofallsorts(setsofnumber, letters, geometric figures, addresses to arrays, pointers to structures, etc.). In almost all cases, you will work with these sets as lists (also called “linear orders”) of some type where order does matter. The order matters in terms of the efficiency of your computations, not in terms of the rules of set theory. Inmanycases,thelinearorderingoftheelementsofasetisinheritedfromtheuniversal setU. Forexample,thesetsA =1,2,3andB =a,b,c inheritanaturallinearordering from the integers and the alphabet, respectively. But what about C =?,,,? There is no standard convention for C. You could use the ASCII code order (,,?), but if you do, some explanation should be given. SF-6Section 1: Sets Example 5 (Lexicographic order) If you have decided on linear orders (i.e., listings) for a set X and a set Y, there is a commonly used and natural linear ordering for X×Y called lexicographic order. Suppose we list X and Y in some manner: (x ,x ,...,x ) and (y ,y ,...,y ). 1 2 n 1 2 m Given pairs (a,b) ∈ X ×Y and (c,d) ∈ X ×Y, we say that (a,b) is lexicographically less than or equal to (c,d) if (1) a is before c in the linear order on X or (2) a=c and b is equal to or before d in the linear order on Y. For example, the lexicographic order for 1,2,7×a,b is  (1,a), (1,b), (2,a), (2,b), (7,a), (7,b) . Lexicographic order is called lex order for short. Once you have ordered X ×Y lexicographically, you can order (X ×Y)×Z by the same two rules (1) and (2) above, provided an order is specified on Z. You can use lex order on X ×Y and the given linear order on Z. Likewise, you can apply (1) and (2) to X×(Y×Z)usingthegiven linearorderonX andlexorderonY×Z. Thesets(X×Y)×Z and X ×(Y ×Z) are different sets – elements in the former have the form ((x,y),z) and those in the latter have the form (x,(y,z)). Imagine listing (X×Y)×Z in lex order and stripping off the inner parentheses so that ((x,y),z) becomes (x,y,z). Now do the same with X ×(Y ×Z). The two lists will contain the same elements in the same order. It’s easy to see why the elements are the same, but it’s not so easy to see why the orders are the same. Let’s prove the orders are the same. That means we have to prove ((x ,y ),z ) precedes ((x ,y ),z ) if and only if (x ,(y ,z )) precedes (x ,(y ,z )). 1 1 1 2 2 2 1 1 1 2 2 2 It will make things easier if we write “((x ,y ),z ) ((x ,y ),z )” for “((x ,y ),z ) pre- 1 1 1 2 2 2 1 1 1 cedes ((x ,y ),z ).” By definition the definition of lex order, ((x ,y ),z ) ((x ,y ),z ) 2 2 2 1 1 1 2 2 2 means that (x ,y ) (x ,y ) or (x ,y ) = (x ,y ) and z z . By the definition of 1 1 2 2 1 1 2 2 1 2 lex order, the first case means that either x x or x = x and y y . Note that 1 2 1 2 1 2 (x ,y ) =(x ,y )meansx =x andy =y . Puttingallthistogether,wehaveshownthat 1 1 2 2 1 2 1 2 ((x ,y ),z )((x ,y ),z ) means that either 1 1 1 2 2 2 (1) x x or 1 2 (2) x =x and y y or 1 2 1 2 (3) x =x and y =y and z z . 1 2 1 2 1 2 In otherwords, look for the first positionwhere (x ,y ,z ) and (x ,y ,z ) disagreeand use 1 1 1 2 2 2 that position to determine the order. We leave it to you to show that the same conditions describe (x ,(y ,z )) (x ,(y ,z )). This completes the proof. 1 1 1 2 2 2 Since (X×Y)×Z and X×(Y ×Z) have the same order when inner parentheses are dropped, one usually does that. We just write X×Y ×Z and call the elements (x,y,z). SF-7Sets and Functions When you think about what we’ve just done, you should be able to see that, if S ,S ,...,S are sets, we can write S × S ×···× S , leaving out parentheses. The 1 2 n 1 2 n n product S ×S ×···×S is also written× S . 1 2 n i i=1 Suppose (s ,s ,...,s ) and (t ,t ,...,t ) are in S ×S ×···×S . Which comes 1 2 n 1 2 n 1 2 n first? You should be able to see that we determine which precedes which as follows: By going left to right, find the first position where they disagree. Say position k is where this disagreementoccurs. Usetheorderofs andt todeterminetheorderof(s ,s ,...,s )and k k 1 2 n (t ,t ,...,t ). This is the same order you use when you look things up in a dictionary. 1 2 n Example 6 (Dictionary order on words or strings) The order of words in the dictionary is called “dictionary order.” Lex order appears to be the same as dictionary order, but there is a problem with this. We’ve only defined lex order for n-tuples where n has some fixed value, but words in the dictionary have different length. Let’s look at this more carefully. k k Let S be a finite set. Let S =× S be the product of S with itself k times. The set 0 ∗ ∞ k S is special and consists of one string ǫ called the empty string. Let S = ∪ S . In k=0 ∗ words, S consists of all strings (words, vectors) of all possible lengths (including length ∗ zero) over S. Assume S is linearly ordered. We now define an order relation on S called ∗ lexicographic order or dictionary order, denoted by ≤ , on S . L ∗ Let (a ,a ,...,a ) and (b ,b ,...,b ) be two elements of S with m,n 0. We say 1 2 m 1 2 n that (a ,a ,...,a )≤ (b ,b ,...,b ) 1 2 m L 1 2 n if either of the following two conditions hold: (D1) m≤n and a =b for i = 1,...,m. i i (D2) For some k min(m,n), a = b , i = 1,...,k, a = 6 b , and a is before i i k+1 k+1 k+1 b in the linear order on S. k+1 Since m,n 0, we have not discussed the empty string. Thus we need: (D3) The empty string ǫ ≤ x for any string x. L We have just defined dictionary order and also called it lex order. Is this the same as our previous definition of lex order? Yes because the two definitions of lex order agree when the strings have the same length. We shall study this ordering on words carefully when we study order relations in general. For now we just give an example. Let S = x,y with the ordering on S the alphabeticorder. Ifu =(x,x,y) andv =(x,x,y,x), thenu≤ v by(D1). Ifs = (x,x,y,x) L andt =(x,x,x,y), thent≤ s by (D2). More examples will be given in the exercises. The L standard English dictionary is an example where this linear order is applied to a subset of all words on the standard English alphabet (the words that have meaning in English). A variation on this dictionary order is to order all words first by length and then by lex order. Thus, u =(y,y,y) comesbeforev = (x,x,x,x) becauseu haslengththree(three ∗ components)and v has length one. This order on S is called length-first lex order or short lex order. SF-8Section 1: Sets Subsets of Sets We use the notation P(A) to denote the set of all subsets of A and P (A) the set of all k subsets of A of size (or cardinality) k. We callP(A) “the set of all subsets of A” or simply the power set of A. Let C(n,k) = P (A) denote the number of different k-subsets that k  n can be formed from an n-set. The notation is also frequently used. These are called k binomial coefficients and are read “n choose k.” We now prove Theorem 2 (Binomial coefficient formula) The value of the binomial coefficient is   n n(n−1)···(n−k+1) n =C(n,k)= = , k k k(n−k) where 0 = 1 and, for j 0, j is the product of the first j integers. We read j as “j factorial”. Proof: Let A be a set of size n. The elements ofP (A) are sets and are thus unordered. k Generally speaking, unordered things are harder to count than ordered ones. Suppose, instead of a set of size k chosen from A, you wanted to construct an ordered list L of k elements from A (L is called a “k-list”). We could construct L in two stages. • First choose an element of S ∈ P (A) (a subset of A with k elements). This can be k done in C(n,k) ways since C(n,k)=P (A). k • Next orderS to obtainL. This orderingcan be donein k =k(k−1)···1 ways. Why? You have k choices for the element of S to appear first in the list L, k−1 choices for the next element, k−2 choices for the next element, etc. Fromthistwo-stageprocess,weseethatthereareC(n,k)korderedk-listswithnorepeats. (The factor C(n,k) is the number of ways to carry out the first stage and the factor k is the number of ways to carry out the second stage.) Theorem 3 (Number of ordered lists) The number of ordered k-lists L that can be made from and n-set A is k • n if repeats are allowed and • n(n−1)···(n−k+1)=n/(n−k) if repeats are not allowed. One also uses the notation (n) for these values. This is called the “falling factorial” and is read “n k falling k”. Why? With repeats allowed, there are n choices of elements in A for the first entry in the k-list L, n choices for the second entry, etc. If repeats are not allowed, there are n choices of elements in A for the first entry in the k-list L, n−1 choices for the second entry, etc. SF-9Sets and Functions Since we’ve counted the same thing (k-lists made from A) in two different ways, the two answers must be equal; that is, C(n,k)k = n/(n−k). Dividing by k, we have the theorem. In high school, you learned about “Pascal’s Triangle” for computing binomial coeffi- cients. We review this idea in the next example. Example 7 (Binomial recursion) Let X = x ,...,x . We’ll think of C(n,k) as 1 n counting k-subsets of X. Imagine that we are going to construct a subset S of X with k elements. Either the element x is in our subset S or it is not. The cases where it is in the n subset S are all formed by taking the various (k−1)-subsets of X −x and adding x n n  n−1 to them. By the definition of binomial coefficients, there are such subsets. The cases k−1 where it is not in the subset S are all formed by taking the various k-subsets of X−x . n  n−1 By the definition of binomial coefficients, there are such subsets. What we’ve done k is describe how to build all k-subsets of X from certain subsets of X −x . Since this n gives each subset exactly once,       n n−1 n−1 = + , k k−1 k which can be written C(n,k) = C(n−1,k−1)+C(n−1,k). This equation is called a recursion because it tells how to compute the function C(n,k) from values of the function with smaller arguments. Here are the starting values together with the basic recursion: C(1,0)=C(1,1) =1, C(1,k)=0 for k = 6 0,1 and C(n,k)=C(n−1,k−1)+C(n−1,k) for n 1. Below we have made a table of values for C(n,k). k 0 1 2 3 4 5 6 n 1 0 1 1 1 C(n,k) 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 This tabular representation of C(n,k) is called “Pascal’s Triangle.” Definition 2 (Characteristic function) Let U be the universal set and let A ⊆ U. The characteristic function of A, denoted χ is defined for each x∈U by A  1, if x∈A, χ (x)= A 0, if x∈/ A. 2 Thus the domain of χ is U and the range of χ is 0,1. A A 2 If you are not familiar with “domain” and “range”, see the definition at the beginning SF-10Section 1: Sets Example 8 (Subsets as (0,1)-vectors) If A has n elements, listed (a ,a ,...,a ), 1 2 n then you can specify any subset X ⊂ A by a sequence (ǫ ,ǫ ,...,ǫ ) where ǫ = 0 if the 1 2 n k element a ∈/ X and ǫ = 1 if the element a ∈ X. The vector (ǫ ,ǫ ,...,ǫ ) is just the k k k 1 2 n characteristic function of X since ǫ =χ (a ). k k X n How many different subsets of A are there? We’ll show that there are 2 choices for n n (ǫ ,ǫ ,...,ǫ ) andthusP(A)= 2 . Why 2 ? Thereareclearlytwo choicesforǫ andtwo 1 2 n 1 n choices for ǫ and so forth. Thus there are 2×2×··· =2 choices for (ǫ ,ǫ ,...,ǫ ). 2 1 2 n Example 9 (Sets with sets as elements) Sets can have sets as elements. In the first exercise of this section, you will be asked such questions as “Is 1,2 ∈ 1,2,3,4?” or “Is 1∈1,2,3?” Easy stuff if you understand the definitions: You can see that the set1,2 is indeed an element of the set1,2,3,4 because this latter set has just two elements, each of them a set of size two, one of which is 1,2. You can also see that every element of 1,2,3 is a set and that the number 1 is nowhere to be found as an element of this set. YouhavealreadyseenP(A),whichisasetwhoseelementsaresets,namelythesubsets of A. Another important class of sets with sets as elements are the set partitions. Some of the elementary aspects of set partitions fit into our present discussion. More advanced aspects of them will be discussed in Section 2. Here is a preview. Let A = 1,2,...,15. Consider the following set whose elements are themselves subsets of A.  α = 1, 2,9, 3,5, 4,7, 6,8,10,15, 11,12,13,14 . This set is a subset of the power setP(A). But, it is a very special type of subset, called a set partition of A because it satisfies the three conditions: (1) every element of α is nonempty, (2) the union of the elements of α is A, and (3) if you pick sets X ∈ α and Y ∈α, either X =Y or X∩Y =∅. Any collection of subsets of a set A satisfying (1), (2), and (3) is a set partition of A or simply a partition of A. Each element of α (which is, of course, a subset of A) is called a block of the partition α. How many partitions are there of a set A? This is a tricky number to compute and n there is no simple formula like C(n,k)= for it. We will discuss it in the Section 2. k(n−k) The number of partitionsof a set of sizen is denotedbyB . These numbersare called Bell n numbers after Eric Temple Bell. The first few Bell numbers are B = 1, B = 2, B = 5, 1 2 3 B =15, B =52. 4 5 We can refine the partition α by splitting blocks into smaller blocks. For example, we might split the block 6,8,10,15 into two blocks, say 6,15 and 8,10, and also split the block 11,12,13,14 into three blocks, say 13, 14, and 11,12. The resulting partition is called a refinement of α and equals  1,2, 9, 3,5, 4,7, 6,15, 8,10, 13,14,11,12 . of the next section. SF-11Sets and Functions Note that a refinement of a partition is another partition of the same set. We also consider a partition α to be a refinement of itself. We shall gain a deeper understanding of the notion of refinement when we study order relations. Exercises for Section 1 1.1. Answer the following about the ∈ and⊆ operators. (a) Is 1,2∈1,2,3,4? (b) Is 2∈1,2,3,4? (c) Is 3∈1,2,3 (d) Is 1,2⊆1, 2, 1,2, 3,4? (e) Is 1∈1,2, 3? (f) Is 1,2,1⊆1,2? 1.2. For each of the following, draw a Venn diagram. (a) A⊆B, C ⊆B, A∩C =∅ (b) A⊇C, B∩C =∅. 1.3. Let A = w,x,y,z and B = a,b. Take the linear orders on A and B to be alphabetic order. List the elements in each of the following sets in lexicographic order. (a) A×B (b) B×A (c) A×A (d) B×B 1.4. Let A = 1,2,3, B = u,v, and C = m,n. Take the linear order on A to be numeric and the linear orders on B and C to be alphabetic. List the elements in each of the following sets in lexicographic order. (a) A×(B×C) (use lex order on B×C). (b) (A×B)×C (use lex order on A×B). (c) A×B×C. 1.5. Let Σ = (x,y) be an alphabet. List each of the following sets of strings over this alphabet in the order indicated. SF-12Section 1: Sets (a) All palindromes (strings that read the same forward and backward) of length less than or equal to 4. List them in dictionary order. (b) All strings(words) thatbeginwith xand have lengthlessthanfour. List them in both dictionary and length-first lex order. (c) List all strings of length four in lex order. 1.6. Each of the following statements about subsets of a set U is FALSE. Draw a Venn diagram to represent the situation being described. In each case case, show that the assertion is false by specializing the sets. (a) For all A, B, and C, if A6⊆B and B 6⊆C then A6⊆C. (b) For all sets A, B, and C, (A∪B)∩C =A∪(B∩C). (c) For all sets A, B, and C, (A−B)∩(C−B) =A−(B∪C). (d) For all A, B, and C, if A∩C ⊆B∩C and A∪C ⊆B∪C then A=B. (e) For all A, B, and C, if A∪C =B∪C then A =B. (f) For all sets A, B, and C, (A−B)−C = A−(B−C). 1.7. Prove each statement directly from the definitions. (a) IfA,B,andC aresubsetsofU,thenA⊆B andA⊆C impliesthatA⊆B∩C. (b) IfA,B,andC aresubsetsofU,thenA⊆C andB ⊆C impliesthatA∪B ⊆C. 1.8. Prove, using the definition of set equality, that for all sets A, B, and C, (A−B)∩(C−B) =(A∩C)−B. 1.9. Prove each statement by the method indicated. (a) Prove using element arguments that if U is the universal set and A and B subsets of U, then A⊆ B implies that U −A⊇ U −B (alternative notation: c c ′ ′ A⊆B implies A ⊇B , or A ⊇B ) (b) Prove, using element arguments and the definition of set inclusion, that for all A, B, and C, if A⊆B then A∩C ⊆B∩C. (c) Prove, using (a), (b), and DeMorgan’s law, that for all A, B, and C, if A⊆B then A∪C ⊆B∪C. 1.10. Prove each statement by the “element method.” (a) If A, B, and C are subsets of U, then A×(B∪C) =(A×B)∪(A×C). (b) If A, B, and C are subsets of U, then A×(B∩C) =(A×B)∩(A×C). 1.11. Prove each of the following identities from the basic algebraic rules for sets. You c may want to use the fact that D−E =D∩E . SF-13Sets and Functions (a) If A, B, and C are subsets of U, then (A−B)−C =A−(B∪C). (b) If A, B, and C are subsets of U, then (A−B)−C =(A−C)−B. (c) If A and B are subsets of U, then (A−B)∪(B−A) =(A∪B)−(A∩B). 1.12. Prove or give a counterexample. Use a Venn diagram argument for the proof. For the counterexample, use a Venn diagram or use set specialization. (a) If A, B, and C are subsets of U, then (A−C)∩(B−C)∩(A−B) =∅. (b) If A and B are subsets of U and if A⊆B, then A∩(U −B) =∅. (c) If A, B, and C are subsets of U, and if A⊆B, then A∩(U −(B∩C)) =∅. (d) IfA,B,andC aresubsetsofU,andif(B∩C)⊆A,then(A−B)∩(A−C) =∅. (e) If A and B are subsets of U and if A∩B =∅, then A×B =∅. 1.13. Recall that the symmetric difference of setsA and B is A⊕B =(A−B)∪(B−A). It is evident from the definition that A⊕B = B⊕A, the commutative law. Let U be the universal set. Prove each of the following properties either using a Venn diagram argument or algebraically or directly from the definition. (a) A⊕(B⊕C) =(A⊕B)⊕C (associative law for ⊕). (b) A⊕∅ =A. c (c) A⊕A =U. (d) A⊕A =∅. (e) If A⊕C =B⊕C then A =B. 1.14. Let A, B, and C be subsets of U. Prove or disprove using Venn diagrams. (a) A−B and B−C are disjoint. (b) A−B and C−B are disjoint. (c) A−(B∪C) and B−(A∪C) are disjoint. (d) A−(B∩C) and B−(A∩C) are disjoint. 1.15. Which of the following are partitions of 1,2,...,8? Explain your answers.  (a) 1,3,5, 1,2,6, 4,7,8  (b) 1,3,5, 2,6,7, 4,8  (c) 1,3,5, 2,6, 2,6, 4,7,8  (d) 1,5, 2,6, 4,8  1.16. Howmanyrefinementsarethereofthepartition 1,3,5, 2,6, 4,7,8,9 ? Ex- plain. 1.17. Suppose S and T are sets with S∩T =∅. Suppose σ is a partition of S and τ is a partition of T. SF-14

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.