無(wú)窮集合及基數(shù)

關(guān)于無(wú)窮集合及基數(shù)1第1頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三2第4節(jié)無(wú)窮集合及其基數(shù)可數(shù)集不可數(shù)集基數(shù)及其比較康托-伯恩斯坦定理悖論與公理化集合論主要內(nèi)容：第2頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三3

集合的基數(shù)亦稱作集合的勢(shì)。粗略的說(shuō)，就是一個(gè)集合的“規(guī)?！保摹按笮　?，或者更確切地說(shuō)，它有多少個(gè)元素。通俗的說(shuō)，集合的勢(shì)是量度集合所含元素多少的量。集合的勢(shì)越大，所含的元素越多。很明顯，如果集合中只有有限個(gè)元素，我們只要數(shù)一數(shù)它有多少個(gè)可以了，這時(shí)集合的基數(shù)就是其中所含元素的個(gè)數(shù)。什么是集合的基數(shù)？

值得注意的是無(wú)限集，它所含的元素有無(wú)窮多個(gè)，這時(shí)怎樣去數(shù)？為了解決這個(gè)問(wèn)題，我們首先從伽利略“悖論”說(shuō)起。

第3頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三41638年意大利的天文學(xué)家伽利略發(fā)現(xiàn)了下面的問(wèn)題：

N+={1,2,3,…,n,…}與N(2)={1,4,9,…,n2,…}這兩個(gè)集合，哪一個(gè)的元素更多一些？伽利略“悖論”

一方面，凡是N(2)的元素都是N+的元素，也就是說(shuō)N(2)?N+，而且由于2，3，5等元素都不在N(2)中，所以N(2)?N+。這樣看來(lái)，N+中的元素要比N(2)中的元素要多。第4頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三5

但另一方面，對(duì)于N+中的每個(gè)元素都可以在N(2)中找到一個(gè)元素與之對(duì)應(yīng)，這樣看來(lái)，N(2)中的元素不比N+中的元素要少。那么到底N+與N(2)中所含元素的個(gè)數(shù)是否一樣呢？如果是，那么就有

部分=整體？然而按照傳統(tǒng)，部分怎么能等于全體呢？這就是伽利略“悖論”，它不僅困惑了伽利略，還使許多數(shù)學(xué)家亦束手無(wú)策。伽利略“悖論”第5頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三61874年，Cantor注意到伽利略”悖論”。在1874年到1897年間完全解決了這個(gè)問(wèn)題。

Cantor詳細(xì)地分析了斷定有限集合的元素多少的方法，即采用數(shù)數(shù)的方法。他認(rèn)為“數(shù)數(shù)的過(guò)程”就是作“一一對(duì)應(yīng)的過(guò)程”。

Cantor認(rèn)為這種“一一對(duì)應(yīng)”的方法不僅適用于有限集，也適用于無(wú)限集。他牢牢地抓住這個(gè)原則，拋棄了部分必定小于全體的教條，經(jīng)歷了大約23年之后，他才沖破了傳統(tǒng)觀念的束縛，革命性的解決了伽利略“悖論”。

Cantor認(rèn)為在N+與N(2)之間存在著一一對(duì)應(yīng)(即雙射)，因此N+與N(2)的元素個(gè)數(shù)是相等的。一一對(duì)應(yīng)與可數(shù)集第6頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三7

定義4.1

設(shè)A，B是集合，若存在著從A到B的雙射，就稱A和B等勢(shì)(或?qū)Φ?，記作A≈B。

Cantor把自然數(shù)集N+稱為可數(shù)集(或可列集)，這是因?yàn)樗脑乜梢砸粋€(gè)一個(gè)的數(shù)出來(lái)。凡是與自然數(shù)集N+等勢(shì)的集合，它們的元素通過(guò)一一對(duì)應(yīng)關(guān)系，也都可以一個(gè)一個(gè)的數(shù)出來(lái)，因此：一一對(duì)應(yīng)與可數(shù)集

定義4.2

