離散數(shù)學(xué)第八章-最新版

1、第八章 自然數(shù)和基數(shù),§8.1 自然數(shù)及數(shù)學(xué)歸納法§8.2 基數(shù),自然數(shù)和歸納法,主要概念： 集合的后繼主要方法：歸納原理、第一歸納法、第二歸納法,自然數(shù)的引進(jìn)方法,① 公理化方法：皮亞諾公理（G. Peano）；② 構(gòu)造性方法：借助集合論，具體構(gòu)造出 N。,自然數(shù)構(gòu)造的出發(fā)點(diǎn),1) 自然數(shù)的各種性質(zhì) ( 運(yùn)算、大小次序 及 基本定律 ) , 都可以從 Peano 公理一一推導(dǎo)出

2、來(lái)；證明構(gòu)造出來(lái)的 “自然數(shù)” 滿足Peano公理，因此具有普通自然數(shù)的一切性質(zhì)。,集合的后繼,定義8.2 (后繼集合) 對(duì)于任意集合 A，其后繼集合 A+ 定義為：A+ = A ∪ { A } 。 每個(gè)集合都有唯一的一個(gè)后繼。,引理 1 設(shè) A 為任意集合， 則 i) ?＋ = { ? } ； ii) { ? }＋ = { ?, { ? } }； iii) A

3、∈ A＋； iv) A ? A＋； v) A＋ ≠ ? 。,構(gòu)造自然數(shù)系統(tǒng)＜N，+，·＞馮 ? 諾依曼（Von Neumann）方案：,0 = ?1 = 0+ = { ? } = { 0 }2 = 1+ = { ?, { ? } } = { 0, 1 }3 = 2+ = { ?, { ? }, { ?, { ? } } } = { 0, 1, 2 }

4、? ?n+1 = n+ = ? = { 0, 1, ?, n }?,自然數(shù)集合 N（歸納定義法）,i) 0∈N， 這里 0 = ?；ii) 若 n∈ N ，則 n＋∈ N ；iii) 若 S ? N 滿足 （極小化） 1) 0∈S 2) 如果 n∈S, 則 n+∈S 則 S = N。,大于/小于、

5、加法、乘法,對(duì)每個(gè)自然數(shù) n∈ N ，皆有 n∈n＋ 及 n ? n＋，據(jù)此有:定義 8.4 若 m, n∈N 使 m∈n, 則稱 m小于n ( 或 n大于m ), 記為 m＜n ( 或 n＞m)。 “小于” 關(guān)系 ＜是自然數(shù)集 N上的反自反、反對(duì)稱、傳遞的二元關(guān)系可以用歸納定義法在 N 上定義 “ + ” 與 “ · ” 如下 ：[加法/乘法] 對(duì)任意的 n, m∈ N ，令 i)

6、m + 0 = m， m · 0 = 0 ii) m + n+ = (m + n ) +， m · n+ = m · n + m 。,引理 2 若 n∈ N，則 ∪ n＋ = n 。,證明：令 S = { n｜n∈N 且 ∪n＋ = n }顯然 S ? N 。 為證明 S = N ，只需 驗(yàn)證 S

7、 滿足：0∈S。因?yàn)?0∈N 且 ∪0＋ = ∪?＋ = ∪{ ? } = ? = 0。若 n∈S，則 n∈N 且 ∪n＋ = n。因此有 n＋∈N ，此外 ∪ ( n＋ ) ＋ = ∪ ( n＋∪{ n＋ } ) = ( ∪ n＋ ) ∪ (∪{ n＋ } ) = n ∪ n＋ = n＋ 。 所以 n＋∈S 。由自然數(shù)集合 N 歸納定義法的 iii), 由 1)

