離散數(shù)學(xué)第四章第二節(jié)

1、1第4-2講 集合的基數(shù)1. 自然數(shù)集合2. 等勢(shì)3. 可數(shù)集4. 不可數(shù)集5. 基數(shù)的比較6. 第4-2講 作業(yè)21、自然數(shù)集合（1） 有時(shí)有時(shí)我們會(huì)對(duì)集合中元素的個(gè)數(shù)感興趣，利用映射可我們會(huì)對(duì)集合中元素的個(gè)數(shù)感興趣，利用映射可以研究這一問題。為此以研究這一問題。為此, 要用到自然數(shù)集合，它可由空要用到自然數(shù)集合，它可由空集及其后繼集合的概念來產(chǎn)生。集及其后繼集合的概念來產(chǎn)生。 若若A=A= ，則可產(chǎn)生下列后繼集序列：，則可產(chǎn)生下列后繼集序列： ， + +，( ( + +) )+ + ，( + +) )+ + )+，按按后繼集定義，該序列就是：后繼集定義，該序列就是： ， ， ， 可化簡(jiǎn)為：

2、可化簡(jiǎn)為： ， ， ， ， ， ， , 定義1 給定集合A，其后繼集定義為集合： A+=AA31、自然數(shù)集合（2） 為書寫方便，記空集為為書寫方便，記空集為0 0，并且用，并且用1 1，2 2，3 3，表示序列表示序列 ， ， ， ， ， ， , ，中的其它元素，就得到序列：中的其它元素，就得到序列： 0，1，2，3， 這里的這里的0 0、1 1、2 2、3 3不過是集合的代號(hào)而已，完全可用任何不過是集合的代號(hào)而已，完全可用任何其它的符號(hào)取代。詳細(xì)的說就是：其它的符號(hào)取代。詳細(xì)的說就是： 0 = 0 = 1 = 0 1 = 0+ + = = = 0 2 = 12 = 1+ + = = ， =

3、0，1 3 = 2 3 = 2+ + = = ， ， , = 0，1，2 n+1= n+ = 0，1，2，3，n 如此可得如此可得“自然數(shù)集自然數(shù)集”：N=0N=0，1 1，2 2，3 3， ，它是集合的集合！它是集合的集合！41、自然數(shù)集合（3）自然數(shù)集自然數(shù)集N可用皮亞諾公理來概括：可用皮亞諾公理來概括： 1. 0 N; 2. 對(duì)每個(gè)對(duì)每個(gè)n N,恰有唯一的恰有唯一的n+ N; 3. 不存在不存在n N,使得使得n+=0; 4. 如果如果n+= m+,則則n=m; 5. 如果如果S N;且且0 S;同時(shí)同時(shí),若若n S,則則n+ S；那么；那么S=N。l 皮亞諾公理使自然數(shù)具有如下結(jié)構(gòu)皮亞

4、諾公理使自然數(shù)具有如下結(jié)構(gòu): :l 而排除了而排除了左面結(jié)構(gòu)的左面結(jié)構(gòu)的可能：可能：52、等勢(shì)（1）定義3 當(dāng)且僅當(dāng)集合A、B元素之間存在一一對(duì)應(yīng)，稱集合A與B是等勢(shì)的，或者說集合A、B有相同的基數(shù)，記作AB。集合A的基數(shù)記作KA。定義2 給定兩個(gè)集合P與Q，如果存在雙射f:PQ，則稱集合P和Q的元素之間存在一一對(duì)應(yīng)。 例如，自然數(shù)集例如，自然數(shù)集N與非負(fù)偶數(shù)集與非負(fù)偶數(shù)集M是等勢(shì)的。因?yàn)榇嬖陔p射是等勢(shì)的。因?yàn)榇嬖陔p射 f:NM，f(n)=2n。例1 設(shè)設(shè)R為實(shí)數(shù)集，為實(shí)數(shù)集，S=x|x R 0 x1，證明，證明SR。證：作映射：作映射f:RS,f(x)=(1/ )arctgx+1/2,顯然，

