《离散数学课件章集合的基数ppt.pptx》由会员分享，可在线阅读，更多相关《离散数学课件章集合的基数ppt.pptx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学课件章集合的基数离散数学课件章集合的基数9 9、1 1 集合得等势与优势集合得等势与优势9 9、2 2 集合得基数集合得基数 本章小结本章小结 习题习题 作业作业本章内容本章内容本章内容本章内容定义定义9 9、1 1 设设A,BA,B就是集合就是集合,如果存在着从如果存在着从A A到到B B得双射函数得双射函数,就称就称A A与与B B就是等势就是等势(samecardinality)得得,记作记作ABAB。如果如果A A不与不与B B等势等势,则记作则记作A BA B。9 9、1 1 集合得等势与优势集合得等势与优势集合得等势与优势集合得等势与优势q通俗得说通俗得说,集合得势就是量度
2、集合所含元素多少得量。集合得势就是量度集合所含元素多少得量。q集合得势越大集合得势越大,所含得元素越多。所含得元素越多。(1)ZN。则则f就是就是Z到到N得双射函数。得双射函数。从而证明了从而证明了ZN。等势集合得实例等势集合得实例等势集合得实例等势集合得实例(1)(1)(1)(1)等势集合得实例等势集合得实例(2)(2)(2)NNN。双射函数双射函数等势集合得实例等势集合得实例(3)(3)(3)(3)NQNQ。把所有形式为把所有形式为p p/q q(p p,q q为整数且为整数且q q0)0)得数排成一张表。得数排成一张表。-2/1-2/155-1/1-1/144-3/1-3/118182/
3、12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414以以0/10/1作为第一个数作为第一个数,按照箭头规定得顺序可以按照箭头规定得顺序可以“数遍数遍”表中所表中所有得数。计数过程中必须跳过第二次以及以后各次所遇到得同有得数。
4、计数过程中必须跳过第二次以及以后各次所遇到得同一个有理数。一个有理数。等势集合得实例等势集合得实例(4)(4)(4)(0,1)R。其中实数区间其中实数区间(0,1)=x|xR0 x1。令双射函数令双射函数则则f 就是就是(0,1)到到R得双射函数。从而证明了得双射函数。从而证明了(0,1)R。等势集合得实例等势集合得实例(5)(5)(5)(5)0,1(0,1)。其中其中(0,1)与与0,1分别为实数开区间与闭区间。分别为实数开区间与闭区间。双射函数双射函数f:0,1(0,1)，2 2等势集合得实例等势集合得实例(6)(6)(6)(6)对任何对任何a,bR,ab,0,1a,b。双射函数双射函数f
5、:0,1a,b,f(x)(b a)x+a。例例9 9、2 2设设A为任意集合为任意集合,则则P(A)0,1A。构造构造f:P(A)0,1A,f(A)=A ,A P(A)。其中其中 A 就是集合就是集合A 得特征函数得特征函数。(1)(1)易证易证f 就是单射得就是单射得。(2)(2)对于任意得对于任意得g0,1A,那么有那么有g:A0,1。令令 B=x|xAg(x)=1则则B A,且且 B=g,即即 BP(A),使得使得f(B)=g。所以所以f 就是满射得。就是满射得。由等势定义得由等势定义得P(A)0,1A。例例例例9 9 9 9、2 2 2 2证明证明复习复习定理定理9 9、1 1 设设A
6、,B,C就是任意集合就是任意集合,(1)AA。(2)若若AB,则则BA。(3)若若AB,BC,则则AC。(1)(1)IA就是从就是从A到到A得双射得双射,因此因此AA。(2)假设假设AB,存在存在f:AB就是双射就是双射,那么那么f 1:BA就是从就是从B到到A得双射得双射,所以所以BA。(3)假设假设AB,BC,存在存在 f:AB,g:BC就是双射就是双射,则则f g:AC就是从就是从A 到到C 得双射得双射。所以所以AC。等势得性质等势得性质等势得性质等势得性质证明证明大家学习辛苦了，还是要坚持继续保持安静继续保持安静继续保持安静继续保持安静q N Z Q NNq R 0,1(0,1)q任
7、何得实数区间任何得实数区间(开区间、闭区间以及半开半闭得区间开区间、闭区间以及半开半闭得区间)都都与实数集合与实数集合R R等势。等势。q问题问题:N N与与R R就是否等势？就是否等势？若干等势集合若干等势集合若干等势集合若干等势集合(1)如果能证明如果能证明N0,1,就可以断定就可以断定NR。只需证明任何函数只需证明任何函数f:N0,1都不就是满射得。都不就是满射得。构造一个构造一个0,1区间得小数区间得小数b,使得使得b在在N中不存在原像。中不存在原像。(2)任取函数任取函数f:AP(A),构造构造BP(A),使得使得B在在A中不存在原像。中不存在原像。或者使用反证法。或者使用反证法。定
8、理定理9 9、2 2康托定理康托定理(1)N R。(2)对任意集合对任意集合A都有都有A P(A)。康托定理康托定理康托定理康托定理分析分析(1)(1)首先规定首先规定0,1中数得表示。中数得表示。对任意得对任意得x0,1,令令x=0、x1x2,(0 xi 9)注意注意:为了保证表示式得唯一性为了保证表示式得唯一性,如果遇到如果遇到0 0、2499924999,则将则将x x表示表示为为0 0、2500025000。设设 f:N0,1就是从就是从N到到0,1得任何一个函数。得任何一个函数。f得所有函数值得所有函数值为为:f(0)=0、a1(1)a2(1)f(1)=0、a1(2)a2(2)f(n
9、 1)=0、a1(n)a2(n)令令y得表示式为得表示式为0、b1b2,并且满足并且满足bi ai(i),i=1,2,则则y0,1,但但y与上面列出得任何一个函数值都不相等与上面列出得任何一个函数值都不相等。即即f不就是满射得。不就是满射得。所以所以,N R。康托定理康托定理康托定理康托定理康托定理康托定理q假设假设A AP(A),则必有函数则必有函数f:AP(A)就是双射函数。就是双射函数。如下构造集合如下构造集合B:Bx|xAx f(x)可知可知BP(A)。于就是存在唯一一个元素于就是存在唯一一个元素bA,使得使得f(b)B。若若bB,则由则由B得定义知得定义知,b f(b),即即b B,
10、矛盾矛盾。若若b B,则则b f(b),于就是由于就是由B得定义知得定义知,bB,矛盾。矛盾。(2)(2)设设g:AP(A)就是从就是从A到到P(A)得任意函数得任意函数,如下构造集合如下构造集合B:Bx|xAx g(x)则则BP(A)。但就是但就是对任意对任意xA,都有都有xB x g(x)所以所以,对任意得对任意得xA都有都有Bg(x),即即B ran ran g 即即P(A)中存在元素中存在元素B,在在A中找不到原像。中找不到原像。所以所以,g不就是满射得。不就是满射得。所以所以,A P(A)。说说明明康托定理康托定理康托定理康托定理q根据这个定理可以知道根据这个定理可以知道N P(N)
11、。q综合前面的结果，可知综合前面的结果，可知N 0,1N。q实际上，实际上，P(N)P(N)，0,10,1N N和和R R都是比都是比N N“更大更大”的集合。的集合。定义定义9 9、2 2(1)(1)设设A,B就是集合就是集合,如果存在从如果存在从A到到B得单射函数得单射函数,就称就称B优势优势于于A,记作记作AB。如果如果B不就是优势于不就是优势于A,则记作则记作AB。(2)(2)设设A,B就是集合就是集合,若若AB且且A B,则称则称B真优势于真优势于A,记作记作AB。如果如果B不就是真优势于不就是真优势于A,则记作则记作AB。例如例如:N NN RA P(A)N RA P(A)R NN
12、 N优势优势优势优势RN定理定理9 9、3 3 设设A,B,C就是任意得集合就是任意得集合,则则(1)A A。(2)若若A B且且B A,则则AB。(3)若若A B且且B C,则则A C。证明证明:(1)(1)IA就是就是A到到A得单射得单射,因此因此A A。(2)(2)证明略。证明略。(3)(3)假设假设A B且且B C,那么存在单射那么存在单射 f:AB,:AB,g:BC,:BC,于就是于就是 f g:AC也就是单射得也就是单射得,因此因此A C。优势得性质优势得性质优势得性质优势得性质说说明明q该定理为证明集合之间得等势提供了有力得工具该定理为证明集合之间得等势提供了有力得工具。q构造两
13、个单射构造两个单射f:A:AB B 与与 g:Bg:BA A函数容易集合等势函数容易集合等势。例题例题例题例题:证明证明0,10,1与与(0,1)(0,1)等势。等势。证明证明:构造两个单射函数构造两个单射函数f:(0,1)0,1,:(0,1)0,1,f(x)xg:0,1(0,1),:0,1(0,1),g(x)x/2+1/4/2+1/4证明证明 0,1N0,1)(1)设设x 0,1),0、x1x2就是就是x得二进制表示。得二进制表示。为了使表示唯一为了使表示唯一,规定表示式中不允许出现连续无数个规定表示式中不允许出现连续无数个1。例如例如x0、1010111,应按规定记为应按规定记为0、101
14、1000。对于对于x,如下定义如下定义f:0,1)0,1N,使得使得f(x)=tx,且且tx:N0,1,tx(n)=xn+1,n=0,1,2,例如例如x=0、10110100,则对应于则对应于x得函数得函数tx就是就是:n 01234567tx(n)10110100易见易见tx0,1N,且对于且对于x,y0,1),xy,必有必有tx ty,即即f(x)f(y)。所以所以,f:0,1)0,1N就是单射得。就是单射得。(2)定义函数定义函数g:0,1N0,1)。g得映射法则恰好与得映射法则恰好与f 相反相反,即即 t0,1N,t:N0,1,g(t)=0、x1x2,其中其中xn+1=t(n)。但不同
15、得就是但不同得就是,将将0、x1x2看作数看作数x得十进制表示。得十进制表示。例如例如t1,t20,1N,且且g(t1)0、0111,g(t2)0、1000,若将若将g(t1)与与g(t2)都看成二进制表示都看成二进制表示,则则g(t1)g(t2);但若看成十进制表示但若看成十进制表示,则则g(t1)g(t2)。所以所以,g:0,1N0,1)就是单射得。就是单射得。根据定理根据定理9、3,有有0,1N0,1)。证明证明证明证明 0,10,1N N0,1)0,1)总结总结qN Z Q NNqR a,b(c,d)0,1N P(N)其中其中a,b,(c,d)代表任意得实数闭区间与开区间代表任意得实数
16、闭区间与开区间。q0,1A P(A)qN RqA P(A)9 9、2 2 集合得基数集合得基数 q上一节我们只就是抽象地讨论了集合得等势与优势。上一节我们只就是抽象地讨论了集合得等势与优势。q本节将进一步研究度量集合得势得方法。本节将进一步研究度量集合得势得方法。q最简单得集合就是有穷集。尽管前面已经多次用到最简单得集合就是有穷集。尽管前面已经多次用到“有穷集有穷集”这一概念这一概念,当时只就是直观地理解成含有有限多个元素得当时只就是直观地理解成含有有限多个元素得集合集合,但一直没有精确地给出有穷集得定义。为解决这个问但一直没有精确地给出有穷集得定义。为解决这个问题我们需要先定义自然数与自然数
17、集合。题我们需要先定义自然数与自然数集合。定义定义9 9、3 3 设设a为为集合集合,称称aa 为为a得后继得后继,记作记作a+,即即a+=aa。例例9 9、3 3 考虑空集得一系列后继。考虑空集得一系列后继。+=+=+=,=,+=,+=,=,=,+,+后继后继后继后继 说说明明q前边得集合都就是后边集合得元素。前边得集合都就是后边集合得元素。q前边得集合都就是后边集合得子集。前边得集合都就是后边集合得子集。利用后继得性质利用后继得性质,可以考虑以构造性得方法用集合来给出自可以考虑以构造性得方法用集合来给出自然数得定义然数得定义,即即0=1=0+02=1+,0,132+,+,0,1,2n0,1
18、,n 1说说明明自然数得定义自然数得定义自然数得定义自然数得定义 这种定义没有概括出自然数得共同特征。这种定义没有概括出自然数得共同特征。定义定义9 9、4 4 设设A为为集合集合,如果满足下面得两个条件如果满足下面得两个条件:(1)A(2)a(aAa+A)称称A就是归纳集。就是归纳集。例如例如:下面得集合下面得集合,+,+,+,+,+,+,a,a+,a+,a+,都就是归纳集。都就是归纳集。归纳集归纳集归纳集归纳集 定义定义9 9、5 5 自然数自然数(1)(1)一个自然数一个自然数n就是属于每一个归纳集得集合。就是属于每一个归纳集得集合。(2)(2)自然数集自然数集N就是所有归纳集得交集。就
19、是所有归纳集得交集。说明说明:根据定义根据定义9、5得到得自然数集得到得自然数集N 恰好由恰好由,+,+,+,等集合构成。而这些集合正就是构造性方法所定义等集合构成。而这些集合正就是构造性方法所定义得全体自然数。得全体自然数。例如例如:自然数都就是集合自然数都就是集合,集合得运算对自然数都适用。集合得运算对自然数都适用。250,10,1,2,3,40,1,2,3,45340,1,20,1,2,30,1,234-20,1,2,3-0,1=2,3 230,10,1,2,自然数自然数自然数自然数n n n n与自然数集合与自然数集合与自然数集合与自然数集合N N N N得定义得定义得定义得定义 P(
20、1)P(0),00,1230,10,1,2f|f:0,1,20,1f0,f1,f7其中其中f0,f1,f2,f3,f4,f5,f6,f7,举例举例举例举例 (1)对任何自然数对任何自然数n,有有n n。(2)对任何自然数对任何自然数n,m,若若m n,则则m n。(3)对任何自然数对任何自然数n,m,若若mn,则则m n。(4)对任何自然数对任何自然数n与与m,以下三个式子以下三个式子:mn,m n,nm必成立其一且仅成立其一。必成立其一且仅成立其一。(5)自然数得相等与大小顺序自然数得相等与大小顺序对任何自然数对任何自然数m与与n,有有m=n m n m n mn自然数得性质自然数得性质自然
21、数得性质自然数得性质 定义定义9 9、6 6 有穷集、无穷集有穷集、无穷集(1)(1)一个集合就是有穷得当且仅当她与某个自然数等势一个集合就是有穷得当且仅当她与某个自然数等势;(2)(2)如果一个集合不就是有穷得如果一个集合不就是有穷得,就称作无穷集。就称作无穷集。例如例如:qa,b,c就是有穷集就是有穷集,因为因为30,1,2,且且a,b,c0,1,23qN与与R都就是无穷集都就是无穷集,因为没有自然数与因为没有自然数与N与与R等势。等势。q任何有穷集只与唯一得自然数等势。任何有穷集只与唯一得自然数等势。说说明明有穷集与无穷集有穷集与无穷集有穷集与无穷集有穷集与无穷集 定义定义9 9、7 7
22、(1)(1)对于有穷集合对于有穷集合A,称与称与A等势得那个唯一得自然数为等势得那个唯一得自然数为A得基数得基数,记作记作cardA,即即cardAn A n(对于有穷集对于有穷集A,cardA也可以记作也可以记作|A|)(2)(2)自然数集合自然数集合N得基数记作得基数记作0,即即cardN=0(3)(3)实数集实数集R得基数记作得基数记作(读作阿列夫读作阿列夫),),即即cardR=基数基数基数基数(cardinalitycardinality)定义定义9 9、8 8 设设A,B为集合为集合,则则(1)cardAcardB AB(2)cardAcardB A B(3)cardA cardB
23、 cardAcardBcardAcardB例如例如:qcardZ cardQ cardNN 0qcardP(N)card2N carda,bcard(c,d)q0说明说明:集合得基数就就是集合得势集合得基数就就是集合得势,基数越大基数越大,势就越大。势就越大。基数得相等与大小基数得相等与大小基数得相等与大小基数得相等与大小 关于基数得说明关于基数得说明关于基数得说明关于基数得说明 q由于对任何集合由于对任何集合A都满足都满足A P(A),所以有所以有cardA cardP(A),这说明不存在最大得基数。这说明不存在最大得基数。q将已知得基数按从小到大得顺序排列就得到将已知得基数按从小到大得顺序
24、排列就得到:0,1,2,n,0,q0,1,2,n,就是全体自然数就是全体自然数,就是有穷基数。就是有穷基数。q0,就是无穷基数。就是无穷基数。q0就是最小得无穷基数就是最小得无穷基数,后面还有更大得基数后面还有更大得基数,如如cardP(R)等。等。可数集可数集定义定义9 9、9 9 设设A为集合为集合,若若cardA0,则称则称A为可数集为可数集(enumerable)或可列集。或可列集。例如例如:qa,b,c、5、整数集整数集Z、有理数集有理数集Q、NN等都就是可数集。等都就是可数集。q实数集实数集R不就是可数集不就是可数集,与与R等势得集合也不就是可数集。等势得集合也不就是可数集。对于任
25、何得可数集对于任何得可数集,都可以找到一个都可以找到一个“数遍数遍”集合中全体集合中全体元素得顺序。回顾前边得可数集元素得顺序。回顾前边得可数集,特别就是无穷可数集特别就是无穷可数集,都都就是用这种方法来证明得。就是用这种方法来证明得。说说明明(1)(1)可数集得任何子集都就是可数集。可数集得任何子集都就是可数集。一个集合得无限子集若不可数一个集合得无限子集若不可数,则该集合也不可数。则该集合也不可数。(2)(2)两个可数集得并就是可数集。两个可数集得并就是可数集。(3)(3)两个可数集得笛卡儿积就是可数集。两个可数集得笛卡儿积就是可数集。(4)(4)可数个可数集得笛卡儿积仍就是可数集。可数个
26、可数集得笛卡儿积仍就是可数集。(5)(5)无穷集无穷集A A得幂集得幂集P P(A A)不就是可数集。不就是可数集。可数集得性质可数集得性质可数集得性质可数集得性质 例例9 9、4 4 求下列集合得基数。求下列集合得基数。(1)Tx|x就是单词就是单词“BASEBALL”中得字母中得字母(2)Bx|xRx2=92x=8(3)CP(A),A=1,3,7,11(1)由由TB,A,S,E,L知知,cardT5。(2)由由B可知可知,cardB0。(3)由由|A|4可知可知,cardCcardP(A)|P(A)|2416。解答解答例例例例9 9 9 9、4 4 4 4 方法一方法一由由cardA0,c
27、ardBn,可知可知A,B都就是可数集。都就是可数集。令令A=a0,a1,a2,B=b0,b1,b2,bn 1。对任意得对任意得,AB,有有i kj l定义函数定义函数f:ABNf()in+j,i0,1,j0,1,n 1由于由于f 就是就是AB到到N得双射函数得双射函数,所以所以cardABcardN。例例例例9 9 9 9、5 5 5 5解答解答例例例例9 9 9 9、5 5 5 5 设设设设A A,B B为集合为集合为集合为集合,且且且且cardcardA A0 0,card,cardB Bn n,n n就是自然数就是自然数就是自然数就是自然数,n n00。求求求求cardcardA A
28、B B。例例9 9、5 5方法二方法二方法二方法二因为因为因为因为cardcardA A0 0,card,cardB Bn n,所以所以所以所以A A,B B都就是可数集。都就是可数集。都就是可数集。都就是可数集。根据性质根据性质根据性质根据性质(3)(3)可知可知可知可知,A A B B也就是可数集也就是可数集也就是可数集也就是可数集,所以所以所以所以,cardcardA A B B 0 0 当当当当B B 时时时时,cardcardA A cardcardA A B B,这就推出这就推出这就推出这就推出0 0 cardcardA A B B综合所述综合所述综合所述综合所述,cardcard
29、A A B B 0 0本章主本章主要内容要内容q集合等势得定义集合等势得定义q等势得性质等势得性质q集合优势得定义集合优势得定义q优势得性质优势得性质q重要得集合等势以及优势得结果重要得集合等势以及优势得结果q自然数及其自然数集合得定义自然数及其自然数集合得定义q可数集与不可数集可数集与不可数集q集合得基数集合得基数 本章学习要求本章学习要求q能够证明两个集合等势。能够证明两个集合等势。q能够证明一个集合优势于另一个集合。能够证明一个集合优势于另一个集合。q知道什么就是可数集与不可数集。知道什么就是可数集与不可数集。q会求一个简单集合得基数。会求一个简单集合得基数。等势得证明方法等势得证明方法
30、q证明集合证明集合A A与与B B等势得方法等势得方法直接构造从直接构造从A A到到B B得双射函数得双射函数 f需要证明需要证明 f 得满射性与得满射性与f f得单射性。得单射性。构造两个单射函数构造两个单射函数f f:A AB B 与与 g g:B BA A。给出函数给出函数f f与与g,g,证明证明f f与与g g得单射性。得单射性。利用等势得传递性利用等势得传递性直接计算直接计算A A与与B B得基数得基数,得到得到card card A A card card B B。q证明集合证明集合A A与自然数集合与自然数集合N N等势得方法等势得方法找到一个找到一个“数遍数遍”A A中元素得
31、顺序。中元素得顺序。例题选讲例题选讲1 1、已知、已知An7 7|nN,B n109|n N,求下列各题求下列各题:(1)(1)cardA(2)(2)cardB(3)(3)card(AB)(4)(4)card(AB)(1)构造双射函数构造双射函数 f:NA,f(n)=n7 7,因此因此 cardA0。(2)构造双射函数构造双射函数 g:NA,g(n)=n109,因此因此 cardB0。(3)(3)可数集得并仍旧就是可数集可数集得并仍旧就是可数集(或者由于或者由于AB N),),因此因此card(AB)0,但就是但就是0cardAcard(AB),从而得到从而得到 card(AB)0。(4)(4)因为因为7与与109互素互素,card(AB)n7 109|n N,与与(1)(1)类似得到类似得到 card(AB)0。解答解答