(黄)第1章集合(2016-3-12).

离散数学第1章集合§1集合的基本概念§2集合的基本运算2§１集合的基本概念本节要求掌握的知识点：1、集合的概念2、集合的几种表示方法3、子集（真子集），集合相等（证明？）4、全集和补集（余集）5、幂集，集合的基，有限集合的幂集的基？3现代集合论的创立者：康托（GeorgCantor）德国数学家贡献：超限数，康托对角线法的发现由于他的理论超越直观，所以曾受到当时一些大数学家的反对，克莱因（Klein,ChristianFelix)、庞加莱(HenriPoincare)、韦尔(HermannWeyl)等著名数学家对康托的集合论持激烈的反对态度,把康托的集合论贬为“病理情形”、HermannWeyl称Cantor的的等级为“雾上之雾”（fogonfog),把康托本人称作“疯子”。GeorgCantor1845-1918甚至他的老师克罗内克（L.Kronecker）攻击康托是神经质，走进了超越数的地狱.对于这些非难和指责，康托仍充满信心，他说:我的理论犹如磐石一般坚固，任何反对它的人将搬起石头砸自己的脚.他还指出:数学的本质在于它的自由性，不必受传统观念束缚。这种争辩持续了十年之久。康托由于经常处于精神压抑之中，致使他1884年患了精神分裂症，最后死于精神病院。伟大德国数学家希尔伯特（DavidHilbert）1926年曾说道：“没有人能把我们从康托为我们创造的乐园中驱赶走”1897年举行的第一次国际数学家会议，Cantor的成就得到承认。DavidHilbert1862-1943并称Cantor的超限算数为“数学思想最惊人的产物，在纯粹理性的范畴中人类的最美观的表现之一”（NooneshallexpelusfromtheparadisewhichCantorcreatedforus.)(themostastonishingproductofmathematicalthought,oneofthemostbeautifulrealizatiomsofhumanactivityinthedomainofthepurelyintelligible.)伯特兰·罗素（BertrandRussell）把康托的工作描述为probablythegreatestofwhichtheagecanboast.（可能是这个时代所能夸耀的最伟大的工作）BertrandRussell1872-1970BertrandRussell英国数学家、数理逻辑学家，哲学家，无神论或者不可知论者，也是上世纪西方最著名、影响最大的学者与和平主义社会活动家之一。1950年获Nobel文学奖以表彰其“多样且重要的作品，持续不断的追求人道主义理想和思想自由”。《数学原理》,《西方哲学史》,《幸福之路》,《物的分析》等朴素集合论中存在悖论一、罗素悖论（Russell'sparadox）(导致第三次数学危机）x}x|{xRRRRR1.RRRR2.一个乡村理发师自称他只给不给自己理发的人理发。理发师给自己理发理发师不给自己理发理发师不给自己理发理发师给自己理发罗素悖论的通俗形式（乡村理发师悖论）现在的问题是这个理发师给不给自己理发？理发师陷入了两难：进退维谷二、由一切集合构成的集合的悖论}x|{xV为集合是集合会导致罗素悖论解决此悖论方法：不再是集合，而把它称为真类（properclass）。若庄子与惠子游于濠梁之上。庄子曰：“鲦鱼出游从容，是鱼乐也。”惠子曰：“子非鱼，安知鱼之乐？”庄子曰：“子非我，安知我不知鱼之乐？”惠子曰：“我非子，固不知子矣，子固非鱼也，子不知鱼之乐，全矣。”庄子曰：“请循其本。子曰汝安知鱼乐云者，既已知吾知之而问我，我知之濠上也。”濠梁之辩《庄子﹒秋水》囚徒困境庄周梦蝶（《庄子·齐物论》）昔者庄周梦为蝴蝶，栩栩然蝴蝶也，自喻适志与，不知周也。俄然觉，则蘧蘧然周也。不知周之梦为蝴蝶与，蝴蝶之梦为周与？周与蝴蝶，则必有分矣。此之谓物化。过去庄周梦见自己变成蝴蝶，很生动逼真的一只蝴蝶，感到多么愉快和惬意啊！不知道自己原本是庄周。突然间醒过来，惊惶不定之间方知原来是我庄周。不知是庄周梦中变成蝴蝶呢，还是蝴蝶梦中变成庄周呢？庄周与蝴蝶那必定是有区别的。这就可叫作物、我的交合与变化。译文BashGame:同余理论NimGame:异或理论WythoffGame:黄金分割BashGame:同余理论一堆n个物品,两人轮流取,每次取1至m个,最后取完者胜.(mn)接着如果后取者再拿走k(1≤k≤m)个，那么先取者再拿走(m+1-k)个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。1.如果n=m+1，后取者取胜。2.如果n=(m+1)r+s,(r为任意自然数,0≤s≤m)(1)当s=0时，后取者胜；(2)当1≤s≤m时,那么先取者要拿走s个物品,NimGame:异或理论m堆物品，每堆若干件物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜.所有物品数目二进制按位的异或为0,先手必输.所有物品数目二进制按位的异或不为0,后手必输.当m=3时，也称为三堆物博弈·设现有三堆棋子，三堆的数量分别为a,b,c甲乙两人轮流从这三堆中取棋子，游戏规则如下：甲先取棋子，每人每一次只能选定任意一堆，从这一堆取棋子的数量不限，但至少要从这一堆中选取一个，谁最先取完这三堆棋子谁胜。对于下列三种情形：问甲、乙二人谁有胜的策略。若甲有胜的策略，甲第一回合应如何取；若乙有胜的策略，在甲第一回合从第一堆个中取走2个后，乙第一回合应如何正确地应对？请用二进制数的异或理论加以说明。（1）(a,b,c)=(13,22,27)（2）(a,b,c)=(23,10,13)（3）(a,b,c)=(21,29,15)（1）(a,b,c)=(13,22,27)a=13b=22c=27110110110=1101111011^00000解乙有胜的策略。1101^10110在甲第一回合从一堆个中取走2个后，10111011011011^001101000011011000001011^-=110乙第一回合应从第二堆中取走(110)2=6个（2）(a,b,c)=(23,10,13)a=23b=10c=131011110101101^10000解甲有胜的策略。0011110101101^00000-=10000甲第一回合应从第一堆中取走(10000)2=16个（3）(a,b,c)=(21,29,15)a=21b=29c=1510101111011111^00111解甲有胜的策略。100101111^00000-=101甲第一回合应从第一堆中取走(101)2=5个11101（3）(a,b,c)=(21,29,15)a=21b=29c=1510101111011111^00111解10101110101111^00000-=101或甲第一回合应从第二堆中取走(101)2=5个（3）(a,b,c)=(21,29,15)a=21b=29c=1510101111011111^00111解10101111011000^00000-=111或甲第一回合应从第三堆中取走(111)2=7个公理集合论（ZFC公理体系）：引入集论公理以避免悖论（ZF：Zermelo及Fraenkel，C：AxiomofChioce)法国数学家亨利·庞加莱对集合论的公理化曾说过：为了防止狼，筑起了栅栏，至于栅栏里面有没有狼还是未知的。狼-----悖论栅栏-----集合论公理化JulesHenriPoincaré1854-1912亨利·庞加莱(JulesHenriPoincaré)法国数学家、天体力学家、数学物理学家、科学哲学家。庞加莱的研究涉及数论、代数学、几何学、拓扑学、天体力学、数学物理、多复变函数论、科学哲学等许多领域。他被公认是19世纪后四分之一和二十世纪初的领袖数学家，是对于数学和它的应用具有全面知识的最后一个人。庞加莱在数学方面的杰出工作对20世纪和当今的数学造成极其深远的影响，他在天体力学方面的研究是牛顿之后的一座里程碑，他因为对电子理论的研究被公认为相对论的理论先驱。前几个冯·诺伊曼序数（VonNeumannordinals）0=Ø1={0}={Ø}2={0,1}={Ø,{Ø}}3={0,1,2}={Ø,{Ø},{Ø,{Ø}}}4={0,1,2,3}={Ø,{Ø},{Ø,{Ø}},{Ø,{Ø},{Ø,{Ø}}}}第一个超限序数ω={0,1,2,…}第n+1有限序数n={0,1,2,3,…,n-1}第二个超限序数ω+1=ω∪{ω}第二个超限序数ω+2=(ω+1)∪{ω+1}约翰·冯·诺伊曼(JohnvonNeumann)匈牙利裔美籍数学家。1903年12月28日生于匈牙利布达佩斯的一个犹太人家庭。20世纪最重要的数学家之一，在现代计算机、博弈论、核武器和生化武器等诸多领域内有杰出建树的最伟大的科学全才之一，被后人称为“计算机之父”和“博弈论之父”。JohnvonNeumann1903-1957Hilbert'shotelImagineahotelwithafinitenumberofrooms.Say,500rooms.Andalltheroomsaretaken.Anewguestarrivesandasksforaroom,andtheownersays,Sorry,alltheroomsaretaken.Butnowlet,simagineahotelwithaninfinitenumberofrooms,andsupposeoncemorethatalltheroomsaretaken.Anewguestasksforaroom,andtheownersays,Butofcourse!Comeonin.Theownerthenshiftsthepersoninroom#1toroom#2,thepersoninroom#2toroom#3,andsoon–intoinfinity.Hethenplacesthenewguestinroom#1.Howdidthishappen?Alltheroomswerefull,andyettheguestcheckedintoroom#1.Whatismore,weaddedanewguest,didn,tloseanyguests,andyettherearethesamenumberofguests!Theirnumberis,specifically,infinite.Itgetsstranger.Thenextday,aninfinityofnewguestsarrive,askingforrooms.Butofcourse!saystheowner,whoshiftsthepersoninroom#1intoroom#2,thepersoninroom#2toroom#4,thepersoninroom#3toroom#6,andsoon.Hemoveseachpersontotheroomthatisnumbereddoublehisoriginalroomnumber.Becausedoublesofintegersarealwayseven,everypersoninthehotelisinaneven-numberedroom.Theinfinitenumberofnewguestsnowcheckintotheodd-numberedrooms.Andyet,beforetheycame,alltheroomswereoccupied!AndyetthenumberofguestsinHilbert,sHotelisthesameasbefore:theirnumberisinfinite.Andthiscanberepeatedaninfinitenumberoftimes.Eachtime,thehotelisfullwhennewguestsarrive,an