CSE115/ENGR160 Discrete Mathematics 02/09/122. 1 Basic structuresSetsNotationSlide 5Slide 6Sets and operationsSlide 8Venn diagramEmpty set and singletonSubsetEmpty set and the set S itselfProper subsetSets have other sets as membersCardinalityInfinite set and power setExampleCartesian productOrdered pairsSlide 20Slide 21Cartesian product: general caseUsing set notation with quantifiersTruth sets of quantifiersSlide 25CSE115/ENGR160 Discrete Mathematics02/09/12Ming-Hsuan YangUC Merced12. 1 Basic structures•Sets•Functions•Sequences•Sums2Sets•Used to group objects together•Objects of a set often have similar properties–all students enrolled at UC Merced–all students currently taking discrete mathematics•A set is an unordered collection of objects•The objects in a set are called the elements or members of the set•A set is said to contain its elements3Notation• •The set of all vowels in the English alphabet can be written as V={a, e, i, o, u}•The set of odd positive integers less than 10 can be expressed by O={1, 3, 5, 7, 9}•Nothing prevents a set from having seemingly unrelated elements, {a, 2, Fred, New Jersey}•The set of positive integers<100: {1,2,3,…, 99} 4otherwise : .set theofelemnet an is : AaAaAa Notation•Set builder: characterize the elements by stating the property or properties•The set O of all odd positive integers < 10: O={x|x is an odd positive integer < 10} or specify as•The set of positive rational numbers 5}10 and odd is |{ xxZxO} and integers positive somefor /|{ qpqpxRxQ Notation•The set {N, Z, Q, R} is a set containing four elements, each of which is a set6numbers real ofset the,numbers rational ofset the}0 and ,,|/{Qintegers positive ofset the}3,2,1{integers ofset the}1012{numbers natural ofset the,...}3,2,1{RqZqZpqp,...Z,..., , , -...,-ZNSets and operations•A datatype or type is the name of a set, •Together with a set of operations that can be performed on objects from that set•Boolean: the name of the set {0,1} together with operations on one or more elements of this set such as AND, OR, and NOT7Sets•Two sets are equal if and only if they have the same elements•That is if A and B are sets, then A and B are equal if and only if . We write A=B if A and B are equal sets•The sets {1, 3, 5} and {3, 5, 1} are equal•The sets {1, 3, 3, 3, 5, 5, 5, 5} is the same as {1, 3, 5} because the have the same elements8)( BxAxx Venn diagram•Rectangle: Universal set that contains all the objects•Circle: sets–U: 26 letters of English alphabet–V: a set of vowels in the English alphabet9Empty set and singleton•Empty (null) set: denoted by {} or Ø•The set of positive integers that are greater than their squares is the null set•Singleton: A set with one element •A common mistake is to confuse Ø with {Ø} 10Subset•The set A is a subset of B if and only if every element of A is also an element of B•Denote by A⊆B•We see A⊆B if and only if 11)( BxAxx Empty set and the set S itself•Theorem: or every set S–(i) Ø⊆S, and –(ii)S⊆S•Let S be a set, to show Ø⊆S, we need to show ∀x(x∈∅→x∈S) is true.•But x∈∅ is always false, and thus the conditional statement is always true•An example of vacuous proof•(ii) is left as an exercise12Proper subset•A is a proper subset of B: Emphasize that A is a subset of B but that A≠B, and write it as A⊂B•One way to show that two sets have the same elements is to show that each set is a subset of the other, i.e., if A⊆B and B⊆A, then A=B13)()( AxBxxBxAxx )( BxAxx Sets have other sets as members•A={∅, {a}, {b}, {a,b}} •B={x|x is a subset of the set {a, b}}•Note that A=B and {a}∊A but a∉A•Sets are used extensively in computing problem14Cardinality•Let S be a set. If there are exactly n distinct elements in S where n is a non-negative integer•S is a finite set•|S|=n, n is the cardi n ality of S–Let A be the set of odd positive integers < 10, |A|=5–Let S be the set of letters in English alphabet, |S|=26–The null set has no elements, thus |∅|=015Infinite set and power set•A set is said to be infinite if it is not finite–The set of positive integers is infinite•Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S)•The power set of {0,1,2}–P({0,1,2})={∅,{0},{1},{2},{0,1},{1,2},{0,2},{0,1,2}}–Note the empty set and set itself are members of this set of subsets16Example•What is the power set of the empty set?–P(∅)={∅} •The set {∅} has exactly two subsets, i.e., ∅, and the set {∅}. Thus P({∅})={∅,{∅}}•If a set has n elements, then its power set has 2n elements17Cartesian product•Sets are unordered•The ordered n-tuple (a1, a2, …, an) is the ordered collection that has a1 as its first element, a2 as its second element, and an as its nth element•(a1, a2, …, an)= (b1, b2, …, bn) if and only if ai=bi for i=1, 2, .., n18Ordered pairs•2-tupels are called ordered pairs•(a, b) and (c, d) are equal if and only if a=c and b=d•Note that (a, b) and (b, a) are not equal unless a=b19Cartesian product•The Cartesian product of sets A and B, denoted by A x B, is the set of all ordered pairs (a,b), where a ∊ A and b ∊ B•A: students of UC Merced, B: all courses offered at UC Merced•A x B consists of all ordered pairs of (a, b), i.e., all possible enrollments of students at UC Merced20}|),{( BbAabaBA Example•A={1, 2}, B={a, b, c}, What is A x B?–A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}•A subset R of the Cartesian product A x B is called a relation•A={a, b, c} and B={0, 1, 2, 3}, R={(a, 0), (a, 1), (a,3), (b, 1), (b, 2), (c, 0), (c,3)} is a relation from A to B•A x B ≠ B x A–B x A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}21Cartesian product: general case•Cartesian product of A1, A2, …, An, is denoted by A1 x A2 x … x An is the set of ordered n-tuples (a1, a2, …, an) where ai belongs to Ai for i=1, 2, …, n•A={0,1}, B={1,2}, C={0,1,2} A x B x C={{0, 1, 0},{0, 1, 1}, {0, 1, 2}, {0, 2, 0}, {0, 2, 1}, {0, 2, 2}, {1, 1, 0}, {1, 1, 1}, {1, 1, 2}, {1, 2, 0}, {1, 2, 1}, {1, 2, 2}}22niAaaaaAAAiinn,,2,1for ,|),,,{(2121 Using set notation with quantifiers• denotes the universal