CMSC 250 Discrete Structures Set Theory Sets Definition of a Set NAME list or description of elements Examples B 1 2 3 C x Z 4 x 4 Axiom of Extension A set of elements is completely defined by elements regardless of order and duplicates Example a b b a a b a a b a b b a January 14 2019 Set Theory 2 Notation Sets defined by property C x Z 4 x 4 C 1 2 3 4 Consider elements glue tape pen Sets are not equivalent to elements glue glue Sets can be elements of other sets pen glue tape January 14 2019 Set Theory 3 Subset A B x U x A x B A is contained in B B contains A A B x U x A x B Relationship between membership and subset x U x A x A Definition of set equality A B A B B A January 14 2019 Set Theory 4 Same Set or Not X x Z p Z x 2p Y y Z q Z y 2q 2 A x Z i Z x 2i 1 B x Z i Z x 3i 1 C x Z i Z x 4i 1 January 14 2019 Set Theory 5 Versus glue glue tape pen glue glue tape pen glue glue tape pen glue glue tape pen January 14 2019 Set Theory 6 Sets C x x 4 and x 4 C x Z x 4 and x 4 What is the first element January 14 2019 Set Theory 7 Set Operations Formal Definitions and Venn Diagrams Union A B x U x A x B Intersection A B x U x A x B Complement c A A x U x A Difference A B x U x A x B A B A B January 14 2019 Set Theory 8 Procedural Versions of Set Definitions Let X and Y be subsets of a universal set U and suppose x and y are elements of U 1 2 3 4 5 x X Y x X or x Y x X Y x X and x Y x X Y x X and x Y x Xc x X x y X Y x X and y Y January 14 2019 Set Theory 9 Venn Diagrams A 1 2 5 7 B 1 5 C 3 7 U 1 2 3 4 5 6 7 B A 2 1 5 A 2 B 1B 5 7 C 3 January 14 2019 4 6 4 6 Set Theory A 7 C 3 10 Venn Diagram for R Z Q Z January 14 2019 Q Set Theory R 11 Ordered n Tuple Ordered n tuple x1 x2 x3 xn takes order and multiplicity into account n values not necessarily distinct in the order given x1 x2 x3 xn y1 y2 y3 yn i Z1 i n xi yi Examples a b b a a b b a Cartesian coordinate system January 14 2019 Set Theory 12 Cartesian Product A B a b a A b B Example A x y z B 5 7 C a b A B C A B C January 14 2019 Set Theory 13 Empty Set Properties 1 2 3 4 5 6 7 is a subset of every set There is only one empty set The union of any set with is that set The intersection of any set with its own complement is The intersection of any set with is The Cartesian Product of any set with is The complement of the universal set is and the complement of the empty set is the universal set January 14 2019 Set Theory 14 Other Definitions Proper Subset A B A B A B Disjoint Set A and B are disjoint A and B have no elements in common x U x A x B x B x A A B A and B are Disjoint Sets January 14 2019 Set Theory 15 Partitions of a Set A collection of nonempty sets A1 A2 An is a partition of the set A If and only if 1 A A1 A2 An 2 A1 A2 An are mutually disjoint January 14 2019 Set Theory 16 Power Sets Power set of A P A Set of all subsets of A Example A a b c Can also think of as a truth table Prove that A B sets A B P A P B Prove that where n X means the size of set X A sets n A k n P A 2k January 14 2019 Set Theory 17 Edwards Venn Diagram January 14 2019 Set Theory 18 Properties of Sets Theorems 5 2 1 5 2 2 Inclusion A B A A A B A B B B A B Transitivity A B B C A C DeMorgan s for Complement Distribution of union and intersection A B A B A B A B A B C A B A C A B C A B A C January 14 2019 Set Theory 19 Element Argument Basic Method for proving that one set is a subset of another Let sets X and Y be given To prove X Y Suppose that x is a particular but arbitrarily chosen element of X Show that x is an element of Y January 14 2019 Set Theory 20 Set Equality Two sets A and B are equal if and only if they have the same exact elements Expressed as A B A B A B A B January 14 2019 A B and B A x A x B x B x A x U x A x B x B x A x U x A x B x U x B x A Set Theory 21 Prove A C A n Z p Z n 2p C m Z q Z m 2q 2 January 14 2019 Set Theory 22 Does A D A x Z p Z x 2p D y Z q Z y 3q 1 Easy to disprove universal statements January 14 2019 Set Theory 23 Prove A B A A B LHS A B x U x A x B RHS A A B x U x U x U x U x U x U x U x U x A x A B x A x A B x A x A B x A x A x B x A x A x A x B FALSE x A x B x A x B x A x B LHS RHS January 14 2019 Set Theory 24 Prove A B A sets A B x U x A B x A Choose generic sets A B and element x U Assume x A B x A x B by def of intersection x A by conjunctive simplification x A B x A by closing cond world sets A B x U x A B x A January 14 2019 Set Theory 25 Using Venn Diagrams to help find counter example A B C A B C A B C A B A C A B C A B C …
View Full Document
Unlocking...