-集合的势.pptVIP

集合的等势与优势 离散数学：第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的任一单射不可能是满射。 “宇宙旅馆” 证明无限集等势的例子 (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）不含在上述序列中 直线上的点集与平面上的点集等势 康托尔定理 任何集合与其幂集不等势 即：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不可能是满射。 康托尔悖论：不存在“一切集合的集合”。 集合的“大小” “家家有本难念的经” 数学史上的“三次危机” 第一次危机 芝诺悖论(关于运动的四个悖论，如“飞箭不动”)，导致数学真正严谨性的开始(公理化) 第二次危机 微积分悖论(无穷小量等于零吗？“那逝去的量的鬼魂”)，导致极限论的诞生 第三次危机 有关一切集合的集合的悖论，导致集合论公理化。 集合的优势关系 如果存在从集合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]。 优势关系的反对称性用于证明等势 (续) 证明实数集的