8、 和 2) 即知 S = N。,按上述方法構(gòu)造出來(lái)的自然數(shù)系統(tǒng) ＜N, +, ·＞ 滿足以下的皮亞諾 ( Peano ) 公理：P1：0∈ N ；P2：若 n∈ N ，則有唯一的后繼 n＋∈ N ；P3：若 n∈ N ，則 n＋ ≠ 0；P4：若 n, m∈N 且 n＋ = m＋， 則 n = m；P5：若 S ? N 滿足 （歸納

9、原理） i) 0∈S ii) 如果 n∈S，則 n＋∈S 則 S = N 。,證明：P1，P2 和 P5 分別為自然數(shù)集 N 歸納定義法的 i), ii) 和 iii)。P3 可以從引理 1 的 v) 直接推導(dǎo)出來(lái)。P4：若 n, m? N 且 n+ = m+ ， 則由 引理 2 可得：n = ∪n+ = ∪m+ = m 。,Peano公理說明： （1）0 是自然數(shù)

10、；（2）每一個(gè)自然數(shù) n 都有一個(gè)確定的后繼數(shù) n + ；（3）沒有以 0 為后繼的自然數(shù)；（4）每一個(gè)自然數(shù) n 的后繼 是唯一的；（5）自然數(shù)集合是 滿足 1)、2) 條件的極小集合。,（3）良基性：不存在一個(gè)自然數(shù)的無(wú)窮遞降序列 n1, n2, n3 , … , ni , ni+1 , … 使得 ni+1∈ ni 。 由自然數(shù)的定義可知，對(duì)于每一個(gè)自然數(shù)，比它小的 自然數(shù)總是有窮個(gè)

11、，并且 0 ∈ 1 ∈ 2 ∈ 3 ∈ …… 0 ? 1 ? 2 ? 3 ? ……,性質(zhì) 8.1（作為集合的自然數(shù)的性質(zhì)）:,（1）傳遞性：若 n1∈n2 且 n2∈n3 , 則 n1∈n3 。,（2）三歧性：對(duì)于任何兩個(gè)自然數(shù) n1，n2，下列三式 恰有一個(gè)成立：n1∈n2 , n1

12、= n2 , 或 n2∈n1 。,數(shù)學(xué)歸納法（第一數(shù)學(xué)歸納法）：設(shè) P (n) 是自然數(shù)集合上的性質(zhì)(或 謂詞), 如果能證明1) P(0) 是真；2) 對(duì)任何 n∈N, P (n) ? P (n+ )。則對(duì)所有 n∈N, P (n) 為真。,Peano公理(5)的極小化就是自然數(shù)集合定義中的極小化, 是數(shù)學(xué)歸納法的基礎(chǔ)。下面給出一個(gè)等價(jià)的數(shù)學(xué)歸納法:,數(shù)學(xué)歸納法是論域?yàn)樽匀粩?shù)集合的推理規(guī)則，可

13、形式表達(dá)如下： P(0) ? (?n) ( P(n) ? P(n+1) ) ? (?n) P(n),設(shè)k是某個(gè)自然數(shù)，如果要證明謂詞P(x)對(duì)所有x≥k的自然數(shù)成立，則上述原理可寫成： P(k) ? (?n)(n?k ? P(n)?P(n+1)) ?(?x)(x?k?P(x)),第一、第二歸納法對(duì)任意 n? N ，令 = N – Nn = { n, n+1, n+2, ? },第

14、二數(shù)學(xué)歸納法： 第二數(shù)學(xué)歸納法是一種更強(qiáng)形式的數(shù)學(xué)歸納法，它在證明對(duì)所有自然數(shù)x ，P(x)為真時(shí)，使用下述步驟： 假設(shè)對(duì)所有k<n， P(k)是真，推出P(n)為真，則(?x)P(x)為真。即 (?n)((?k)(k<n?P(k))? P(n) )?(?x)P(x).,,上述推論前提中包含了P（0）為真。因?yàn)榘裯=0代入上式后， k<0?P(k)為真，推