5、顯然，f是雙射。是雙射。62、等勢(shì)（2）證：設(shè)設(shè)集合集合A A S，則，則AA，故，故是自反的。是自反的。 設(shè)設(shè)集合集合A A、B B S，如果，如果AB，則存在雙射，則存在雙射f:AB，因，因而而fC是是B到到A的雙射，所以的雙射，所以BA。故故是對(duì)稱的。是對(duì)稱的。 設(shè)設(shè)集合集合A A、B B、C C S，如果，如果AB，BC,則存在雙射則存在雙射f:AB，g:BC,因而因而g f是是A到到C的雙射，所以的雙射，所以AC。故故是傳遞的。是傳遞的。 綜上述，等勢(shì)關(guān)系綜上述，等勢(shì)關(guān)系是等價(jià)關(guān)系。是等價(jià)關(guān)系。定理2 設(shè)集合S的元素為集合(稱S為集合族)，則S上的等勢(shì)關(guān)系是等價(jià)關(guān)系。 等價(jià)關(guān)系等價(jià)關(guān)

6、系導(dǎo)出集合導(dǎo)出集合S的一個(gè)劃分，這個(gè)劃分的等價(jià)類的一個(gè)劃分，這個(gè)劃分的等價(jià)類叫基數(shù)類。屬于同一基數(shù)類的集合有相同的基數(shù)，稱它叫基數(shù)類。屬于同一基數(shù)類的集合有相同的基數(shù)，稱它們們“同基同基”。72、等勢(shì)（3）定理3 自然數(shù)集N是無限集。證明：只須證集合只須證集合N N與集合與集合N Nm m不等勢(shì)。即證不等勢(shì)。即證不不存在存在N Nm m到到N N的的雙射。雙射。 假設(shè)存在雙射假設(shè)存在雙射f:Nf:Nm mN N， 令令k=1+maxf(0), f(1),k=1+maxf(0), f(1),f(m),f(m)，則，則k k N N。但。但 x x N Nm m，f(x)f(x) k k，所以，所

7、以f f不可能是滿射，更不能是雙射。不可能是滿射，更不能是雙射。這說明不這說明不存在存在N Nm m到到N N的的雙射，從而雙射，從而N N不是有限的。不是有限的。定義4 令令Nm=0,1,2,3,m ，如果集合A與Nm等勢(shì)，則稱A為有限集，否則A稱為無限集。83、可數(shù)集（1） 自然數(shù)集是無限的，但是否所有的無限集都能與自然數(shù)自然數(shù)集是無限的，但是否所有的無限集都能與自然數(shù)集建立一一對(duì)應(yīng)呢？集建立一一對(duì)應(yīng)呢？定 理 4 集 合 A 是 可 數(shù) 集 當(dāng) 且 僅 當(dāng) A 可 寫 成a1,a2,.,an,.。定義5 與自然數(shù)集N等勢(shì)的集合稱為可數(shù)集(可列集)，可數(shù)集的基數(shù)用符號(hào) 表示，讀作阿列夫零。

8、證：若若A可寫為可寫為a1,a2,.,an,.?？勺麟p射可作雙射f:Nf:NA A，f(n)=af(n)=an n，按定義，按定義，A A是可數(shù)集。是可數(shù)集。 反之，若反之，若A A是可數(shù)集，那么，是可數(shù)集，那么，A A與與N N存在一一對(duì)應(yīng)關(guān)系存在一一對(duì)應(yīng)關(guān)系：f:Nf:NA A，可令，可令f(n)=af(n)=an n(n(n N)N)，于是，于是A A可寫成可寫成aa1 1, , a a2 2, ., a, ., an n,. ,. 。93、可數(shù)集（2）定理5 任一無限集 必含有可數(shù)子集。定理6 任一無限集必與它的一個(gè)真子集等勢(shì)。 證：設(shè)設(shè)A A為無限集，可取為無限集，可取a1 A A；

