離散數(shù)學第四章

1、有限集和無限集,有限集合元素的個數(shù)稱為該集合的基數(shù)；滿足包含排斥原理。無限集合元素無限多，如：自然數(shù)集合N、整數(shù)集I、實數(shù)集R等。問題：對于這樣的集合有沒有基數(shù)呢？如果有，基數(shù)是多少？無限集合之間有無大小的差別? 本章主要借助于函數(shù)討論集合的所謂“大小”問題。這里用到自然數(shù)集合這個重要的概念討論無限集。,基本概念,定義4.1 一個集合S與集合Nn={0,1,2，…n-1}，如存在一一對應(yīng)函數(shù) f : Nn→S，則稱S是

2、有限集合，并稱其有基數(shù)n，如果S不是有限集合，則稱為無限集合。說明：由集合的元素個數(shù)來定義；由于量變引起的質(zhì)變；它們中的一種性質(zhì)都不能隨意擴展到另一個集合中。,基本概念,定義4.2 集合A和集合B的元素間，如果存在一一對應(yīng)的關(guān)系，則說A和B是等勢（Cardinality）的，記作A~B說明：對有限集來說，兩集合等勢即說明兩個集合的元素的個數(shù)相同；集合的勢：Cardinality of Sets,Hilbert旅館,問

3、題：一旅店有無窮多個房間，各房間編號依次為：#1， #2， #3，……現(xiàn)所有房間已住滿了人，這時來了一位新客人要求住店，怎么安排？,客 滿,Hilbert旅館,解決方法：店主人把#1房的客人移到#2房，把#2房的客人移到#3房，依此類推，新客人就住進了已騰空的#1房間； 接著，又來了第二位新客人，旅店主也照此辦理，使第二位客人得到落實。緊接著，來了一個有無限多個游客的旅游團要求定住房間，怎么辦 ？店主人把#1房的客人移

4、到#2房，把#2房的客人移到#4房，#3房的客人移到#6房，等等，所有奇數(shù)號的房間全部騰空了，新的無限多個客人就全住進了旅店。,,緊接著發(fā)生了更為嚴重的情況，來了無窮多個具有無窮多名游客的旅游團，怎么辦？第一個旅游團客人按如下房間編號住第二個旅游團客人住的房間編號為 接著是,,這樣不僅安排了無窮多個旅游團的住宿，而且還空出了很多房間！無限多個房間可住無窮多個具有無窮多個游客的旅游團！,對于一個無窮集合，向其中添加有限個元

5、素，甚至“無窮多個”元素得到的新集合，其勢不變,一個集合A，若真子集B ：B?A，B與A等勢，則A一定是無限集,,Hilbert旅館的內(nèi)涵如果把自然數(shù)集合中的元素數(shù)量記為z， 那么z不管加上多大的數(shù)，乘以多少，它始終是一個無窮，不會變大或變小。問題：自然數(shù)和平方數(shù)誰要更多。 用普通人的眼光來看，前10個數(shù)字中不過4和9兩個數(shù)， 前100個數(shù)中也不過10個；再往后， 平方數(shù)在自然數(shù)中所占的比例越來越小；但是從另一個角度看，每一個

6、自然數(shù)都對應(yīng)著一個平方數(shù)；所以，自然數(shù)和平方數(shù)是一樣多的， 這 “一一對應(yīng)” 的規(guī)則也就是判斷集合是否一樣大的標準。,,任何一個有限集合不能與其真子集等勢。另一種有限集、無限集的定義方法；定義：如果存在一一對應(yīng)的f: S→S，使得f(S)?S，即f(S)是S的真子集，則S是無限集合，否則S是有限集合。,,定理4.1 自然數(shù)集N是無限集。證明：設(shè)函數(shù)f: N→N，定義為f(x)=2x，顯然f是一一對應(yīng)，而且f(N)?N ，因此

7、N是無限集。定理4.2 常數(shù)集R是無限集。證明：設(shè)函數(shù)f: R→R，為,顯然f(x)是一一對應(yīng)的，而且顯然有f(R)?R，因此R是無限的。,,例1：證明 N={0,1,2,3,4,…...} 與下列集合等勢 A={0,2,4,6,8,…...} B={1,3,5,7,9,…...} C={100,10,102,103,104,,…...} 證： f:N?A，f

