资源描述：
《1 mathematical preliminaries》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1MathematicalPreliminaries1.1IntroductionAnAfricanexplorerconversantwiththelanguageoftheHottentottribeasksanative,“Howmanychildrendoyouhave?”Thetribesmananswers,“Many.”Thedeterminedexplorerpersistson.Heshowshisindexfinger,meaning“one?”Promptlycomestheanswer,“no.”Headdshismiddlefinger,meaning“two”;thea
2、nsweris“no”;“three?,”“no”;“four,”“no.”Nowallthefivefingersontheexplorer’srighthandarestraight.Answercomes,“yes.”Thepuzzledexplorerexperimentswithanothertribesman.Overthenextweek,hediscoversthattheyhaveonlythreekindsofnumbers,one,two,andmany.Itisanoldstory,butperhapsnotwithoutmorals.TheHottentottribesm
3、andoesnothaveawayofnamingthenumbersmorethantwo.Howdoeshemanagehiscattle?Ourmathematicaltraditionhasgonesofarandsodeepthatitisindeeddifficulttoimaginelivingwithoutit.Inthissmallchapter,wewilldiscussafragmentofthistraditionsothattheritualsoflearningthetheoryofcomputationcanbeconductedrelativelyeasily.I
4、ntheprocess,wewillfixournotation.1.2SetsAsetisacollectionofobjects,calleditsmembersorelements.Whenwritingasetbyshowingitselements,wewriteitwithtwoclosingcurlybrackets.Thecurlybracketsservetwopurposes:one,itshowstheelementsinside,andtwo,itsaysthatthewholethingputtogetherisanotherobjectonitsownright.So
5、metimes,webecometiredofwritingoutalltheelements,andweputthreedots.Forexample,{pen,pencil,knife,scissors,paper,chalk,duster,paperweight,...}isthesetofnamesofeducationalstationery.Itistheextensionalwayofrepresentingaset.Butwhatabouttheexpression,“thesetofnamesofeducationalstationery?”Itisaset,nonethel
6、ess,andthesamesetasabove.WethusagreetorepresentaA.Singh,ElementsofComputationTheory,TextsinComputerScience,1cSpringer-VerlagLondonLimited200921MathematicalPreliminariessetbyspecifyingapropertythatmaybesatisfiedbyeachofitselements.Itistheintensionalwayofrepresentingaset.(Notethespellingof“intensional
7、.”)IfAisasetandaisanelementinA,wewriteitasa∈A.ThefactthataisnotanelementofAiswrittenasa∈A.Whenspecifyingasetbyaproperty,wewriteitas{x:P(x)},meaningthatthissethasallandonlythosexaselementswhichsatisfy
