無窮集合以及基數(shù)

1、關(guān)于無窮集合及基數(shù)第一張，PPT共二十九頁，創(chuàng)作于2022年6月1第4節(jié) 無窮集合及其基數(shù)可數(shù)集不可數(shù)集基數(shù)及其比較康托-伯恩斯坦定理悖論與公理化集合論主要內(nèi)容：第二張，PPT共二十九頁，創(chuàng)作于2022年6月2 集合的基數(shù)亦稱作集合的勢。 粗略的說，就是一個(gè)集合的“規(guī)?！?，它的“大小”，或者更確切地說，它有多少個(gè)元素。 通俗的說，集合的勢是量度集合所含元素多少的量。集合的勢越大，所含的元素越多。 很明顯，如果集合中只有有限個(gè)元素，我們只要數(shù)一數(shù)它有多少個(gè)可以了，這時(shí)集合的基數(shù)就是其中所含元素的個(gè)數(shù)。 什么是集合的基數(shù)？ 值得注意的是無限集，它所含的元素有無窮多個(gè)， 這時(shí)怎樣去數(shù)？ 為了解決這個(gè)

2、問題，我們首先從伽利略“悖論”說起。 第三張，PPT共二十九頁，創(chuàng)作于2022年6月3 1638年意大利的天文學(xué)家伽利略發(fā)現(xiàn)了下面的問題： N+=1,2,3,n,與N(2)=1,4,9,n2,這兩個(gè)集合，哪一個(gè)的元素更多一些？伽利略“悖論” 一方面，凡是N(2)的元素都是N+的元素，也就是說N(2)N+，而且由于2，3，5等元素都不在N(2)中，所以N(2)N+。這樣看來，N+中的元素要比N(2)中的元素要多。第四張，PPT共二十九頁，創(chuàng)作于2022年6月4 但另一方面，對于N+中的每個(gè)元素都可以在N(2)中找到一個(gè)元素與之對應(yīng)，這樣看來，N(2)中的元素不比N+中的元素要少。 那么到底N+與

3、N(2)中所含元素的個(gè)數(shù)是否一樣呢？如果是，那么就有 部分=整體？ 然而按照傳統(tǒng)，部分怎么能等于全體呢？這就是伽利略“悖論”，它不僅困惑了伽利略，還使許多數(shù)學(xué)家亦束手無策。 伽利略“悖論”第五張，PPT共二十九頁，創(chuàng)作于2022年6月5 1874年，Cantor注意到伽利略”悖論”。 在1874年到1897年間完全解決了這個(gè)問題。 Cantor詳細(xì)地分析了斷定有限集合的元素多少的方法，即采用數(shù)數(shù)的方法。他認(rèn)為“數(shù)數(shù)的過程”就是作“一一對應(yīng)的過程”。 Cantor認(rèn)為這種“一一對應(yīng)”的方法不僅適用于有限集，也適用于無限集。 他牢牢地抓住這個(gè)原則，拋棄了部分必定小于全體的教條，經(jīng)歷了大約23年之后

4、，他才沖破了傳統(tǒng)觀念的束縛，革命性的解決了伽利略“悖論”。 Cantor認(rèn)為在N+與N(2)之間存在著一一對應(yīng)(即雙射)，因此N+與N(2)的元素個(gè)數(shù)是相等的。 一一對應(yīng)與可數(shù)集第六張，PPT共二十九頁，創(chuàng)作于2022年6月6 定義4.1 設(shè)A，B是集合，若存在著從A到B的雙射，就稱A和B等勢(或?qū)Φ?，記作AB。 Cantor把自然數(shù)集N+稱為可數(shù)集(或可列集)，這是因?yàn)樗脑乜梢砸粋€(gè)一個(gè)的數(shù)出來。 凡是與自然數(shù)集N+等勢的集合，它們的元素通過一一對應(yīng)關(guān)系，也都可以一個(gè)一個(gè)的數(shù)出來，因此：一一對應(yīng)與可數(shù)集 定義4.2 凡是與自然數(shù)集N+等勢的集合，稱為可數(shù)集(或可列集)。 第七張，PPT共

