离散数学第17讲课件.ppt

1、2022-12-92022-12-9计算机学院计算机学院1 1主要内容主要内容1.1.集合的基数集合的基数2.2.有限集、无限集有限集、无限集3.3.可数集和不可数集可数集和不可数集2022-12-92022-12-9计算机学院计算机学院2 26.4 6.4 集合的基数、可数集和不可数集合的基数、可数集和不可数集集 先看几个问题：先看几个问题：有限集同无限集的区别是什么？两个无限集有限集同无限集的区别是什么？两个无限集之间可不可以比较大小？之间可不可以比较大小？自然数集中元素的个数同有理数集中元素的自然数集中元素的个数同有理数集中元素的个数那一个多？个数那一个多？有理数集中元素的个数同无理数集

2、中元素的有理数集中元素的个数同无理数集中元素的个数那一个多？个数那一个多？无理数集中元素的个数同实数集中元素的个无理数集中元素的个数同实数集中元素的个数那一个多？数那一个多？有没有最大的集合，它包含了所有的集合？有没有最大的集合，它包含了所有的集合？2022-12-92022-12-9计算机学院计算机学院3 3集合的基数集合的基数 集合的基数就是集合中元素的个数集合的基数就是集合中元素的个数,是集合容量的度是集合容量的度量。一般是在两个集合的元素间建立一一对应关系量。一般是在两个集合的元素间建立一一对应关系,其中其中一个作为尺度。比如我们在计算一群人和一堆物品时，一个作为尺度。比如我们在计算一

3、群人和一堆物品时，就是将人和物品同数字就是将人和物品同数字1 1、2 2、3 3等一一对应起来，其本质等一一对应起来，其本质就是在两个集合的元素之间建立了一一对应关系（即双就是在两个集合的元素之间建立了一一对应关系（即双射）。射）。定义定义6.76.7 设设X X，Y Y是两个集合，若在是两个集合，若在X X，Y Y之间存在之间存在1-11-1对应的关系（在集合对应的关系（在集合X X和和Y Y之间建立之间建立双射双射），则称集合），则称集合X X与与Y Y是是对等的对等的或或等势的等势的，记为：，记为：X X Y Y 集合集合X X的基数一般记为的基数一般记为card(X),card(X),

4、如果如果A A是有限集合是有限集合,A,A的基数通常记为的基数通常记为A A（它是（它是A A中元素的个数）。中元素的个数）。2022-12-92022-12-9计算机学院计算机学院4 4定理定理6.46.4 等势是集合族上的等价关系。等势是集合族上的等价关系。即对任意的集合即对任意的集合A A、B B、C C，A A A A A A B B B B A A A A B B、B B C C A A C C 而等价关系决定等价类，因此，所有等势的而等价关系决定等价类，因此，所有等势的集合构成一个等价类。集合构成一个等价类。一般地：一般地：若若X XY Y，则，则 X X Y Y。反之不然。反之不

5、然。2022-12-92022-12-9计算机学院计算机学院5 5 记记 N Nm m=x x|x x是正整数，且是正整数，且x xmm 问题：对同一个集合问题：对同一个集合X X，是否会出现，是否会出现X X N Nm m ，同时又出现同时又出现X X N Nn n，而而mnmn？定理定理6.56.5 如果如果正整数正整数m m n n，则不存在从，则不存在从N Nn n到到N Nm m的单射。的单射。定义定义6.86.8 设设X X，Y Y是两个集合，若存在从是两个集合，若存在从X X到到Y Y的单的单射，则射，则card(X)card(X)card(Y)card(Y)；如果不存在从；如果

6、不存在从X X到到Y Y的双射，则的双射，则card(X)card(X)card(Y)card(Y)。下面，我们对集合按照基数进行分类。下面，我们对集合按照基数进行分类。2022-12-92022-12-9计算机学院计算机学院6 6自然数集合自然数集合N N的定义的定义1.1.N N，2.2.若若n n N N，则，则n n:n nnn N N。也即：也即：0:0:，1:1:=0=0，2:2:,=0,1=0,1.n:n:0,1,2,3,.n-10,1,2,3,.n-1.N N0,1,2,3,.,n,.0,1,2,3,.,n,.二十世纪初，集合成为数学的基本概念之二十世纪初，集合成为数学的基本概