9、因；因A A是無限的，所以是無限的，所以A-A-a1 仍為無限仍為無限集，再取集，再取a2 A A-a1 ；同樣；同樣A-A-a1 ,a2 仍為無限集，再取仍為無限集，再取a3 A A- - a1 ,a2 ；如此繼續(xù)，就得如此繼續(xù)，就得A的一個(gè)可數(shù)子集的一個(gè)可數(shù)子集 a1，a2，a3， 。證：設(shè)設(shè)M為為無限集無限集，按定理5，M含可數(shù)子集可數(shù)子集A=A=aa1 1, a, a2 2, ., .。令。令B=M-AB=M-A，那么，那么M=BM=B A=BA=B aa1 1, a, a2 2, ., .。 記記M=M=B B aa2 2, a, a4 4, ., .。它是。它是M M的一個(gè)真子集。

10、可作雙射的一個(gè)真子集。可作雙射f:Mf:MM M，使，使: :Bxxxfiaafii)(,.3 , 2 , 1)(2 所以所以MM。103、可數(shù)集（3）定理7 可數(shù)集的任一無限子集是可數(shù)的。 （證明從略）定理8 可數(shù)個(gè)可數(shù)集的并是可數(shù)集。 （證明從略）定理9 NN是可數(shù)集(N為自然數(shù)集)。 （證明從略）定理10 全體有理數(shù)的集合是可數(shù)集。 可按下列規(guī)則將全體有理數(shù)排成一列：可按下列規(guī)則將全體有理數(shù)排成一列： 1、正分?jǐn)?shù)按分子分母之和從小到大排列；、正分?jǐn)?shù)按分子分母之和從小到大排列； 2、正分?jǐn)?shù)分子分母之和相同時(shí)，按分子的大小由小到大排列；、正分?jǐn)?shù)分子分母之和相同時(shí)，按分子的大小由小到大排列；

