chap可數(shù)集與不可數(shù)集實用PPT課件

1、2021-10-221證明“”是一個等價關(guān)系證明：設(shè)S=X|任意兩個元素之間存在雙射，X是集合，是S上的二元關(guān)系： =|A,BS,存在雙射:AB 1) 對每個AS,存在恒等映射I:AA，I是雙射,于是AA，故是自反的。2) 對任意A,BS，若AB，則存在雙射:AB，顯然雙射-1:BA存在，于是BA，故是對稱的。3) 對任意A,B,CS，若AB,BC,則存在雙射 :AB和:BC，而(A)=(A)=(B)=C，即雙射:AC存在，于是AC，故是傳遞的。 綜上所述，是等價關(guān)系。第1頁/共39頁2021-10-222有限與無限 定義4.1.2：設(shè)Nn=0,1, , n 1 , n1 ,若集合A與Nn等勢

2、，則稱A為有限集；否則稱A為無限集。第2頁/共39頁2021-10-223無限多的自然數(shù) 定理4.1.1 自然數(shù)集合N是無限集。證明：設(shè)nN，n 1 , 令是從Nn到N的映射，Nn=0,1, , n1 ，下證不是雙射。 令k=1+max(0), (1), , (n1) , 于是kN，但對任意xNn ,均有(x) k , 因此，不是滿射，更不是雙射。由定義4.1.2知，N為無限集。啊哈！這下我們知道有無限多個自然數(shù)了！第3頁/共39頁2021-10-224抽屜原理（鴿巢原理） 我們知道，若A，B均為有限集，且A與B之間存在雙射，則A和B的元素個數(shù)相等，即AB。但是：定理4.1.2 任何有限集均不

3、能和其真子集等勢。 此定理也稱為抽屜原則：若將n+1個物體放入n個抽屜中，則至少有一個抽屜中放了兩個或兩個以上的物體。 抽屜原則對無限集并不總是成立，即無限集能夠與其真子集等勢。這是無限集合的一個非常重要的性質(zhì)。 我們已經(jīng)看到自然數(shù)集等勢于它的真子集偶數(shù)集合。下面我們再看幾個例子。第4頁/共39頁2021-10-225正實數(shù)和全體實數(shù)一樣多例2： 令R和R+分別為實數(shù)集合和正實數(shù)集合，即R+=xR | x 0 ，顯然，R+ R ，即R+是R的真子集。但是RR+ 證明：定義映射 f 如下： f (x) = ex , xR 于是，對任意的xR，存在唯一的yR+ ,使 y = ex = f (x)

4、； 另一方面，對任意的yR+ ,存在唯一的 x =lnyR , 使 f (x) = ex = elny = y , 這說明 f 是R到R+的一個雙射。因此， RR+ 。 第5頁/共39頁2021-10-226例3：A=0, 1）, B=0, 1 , A,B R.顯然 A B.構(gòu)造一A到B的雙射,說明AB.解: 令 A1=0,1/2,1/3,1/n,.作f: AB為: 任取x1,x2A, x1x2 , 顯然, f(x1)f(x2) , 且對 任意yB:若y=0 , 則取x=0 , 有f(0)=0若y=1, 則取x=1/2A1, 于是f(1/2)=1/(2-1)=y若y=1/n,取x=1/(n+1

5、)A1,故f(1/(n+1)=1/n=y若yBA1,則取x=y,于是f(x)=x=y 綜上所述f是A到B的雙射,于是AB. f(0)=0 f(1/n)=1/(n-1) (n1 , 1/nA1 , nN) f(x)=x (x0,1)A1 )第6頁/共39頁2021-10-2274.2 集合的基數(shù)幾個記號： 同有限集合中元素的個數(shù)的記法一樣，集合A的基數(shù)用 |A|表示。 每個有限集合都恰與某個集合Nn= 0,1, , n1等勢，其中n 0 , N0 = 。如果A Nn , 則A中有n個元素，即|A| = n; 若A為無限集，則用一個特殊的符號i(讀作阿列夫i，i是一個正整數(shù))來表示它的基數(shù)。例如，

