《集合的势》ppt课件

集合的等势与优势,离散数学：第8讲,上一讲内容的回顾,函数的定义 像与完全原像 几种特殊的函数 满射、单射(一对一的)、双射(一一对应的) 集合的特征函数 自然映射 函数的复合 反函数 鸽巢原理,集合的等势与优势,集合的等势关系 与自然数集合等势的集合-可列集 有穷与无穷 等势关系是等价关系 康托尔定理 优势关系 优势关系的性质,我们怎么比较集合的大小,“数得清”的我们就数元素个数 “无数”的怎么办？ “常识”不一定经得起追问集合的等势关系,等势关系的定义： 如果存在从集合A到集合B的双射，则称集合A与B等势 集合A与B等势记为：AB, 否则A≉B AB意味着：A，B中的元素可以“一一对应” 要证明AB，找出任意一个从A到B的双射即可 “等势”的集合就被认为是“一样大”,等势关系是等价关系,自反性：ƒ:AA, ƒ(x)=x 对称性：如果ƒ:AB是双射，则存在ƒ的反函数ƒ-1:BA，也是双射 传递性：如果ƒ:AB，g:BC均是双射，则ƒ°g是从A到C的双射 例子：所有与自然数集等势的集合构成一个等价类可列集(无穷可数集),与自然数集等势的集合称为可列集 直观上说：集合的元素可以按确定的顺序线性排列，所谓“确定的”顺序是指对序列中任一元素，可以说出：它“前”、“后”元素是什么。

整数集(包括负数)与自然数集等势 0, -1, 1, -2, 2, -3, 3, -4, ,,自然数集的笛卡儿积是可列集,所有的整数对构成的集合与自然数集等势,, , , , , , , ,类似的图形显示：可列个可列集的并集仍然是可列集合,有穷与无穷：差别不仅是数量,伽利略悖论： 传统公理：“整体大于部分” 伽利略发现：{1,2,3,…}与{12,22,32,…}一一对应有限集与无限集,S是有限集合，iff. 存在自然数n，使得S与{1,2,…n}等势 S不是有限集合(即：无限集)，iff. 存在S的真子集S’，使得S与S’等势  S一定包含一个与自然数集合等势的子集M = {a1,a2,a3,…} (这实际上意味着：自然数集是“最小的”无限集) 令S’=S-{a1}，可以定义ƒ:SS’如下： 对于任意xM, ƒ(ai)= ai+1； 对于任意xS-M, ƒ(x)= x 显然这是双射，即S与其真子集S’等势  假设S是有限集，令|S|=n, 则给S任意的真子集S’, 若|S’|=m，必有mn, 因此从S ’到S的任一单射不可能是满射宇宙旅馆”,啊？客满啦？ 没关系，我让现在住在 k 号房间的客人移到 k+1号。

你就住进第1号房间吧！,客 满,证明无限集等势的例子,(0,1)与整个实数集等势 双射：f : (0,1)R : f (x) =tg(x- ) 对任意不相等的实数a,b(ab), [0,1]与[a,b]等势 双射： f : [0,1][a,b]: f (x) =(b-a)x+a (这实际上意味着：任意长的线段与任意短的线段等势),实数集不是可列集,注意：(0,1)与实数集合等势 (0,1)不是可列集 “对角线证明法” 假设(0,1)中的元素可以线性排列： 0.b11b12b13b14… 0.b21b22b23b24… 0.b31b32b33b34… 0.b41b42b43b44… ⋮ 则0. b1b2b3b4…（bi≠bii）不含在上述序列中,直线上的点集与平面上的点集等势,,,,0.a1b1a2b2a3b3.,,0.a1a2a3. 0.b1b2b3,,,,这实际上意味着直线上的点与任意有限维空间的点“一样多”！,康托尔定理,任何集合与其幂集不等势 即：A≉(A) 证明要点： 设g是从A到(A)的函数，构造集合B如下： B={x| xA, 但xg(x)} 则B(A)，但不可能存在xA，能满足g(x)=B，因为，如果有这样的x, 则xB iff. xB。

因此，g不可能是满射 康托尔悖论：不存在“一切集合的集合”集合的“大小”,,,有限,我们能感觉到的世界,,可列,N0,,N1,点,,N2,曲线,我们能想象到的世界,？,还有什么,,,“家家有本难念的经”,康托尔，他有许多许多的数，但才用了3个, 就没有东西可以数了大脚，他有许多许多的儿子，但他最多只能数到3数学史上的“三次危机”,第一次危机 芝诺悖论(关于运动的四个悖论，如“飞箭不动”)，导致数学真正严谨性的开始(公理化) 第二次危机 微积分悖论(无穷小量等于零吗？“那逝去的量的鬼魂”)，导致极限论的诞生 第三次危机 有关一切集合的集合的悖论，导致集合论公理化集合的优势关系,如果存在从集合A到集合B的单射，则称“集合B优势于集合A” 集合B优势于集合A 记为 A≼•B 如果集合B优势于集合A，且B与A不等势，则称“集合B真优势于集合A”，记为A≺•B 实数集合真优势于自然数集 例子：对任意集合A，A的幂集真优势于集合A,集合优势关系的性质,自反性：恒等函数 若A≼•B，且B≼•A，则AB (Cantor-Bernstein定理) 传递性：单射的复合仍然是单射 因此，集合优势关系是偏序关系 其实，优势关系是全序,优势关系的反对称性用于证明等势,有时候找双射不太容易 证明实数集的两个子集(0,1)和[0,1]。

关键是如何安排在[0,1]中但不在(0,1)中的0和1 想象那个“宇宙旅馆”我们可以取(0,1)的一个与自然数集合等势的子集(一定有){a1,a2 ,a3 ,.}, “腾出”前两个位置安排0和1,,,优势关系的反对称性用于证明等势 (续),证明实数集的两个子集(0,1)和[0,1] 分别找两个一对一的映射往往比找一个双射容易,习题,p.178 2 5 6 11,康托尔(Georg Cantor 1845-1918),“无限！再没有其它问题如此深刻地打动过人类的心灵 - 戴维希尔伯特 “由康托尔在1874-1895年创造地集合论的引起争论的题目，象征着19世纪有先见之明的预言家们认为是从物理科学到民主政府的一切事物中，极其合理的原则的总崩溃，这些预言家们预见到了一切，只是没有预见到这场大崩溃 “悖论和自相矛盾开始同时出现，这些可能最终是康托尔的理论注定要对数学做出的最大贡献，因为它们就在围绕无穷的逻辑和数学推理的基础中意想不到地存在，是现在整个演绎推论中批判运动地直接启迪我们希望从这里能得出一个…更丰富、更“真实”—摆脱了不一致—的数学 上述两段摘自 E.T.贝尔：《数学精英》,。