15、出(?k)(k<0?P(k))為真， (?k)(k<0?P(k)) ? P(0) 等價(jià)于P(0) 。因此兩個(gè)原理的假設(shè)是等價(jià)的。,證明： 設(shè)P(n)：n<2n （1）對(duì)于n=0, P(0)：0<20=1,因此P(0)為真.（2）對(duì)于任意的m∈N,假定P(m)是真,即P(m)：m<2m.（3）m+1 < 2m+1 ? 2m+ 2m = 2? 2m= 2m+1,即m+1 < 2m+1. 說明

16、P(m+1)為真.因此P(m) ?P(m+1),由數(shù)學(xué)歸納法,對(duì)于所有的n∈N, P(n)為真.,例8.1：證明n<2n,證明 ：設(shè)P(n)：2n＜n! (1) P(4) : 24<4!, 24=16，4!=24. P(4)成立 . (2) 設(shè)對(duì)于任何m＞4, P(m)為真,即2m＜m!. (3) 2?2m＜2 ?m!, 2m+1＜2 ?m!＜(m+1) ×m!=(m+1

17、)!, 即2m+1＜(m+1) ! 上式說明P(m+1)為真.因此,對(duì)于所有的n∈N , n≥4 , P(n)為真.,例8.2 證明對(duì)于任何n?4,2n<n! .,例8.3 證明所有n?2的整數(shù)能寫成質(zhì)數(shù)的乘積 .,證明： 對(duì)任意的n作歸納假設(shè),設(shè)對(duì)每個(gè)k,2?k<n能寫成質(zhì)數(shù) 的乘積, 證明n也能寫成質(zhì)數(shù)的乘積.證明分兩種情況：

18、 (1) 若n是質(zhì)數(shù),顯然它就是一個(gè)質(zhì)數(shù)的乘積. (2) 若n不是質(zhì)數(shù),則可寫成n=a?b,而2?a,b<n.根據(jù)假設(shè)a和b都可寫成質(zhì)數(shù)的乘積,所以n也能寫成質(zhì)數(shù)的乘積. 根據(jù)第二數(shù)學(xué)歸納法結(jié)論成立.,思考題,證明以下的二重歸納原理的正確性：設(shè) i0 , j0?N。假定對(duì)任意自然數(shù)i ? i0 及 j ? j0皆有 一個(gè)命題 P ( i, j ) 滿足：1) P ( i0 , j0 ) 真；2) 對(duì)任意

19、自然數(shù) k ? i0 及 l ? j0， 若P (k, l) 真，則P (k+1, l) 和 P (k, l+1)皆真。則對(duì)任意自然數(shù) i ? i0 及 j ? j0, P (i, j) 皆真。,證明：用第一歸納法 對(duì)于每個(gè) i ? i0，用 Q(i) 表示下列命題： 對(duì)于任意j ? j0 ，P (i, j) 皆真。下面驗(yàn)證：Q(i) 滿足第一歸納法i) Q( i0 )為真

20、，為此對(duì) j 施用第一歸納法）： a) P (i0 , j0) 為真； b) 若 P(i0, j) 為真，則 P( i0 , j+1 )為真； 由歸納法可知，Q(i0)為真。ii) 假設(shè)Q(i) 為真（i ? i0），即對(duì)于任意i ? i0，j ? j0，P (i, j)為真 則對(duì)于任意j ? j0，P( i+1, j) 為真，即 Q (i+1)為真。由 i) 和 ii) 可知，對(duì)于任意

21、i ? i0 ，Q (i) 皆真。所以，對(duì)于任意i ? i0，j ? j0， P (i, j) 為真。,,§ 8.2 基 數(shù),本節(jié)討論度量和比較 兩個(gè)集合大小的方法。重點(diǎn)掌握 等勢(shì)，有窮、無(wú)窮集合，可數(shù)無(wú)窮集合， 可數(shù)、不可數(shù)集合，無(wú)窮集合的性質(zhì)， 有窮集合、N 與 R 的基數(shù)，基數(shù)的比較。,比較兩個(gè)集合的大小： 1?