凡是與自然數(shù)集N+等勢(shì)的集合，稱為可數(shù)集(或可列集)。

第7頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三8

顯然，N也是可數(shù)的。

Cantor以此為出發(fā)點(diǎn)，對(duì)無(wú)限集合進(jìn)行考察，他發(fā)現(xiàn)下面的集合都是可數(shù)集：(1)ODD={x|xN，x是奇數(shù)}≈N

F：NODDF(n)=2n+1（F：N+ODDF(n)=2n-1）(2)EVEN={x|xN，x是偶數(shù)}≈NF：NEVENF(n)=2n（F：N+EVENF(n)=2(n-1)）

(3)N(n)={x|x=mn，m，nN}≈NF：NN(n)F(m)=mn一一對(duì)應(yīng)與可數(shù)集第8頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三9(4)N×N≈N一一對(duì)應(yīng)與可數(shù)集第9頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三10(6)Z×Z≈N

F:ZNF(n)=2n(n≥0)F(n)=2|n|-1(n<0)

(5)Z≈N一一對(duì)應(yīng)與可數(shù)集第10頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三11Cantor在解決了Z×Z≈N后，用類(lèi)似的思想解決了Zn≈N。在這種想法之下，Cantor得到了一個(gè)令人驚異的發(fā)現(xiàn)：Q≈N。并且利用他獨(dú)創(chuàng)的“折線法”，巧妙的建立了Q與N的一一對(duì)應(yīng)。為建立N到Q的雙射函數(shù)，先把所有形式為p/q(p，q為整數(shù)且q>0)的數(shù)排成一張表。顯然所有的有理數(shù)都在這張表內(nèi)。一一對(duì)應(yīng)與可數(shù)集第11頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三12一一對(duì)應(yīng)與可數(shù)集第12頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三13

注意：以0/1作為第一個(gè)數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍”表中所有的數(shù)。但是這個(gè)計(jì)數(shù)過(guò)程并沒(méi)有建立N到Q的雙射，因?yàn)橥粋€(gè)有理數(shù)可能被多次數(shù)到。例如1/1，2/2，3/3，…都是有理數(shù)1。為此我們規(guī)定，在計(jì)數(shù)過(guò)程中必須跳過(guò)第二次以及以后各次所遇到的同一個(gè)有理數(shù)。如1/1被計(jì)數(shù)，那么2/2，3/3，…都要被跳過(guò)。表中數(shù)p/q上方的方括號(hào)內(nèi)標(biāo)明了這個(gè)有理數(shù)所對(duì)應(yīng)的計(jì)數(shù)。這樣就可以定義雙射函數(shù)f：N→Q，其中f(n)是[n]下方的有理數(shù)。從而證明了N≈Q。

一一對(duì)應(yīng)與可數(shù)集第13頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三14

正是由于這一發(fā)現(xiàn)，使得他甚至猜想R也是可數(shù)集，并且著手去證明它。他沒(méi)有得到預(yù)期的結(jié)果，卻又作出了更偉大的發(fā)現(xiàn)。

Cantor利用它著名的對(duì)角線法，證明了[0,1]是不可數(shù)集，在這個(gè)基礎(chǔ)上證明了R也是不可數(shù)的，甚至于Rn也是不可數(shù)的。Cantor對(duì)角線法與不可數(shù)集

注：(1)如果集合X不是可數(shù)集且X不是有限集，則稱X為不可數(shù)集。(2)可數(shù)集與不可數(shù)集是對(duì)無(wú)窮集合而言的，有限集既不稱作不可數(shù)集合也不稱作可數(shù)集。第14頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三15

定理4.1

區(qū)間[0,1]中的所有實(shí)數(shù)構(gòu)成的集合是不可數(shù)集。

證區(qū)間[0,1]中每個(gè)實(shí)數(shù)，都可以寫(xiě)成十進(jìn)制無(wú)限位小數(shù)形式0.a1a2a3a4...，其中每位ai{0,1,2,...,9}。

約定每個(gè)有限位小數(shù)后均補(bǔ)以無(wú)限多0。

