《离散数学课件：4-4 基数的概念》由会员分享，可在线阅读，更多相关《离散数学课件：4-4 基数的概念（16页珍藏版）》请在金锄头文库上搜索。
1、四、基数的概念四、基数的概念后继集：后继集：设设A是任一给定集合是任一给定集合, AA称为称为A的后的后继集合继集合, 简称简称后继后继, 记为记为A+.(一一) 自然数集的定自然数集的定义义自然数集：自然数集：设设N为自然数集为自然数集, 它的递归定义如下它的递归定义如下:(1)(基础基础)N;(2)(归纳归纳)如果如果n N, 则则n+ N(这里这里n+=nn);(3)(闭合闭合)如果如果S N,且且S满足满足(1)、(2), 则则S=N.按照这个定义，自然数集的元素为：按照这个定义，自然数集的元素为：,+,(+)+, (+)+)+,即为：即为：,可以简化为：可以简化为： , ,自然数集的
2、定义自然数集的定义用记号用记号:=给这些集合命名：给这些集合命名：0:=0+=一般地若已给出一般地若已给出n, 则则n+1:=n+=0,1,2,n.;1:=0;2:= 1+= ,=0,1;3:= 2+= ,=0,1,2; 自自然然数数集集N=0,1,2,3,其其中中除除0外外每每一一个个自自然然数是它前一个自然数的后继。数是它前一个自然数的后继。F0不是任何自然数的后继；不是任何自然数的后继；任何自然数的后继是唯一的；任何自然数的后继是唯一的；如果如果n+=m+, 则则n=m.四、基数的概念四、基数的概念自然数集的定义自然数集的定义贝安诺贝安诺(G. Peano)公理公理(1)0 N;(2)对
3、对每每一一个个n N, 恰恰存存在在一一个个n+ N(称称n+为为n的后继的后继);(3)不存在一个不存在一个n N,使使n+=0;(4)如果如果n+=m+, 则则n=m;(5)如果如果S N, 且且(a)0 S;(b)如果如果n S,就必有就必有n+ S,则则S=N。四、基数的概念四、基数的概念问题：问题：所有整数的个数，一条线上所有几何点个所有整数的个数，一条线上所有几何点个数数(即区间即区间a,b上个数上个数)，上面两个数哪个大些，上面两个数哪个大些？Cantorl 从原始部落物品交换中得到启发。从原始部落物品交换中得到启发。F在古代原始部落中，不存在比在古代原始部落中，不存在比3大的数
4、。若问大的数。若问他们当中的一个人有几个孩子，当孩子多于他们当中的一个人有几个孩子，当孩子多于3个个时，其回答是很多。时，其回答是很多。F在比较一堆珠子和一堆铜币哪个多时，他们将在比较一堆珠子和一堆铜币哪个多时，他们将怎么完成呢？怎么完成呢？ 他他们们是是通通过过把把珠珠子子和和铜铜币币逐逐个个比比较较，最后看哪堆有多余，若同时没有则两者相同。最后看哪堆有多余，若同时没有则两者相同。(二二) 等势等势四、基数的概念四、基数的概念问题：问题：所有整数的个数，一条线上所有几何点个所有整数的个数，一条线上所有几何点个数数(即区间即区间a,b上个数上个数)，上面两个数哪个大些，上面两个数哪个大些？Ca
5、ntorl对对于于该该问问题题中中的的两两个个无无穷穷大大数数的的比比较较，我我们们也也面临类似于原始部落的困难。面临类似于原始部落的困难。FCantor的解决办法与上述原始部落的方法相同：的解决办法与上述原始部落的方法相同：给两组元素无穷多的序列中的各个数一一配对，给两组元素无穷多的序列中的各个数一一配对，若最后这两组元素恰配对完毕，则认为这两个无若最后这两组元素恰配对完毕，则认为这两个无穷大数就是相等的，若有一组还没配完，则该组穷大数就是相等的，若有一组还没配完，则该组就比另一组大。就比另一组大。F正是基于这一基本设想，我们可给出对于两个正是基于这一基本设想，我们可给出对于两个集合比较其元
6、素个数大小的方法。集合比较其元素个数大小的方法。四、基数的概念四、基数的概念 等势（同浓）：等势（同浓）：设设A, B是任意两个集合，若存是任意两个集合，若存在一个在一个双射双射f : AB, 则称则称A和和B是是等势等势的的(或或同浓同浓的的)，记为，记为AB。例例例例4.4.14.4.1验证自然数集验证自然数集N与非负偶数集合与非负偶数集合E=2n|n N是等势的。是等势的。证证： 因为因为N与与E之间可作如下双射：之间可作如下双射：f (n)=2n所以所以NE.等势的定义等势的定义四、基数的概念四、基数的概念等势的定义等势的定义例例例例4.4.2 4.4.2 设设R为实数集合，为实数集合
7、，S =x|x R 0x1, 证明：证明： RS .证证： 令令f : RS f (x) =(arctan x)/ +1/2,显然显然f是双射函数，是双射函数，故故 RS .四、基数的概念四、基数的概念定理定理1: 在集合族上等势关系是一个等价关系在集合族上等势关系是一个等价关系。证证： 设设S为一个集合族，为一个集合族，(1)自反性：自反性： AS, 可作恒等函数可作恒等函数IA : AA, IA(x)= x. 显然显然IA:A A 为一个双射函数，为一个双射函数， 故故AA. (2)对称性：对称性： A, BS, 若若AB, 即存在双射函数即存在双射函数 f :AB,故故BA. 则则f -
8、1: BA存在且也为双射存在且也为双射，(3)传递性：传递性： A, B, CS, 若若AB且且BC, 即存在双射即存在双射f :AB, g :BC, 则则g f : AC也为双射也为双射， 故故AC. 等势的性质等势的性质四、基数的概念四、基数的概念(三三) 无限集无限集 设设A为一个集合，若为一个集合，若A为空集或与集合为空集或与集合0,1,n-1存在双射存在双射, 则称则称A为为有限集有限集，否则称，否则称A为为无限集无限集。FNn=0,1,2, ,n-1称为称为N的初始段的初始段，Nn可用于证可用于证明集合为有限集，故明集合为有限集，故Nn又作为一个又作为一个“标准集合标准集合”。F若
9、若ANn, 则集合则集合A的的“大小大小” 即为即为A中所含元素中所含元素的个数的个数n.四、基数的概念四、基数的概念定理定理2: 自然数集合自然数集合N是无限集。是无限集。无限集无限集证明思路证明思路： 证明证明N不是有限集，即证明对任何不是有限集，即证明对任何n N，不存在从不存在从Nn到到N的双射。的双射。证：证： 设设n是是N中任一元素，中任一元素，f是是Nn到到N的任一函数，的任一函数，令令k=1+max f (0), f (1), , f (n-1),则则k N, 但但对任意对任意a Nn, 有有f(a) k.所以所以f不是满射，从而不是满射，从而f也不是双射。也不是双射。由由n和
10、和f 的任意性知的任意性知N是无限集。是无限集。四、基数的概念四、基数的概念无限集无限集基数基数: 所有与集合所有与集合A等势的集合所组成的集合族的共等势的集合所组成的集合族的共同特征，称为集合同特征，称为集合A的基数，记为的基数，记为KA(或或|A|, ).FCantor认为集合认为集合A的基数是两次抽象的结果，一次从的基数是两次抽象的结果，一次从A 的的元素中抽去质的特性，另一次是抽去元素之间的次序关系。元素中抽去质的特性，另一次是抽去元素之间的次序关系。故用故用 或或 |A| 中的两个杠表示二次抽象。中的两个杠表示二次抽象。F根据根据Cantor的原意，基数的定义也可描述为：的原意，基数
11、的定义也可描述为：度量集合大度量集合大小的量小的量。F有限集合的基数就是其元素的个数，约定空集的基数为有限集合的基数就是其元素的个数，约定空集的基数为0。F若若A,B为无限集且为无限集且AB, 则有则有KA = KB 。F没有一个自然数能作为没有一个自然数能作为N的基数，因此我们将记的基数，因此我们将记KN为为0 ,读作阿列夫零。读作阿列夫零。四、基数的概念四、基数的概念无限集无限集例例例例4.4.3 4.4.3 求整数集求整数集I的基数的基数K(I).证：证：即存在双射即存在双射f :NI, 使对任意使对任意n N,有有 因为因为N与与I 之间有如下一一对应之间有如下一一对应: N: 0,1
12、, 2,3, 4,5, 6, I: 0,1,-1,2,-2,3,-3,f(n)=n为偶数为偶数-n/2,n为奇数为奇数(n+1)/2,所以所以KI=0.KN四、基数的概念四、基数的概念 设设A=0, 1, 1/2, , 1/n, , A 0,1无限集无限集例例例例4.4.4 4.4.4 证明区间证明区间0,1与与(0,1)基数相等。基数相等。证：证：f(0)=n 11/2,则则f是双射函数。是双射函数。定义定义f :0,1(0,1)(如下图所示如下图所示), 使对任意使对任意n 0,1, 有有f(1/n)= 1/(n+2),f(x)= x, x 0,1-A01/6 1/51/31/41/210
13、1/6 1/51/31/41/21四、基数的概念四、基数的概念 从中取一元素记为从中取一元素记为a1, 则则A-a1 为非空无限集，为非空无限集，无限集无限集定理定理3: 任一无限集必与其某一真子集等势。任一无限集必与其某一真子集等势。证：证：则则f是双射，是双射，f(x)=a2i,x,x=aix A从而从而AB.现构造函数现构造函数f：AB, 使得使得设设A是任意的无限集，是任意的无限集， 再在再在A-a1中取一元素记为中取一元素记为a2, A-a1,a2还是非空无限集，还是非空无限集， 取元素过程一直进行下去，从取元素过程一直进行下去，从A中可取中可取出一列元素出一列元素a1, a2, 将
14、将A-a1,a2,记为记为A, 则则 A=A a1,a2,. 在在A中取真子集中取真子集B=Aa2, a4,.例如，自然数集与非负偶数集合等势。例如，自然数集与非负偶数集合等势。四、基数的概念四、基数的概念用图形描述：用图形描述： 设有线段设有线段AB, 其上有线段其上有线段CD, 则线段则线段AB与与CD上所有的点可作成一一对应。上所有的点可作成一一对应。作法是：作法是： 把把CD移出与移出与AB平行平行,联联AC-BD延长线交于延长线交于G, 则则AB上上任意点任意点E与与G的联线的联线EG必与必与CD交于交于F. 反之，反之，CD上任意点上任意点F与与G的联线的联线FG延长必交延长必交A
15、B于于E.ABCDABCDGFE上述上述E、F的对应作法，即说明的对应作法，即说明ABCD.定理定理3: 任一无限集必与其某一真子集等势。任一无限集必与其某一真子集等势。四、基数的概念四、基数的概念无限集无限集推论推论:F凡不能与自身的任一真子集等势的集合为有限凡不能与自身的任一真子集等势的集合为有限集；集；F凡能与自身的某一真子集等势的集合必为无限凡能与自身的某一真子集等势的集合必为无限集，否则为有限集。集，否则为有限集。 前面的例子和定理说明了这样的事实：前面的例子和定理说明了这样的事实： 在无穷大的世界里，部分可能等于全部。在无穷大的世界里，部分可能等于全部。那么是否无穷大数都是相等的？那么是否无穷大数都是相等的？无限集的等价定义：无限集的等价定义： A 是无限集当且仅当与其是无限集当且仅当与其某一个真子集等势某一个真子集等势四、基数的概念四、基数的概念HW: 4-4习题习题 (1)a,d,e;(2);(3);(4)