6、對于自然數(shù)集合N，令|N| = 0 ( 讀作 “ 阿列夫零 ” ) 。第7頁/共39頁2021-10-228如何比較集合的大小(1)若AB , 則稱A的基數(shù)與B的基數(shù)相等, 記為|A|=|B|，否則記為|A|B|。(2)若存在A到B的單射，則稱A的基數(shù)小于或等于B的基數(shù)，記為|A| |B|；或稱B的基數(shù)大于或等于A的基數(shù)，記為|B| |A|。(3)若|A|B|，且|A|B| ，則稱A的基數(shù)小于B的基數(shù)，記為|A| |A| 。 根據(jù)集合的基數(shù)來比較它們的大小。定義定義4.2.1 令A(yù)、B為兩個集合， 由定義，|A|=|B|可形象地理解為A中的元素與B中的元素一樣多。第8頁/共39頁2021-10

7、-229集合大小是可比的 定理4.2.1 設(shè)A和B為兩個集合，總有 |A| |B|或者|B| |A| 。即任意兩個集合總可比較大小。 像實數(shù)一樣，任何兩個基數(shù)都可以比較大小，所以有第9頁/共39頁2021-10-2210基數(shù)之間的相等關(guān)系是等價關(guān)系 定理4.2.2 基數(shù)之間的相等關(guān)系“= ”是一個等價關(guān)系,即對任何集合A , B和C, 有: (1)|A|=|A|; (2)若|A|=|B| ,則 |B|=|A|; (3)若|A|=|B|且|B|=|C| , 則|A|=|C| .第10頁/共39頁2021-10-2211基數(shù)間的是偏序關(guān)系 定理4.2.3 基數(shù)之間的小于或等于關(guān)系“ ”是一個偏序關(guān)

8、系,即對任何集合A , B和C, 有: (1)|A| |A|; (2)若|A| |B|且|B| |A| ,則 |A|=|B|; (3)若|A| |B|且|B| |C| , 則|A| |C| .第11頁/共39頁2021-10-2212幾個關(guān)于基數(shù)的問題 我們知道自然數(shù)有無限多個。那么自然數(shù)集合是不是就是最大集合的呢？ 如果自然數(shù)集合不是最大的，那么比它更大的集合是什么樣的呢？ 是不是存在最大的基數(shù)呢？ 不！不存在最大的集合。山外有山，天外有天。我們的口號是：只有更大，沒有最大！第12頁/共39頁2021-10-2213山外青山樓外樓 定理4.2.4 對任意集合A,均有|A|(A) |,其中(A

9、)為A的冪集。 證明： 令 f : A(A)。f (a) =a， aA。 顯然，f 是單射,于是|A| |(A)| . 顯然，象集 a | aA 是(A)的真子集，所以，f 不是滿射，從而不是雙射。于是我們有|A| |(A)|。 錯！錯！錯！錯！錯！錯！錯誤是：雖然f不是雙射，但不能說明A與 (A)之間不存在其它的映射是雙射。正確的作法是證明A與 (A)存在任何的雙射都是不可能的。 第13頁/共39頁2021-10-2214山外青山樓外樓 假設(shè)|A| = |(A)|，則存在A到(A)的雙射g . 令B=aA | a g(a) (g(a)是a所對應(yīng)的A的子集)，顯然B(A)。bA,使g(b) =

10、B 。但是 (1)若bB，則由B之定義有bg(b)，即bB ; (2)若bB，即bg(b)，則由B之定義有bB。 總之有bB當(dāng)且僅當(dāng)b B，矛盾。 故|A|(A)|。綜合以上，定理得證。定理4.2.4 對任意集合A,均有|A| | (A)| ,其中(A)為A的冪集。證明： 令f ：A(A)。f (a) =a， aA。顯然，f 是單射，于是|A| |(A)| 。 討論B的存在性：雙射g：A(A)， aA，g(a)(A)即： g(a)是A的子集。又：作集合D=AA，AA，顯然，D A，即D(A) 。令： aA，g(a)=D，于是，aD，即a g(a)，但aA A。第14頁/共39頁2021-10-

11、2215無限集也分大小，且無最大者 定理4.2.4說明：對任意無限集，它的冪集就比它大。因此對任意無限集都存在更大的集合。 我們記自然數(shù)集合N的冪集的基數(shù)為1，也就是| (N)| =1 ， 由定理4.2.4知， 0 1 。 可以證明 |R| = | (N)| , 其中R為實數(shù)集，于是， | N | |R|。實際上N是最小的無限集。 依次可以推得實數(shù)集合的冪集的基數(shù)為2，第15頁/共39頁2021-10-22164.3 可數(shù)集與不可數(shù)集定義4.3.1：設(shè)A是一個集合，若A與N等勢，則稱A為可數(shù)無限集；若A是有限集，則稱A為可數(shù)集。 有時也將可數(shù)無限集簡稱為可數(shù)集。（遇到討論可數(shù)集的問題時要注意區(qū)

