無窮集合及基數(shù)第4節(jié)無窮集合及其基數(shù)可數(shù)集不可數(shù)集基數(shù)及其比較康托-伯恩斯坦定理悖論與公理化集合論主要內(nèi)容：第2頁,共26頁，星期六，2024年，5月

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

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

第3頁,共26頁，星期六，2024年，5月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)中的元素要多。第4頁,共26頁，星期六，2024年，5月

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

部分=整體？然而按照傳統(tǒng)，部分怎么能等于全體呢？這就是伽利略“悖論”，它不僅困惑了伽利略，還使許多數(shù)學(xué)家亦束手無策。伽利略“悖論”第5頁,共26頁，星期六，2024年，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年之后，他才沖破了傳統(tǒng)觀念的束縛，革命性的解決了伽利略“悖論”。

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

定義4.1

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

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ù)集(或可列集)。

第7頁,共26頁，星期六，2024年，5月

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

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

N，x是奇數(shù)}≈N

F：N

ODDF(n)=2n+1（F：N+

ODDF(n)=2n-1）(2)EVEN={x|x

N，x是偶數(shù)}≈NF：N

EVENF(n)=2n（F：N+

EVENF(n)=2(n-1)）

(3)N(n)={x|x=mn，m，n

N}≈NF：N

N(n)F(m)=mn一一對應(yīng)與可數(shù)集第8頁,共26頁，星期六，2024年，5月(4)N×N≈N一一對應(yīng)與可數(shù)集第9頁,共26頁，星期六，2024年，5月(6)Z×Z≈N

F:Z

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

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

注意：以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上方的方括號(hào)內(nèi)標(biāo)明了這個(gè)有理數(shù)所對應(yīng)的計(jì)數(shù)。這樣就可以定義雙射函數(shù)f：N→Q，其中f(n)是[n]下方的有理數(shù)。從而證明了N≈Q。

一一對應(yīng)與可數(shù)集第13頁,共26頁，星期六，2024年，5月

正是由于這一發(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ù)集。第14頁,共26頁，星期六，2024年，5月

定理4.1

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

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

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

假定定理不成立，于是[0,1]中全體實(shí)數(shù)可排成一個(gè)無窮序列:a1,a2,a3,...,an,...。Cantor對角線法與不可數(shù)集第15頁,共26頁，星期六，2024年，5月每個(gè)ai寫成十進(jìn)制無限小數(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對角線法與不可數(shù)集第16頁,共26頁，星期六，2024年，5月

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

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

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

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

性質(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，則A\M仍是可數(shù)集，即A≈A\M。無限集合的性質(zhì)

性質(zhì)5

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

定義4.3

凡能與自身的一個(gè)真子集對等的集合稱為無窮集合，或無限集合。第18頁,共26頁，星期六，2024年，5月

如果要對任意的集合談?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ī)定：第19頁,共26頁，星期六，2024年，5月(3)對于自然數(shù)集合N，規(guī)定cardN=?0

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

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

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

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

(2)對于任意的有限集合A，規(guī)定與A等勢的自然數(shù)n為A的基數(shù)，記作cardA=n。集合的基數(shù)第20頁,共26頁，星期六，2024年，5月

定義4.4

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

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

定義4.4’’

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

集合的基數(shù)第21頁,共26頁，星期六，2024年，5月Cantor連續(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)展之一。第22頁,共26頁，星期六，2024年，5月

定義4.6

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

定義4.7

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

<。

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

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

規(guī)定≥當(dāng)且僅當(dāng)>或=?；鶖?shù)及其比較第23頁,共26頁，星期六，2024年，5月規(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ù)及其比較