22、 計(jì)數(shù)法：先數(shù)出它們的元素個(gè)數(shù)，再加以比較。 2? 愚人比寶法：每次各取一，看哪個(gè)最后取完。 對(duì)無(wú)限集，方法 1? 失效。,什么叫做 數(shù)一個(gè)集合中元素個(gè)數(shù) ？在該集合與某個(gè)自然數(shù) 之間建立一個(gè)雙射。,等勢(shì),設(shè) A 和 B 為二集合，若存在從 A 到 B 的雙射，則稱 A 和 B 對(duì)等，或稱 A 和 B 等勢(shì)，記為 A ～ B。,例 設(shè) N = { 0 , 1 , 2 , …}, E = { 0 , 2

23、 , 4 , …} , 令 f : N ? E 為 f (n) = 2n, 其中 n∈N, 則 f 為雙射, 故 N ～ E。,等勢(shì)關(guān)系的性質(zhì)：對(duì)于任何集合 A , B , C ，均有： (1) A ~ A； (2) 若 A ~ B , 則 B ~ A； (3) 若 A ~ B , B ~ C , 則 A

24、 ~ C。即 等勢(shì)關(guān)系有自反性 , 對(duì)稱性和傳遞性，因此等勢(shì)是集合族上的等價(jià)關(guān)系。,,定義8.6：集合是有窮的，當(dāng)且僅當(dāng) 它與某個(gè)自然數(shù)等勢(shì)，否則就是無(wú)窮的。,例 8.7: 單位開區(qū)間 (0, 1) = { x | x?R ? 0 < x < 1 } 與實(shí)數(shù)集合 R 等勢(shì)。下面是 從 (0, 1) 到 R 的 一一對(duì)應(yīng)的幾何結(jié)構(gòu)示意圖,圖8.4 ( 0, 1 ) ~ R 圖,還可以建立 ( 0, 1 ) 到 R

25、 的雙射函數(shù)如下：,0,,,f (x) = tg ( ( x – 0.5 ) ? ) , 由函數(shù) f 的圖象可見， F 是從 ( 0, 1 ) 到 R 的雙射函數(shù)。,0,x,例：如果 a，b? R，a < b，則 (a，b) ～ R 。證：定義 f ：(a，b) → R 如下：x∈(a，b)，令 f (x) = tg [ π ( x- (a+b)／2 )／(b-a) ] ，若 x∈(a，b) 時(shí), 則π ( x

26、- (a+b)／2 )／(b-a) ? (-π/2, π/2)顯然f 是雙射，所以 (a，b) ～ R 。無(wú)窮集合可以與它本身的真子集 等勢(shì)任何無(wú)限集都如此，這正是無(wú)限集與有限集之間的本質(zhì)區(qū)別，也可以把它作為無(wú)限集的定義。,鴿籠原理（抽屜原理）,任何有限集都不能與它的真子集 對(duì)等。,這個(gè)定理也叫抽屜原理，可通俗表述為：“如果把 n+1 本書放進(jìn) n 個(gè)抽屜里，至少在一個(gè)抽屜里有兩本或兩本以上的書。”,上述原理可以導(dǎo)出有窮集

27、合與無(wú)窮集合的根本差別： 任何與自身真子集等勢(shì)的集合均是無(wú)窮集合 。,例子,把 s 個(gè)元素分成 t 個(gè)組，當(dāng)不能均勻分放時(shí)，必有一個(gè)組，其元素個(gè)數(shù)要超出 “ 平均數(shù) ” 。形式地?cái)⑹鰹椋憾ɡ恚喊?s ( s ? 1 ) 個(gè)元素分成 t 個(gè)組， 那么必存在 一個(gè)組，至少含有 ?s / t? 個(gè)元素。其中， ? ? 為 “ 向上取整 ” 記號(hào)， 如 ? 4/3? = 2。,例子,任意 13 個(gè)人，至少

