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

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

2、{?}， ??{?}?{??{?}} ，…… 可化簡為： ?， {?}， {?，{?}}，{?，{?}，{?,{?}}}……,定義1 給定集合A，其后繼集定義為集合： A+=A?{A},,,,,3,1、自然數(shù)集合（2）,為書寫方便，記空集為0，并且用1，2，3，…表示序列 ?， {?}， {?，{?}}，{?，{?}，{?,{?}}，……中的其它元素，就得

3、到序列： 0，1，2，3，……,這里的0、1、2、3……不過是集合的代號而已，完全可用任何其它的符號取代。詳細(xì)的說就是： 0 = ? 1 = 0+ = {?} = {0} 2 = 1+ = {?，{?}} = {0，1} 3 = 2+ = {?，{?}，{?,{?}} } = {0，1，2} …… n+1= n+ = {0，1，2，3，…，n}

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

5、面結(jié)構(gòu)的可能：,,,,,5,2、等勢（1）,定義3 當(dāng)且僅當(dāng)集合A、B元素之間存在一一對應(yīng)，稱集合A與B是等勢的，或者說集合A、B有相同的基數(shù)，記作A~B。集合A的基數(shù)記作K[A]。,定義2 給定兩個集合P與Q，如果存在雙射f:P?Q，則稱集合P和Q的元素之間存在一一對應(yīng)。,例如，自然數(shù)集N與非負(fù)偶數(shù)集M是等勢的。因?yàn)榇嬖陔p射 f:N?M，f(n)=2n。,例1 設(shè)R為實(shí)數(shù)集，S={x|x?R

6、?0<x<1}，證明S~R。證：作映射f:R?S,f(x)=(1/?)arctgx+1/2,顯然，f是雙射。,,,,,6,2、等勢（2）,證：設(shè)集合A?S，則A~A，故~是自反的。 設(shè)集合A、B?S，如果A~B，則存在雙射f:A?B，因而fC是B到A的雙射，所以B~A。故~是對稱的。 設(shè)集合A、B、C?S，如果A~B，B~C,則存在雙射f:A?B，g:B?C,因而g?f是A到C的雙射，所以A~C。故~是傳遞的。

7、 綜上述，等勢關(guān)系~是等價關(guān)系。,定理2 設(shè)集合S的元素為集合(稱S為集合族)，則S上的等勢關(guān)系是等價關(guān)系。,等價關(guān)系~導(dǎo)出集合S的一個劃分，這個劃分的等價類叫基數(shù)類。屬于同一基數(shù)類的集合有相同的基數(shù)，稱它們“同基”。,,,,,7,2、等勢（3）,定理3 自然數(shù)集N是無限集。證明：只須證集合N與集合Nm不等勢。即證不存在Nm到N的雙射。 假設(shè)存在雙射f:Nm?N， 令k=1+max{f(0), f(1),…,f(m)

8、}，則k?N。但 ?x?Nm，f(x)?k，所以f不可能是滿射，更不能是雙射。這說明不存在Nm到N的雙射，從而N不是有限的。,定義4 令Nm={0,1,2,3,…,m} ，如果集合A與Nm等勢，則稱A為有限集，否則A稱為無限集。,,,,,8,3、可數(shù)集（1）,自然數(shù)集是無限的，但是否所有的無限集都能與自然數(shù)集建立一一對應(yīng)呢？,,,,,定理4 集合A是可數(shù)集當(dāng)且僅當(dāng)A可寫成{a1,a2,...,an,...}。,定義5 與自然數(shù)集N

9、等勢的集合稱為可數(shù)集(可列集)，可數(shù)集的基數(shù)用符號 表示，讀作阿列夫零。,證：若A可寫為{a1,a2,...,an,...}。可作雙射f:N?A，f(n)=an，按定義，A是可數(shù)集。 反之，若A是可數(shù)集，那么，A與N存在一一對應(yīng)關(guān)系：f:N?A，可令f(n)=an(n?N)，于是A可寫成{a1, a2, ..., an,... }。,,,,,9,3、可數(shù)集（2）,定理5 任一無限集 必含有可數(shù)子集。,定理6 任一無限集必與它

10、的一個真子集等勢。,證：設(shè)A為無限集，可取a1?A；因A是無限的，所以A-{a1}仍為無限集，再取a2?A-{a1}；同樣A-{a1 ,a2}仍為無限集，再取a3?A-{a1 ,a2}；……如此繼續(xù)，就得A的一個可數(shù)子集{a1，a2，a3，…}。,證：設(shè)M為無限集，按定理5，M含可數(shù)子集A={a1, a2, ...}。令B=M-A，那么M=B?A=B?{a1, a2, ...}。 記M’=B?{a2, a4, ...}。它是M的一

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

