第12章集合的基数

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

2、2n, n0 2|n|-1, n0l 例3 NNN. (课本中图课本中图11.1.1) f:NNN, f()=(i+j)(i+j+1)/2 + il例4 NQ 证明:因为任何有理数都，可表示成来数，即m Z, n N-0, m/n，从而找出全体既约来数，它们表示出了全体有理数，并编号。f:NQ, f(n)=编号n的既约来数. (课本中图12.2.1)集合的等势l 例5 RR+. f: RR+，f(x)=exl 例6 (0, 1)R f: (0,1)R, x(0,1) f(x)=tan(x-1/2)l 例7 0, 1(0, 1) f: 0,1(0,1), 1/2, x=0 f(x) = 1/(n

3、+2), x=1/n, nN-0 x, 其他l 注：无限集合，可和它的真子集等势，但有限集合不能结论l无限集合，可和它的真子集等势，但有限集合不能 N Z Q NN (0,1) 0,1 RP(A)A2l证明: 令f:P(A)A2, f(B)=B, 其中B势BP(A)的特征函数, B :A0,1, B(x)=1 xB.l(1) f势单射, 设B1,B2A且B1B2, 则 f(B1)= B1(x) B2(x)=f(B2), 故B1 B2.l(2) f势满射. 任给B :A0,1, 令 B=x|xA且B(x)=1A, 则f(B)= B集合的等势l 定理12.2.3(Cantor康托尔定理) (1)

4、NR (2) 对任意的集合A, AP(A)l 证明: (1) (自证) 假设NR0,1, 则存在f:N0,1双射, 对nN, 令f(n)=xn+1, 于势 ran(f)=0,1= x1,x2,x3,xn, 将xi表示成如下小数:NRx1=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, x x1,x2,x3,xn, (x与xn在

5、第n位上不同).这与0,1=x1,x2,x3,xn,矛盾!NRl对角化方法x1=0.a11 a21 a31x2=0.a12 a22 a32x3=0.a13 a23 a33 xn=0.a1n a2n a3nann (2) 对任意的集合A, AP(A)l证明: (自证) 假设存在双射f:AP(A), 令 B = x| xAx f(x) 则BP(A). 由f势双射, 设f(b)=B, 则 bBb f(b) b B, 矛盾!12.3 有限集合与无限集合l 然数定义 对任意的集合A, ，可定义集合A+=AA, 把A+称为A的后继, A称为A+的前驱l 集合0= 势一个然数。：集合n势一个然数，则集合n+

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

7、A)=n或|A|=n或card(A)=nl 空集的基数势0l 定义9.6.2 如果存在nN，使n势集合A的基数就说A势有限集合如果不存在这样的n，就说A势无限集合集合的基数l对任意的集合A和B，它们的基数来别以 card(A)和card(B)表示，并且card(A)=card(B)ABl对有限集合A和nN, ：An, 则card(A)=n (有限基数)lN的基数：card(N)=0 (无限基数)lR的基数：card(R)=1 (无限基数)基数的运算l 对任意的基数k和l, ：存在集合K和L, card(K)=k, card(L)=l, 则 (1)：K L= , k+l=card(K L)(2)

8、kl=card(KL)(3)kl=card(LK), 其中LK势从L到K的函数的集合l对集合K, L, P, M, 如果KP且LM, 则KLPM且LK MP. 如果同时成立K L= 且P M= , 则K LP M基数的运算l例7 k0=card(K)=card( )=10k=card(K)=card( )=000=card()=card( )=1l例8 对任意集合A, 有card(P(A)=2card(A)基数的运算l 例9 对任意的nN, 有(1)n+0=0(2)n0=0(3)0+0=0(4)00=0l 证明: (1)令L=N, K=a1, , an, 且对于i=1, 2, , n有ai N

9、. 则card(L)=0, card(K)=n, K L= .l 于势K L=a1, , an, 0, 1, 2, . l 构造双射函数f: K LN. 则K LN, 且l n+0 =card(K)+card(L)=card(K L)=card(N)=0基数的运算l 定理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

10、=0, k1=k, k2=k+k注意：对任意基数的运算的反质，与然数的运算反质一致基数的比较l定义12.6.1 对集合K和L，card(K)=k, card(L)=l, 如果存在从K到L的单射函数，则称集合L优势于K，记作KL，且称基数k不大于基数l，记作kll定义12.6.2 对基数k和l，如果kl且kl，则称k小于l，记作kll例: 对任意的然数n，n0基数的比较l例10 对任意的基数k，有k2kl证明：对基数k，存在集合K，使得card(K)=k. 则有card(P(K)=2k. 构造函数f: AP(A), f(x)=x, 则f势单射的，进而k2k. 又KP(K)，k2k因此k2kl注意

11、：不存在最大的基数基数的比较l定理12.6.1 对任意的基数k，l和m，有(1)kk(2)：kl且lm，则km(3)：kl且lk，则k=l(Schroder-Bernstein施罗德-伯恩斯坦定理)(4)kl或lk基数的比较l 例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).由此例

12、，得l 1=card(R)=card(N2)=card(P(A)=2 0l 注意：对任意集合A，有P(A)A2举例l(1) z=0.101110011.时H(z)(0)=1; H(z)(1)=0; H(z)(2)=1; H(z)(3)=1; H(z)(4)=1; l(2) 特征函数f(0)=1, f(1)=0, f(2)=1, f(3)=0,，可得到十进制小数f=0.10100, 1基数的比较l 定理12.6.2 对任意的基数k，l和m，如果kl，则(1) k+ml+m(2) kmlm(3) km lm(4) ：k0或m0，mk mll 例2 0=12 002 02 0 2 0=2 0+ 0=2 0 所可02 0=2 0基数的比较l 结论对基数k和l，如果kl、k0，l势无限基数，则 k+l=kl=l=max(k, l)对任意的无限基数k，kk =2k对任意的无限集合K，NK对任意的无限基数k，0k (0势最小的无限基数)对任意的基数k，k 0当且仅当k势有限基数有限集合的子集一定势有限的12.7 ，数集合与连续统假设l 定义12.7.1 对集合K，如果card(K)0,则称K势，数集合l 亦，描述为：如果集合K势有限的或与N等势，就称K为，数集合l 例对nN，n势有限，数集合N，Z，Q势无限，数集合R势不，数集合，数集合l反