28、有二人生日在同一個(gè)月；任意 50 個(gè)人中，至少有5人生日同月。,例：在 1, 2, ? , 2n 中任取 n+1個(gè)互不相同的數(shù)中, 必存在兩個(gè)數(shù), 其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)。,證明：任何正整數(shù) n 都可以表示成 n = 2 a ? b （這里 a = 0, 1, 2, ?且 b為奇數(shù)）設(shè)取出的 n+1 個(gè)數(shù)為 k1, k2, ?, kn+1，且 ki = 2 ai ? bi ，由

29、于 b1, b2, ?, bn+1 是奇數(shù)，共有 n+1個(gè)，并且 bi ? ki 。而在 { 1, 2, ? , 2n } 中只有 n 個(gè)不同的奇數(shù)，所以必存在 i, j (1 ? i < j ? n+1) 使得 bi = bj 。不妨設(shè) ki < kj，則有 kj / ki = 2 aj – ai為正整數(shù)，因此 kj是 ki的倍數(shù)。,例：任給 52 個(gè)整數(shù)，證明其中必有兩數(shù)之和（或之差）能被100整除。,證明：設(shè)

30、r 為任意整數(shù) n 被100 除的余數(shù)，則 r 均滿足： 0 ?r ? 99 。 這些余數(shù)可以構(gòu)成 51個(gè)抽屜如下： (0, 0), (1, 99), (2, 98), (3, 97) , ?, (49, 51), (50, 50) 任給 52 個(gè)整數(shù)，則必有兩個(gè)整數(shù) a 和 b 的余數(shù) ra和 rb 落在同一個(gè)抽屜中，若 ra和 rb落在(0, 0) 或 (50, 50)中，則a

31、 和 b之和、之差均能被100整除。若 ra和 rb落在 (i, 100-i) (1 ? i ? 49)中, 當(dāng) ra和 rb 取同一個(gè)數(shù)時(shí)，則 a 和 b之差能被100整除，否則a 和 b之和能被100整除。,,定理8.1：任意有窮集合 A 唯一地與一個(gè)自然數(shù)等勢(shì) 。,證明 : 設(shè)對(duì)于某兩個(gè)自然數(shù) m 和 n , A ~ m 且 A ~ n, 則 m ~ n。根據(jù)自然數(shù)的 三岐性 和 傳遞性 , 則

32、 m = n，或者 其中一個(gè)是另一個(gè)的真子集。因?yàn)?m ~ n , 所以 后一種可能 是不存在的 , 因此 只能是 m = n 。 證畢,定義8.7 ( 有窮集合的 基數(shù) )： 對(duì)于任意有窮集合 A , 存在唯一的自然數(shù) n , 使得 A ~ n, 稱 n 為 A 的基數(shù) , 記為 #A 。,集合的基數(shù),我們現(xiàn)在拓廣

33、集合中含有的元素個(gè)數(shù)這一概念，引進(jìn)集合的基數(shù)的概念。 A：＃(A)（ card (A) 或｜A｜）顯然，每個(gè)有限集都與唯一的自然數(shù) 對(duì)等。設(shè) n ∈N，若 A ～ n，則令 # (A) = n 。對(duì)于無(wú)限集的基數(shù)，我們規(guī)定特殊的記號(hào)，例如令 # ( N ) = ?0? 是希伯來(lái)語(yǔ)的第一個(gè)字母，念作阿列夫。,基數(shù)相等和大

34、小順序,定義： 設(shè) A 和 B 為二集合。1) 如果 A～B，就稱 A 和 B 的基數(shù)相等，記為 # (A) = # (B)。2) 如果存在從 A 到 B 的單射， 就稱 A 的基數(shù)小于等于 B 的基數(shù)，記為 #(A) ? #(B)， 或稱 B 的基數(shù)大于等于 A 的基數(shù)， 記為 #(B) ? #(A) 。3) 如果 #(A) ? #(B) 且 #(A) ≠ #(B)， 就

