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

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

12.2集合的等勢

定義12.2.1對集合A和B，如果存在從A到B的雙射函數(shù)，就稱A和B等勢，記作A≈B如果不存在從A到B的雙射函數(shù)，就稱A和B不等勢，記作?

A≈B注意：證明等勢即構(gòu)造雙射等勢是等價關(guān)系，可以用來分類自反性：A≈AIA:A→A對稱性：若A≈B，則B≈Af:A→Bf-1:B→A傳遞性：若A≈B且B≈C，則A≈Cf:A→B,g:B→Cgof:A→C

集合的等勢

例1N≈N偶，N≈N奇f:N→N偶,f(n)=2n；g:N→N奇,g(n)=2n+1例2Z≈N.f:Z→N,0,n=0f(n)=2n,n>02|n|-1,n<0例3N≈N×N.(課本中圖11.1.1)f:N×N→N,f(<i,j>)=(i+j)(i+j+1)/2+i例4N≈Q證明:因為任何有理數(shù)都可以表示成分?jǐn)?shù)，即?m∈Z,?n∈

N-{0},m/n，從而找出全體既約分?jǐn)?shù)，它們表示出了全體有理數(shù)，并編號。f:N→Q,f(n)=編號[n]的既約分?jǐn)?shù).(課本中圖12.2.1)

集合的等勢