8、(x)=2x g:N?B， g(x)=2x+1 h:N?C， h(x)=10x 是雙射， 故N與A、B、C等勢可見：無限集合與其真子集等勢。,,對于無限集合，可用下面的例子說明自然數(shù)集合N={0,1,2,...}與其子集S={1,3,…}均為無限集，且N~S；可得無限集的一個特性：S?N及S~N；即表明S是N的一個真子集，并且同時S與N等勢；這種特性在有限集是

9、不可能存在的。,,集合間的等勢關(guān)系“~”是個等價關(guān)系證明：令S是個集合族(即“所有集合構(gòu)成的集合”)，在S上的等勢關(guān)系~，滿足： ⑴自反性：因為任何集合A，存在雙射 IA:A?A,因此A~A ⑵對稱性：任何集合A,B，若A~B，有雙射 f:A?B，又有雙射f -1:B?A，所以B~A。,,⑶傳遞性：任何集合A、B、C，若A~B，且B~C，則有雙射f:A?B，和雙射g:B?C，由函數(shù)的復合得雙射： g?f:A?C，所

10、以A~C。 所以~是等價關(guān)系。 按照等勢關(guān)系“~”對集合族S，進行劃分，得到商集S/~，進而得到基數(shù)類的概念。,,定理4.7 一個集合為無限集，則它必會有與它等勢的真子集。說明：1.無限集的另一個定義；2.該無限集減去這個真子集后得到的差集，可以是無限集，可以是有限集。設(shè)M是一個無限集，現(xiàn)在需要證明：必存在另一個無限集M’，M? M’且M~ M’； 因為M不一定是可列集，因此才要這樣證明，即M=一個可列集

11、?另一個集合。,,證明過程：構(gòu)造一個集合M，先從M中任取一個元素m1，這樣剩余部分也是一個集合M-{m1}，并且是無限集；再從此無限集M-{m1}中任取一個元素m2，剩余部分為M-{m1，m2}也是一個無限集；如此繼續(xù)，可取出m3,m4,m5,…無限多個元素，則可得到另一個集合M1={m1,m2,…}；令M2=M-M1，即M中除去M1后得到的集合，則M=M1∪ M2，做另一集合M’={m2,m3,…} ∪M2，顯然M?M’

12、且M’~M，因此存在如下一一對應(yīng)的關(guān)系：對于M的每個mi對應(yīng)mi+1，對于M中的每個m∈ M2，對應(yīng)M’中的m。,,推論：一集合為無限集的充分必要條件是它包含有與它等勢的真子集。證明：必要條件已經(jīng)在前面證明，下面證明其充分條件。反證法：設(shè)一集合M含有與其等勢的真子集M’，若M’為有限集，設(shè)其元素個數(shù)為n，即|M|=n，則此時必有n>m；但此時M與M’間由于元素個數(shù)不同而無法建立一一對應(yīng)的關(guān)系而產(chǎn)生矛盾。,鴿洞原理,,有

13、限集和無限集的重要定義定義4.5 一集合存在與其等勢的真子集，則稱為無限集，否則稱為有限集。無限子集可做進一步劃分：可列集和不可列集。定義4.6 與自然數(shù)集N等勢的集合稱為可列集。能和自然數(shù)集合N建立一一對應(yīng)關(guān)系的集合是可列集；可排成一列，能一個一個數(shù)下來的集合；也稱為可數(shù)集。,,定理4.8 無限集必包含可列集。證明：設(shè)一無限集A，由A中取出一個元素a0，再從其剩余部分取出一個元素a1，如此繼續(xù)進行，可得一個序列：

14、a0，a1，a2.。。。由此可得一個無限集A’={a0,a1,a2,...}集合A’為可列集,,定理4.9 可列集的無限子集仍為一可列集。證明：設(shè)有一可列集A={a0,a1,a2,...}，依次順序取一個任意的無限集A’={am0,am1,am2,...}，A’與N一一對應(yīng)；故A’為可列集；由此可知，可列集是無限集中最小的集合。,,,,定理4.10 整數(shù)集I是可列集。證明：整數(shù)集合Ｉ與Ｎ是等勢的。 將集合Ｉ元素