35、稱 A 的基數(shù)小于 B 的基數(shù)，記為 #(A) #(A)。,任何兩個(gè)基數(shù)都可以比較大小,設(shè) A 和 B 為任意兩個(gè)集合，則 #(A) ? #(B) ，或 #(B) ? #(A) ，二者之中至少有一個(gè)成立。（證明要用選擇公理）,基數(shù)的相等關(guān)系 “ = ” 是等價(jià)關(guān)系,設(shè) A、B 和 C為三集合，則有1） #(A) = #(A)；2）若 #(A) = #(B)，則 #(B) = #(A)；3

36、）若 #(A) = #(B) 且 #(B) = #(C)， 則 #(A) = #(C),基數(shù)的小于等于關(guān)系“ ? ”是半序,設(shè) A，B 和 C 為三集合，則有1) #(A) ? #(A)；2) 若 #(A) ? #(B) 且 #(B) ? #(A)，則#(A) = #(B)；3) 若 #(A) ? #(B) 且 #(B) ? #(C)，則#(A) ? #(C)。其中， 2）為著名的 Bernstein

37、定理。,基數(shù)的相等關(guān)系 “ = ” 是等價(jià)關(guān)系,設(shè)A、B和C為三集合，則有1） #(A) = #(A)；2）若 #(A) = #(B)，則 #(B) = #(A)；3）若 #(A) = #(B) 且 #(B) = #(C)， 則 #(A) = #(C),定義8.8 ( 基數(shù) ) 設(shè) F 是集合族 , ~ 是 F 上的等勢(shì)關(guān)系。關(guān)系 ~ 在 F 上的等價(jià)類 稱為 基數(shù)。對(duì)于 A ? F , A 所屬

38、的等價(jià)類用 #A 表示 , 稱之為 A 的基數(shù)。 對(duì)于 A , B ? F ： #A = #B ? A ~ B 。,定義8.9（可數(shù)無(wú)窮集合）：任何與自然數(shù)集合等勢(shì)的集合稱為 可數(shù)無(wú)窮集合。,可數(shù)無(wú)窮集合的基數(shù) ， 用 ?0 表示 ，讀作 阿列夫零 。,定義8.10（可數(shù)、不可數(shù)集合 ）：如果一個(gè)集合是有窮集合或是 可數(shù)無(wú)窮集合 , 就稱它為 可數(shù)集合 ； 如果一個(gè)集合是無(wú)窮的，而且不是可數(shù)

39、的 ，就稱它為不可數(shù)集合 。,無(wú)窮集的等價(jià)條件,定理 以下三個(gè)條件等價(jià)：1) A 為無(wú)窮集；2) A 有可數(shù)無(wú)窮子集；3) A 有與它對(duì)等的真子集。,,定理8.2：任何無(wú)窮集合 必含有 可數(shù)無(wú)窮子集。,證明：設(shè) A 是無(wú)窮集合, 可以順序地從 A 的子集中取元素。構(gòu)造一個(gè) 無(wú)窮序列 , 方法如下 :,從 A 中 選 a0

40、 從 A – { a0 } 中選 a1 從 A – { a0 , a1 } 中選 a2 ……

41、 從 A – { a0 , a1 , … , an-1 } 中選 an 而集合 A – { a0 , a1 , … , an } 是無(wú)窮集 , 不論取到何時(shí) ,

42、必有元素剩下 , 否則 A 就是個(gè)有窮集合 。繼續(xù)上述過程 , 可以得到一個(gè)沒有重復(fù)的無(wú)窮序列 , 它組成了 A 的一個(gè)可數(shù)子集 { a0 , a1 , a2, … } 。 證畢,,證明 ：設(shè) A 是可數(shù)無(wú)窮集合， S 是 A 的無(wú)窮子集，顯然 A ? N, 故有雙射函數(shù) f : N?A , f (n) = x, x?A，把A中的元素可以排列為: f (0), f (1), f

