Introduction I Sets Slides by Christopher M Bourke Instructor Berthe Y Choueiry 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 Fall 2007 Sets are fundamental discrete structures that form the basis of more complex discrete structures like graphs Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 2 1 2 2 of Rosen cse235 cse unl edu Introduction II Contrast this definition with the one in the book compare bag multi set tuples etc Definition Terminology I 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 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 otherwise Also 2 3 5 7 2 2 3 3 5 7 since a set contains unique elements Latex notation in notin However 2 3 5 7 6 2 3 Terminology II Terminology III We ve already seen set builder notation O x x Z x 2k for some k Z 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 should be read O is the set that contains all x such that x is an integer and x is even Note in CS Databases we distinguish A set is defined in intension when you give its set builder notation I a set is w o repetition I a bag is a set with repetition O x x Z 0 x 8 x 2k for some k Z A set is defined in extension when you enumerate all the elements O 0 2 4 6 8 Venn Diagram More Terminology Notation I Example A set can also be represented graphically using a Venn diagram A set that has no elements is referred to as the empty set or null set and is denoted U x A y B z 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 C a 6 The first is a set the second is a set containing a set Figure Venn Diagram More Terminology Notation II More Terminology Notation III Definition Theorem A is said to be a subset of B and we write For any set S A B I S and I S S if and only if every element of A is also an element of B Theorem 1 page 115 That is we have an equivalence A B x x A x B 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 More Terminology Notation V 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 Sets can be elements of other sets Example A B a b a b and Example Let A 2 Let B x x N x 100 x is prime Then A B Latex notation subsetneq 1 2 3 are sets with sets for elements More Terminology Notation VI Definition More Terminology Notation VII Example 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 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 A set that is not finite is said to be 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 Proving Equivalence II 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 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 The Power Set I The Power Set II Definition The power set of a set S denoted P S is the set of all subsets of S The power set is a fundamental combinatorial object useful when considering all possible combinations of elements of a set Fact Example Let S be a set such that S n then 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 p115 P S 2n Tuples I Cartesian Products I Definition Sometimes we may need to consider ordered collections 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 Definition A B a b a A b B 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 The Cartesian product is also known as the cross product Definition For n 2 we have ordered pairs 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 Cartesian Products III Cartesian products can be generalized for any n tuple Note that A B 6 B A unless A or B or A B Can you find a counter example to prove this Definition The Cartesian product of n sets A1 A2 An denoted A1 A2 An is A1 A2 An a1 a2 an …
View Full Document
Unlocking...