15、重排，寫成 Ｎ＝｛0， 1，　2，　3，　4，　5，…｝Ｉ＝｛0，＋1, －1，＋2, －2， +3 －3，…｝　　　f(i)＝ 是Ｉ到Ｎ的雙射。 因此Ｉ是可列集。,,定理4.11 有理數(shù)集Q是可列集證明：一切有理數(shù)均呈的形式，現(xiàn)將所有按下列次序排列，正分數(shù)按其分子分母之和的大小

16、順序排列：從小到大正分數(shù)的分子分母之和相同者按照分子大小順序排列：從大到小與正分數(shù)具有相同形式的負分數(shù)拍于正分數(shù)之后按照上述規(guī)則可以得到一個序列此序列可以跟自然數(shù)一一對應(yīng)，因此是可列集。,,,直觀上看，有理數(shù)比自然數(shù)多得多，但本質(zhì)上它們卻 “一樣多”！,“全體正整數(shù)的集合和全體有理數(shù)的集合等勢”是在數(shù)學上很重要的一個例子，說明一個實數(shù)中的稠密集可以和一個離散集等勢（稠密：在任意兩個元素之間存在第三個元素）,,因為每個有理數(shù)都

17、可以寫成一個分數(shù)形式如下：可以從0/1開始按照箭頭指定次序排列Q中元素(如果這個有理數(shù)在前面出現(xiàn)，就跳過去)，所以Q是可數(shù)集。另外 I×I~N如右圖所示。同理可證 N×N~N,,,之前出現(xiàn)過了,,定理4.12 實數(shù)集R不是可列集。思路：首先證明R~(0,1)，然后證明(0,1)不是可列集。證明：構(gòu)造函數(shù)f: (0,1) ? R f(x)=tg(πx-π/2

18、) 顯然 f是雙射，所以R~(0,1).,,實數(shù)軸上的(0,1)區(qū)間中的實數(shù)是不可數(shù)的。證明：假設(shè)(0,1)是可數(shù)的，則可以將它的元素寫成如下序列形式：{x1,x2,x3,...} ，其中 xi =0.ai1ai2ai3 …… i=1,2,3,….. 即 0＜ xi＜1 aik∈{0,1,2,3,4,5,6,7,8,9} k=1,2,3,4,…令 x1 =0.a11a12a13a14…..

19、. x2 =0.a21a22a23a24…... x3 =0.a31a32a33a34…... ………... xn =0.an1an2an3an4…... ..……..,,構(gòu)造一個數(shù)b=0.b1b2b3b4…bn……，其中 ： b1≠a11 b2 ≠ a22 b3≠a33… bn≠ ann... 于是

20、 b≠x1, b≠ x2, b≠ x3 ... b ≠ xn … 因此： b?(0,1)但是b這樣的形式應(yīng)該是屬于集合(0,1)的，因此產(chǎn)生矛盾，所以(0,1)是不可數(shù)的。,,說明：這種方法稱為：康托對角線法；對角線法并非康托爾關(guān)于實數(shù)不可數(shù)的第一個證明，而是發(fā)表在他第一個證明的三年后；他的第一個證明既未用到十進制展開，也未用到任何其它數(shù)字系統(tǒng)；自從該技巧第一次使用以

21、來，在很大范圍內(nèi)的證明中都用到了類似的證明構(gòu)造方法。,,由前面這些定理可知：實數(shù)集比可列集要大；可列集的基數(shù)可表示為?0 （Aleph 0，阿列夫零）； 實數(shù)集的基數(shù)用?1或c表示，稱作連續(xù)統(tǒng)的勢。因此：無限集也有大小，最小的無限集是可列集，其次是實數(shù)集；對于任何一個無限集，總存在一個基數(shù)大于這個集合的集合，比如這個集合的冪集；可列集的冪集和實數(shù)集等勢。,,自然數(shù) N 的冪集 (2N) 是不可數(shù)的[0,1) 之間的小

22、數(shù)可以用十進制表示，也可以用二進制表示，表示形式是唯一的，0.5 D = 0.1 B，0.25 D = 0.01 B，....任意一個小于1 的非負小數(shù)，取其二進制形式，比如 0.1101001，如果將小數(shù)點后第 i 位對應(yīng)的 0/1 看成是自然數(shù) i 在某個集合中的無/有，那么0.1101001就對應(yīng)自然數(shù)的一個子集 {1, 2, 4, 7}；所以，任一個小數(shù)可以對應(yīng)一個自然數(shù)的子集，當然，自然數(shù)的一個子集，也可以很容易寫出一個小

