Today’s topicsIntroduction to Set Theory (§1.6)Naïve set theoryBasic notations for setsBasic properties of setsDefinition of Set EqualityInfinite SetsVenn DiagramsBasic Set Relations: Member ofThe Empty SetSubset and Superset RelationsProper (Strict) Subsets & SupersetsSets Are Objects, Too!Cardinality and FinitenessThe Power Set OperationReview: Set Notations So FarNaïve Set Theory is InconsistentOrdered n-tuplesCartesian Products of SetsReview of §1.6Start §1.7: The Union OperatorUnion ExamplesThe Intersection OperatorIntersection ExamplesDisjointednessInclusion-Exclusion PrincipleSet DifferenceSet Difference ExamplesSet Difference - Venn DiagramSet ComplementsMore on Set ComplementsSet IdentitiesDeMorgan’s Law for SetsProving Set IdentitiesMethod 1: Mutual subsetsMethod 3: Membership TablesMembership Table ExampleMembership Table ExerciseReview of §1.6-1.7Generalized Unions & IntersectionsGeneralized UnionGeneralized IntersectionRepresentationsRepresenting Sets with Bit StringsCompSci 102 © Michael Frank 4.1Today’s topics•SetsSets–Indirect, by cases, and direct–Rules of logical inference–Correct & fallacious proofs•Reading: Sections 1.6-1.7Reading: Sections 1.6-1.7•UpcomingUpcoming–FunctionsFunctionsCompSci 102 © Michael Frank 4.2Introduction to Set Theory (§1.6)•A A setset is a new type of structure, representing an is a new type of structure, representing an unordered unordered collection (group, plurality) of zero or more collection (group, plurality) of zero or more distinct distinct (different) objects.(different) objects.•Set theory deals with operations between, relations among, Set theory deals with operations between, relations among, and statements about sets.and statements about sets.•Sets are ubiquitous in computer software systems.Sets are ubiquitous in computer software systems.•AllAll of mathematics can be defined in terms of some form of mathematics can be defined in terms of some form of set theory (using predicate logic).of set theory (using predicate logic).CompSci 102 © Michael Frank 4.3Naïve set theory•Basic premise:Basic premise: Any collection or class of objects Any collection or class of objects ((elementselements) that we can ) that we can describedescribe (by any means (by any means whatsoever) constitutes a set.whatsoever) constitutes a set.•But, the resulting theory turns out to be But, the resulting theory turns out to be logically logically inconsistentinconsistent! ! –This means, there exist naïve set theory propositions This means, there exist naïve set theory propositions pp such that such that you can prove that both you can prove that both pp and and pp follow logically from the axioms follow logically from the axioms of the theory!of the theory! The conjunction of the axioms is a contradiction!The conjunction of the axioms is a contradiction!–This theory is fundamentally uninteresting, because any possible This theory is fundamentally uninteresting, because any possible statement in it can be (very trivially) “proved” by contradiction!statement in it can be (very trivially) “proved” by contradiction!•More sophisticated set theories fix this problem.More sophisticated set theories fix this problem.CompSci 102 © Michael Frank 4.4Basic notations for sets•For sets, we’ll use variables For sets, we’ll use variables SS, , TT, , UU, … , … •We can denote a set We can denote a set SS in writing by listing in writing by listing all of its elements in curly braces: all of its elements in curly braces: –{a, b, c} is the set of whatever 3 objects are {a, b, c} is the set of whatever 3 objects are denoted by a, b, c.denoted by a, b, c.•SetSet builder notationbuilder notation: For any proposition : For any proposition PP((xx) over any universe of discourse, {) over any universe of discourse, {xx||PP((xx)} is )} is the set of all x such that P(x).the set of all x such that P(x).CompSci 102 © Michael Frank 4.5Basic properties of sets•Sets are inherently Sets are inherently unorderedunordered::–No matter what objects a, b, and c denote, No matter what objects a, b, and c denote, {a, b, c} = {a, c, b} = {b, a, c} ={a, b, c} = {a, c, b} = {b, a, c} ={b, c, a} = {c, a, b} = {c, b, a}.{b, c, a} = {c, a, b} = {c, b, a}.•All elements are All elements are distinctdistinct (unequal); (unequal);multiple listings make no difference!multiple listings make no difference!–If a=b, then {a, b, c} = {a, c} = {b, c} = If a=b, then {a, b, c} = {a, c} = {b, c} = {a, a, b, a, b, c, c, c, c}. {a, a, b, a, b, c, c, c, c}. –This set contains (at most) 2 elements!This set contains (at most) 2 elements!CompSci 102 © Michael Frank 4.6Definition of Set Equality•Two sets are declared to be equal Two sets are declared to be equal if and only ifif and only if they they contain contain exactly the sameexactly the same elements. elements.•In particular, it does not matter In particular, it does not matter how the set is defined or how the set is defined or denoted.denoted.•For example:For example: The set {1, 2, 3, 4} = The set {1, 2, 3, 4} = {{xx | | xx is an integer where is an integer where xx>0 and >0 and xx<5 } = <5 } = {{xx | | xx is a positive integer whose square is a positive integer whose square is >0 and <25} is >0 and <25}CompSci 102 © Michael Frank 4.7Infinite Sets•Conceptually, sets may be Conceptually, sets may be infiniteinfinite ( (i.e., i.e., not not finitefinite, , without end, unending).without end, unending).•Symbols for some special infinite sets:Symbols for some special infinite sets:NN = {0, 1, 2, …} The = {0, 1, 2, …} The NNatural numbers.atural numbers.ZZ = {…, -2, -1, 0, 1, 2, …} The = {…, -2, -1, 0, 1, 2, …} The ZZntegers.ntegers.RR = The “ = The “RReal” numbers, such as eal” numbers, such as 374.1828471929498181917281943125…374.1828471929498181917281943125…•““Blackboard Bold” or double-struck font (Blackboard Bold” or double-struck font (ℕℕ,,ℤℤ,,ℝℝ) ) is also often used for these special number sets.is also often used for these special number sets.•Infinite sets come in different sizes!Infinite sets come in different sizes!More on this after module #4 (functions).CompSci 102 © Michael Frank 4.8Venn DiagramsJohn Venn1834-1923CompSci 102 © Michael Frank 4.9Basic Set Relations: Member of•xxS S (“(“xx is in is in
View Full Document
Unlocking...