CMSC 250 Discrete StructuresSetsNotationSubsetSame Set or Not??? Versus Slide 7Set Operations Formal Definitions and Venn DiagramsProcedural Versions of Set DefinitionsVenn DiagramsVenn Diagram for R, Z, QOrdered n-TupleCartesian ProductEmpty Set PropertiesOther DefinitionsPartitions of a SetPower SetsEdwards-Venn DiagramProperties of Sets (Theorems 5.2.1 & 5.2.2)Element ArgumentSet EqualityProve A=CDoes A=DProve A – B = A – (A B)Prove A B AUsing Venn Diagrams to help find counter exampleDeriving new Properties using rules and Venn diagramsFormal LanguagesCMSC 250Discrete StructuresSet TheoryJanuary 14, 2019 Set Theory 2SetsDefinition of a Set:–NAME = {list or description of elements}–ExamplesB = {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 3NotationSets defined by property–C = {xZ+ | - 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 4SubsetAB xU, xA xB–A is contained in B–B contains AAB xU, xA xBRelationship between membership and subset:– xU, x A {x} ADefinition of set equality:– A = B AB BAJanuary 14, 2019 Set Theory 5Same Set or Not???X={xZ | pZ, x = 2p}Y={yZ | qZ, y = 2q-2}A={xZ | iZ, x = 2i+1}B={xZ | iZ, x = 3i+1}C={xZ | iZ, x = 4i+1}January 14, 2019 Set Theory 6 Versus glue {glue, tape, pen}{glue} {glue, tape, pen}{glue} {{glue}, {tape}, pen}{glue} {{glue}, {tape}, pen}January 14, 2019 Set Theory 7SetsC = {x | x > - 4 and x < 4}C = {xZ+ | x > - 4 and x < 4}–What is the first element?January 14, 2019 Set Theory 8Set OperationsFormal Definitions and Venn DiagramsUnion:Intersection:Complement:Difference:}|{ BxAxUxBA }|{ BxAxUxBA }|{ BxAxUxBA }|{' AxUxAAc'BABA January 14, 2019 Set Theory 9Procedural Versions of Set DefinitionsLet X and Y be subsets of a universal set U and suppose x and y are elements of U.1. x(XY) xX or x Y 2. x(XY) xX and xY 3. x(X–Y) xX and xY 4. xXc xX 5. (x,y) (XY) x X and yYJanuary 14, 2019 Set Theory 10Venn DiagramsA={1,2,5,7}; B= {1,5}; C={3,7}U={1,2,3,4,5,6,7}ACB7145326ACB7145326BAJanuary 14, 2019 Set Theory 11Venn Diagram for R, Z, QZ Q RJanuary 14, 2019 Set Theory 12Ordered n-TupleOrdered n-tuple – takes order and multiplicity into account(x1,x2,x3,…,xn) –n values–not necessarily distinct–in the order given(x1,x2,x3,…,xn) = (y1,y2,y3,…,yn) iZ1in, xi=yiExamples–{a,b} = {b,a}–{(a,b)} {(b,a)}–Cartesian coordinate systemJanuary 14, 2019 Set Theory 13Cartesian ProductExample–A = {x,y,z}–B = {5,7}–C = {a,b}A B C (A B) C }|),{( BbAabaBA January 14, 2019 Set Theory 14Empty Set Properties1. Ø is a subset of every set.2. There is only one empty set.3. The union of any set with Ø is that set.4. The intersection of any set with its own complement is Ø.5. The intersection of any set with Ø is Ø.6. The Cartesian Product of any set with Ø is Ø.7. The complement of the universal set is Ø and the complement of the empty set is the universal set.January 14, 2019 Set Theory 15Other DefinitionsProper SubsetDisjoint Set: A and B are disjointA and B have no elements in commonxU, xAxB ^ xBx AAB = Ø A and B are Disjoint SetsBABABA January 14, 2019 Set Theory 16Partitions of a SetA collection of nonempty sets {A1,A2,…,An} is a partition of the set AIf and only if1. A = A1 A2…An2. A1,A2,…,An are mutually disjointJanuary 14, 2019 Set Theory 17Power SetsPower set of A = P(A) = Set of all subsets of AExample: A={a,b,c}Can also think of as a truth table …Prove thatA,B{sets}, AB P(A) P(B) Prove that (where n(X) means the size of set X)A{sets}, n(A) = k n(P(A)) = 2kJanuary 14, 2019 Set Theory 18Edwards-Venn DiagramJanuary 14, 2019 Set Theory 19Properties of Sets (Theorems 5.2.1 & 5.2.2)Inclusion TransitivityDeMorgan’s for ComplementDistribution of union and intersectionABA BBA BAA BAB CACBBA '')'( BABA '')'( BABA )()()( CABACBA )()()( CABACBA January 14, 2019 Set Theory 20Element ArgumentBasic Method for proving that one set is a subset of anotherLet sets X and Y be given. To prove XY,–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 21Set EqualityTwo sets A and B are equal, if and only if, they have the same exact elements.Expressed as:–A=B AB and BA–A=B (xA, xB) (xB, xA)–A=B xU, (xAxB xBxA)–A=B (xU, xAxB) (xU, xBxA)January 14, 2019 Set Theory 22Prove A=CA={nZ | pZ, n = 2p}C={mZ | qZ, m = 2q-2}January 14, 2019 Set Theory 23Does A=DA={xZ | pZ, x = 2p}D={yZ | qZ, y = 3q+1}Easy to disprove universal statements!January 14, 2019 Set Theory 24Prove A – B = A – (A B)LHS: A – B = {xU | xA xB}RHS: A – (A B)={xU | x A x(A B)}={xU | x A x(A B)’}={xU | x A x(A’ B’)}={xU | x A (xA’ xB’)}={xU | (xA x A’) (xA xB’)}={xU | FALSE (x A xB’)}={xU | x A xB’}={xU | x A xB}LHS = RHSJanuary 14, 2019 Set Theory 25Prove A B Asets A,B xU x(A B) xAChoose generic sets A, B and element xUAssume x(A B)–xA xB (by def of intersection “”)–xA (by conjunctive simplification)x(A B) x A (by closing cond. world)sets A,B xU x(A B) xAJanuary 14, 2019 Set Theory 26Using Venn Diagrams to help find counter
View Full Document