5、二十九頁，創(chuàng)作于2022年6月7 顯然，N也是可數(shù)的。 Cantor以此為出發(fā)點(diǎn)，對無限集合進(jìn)行考察，他發(fā)現(xiàn)下面的集合都是可數(shù)集：(1) ODD = x| xN，x是奇數(shù)N F：NODD F(n)=2n+1（F： N+ODD F(n)=2n-1）(2) EVEN = x| xN，x是偶數(shù)NF：NEVEN F(n)=2n（F： N+EVEN F(n)=2(n-1)） (3) N(n)=x|x=mn，m，nN NF：NN(n) F(m)= mn一一對應(yīng)與可數(shù)集第八張，PPT共二十九頁，創(chuàng)作于2022年6月8(4) NNN一一對應(yīng)與可數(shù)集第九張，PPT共二十九頁，創(chuàng)作于2022年6月9(6) ZZN

6、 F: ZN F(n)=2n (n0)F(n)=2|n|-1 (n0)的數(shù)排成一張表。顯然所有的有理數(shù)都在這張表內(nèi)。一一對應(yīng)與可數(shù)集第十一張，PPT共二十九頁，創(chuàng)作于2022年6月11一一對應(yīng)與可數(shù)集第十二張，PPT共二十九頁，創(chuàng)作于2022年6月12 注意：以0/1作為第一個(gè)數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍”表中所有的數(shù)。但是這個(gè)計(jì)數(shù)過程并沒有建立N到Q的雙射，因?yàn)橥粋€(gè)有理數(shù)可能被多次數(shù)到。例如1/1，2/2，3/3，都是有理數(shù)1。 為此我們規(guī)定，在計(jì)數(shù)過程中必須跳過第二次以及以后各次所遇到的同一個(gè)有理數(shù)。如1/1被計(jì)數(shù)，那么2/2，3/3，都要被跳過。表中數(shù)p/q上方的方括號內(nèi)標(biāo)明了這個(gè)

7、有理數(shù)所對應(yīng)的計(jì)數(shù)。 這樣就可以定義雙射函數(shù)f：NQ，其中f(n)是n下方的有理數(shù)。從而證明了NQ。 一一對應(yīng)與可數(shù)集第十三張，PPT共二十九頁，創(chuàng)作于2022年6月13 正是由于這一發(fā)現(xiàn)，使得他甚至猜想R也是可數(shù)集，并且著手去證明它。他沒有得到預(yù)期的結(jié)果，卻又作出了更偉大的發(fā)現(xiàn)。 Cantor利用它著名的對角線法，證明了0,1是不可數(shù)集，在這個(gè)基礎(chǔ)上證明了R也是不可數(shù)的，甚至于Rn也是不可數(shù)的。 Cantor對角線法與不可數(shù)集 注：(1)如果集合X不是可數(shù)集且X不是有限集，則稱X為不可數(shù)集。 (2)可數(shù)集與不可數(shù)集是對無窮集合而言的，有限集既不稱作不可數(shù)集合也不稱作可數(shù)集。第十四張，PPT共

8、二十九頁，創(chuàng)作于2022年6月14 定理4.1 區(qū)間0,1中的所有實(shí)數(shù)構(gòu)成的集合是不可數(shù)集。 證 區(qū)間0,1中每個(gè)實(shí)數(shù)，都可以寫成十進(jìn)制無限位小數(shù)形式0.a1a2a3a4.，其中每位ai0,1,2,.,9。 約定每個(gè)有限位小數(shù)后均補(bǔ)以無限多0。 假定定理不成立，于是0,1中全體實(shí)數(shù)可排成一個(gè)無窮序列:a1,a2,a3,.,an,.。 Cantor對角線法與不可數(shù)集第十五張，PPT共二十九頁，創(chuàng)作于2022年6月15每個(gè)ai寫成十進(jìn)制無限小數(shù)形式排成下表 a1=0.a11a12a13a14.a1n.a2=0.a21a22a23a24.a2n.a3=0.a31a32a33a34.a3n.an=0.