11、3、與正分?jǐn)?shù)分子分母對(duì)應(yīng)相同的負(fù)分?jǐn)?shù)排在相應(yīng)的正分?jǐn)?shù)之后。、與正分?jǐn)?shù)分子分母對(duì)應(yīng)相同的負(fù)分?jǐn)?shù)排在相應(yīng)的正分?jǐn)?shù)之后。 0，1/1，-1/1，1/2，-1/2，2/1，-2/1，1/3，-1/3，3/1，-3/1，1/4，-1/4，2/3，-2/3，3/2，-3/2，4/1，-4/1，.114、不可數(shù)集（1）定理11 實(shí)數(shù)集R是不可數(shù)的。 證明：先證集合先證集合S=x|xS=x|x R R (0 x1)(0 x1) 與與R R等勢(shì)。等勢(shì)。為此，作雙射為此，作雙射f:Sf:SR,R,12/11) 1(212/10121)(xxxxxf其次，用反證法證其次，用反證法證S是不可數(shù)的，從而是不可數(shù)的，從而

12、R不可數(shù)。不可數(shù)。 假設(shè)假設(shè)S S可數(shù)，則可數(shù)，則S S可表示為可表示為SS1 1，S S2 2，.，其中，其中S Si i 為為(0,1)(0,1)內(nèi)的內(nèi)的任一實(shí)數(shù)，可表示為任一實(shí)數(shù)，可表示為0.y0.y1 1 y y2 2 y y3 3, ,其中其中y yi i 0,1,2,0,1,2,9,9?？稍O(shè)可設(shè) S S1 1= = 0.a 0.a11 11 a a12 12 a a1313a a1n1n ； . .S S2 2= = 0.a 0.a21 21 a a22 22 a a2323a a2n2n S S3 3= = 0.a 0.a31 31 a a32 32 a a3333a a3n3n

13、 ； 令令r=0.br=0.b1 1b b2 2b b3 3，其中，其中b bi i=1(a=1(aiiii 1)1)或或b bi i=2(a=2(aiiii=1)=1)，i=1,2,3,i=1,2,3,顯然顯然r r S S，但由上所設(shè)，這個(gè)，但由上所設(shè)，這個(gè)r r與所有的與所有的S Si i都不同，因而都不同，因而r r S S，與所，與所設(shè)矛盾。故設(shè)矛盾。故S S是不可數(shù)的，所以是不可數(shù)的，所以R R也是不可數(shù)的。也是不可數(shù)的。124、不可數(shù)集（2） 將實(shí)數(shù)集R的基數(shù)記為 ，稱為連續(xù)統(tǒng)的勢(shì)。直觀上看，自然數(shù)集N是實(shí)數(shù)集R的子集，那么， 。135、基數(shù)的比較（1）定義6 設(shè)A、B為集合，如

14、果存在A到B的入射，則稱A的基數(shù)小于或等于B的基數(shù)，記作KAKB。如果存在A到B的入射，但不存在雙射，則稱A的基數(shù)小于B的基數(shù)，記作KAKB。 無限集合也有無限集合也有“大小大小”之分，下面的定義提供了無之分，下面的定義提供了無限集合比較的基礎(chǔ)。限集合比較的基礎(chǔ)。定理12 (Zermelo定理) 設(shè)A、B為任意兩個(gè)集合，則下列三者恰有一個(gè)成立： (1) KAKB；(2) KBKA；(3) KA=KB。定理13 (Bernstein定理)設(shè)A、B為集合,如果KAKB,KBKA，則KA=KB。 按定義按定義6 6和定理和定理13,13,如果能作出如果能作出A A到到B B和和B B到到A A兩個(gè)入

15、射兩個(gè)入射, ,就可就可證明證明集集合合A A與與B B的基數(shù)相同。這比直接作的基數(shù)相同。這比直接作A A到到B B的雙射來證明要容易些。的雙射來證明要容易些。145、基數(shù)的比較（2）定理14 設(shè)A為有限集合，KA 。證明：設(shè)設(shè)KA=n，則A0，1，2，n-1。可作入射 f： 0,1,2,n-1N ， f(x)=x 所以，KA KN。 顯然A到N不可能存在雙射，故KA KN，所以KA KN，即 KA 。 作入射g：N0，1，g(n)=1/(n+1)?？芍?。 因0，1是不可數(shù)集，所以N與0,1之間不能建立一一對(duì)應(yīng)，故 155、基數(shù)的比較（3）定理15 (Cantor定理) 設(shè)M為集合，則KMK

16、(M)。(證明從略)l定理定理15說明，沒有最大的集合，也沒有最大的基數(shù)。說明，沒有最大的集合，也沒有最大的基數(shù)。lCantor(1845-1918)早在早在100多年前提出一個(gè)猜想：多年前提出一個(gè)猜想： 是大于是大于 的最小基數(shù)。即不存在任何集合的最小基數(shù)。即不存在任何集合X，它的基數(shù)，它的基數(shù)KX能使能使 KX 成立。這個(gè)問題是近百年來數(shù)理邏成立。這個(gè)問題是近百年來數(shù)理邏輯的中心問題之一，也是集合論中最難的問題之一。它至輯的中心問題之一，也是集合論中最難的問題之一。它至今仍然沒有得到證明。今仍然沒有得到證明。165、課堂練習(xí)練習(xí)1 證明 0，1與（0，1）表示的集合有相同的基數(shù)。證： 作入射：作入射： f:(0,1)f:(0,1)0,1,f(x)=x0,1,f(x)=x g:0,1g:0,1(0,1)(0,1)，g(x)=g(x)=( (x+1)/4x+1)/4 根據(jù)根據(jù)定義定義6 6和和定理定理1313, 0, 0，11與（與（0 0，1 1）表示的集合有）表示的集合有相同的基數(shù)。相同的基數(shù)。練習(xí)2 （P173，1）證明證明(0,1(0,1與與0