B Sets Etc Many chapters of this book touch on the elements of discrete mathematics This appendix reviews more completely the notations de nitions and elementary properties of sets relations functions graphs and trees If you are already well versed in this material you can probably just skim this chapter B 1 Sets A set is a collection of distinguishable objects called its members or elements If an object x is a member of a set S we write x 2 S read x is a member of S or more brie y x is in S If x is not a member of S we write x 62 S We can describe a set by explicitly listing its members as a list inside braces For example we can de ne a set S to contain precisely the numbers 1 2 and 3 by writing S D f1 2 3g Since 2 is a member of the set S we can write 2 2 S and since 4 is not a member we have 4 S A set cannot contain the same object more than once 1 and its elements are not ordered Two sets A and B are equal written A D B if they contain the same elements For example f1 2 3 1g D f1 2 3g D f3 2 1g We adopt special notations for frequently encountered sets denotes the empty set that is the set containing no members Z denotes the set of integers that is the set f 2 1 0 1 2 g R denotes the set of real numbers N denotes the set of natural numbers that is the set f0 1 2 g 2 1A variation of a set which can contain the same object more than once is called a multiset 2 Some with 0 authors start the natural numbers with 1 instead of 0 The modern trend seems to be to start B 1 Sets 1159 If all the elements of a set A are contained in a set B that is if x 2 A implies x 2 B then we write A B and say that A is a subset of B A set A is a proper subset of B written A B if A B but A B Some authors use the symbol to denote the ordinary subset relation rather than the proper subset relation For any set A we have A A For two sets A and B we have A D B if and only if A B and B A For any three sets A B and C if A B and B C then A C For any set A we have A We sometimes de ne sets in terms of other sets Given a set A we can de ne a set B A by stating a property that distinguishes the elements of B For example we can de ne the set of even integers by fx W x 2 Z and x 2 is an integerg The colon in this notation is read such that Some authors use a vertical bar in place of the colon Given two sets A and B we can also de ne new sets by applying set operations The intersection of sets A and B is the set A B D fx W x 2 A and x 2 Bg The union of sets A and B is the set A B D fx W x 2 A or x 2 Bg The difference between two sets A and B is the set A B D fx W x 2 A and x Bg Set operations obey the following laws Empty set laws A D A D A Idempotency laws A A D A A A D A Commutative laws A B D B A A B D B A 1160 Appendix B A Sets Etc B A B C A A C B D B C A C D B D A B C A C D B A B C A C Figure B 1 A Venn diagram illustrating the rst of DeMorgan s laws B 2 Each of the sets A B and C is represented as a circle Associative laws A B C D A B C A B C D A B C Distributive laws A B C D A B A C A B C D A B A C B 1 Absorption laws A A B D A A A B D A DeMorgan s laws A B C D A B A C A B C D A B A C B 2 Figure B 1 illustrates the rst of DeMorgan s laws using a Venn diagram a graphical picture in which sets are represented as regions of the plane Often all the sets under consideration are subsets of some larger set U called the universe For example if we are considering various sets made up only of integers the set Z of integers is an appropriate universe Given a universe U we de ne the complement of a set A as A D U A D fx W x 2 U and x 62 Ag For any set A U we have the following laws A D A A A D A A D U B 1 Sets 1161 We can rewrite DeMorgan s laws B 2 with set complements For any two sets B C U we have B C B C D B C D B C Two sets A and B are disjoint if they have no elements in common that is if A B D A collection S D fSi g of nonempty sets forms a partition of a set S if the sets are pairwise disjoint that is Si Sj 2 S and i j imply Si Sj D and their union is S that is Si SD Si 2S In other words S forms a partition of S if each element of S appears in exactly one Si 2 S The number of elements in a set is the cardinality or size of the set denoted jSj Two sets have the same cardinality if their elements can be put into a one to one correspondence The cardinality of the empty set is j j D 0 If the cardinality of a set is a natural number we say the set is nite otherwise it is in nite An in nite set that can be put into a one to one correspondence with the natural numbers N is countably in nite otherwise it is uncountable For example the integers Z are countable but the reals R are uncountable For any two nite sets A and B we have the identity jA Bj D jAj C jBj jA Bj B 3 from which we can conclude that jA Bj jAj C jBj If A and B are disjoint then jA Bj D 0 and thus jA Bj D jAj C jBj If A B then jAj jBj A nite set of n elements is sometimes called an n set A 1 set is called a singleton A subset of k elements …