08-集合的势(精品).ppt

《08-集合的势(精品).ppt》由会员分享，可在线阅读，更多相关《08-集合的势(精品).ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合的等势与优势集合的等势与优势 离散数学：第8讲上一讲上一讲内容的回顾内容的回顾l函数的定义l像与完全原像l几种特殊的函数满射、单射(一对一的)、双射(一一对应的)l集合的特征函数l自然映射l函数的复合l反函数l鸽巢原理集合的等势与优势集合的等势与优势l集合的等势关系l与自然数集合等势的集合-可列集l有穷与无穷l等势关系是等价关系l康托尔定理l优势关系l优势关系的性质我们怎么比较集合的大小我们怎么比较集合的大小l“数得清”的我们就数元素个数。l“无数”的怎么办？“常识”不一定经得起追问。集合的等势关系集合的等势关系l等势关系的定义：如果存在从集合A到集合B的双射双射，则称集合A与B等等势势。

2、集合A与B等势记为：AB,否则ABAB意味着：A，B中的元素可以“一一对应一一对应”。要证明AB，找出任意一个从A到B的双射即可。l“等势”的集合就被认为是“一样大”等势等势关系是等价关系关系是等价关系l自反性：:AA,(x)=xl对称性：如果:AB是双射，则存在的反函数-1:BA，也是双射。l传递性：如果:AB，g:BC均是双射，则g是从A到C的双射。l例子：所有与自然数集等势的集合构成一个等价类。可列可列集集(无穷可数集无穷可数集)l与自然数集等势的集合称为可列集直观上说：集合的元素可以按确定的顺序线性排列，所谓“确定的”顺序是指对序列中任一元素，可以说出：它“前”、“后”元素是什么。l整

3、数集(包括负数)与自然数集等势0,-1,1,-2,2,-3,3,-4,.自然数集的笛卡儿积是可列集自然数集的笛卡儿积是可列集l所有的整数对构成的集合与自然数集等势 .,.类似的图形显示：可列个可列集的并集仍然是可列集合有穷与有穷与无穷：差别不仅是数量无穷：差别不仅是数量l伽利略悖论：传统公理：“整体大于部分”伽利略发现：1,2,3,与12,22,32,一一对应。有限集与无限集有限集与无限集lS是有限集合，iff.存在自然数n，使得S与1,2,n等势lS不是有限集合(即：无限集)，iff.存在S的真子集S，使得S与S等势 S一定包含一个与自然数集合等势的子集M=a1,a2,a3,(这实际上意味着

4、：自然数集是“最小的”无限集)令S=S-a1，可以定义:SS如下：对于任意xM,(ai)=ai+1；对于任意xS-M,(x)=x 显然这是双射，即S与其真子集S等势 假设S是有限集，令|S|=n,则给S任意的真子集S,若|S|=m，必有mn,因此从S 到S的任一单射不可能是满射。“宇宙旅馆宇宙旅馆”啊？客满啦？没关系，我让现在住在 k 号房间的客人移到 k+1号。你就住进第1号房间吧！客 满证明无限集等势的例子证明无限集等势的例子l(0,1)与整个实数集等势双射：f:(0,1)R:f(x)=tg(x-)l对任意不相等的实数a,b(ab),0,1与a,b等势双射：f:0,1a,b:f(x)=(b

5、-a)x+a(这实际上意味着：任意长的线段与任意短的线段等势)实数集不是可列集实数集不是可列集l注意：(0,1)与实数集合等势l(0,1)不是可列集“对角线证明法”假设(0,1)中的元素可以线性排列：0.b11b12b13b140.b21b22b23b240.b31b32b33b340.b41b42b43b44则0.b1b2b3b4（bibii）不含在上述序列中直线上的点集与平面上的点集等势直线上的点集与平面上的点集等势0.a1b1a2b2a3b3.0.a1a2a3.0.b1b2b3.这实际上意味着直线上的点与这实际上意味着直线上的点与任意有限维空间的点任意有限维空间的点“一样多一样多”！康托

6、尔康托尔定理定理l任何集合与其幂集不等势即：A(A)证明要点：设g是从A到(A)的函数，构造集合B如下：B=x|xA,但xg(x)则B(A)，但不可能存在xA，能满足g(x)=B，因为，如果有这样的x,则xB iff.xB。因此，g不可能是满射。l康托尔悖论：不存在“一切集合的集合”。集合的集合的“大小大小”有限我们能感觉到的世界可列N0N1点N2曲线我们能想象到的世界？还有什么“家家有本难念的经家家有本难念的经”康托尔，他有许多许多的数，但才用了3个,就没有东西可以数了。大脚，他有许多许多的儿子，但他最多只能数到3。数学史上的数学史上的“三次危机三次危机”l第一次危机芝诺悖论(关于运动的四个

7、悖论，如“飞箭不动”)，导致数学真正严谨性的开始(公理化)l第二次危机微积分悖论(无穷小量等于零吗？“那逝去的量的鬼魂”)，导致极限论的诞生l第三次危机有关一切集合的集合的悖论，导致集合论公理化。集合的优势关系集合的优势关系l如果存在从集合A到集合B的单射单射，则称“集合B优势于优势于集合A”l集合B优势于集合A 记为 ABl如果集合B优势于集合A，且B与A不等势不等势，则称“集合B真优势于真优势于集合A”，记为ABl实数集合真优势于自然数集l例子：对任意集合A，A的幂集真优势于真优势于集合A集合优势关系的性质集合优势关系的性质l自反性：恒等函数l若AB，且BA，则AB(Cantor-Bern

8、stein定理)l传递性：单射的复合仍然是单射l因此，集合优势关系是偏序关系其实，优势关系是全序优势关系的反对称性用于证明等势优势关系的反对称性用于证明等势l有时候找双射不太容易证明实数集的两个子集(0,1)和0,1。关键是如何安排在0,1中但不在(0,1)中的0和1。想象那个“宇宙旅馆”。我们可以取(0,1)的一个与自然数集合等势的子集(一定有)a1,a2,a3,.,“腾出”前两个位置安排0和1优势关系的反对称性用于证明等势优势关系的反对称性用于证明等势(续续)l证明实数集的两个子集(0,1)和0,1。l分别找两个一对一的映射往往比找一个双射容易习题习题lp.17825611康托康托尔尔(G

9、eorg Cantor 1845-1918)l“无限！再没有其它问题如此深刻地打动过人类的心灵。”-戴维。希尔伯特l“由康托尔在1874-1895年创造地集合论的引起争论的题目，象征着19世纪有先见之明的预言家们认为是从物理科学到民主政府的一切事物中，极其合理的原则的总崩溃，这些预言家们预见到了一切，只是没有预见到这场大崩溃。”l“悖论和自相矛盾开始同时出现，这些可能最终是康托尔的理论注定要对数学做出的最大贡献，因为它们就在围绕无穷的逻辑和数学推理的基础中意想不到地存在，是现在整个演绎推论中批判运动地直接启迪。我们希望从这里能得出一个更丰富、更“真实”摆脱了不一致的数学。上述两段摘自 E.T.贝尔：数学精英