假定定理不成立，于是[0,1]中全體實(shí)數(shù)可排成一個(gè)無(wú)窮序列:a1,a2,a3,...,an,...。Cantor對(duì)角線法與不可數(shù)集第15頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三16每個(gè)ai寫(xiě)成十進(jìn)制無(wú)限小數(shù)形式排成下表a1=0.a11a12a13a14...a1n...a2=0.a21a22a23a24...a2n...a3=0.a31a32a33a34...a3n..........................an=0.an1an2an3an4...ann..........................其中aij{0,1,2,...,9}構(gòu)造一個(gè)新的小數(shù)b=0.b1b2b3...bn...，顯然，b[0,1]，但nN，ban，矛盾。其中：若ann=5，則bn≠5；若ann≠5，則bn=5，n=1,2,3,…Cantor對(duì)角線法與不可數(shù)集第16頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三17

這說(shuō)明[0,1]是不可數(shù)集，從而證明了并非一切無(wú)限集合都是可數(shù)集，無(wú)限集合也是有區(qū)別的。

Cantor首次對(duì)無(wú)限集合從“定量”方面進(jìn)行了深入研究，使人們深刻認(rèn)識(shí)到集合N與R有本質(zhì)不同。

Cantor用對(duì)角線元素來(lái)構(gòu)造小數(shù)x*的方法稱為Cantor對(duì)角線法。

Cantor所創(chuàng)造的這一方法是一個(gè)強(qiáng)有力的證明方法，在函數(shù)論和計(jì)算機(jī)科學(xué)中有許多應(yīng)用。在計(jì)算的復(fù)雜性理論和不可判定問(wèn)題中，對(duì)角線法也是為數(shù)不多的幾個(gè)重要方法之一。Cantor對(duì)角線法與不可數(shù)集第17頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三18

性質(zhì)1

集合A為可數(shù)集的充分必要條件是A的全部元素可以排成無(wú)重復(fù)項(xiàng)的序列a1,a2,...,an,...性質(zhì)2無(wú)限集A必包含可數(shù)子集。性質(zhì)3

可數(shù)集的任一無(wú)限子集也是可數(shù)集。

性質(zhì)4

從可數(shù)集A中除去一個(gè)有限集M，則A\M仍是可數(shù)集，即A≈A\M。無(wú)限集合的性質(zhì)

性質(zhì)5

設(shè)M是一個(gè)無(wú)窮不可數(shù)集，A為M的至多可數(shù)子集(即A有窮或可數(shù))，則M≈M\A。

定義4.3

凡能與自身的一個(gè)真子集對(duì)等的集合稱為無(wú)窮集合，或無(wú)限集合。第18頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三19

如果要對(duì)任意的集合談?wù)撍鼈冎性氐摹皞€(gè)數(shù)”，這就需要把有限集合里元素“個(gè)數(shù)”的概念推廣到無(wú)限集合中，要求下一個(gè)定義對(duì)任何集合都適用。集合的基數(shù)或集合的勢(shì)是集合論中基本概念之一，在樸素集合論體系中討論基數(shù)的概念，只能從幾條規(guī)定或公理出發(fā)。集合的基數(shù)

設(shè)A為任意一個(gè)集合，現(xiàn)在規(guī)定用cardA表示A中的元素“個(gè)數(shù)”，并稱cardA為集合A的基數(shù)，并再作以下五條規(guī)定：第19頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三20(3)對(duì)于自然數(shù)集合N，規(guī)定cardN=?0

(讀作阿列夫零)。(4)對(duì)于實(shí)數(shù)集合R，規(guī)定cardR=?

(讀作阿列夫)。(5)將0，1，2，…，?0，?，…都稱作基數(shù)，其中0，1，2，…稱作有窮基數(shù)，而?0，?…稱作無(wú)窮基數(shù)。

(1)對(duì)于任意的集合A和B，規(guī)定

cardA=cardB當(dāng)且僅當(dāng)A≈B。

