關(guān)于無窮集合及基數(shù)1第1頁，課件共29頁，創(chuàng)作于2023年2月2第4節(jié)無窮集合及其基數(shù)可數(shù)集不可數(shù)集基數(shù)及其比較康托-伯恩斯坦定理悖論與公理化集合論主要內(nèi)容：第2頁，課件共29頁，創(chuàng)作于2023年2月3

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

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

第3頁，課件共29頁，創(chuàng)作于2023年2月41638年意大利的天文學家伽利略發(fā)現(xiàn)了下面的問題：

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

一方面，凡是N(2)的元素都是N+的元素，也就是說N(2)?N+，而且由于2，3，5等元素都不在N(2)中，所以N(2)?N+。這樣看來，N+中的元素要比N(2)中的元素要多。第4頁，課件共29頁，創(chuàng)作于2023年2月5

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

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

Cantor詳細地分析了斷定有限集合的元素多少的方法，即采用數(shù)數(shù)的方法。他認為“數(shù)數(shù)的過程”就是作“一一對應的過程”。

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

Cantor認為在N+與N(2)之間存在著一一對應(即雙射)，因此N+與N(2)的元素個數(shù)是相等的。一一對應與可數(shù)集第6頁，課件共29頁，創(chuàng)作于2023年2月7

定義4.1

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

Cantor把自然數(shù)集N+稱為可數(shù)集(或可列集)，這是因為它的元素可以一個一個的數(shù)出來。凡是與自然數(shù)集N+等勢的集合，它們的元素通過一一對應關(guān)系，也都可以一個一個的數(shù)出來，因此：一一對應與可數(shù)集

定義4.2

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

第7頁，課件共29頁，創(chuàng)作于2023年2月8

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

Cantor以此為出發(fā)點，對無限集合進行考察，他發(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一一對應與可數(shù)集第8頁，課件共29頁，創(chuàng)作于2023年2月9(4)N×N≈N一一對應與可數(shù)集第9頁，課件共29頁，創(chuàng)作于2023年2月10(6)Z×Z≈N

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

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

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

一一對應與可數(shù)集第13頁，課件共29頁，創(chuàng)作于2023年2月14

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

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

注：(1)如果集合X不是可數(shù)集且X不是有限集，則稱X為不可數(shù)集。(2)可數(shù)集與不可數(shù)集是對無窮集合而言的，有限集既不稱作不可數(shù)集合也不稱作可數(shù)集。第14頁，課件共29頁，創(chuàng)作于2023年2月15

定理4.1

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

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

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

假定定理不成立，于是[0,1]中全體實數(shù)可排成一個無窮序列:a1,a2,a3,...,an,...。Cantor對角線法與不可數(shù)集第15頁，課件共29頁，創(chuàng)作于2023年2月16每個ai寫成十進制無限小數(shù)形式排成下表a1=0.a11a12a13a14...a1n...a2=0.a21a22a23a24...a2n...a3=0.a31a32a33a34...a3n..........................an=0.an1an2an3an4...ann..........................其中aij{0,1,2,...,9}構(gòu)造一個新的小數(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頁，課件共29頁，創(chuàng)作于2023年2月17

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

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

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

Cantor所創(chuàng)造的這一方法是一個強有力的證明方法，在函數(shù)論和計算機科學中有許多應用。在計算的復雜性理論和不可判定問題中，對角線法也是為數(shù)不多的幾個重要方法之一。Cantor對角線法與不可數(shù)集第17頁，課件共29頁，創(chuàng)作于2023年2月18

性質(zhì)1

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

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

性質(zhì)4

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

性質(zhì)5

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

定義4.3

凡能與自身的一個真子集對等的集合稱為無窮集合，或無限集合。第18頁，課件共29頁，創(chuàng)作于2023年2月19

如果要對任意的集合談論它們中元素的“個數(shù)”，這就需要把有限集合里元素“個數(shù)”的概念推廣到無限集合中，要求下一個定義對任何集合都適用。集合的基數(shù)或集合的勢是集合論中基本概念之一，在樸素集合論體系中討論基數(shù)的概念，只能從幾條規(guī)定或公理出發(fā)。集合的基數(shù)

設A為任意一個集合，現(xiàn)在規(guī)定用cardA表示A中的元素“個數(shù)”，并稱cardA為集合A的基數(shù)，并再作以下五條規(guī)定：第19頁，課件共29頁，創(chuàng)作于2023年2月20(3)對于自然數(shù)集合N，規(guī)定cardN=?0

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

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

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

cardA=cardB當且僅當A≈B。

(2)對于任意的有限集合A，規(guī)定與A等勢的自然數(shù)n為A的基數(shù)，記作cardA=n。集合的基數(shù)第20頁，課件共29頁，創(chuàng)作于2023年2月21

定義4.4

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

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

定義4.4’’

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

集合的基數(shù)第21頁，課件共29頁，創(chuàng)作于2023年2月22Cantor連續(xù)統(tǒng)猜想Cantor猜想(連續(xù)統(tǒng)猜想，CH)：在?0與?之間是否還有別的基數(shù)？

定義4.5

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

1963年，P.J.科恩證明CH對ZFC公理系統(tǒng)是獨立的。這樣，在ZFC公理系統(tǒng)中，CH是不可能判定真假的。這是20世紀60年代集合論的最大進展之一。第22頁，課件共29頁，創(chuàng)作于2023年2月23

定義4.6

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

定義4.7

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

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

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

規(guī)定≥當且僅當>或=。基數(shù)及其比較第23頁，課件共29頁，創(chuàng)作于2023年2月24規(guī)定≤當且僅當存在單射f:AB。

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

無窮集合的基數(shù)也稱超窮數(shù)，超窮數(shù)也可以比較大小。于是，像下面這些句子是有意義的：“平面上的點多還是平面上的圓多？”，“集合[0,1]中的數(shù)比自然數(shù)集N中的數(shù)多”，“有理數(shù)和自然數(shù)一樣多?！被鶖?shù)及其比較問題：無窮基數(shù)有多少？有沒有最大的無窮基數(shù)？定理4.2(康托)對任一集合M，M<2M。第24頁，課件共29頁，創(chuàng)作于2023年2月25康托-伯恩斯坦定理

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

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

<，=，>。

答案是肯定的。第25頁，課件共29頁，創(chuàng)作于2023年2月26

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

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

若<，<同時成立，則從A到B的每個單射都不是滿射，而從B到A的每個單射都不是滿射。

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