9、an1an2an3an4.ann.其中aij0,1,2,.,9構(gòu)造一個(gè)新的小數(shù) b=0.b1b2b3.bn.，顯然，b0,1，但nN，ban，矛盾。其中：若ann=5，則bn5； 若ann5，則bn=5，n=1,2,3,Cantor對角線法與不可數(shù)集第十六張，PPT共二十九頁，創(chuàng)作于2022年6月16 這說明0,1是不可數(shù)集，從而證明了并非一切無限集合都是可數(shù)集，無限集合也是有區(qū)別的。 Cantor首次對無限集合從“定量”方面進(jìn)行了深入研究，使人們深刻認(rèn)識到集合N與R有本質(zhì)不同。 Cantor用對角線元素來構(gòu)造小數(shù)x*的方法稱為Cantor對角線法。 Cantor所創(chuàng)造的這一方法是一個(gè)強(qiáng)有力的

10、證明方法，在函數(shù)論和計(jì)算機(jī)科學(xué)中有許多應(yīng)用。在計(jì)算的復(fù)雜性理論和不可判定問題中，對角線法也是為數(shù)不多的幾個(gè)重要方法之一。Cantor對角線法與不可數(shù)集第十七張，PPT共二十九頁，創(chuàng)作于2022年6月17 性質(zhì)1 集合A為可數(shù)集的充分必要條件是A的全部元素可以排成無重復(fù)項(xiàng)的序列a1,a2,.,an,.性質(zhì)2 無限集A必包含可數(shù)子集。性質(zhì)3 可數(shù)集的任一無限子集也是可數(shù)集。 性質(zhì)4 從可數(shù)集A中除去一個(gè)有限集M，則AM仍是可數(shù)集，即AAM。無限集合的性質(zhì) 性質(zhì)5 設(shè)M是一個(gè)無窮不可數(shù)集，A為M的至多可數(shù)子集(即A有窮或可數(shù))，則MMA。 定義4.3 凡能與自身的一個(gè)真子集對等的集合稱為無窮集合，或

11、無限集合。第十八張，PPT共二十九頁，創(chuàng)作于2022年6月18 如果要對任意的集合談?wù)撍鼈冎性氐摹皞€(gè)數(shù)”，這就需要把有限集合里元素“個(gè)數(shù)”的概念推廣到無限集合中，要求下一個(gè)定義對任何集合都適用。 集合的基數(shù)或集合的勢是集合論中基本概念之一，在樸素集合論體系中討論基數(shù)的概念，只能從幾條規(guī)定或公理出發(fā)。集合的基數(shù) 設(shè)A為任意一個(gè)集合，現(xiàn)在規(guī)定用cardA表示A中的元素“個(gè)數(shù)”，并稱cardA為集合A的基數(shù)，并再作以下五條規(guī)定：第十九張，PPT共二十九頁，創(chuàng)作于2022年6月19 (3) 對于自然數(shù)集合N，規(guī)定cardN=0 (讀作阿列夫零)。 (4) 對于實(shí)數(shù)集合R，規(guī)定cardR= (讀作阿列

12、夫)。 (5) 將0，1，2，0， 都稱作基數(shù)，其中0，1，2，稱作有窮基數(shù)，而0，稱作無窮基數(shù)。 (1) 對于任意的集合A和B，規(guī)定 cardA=cardB當(dāng)且僅當(dāng)AB。 (2) 對于任意的有限集合A，規(guī)定與A等勢的自然數(shù)n為A的基數(shù)，記作cardA=n。 集合的基數(shù)第二十張，PPT共二十九頁，創(chuàng)作于2022年6月20 定義4.4 集合A的基數(shù)是一個(gè)符號，凡與A等勢的集合都賦以同一個(gè)記號，集合A的基數(shù)記為|A|，也記作cardA。 定義4.4 所謂集合的基數(shù)是指所有與該集合等勢的集合所構(gòu)成的集族的共同性質(zhì)。(馮 諾伊曼) 定義4.4 集合的基數(shù)是集合的這樣一種特性，當(dāng)把集合里元素固有特點(diǎn)抽出