12、 3、與正分?jǐn)?shù)分子分母對應(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，...,,,,,11,4、不可數(shù)集（1）,定理11 實(shí)數(shù)集R是不可數(shù)的。,證明：先證集合S={x|x?R?(0<x<1)}與R等勢。為此，作雙射f:S?R,,其次，用反證法證S是不可數(shù)的，從而

13、R不可數(shù)。 假設(shè)S可數(shù)，則S可表示為{S1，S2，...}，其中Si 為(0,1)內(nèi)的任一實(shí)數(shù)，可表示為0.y1 y2 y3…,其中yi ?{0,1,2,…,9}?？稍O(shè) S1= 0.a11 a12 a13…a1n… ； .S2= 0.a21 a22 a23…a2n… S3= 0.a31 a32 a33…a3n… ； …… 令r=0.b1b2b3…，其中bi=1(aii?1)或bi=2(aii=1)，i=1,2,3,

14、…顯然r?S，但由上所設(shè)，這個r與所有的Si都不同，因而r?S，與所設(shè)矛盾。故S是不可數(shù)的，所以R也是不可數(shù)的。,,,,,12,4、不可數(shù)集（2）,將實(shí)數(shù)集R的基數(shù)記為 ，稱為連續(xù)統(tǒng)的勢。直觀上看，自然數(shù)集N是實(shí)數(shù)集R的子集，那么， 。,,,,,13,5、基數(shù)的比較（1）,定義6 設(shè)A、B為集合，如果存在A到B的入射，則稱A的基數(shù)小于或等于B的基數(shù)，記作K[A]?K[B]。如果存在A到B的入射，但不存在雙射，則稱A的基數(shù)小

15、于B的基數(shù)，記作K[A]<K[B]。,無限集合也有“大小”之分，下面的定義提供了無限集合比較的基礎(chǔ)。,定理12 (Zermelo定理) 設(shè)A、B為任意兩個集合，則下列三者恰有一個成立： (1) K[A]<K[B]；(2) K[B]<K[A]；(3) K[A]=K[B]。,定理13 (Bernstein定理)設(shè)A、B為集合,如果K[A]?K[B],K[B]?K[A]，則K[A]=K[B]。,按定義6和定理1

16、3,如果能作出A到B和B到A兩個入射,就可證明集合A與B的基數(shù)相同。這比直接作A到B的雙射來證明要容易些。,,,,,14,5、基數(shù)的比較（2）,定理14 設(shè)A為有限集合，K[A]< < 。,證明：設(shè)K[A]=n，則A~{0，1，2，…，n-1}?？勺魅肷?f： {0,1,2,…,n-1}?N ， f(x)=x 所以，K[A] ? K[N]。 顯然A到N不可能存在雙射，故K[A]

17、? K[N]，所以K[A] < K[N]，即 K[A] < 。 作入射g：N?[0，1]，g(n)=1/(n+1)?？芍?? 。 因[0，1]是不可數(shù)集，所以N與[0,1]之間不能建立一一對應(yīng)，故 <,,,,,15,5、基數(shù)的比較（3）,定理15 (Cantor定理) 設(shè)M為集合，則K[M]<K[?(M)]。(證明從略),定理15說明，沒有最大的集合，也沒有最大的

18、基數(shù)。Cantor(1845-1918)早在100多年前提出一個猜想： 是大于 的最小基數(shù)。即不存在任何集合X，它的基數(shù)K[X]能使 < K[X]< 成立。這個問題是近百年來數(shù)理邏輯的中心問題之一，也是集合論中最難的問題之一。它至今仍然沒有得到證明。,,,,,16,5、課堂練習(xí),練習(xí)1 證明 [0，1]與（0，1）表示的集合有相同的基數(shù)。,證： 作入射： f:(0,1)?[0,1

19、],f(x)=x g:[0,1]?(0,1)，g(x)=(x+1)/4 根據(jù)定義6和定理13, [0，1]與（0，1）表示的集合有相同的基數(shù)。,練習(xí)2 （P173，1）證明(0,1]與[0,1)等勢。,證：作入射f: (0,1]?[0,1),f(x)=(1-x)/2 g: [0,1)?(0,1],g(x)=1-x根據(jù)定義6和定理13, (0，1]與[0，1）等勢。注： g(x)=1-x是(0,1]到