23、數(shù)： [0,1) 之間的小數(shù)與自然數(shù) N 的所有子集的一一對應(yīng)關(guān)系；自然數(shù)的冪集，也就是自然數(shù)所有的子集形成的集合，它的基數(shù)，或是勢，與 [0,1) 之間的實數(shù)相等，也有所有的實數(shù)的勢相等；,連續(xù)統(tǒng),定義：與區(qū)間（0，1)對等的集合就叫做連續(xù)統(tǒng)。對等就是找到一個映射，使得他們之間的元素滿足一一映射。在集合論中，連續(xù)統(tǒng)是一個擁有多于一個元素的線性序集，且滿足如下性質(zhì)（具此性質(zhì)的序稱為“稠密無洞”）：稠密：在任意兩個元素之間存在第三個

24、元素無洞：有上界的非空子集一定有上確界，實數(shù)集即為連續(xù)統(tǒng)的例子，實際上它是連續(xù)統(tǒng)的原型。連續(xù)統(tǒng)假設(shè)（Continuum Hypothesis，常記作CH）無窮集合中，除了整數(shù)集的基數(shù)，實數(shù)集的基數(shù)是最小的；即?0和?1之間不存在其它?x,,康拓的一些結(jié)論：1.任何一個集合A，它的冪集ρ(A)的一定比A的基數(shù)大（已經(jīng)證明）。2. ?0和?1之間沒有其他基數(shù)存在 （連續(xù)統(tǒng)假設(shè)）1874年格奧爾格·康托爾猜測；又被

25、稱為希爾伯特第一問題，在1900年第二屆國際數(shù)學家大會上，大衛(wèi)·希爾伯特把康托爾的連續(xù)統(tǒng)假設(shè)列入20世紀有待解決的23個重要數(shù)學問題之首；1938年哥德爾證明了連續(xù)統(tǒng)假設(shè)和世界公認的ZFC公理系統(tǒng)（帶有選擇公理的集合論之公理系統(tǒng)）不矛盾；1963年美國數(shù)學家科亨證明連續(xù)假設(shè)和ZFC公理系統(tǒng)彼此獨立；連續(xù)統(tǒng)假設(shè)不能在ZFC公理系統(tǒng)內(nèi)證明其正確性與否。,,判定連續(xù)統(tǒng)假設(shè)對數(shù)學的重大意義數(shù)學基礎(chǔ)中最主要的問題就是如何處理自然

26、數(shù)和實數(shù)的關(guān)系，即如何用離散的方法來構(gòu)造連續(xù)統(tǒng)；自從古希臘人發(fā)現(xiàn)這個難題以來，至今它仍未得到完全解決，到目前為止，我們對連續(xù)統(tǒng)還所知甚少；數(shù)學歸納法是數(shù)學的基本方法，它是建立在自然數(shù)基礎(chǔ)上的，對連續(xù)統(tǒng)假設(shè)的否定性證明正好說明：人們可以用這種方法去無限逼近連續(xù)統(tǒng)，但卻永遠也不能達到其盡頭。,有限和無限的區(qū)別及聯(lián)系,區(qū)別：無限集中，部分可以等于全體（無限的本質(zhì)），有限情況下，部分小于全體；無限集中，有限時成立的許多命題不再成立，如加

27、法的結(jié)合律：聯(lián)系：數(shù)學歸納法：通過有限證明無限；極限：通過有限描述無限 ；無限可由有限構(gòu)成，無限多個有限?無限；有限也由無限構(gòu)成：有限的長度由無限個點組成。,,,,集合基數(shù)的判別定理：無限集減去一個有限子集，或添上有限個元素，基數(shù)不變；有限個或可列個可列集的并集可列；可列個有限集的并集至多可列；無限集并一個可列集，基數(shù)不變；不可列無限集，減去一個可列子集，基數(shù)不變；有限個或可列個基數(shù)為?的集合的并，基數(shù)為?。,