13、，以及把各元素在集合中的次序不顧之后，仍然保留下來的特性，就叫做基數(shù)。 集合的基數(shù)第二十一張，PPT共二十九頁，創(chuàng)作于2022年6月21Cantor連續(xù)統(tǒng)猜想Cantor猜想(連續(xù)統(tǒng)猜想，CH)： 在 0與之間是否還有別的基數(shù)？ 定義4.5 凡與集0,1對等的集稱為具有“連續(xù)統(tǒng)的勢”的集，或簡稱連續(xù)統(tǒng)。實(shí)數(shù)集R、無理數(shù)之集都是連續(xù)統(tǒng)。 1938年，K.哥德爾證明了CH對ZFC公理系統(tǒng)（見公理集合論)是協(xié)調(diào)的。 1963年，P.J.科恩證明CH對ZFC公理系統(tǒng)是獨(dú)立的。 這樣，在ZFC公理系統(tǒng)中，CH是不可能判定真假的。這是20世紀(jì)60年代集合論的最大進(jìn)展之一。第二十二張，PPT共二十九頁，創(chuàng)作

14、于2022年6月22 定義4.6 集合A的基數(shù)與集合B的基數(shù)稱為是相等的，當(dāng)且僅當(dāng)AB。 定義4.7 ，是任意兩個(gè)基數(shù)，A，B是分別以，為其基數(shù)的集。如果A與B的一個(gè)真子集對等，但A卻不能與B對等，則稱基數(shù)小于基數(shù)，記為。 規(guī)定當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)或=。 基數(shù)及其比較第二十三張，PPT共二十九頁，創(chuàng)作于2022年6月23規(guī)定當(dāng)且僅當(dāng)存在單射f: AB。 規(guī)定當(dāng)且僅當(dāng)存在單射f: AB，且不存在A到B的雙射。 無窮集合的基數(shù)也稱超窮數(shù)，超窮數(shù)也可以比較大小。于是，像下面這些句子是有意義的：“平面上的點(diǎn)多還是平面上的圓多？”，“集合0,1中的數(shù)比自然數(shù)集N中的數(shù)多”，“有理數(shù)和自然數(shù)一樣多?！被鶖?shù)及其

15、比較問題：無窮基數(shù)有多少？ 有沒有最大的無窮基數(shù)？定理4.2 (康托)對任一集合M，Mn，m=n，mn。 那么，對任兩個(gè)無限數(shù)，下面三個(gè)式子是否也有且僅有一個(gè)成立呢? 。 答案是肯定的。第二十五張，PPT共二十九頁，創(chuàng)作于2022年6月25 設(shè)是一個(gè)基數(shù)為的集合，是基數(shù)為的集合。 如果=，那么，都不能成立。 若，同時(shí)成立，則從A到B的每個(gè)單射都不是滿射，而從B到A的每個(gè)單射都不是滿射。 我們能證明這是不可能的，從而與不能同時(shí)成立。 定理4.3 (康托-伯恩斯坦)設(shè)A，B是兩個(gè)集合。如果存在單射f: AB與單射g: BA，則A與B對等。 只要能利用f與g直接建立一個(gè)從到的一個(gè)一一對應(yīng)即可?？低?伯恩斯坦定理第二十六張，PPT共二十九頁，創(chuàng)作于2022年6月26 推論 設(shè),為任意三個(gè)基數(shù)。如果，則。 定理4.4 (E. Zermelo，策梅羅) 設(shè)與為任意兩個(gè)基數(shù)，則以下三個(gè)式子=，中恰有一個(gè)式子成立。第二十七張，PPT共二十九頁，創(chuàng)作于2022年6月27 但另一方面，U是所有集合組成的集合，所以對任一XP(U)， XU 且X是一個(gè)集合，從而