12、分無限和有限兩種情況。） 不是可數(shù)集的集合就稱為不可數(shù)集。第16頁/共39頁2021-10-2217整數(shù)集是可數(shù)集例1：整數(shù)集Z是可數(shù)集。 證明：可定義N到Z的映射如下： (n) =n/2 (n為偶數(shù)） (n) =(1-n)/2 (n為奇數(shù)） 不難驗證為雙射,故NZ, 則Z是可數(shù)集。說明：映射 將 10，偶數(shù)正整數(shù)， 奇數(shù)（除1外） 負(fù)整數(shù)。第17頁/共39頁2021-10-2218定理4.3.1 A是可數(shù)無限集當(dāng)且僅當(dāng)A的所有元素可以如下編號排出： a1 , a2 , a3 , , an , 此定理告訴我們，任何集合只要它的元素可以排序，就是可數(shù)的。如何判別一集合是可數(shù)的第18頁/共39頁2

13、021-10-2219可數(shù)集的子集仍是可數(shù)的定理4.3.2 可數(shù)集的子集仍是可數(shù)集。 證明：設(shè)A是可數(shù)集，若A是有限集，則它的子集仍是有限集，當(dāng)然也是可數(shù)集。若A是無限集，則由定理4.3.1知，A的元素可排列成： a1 , a2 , a3 , , an , (3.3) 顯然，A的無限子集可如下得到： 從左向右看式(3.3)，可以依據(jù)子集中元素出現(xiàn)的次序?qū)⒃撟蛹脑嘏帕袨椋?ai1 , ai2 , ai3 , , ain , 由定理4.3.1知，該子集是可數(shù)集。第19頁/共39頁2021-10-2220有理數(shù)集Q是可數(shù)集。 例2：有理數(shù)集是可數(shù)集。 證明：已知任何非零有理數(shù)均可表示成確定的既約

14、分?jǐn)?shù)，故把全體有理數(shù)按如下方式排列： (1)0排在最前面； (2)對正分?jǐn)?shù)，按它的分子與分母的和數(shù)由小到大排列，若和數(shù)相等，則分子小的排前面； (3)對負(fù)分?jǐn)?shù)，把它緊排在相應(yīng)的正分?jǐn)?shù)后面。 顯然，任意有理數(shù)總會排入此序列中。由定理4.3.1知，Q是可數(shù)集。 這種排序的方法稱為字典排序法。第20頁/共39頁2021-10-2221三角形方法 有理數(shù)還可以按下表排序： 顯然用此方法可將所有的有理數(shù)排序。分子分母 1 2 3 4 5 6 1234 . . . 此方法稱為三角形方法，是很有用的方法。第21頁/共39頁2021-10-2222符號串的集合是可數(shù)的 令為一字母表， 上的符號串為+： + =

15、 1 +2 +3 +4+=i i=1 這里i為長度為i的符號串的集合。 +為可數(shù)集。 事實上，若| = k， 則每一個符號串就是一個 k 進制的數(shù)，顯然它們是可以按序排列起來。所以+為可數(shù)集。 第22頁/共39頁2021-10-2223不是所有的集合都能排序 如果一個集合的元素可以排序，那么我們就可以一個一個地去數(shù)。 是不是所有的集合的元素都能排序呢？ 不！不是所有的集合都能排序。 比如0，1中實數(shù)的集合。讓我們來設(shè)想一下將它的元素排一個序： 0理所當(dāng)然排在第一位。 但是0之后應(yīng)該排哪個呢？0.1？不！0.01？不！0.001？不！.？ 你會發(fā)現(xiàn)第二個就不知道排哪個好了。 這樣看來實數(shù)集合是沒