28、,補充內(nèi)容： 基數(shù)的比較前邊基數(shù)相等與否的問題，下面討論諸如?和?0哪個大的問題，即所謂無限集合的“次序”問題。在比較兩個集合基數(shù)相等時，要看這兩個集合之間是否存在雙射， 但是找雙射往往是個麻煩的事, 為了解決這個問題，提出下面定理：,,定理.1 如果集合A到B存在內(nèi)射函數(shù)，則K[A]≤K[B]。K[A]表示A的基數(shù)。定理.2　(Zermelo定理) A和B是任何集合，則以下三條之一必有一個成立： a.) K[A

29、]<K[B]. b.) K[B]<K[A] c.) K[A]=K[B].定理.3 (Contor- Schroder- Bernstein定理) A和B是任何集合， 如果 K[A]≤K[B] 且 K[B]≤K[A] 則K[A]=K[B]。定理.4 設(shè)A是有限集合，則K[A]< ?0 < ?定理.5 設(shè)A是無限集合，則?0≤ K[A],可數(shù)集合是“最小的”無限集合,,可以用這些定理對集合基

30、數(shù)進行比較。例. 證明[0,1]與(0,1)等勢。證明：構(gòu)造兩個內(nèi)射函數(shù): f:(0,1)?[0,1] f(x)=x g:[0,1]?(0,1) g(x)=x/2+ 1/4 因為f和g都是單射的，所以有： K[(0,1)]≤K[[0,1]] 且 K[[0,1]]≤K[(0,1)] 根據(jù)定理3，可得 K[[0,1]]=K[(0,1)],選擇公理（Axiom of Choice

31、）,選擇公理：設(shè)C為一個由非空集合所組成的集合。那么可以從每一個在C中的集合中，都選擇一個元素來組成一個新的集合。,選擇公理的意思是：如果有一堆非空集合，那么我們可以從每個集合里各取出一個元素。,,說明怎么從集合中選擇一個元素？考慮實數(shù)的所有非空子集，怎么從每個非空子集中選一個元素？目前為止，沒有人能找到一個恰當?shù)膄(s)作為選擇函數(shù)，并且，模型論(model theory)中有一些頗具說服力的論證表明，這樣的f(s)是不可能找到

32、的。接受了選擇公理，就意味著我們假定了選擇函數(shù)f(s)始終存在，即使我們沒有辦法給出任何具體的構(gòu)造和例子。哥德爾和寇恩證明了，無論接受選擇公理與否，都不會導致矛盾，只是身處不同的『數(shù)學世界』而已。,選擇公理（Axiom of Choice）,不少數(shù)學家曾嘗試證明選擇公理，他們希望用最基本的工具來作證明，但往往在這些證明中，都用了一些并不基本的理論，例如：「良序原理」（Well-ordering Principle）及「佐恩引理」（Z

33、orn's Lemma），良序原理：所有集合也是良序集。換句話說，對每一個集合來說，都存在一種排序方法，使得它的所有子集也有極小元素。 佐恩引理：若一偏序集是歸納序集，那么，它必然存在最大元素。換句話說，如果在一個偏序集的每一條鏈中都存在著上界，這偏序集必存在最大元素。 事實上，「選擇公理」、「良序原理」及「佐恩引理」都是等價的命題。,,要在數(shù)學上證明或否證「選擇公理」并非易事，對於這條公理不只是接納和不接納的問題，如果放

34、棄這條公理，有很多美好且乎合「常理」的結(jié)果會同時被放棄；但它實際上又與很多「常理」大不協(xié)調(diào)。其中一個為人熟識的不合乎常理的結(jié)果是「巴拿赫─塔斯基悖論」（Banach-Tarski Paradox），或稱「分球問題」。這個誖論可以說是違反了物理學定律，因為這個誖論說可以把一個單位球體（半徑為1）分成有限份，最少可分成五份，然後透過一些剛體運動，即旋轉(zhuǎn)和平移，再重新組合，不過在組合後，竟然成為兩個單位球體，也即是體積增加了一倍，而這個誖論

35、的證明是必須利用到「選擇公理」的。也就是說，如果我們選擇接納「選擇公理」，則「巴拿赫─塔斯基誖論」便是一條定理，但現(xiàn)實中有這個可能嗎？這其實也是牽涉另一個數(shù)學概念──可測集合（Measurable Set）?！赴湍煤诈に够Ｕ摗贡闶谴嬖诓豢蓽y集合的結(jié)果。如果我們接納「選擇公理」，則我們必須接納不可測集合。若我們不接納「選擇公理」，則可設(shè)所有集合皆是「勒貝格可測的」（Lebesgue Measurable），而這個假設(shè)也可能是較合乎常