第12章集合的基数.ppt

1、第12章集合的基数,集合的等势基数的定义基数的运算基数的比较,12.2 集合的等势,定义12.2.1 对集合A和B，如果存在从A到B的双射函数，就称A和B等势，记作AB 如果不存在从A到B的双射函数，就称A和B不等势，记作 A B 注意：证明等势即构造双射等势是等价关系，可以用来分类自反性：AA IA:AA双射对称性：若AB，则BA f:AB双射f-1:BA双射传递性：若AB且BC，则AC f:AB, g:BC双射gof:AC双射,集合的等势,例1 N N偶，N N奇 f: N N偶, f(n)=2n；g: N N奇, g(n)=2n+1例2 ZN. f: ZN, 0, n=0 f(n) =

2、2n, n0 2|n|-1, n)=(i+j)(i+j+1)/2 + i,例4 NQ 证明:因为任何有理数都可以表示成分数，即m Z, n N-0, m/n，从而找出全体既约分数，它们表示出了全体有理数，并编号。f:NQ, f(n)=编号n的既约分数. (课本中图12.2.1),集合的等势,例5 RR+. f: RR+，f(x)=ex例6 (0, 1)R f: (0,1)R, x(0,1) f(x)=tan(x-1/2)例7 0, 1(0, 1) f: 0,1(0,1), 1/2, x=0 f(x) = 1/(n+2), x=1/n, nN-0 x, 其他注：无限集合可以和它的真子集等势，但有

3、限集合不能,结论,无限集合可以和它的真子集等势，但有限集合不能 N Z Q NN (0,1) 0,1 R,P(A)A2,证明: 令f:P(A)A2, f(B)=B, 其中B是BP(A)的特征函数, B :A0,1, B(x)=1 xB.(1) f是单射, 设B1,B2A且B1B2, 则 f(B1)= B1(x) B2(x)=f(B2), 故B1 B2.(2) f是满射. 任给B :A0,1, 令 B=x|xA且B(x)=1A, 则f(B)= B,集合的等势,定理12.2.3(Cantor康托尔定理) (1) NR (2) 对任意的集合A, AP(A)证明: (1) (反证) 假设NR0,1,

4、则存在f:N0,1双射, 对nN, 令f(n)=xn+1, 于是 ran(f)=0,1= x1,x2,x3,xn, 将xi表示成如下小数:,NR,x1=0.a11 a21 a31x2=0.a12 a22 a32x3=0.a13 a23 a33 xn=0.a1n a2n a3n 其中0aji9, i,j=1,2,NR,选一个0,1中的小数x=0.b1b2b3使得(1) 0bj9, i=1,2,(2) bn ann(3) 对x也注意表示的唯一性由x的构造可知, x0,1, xx1,x2,x3,xn, (x与xn在第n位上不同).这与0,1=x1,x2,x3,xn,矛盾!,NR,对角化方法x1=0.

5、a11 a21 a31x2=0.a12 a22 a32x3=0.a13 a23 a33 xn=0.a1n a2n a3nann ,(2) 对任意的集合A, AP(A),证明: (反证) 假设存在双射f:AP(A), 令 B = x| xAxf(x) 则BP(A). 由f是双射, 设f(b)=B, 则 bBbf(b) bB, 矛盾!,12.3 有限集合与无限集合,自然数定义 对任意的集合A, 可以定义集合A+=AA, 把A+称为A的后继, A称为A+的前驱集合0=是一个自然数。若集合n是一个自然数，则集合n+1=n+也是 一个自然数列出自然数 0=1=0+=00=02=1+=11=0, 13=2

6、+=22=0, 1, 2,有限集合与无限集合,定义12.3.1 集合A是有限集合，当且仅当存在nN, 使nA.集合A是无限集合，当且仅当A不是有限集合，即不存在nN, 使nA.结论不存在与自己真子集等势的自然数(鸽巢原理)不存在与自己真子集等势的有限集合任何与自己真子集等势的集合是无限集合.例N, R任何有限集合只与唯一的自然数等势,12.4 集合的基数,集合的基数就是集合中元素的个数定义9.6.1 如果存在nN，使集合A与集合x|xNxn=0，1，2，n-1的元素个数相同，就说集合A的基数是n，记作#(A)=n或|A|=n或card(A)=n空集的基数是0定义9.6.2 如果存在nN，使n是

