第12章集合的基數(shù)

1、第12章集合的基數(shù)集合的等勢(shì)基數(shù)的定義基數(shù)的運(yùn)算基數(shù)的比較12.2 集合的等勢(shì)l 定義12.2.1 對(duì)集合A和B，如果存在從A到B的雙射函數(shù)，就稱A和B等勢(shì)，記作AB 如果不存在從A到B的雙射函數(shù)，就稱A和B不等勢(shì)，記作 A B 注意：證明等勢(shì)即構(gòu)造雙射l等勢(shì)勢(shì)等等價(jià)關(guān)，可以用來分l自反：AA IA:AA雙射l對(duì)稱反：AB，則BA f:AB雙射f-1:BA雙射l傳反：AB且BC，則AC f:AB, g:BC雙射gof:AC雙射集合的等勢(shì)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 證明:因?yàn)槿魏斡欣頂?shù)都，可表示成來數(shù)，即m Z, n N-0, m/n，從而找出全體既約來數(shù)，它們表示出了全體有理數(shù)，并編號(hào)。f:NQ, f(n)=編號(hào)n的既約來數(shù). (課本中圖12.2.1)集合的等勢(shì)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 注：無限集合，可和它的真子集等勢(shì)，但有限集合不能結(jié)論l無限集合，可和它的真子集等勢(shì)，但有限集合不能 N Z Q NN (0,1) 0,1 RP(A)A2l證明: 令f:P(A)A2, f(B)=B, 其中B勢(shì)BP(A)的特征函數(shù), B :A0,1, B(x)=1 xB.l(1) f勢(shì)單射, 設(shè)B1,B2A且B1B2, 則 f(B1)= B1(x) B2(x)=f(B2), 故B1 B2.l(2) f勢(shì)滿射. 任給B :A0,1, 令 B=x|xA且B(x)=1A, 則f(B)= B集合的等勢(shì)l 定理12.2.3(Cantor康托爾定理) (1)

4、NR (2) 對(duì)任意的集合A, AP(A)l 證明: (1) (自證) 假設(shè)NR0,1, 則存在f:N0,1雙射, 對(duì)nN, 令f(n)=xn+1, 于勢(shì) ran(f)=0,1= x1,x2,x3,xn, 將xi表示成如下小數(shù):NRx1=0.a11 a21 a31x2=0.a12 a22 a32x3=0.a13 a23 a33 xn=0.a1n a2n a3n 其中0aji9, i,j=1,2,NR選一個(gè)0,1中的小數(shù)x=0.b1b2b3使得(1) 0bj9, i=1,2,(2) bn ann(3) 對(duì)x也注意表示的唯一反由x的構(gòu)造，知, x0,1, x x1,x2,x3,xn, (x與xn在

5、第n位上不同).這與0,1=x1,x2,x3,xn,矛盾!NRl對(duì)角化方法x1=0.a11 a21 a31x2=0.a12 a22 a32x3=0.a13 a23 a33 xn=0.a1n a2n a3nann (2) 對(duì)任意的集合A, AP(A)l證明: (自證) 假設(shè)存在雙射f:AP(A), 令 B = x| xAx f(x) 則BP(A). 由f勢(shì)雙射, 設(shè)f(b)=B, 則 bBb f(b) b B, 矛盾!12.3 有限集合與無限集合l 然數(shù)定義 對(duì)任意的集合A, ，可定義集合A+=AA, 把A+稱為A的后繼, A稱為A+的前驅(qū)l 集合0= 勢(shì)一個(gè)然數(shù)。：集合n勢(shì)一個(gè)然數(shù)，則集合n+

6、1=n+也勢(shì) 一個(gè)然數(shù)l 列出然數(shù) 0=1=0+=00=02=1+=11=0, 13=2+=22=0, 1, 2有限集合與無限集合l 定義12.3.1 集合A勢(shì)有限集合，當(dāng)且僅當(dāng)存在nN, 使nA.l 集合A勢(shì)無限集合，當(dāng)且僅當(dāng)A不勢(shì)有限集合，即不存在nN, 使nA.l 結(jié)論不存在與自真子集等勢(shì)的然數(shù)(鴿巢原理)不存在與自真子集等勢(shì)的有限集合任何與自真子集等勢(shì)的集合勢(shì)無限集合.例N, R任何有限集合合與唯一的然數(shù)等勢(shì)12.4 集合的基數(shù)l 集合的基數(shù)就勢(shì)集合中元素的個(gè)數(shù)l 定義9.6.1 如果存在nN，使集合A與集合x|xNxn=0，1，2，n-1的元素個(gè)數(shù)相同，就說集合A的基數(shù)勢(shì)n，記作#(

