离散数学DMA_2.1-4

《离散数学DMA_2.1-4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Module#2:TheTheoryofSetsRosen6thed.,§§2.1-2.2IntroductiontoSetTheory集合论(§2.1)Asetisanewtypeofstructure,representinganunorderedcollection(group,plurality)ofzeroormoredistinct(different)objects.Settheorydealswithoperationsbetween,relationsamong,andstatementsa

2、boutsets.Setsareubiquitousincomputersoftwaresystems.Allofmathematicscanbedefinedintermsofsomeformofsettheory(usingpredicatelogic).NaïvesettheoryBasicpremise:Anycollectionorclassofobjects(elements)thatwecandescribe(byanymeanswhatsoever)constitutesaset.But,th

3、eresultingtheoryturnsouttobelogicallyinconsistent!Thismeans,thereexistnaïvesettheorypropositionspsuchthatyoucanprovethatbothpandpfollowlogicallyfromtheaxiomsofthetheory!Theconjunctionoftheaxiomsisacontradiction!Thistheoryisfundamentallyuninteresting,becau

4、seanypossiblestatementinitcanbe(verytrivially)“proved”bycontradiction!Moresophisticatedsettheoriesfixthisproblem.BasicnotationsforsetsForsets,we’llusevariablesS,T,U,…WecandenoteasetSinwritingbylistingallofitselementsincurlybraces:{a,b,c}isthesetofwhatever3o

5、bjectsaredenotedbya,b,c.Setbuildernotation:ForanypropositionP(x)overanyuniverseofdiscourse,{x

6、P(x)}isthesetofallxsuchthatP(x).BasicpropertiesofsetsSetsareinherentlyunordered:Nomatterwhatobjectsa,b,andcdenote,{a,b,c}={a,c,b}={b,a,c}={b,c,a}={c,a,b}={c,b,a}

7、.Allelementsaredistinct(unequal);multiplelistingsmakenodifference!Ifa=b,then{a,b,c}={a,c}={b,c}={a,a,b,a,b,c,c,c,c}.Thissetcontains(atmost)2elements!DefinitionofSetEquality集合相等Twosetsaredeclaredtobeequalifandonlyiftheycontainexactlythesameelements.Inparti

8、cular,itdoesnotmatterhowthesetisdefinedordenoted.Forexample:Theset{1,2,3,4}={x

9、xisanintegerwherex>0andx<5}={x

10、xisapositiveintegerwhosesquareis>0and<25}InfiniteSets无限集Conceptually,setsmaybeinfinite(i.e.,notfinite,withoutend,unending).Symbolsforsomespecial

11、infinitesets:N={0,1,2,…}TheNaturalnumbers.Z={…,-2,-1,0,1,2,…}TheZntegers.R=The“Real”numbers,suchas374.1828471929498181917281943125…“BlackboardBold”ordouble-struckfont(ℕ,ℤ,ℝ)isalsooftenusedforthesespeci