7、集合A的基数就说A是有限集合如果不存在这样的n，就说A是无限集合,集合的基数,对任意的集合A和B，它们的基数分别用 card(A)和card(B)表示，并且card(A)=card(B)AB对有限集合A和nN, 若An, 则card(A)=n (有限基数)N的基数：card(N)=0 (无限基数)R的基数：card(R)=1 (无限基数),基数的运算,对任意的基数k和l, 若存在集合K和L, card(K)=k, card(L)=l, 则 (1)若KL=, k+l=card(KL)(2)kl=card(KL)(3)kl=card(LK), 其中LK是从L到K的函数的集合对集合K, L, P,

8、M, 如果KP且LM, 则KLPM且LK MP. 如果同时成立KL=且PM=, 则KLPM,基数的运算,例7 k0=card(K)=card()=10k=card(K)=card()=000=card()=card()=1例8 对任意集合A, 有card(P(A)=2card(A),基数的运算,例9 对任意的nN, 有(1)n+0=0(2)n0=0(3)0+0=0(4)00=0证明: (1)令L=N, K=a1, , an, 且对于i=1, 2, , n有aiN. 则card(L)=0, card(K)=n, KL=.于是KL=a1, , an, 0, 1, 2, . 构造双射函数f: KLN

9、. 则KLN, 且n+0 =card(K)+card(L)=card(KL)=card(N)=0,基数的运算,定理12.5.1 对任意的基数k、l和m，有(1) k+l= l+k, kl=lk(2) k+(l+m)=(k+l)+m,k (lm)=(kl) m(3) k (l+m)=kl+km(4) k(l+m) =K l km(5) (kl)m = km lm(6) (K l)m= k(lm)另外，对任意的基数k，有 k+0 =k, k0=0, k1=k, k2=k+k注意：对任意基数的运算的性质，与自然数的运算性质一致,基数的比较,定义12.6.1 对集合K和L，card(K)=k, car

10、d(L)=l, 如果存在从K到L的单射函数，则称集合L优势于K，记作KL，且称基数k不大于基数l，记作kl定义12.6.2 对基数k和l，如果kl且kl，则称k小于l，记作kl例: 对任意的自然数n，n0,基数的比较,例10 对任意的基数k，有k2k证明：对基数k，存在集合K，使得card(K)=k. 则有card(P(K)=2k. 构造函数f: AP(A), f(x)=x, 则f是单射的，进而k2k. 又KP(K)，k2k因此k2k注意：不存在最大的基数,基数的比较,定理12.6.1 对任意的基数k，l和m，有(1)kk(2)若kl且lm，则km(3)若kl且lk，则k=l(Schroder

11、-Bernstein施罗德-伯恩斯坦定理)(4)kl或lk,基数的比较,例11 RN2 证明：先证RN2. 因(0,1)R, 即证(0, 1)N2 H: (0,1)(N2) 单射,z(0,1)的二进制小数, H(z):N0,1, H(z)(n)=z的二进制表示的第n+1位小数.再证N2R.因0,1R, 即证N20, 1(2) G: (N2)0,1 单射, f:N2, G(f)=0.f(0)f(1)f(2) (第n+1位小数是f(n).由此例可得1=card(R)=card(N2)=card(P(A)=20注意：对任意集合A，有P(A)A2,举例,(1) z=0.101110011.时H(z)(

12、0)=1; H(z)(1)=0; H(z)(2)=1; H(z)(3)=1; H(z)(4)=1; (2) 特征函数f(0)=1, f(1)=0, f(2)=1, f(3)=0,可以得到十进制小数f=0.10100, 1,基数的比较,定理12.6.2 对任意的基数k，l和m，如果kl，则(1) k+ml+m(2) kmlm(3) km lm(4) 若k0或m0，mk ml例20=12002020 20=20+0=20 所以020=20,基数的比较,结论对基数k和l，如果kl、k0，l是无限基数，则 k+l=kl=l=max(k, l)对任意的无限基数k，kk =2k对任意的无限集合K，NK对任

13、意的无限基数k，0k (0是最小的无限基数)对任意的基数k，k 0当且仅当k是有限基数有限集合的子集一定是有限的,12.7 可数集合与连续统假设,定义12.7.1 对集合K，如果card(K)0,则称K是可数集合亦可描述为：如果集合K是有限的或与N等势，就称K为可数集合例对nN，n是有限可数集合N，Z，Q是无限可数集合R是不可数集合,可数集合,性质可数集的任何子集是可数集两个可数集的并集和笛卡儿积是可数集若K是无限集合，则P(K)是不可数的可数个可数集的并集是可数集 (或者，若A是可数集，A的元素都是可数集，则A是可数集),连续统假设,已知的基数按从小到大的次序排列为： 0，1，n，0，1，21 ，连续统假设断言：不存在基数k，使得 0k1=20该假设至今未得到证明. 但是，据证，根据现有的公理系统，既不能证明它是对的，也不能证明它是错的,