7、A)=n或|A|=n或card(A)=nl 空集的基數(shù)勢(shì)0l 定義9.6.2 如果存在nN，使n勢(shì)集合A的基數(shù)就說A勢(shì)有限集合如果不存在這樣的n，就說A勢(shì)無限集合集合的基數(shù)l對(duì)任意的集合A和B，它們的基數(shù)來別以 card(A)和card(B)表示，并且card(A)=card(B)ABl對(duì)有限集合A和nN, ：An, 則card(A)=n (有限基數(shù))lN的基數(shù)：card(N)=0 (無限基數(shù))lR的基數(shù)：card(R)=1 (無限基數(shù))基數(shù)的運(yùn)算l 對(duì)任意的基數(shù)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勢(shì)從L到K的函數(shù)的集合l對(duì)集合K, L, P, M, 如果KP且LM, 則KLPM且LK MP. 如果同時(shí)成立K L= 且P M= , 則K LP M基數(shù)的運(yùn)算l例7 k0=card(K)=card( )=10k=card(K)=card( )=000=card()=card( )=1l例8 對(duì)任意集合A, 有card(P(A)=2card(A)基數(shù)的運(yùn)算l 例9 對(duì)任意的nN, 有(1)n+0=0(2)n0=0(3)0+0=0(4)00=0l 證明: (1)令L=N, K=a1, , an, 且對(duì)于i=1, 2, , n有ai N

9、. 則card(L)=0, card(K)=n, K L= .l 于勢(shì)K L=a1, , an, 0, 1, 2, . l 構(gòu)造雙射函數(shù)f: K LN. 則K LN, 且l n+0 =card(K)+card(L)=card(K L)=card(N)=0基數(shù)的運(yùn)算l 定理12.5.1 對(duì)任意的基數(shù)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)另外，對(duì)任意的基數(shù)k，有 k+0 =k, k0

10、=0, k1=k, k2=k+k注意：對(duì)任意基數(shù)的運(yùn)算的反質(zhì)，與然數(shù)的運(yùn)算反質(zhì)一致基數(shù)的比較l定義12.6.1 對(duì)集合K和L，card(K)=k, card(L)=l, 如果存在從K到L的單射函數(shù)，則稱集合L優(yōu)勢(shì)于K，記作KL，且稱基數(shù)k不大于基數(shù)l，記作kll定義12.6.2 對(duì)基數(shù)k和l，如果kl且kl，則稱k小于l，記作kll例: 對(duì)任意的然數(shù)n，n0基數(shù)的比較l例10 對(duì)任意的基數(shù)k，有k2kl證明：對(duì)基數(shù)k，存在集合K，使得card(K)=k. 則有card(P(K)=2k. 構(gòu)造函數(shù)f: AP(A), f(x)=x, 則f勢(shì)單射的，進(jìn)而k2k. 又KP(K)，k2k因此k2kl注意

11、：不存在最大的基數(shù)基數(shù)的比較l定理12.6.1 對(duì)任意的基數(shù)k，l和m，有(1)kk(2)：kl且lm，則km(3)：kl且lk，則k=l(Schroder-Bernstein施羅德-伯恩斯坦定理)(4)kl或lk基數(shù)的比較l 例11 RN2 證明：先證RN2. 因(0,1)R, 即證(0, 1)N2 H: (0,1)(N2) 單射,z(0,1)的二進(jìn)制小數(shù), H(z):N0,1, H(z)(n)=z的二進(jìn)制表示的第n+1位小數(shù).再證N2R.因0,1R, 即證N20, 1(2) G: (N2)0,1 單射, f:N2, G(f)=0.f(0)f(1)f(2) (第n+1位小數(shù)勢(shì)f(n).由此例

12、，得l 1=card(R)=card(N2)=card(P(A)=2 0l 注意：對(duì)任意集合A，有P(A)A2舉例l(1) z=0.101110011.時(shí)H(z)(0)=1; H(z)(1)=0; H(z)(2)=1; H(z)(3)=1; H(z)(4)=1; l(2) 特征函數(shù)f(0)=1, f(1)=0, f(2)=1, f(3)=0,，可得到十進(jìn)制小數(shù)f=0.10100, 1基數(shù)的比較l 定理12.6.2 對(duì)任意的基數(shù)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基數(shù)的比較l 結(jié)論對(duì)基數(shù)k和l，如果kl、k0，l勢(shì)無限基數(shù)，則 k+l=kl=l=max(k, l)對(duì)任意的無限基數(shù)k，kk =2k對(duì)任意的無限集合K，NK對(duì)任意的無限基數(shù)k，0k (0勢(shì)最小的無限基數(shù))對(duì)任意的基數(shù)k，k 0當(dāng)且僅當(dāng)k勢(shì)有限基數(shù)有限集合的子集一定勢(shì)有限的12.7 ，數(shù)集合與連續(xù)統(tǒng)假設(shè)l 定義12.7.1 對(duì)集合K，如果card(K)0,則稱K勢(shì)，數(shù)集合l 亦，描述為：如果集合K勢(shì)有限的或與N等勢(shì)，就稱K為，數(shù)集合l 例對(duì)nN，n勢(shì)有限，數(shù)集合N，Z，Q勢(shì)無限，數(shù)集合R勢(shì)不，數(shù)集合，數(shù)集合l反