Notes Sets Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 1 6 1 7 of Rosen cse235 cse unl edu Introduction I Notes 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 Definition Introduction II Notes 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 Terminology I Notes 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 Terminology II Notes 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 I a set is w o repetition I a bag is a set with repetition Terminology III Notes We ve already seen set builder notation 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 Venn Diagram Notes Example A set can also be represented graphically using a Venn diagram U x A y B z a C Figure Venn Diagram More Terminology Notation I Notes 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 More Terminology Notation II 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 Notes More Terminology Notation III Notes Theorem For any set S I S and I 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 More Terminology Notation IV Notes 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 More Terminology Notation V Sets can be elements of other sets Example a b a b and 1 2 3 are sets with sets for elements Notes More Terminology Notation VI Notes 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 More Terminology Notation VII Notes 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 Proving Equivalence I 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 Finally to show two sets equal it is enough to show much like an equivalence that A B and B A independently Notes Proving Equivalence II Notes 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 The Power Set I Notes 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 The Power Set II Notes 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 Tuples I Notes 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 Cartesian Products I Notes 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 of slides Cartesian Products II Note that A B 6 B A unless A or B or A B Can you find a counter example to prove this Notes Cartesian Products III Notes Cartesian products can be generalized for any n tuple Definition The Cartesian product of n sets A1 …
View Full Document
Unlocking...