7、念之后，由冯后，由冯诺依曼（诺依曼（Von NeumannVon Neumann，J.J.）用集合的）用集合的方式来定义自然数取得了成功。方式来定义自然数取得了成功。2022-12-92022-12-9计算机学院计算机学院7 7定义定义6.96.9 如果如果X X是空集是空集,或者或者 自然数自然数m m，X X N Nm m ,则称则称X X为有限集为有限集,否则称否则称X X为无限集。为无限集。定理定理6.66.6 自然数集自然数集N N是无限集。是无限集。定理定理6.76.7 非空集合非空集合X X是无限集当且仅当存在从是无限集当且仅当存在从N N到到X X的单的单射。射。将将自然数集自

8、然数集N N的基数记为的基数记为 （读为（读为“阿列夫阿列夫0 0”）。）。02022-12-92022-12-9计算机学院计算机学院8 8可数集可数集例例6.8 6.8 下列集合都是可数集合：下列集合都是可数集合：定义定义6.10 6.10 凡是与自然数集合等势的集合，统称凡是与自然数集合等势的集合，统称为为可数集合可数集合或或可列集合可列集合。1)1)O O+x|xx|x N N，x x是奇数是奇数 2)2)E E+x|xx|x N-0N-0，x x是偶数是偶数 3)3)P Px|xx|x N N，x x是素数是素数 4)4)整数集合整数集合Z Z2022-12-92022-12-9计算机

9、学院计算机学院9 9解：（解：（1 1）在在O O+与与N N之间建立之间建立1-11-1对应的关系对应的关系 f f：NONO+如如下：下：f f：NONO+f f（n)=2n+1 n)=2n+1 N N .O O+.2n+1.2n+1.所以，所以，O O+也是可数集合。也是可数集合。2022-12-92022-12-9计算机学院计算机学院1010（2 2）在在N N与与E E+之间建立之间建立1-11-1对应的关系对应的关系f f：NENE+如下：如下：f f：NENE+f f（n)=2n+2 n)=2n+2 N N .E E+10.2n+2.10.2n+2.所以，所以，E E+也是可数集

10、合。也是可数集合。2022-12-92022-12-9计算机学院计算机学院1111（3 3）在在P P与与N N之间建立之间建立1-11-1对应的关系对应的关系f f：NPNP如下：如下：N N .P P 11.11.所以，所以，P P也是可数集合。也是可数集合。枚举法枚举法2022-12-92022-12-9计算机学院计算机学院1212（4 4）在在N N与与Z Z之间建立之间建立1-11-1对应的关系对应的关系f f：NZNZ如下：如下：f f：NZNZN N .2n-1 2n .2n-1 2n .Z Z -1-1 -2.n -n .-2.n -n .所以，所以，Z Z也是可数集合。也是可

11、数集合。2n 2)1()(为偶数为奇数nnnnf2022-12-92022-12-9计算机学院计算机学院1313可数集的性质可数集的性质定理定理6.8 6.8 每个无限集必含有子集是可数集。每个无限集必含有子集是可数集。定理定理6.9 6.9 可数个可数集的并集为可数集。可数个可数集的并集为可数集。推论推论6.9.16.9.1:NN是可数集。证明：证明：令令 A Ai i=（i i，0 0），（），（i i，1 1），（），（i i，2 2），），i0i0 显然，显然，A Ai i（i0i0）是可数集）是可数集 N NN=N=A A0 0AA1 1AA2 2AA3 3 由由定理定理6.96.9

12、知，知，N NN N是可数集。是可数集。2022-12-92022-12-9计算机学院计算机学院1414定理定理6.10 6.10 有理数是可数集。有理数是可数集。证明：证明：由由推论推论6.9.16.9.1知：知：N NN N是可数集。是可数集。构造构造 S=(m,n)S=(m,n)N NN|mN|m和和n n互素且互素且mn0mn0显然，显然，S S是可数集。是可数集。令令 g:SQ g:SQ+，g(m,n)g(m,n)）=m/n=m/n，则，则g g是双射，是双射，所以，正有理数集是可数集。所以，正有理数集是可数集。同理，可证负有理数集也是可数集。同理，可证负有理数集也是可数集。再由再由

13、定理定理6.96.9知，知，Q=QQ=Q+0Q0Q-是可数集。是可数集。2022-12-92022-12-9计算机学院计算机学院1515不可数集不可数集定理定理6.116.11 实数集合实数集合R R是不可数集合。是不可数集合。证明：证明：1)1)首先证明（首先证明（0 0，1 1）是不可数集。）是不可数集。约定（约定（0 0，1 1）中的任何数都可用无限位）中的任何数都可用无限位小数表示。例如小数表示。例如0.320.32用无限位小数表示时应用无限位小数表示时应为为0.319990.31999。假设（。假设（0 0，1 1）是可数集，那么，）是可数集，那么，可在（可在（0 0，1 1）和）和

