第11讲--基数-北京大学计算机系离散数学讲义(版).ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,集合论与图论第11讲,*,第11讲 基数,内容提要,等势,优势,劣势,绝对优势,绝对劣势,Cantor,定理,Schr,der-Bernstein,定理,基数(势),0,有穷集,无穷集,可数集(可列集),基数运算,2026/10/22,1,集合论与图论第11讲,两个基本过程,匹配,(,matching):,多少,大小(基数)-双射,a 0=1,a,b 0,1=2,a,b,c,0,1,2=3,计数,(,counting):,首尾,先后(序数)-良序,0,123,a,b,cba,2026/10/22,2,集合论与图论第11讲,无穷之迷,许多关于无穷的悖论,无穷是否“存在”?人是否“理解”无穷?,无穷大,无穷小,无限可分性,极限,有穷与无穷的区别?,2026/10/22,3,集合论与图论第11讲,芝诺悖论(,Zenos paradox),芝诺悖论,:阿基里斯(,Achilles),追不上乌龟,阿基里斯比乌龟快一倍,乌龟在阿基里斯前面起跑,2026/10/22,4,集合论与图论第11讲,等势关系是等价关系,自反,:,AA,I,A,:AA,双射,对称,:,AB BA,f,:AB,双射,f,-1,:BA,双射,传递,:,AB,BC AC,f,:AB,g:BC,双射,g,f:AC,双射,2026/10/22,6,集合论与图论第11讲,证明等势,构造双射,直接构造双射:,NNN,R(0,1),0,1(0,1),(0,1)2,N,P(A)2,A,A(BC)(AB)C,间接构造双射:,传递性:,AB BC AC,S-B,定理:,AB BA AB,2026/10/22,7,集合论与图论第11讲,R(0,1),2026/10/22,8,集合论与图论第11讲,0,1(0,1),2026/10/22,10,集合论与图论第11讲,(0,1)2,N,N 0,1,2,3,S,1,0,1,1,0,S,2,1,0,1,0,0,0,0,0,N 1,1,1,1,0.0110,0.1010,0.0000,0.1111,问题,:0.0111111=0.1000,非单射!,解决:,?,2026/10/22,11,集合论与图论第11讲,A(BC)(AB)C,证明,:,令,F:(,A(BC)(AB)C),F(f)=g,其中,f:A(BC),g:(AB)C,g()=(f(a)(b),注意,f(a):BC.,2026/10/22,13,集合论与图论第11讲,A(BC)(AB)C,证明(续),:(2),F,是,满射,.,任给,g:(AB)C,下证,f:A(BC),使得,F(f),=,g.,令,f:A(BC),aA,f(a):BC,xB,(f(a)(x)=g(),则,F(f),=,g.#,2026/10/22,15,集合论与图论第11讲,S-B,定理,Schr,der-Bernstein,定理,:,AB BA AB,证明,:设,f,:AB,g:BA,单射,要构造,h:AB,双射.,2026/10/22,16,集合论与图论第11讲,S-B,定理,A,B,f,g,B,0,=B-ran f,A,0,=g(B,0,),B,1,=f(A,0,),A,1,=g(B,1,),B,2,=f(A,1,),A,n,=g(B,n,),B,n+1,=f(A,n,),B,0,B,1,B,2,B,3,A,0,A,1,A,2,A,3,2026/10/22,18,集合论与图论第11讲,S-B,定理,A,B,f,g,-1,B,0,B,1,B,2,B,3,A,0,A,1,A,2,A,3,A,B,f,g,B,0,B,1,B,2,B,3,A,0,A,1,A,2,A,3,2026/10/22,19,集合论与图论第11讲,证明不等势:,归纳法,对角化,n,m,N nm nm,NP(N),AP(A),2026/10/22,20,集合论与图论第11讲,n,m,N nm nm,定理,:不存在与自己的真子集等势的自然数.,说明,:,0,1,n-1,0,1,m-1,n-1,证明,:(数学归纳法)令,S=n,N|f(f:nn f,单射,f,满射.,(1)0,S:f:00 f,是空函数,f,满射.,2026/10/22,21,集合论与图论第11讲,n,m,N nm nm,证明(续),:(2)设,n,S,要证,n,+,S.,设,f:n,+,n,+,且,f,是单射,下证,f,是满射.,设,g=f,n:nn,+,(a)n,在,f,下封闭.,ran f=ran g,n=n n=n,+,.,(,由归纳假设,ran g,=n,),说明,:,0,n-1,n ,0,n-1,n,0,n-1,n,0,n-1,n,2026/10/22,22,集合论与图论第11讲,Cantor,定理,Cantor,定理,:设,A,为任意集合,则,A,P(A).,证明,:(反证)假设存在双射,f:A,P(A),令,B=x,A,|x,f(x),则,B,P(A).,由,f,是双射,设,f(b)=B,则,bB bf(b)bB,矛盾!#,2026/10/22,24,集合论与图论第11讲,Cantor,定理(证明),A,P(A),a,b,c,a,ab,ac,bc,abc,b,c,abc,000,001,c,010,b,011,b,c,100,a,101,a,c,110,a,b,111,a,b,c,2026/10/22,25,集合论与图论第11讲,Cantor,定理(证明),A,P(A),?,2026/10/22,26,集合论与图论第11讲,m,nN,m,S,n,?,0,1,2,3,4,5,S,0,是,否,是,否,是,是,S,1,否,是,否,否,是,否,S,2,否,否,否,否,否,否,S,3,是,否,是,否,是,否,S,4,是,是,是,是,是,是,S,5,否,是,否,否,否,是,2026/10/22,28,集合论与图论第11讲,nN,nS,n,?,0,1,2,3,4,5,S,0,是,否,是,否,是,是,S,1,否,是,否,否,是,否,S,2,否,否,否,否,否,否,S,3,是,否,是,否,是,否,S,4,是,是,是,是,是,是,S,5,否,是,否,否,否,是,2026/10/22,29,集合论与图论第11讲,对角化(,diagonalization),证明,(,续):,构造“对角化集”,S,d:,S,d,=n,N,|n,S,n,显然,S,d,S,0,S,1,S,2,这是因为,n,S,d,n,S,n,(,nN).,但是,S,d,S,0,S,1,S,2,这是因为,S,0,S,1,S,2,是对全体自然数的幂集的列举,矛盾!#,2026/10/22,31,集合论与图论第11讲,对角化简史(1),公元前7世纪(600,BC):Epimenides,悖论,所有克里特人都是说谎者,-一个,克里特,诗人如是说,.,公元前5世纪,(400 BC):Eubulides,悖论,这句话是假的,.,公元13世纪(1200,AD):Medieval Study of Insolubia.,我是说谎者,.,2026/10/22,32,集合论与图论第11讲,对角化简史(2),1874年:,Cantor,定理,实数集是不可数的,.,1901,年:,Russell,悖论,不以自身作为元素的集合的全体,.,1931,年:,Gdel,不完全性定理,这句话没有证明,.,2026/10/22,33,集合论与图论第11讲,对角化简史(3),1936年:,Turing.,停机问题是不可判定的,.,1956,年:,Friedberg&Muchnik.,存在不完全的,Turing,度,.,1965,年:,Hartmanis&Stearns,更多的时间可以“计算出”更多的语言,.,2026/10/22,34,集合论与图论第11讲,有穷集,无穷集,有穷集,(,finite set):,不能与自身真子集建立双射的集合,无穷集,(,infinite set),:可以与自身真子集建立双射的集合,无穷集也称,无限集,Bernhard Bolzano(17811848),Czech,人,1851,“,paradoxes of the infinite”,首次使用“,set”,一词,给出无穷集的上述定义,2026/10/22,35,集合论与图论第11讲,基数(,cardinality),基数,:|,A|,或,card A,满足5条约定(公理),1,.card A=card B,A B,2,.A,为有穷集,则,card A=n,其中,A n,(n,是唯一的),3,.card N=,0,4,.,card R=,5,.0,1,2,0,都是基数,0,1,2,是有穷基数,K,0,=,K,1,=x|card x=1,K,=x|card x=,2026/10/22,36,集合论与图论第11讲,基数的比较,设,为基数,A,B,为集合,card A=,card B=,规定:,A B,A B,=,A B,例:0,.设,card A=,单射:,A.,A,非空时,0.,n,0,.,card A card P(A).,2026/10/22,37,集合论与图论第11讲,可数集(,enumerable set),可数集,(,可列集,):,card A,0,.,有穷可数集,:,n,(nN),无穷可数集,:,N,定理15,:,A,是无穷可数集,A=a,1,a,2,定理18,:,A,是无穷集,P(A),不是可数集,2026/10/22,38,集合论与图论第11讲,基数运算,设,为基数,K,L,为集合,card K=,card L=,规定,(1),+,=,card(,K,L),其中,K,L=,(2),=,card(,K,L),(3),=,card(,L,K),也记作,或,2026/10/22,39,集合论与图论第11讲,基数运算,定理19,:设,K,1,K,2,L,1,L,2,为集合,K,1,K,2,L,1,L,2,则,(1)若,K,1,L,1,=K,2,L,2,=,则,K,1,L,1,K,2,L,2,(2),K,1,L,1,K,2,L,2,(3),K,1,L,1,K,2,L,2,.#,2026/10/22,40,集合论与图论第11讲,基数运算,定理20,:(1)2,cardA,=card P(A),(2),2,.#,推论,:(1),card P(N)=2,0,(2)card P(R)=2,(3)=2,0,.#,2026/10/22,41,集合论与图论第11讲,基数运算,定理21,:设,为基数,(1),+,=,+,(2)(,+)+,=,+(+),(3),(,+),=(,)+(),(4),+,=,(5)(,),=,(6)(,),=,.#,2026/10/22,42,集合论与图论第11讲,基数运算,定理22,:设,为基数,(1),+,+,(2),(3),(4),其中,不同时为0.#,2026/10/22,43,集合论与图论第11讲,基数运算,定理23,:设,为无穷基数,则,=.#,定理24,:设,为无穷基数,为基数,则,+=,=,max,(,其中,0,),推论,:+=.#,定理25,:设,为无穷基数,则,=2,.#,2026/10/22,44,集合论与图论第11讲,总结,等势,优势,劣势,绝对优势,绝对劣势,Cantor,定理,Schr,der-Bernstein,定理,基数(势),0,有穷集,无穷集,可数集(可列集),基数运算,2026/10/22,45,集合论与图论第11讲,作业(#9),p148,习题五,5,11,12,+补充题,补充题,:设,为任意基数,证明:,(1),0,=1;,(2)当 0 时,0,=0;,(3)+=2,2026/10/22,46,集合论与图论第11讲,通知,ftp:/162.105.30.157:,graph,:,graph,第4周,3月13日(本周四):序数,第5周,3月17日(下周一):习题课,3月19日(下周三):图论,3月20日(下周四):测验(1小时),2026/10/22,47,集合论与图论第11讲,