CompSci 102 © Michael Frank4.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 Frank4.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 unorderedunorderedcollection (group, plurality) of zero or more collection (group, plurality) of zero or more distinctdistinct(different) objects.(different) objects.••Set theory deals with operations between, relationsSet theory deals with operations between, relationsamong, and statements about sets.among, 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 formof set theory (using predicate logic).of set theory (using predicate logic).CompSci 102 © Michael Frank4.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 meanswhatsoever) constitutes a set.whatsoever) constitutes a set.••But, the resulting theory turns out to be But, the resulting theory turns out to be logicallylogicallyinconsistentinconsistent!!––This means, there exist naïve set theory propositions This means, there exist naïve set theory propositions pp such that such thatyou can prove that both you can prove that both pp and and ¬¬pp follow logically from the follow logically from theaxioms of the theory!axioms 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 possibleThis theory is fundamentally uninteresting, because any possiblestatement in it can be (very trivially) statement in it can be (very trivially) ““provedproved”” by contradiction! by contradiction!••More sophisticated set theories fix this problem.More sophisticated set theories fix this problem.CompSci 102 © Michael Frank4.4Basic notations for sets••For sets, weFor sets, we’’ll use variables ll use variables SS, , TT, , UU, , ……••We can denote a set We can denote a set SS in writing by listing in writing by listingall 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 aredenoted by a, b, c.denoted by a, b, c.••SetSet builder notationbuilder notation: For any proposition: For any propositionPP((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 Frank4.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 Frank4.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 theycontain 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 orhow the set is defined ordenoted.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 Frank4.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, = {0, 1, 2, ……} The } The NNatural numbers.atural numbers.ZZ = { = {……, -2, -1, 0, 1, 2, , -2, -1, 0, 1, 2, ……} The } The ZZntegersntegers..RR = The = The ““RRealeal”” numbers, such as numbers, such as374.1828471929498181917281943125374.1828471929498181917281943125……••““Blackboard BoldBlackboard Bold”” or double-struck font ( 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 Frank4.8Venn DiagramsJohn Venn1834-1923CompSci 102 © Michael Frank4.9Basic Set Relations: Member of••xx S S ((““xx is in is in SS””)) is the proposition thatis the proposition thatobject object xx is an is an lementlement or or membermember of set of set SS..––e.g.e.g. 3 3 NN, , ““aa”” {{xx | | xx is a letter of the alphabet} is a letter of the alphabet}––Can define set equality in terms of Can define set equality in terms of relation: relation:SS,,TT: : SS==T T ( (xx: : xx SS xx TT))““Two sets are equal Two sets are equal iffiff they have all the same they have all the samemembers.members.””••xxS S :: ¬¬((xx SS) ) ““xx is not in is not in SS””CompSci 102 © Michael Frank4.10The Empty Set•• ( (““nullnull””, , ““the empty setthe empty set””) is the unique) is the uniqueset that contains no elements whatsoever.set that contains no elements whatsoever.•• = {} = { = {} = {x|x|FalseFalse}}••No matter the domain of discourse,No matter the domain of discourse,we have the
View Full Document
Unlocking...