Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 8 page Class Notes was uploaded by Chaya Botsford II on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 428 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
9SETS A set is a collection of objects called its elements and usually denoted by means of curly brackets Hence abc denotes the set whose elements are a b and c CAUTION The order in which the elements are written is irrelevant but the elements must be different When the set has in nitely many elements the above notation becomes impractical so we resort to the setbuilder notation This is manufactured by writing Adummy variable condition satis ed by the variable The semicolon here means quotsuch that J Viola Prioli For instance A x x E Z and 2x is read quotthe set of integers divisible by 2 That is A is the set of even numbers Here of course x is our dummy variable and could be replaced by a different symbol or letter Likewise the set of odd integers between 10 and 100 can be denoted by 2n1 E Z 4 lt n lt 50 or equivalently as 2n1 n E Z and 4 lt n lt 50 The empty set Q is the set with no elements A set builder notation for the empty set is Q x EZ x x Two sets are equal when they have the same elements For instance although with the tools at our disposal right now is not evident the sets x E Z 6x and x E Z 2x and 3x are equal DEFINITION A is a subset of B written A Q B if every element of A is an element of B Therefore to prove that A Q B one must show that if a E A then a E B J Viola Prioli Equivalent formulations for A Q B are A is contained in B and also B contains A Please notice the distinction between quotbelongs to and quotcontained in The former applies to elements in a set The latter refers to a set being a subset ofanother The template to prove the equality of two sets follows to prove that AB we must show that A Q B and also B Q A TIP The basic step in dealing with sets is making sure to understand and list them if possible what the elements are The elements of a set can be of different nature Observe the following examples J Viola Prioli a A 1 5 has three elements b B 1 5 2 6 is a set with three elements which are the numbers 1 and 6 and the set 5 2 We emphasize that B does not have four elements c C 2 Q has two elements the number 2 and the empty set cl D Q Q has two elements the empty set and the set whose element is the empty set e A 1 1 3 We conclude that 3 i A 1 3 E A 1 3 is not a subset of A f A 1 2 13 has three elements 1 2 and 13 B 1 2 v w has four elements Is A Q B J Viola Prioli To say that A is not a subset of B denoted by A Z B means that there exists an element of a that is not an element of B g Let us prove that ifA n E N last digit of n is a zero and B n E N 5n thenAQB To that end let a E A Therefore a 10 k for some integer k Since 10 2XS a 5 2k so a is a multiple of 5Thus a E B Observe that the empty set is a subset of any given set Also for any set A we have A Q A NOTATION In what follows A denotes the number of elements of the set A J Viola Prioli We are interested in nding the number of subsets of a set with n elements For instance if A has three elements we may assume A abc and proceed to list of its subsets beginning with the empty set then with the subsets of 1 element and so on We have Q a b c a b a c b c a b cA There are therefore 8 subsets Notice that 8 23 What we just illustrated for n 3 is generalized in our next THEOREM If A has n elements then A has exactly 2n subsets Observe that if n O A is the empty set which has only one subet Q itself so the formula is valid for n 0 We may assume n gt O and since we are interested only in counting we may assume that A 1 2 3 n without loss of generality Since a subset is totally identi ed by knowing each of its elements we can prepare n blocks which we align orderly Then we ll the jth block with a O ifj is not in the subset and with 1 ifj is an element of the subset That way each subset is identi ed with a binary string of length n Since there are 2n such binary strings as we proved in a previous section the conclusion follows J Viola Prioli For instance if n5 the string 0 O 1 1 0 corresponds to the subset 3 4 whereas 0 O O O 0 corresponds to the empty set and 1 1 1 1 1 identi es the set A 1 2 3 4 5 NOTATION The set of all subsets of A is denoted by 2 and called the power set of A We emphasize that 2A is not a number but iust a symbol to denote a set formed as explained above Thus ifA a b then 2A Q a b a b Of course the theorem above shows that the set 2A has 2IAI elements Notice how suggestive the notation chosen 2 is J Viola Prioli PROBLEM Assume A 20 Compute the number of subsets of A with at most 18 elements Solution There are 220 subsets of A Only one of them has 20 elements and there are 20 subsets with 19 elements Do you see why Can you list them Hence we have so far 21 subsets found These 21 subsets are precisely those we are not interested in Hence the answer is 220 21 See remarks Section 10 in our Syllabus for some additional problems with solutions J Viola Prioli
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'