DOC PREVIEW
UMD CMSC 250 - Set Theory

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 2Sets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 3Notation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 4Subset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AJanuary 14, 2019 Set Theory 5Same 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 6 Versus glue  {glue, tape, pen}{glue}  {glue, tape, pen}{glue}  {{glue}, {tape}, pen}{glue}  {{glue}, {tape}, pen}January 14, 2019 Set Theory 7Sets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 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(XY) xX or x Y 2. x(XY) xX and xY 3. x(X–Y) xX and xY 4. xXc xX 5. (x,y) (XY) x X and yYJanuary 14, 2019 Set Theory 10Venn DiagramsA={1,2,5,7}; B= {1,5}; C={3,7}U={1,2,3,4,5,6,7}ACB7145326ACB7145326BAJanuary 14, 2019 Set Theory 11Venn Diagram for R, Z, QZ Q RJanuary 14, 2019 Set Theory 12Ordered n-TupleOrdered 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) iZ1in, xi=yiExamples–{a,b} = {b,a}–{(a,b)}  {(b,a)}–Cartesian coordinate systemJanuary 14, 2019 Set Theory 13Cartesian ProductExample–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 DefinitionsProper SubsetDisjoint Set: A and B are disjointA and B have no elements in commonxU, xAxB ^ xBx AAB = Ø  A and B are Disjoint SetsBABABA January 14, 2019 Set Theory 16Partitions of a SetA collection of nonempty sets {A1,A2,…,An} is a partition of the set AIf 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 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)) = 2kJanuary 14, 2019 Set Theory 18Edwards-Venn DiagramJanuary 14, 2019 Set Theory 19Properties of Sets (Theorems 5.2.1 & 5.2.2)Inclusion TransitivityDeMorgan’s for ComplementDistribution of union and intersectionABA  BBA BAA BAB CACBBA '')'( BABA   '')'( BABA  )()()( CABACBA  )()()( CABACBA  January 14, 2019 Set Theory 20Element 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 21Set EqualityTwo sets A and B are equal, if and only if, they have the same exact elements.Expressed as:–A=B  AB and BA–A=B  (xA, xB)  (xB, xA)–A=B  xU, (xAxB  xBxA)–A=B  (xU, xAxB) (xU, xBxA)January 14, 2019 Set Theory 22Prove A=CA={nZ | pZ, n = 2p}C={mZ | qZ, m = 2q-2}January 14, 2019 Set Theory 23Does A=DA={xZ | pZ, x = 2p}D={yZ | qZ, y = 3q+1}Easy to disprove universal statements!January 14, 2019 Set Theory 24Prove A – B = A – (A  B)LHS: A – B = {xU | xA  xB}RHS: A – (A  B)={xU | x A  x(A  B)}={xU | x A  x(A  B)’}={xU | x A  x(A’  B’)}={xU | x A  (xA’  xB’)}={xU | (xA  x A’)  (xA  xB’)}={xU | FALSE  (x A  xB’)}={xU | x A  xB’}={xU | x A  xB}LHS = RHSJanuary 14, 2019 Set Theory 25Prove 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AJanuary 14, 2019 Set Theory 26Using Venn Diagrams to help find counter


View Full Document

UMD CMSC 250 - Set Theory

Download Set Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Set Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Set Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?