Sets CSE235 Sets Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 1 Sections 1 6 1 7 of Rosen Introduction I Sets CSE235 We ve already implicitly dealt with sets integers Z rationals Q etc but here we will develop more fully the definitions properties and operations of sets Definition A set is an unordered collection of unique objects Sets are fundamental discrete structures that form the basis of more complex discrete structures like graphs Contrast this definition with the one in the book compare bag multi set tuples etc 2 1 Introduction II Sets CSE235 Definition The objects in a set are called elements or members of a set A set is said to contain its elements Recall the notation for a set A an element x we write x A if A contains x and x 6 A otherwise Latex notation in neg in 3 1 Terminology I Sets CSE235 Definition Two sets A and B are equal if they contain the same elements In this case we write A B Example 2 3 5 7 3 2 7 5 since a set is unordered Also 2 3 5 7 2 2 3 3 5 7 since a set contains unique elements However 2 3 5 7 6 2 3 4 1 Terminology II Sets CSE235 A multi set is a set where you specify the number of occurrences of each element m1 a1 m2 a2 mr ar is a set where m1 occurs a1 times m2 occurs a2 times etc Note in CS Databases we distinguish a set is w o repetition a bag is a set with repetition 5 1 Terminology III Sets We ve already seen set builder notation CSE235 O x x Z x 2k for some k Z should be read O is the set that contains all x such that x is an integer and x is even A set is defined in intension when you give its set builder notation O x x Z x 8 A set is defined in extension when you enumerate all the elements O 0 2 6 8 6 1 Venn Diagram Example Sets A set can also be represented graphically using a Venn diagram CSE235 U x A y B z a C Figure Venn Diagram 7 1 More Terminology Notation I Sets CSE235 A set that has no elements is referred to as the empty set or null set and is denoted A singleton set is a set that has only one element We usually write a Note the different brackets indicate that the object is a set while a without brackets is an element The subtle difference also exists with the empty set that is 6 The first is a set the second is a set containing a set 8 1 More Terminology Notation II Sets CSE235 Definition A is said to be a subset of B and we write A B if and only if every element of A is also an element of B That is we have an equivalence A B x x A x B 9 1 More Terminology Notation III Sets CSE235 Theorem For any set S S and S S Theorem 1 page 81 The proof is in the book note that it is an excellent example of a vacuous proof Latex notation emptyset subset subseteq 10 1 More Terminology Notation IV Sets CSE235 Definition A set A that is a subset of B is called a proper subset if A 6 B That is there is some element x B such that x 6 A In this case we write A B or to be even more definite we write A B Example Let A 2 Let B x x 100 x is prime Then A B Latex notation subsetneq 11 1 More Terminology Notation V Sets CSE235 Sets can be elements of other sets Example a b a b and 1 2 3 are sets with sets for elements 12 1 More Terminology Notation VI Sets CSE235 Definition If there are exactly n distinct elements in a set S with n a nonnegative integer we say that S is a finite set and the cardinality of S is n Notationally we write S n Definition A set that is not finite is said to be infinite 13 1 More Terminology Notation VII Sets CSE235 Example Recall the set B x x 100 x is prime its cardinality is B 25 since there are 25 primes less than 100 Note the cardinality of the empty set 0 The sets N Z Q R are all infinite 14 1 Proving Equivalence I Sets CSE235 You may be asked to show that a set is a subset proper subset or equal to another set To do this use the equivalence discussed before A B x x A x B To show that A B it is enough to show that for an arbitrary nonspecific element x x A implies that x is also in B Any proof method could be used To show that A B you must show that A is a subset of B just as before But you must also show that x x B x 6 A 15 1 Proving Equivalence II Sets CSE235 Finally to show two sets equal it is enough to show much like an equivalence that A B and B A independently Logically speaking this is showing the following quantified statements x x a x B x x B x A We ll see an example later 16 1 The Power Set I Sets CSE235 Definition The power set of a set S denoted P S is the set of all subsets of S Example Let A a b c then the power set is P S a b c a b a c b c a b c Note that the empty set and the set itself are always elements of the power set This follows from Theorem 1 Rosen p81 17 1 The Power Set II Sets CSE235 The power set is a fundamental combinatorial object useful when considering all possible combinations of elements of a set Fact Let S be a set such that S n then P S 2n 18 1 Tuples I Sets CSE235 Sometimes we may need to consider ordered collections Definition The ordered n tuple a1 a2 an is the ordered collection with the ai being the i th element for i 1 2 n Two ordered n tuples are equal if and only if for each i 1 2 n ai bi For n 2 we have ordered pairs 19 1 Cartesian Products I Sets CSE235 Definition Let A and B be sets The Cartesian product of A and B denoted A B is the set of all ordered pairs a b where a A and b B A B a b a A b B The Cartesian product is also known as the cross product Definition A subset of a Cartesian product R A B is called a relation We will talk more about relations in the next set …
View Full Document
Unlocking...