CS 30: Discrete MathematicsProfessor'Amit'Chakrabarti'Teaching'Assistants'http://www.cs.dartmouth.edu/~cs304Sagar'Kale' Head4TA4Yining'Chen' Chief4grader4Richard'(Rick)'Dionne' Ninja4Nan'Hu' Ninja4Hang'(Christine)'Qi' Ninja4Shikhin'Sethi' Ninja4The Language of Mathematics• Math'is'not'just'a'tool,'it'is'a'way'of'communicating'ideas.'It'is'a'language.'We'must'Jirst'become'comfortable'with'it.'• The'building'blocks'of'this'language:'– Sets'– Integers'- More'general'numbers'(rational,'real,'complex,'…)'– Functions'– Logic'• More'advanced'math:'sets'are'the'only'building'blocks'we'need,'all'else'can'be'built'from'sets.'Review of SetsA'set'is'a'collection'of'distinct'objects.'• These'objects:'elements'or'members'of'the'set.'• If'x'is'an'element'of'the'set'S,'we'write'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''x'∈'S'(read:'“x'belongs'to'S”'or'“x'is'in'S”).''Example:'the'set'of'fruits'I'like,'F'='{apple, banana, fig, mango, pear}'• apple'is'an'element'of'F,'so'apple'∈'F.'• apricot'is'not,'so'apricot'∉'F.'Review of Sets, IIAn'element'either'belongs'to'a'set'or'does'not.'• No'such'thing'as'partially'belonging 'to'a'set.'• No'such'thing'as'number'of'copies 'of'an'element'in'a'set.''Example:''''''''set'of'letters'in'“DARTMOUTH'COLLEGE”'{'D,'A,'R,'T,'M,'O,'U,'H,'C,'L,'E,'G'}'='{'A,'C,'D,'E,'G,'H,'L,'M,'O,'R,'T,'U'}'='Finite and Infinite Sets• The'sets'seen'so'far'are'all'Jinite'sets.'• Number'of'elements'='cardinality'of'the'set.'• Notation:'|S|'='cardinality'of'set'S'• E.g.,'F'='{apple, banana, fig, mango, pear}'results'in'|F|'='5.'• Not'all'sets'are'Jinite.'E.g.,'the'set'of'all' even' natural'numbers'E'='{2,4,6,8,10,12,…}'is'an'inJinite'set.'– Other'inJinite'sets:'– N'='{1,2,3,4,…} ' ''the'set'of'natural'numbers – Z'='{...,-3,-2,-1,0,1,2,3,…} ' ''the'set'of'integers – Q'='{0,'1,'1/2,'2,'1/3,'2/3,'…,'9/5,'22/7,'...} 'rational'numbers – R'='the'set'of'real'numbers'(includes'√2,'π,'etc.)Other Interesting Possibilities• A'set'with'just'one'element'is'called'a'singleton'set.'E.g.,'{5}.'Note'that'the'set'{5}'is'not4the4same'as'the'integer'5.'• A'set'may'have'no'elements'at'all!'This'very'special'set'is'called'the'empty'set,'and'denoted'∅'or'{'}.'• The'elements'of'a'set'might'themselves'be'sets,'e.g.'{'{A,H,I,M,O,T,U,V,W,X,Y},'{B,C,D,E,H,I,K,O,X},'{H,I,O,X}'}.'• Quick'quiz:'what'is'the'cardinality'of'the'above'set?'• Answer:'3'Describing a SetThere'are'two'main'ways:'1. Roster'notation:'list'out'all'the'elements'– F'='{apple, banana, fig, mango, pear}'2. Set-builder'notation:'describe'the'property'of'a'generic'element'of'the'set'and'write'''{x':'some'property'of'x}.'– F'='{'x':'x'is'a'fruit'and'I'like' x'}'– Read:'“F'is'the'set'of'all'x'such'that'''''''''''''''''''''''''''''''''''''x'is'a'fruit'and'I'like'x.”'Describing Large or Infinite Sets• For'informal'descriptions,'using'an'ellipsis'is'Jine,'e.g.'{2,4,6,8,…}'or'{0,1,2,…,99}.'• But'in'formal'mathematical'writing'(such'as'in'this'course),'you'should'use'set-builder'notation.''• This'avoids'ambiguity,'e.g.,'when'you'see'{1,3,5,7,…}'is'it'– {1,3,5,7,'9,11,13,15,'17,…}'='{x':'x'is'an'odd'positive'integer}'?''– {1,3,5,7,11,13,17,19,23…}'='{x':'x'is'an'odd'prime'number}'?'– {1,3,5,7,11,13,15,17,21,23,25,27,…}'='{y':'y'is'an'odd'number'that'does'not'end'in'9}'?'Depicting Sets: Venn Diagrams1'11'21'51'81'121'36'256'76'201'49'100'25'6'606'C"A"B"Z A'='{1,11,21,51,81,121,201},'''B'='{6,36,76,256,606}'C'='{1,25,36,49,81,100,121,256},''Z'='set'of'all'integers'Operations on Sets: Union1'11'21'51'81'121'36'256'76'201'49'100'25'6'606'C"A"B"Z A'∪'C'='{1,'11,'21,'25,'36,'49,'51,'81,'100,'121,'201,'256}'S'∪'T'='{x':'either'x'∈'S'or'x'∈'T}'Operations on Sets: Intersection1'11'21'51'81'121'36'256'76'201'49'100'25'6'606'C"A"B"Z"A'∩'C'='{1,'81,'121}'S'∩'T'='{x':'x'∈'S'and'x'∈'T}'Disjoint Sets1'11'21'51'81'121'36'256'76'201'49'100'25'6'606'C"A"B"Z"Two'sets'with'no'elements'in'common,'e.g.'A'&'B'above.'Mathematically,'S'and'T'are'disjoint'if'S'∩'T'='∅.'Subsets• If'a'set'A'lies'completely'“within” a'set'B,'then'we'say'that'A'is'a'subset'of'B.'We'write'A'⊆'B.'• We'will'use'A'⊂'B'to'mean'“A'⊆'B'and'A'≠'B.”'• Mathematically,'A'⊆'B'means'that'every'element'of'A'is'also'an'element'of'B.''In'other'words,'if'x'∈'A'then'x'∈'B.'• Venn'diagram:'blob'for'A'sits'inside'blob'for'B.'• Quick'quiz:''are'there'any'subset'relationships'between'A,'A'∪'B'and'A'∩'B'?'– A'⊆'A'∪'B'– A'∩'B'⊆'A'Basic Facts about Subsets• For'any'set'A,'we'have'A'⊆'A.'• If'A'⊆'B'and'B'⊆'A,'then'A'='B.'– In'fact,'this'is'the'only'rigorous'way'to'prove'that'two'sets'A'and'B'are'equal.''Break'your'proof'into'two'parts.''First'prove'A'⊆'B.''Then'prove'B'⊆'A.'• For'any'set'A,'we'have'∅"⊆'A.'– Why'does'this'make'logical'sense?'– DeJinition'says'if'x'∈'∅'then'x'∈'A ,'but'∅'is'the'empty'set'so'we'can'never'have'x'∈'∅.'– Well'revisit'this'issue'when'we'study'logic.'For'now,'think'in'terms'of'Venn'diagrams.'Operations on Sets: Difference1'11'21'51'81'121'36'256'76'201'49'100'25'6'606'C"A"B"Z A'–'C'='{11,'21,'51,'201}'S'–'T'='{x':'x'∈'S'and'x'∉'T}'Operations on Sets: Complement1'11'21'51'81'121'36'256'76'201'49'100'25'6'606'C"A"B"Z Ā'='“A'complement”'='{all'integers'except'those'in'A}'Ā'='{x':'x'∈'Z'and'x'∉'A}'More Facts about SetsFor'any'two'sets'A'and'B,'• A'–'B'⊆'A.'• The'sets'B'and'(A'–'B)'are'disjoint.'• If'A'∩'B'='∅,'then'A'–'B'='A.''Many'interesting'distributive'laws,'e.g.'• A'∩'(B'∪'C)''=''(A'∩'B)'∪'(A'∩'C).'• (A'–'B)'∩'C''=''(A'∩'C)'–'(B'∩'C).'• But'beware!!''(A'–'B)'∪'C''≠''(A'∪'C)'–'(B'∪'C).'Cartesian ProductA'more'sophisticated'operation'on'sets:'produces'a'set'of'“ordered'pairs”'(a,b).'A'×'B''=''{'(a,b)':'a'∈'A'and'b'∈'B'}.''''''e.g.,''if'A'='{table,'pen,'hair},''B'='{red,'black},''then'A'×'B''='{'(table,'red),''(table,'black),''(pen,'red),''(pen,'black),'(hair,'black),''(hair,'black)'}.'black' (table,'black)' (pen,'black)' (hair,'black)'red' (table,'red)' (pen,'red)' (hair,'red)'table' pen' hair'Set versus Ordered