16、法去數(shù)了！?第23頁/共39頁2021-10-2224實數(shù)集是不可數(shù)的定理4.3.3 實數(shù)集是不可數(shù)的。 證明：取R的子集 (0,1)=xR | 0 x 1 ,由定理4.3.2知，只需證明(0,1)是不可數(shù)集即可。 若(0,1)可數(shù)，則可將(0,1)中的數(shù)排成序列： 1： 0.a11 a12 a13 2： 0.a21 a22 a23 3： 0.a31 a32 a33 考慮數(shù)r =0.r1 r2 rk，其中當(dāng)akk1則rk=1 ;當(dāng)akk=1則 rk=2，k = 1,2, 。這樣就保證了r不等于序列中任何數(shù)，因為對任意k，r的第k位rk與序列中第k號數(shù)的第k位akk不相等。 因為r不在序列中，所

17、以，(0,1)是不可數(shù)集。第24頁/共39頁2021-10-2225對角線方法 定理4.3.3中所使用的方法稱為對角線方法。a11a22a33r1r2r31 2 3 對角線方法是一種非常有用的方法。第25頁/共39頁2021-10-2226連續(xù)統(tǒng)問題 已知N是可數(shù)集，而|N|R|.能否找到一個實數(shù)集R的子集A，使得： NAR ,但又不存在A到R的雙射？ 這個問題稱為“連續(xù)統(tǒng)問題”。 現(xiàn)已證明：在現(xiàn)有公理系統(tǒng)中，證明它成立與否都不可能。第26頁/共39頁2021-10-2227新春曉信息時代到，處處有電腦。夜來打字聲，程序知多少？ 答曰： 詩中的問題是計算機上所有程序有多少？為何如此？有詩為證：

18、計算機，靠程序，它的本事知底細。程序都是符號串，理應(yīng)是個可數(shù)集。程序時時新， 落花處處飄。它們同為0 ，數(shù)數(shù)便知道。第27頁/共39頁2021-10-2228集合論總結(jié) 集合； 關(guān)系； 映射； 可數(shù)集與不可數(shù)集。集合論的主要內(nèi)容有：第28頁/共39頁2021-10-2229集合 基本概念：集合、子集、冪集。 集合之間的關(guān)系：(真)含于( / )，相等()。 集合的基本運算： 并()、交()、差()和對稱差()。 笛卡爾直積： n個集合的笛卡爾直積是它們的 n元有序組的集合。它仍然是個集合。 集合的表示：列舉法和描述法。第29頁/共39頁2021-10-2230關(guān)系 關(guān)系的概念： A到B的二元關(guān)

19、系R是笛卡爾直積AB的子集。 關(guān)系仍然是集合。 關(guān)系的表示：仍然可以采用集合的表示方法。 若A、B是有限集合，或者說R是有限集上的關(guān)系，則R的表示還可以采用：關(guān)系矩陣 和 關(guān)系圖。第30頁/共39頁2021-10-2231關(guān)系的性質(zhì) 自反性： x A xRx。 反自反性： x A (xRx)。 對稱性： x ，yA， 若xRy yRx。 反對稱性：x ，yA， 若xRy且yRx x = y 。 傳遞性： x ，y，zA， 若xRy且yRz xRz 。令R是定義在集合A上的關(guān)系。第31頁/共39頁2021-10-2232關(guān)系的運算 關(guān)系是集合，可具有集合的各種運算。 復(fù)合運算：RS = x，z

20、| yB：xRy 且ySz，其中，R，S分別為A到B和B到C的關(guān)系。 逆關(guān)系：R-1 = y，x | x，y R。 注意復(fù)合運算的逆： (RS) 1 = S-1R-1。 在一個集合A上的關(guān)系的冪運算： R0 =x，x | x A , Rk = Rk-1R 。第32頁/共39頁2021-10-2233關(guān)系的閉包 某關(guān)系的具有某種性質(zhì)的閉包是：包含該關(guān)系的最小的有此性質(zhì)的關(guān)系。 依據(jù)關(guān)系的性質(zhì)有：r(R)、 s(R)和t(R)，即自反閉包、對稱閉包和傳遞閉包。 r(R) = RR0。 s(R) = RR-1。 t(R) =Ri。 i=1第33頁/共39頁2021-10-2234用關(guān)系矩陣實現(xiàn)關(guān)系的運算 MRS = MR MS。 MR0為R0的關(guān)系矩陣。 顯然R-1的關(guān)系矩陣就是MRT。 顯然的Rk關(guān)系矩陣是MRk = MRk-1 MR。 R的自反閉包為MRMR0。 R的對稱閉包為MRMRT。 n R的傳遞閉包為 MRk。 k=1令R、S為有限