例5R≈R+.f:R→R+，f(x)=ex例6(0,1)≈Rf:(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=0f(x)=1/(n+2),x=1/n,n∈N-{0}x,其他注：無限集合可以和它的真子集等勢，但有限集合不能

結(jié)論

無限集合可以和它的真子集等勢，但有限集合不能N≈Z≈Q≈N×N(0,1)≈[0,1]≈R

P(A)≈A2

證明:令f:P(A)→A2,f(B)=χB,其中χB是B∈P(A)的特征函數(shù),χB:A→{0,1},χB(x)=1?x∈B.(1)f是單射,設(shè)B1,B2?A且B1≠B2,則f(B1)=χB1(x)≠χB2(x)=f(B2),故χB1

≠χB2.(2)f是滿射.任給χB:A→{0,1},令B={x|x∈A且χB(x)=1}?A,則f(B)=χB

集合的等勢

定理12.2.3(Cantor康托爾定理)(1)?N≈R(2)對任意的集合A,?A≈P(A)證明:(1)(反證)假設(shè)N≈R≈[0,1],則存在f:N→[0,1]雙射,對?n∈N,令f(n)=xn+1,于是ran(f)=[0,1]={x1,x2,x3,…,xn,…}將xi表示成如下小數(shù):

?N≈R

x1=0.a11a21a31……x2=0.a12a22a32……x3=0.a13a23a33……┇xn=0.a1na2na3n……┇其中0≤aji≤9,i,j=1,2,…

?N≈R

選一個[0,1]中的小數(shù)x=0.b1b2b3……使得(1)0≤bj≤9,i=1,2,…(2)bn

≠ann(3)對x也注意表示的唯一性由x的構(gòu)造可知,x∈[0,1],x?{x1,x2,x3,…,xn,…}(x與xn在第n位上不同).這與[0,1]={x1,x2,x3,…,xn,…}矛盾!

?N≈R

對角化方法x1=0.a11a21a31……x2=0.a12a22a32……x3=0.a13a23a33……┇xn=0.a1na2na3n……ann…┇

(2)對任意的集合A,?A≈P(A)

證明:(反證)假設(shè)存在雙射f:A→P(A),令B={x|x∈A∧x?f(x)}則B∈P(A).由f是雙射,設(shè)f(b)=B,則b∈B?b?f(b)?b?B,矛盾!

12.3有限集合與無限集合

自然數(shù)定義對任意的集合A,可以定義集合A+=A∪{A},把A+稱為A的后繼,A稱為A+的前驅(qū)集合0=?是一個自然數(shù)。若集合n是一個自然數(shù)，則集合n+1=n+也是一個自然數(shù)列出自然數(shù)0=? 1=0+=0∪{0}={0} 2=1+=1∪{1}={0,1} 3=2+=2∪{2}={0,1,2} …

有限集合與無限集合

定義12.3.1集合A是有限集合，當(dāng)且僅當(dāng)存在n∈N,使n≈A.集合A是無限集合，當(dāng)且僅當(dāng)A不是有限集合，即不存在n∈N,使n≈A.結(jié)論不存在與自己真子集等勢的自然數(shù)(鴿巢原理)不存在與自己真子集等勢的有限集合任何與自己真子集等勢的集合是無限集合.例N,R任何有限集合只與唯一的自然數(shù)等勢

12.4集合的基數(shù)

集合的基數(shù)就是集合中元素的個數(shù)定義9.6.1如果存在n∈N，使集合A與集合{x|x∈N∧x<n}={0，1，2，…，n-1}的元素個數(shù)相同，就說集合A的基數(shù)是n，記作#(A)=n或|A|=n或card(A)=n空集Φ的基數(shù)是0定義9.6.2如果存在n∈N，使n是集合A的基數(shù)．就說A是有限集合．如果不存在這樣的n，就說A是無限集合

集合的基數(shù)

對任意的集合A和B，它們的基數(shù)分別用card(A)和card(B)表示，并且card(A)=card(B)?A≈B對有限集合A和n∈N,若A≈n,則card(A)=n(有限基數(shù))N的基數(shù)：card(N)=?0(無限基數(shù))R的基數(shù)：card(R)=?1(無限基數(shù))

基數(shù)的運算

對任意的基數(shù)k和l,若存在集合K和L,card(K)=k,card(L)=l,則(1)若K?L=?,k+l=card(K?L) (2)k·l=card(K×L) (3)kl=card(LK),其中LK是從L到K的函數(shù)的集合對集合K,L,P,M,如果K≈P且L≈M,則K×L≈P×M且LK

≈MP.如果同時成立K?L=?且P?M=?,則K?L≈P?M

基數(shù)的運算

例7 k0=card(?K)=card({?})=1 0k=card(K?)=card(?)=0 00=card(??)=card({?})=1例8對任意集合A,有card(P(A))=2card(A)

基數(shù)的運算

例9對任意的n∈N,有 (1)n+?0=?0 (2)n·?0=?0 (3)?0+?0=?0 (4)?0·?0=?0證明:(1)令L=N,K={a1,…,an},且對于i=1,2,…,n有ai?N.則card(L)=?0,card(K)=n,K?L=?.于是K?L={a1,…,an,0,1,2,…}.構(gòu)造雙射函數(shù)f:K?L→N.則K?L≈N,且n+?0=card(K)+card(L)=card(K?L)=card(N)=?0

基數(shù)的運算

定理12.5.1對任意的基數(shù)k、l和m，有 (1)k+l=l+k,k·l=l·k (2)k+(l+m)=(k+l)+m, k·(l·m)=(k·l)·m (3)k·(l+m)=k·l+k·m (4)k(l+m)=Kl·km (5)(k·l)m=km·lm (6)(Kl)m=k(l·m) 另外，對任意的基數(shù)k，有k+0=k,k·0=0,k·1=k,k·2=k+k注意：對任意基數(shù)的運算的性質(zhì)，與自然數(shù)的運算性質(zhì)一致

基數(shù)的比較

定義12.6.1對集合K和L，card(K)=k,card(L)=l,如果存在從K到L的單射函數(shù)，則稱集合L優(yōu)勢于K，記作K≤L，且稱基數(shù)k不大于基數(shù)l，記作k≤l定義12.6.2對基數(shù)k和l，如果k≤l且k≠l，則稱k小于l，記作k<l例:對任意的自然數(shù)n，n≤?0

基數(shù)的比較

例10對任意的基數(shù)k，有k<2k證明：對基數(shù)k，存在集合K，使得card(K)=k.則有card(P(K))=2k.構(gòu)造函數(shù)f:A→P(A),f(x)={x},則f是單射的，進(jìn)而k≤2k. 又?K≈P(K)，k≠2k 因此k<2k注意：不存在最大的基數(shù)

基數(shù)的比較

定理12.6.1對任意的基數(shù)k，l和m，有 (1)k≤k (2)若k≤l且l≤m，則k≤m (3)若k≤l且l≤k，則k=l(Schroder-Bernstein施羅德-伯恩斯坦定理) (4)k≤l或l≤k

基數(shù)的比較

例11R≈N2證明：先證R≤N2.因(0,1)≈R,即證(0,1)≤N2H:(0,1)→(N→2)單射, ?z∈(0,1)的二進(jìn)制小數(shù),H(z):N→{0,1}, H(z)(n)=z的二進(jìn)制表示的第n+1位小數(shù). 再證N2≤R.因[0,1]≈R,即證N2≤[0,1] (2)G:(N→2)→[0,1]單射,?f:N→2,G(f)=0.f(0)f(1)f(2)…(第n+1位小數(shù)是f(n)). 由此例可得?1=card(R)=card(N2)=card(P(A))=2?0注意：對任意集合A，有P(A)≈A2

舉例

(1)z=0.101110011..時 H(z)(0)=1;H(z)(1)=0;H(z)(2)=1;H(z)(3)=1;H(z)(4)=1;…(2)特征函數(shù)f(0)=1,f(1)=0,f(2)=1,f(3)=0,… 可以得到十進(jìn)制小數(shù)f=0.1010…∈[0,1]

基數(shù)的比較

定理12.6.2對任意的基數(shù)k，l和m，如果k≤l，則 (1)k+m≤l+m (2)k·m≤l·m (3)km

≤lm (4)若k≠0或m≠0，mk

≤ml例2?0=1·2?0≤?0·2?0≤2?0·2?0=2?0+?0=2?0所以?0·2?0=2?0

基數(shù)的比較

結(jié)論 對基數(shù)k和l，如果k≤l、k≠0，l是無限基數(shù)，則k+l=k·l=l=max