43、(2), …, 把不在 S 中的元素從這序列中去掉。 由于 S 是無(wú)窮集合，所以余下的元素仍然是無(wú)窮的，用 f (i0), f (i1), f (i2), … 來(lái)表示余下的元素，并確定函數(shù)g: N ? S, 使得 g (n) = f ( in ) ，則 g 是雙射函數(shù)，因此 S 是可數(shù)無(wú)窮的。,定理8.3：可數(shù)無(wú)窮集合的無(wú)窮子集 必是 可數(shù)無(wú)窮的。,,定理 # (B) ? # (A) iff 存

44、在從 A 到 B 的滿射。 證明：i) 設(shè) f：A→B 為滿射，則 f 有右逆 g : B→A 使得 f ? g = IB，因?yàn)?IB 是單射，所以 g 是單射，故 #(B) ? #(A) 。ii) 若 #(B) ? #(A)，則有單射 g : B→A， g 有左逆 f : A→B 使得 f ? g = IB 。因?yàn)?IB 是 滿射， 所以 f 是滿射。,如圖 8.2所示，函數(shù) ? 是 從 N × N

45、到 N 的雙射： ? (m, n) = ( m + n ) ( m + n + 1)/2 + m = [ (m + n)2 + 3 m + n] / 2 ? (m, n) 的值 寫在坐標(biāo)為 (m, n) 的點(diǎn)上。,圖8.2 N × N ~ N,例8.5： 集合 N × N 與集合 N 等勢(shì)。,,,,,,m,n

46、,例8.6 自然數(shù)集合 N 與有理數(shù)集合 Q 等勢(shì), 即 N ~ Q 。,圖 8.3 N ~ Q,例 8.8 設(shè) Z = {… , -2 , -1 , 0 , 1 , 2 , …}, 若列舉 Z 的元素 , 就能建立 N 到 Z 的一一對(duì)應(yīng)如下 :,0,1,3,4,5,0,-1,1,-2,2,2,-3,,,,,,,…,…,這個(gè)對(duì)應(yīng) Z ~ N , 也可以用一個(gè)雙射函數(shù) f : N?Z 來(lái)表示：,,可數(shù)無(wú)窮集合是無(wú)

47、窮集合中十分重要的一類，可以證明:可數(shù)無(wú)窮集合的并集和可數(shù)無(wú)窮集合的笛卡兒乘積都仍然是可數(shù)無(wú)窮集合。,f(n) =,,n/2 n是偶數(shù),-(n+1)/2 n是奇數(shù),{,至此已證明了：偶數(shù)集E ~ N , N?N ~ N , Q~N , Z ~ N ,可見：偶數(shù)集合、平面上整格點(diǎn)的集合、有理數(shù)集合、整數(shù)集合都是可數(shù)無(wú)窮集合。,定理：實(shí)數(shù)集合 R 是 不可數(shù)的 。,基數(shù)的個(gè)數(shù)也是無(wú)限的，且無(wú)最大

48、者,對(duì)每個(gè)集合 A，皆有 # (A) < # ? (A)。證明：i) 定義 g ：A → ? (A) 為 g (a) = { a }顯然 g 是內(nèi)射，所以 # (A) ? # ? (A) 。ii) 用反證法來(lái) 證明： # (A) ≠ # ? (A)假設(shè) #(A) = # ?(A)，則有雙射 f：A→ ?(A)。令 B = { a｜a ∈A 且 a ? f

49、 (a) }則 B∈ ?(A)。因 f 為雙射，故有 t∈A 使 f (t) = B 。（1） 若 t∈B，按 B 的定義，t ? f (t)，即 t ? B ；（2） 若 t ?B，即 t ? f (t)。而按 B 的定義，t∈B?？傊?t∈B 當(dāng)且僅當(dāng) t ? B。 這是一個(gè)矛盾。故假設(shè)有誤，所以必有 # (A) ≠ # ?(A) 。由 i) 和 ii) 知， # (A) < # ?(

