08-集合的势.ppt

《08-集合的势.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、证明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,

3、-4,......自然数集的笛卡儿积是可列集所有的整数对构成的集合与自然数集等势<0,0><1,0><2,0><3,0><4,0><0,1><1,1><2,1><3,1><0,2><1,2><2,2><0,3><1,3><0,4>............<0,0>,<0,1>,<1,0>,<0,2>,<1,1>,<2,0>,<0,3>,......类似的图形显示：可列个可列集的并集仍然是可列集合有穷与无穷：差别不仅是数量伽利略悖论：传统公理：“整体大于部分”伽利略发现：{1,2,3,…}与{12,22,32,…}一一对应。有限集与无限集S是有限集合，

4、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是有限集，令

5、S

6、=n,则给S任意的真子集S’,若

7、S’

8、=m，必有m

9、在k号房间的客人移到k+1号。你就住进第1号房间吧！客满证明无限集等势的例子(0,1)与整个实数集等势双射：f:(0,1)R:f(x)=tg(x-)对任意不相等的实数a,b(a

10、44…⋮则0.b1b2b3b4…（bi≠bii）不含在上述序列中直线上的点集与平面上的点集等势0.a1b1a2b2a3b3.....0.a1a2a3.......0.b1b2b3......这实际上意味着直线上的点与任意有限维空间的点“一样多”！康托尔定理任何集合与其幂集不等势即：A≉(A)证明要点：设g是从A到(A)的函数，构造集合B如下：B={x

11、xA,但xg(x)}则B(A)，但不可能存在xA，能满足g(x)=B，因为，如果有这样的x,则xBiff.xB。因此，g不可能是满射。康托尔悖论：不存在“一切集合的集合”。集合的“大小

12、”有限我们能感觉到的世界可列N0N1点N2曲线我们能想象到的世界？还有什么“家家有本难念的经”康托尔，他有许多许多的数，但才用了3个,就没有东西可以数了。大脚，他有许多许多的儿子，但他最多只能数到3。数学史上的“三次危机”第一次危机芝诺悖论(关于运动的四个悖论，如“飞箭不动”)，导致数学真正严谨性的开始(公理化)第二次危机微积分悖论(无穷小量等于零吗？“那逝去的量的鬼魂”)，导致极限论的诞生第三次危机有关一切集合的集合的悖论，导致集合论公理化。集合的优势关系如果存在从集合A到集合B的单射，则称“集合B优势于集合A”集合B优势于集合A记为A≼•B如果集

13、合B优势于集合A，且B与A不等势，则称“集合B真优势于集合A”，记为A≺•B实数集合真优势于自然数集例子：对