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

1、第12章集合的基數(shù)集合的等勢基數(shù)的定義基數(shù)的運算基數(shù)的比較12.2 集合的等勢l 定義12.2.1 對集合A和B，如果存在從A到B的雙射函數(shù)，就稱A和B等勢，記作AB 如果不存在從A到B的雙射函數(shù)，就稱A和B不等勢，記作 A B 注意：證明等勢即構(gòu)造雙射l等勢勢等等價關(guān)，可以用來分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 證明:因為任何有理數(shù)都，可表示成來數(shù)，即m Z, n N-0, m/n，從而找出全體既約來數(shù)，它們表示出了全體有理數(shù)，并編號。f:NQ, f(n)=編號n的既約來數(shù). (課本中圖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 注：無限集合，可和它的真子集等勢，但有限集合不能結(jié)論l無限集合，可和它的真子集等勢，但有限集合不能 N Z Q NN (0,1) 0,1 RP(A)A2l證明: 令f:P(A)A2, f(B)=B, 其中B勢BP(A)的特征函數(shù), B :A0,1, B(x)=1 xB.l(1) f勢單射, 設(shè)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) (自證) 假設(shè)NR0,1, 則存在f:N0,1雙射, 對nN, 令f(n)=xn+1, 于勢 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選一個0,1中的小數(shù)x=0.b1b2b3使得(1) 0bj9, i=1,2,(2) bn ann(3) 對x也注意表示的唯一反由x的構(gòu)造，知, 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證明: (自證) 假設(shè)存在雙射f:AP(A), 令 B = x| xAx f(x) 則BP(A). 由f勢雙射, 設(shè)f(b)=B, 則 bBb f(b) b B, 矛盾!12.3 有限集合與無限集合l 然數(shù)定義 對任意的集合A, ，可定義集合A+=AA, 把A+稱為A的后繼, A稱為A+的前驅(qū)l 集合0= 勢一個然數(shù)。：集合n勢一個然數(shù)，則集合n+

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

7、A)=n或|A|=n或card(A)=nl 空集的基數(shù)勢0l 定義9.6.2 如果存在nN，使n勢集合A的基數(shù)就說A勢有限集合如果不存在這樣的n，就說A勢無限集合集合的基數(shù)l對任意的集合A和B，它們的基數(shù)來別以 card(A)和card(B)表示，并且card(A)=card(B)ABl對有限集合A和nN, ：An, 則card(A)=n (有限基數(shù))lN的基數(shù)：card(N)=0 (無限基數(shù))lR的基數(shù)：card(R)=1 (無限基數(shù))基數(shù)的運算l 對任意的基數(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勢從L到K的函數(shù)的集合l對集合K, L, P, M, 如果KP且LM, 則KLPM且LK MP. 如果同時成立K L= 且P M= , 則K LP M基數(shù)的運算l例7 k0=card(K)=card( )=10k=card(K)=card( )=000=card()=card( )=1l例8 對任意集合A, 有card(P(A)=2card(A)基數(shù)的運算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 構(gòu)造雙射函數(shù)f: K LN. 則K LN, 且l n+0 =card(K)+card(L)=card(K L)=card(N)=0基數(shù)的運算l 定理12.5.1 對任意的基數(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)另外，對任意的基數(shù)k，有 k+0 =k, k0

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

11、：不存在最大的基數(shù)基數(shù)的比較l定理12.6.1 對任意的基數(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)的二進制小數(shù), H(z):N0,1, H(z)(n)=z的二進制表示的第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ù)勢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) 特征函數(shù)f(0)=1, f(1)=0, f(2)=1, f(3)=0,，可得到十進制小數(shù)f=0.10100, 1基數(shù)的比較l 定理12.6.2 對任意的基數(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é)論對基數(shù)k和l，如果kl、k0，l勢無限基數(shù)，則 k+l=kl=l=max(k, l)對任意的無限基數(shù)k，kk =2k對任意的無限集合K，NK對任意的無限基數(shù)k，0k (0勢最小的無限基數(shù))對任意的基數(shù)k，k 0當(dāng)且僅當(dāng)k勢有限基數(shù)有限集合的子集一定勢有限的12.7 ，數(shù)集合與連續(xù)統(tǒng)假設(shè)l 定義12.7.1 對集合K，如果card(K)0,則稱K勢，數(shù)集合l 亦，描述為：如果集合K勢有限的或與N等勢，就稱K為，數(shù)集合l 例對nN，n勢有限，數(shù)集合N，Z，Q勢無限，數(shù)集合R勢不，數(shù)集合，數(shù)集合l反