14、N N之间建立双射，即（之间建立双射，即（0 0，1 1）中的元素可依序列出为中的元素可依序列出为 。2022-12-92022-12-9计算机学院计算机学院1616设这些元素的无限位为设这些元素的无限位为现在构造实数，现在构造实数，其中其中可见可见r r与与 中的任何一个都不同。中的任何一个都不同。但是，但是，rr（0 0，1 1），这与（），这与（0 0，1 1）是可数集相）是可数集相2022-12-92022-12-9计算机学院计算机学院1717矛盾，所以（矛盾，所以（0 0，1 1）不是可数集。）不是可数集。2 2）要证明）要证明实数集合实数集合R R是不可数集合，只需证明是不可数集合

15、，只需证明R R与（与（0 0，1 1）等势就行了。）等势就行了。建立映射建立映射f f：RR（0 0，1 1）f(y)=(arctan y)/f(y)=(arctan y)/+1/2 +1/2 y y R R(当当x x(-(-/2,/2,/2),y=tan x/2),y=tan x R Rx=x=arctan y arctan y (-(-/2,/2,/2),/2),那么那么 x/x/+1/2+1/2(0(0,1),1),即即 f(y)=(arctan y)/f(y)=(arctan y)/+1/2+1/2 (0(0,1),1)显然，函数显然，函数f f是一个双射，所以是一个双射，所以R

16、R（0 0，1 1）2022-12-92022-12-9计算机学院计算机学院1818 本定理中使用的证明方法，是一本定理中使用的证明方法，是一种著名的对角化方法。种著名的对角化方法。开区间开区间(0,1)(0,1)称为称为不可数集合不可数集合，其，其基数基数设为设为 (读作阿列夫读作阿列夫)；凡是与区间凡是与区间(0,1)(0,1)等势的集合都是不可等势的集合都是不可数集合。数集合。2022-12-92022-12-9计算机学院计算机学院1919Cantor定理定理 设设M M是任意集合是任意集合,S,S是是M M的幂集的幂集,那么那么,card(M)card(S)(card(M)card(S

17、)(M M (M)(M)证明：证明：1 1）当）当M=M=时，时，S=S=，则，则card(M)=0,card(M)=0,card(S)=1,card(S)=1,结论成立。结论成立。2 2）当）当M M 时，构造时，构造f:Mf:MS,S,对对 a a M M有有f(a)=a,f(a)=a,则则f(M)f(M)S,S,card(M)card(M)card(S)card(S)下面证明等号不成立（下面证明等号不成立（反证法反证法）2022-12-92022-12-9计算机学院计算机学院2020设设 :M:MS S（是双射是双射），），构造构造 B=x B=x M|xM|x(x),(x),则则B B

18、 S S。是双射，是双射，c c M M (c)=B(c)=B。如果如果c c B B，由，由B B的定义，的定义，c c B B，矛盾，矛盾如果如果c c B B，由，由B B的定义，的定义，c c B B，矛盾，矛盾 不可能是双射不可能是双射故故 card(M)card(M)card(S)card(S)对对 a a M M，如果，如果a a(x)(x)时称时称a a为为关于关于 的内部元的内部元素，否则称为外素，否则称为外部元素部元素2022-12-92022-12-9计算机学院计算机学院2121 此定理表明：此定理表明：没有最大基数的集合，也就没有最大没有最大基数的集合，也就没有最大的集合，因此就不存在无所不包的集合。的集合，因此就不存在无所不包的集合。0A2022-12-92022-12-9计算机学院计算机学院2222习题六习题六18、20、21、22