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

1、第12章集合的基數(shù),集合的等勢基數(shù)的定義基數(shù)的運算基數(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≈A IA:A→A雙射

2、􀂄對稱性：若A≈B，則B≈A f:A→B雙射?f-1:B→A雙射􀂄傳遞性：若A≈B且B≈C，則A≈C f:A→B, g:B→C雙射?gof:A→C雙射,集合的等勢,例1 N ≈N偶，N ≈N奇 f: N→ N偶, f(n)=2n；g: N→ N奇, g(n)=2n+1例2 Z≈N. f:

3、Z→N, 0, n=0 f(n) = 2n, n>0 2|n|-1, n)=(i+j)(i+j+1)/2 + i,,例4 N≈Q 證明:因為任何有理數(shù)都可以表示成分數(shù)，即?m ∈Z, ?n ∈ N-{0}, m/n，從而找出全體既約分數(shù)，它們表示出了全體有理數(shù)，并編號。f:N→Q, f(n)=編號[n]的既約分數(shù).

4、 (課本中圖12.2.1),集合的等勢,例5 R≈R+. f: R→R+，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),

5、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

6、? 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)證明

7、: (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.a11 a21 a31……x2=0.a12 a22 a32……x3=0.a13 a23 a33…… ┇xn=0.a1n a2n a3n……

8、┇其中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.a11 a

9、21 a31……x2=0.a12 a22 a32……x3=0.a13 a23 a33…… ┇xn=0.a1n a2n a3n……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,

10、 矛盾!,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是

11、有限集合，當且僅當存在n∈N, 使n≈A.集合A是無限集合，當且僅當A不是有限集合，即不存在n∈N, 使n≈A.結(jié)論􀂄不存在與自己真子集等勢的自然數(shù)(鴿巢原理)􀂄不存在與自己真子集等勢的有限集合􀂄任何與自己真子集等勢的集合是無限集合.例N, R􀂄任何有限集合只與唯一的自然數(shù)等勢,12.4 集合的基數(shù),集合的基數(shù)就是集合中元素的個數(shù)定義9.6.1 如果存

12、在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

13、和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ù)的集

14、合􀂆對集合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({?})=10k=card(K?)=card(?)=000=card(??)=card({?})=1例8 對任意集合A, 有card(P(A))=2card(A),基數(shù)的運算,例9 對任意

15、的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

16、)+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) =K l ·km(5

17、) (k·l)m = km ·lm(6) (K l)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，且稱

18、基數(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是單射的，進而k≤2k. 又¬K≈P(K)，k≠2k因此k<2k注意

19、：不存在最大的基數(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ù)的比較,例11 R≈N2 證明：先證R≤N2. 因(0,1)≈R, 即證(0, 1)≤N2 H: (0,1)→(N→2) 單射,?z∈(0,1)的二進制小數(shù), H(

20、z):N→{0,1}, H(z)(n)=z的二進制表示的第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.

21、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,…可以得到十進制小數(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 ≤

22、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(k, l)對任意的無限基數(shù)k，kk =2k對任意的無限集合K，N≤K對任意的無限基數(shù)k，?0≤k (?0是最小的無限基數(shù))

23、對任意的基數(shù)k，k < ?0當且僅當k是有限基數(shù)有限集合的子集一定是有限的,12.7 可數(shù)集合與連續(xù)統(tǒng)假設(shè),定義12.7.1 對集合K，如果card(K)≤?0,則稱K是可數(shù)集合亦可描述為：如果集合K是有限的或與N等勢，就稱K為可數(shù)集合例對n∈N，n是有限可數(shù)集合􀂄N，Z，Q是無限可數(shù)集合􀂄R是不可數(shù)集合,可數(shù)集合,性質(zhì)􀂄可數(shù)集的任何子集是可數(shù)集&#

24、1048708;兩個可數(shù)集的并集和笛卡兒積是可數(shù)集􀂄若K是無限集合，則P(K)是不可數(shù)的􀂄可數(shù)個可數(shù)集的并集是可數(shù)集 (或者，若A是可數(shù)集，A的元素都是可數(shù)集，則?A是可數(shù)集),連續(xù)統(tǒng)假設(shè),已知的基數(shù)按從小到大的次序排列為： 0，1，…，n，…，?0，?1，2?1 ，…連續(xù)統(tǒng)假設(shè)斷言：不存在基數(shù)k，使得 ?0<k<?1=2?0該假設(shè)至今未得到證明.