SetsSubsetSame Set or Not??Set Operations Formal Definitions and Venn DiagramsOrdered n-tuple and the Cartesian ProductFormal LanguagesEmpty Set PropertiesOther DefinitionsProperties of Sets in Theorems 5.2.1 & 5.2.2Using Venn Diagrams to help find counter exampleDeriving new Properties using rules and Venn diagramsPartitions of a setProofs about Power SetsSetsDefinition of a Set:NAME = {list of elements or description of elements} i.e. B = {1,2,3} or C = {xZ+ | -4 < x < 4}Axiom of Extension: A set is completely defined by its elements i.e. {a,b} = {b,a} = {a,b,a} = {a,a,a,b,b,b}SubsetAB xU, xAx B A is contained in B B contains AA B x U, xA ^ xBRelationship between membership and subset:xU, xA {x} A Definition of set equality: A = B A B ^ B ASame Set or Not??X={xZ | p Z, x = 2p}Y={yZ | qZ, y = 2q-2}A={xZ | i Z, x = 2i+1}B={x Z | i Z, x = 3i+1}C={x Z | i Z, x = 4i+1}Set OperationsFormal Definitions and Venn DiagramsUnion:Intersection:Complement:Difference:}|{ BxAxUxBA }|{ BxAxUxBA }|{ BxAxUxBA }|{' AxUxAAc'BABA Ordered n-tuple and the Cartesian Product•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) iZ1in, xi=yi•Cartesian Product}|),{( BbAabaBA Formal Languages = alphabet = a finite set of symbols•string over =empty (or null) string denoted as ORordered n-tuple of elementsn = set of strings of length n* = set of all finite length stringsEmpty 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.Other Definitions•Proper Subset•Disjoint SetA and B are disjointA and B have no elements in commonxU, xAx B ^ xBx AAB = Ø A and B are Disjoint Sets •Power SetP (A) = set of all subsets of ABABABA Properties of Sets in 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 Using Venn Diagrams to help find counter example )()(?)( CABACBA CBACBA )(?)( Deriving new Propertiesusing rules and Venn diagrams )()()( CBABCAB )( BAABA )( CBACABA Partitions 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 disjointProofs about Power SetsPower set of A = P(A) = Set of all subsets of A•Prove that A,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)) =
View Full Document
Unlocking...