Chapter 5 Set Theory CMSC 250 1 Set definitions Definition of a set name of set list of elements or a description of the elements Examples A 1 2 3 or B x Z 4 x 4 or C x Z 4 x 4 A set is completely defined by its elements i e a b b a a b a a a a b b b CMSC 250 2 Discrete Structures CMSC 250 Lecture 28 April 7 2008 CMSC 250 3 More set concepts CMSC 250 The universal set U is the set consisting of all possible elements in some particular situation under consideration A set can be finite or can be infinite For a set S n S or S are used to refer to the cardinality of S which is the number of elements in S The symbol means is an element of The symbol means is not an element of 4 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 CMSC 250 5 Do these represent the same sets 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 CMSC 250 6 Formal definitions of set operations Union A B x U x A x B Intersection A B x U x A x B c Complement A A A x U x A Difference A B x U x A x B A B A B CMSC 250 7 Venn diagrams Sets are represented as regions usually circles in the plane in order to graphically illustrate relationships between them A CMSC 250 B A B 8 The empty set and its properties The empty set has no elements so 1 2 3 4 5 6 7 CMSC 250 sets X X There is only one empty set sets X X X sets X X X sets X X U U 9 Discrete Structures CMSC 250 Lecture 29 April 9 2008 CMSC 250 10 Ordered n tuples An ordered n tuple takes order and multiplicity into account The tuple x1 x2 x3 xn has n values which are not necessarily distinct and which appear in the order listed x1 x2 x3 xn y1 y2 y3 yn i 1 i n xi yi 2 tuples are called pairs and 3 tuples are called triples CMSC 250 11 The Cartesian product The Cartesian product of sets A and B is defined as A B a b a A b B n A B n A n B CMSC 250 12 Proper subset A B A B A B CMSC 250 13 Disjoint sets 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 CMSC 250 14 Power set P A the set of all subsets of A Examples what are P a CMSC 250 P a b c P P P 15 Properties of sets in Theorem 5 2 1 Inclusion A B A A A B Transitivity CMSC 250 A B B B A B A B B C A C 16 Discrete Structures CMSC 250 Lecture 30 April 11 2008 CMSC 250 17 Properties of sets in Theorem 5 2 2 DeMorgan s for complement A B A B A B A B Distribution of union and intersection A B C A B A C A B C A B A C There are a number of others as well see the text or the handout of logical rules and equivalences for the full list CMSC 250 18 Using Venn diagrams to help find counterexamples A B C A B A C A B C A B C CMSC 250 19 Deriving new properties using rules and Venn diagrams B A C B A B C A B A A B A B A C A B C CMSC 250 20 Discrete Structures CMSC 250 Lecture 32 April 16 2008 CMSC 250 21 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 CMSC 250 An infinite set can be partitioned The partitions can be infinite or can be finite 22 Proofs about power sets Prove that sets A B A B P A P B Prove that sets A n A k n P A 2k CMSC 250 23 Russell s paradox A set can be an element or member of itself Consider the set S A A is a set and A A Is S an element of itself CMSC 250 24 The halting problem Is there a computer program suppose it s called Halt which will read as input any program pgm plus some input for that program and be able to determine whether pgm will eventually halt or loop infinitely when run on that input What if we write a program which just runs another program on some input and sees whether it halts and prints the result CMSC 250 25 Discrete Structures CMSC 250 Lecture 33 April 18 2008 CMSC 250 26 Proof for the halting problem Suppose there is a program Halt pgm input which can determine whether any program pgm will halt when run on the input data input or loop infinitely Create a new program Test which also reads another program as input as follows void Test pgm if Halt pgm pgm prints that pgm halts then while true infinite loop never quit else Halt pgm pgm prints that pgm loops infinitely on input exit CMSC 250 27 What if Test is run on itself Now run Test Test if Test Test halts then Halt Test Test will print that Test will halt in which case Test Test loops forever if Test Test loops forever then Halt Test Test will print that Test will loop infinitely in which case Test Test quits CMSC 250 28
View Full Document
Unlocking...