Set, Combinatorics, Probability & Number TheorySet theorySlide 3Set Theory ExamplesSet Theory BasicsOpen and closed intervalRelationship between SetsSlide 8ExerciseSet of SetsSet operationsBinary or unary operationsOperations on SetsDisjoint, Universal and Difference SetsClass ExerciseCartesian ProductBasic Set IdentitiesMore set identitiesSlide 19Set, Combinatorics, Probability & Number TheoryMathematical Structures for Computer ScienceChapter 3Copyright © 2006 W.H. Freeman & Co. MSCS Slides Set, Combinatorics, Probability & Number TheorySection 3.1 Sets 2Set theorySets: Powerful tool in computer science to solve real world problems.The concepts of set and element have no clear-cut definition, except as they relate to each other. A set is a collection of elements or objects, and an element is a member of a set. Traditionally, sets are described by capital letters, and elements by lower case letters.The symbol means “belongs to” and is used to represent the fact that an element belongs to a particular set. Hence, aA means that element a belongs to set A.bA implies that b is not an element of A.Braces {} are used to indicate a set.A = {2, 4, 6, 8, 10} 3A and 2ASection 3.1 Sets 3Set theoryOrdering is not imposed on the set elements and listing elements twice or more is redundant.Two sets are equal if and only if they contain the same elements.Hence, A = B means (x)[(x A x B) Λ (x B x A)] Finite and infinite set: described by number of elements in a setMembers of infinite sets cannot be listed, but a pattern for listing elements could be indicated. e.g. S = {x x is a positive even integer} or using predicate notation.S = {x P(x)} means (x)[(x S P(x)) Λ (P(x) x S)] where P is the unary predicate.Hence, every element of S has the property P and everything that has a property P is an element of S.Section 3.1 Sets 4Set Theory ExamplesDescribe each of the following sets by listing the elements:{x | x is a month with exactly thirty days}{April, June, September, November}{x | x is an integer and 4 < x < 9}{5, 6, 7, 8}What is the predicate for each of the following sets?{1, 4, 9, 16}{x | x is one of the first four perfect squares}{2, 3, 5, 7, 11, 13, 17, ….}{x | x is a prime number}Section 3.1 Sets 5Set Theory BasicsA set that has no members is called a null or empty set and is represented by or {}.Note that is different from {}. The latter is a set with 1 element, which is the empty set.Some notations used for convenience of defining setsN = set of all nonnegative integers (note that 0 N)Z = set of all integersQ = set of all rational numbersR = set of all real numbersC = set of all complex numbersUsing the above notations and predicate symbols, one can describe sets quite easilyA = {x | (y)(y {0,1,2} and x = y2}Hence, A = {0,1, 4}A = {x | x N and (y)(y {2, 3, 4, 5} x y)}B = {x | (y)(z)(y {1,2} and z {2,3} and x = z – y) }Section 3.1 Sets 6Open and closed interval{x R | -2 < x < 3}Denotes the set containing all real numbers between -2 and 3. This is an open interval, meaning that the endpoints -2 and 3 are not included. By all real numbers, we mean everything such as 1.05, -3/4, and every other real number within that interval. {x R | -2 x 3}Similar set but on a closed interval It includes all the numbers in the open interval described above, plus the endpoints.Section 3.1 Sets 7Relationship between SetsSay S is the set of all people, M is the set of all male humans, and C is the set of all computer science students.M and C are both subsets of S, because all elements of M and C are also elements of S.M is not a subset of C, however, since there are elements of M that are not in C (specifically, all males who are not studying computer science). For sets S and M, M is a subset of S if, and only if, every element in M is also an element of S.Symbolically: M S (x), if x M, then x S.If M S and M S, then there is at least one element of S that is not an element of M, then M is a proper subset of S.Symbolically, denoted by M SSection 3.1 Sets 8Relationship between SetsA superset is the opposite of subset. If M is a subset of S, then S is a superset of M. Symbolically, denoted S M. Likewise, if M is a proper subset of S, then S is a proper superset of M.Symbolically, denoted S M.Cardinality of a set is simply the number of elements within the set.The cardinality of S is denoted by |S|. By the above definition of subset, it is clear that set M must have fewer members than S, which yields the following symbolic representation: M S |M| < |S|Section 3.1 Sets 9ExerciseA = {x | x N and x 5} {5, 6, 7, 8, 9, …… }B = {10, 12, 16, 20}C = {x | (y)(y N and x = 2y)} {0, 2, 4, 6, 8, 10, …….} What statements are true?B C B A A C 26 C {11, 12, 13} A {11, 12, 13} C{12} B {12} B {x | x N and x < 20} B 5 A{} B A Section 3.1 Sets 10Set of SetsFor the following sets, prove A B.A = { x | x R such that x2 – 4x + 3 = 0}A = {1, 3}B = { x | x N and 1 x 4}B = {1, 2, 3, 4}All elements of A exist in B, hence A B.From every set, many subsets can be generated. A set whose elements are all such subsets is called the power set.For a set S, (S) is termed as the power set.For a set S = {1, 2, 3} ; (S) = { ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}For a set with n elements, the power set has 2n elements.Section 3.1 Sets 11Set operationsBinary and unary operatorsBinary acts on two elements, say x-y or y-x.Unary acts on a single element, say negation of an element x is –x.Example: +, - and * are all binary operators on Z.An ordered pair of elements is written as (x,y) and is different from (y,x).Two ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.If S = {2,3}, the ordered pairs of this set are (2,2), (2,3), (3,2), (3,3).Binary operation (represented by ) on a set defined as follows: If for every ordered pair (x,y) of elements of S, x y exists, and is unique, and is a
View Full Document