SetsCSE235SetsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.6 – 1.7 of [email protected] / 1SetsCSE235Introduction IWe’ve already implicitly dealt with sets (integers, Z; rationals(Q) etc.) but here we will develop more fully the definitions,properties and operations of sets.DefinitionA set is an unordered collection of (unique) objects.Sets are fundamental discrete structures that form the basis ofmore complex discrete structures like graphs.Contrast this definition with the one in the book (compare bag,multi-set, tuples, etc).2 / 1SetsCSE235Introduction IIDefinitionThe objects in a set are called elements or members of a set. Aset is said to contain its elements.Recall the notation: for a set A, an element x we writex ∈ Aif A contains x andx 6∈ Aotherwise.Latex notation: \in, \neg\in.3 / 1SetsCSE235Terminology IDefinitionTwo sets, A and B are equal if they contain the sameelements. In this case we write A = B.Example{2, 3, 5, 7} = {3, 2, 7, 5} since a set is unordered.Also, {2, 3, 5, 7} = {2, 2, 3, 3, 5, 7} since a set contains uniqueelements.However, {2, 3, 5, 7} 6= {2, 3}.4 / 1SetsCSE235Terminology IIA multi-set is a set where you specify the number ofoccurrences of each element: {m1· a1, m2· a2, . . . , mr· ar} isa set where m1occurs a1times, m2occurs a2times, etc.Note in CS (Databases), we distinguish:a set is w/o repetitiona bag is a set with repetition5 / 1SetsCSE235Terminology IIIWe’ve already seen set builder notation:O = {x | (x ∈ Z) ∧ (x = 2k for some k ∈ Z)}should be read O is the set that contains all x such that x is aninteger and x is even.A set is defined in intension, when you give its set buildernotation.O = {x | (x ∈ Z) ∧ (x ≤ 8)}A set is defined in extension, when you enumerate all theelements.O = {0, 2, 6, 8}6 / 1SetsCSE235Venn DiagramExampleA set can also be represented graphically using a Venn diagram.UA BCxyzaFigure: Venn Diagram7 / 1SetsCSE235More Terminology & Notation IA set that has no elements is referred to as the empty set ornull set and is denoted ∅.A singleton set is a set that has only one element. We usuallywrite {a}. Note the different: brackets indicate that the objectis a set while a without brackets is an element.The subtle difference also exists with the empty set: that is∅ 6= {∅}The first is a set, the second is a set containing a set.8 / 1SetsCSE235More Terminology & Notation IIDefinitionA is said to be a subset of B and we writeA ⊆ Bif and only if every element of A is also an element of B.That is, we have an equivalence:A ⊆ B ⇐⇒ ∀x(x ∈ A → x ∈ B)9 / 1SetsCSE235More Terminology & Notation IIITheoremFor any set S,∅ ⊆ S andS ⊆ S(Theorem 1, page 81.)The proof is in the book—note that it is an excellent exampleof a vacuous proof!Latex notation: \emptyset, \subset, \subseteq.10 / 1SetsCSE235More Terminology & Notation IVDefinitionA set A that is a subset of B is called a proper subset if A 6= B.That is, there is some element x ∈ B such that x 6∈ A. In thiscase we write A ⊂ B or to be even more definite we writeA ( BExampleLet A = {2}. Let B = {x | (x ≤ 100) ∧ (x is prime)}. ThenA ( B.Latex notation: \subsetneq.11 / 1SetsCSE235More Terminology & Notation VSets can be elements of other sets.Example{∅, {a}, {b}, {a, b}}and{{1}, {2}, {3}}are sets with sets for elements.12 / 1SetsCSE235More Terminology & Notation VIDefinitionIf there are exactly n distinct elements in a set S, with n anonnegative integer, we say that S is a finite set and thecardinality of S is n. Notationally, we write|S| = nDefinitionA set that is not finite is said to be infinite.13 / 1SetsCSE235More Terminology & Notation VIIExampleRecall the set B = {x | (x ≤ 100) ∧ (x is prime)}, itscardinality is|B| = 25since there are 25 primes less than 100. Note the cardinality ofthe empty set:|∅| = 0The sets N, Z, Q, R are all infinite.14 / 1SetsCSE235Proving Equivalence IYou may be asked to show that a set is a subset, proper subsetor equal to another set. To do t his, use the equivalencediscussed before:A ⊆ B ⇐⇒ ∀x(x ∈ A → x ∈ B)To show t hat A ⊆ B it is enough to show that for an arbitrary(nonspecific) element x, x ∈ A implies that x is also in B. Anyproof method could be used.To show t hat A ( B you must show that A is a subset of Bjust as before. But you must also show that∃x((x ∈ B) ∧ (x 6∈ A))15 / 1SetsCSE235Proving Equivalence IIFinally, to show two sets equal, it is enough to show (much likean equivalence) that A ⊆ B and B ⊆ A independently.Logically speaking this is showing the following quantifiedstatements:∀x(x ∈ a → x ∈ B)∧∀x(x ∈ B → x ∈ A)We’ll see an example later.16 / 1SetsCSE235The Power Set IDefinitionThe power s et of a set S, denoted P(S) is the set of all subsetsof S.ExampleLet A = {a, b, c} then the power set isP(S) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}Note that the empty set and the set itself are always elementsof the power set. This follows from Theorem 1 (Rosen, p81).17 / 1SetsCSE235The Power Set IIThe power set is a fundamental combinatorial object usefulwhen considering all possible combinations of eleme nts of a set.FactLet S be a set such that |S| = n, then|P(S)| = 2n18 / 1SetsCSE235Tuples ISometimes we may need to consider ordered collections.DefinitionThe ordered n-tuple (a1, a2, . . . , an) is the ordered collectionwith the aibeing the i-th element for i = 1, 2, . . . , n.Two ordered n-tuples are equal if and only if for eachi = 1, 2, . . . , n, ai= bi.For n = 2, we have ordered pairs.19 / 1SetsCSE235Cartesian Products IDefinitionLet A and B be sets. The Cartesian product of A and Bdenoted A × B, is the set of all ordered pairs (a, b) wherea ∈ A and b ∈ B:A × B = {(a, b) | (a ∈ A) ∧ (b ∈ B)}The Cartesian product is also known as the cross product.DefinitionA subset of a Cartesian product, R ⊆ A × B is called a relation.We will talk more about relations in the next set of slides.Note that A × B 6= B × A unless A = ∅ or B = ∅ or A = B.Can you find a counter example to prove this?20 / 1SetsCSE235Cartesian Products IICartesian products can be generalized for any n-tuple.DefinitionThe Cartesian product of n sets, A1, A2, . . . , An, denotedA1× A2× · · · × AnisA1×A2×· · ·×An= {(a1, a2, . . . , an) | ai∈ Aifor i = 1, 2, . . . , n}21 / 1SetsCSE235Notation With
View Full Document
Unlocking...