50、A) 。,,定理8.4：實(shí)數(shù)集合 R 是不可數(shù)的 。,證明 ：設(shè)集合 S = { x | x?( 0 , 1 ) } 假設(shè) S 是可數(shù)的，于是能夠把 S 的元素排列成無(wú)窮序列S0 , S1 , S2 , … Sn , … 已知 Si 是0和1之間的實(shí)數(shù) , 而任何小于 1的正數(shù) s 可以表示為 : s = 0.y1y2y3… 這里 yi ? {0 , 1 , 2 ,

51、 … , 9},將實(shí)數(shù)集合S 的元素S1 , S2 , S3 , … Sn , … 表示成： S0 = 0.a11a12a13 … S1 = 0.a21a22a23 … … Sn = 0.an1an2an3 … …,然后 ,

52、 構(gòu)造一個(gè)實(shí)數(shù) r = 0.b1b2b3 … bn … , 其中 bj ( j= 1 , 2 , 3 , …)按下列原則選取 : 若 ajj ? 1 , 則取 bj=1 ; 若ajj=1 , 則取 bj=2 . 在位置 1 上 r 與 S1 不同 , 在位置 2上r 與 S2 也不同 , …等等 . 所以 r 不同于 S1 , S2 , S3 , … Sn , … 這表明 r ? S

53、 . 從而導(dǎo)致矛盾 . 因此 S 是不可數(shù)的 . 又因?yàn)閷?shí)數(shù)集合 R 和集合 S 是等勢(shì)的 , 從而 R 也是不可數(shù)的 . 證畢 .,與集合 R 等勢(shì)的集合的基數(shù) , 用 ?來(lái)表示 , 并稱為連續(xù)統(tǒng)的勢(shì) . # ? (N) 記為 ?,例：證明 # ? (N)

54、= # (R) 。證明 全體從N到N的嚴(yán)格單調(diào)遞增函數(shù)組成的集合的基數(shù)大于 ?0 。,例： # ( R ? R ) = ?,定義 8.14：若#A = ? , #B = ? , 且 A ? B , 則稱 ? 小于 ? , 記為 ? < ? .,因?yàn)樽匀粩?shù)集合是實(shí)數(shù)集合的真子集 , 由定理 8.4的證明 可知 , 有 N ? R 和 ?0 < C ;又因?yàn)槿魏螣o(wú)窮集合都包含一個(gè)可數(shù)無(wú)窮子集 , 故 ?

55、0 是最小的無(wú)窮基數(shù) . 即對(duì)于任何無(wú)窮集合 A , 有 N A ; 對(duì)任何無(wú)窮基數(shù) k , 有?0 ?k .,定理 8.5 對(duì)于任意集合 A , A ? ? (A) , ? (A)是 A 的冪集 .,證明： (1) 設(shè) f : A ? ? (A) ,對(duì)每一個(gè) a , a ? A . f(a) = { a } ，顯然 f 是單射 . 故 A ? (A) .,(2) 假設(shè)存在一雙射函數(shù) g: A ? ?

56、(A) .如果 a ? g (a) ,就稱 a 為 A 的內(nèi)部元素 ;如果 a ? g (a) , 則稱 a 是 A 的外部元素 .,設(shè) B 是 A 的外部元素的集合 , 即 B ={ x | x ? A ? x ? g (x)}顯然 , B ? A , 所以 B ? ? (A) .,因?yàn)?g 是滿射的 , 就必然存在這樣一個(gè)元素 b ? A ,使得 g(b) = B .,現(xiàn)在存在兩種情況 , b ? B 或 b ?

57、 B . b ? B ? b ? A ? b ? g (b) ? b ? A ? b ? B ( 因?yàn)間(b) = B )這就推出了矛盾 ,故 g 不是一個(gè)雙射函數(shù) . 從而證得A ? ? (A) . 證畢.,若用 ? 和 2? 分別表示 A 和 ? (A) 的基數(shù) , 顯然應(yīng)有? < 2? .,可以證明， ? (N) 的基數(shù)是 C（即? (N) 與