(2)對(duì)于任意的有限集合A，規(guī)定與A等勢(shì)的自然數(shù)n為A的基數(shù)，記作cardA=n。集合的基數(shù)第20頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三21

定義4.4

集合A的基數(shù)是一個(gè)符號(hào)，凡與A等勢(shì)的集合都賦以同一個(gè)記號(hào)，集合A的基數(shù)記為|A|，也記作cardA。定義4.4’

所謂集合的基數(shù)是指所有與該集合等勢(shì)的集合所構(gòu)成的集族的共同性質(zhì)。(馮諾伊曼)

定義4.4’’

集合的基數(shù)是集合的這樣一種特性，當(dāng)把集合里元素固有特點(diǎn)抽出，以及把各元素在集合中的次序不顧之后，仍然保留下來(lái)的特性，就叫做基數(shù)。

集合的基數(shù)第21頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三22Cantor連續(xù)統(tǒng)猜想Cantor猜想(連續(xù)統(tǒng)猜想，CH)：在?0與?之間是否還有別的基數(shù)？

定義4.5

凡與集[0,1]對(duì)等的集稱為具有“連續(xù)統(tǒng)的勢(shì)”的集，或簡(jiǎn)稱連續(xù)統(tǒng)。實(shí)數(shù)集R、無(wú)理數(shù)之集都是連續(xù)統(tǒng)。1938年，K.哥德?tīng)栕C明了CH對(duì)ZFC公理系統(tǒng)（見(jiàn)公理集合論)是協(xié)調(diào)的。

1963年，P.J.科恩證明CH對(duì)ZFC公理系統(tǒng)是獨(dú)立的。這樣，在ZFC公理系統(tǒng)中，CH是不可能判定真假的。這是20世紀(jì)60年代集合論的最大進(jìn)展之一。第22頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三23

定義4.6

集合A的基數(shù)與集合B的基數(shù)稱為是相等的，當(dāng)且僅當(dāng)A≈B。

定義4.7

，是任意兩個(gè)基數(shù)，A，B是分別以，為其基數(shù)的集。如果A與B的一個(gè)真子集對(duì)等，但A卻不能與B對(duì)等，則稱基數(shù)小于基數(shù)，記為<。

規(guī)定≤當(dāng)且僅當(dāng)<或=。

規(guī)定>當(dāng)且僅當(dāng)<。

規(guī)定≥當(dāng)且僅當(dāng)>或=?；鶖?shù)及其比較第23頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三24規(guī)定≤當(dāng)且僅當(dāng)存在單射f:AB。

規(guī)定<當(dāng)且僅當(dāng)存在單射f:AB，且不存在A到B的雙射。

無(wú)窮集合的基數(shù)也稱超窮數(shù)，超窮數(shù)也可以比較大小。于是，像下面這些句子是有意義的：“平面上的點(diǎn)多還是平面上的圓多？”，“集合[0,1]中的數(shù)比自然數(shù)集N中的數(shù)多”，“有理數(shù)和自然數(shù)一樣多。”基數(shù)及其比較問(wèn)題：無(wú)窮基數(shù)有多少？有沒(méi)有最大的無(wú)窮基數(shù)？定理4.2(康托)對(duì)任一集合M，M<2M。第24頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三25康托-伯恩斯坦定理

在有限數(shù)大小的比較中，對(duì)任取兩個(gè)有限數(shù)（非負(fù)整數(shù)）m，n，下面三式有且僅有一式成立:m>n，m=n，m<n。

那么，對(duì)任兩個(gè)無(wú)限數(shù)，，下面三個(gè)式子是否也有且僅有一個(gè)成立呢?

<，=，>。

答案是肯定的。第25頁(yè)，講稿共29頁(yè)，2023年5月2日，星期三26

設(shè)Ａ是一個(gè)基數(shù)為的集合，Ｂ是基數(shù)為的集合。

如果=，那么<，<都不能成立。

若<，<同時(shí)成立，則從A到B的每個(gè)單射都不是滿射，而從B到A的每個(gè)單射都不是滿射。

我們能證明這是不可能的，從而<與<不能同