離散數(shù)學(xué)：第9章 集合的基數(shù)

1、 1第第9 9章章 集合的基數(shù)集合的基數(shù)離散數(shù)學(xué)離散數(shù)學(xué) 2本章說(shuō)明本章說(shuō)明q本章的主要內(nèi)容本章的主要內(nèi)容集合的等勢(shì)及其性質(zhì)集合的等勢(shì)及其性質(zhì)重要的等勢(shì)或不等勢(shì)的結(jié)果重要的等勢(shì)或不等勢(shì)的結(jié)果集合的優(yōu)勢(shì)及其性質(zhì)集合的優(yōu)勢(shì)及其性質(zhì)自然數(shù)與自然數(shù)集合自然數(shù)與自然數(shù)集合集合的基數(shù)集合的基數(shù)可數(shù)集可數(shù)集 39.1 9.1 集合的等勢(shì)與優(yōu)勢(shì)集合的等勢(shì)與優(yōu)勢(shì)9.2 9.2 集合的基數(shù)集合的基數(shù) 本章小結(jié)本章小結(jié) 習(xí)題習(xí)題 作業(yè)作業(yè)本章內(nèi)容本章內(nèi)容 4定義定義9.19.1 設(shè)設(shè)A, BA, B是集合，如果存在著從是集合，如果存在著從A A到到B B的的雙射函數(shù)雙射函數(shù)，就，就稱(chēng)稱(chēng)A A和和B B是等勢(shì)是等勢(shì)（

2、same cardinality）的的，記作，記作ABAB。 如果如果A A不與不與B B等勢(shì)，則記作等勢(shì)，則記作A BA B。9.1 集合的等勢(shì)與優(yōu)勢(shì)集合的等勢(shì)與優(yōu)勢(shì)q通俗的說(shuō)，集合的勢(shì)是量度集合所含元素多少的量。通俗的說(shuō)，集合的勢(shì)是量度集合所含元素多少的量。q集合的勢(shì)越大，所含的元素越多。集合的勢(shì)越大，所含的元素越多。 5（1）ZN。20:,( )210 xxfZNf xxx則則f是是Z到到N的雙射函數(shù)。的雙射函數(shù)。 從而證明了從而證明了ZN。等勢(shì)集合的實(shí)例等勢(shì)集合的實(shí)例(1)(1) 6等勢(shì)集合的實(shí)例等勢(shì)集合的實(shí)例(2)(2)（2） NNN。(1)():,(,)2mnmnfNNNfm nm

3、 雙射函數(shù)雙射函數(shù) 7等勢(shì)集合的實(shí)例等勢(shì)集合的實(shí)例(3)(3)（3 3）NQNQ。 把所有形式為把所有形式為p p/ /q q ( (p p, ,q q為整數(shù)且為整數(shù)且q q0) 0) 的數(shù)排成一張表。的數(shù)排成一張表。-2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/

4、4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414以以0/10/1作為第一個(gè)數(shù)，按照箭頭規(guī)定的順序可以作為第一個(gè)數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍數(shù)遍”表中表中所有的數(shù)。計(jì)數(shù)過(guò)程中必須跳過(guò)第二次以及以后各次所遇到的所有的數(shù)。計(jì)數(shù)過(guò)程中必須跳過(guò)第二次以及以后各次所遇到的同一個(gè)有理數(shù)。同一個(gè)有理數(shù)。 8等勢(shì)集合的實(shí)例等勢(shì)集合的實(shí)例(4)(4)（4）(0,1)R。 其中實(shí)數(shù)區(qū)間其中實(shí)數(shù)區(qū)間 (0,1)=x| xR0 x1。21:(0,1),( )tan2xfRf x令雙射函數(shù)令雙射函數(shù)則則 f 是是(0,1)到到R的雙射函數(shù)。從而證明了的

5、雙射函數(shù)。從而證明了(0,1)R 。 9等勢(shì)集合的實(shí)例等勢(shì)集合的實(shí)例(5)(5)（5 5）0,1(0,1)。 其中其中(0,1)和和0,1分別為實(shí)數(shù)開(kāi)區(qū)間和閉區(qū)間。分別為實(shí)數(shù)開(kāi)區(qū)間和閉區(qū)間。211/201/21( )1/21/2 ,1,2,.nnxxf xxnxx其它雙射函數(shù)雙射函數(shù) f : 0,1(0,1)，n n3 32 22 21 12 21 12 21 12 21 110 02 22 21 12 21 12 2n n5 54 43 32 21 12 21 12 21 12 21 12 2 10等勢(shì)集合的實(shí)例等勢(shì)集合的實(shí)例(6)(6)（6 6）對(duì)任何）對(duì)任何a, bR，ab， 0,1a,

6、b。 雙射函數(shù)雙射函數(shù)f：0,1a,b，f(x)(b a)x+a。 11例例9.29.2 設(shè)設(shè)A為任意集合，則為任意集合，則P(A)0,1A。構(gòu)造構(gòu)造f：P(A)0,1A， f(A )= A ， A P(A)。其中其中 A 是集合是集合A 的特征函數(shù)的特征函數(shù)。(1)(1)易證易證 f 是單射的是單射的。(2)(2)對(duì)于任意的對(duì)于任意的 g0,1A， 那么有那么有 g：A0,1。令令 B=x| xAg(x)=1 則則B A，且且 B=g，即即 BP(A)，使得使得f(B)=g。 所以所以 f 是滿(mǎn)射的。是滿(mǎn)射的。由等勢(shì)定義得由等勢(shì)定義得P(A)0,1A。例例9.29.2證明證明復(fù)習(xí)復(fù)習(xí) 12定

7、理定理9.19.1 設(shè)設(shè)A，B，C是任意集合，是任意集合，（1）AA。（2）若若AB，則則BA。（3）若若AB，BC，則則AC。（1 1） IA是從是從A到到A的雙射，因此的雙射，因此AA。（2） 假設(shè)假設(shè)AB ，存在，存在 f : : AB是雙射，是雙射，那么那么 f 1 : : BA是從是從B到到A的雙射，所以的雙射，所以BA。（3） 假設(shè)假設(shè)AB，BC，存在存在 f : :AB，g: :BC是雙射，是雙射，則則f g : : AC是從是從 A 到到 C 的雙射的雙射。所以所以AC。等勢(shì)的性質(zhì)等勢(shì)的性質(zhì)證明證明 13q N Z Q NNq R 0,1 (0,1)q 任何的實(shí)數(shù)區(qū)間（開(kāi)區(qū)間、

8、閉區(qū)間以及半開(kāi)半閉的區(qū)間）任何的實(shí)數(shù)區(qū)間（開(kāi)區(qū)間、閉區(qū)間以及半開(kāi)半閉的區(qū)間）都與實(shí)數(shù)集合都與實(shí)數(shù)集合R R等勢(shì)。等勢(shì)。q 問(wèn)題：?jiǎn)栴}：N N和和R R是否等勢(shì)？是否等勢(shì)？若干等勢(shì)集合若干等勢(shì)集合 14（1）如果能證明）如果能證明N 0,1，就可以斷定就可以斷定N R。 只需證明任何函數(shù)只需證明任何函數(shù)f：N0,1都不是滿(mǎn)射的。都不是滿(mǎn)射的。 構(gòu)造一個(gè)構(gòu)造一個(gè)0,1區(qū)間的小數(shù)區(qū)間的小數(shù)b，使得使得b在在N中不存在原像。中不存在原像。（2）任取函數(shù)）任取函數(shù)f：AP(A)，構(gòu)造構(gòu)造BP(A)，使得使得B在在A中不存在中不存在原像。原像?；蛘呤褂梅醋C法。或者使用反證法。定理定理9.29.2 康托定理

9、康托定理（1）N R。（2）對(duì)任意集合對(duì)任意集合A都有都有A P(A)?？低卸ɡ砜低卸ɡ矸治龇治?15（1 1）首先規(guī)定）首先規(guī)定0,1中數(shù)的表示。中數(shù)的表示。 對(duì)任意的對(duì)任意的x0,1，令令x = 0. .x1x2 , （0 xi 9） 注意：為了保證表示式的唯一性，如果遇到注意：為了保證表示式的唯一性，如果遇到0.249990.24999，則將，則將x x表表示為示為0.250000.25000。 設(shè)設(shè) f:N0,1是從是從N到到0,1的任何一個(gè)函數(shù)。的任何一個(gè)函數(shù)。f的所有函數(shù)值為的所有函數(shù)值為： f(0)=0.a1(1)a2(1) f(1)=0.a1(2)a2(2) f(n 1)=0.

10、a1(n)a2(n) 令令y的表示式為的表示式為0.b1b2，并且滿(mǎn)足并且滿(mǎn)足bi ai(i)，i=1,2, ,，則則y0,1， 但但y與上面列出的任何一個(gè)函數(shù)值都不相等與上面列出的任何一個(gè)函數(shù)值都不相等。即即f不是滿(mǎn)射的。不是滿(mǎn)射的。 所以所以，N R?？低卸ɡ砜低卸ɡ?16康托定理康托定理q 假設(shè)假設(shè)A AP(A)，則必有函數(shù)則必有函數(shù) f : AP(A)是雙射函數(shù)。是雙射函數(shù)。如下構(gòu)造集合如下構(gòu)造集合B：Bx| xAx f (x) 可知可知 BP(A)。于是存在唯一一個(gè)元素于是存在唯一一個(gè)元素bA，使得使得 f(b)B。若若bB，則由則由B的定義知，的定義知，b f (b)，即即 b B

11、，矛盾矛盾。若若b B，則則b f (b)，于是由于是由B的定義知，的定義知， bB，矛盾。矛盾。 17（2 2）設(shè)）設(shè)g：AP(A)是從是從A到到P(A)的任意函數(shù)，的任意函數(shù)， 如下構(gòu)造集合如下構(gòu)造集合B：Bx| xAx g(x) 則則BP(A)。 但是但是對(duì)任意對(duì)任意xA，都有都有xB x g(x) 所以，對(duì)任意的所以，對(duì)任意的xA都有都有Bg(x)，即即B ran ran g 即即P(A) 中存在元素中存在元素B，在在A中找不到原像。中找不到原像。 所以所以，g不是滿(mǎn)射的。不是滿(mǎn)射的。 所以所以， A P(A)。說(shuō)說(shuō)明明康托定理康托定理q根據(jù)這個(gè)定理可以知道根據(jù)這個(gè)定理可以知道N P(

12、N)。q綜合前面的結(jié)果，可知綜合前面的結(jié)果，可知N 0,1N 。q實(shí)際上，實(shí)際上，P(N)P(N)，0,10,1N N和和R R都是比都是比N“N“更大更大”的集合。的集合。 18定義定義9.29.2（1 1） 設(shè)設(shè)A, B是集合，如果存在從是集合，如果存在從A到到B的的單射單射函數(shù)，就稱(chēng)函數(shù)，就稱(chēng)B優(yōu)優(yōu)勢(shì)于勢(shì)于A，記作記作AB。 如果如果B不是優(yōu)勢(shì)于不是優(yōu)勢(shì)于A， 則記作則記作AB。（2 2）設(shè)設(shè)A, B是集合，若是集合，若AB且且A B，則稱(chēng)則稱(chēng)B真優(yōu)勢(shì)于真優(yōu)勢(shì)于A，記記作作AB。如果如果B不是真優(yōu)勢(shì)于不是真優(yōu)勢(shì)于A，則記作則記作AB。 例如：例如：N NN RA P(A)N RA P(A

13、) R N N N優(yōu)勢(shì)優(yōu)勢(shì)RN 19定理定理9.39.3 設(shè)設(shè)A, B, C是任意的集合，則是任意的集合，則（1）A A。（2）若若A B且且B A，則則AB。（3）若若A B且且B C, 則則A C 。證明：證明：（1 1）IA是是A到到A的單射的單射，因此因此A A。（2 2）證明略。）證明略。（3 3）假設(shè)）假設(shè)A B且且B C，那么存在單射，那么存在單射 f:AB:AB，g:BC:BC， 于是于是 f g：AC也是單射的，因此也是單射的，因此A C 。優(yōu)勢(shì)的性質(zhì)優(yōu)勢(shì)的性質(zhì)說(shuō)說(shuō)明明q 該定理為證明集合之間的等勢(shì)提供了有力的工具該定理為證明集合之間的等勢(shì)提供了有力的工具。q 構(gòu)造兩個(gè)單射構(gòu)

14、造兩個(gè)單射f：A AB B 和和 g g：B BA A函數(shù)容易集合等勢(shì)函數(shù)容易集合等勢(shì)。 20例題例題例題：例題：證明證明0,10,1與與(0,1)(0,1)等勢(shì)。等勢(shì)。證明：證明：構(gòu)造兩個(gè)單射函數(shù)構(gòu)造兩個(gè)單射函數(shù)f: (0,1)0,1: (0,1)0,1，f( (x) )xg: 0,1(0,1): 0,1(0,1)，g( (x) )x/2+1/4/2+1/4 21證明證明 0,1N0,1)(1) 設(shè)設(shè)x 0,1)，0.x1x2是是x的的二進(jìn)制表示二進(jìn)制表示。 為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無(wú)數(shù)個(gè)為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無(wú)數(shù)個(gè)1。 例如例如 x0.1010111，

15、應(yīng)按規(guī)定記為應(yīng)按規(guī)定記為0.1011000。 對(duì)于對(duì)于x，如下定義如下定義f：0,1)0,1N，使得使得 f(x) = tx，且且tx：N0,1， tx(n) = xn+1，n = 0,1,2, 例如例如 x = 0.10110100，則對(duì)應(yīng)于則對(duì)應(yīng)于x的函數(shù)的函數(shù)tx是是： n 0 1 2 3 4 5 6 7tx(n) 1 0 1 1 0 1 0 0 易見(jiàn)易見(jiàn)tx0,1N，且對(duì)于且對(duì)于x,y0,1)，xy，必有必有tx ty， 即即f(x) f(y)。 所以所以，f：0,1)0,1N是單射的。是單射的。 22(2) 定義函數(shù)定義函數(shù)g：0,1N0,1)。 g的映射法則恰好與的映射法則恰好與

16、f 相反，相反， 即即 t0,1N，t：N0,1，g(t)=0.x1x2, 其中其中xn+1=t(n)。 但不同的是，將但不同的是，將0.x1x2看作數(shù)看作數(shù)x的十進(jìn)制表示的十進(jìn)制表示。 例如例如t1，t20,1N，且且g(t1)0.0111，g(t2)0.1000， 若將若將g(t1)和和g(t2)都看成二進(jìn)制表示，則都看成二進(jìn)制表示，則g(t1)g(t2)； 但若看成十進(jìn)制表示，則但若看成十進(jìn)制表示，則g(t1)g(t2)。 所以所以， g：0,1N0,1) 是單射的。是單射的。 根據(jù)根據(jù)定理定理9.3，有，有0,1N0,1)。證明證明 0,1N0,1) 23總結(jié)總結(jié)q N Z Q NNq

17、 R a,b (c,d) 0,1N P(N)其中其中a,b，(c,d)代表任意的實(shí)數(shù)閉區(qū)間和開(kāi)區(qū)間代表任意的實(shí)數(shù)閉區(qū)間和開(kāi)區(qū)間。q 0,1A P(A)q N Rq A P(A) 249.2 9.2 集合的基數(shù)集合的基數(shù) q 上一節(jié)我們只是抽象地討論了集合的等勢(shì)與優(yōu)勢(shì)。上一節(jié)我們只是抽象地討論了集合的等勢(shì)與優(yōu)勢(shì)。q 本節(jié)將進(jìn)一步研究度量集合的勢(shì)的方法。本節(jié)將進(jìn)一步研究度量集合的勢(shì)的方法。q 最簡(jiǎn)單的集合是有窮集。盡管前面已經(jīng)多次用到最簡(jiǎn)單的集合是有窮集。盡管前面已經(jīng)多次用到“有窮集有窮集”這一概念，當(dāng)時(shí)只是直觀地理解成含有有限多個(gè)元素的這一概念，當(dāng)時(shí)只是直觀地理解成含有有限多個(gè)元素的集合，但一直

18、沒(méi)有精確地給出有窮集的定義。為解決這個(gè)集合，但一直沒(méi)有精確地給出有窮集的定義。為解決這個(gè)問(wèn)題我們需要先定義自然數(shù)和自然數(shù)集合。問(wèn)題我們需要先定義自然數(shù)和自然數(shù)集合。 25定義定義9.3 9.3 設(shè)設(shè)a為為集合，稱(chēng)集合，稱(chēng)aa 為為a的的后繼后繼，記作，記作a+，即即 a+=aa。 例例9.39.3 考慮空集的一系列后繼?？紤]空集的一系列后繼。 + = = + = += = ,= , + + =,+= ,= ,= , +, + 后繼后繼 說(shuō)說(shuō)明明q 前邊的集合都是后邊集合的元素。前邊的集合都是后邊集合的元素。q 前邊的集合都是后邊集合的子集。前邊的集合都是后邊集合的子集。 26利用后繼的性質(zhì)，可

19、以考慮以構(gòu)造性的方法用集合來(lái)給出自利用后繼的性質(zhì)，可以考慮以構(gòu)造性的方法用集合來(lái)給出自然數(shù)的定義，然數(shù)的定義，即即 0=1=0+ 02=1+ ,0,132+,+, 0,1,2 n0, 1, , n 1說(shuō)說(shuō)明明自然數(shù)的定義自然數(shù)的定義 這種定義沒(méi)有概括出自然數(shù)的共同特征。這種定義沒(méi)有概括出自然數(shù)的共同特征。 27定義定義9.4 9.4 設(shè)設(shè)A為為集合，如果滿(mǎn)足下面的兩個(gè)條件：集合，如果滿(mǎn)足下面的兩個(gè)條件：（1）A（2） a(aAa+A) 稱(chēng)稱(chēng)A是是歸納集歸納集。例如例如：下面的集合：下面的集合, +, +, +, +, +, +, , a, a+, a+, a+, 都是歸納集。都是歸納集。歸納集

20、歸納集 28定義定義9.59.5 自然數(shù)自然數(shù)（1 1）一個(gè)）一個(gè)自然數(shù)自然數(shù)n是屬于每一個(gè)歸納集的集合。是屬于每一個(gè)歸納集的集合。（2 2）自然數(shù)集自然數(shù)集N是所有歸納集的交集。是所有歸納集的交集。說(shuō)明說(shuō)明：根據(jù)定義根據(jù)定義9.5得到的自然數(shù)集得到的自然數(shù)集 N 恰好由恰好由, +, +, +,等集合構(gòu)成。而這些集合正是構(gòu)造性方法所定義的等集合構(gòu)成。而這些集合正是構(gòu)造性方法所定義的全體自然數(shù)。全體自然數(shù)。 例如：例如：自然數(shù)都是集合，集合的運(yùn)算對(duì)自然數(shù)都適用。自然數(shù)都是集合，集合的運(yùn)算對(duì)自然數(shù)都適用。250,10,1,2,3,40,1,2,3,45340,1,20,1,2,30,1,23 4

21、-20,1,2,3-0,1=2,3 230,10,1,2, 自然數(shù)自然數(shù)n n和自然數(shù)集合和自然數(shù)集合N N的定義的定義 29P(1)P(0),00,1230,10,1,2f | f：0,1,20,1f0,f1,f7其中其中f0,f1 ,f2 ,f3 ,f4 ,f5 ,f6 ,f7 , 舉例舉例 30（1） 對(duì)任何自然數(shù)對(duì)任何自然數(shù)n，有有n n。（2） 對(duì)任何自然數(shù)對(duì)任何自然數(shù)n, m，若若m n，則則m n。（3） 對(duì)任何自然數(shù)對(duì)任何自然數(shù)n, m，若若mn，則則m n。（4） 對(duì)任何自然數(shù)對(duì)任何自然數(shù)n和和m，以下三個(gè)式子：以下三個(gè)式子： mn，m n， nm必成立其一且僅成立其一。必成

22、立其一且僅成立其一。（5） 自然數(shù)的相等與大小順序自然數(shù)的相等與大小順序 對(duì)任何自然數(shù)對(duì)任何自然數(shù)m和和n，有有m = n m n m n mn 自然數(shù)的性質(zhì)自然數(shù)的性質(zhì) 31定義定義9.69.6 有窮集、無(wú)窮集有窮集、無(wú)窮集（1 1）一個(gè)集合是）一個(gè)集合是有窮的有窮的當(dāng)且僅當(dāng)它與某個(gè)自然數(shù)等勢(shì)；當(dāng)且僅當(dāng)它與某個(gè)自然數(shù)等勢(shì)；（2 2）如果一個(gè)集合不是有窮的，就稱(chēng)作）如果一個(gè)集合不是有窮的，就稱(chēng)作無(wú)窮集無(wú)窮集。例如：例如：q a,b,c是有窮集，是有窮集， 因?yàn)橐驗(yàn)?0,1,2，且，且a,b,c0,1,23qN和和R都是無(wú)窮集，都是無(wú)窮集， 因?yàn)闆](méi)有自然數(shù)與因?yàn)闆](méi)有自然數(shù)與N和和R等勢(shì)。等勢(shì)。q

23、任何有窮集只與唯一的自然數(shù)等勢(shì)。任何有窮集只與唯一的自然數(shù)等勢(shì)。說(shuō)說(shuō)明明有窮集和無(wú)窮集有窮集和無(wú)窮集 32定義定義9.7 9.7 （1 1）對(duì)于有窮集合）對(duì)于有窮集合A，稱(chēng)與稱(chēng)與A等勢(shì)的那個(gè)唯一的自然數(shù)為等勢(shì)的那個(gè)唯一的自然數(shù)為A的基的基數(shù)數(shù)，記作記作card A，即即 card A n A n （對(duì)于有窮集對(duì)于有窮集A， card A也可以記作也可以記作|A|）（2 2）自然數(shù)集合自然數(shù)集合N的基數(shù)記作的基數(shù)記作0，即，即card N =0（3 3）實(shí)數(shù)集實(shí)數(shù)集R的基數(shù)記作的基數(shù)記作（讀作阿列夫），即（讀作阿列夫），即card R =基數(shù)基數(shù)( (cardinality) ) 33定義定義9

24、.8 9.8 設(shè)設(shè)A, B為集合，則為集合，則（1）card Acard B AB（2）card Acard B A B（3）card A card B card Acard Bcard Acard B例如：例如：q card Z card Q card NN 0q card P(N) card 2N card a,b card (c,d) q 0說(shuō)明說(shuō)明：集合的基數(shù)就是集合的勢(shì)，基數(shù)越大，勢(shì)就越大。：集合的基數(shù)就是集合的勢(shì)，基數(shù)越大，勢(shì)就越大?；鶖?shù)的相等和大小基數(shù)的相等和大小 34關(guān)于基數(shù)的說(shuō)明關(guān)于基數(shù)的說(shuō)明 q 由于對(duì)任何集合由于對(duì)任何集合A都滿(mǎn)足都滿(mǎn)足A P(A)，所以有所以有 card

25、 A card P(A)，這說(shuō)明這說(shuō)明不存在最大的基數(shù)不存在最大的基數(shù)。q 將已知的基數(shù)按從小到大的順序排列就得到：將已知的基數(shù)按從小到大的順序排列就得到： 0, 1, 2, , n, , 0, , q 0, 1, 2, n, 是全體自然數(shù)，是是全體自然數(shù)，是有窮基數(shù)有窮基數(shù)。q 0, , 是是無(wú)窮基數(shù)無(wú)窮基數(shù)。q 0是最小的無(wú)窮基數(shù)是最小的無(wú)窮基數(shù)，后面還有更大的基數(shù)，如后面還有更大的基數(shù)，如 card P(R)等。等。 35可數(shù)集可數(shù)集定義定義9.99.9 設(shè)設(shè)A為集合，若為集合，若card A0，則稱(chēng)則稱(chēng)A為為可數(shù)集可數(shù)集(enumerable)或或可列集?？闪屑?。例如：例如： q a,

26、b,c、5、整數(shù)集整數(shù)集Z、有理數(shù)集有理數(shù)集Q、NN等都是可數(shù)集。等都是可數(shù)集。q 實(shí)數(shù)集實(shí)數(shù)集R不是可數(shù)集，與不是可數(shù)集，與R等勢(shì)的集合也不是可數(shù)集。等勢(shì)的集合也不是可數(shù)集。 對(duì)于任何的可數(shù)集，都可以找到一個(gè)對(duì)于任何的可數(shù)集，都可以找到一個(gè)“數(shù)遍數(shù)遍”集合中全體集合中全體元素的順序?；仡櫱斑叺目蓴?shù)集，特別是無(wú)窮可數(shù)集，都元素的順序。回顧前邊的可數(shù)集，特別是無(wú)窮可數(shù)集，都是用這種方法來(lái)證明的。是用這種方法來(lái)證明的。說(shuō)說(shuō)明明 36（1 1）可數(shù)集的任何子集都是可數(shù)集。）可數(shù)集的任何子集都是可數(shù)集。 一個(gè)集合的無(wú)限子集若不可數(shù)，則該集合也不可數(shù)。一個(gè)集合的無(wú)限子集若不可數(shù)，則該集合也不可數(shù)。（2

27、2）兩個(gè)可數(shù)集的并是可數(shù)集。）兩個(gè)可數(shù)集的并是可數(shù)集。（3 3）兩個(gè)可數(shù)集的笛卡兒積是可數(shù)集。）兩個(gè)可數(shù)集的笛卡兒積是可數(shù)集。（4 4）可數(shù)個(gè)可數(shù)集的笛卡兒積仍是可數(shù)集。）可數(shù)個(gè)可數(shù)集的笛卡兒積仍是可數(shù)集。（5 5）無(wú)窮集）無(wú)窮集A A的冪集的冪集P P( (A A) )不是可數(shù)集。不是可數(shù)集?？蓴?shù)集的性質(zhì)可數(shù)集的性質(zhì) 37例例9.49.4 求下列集合的基數(shù)。求下列集合的基數(shù)。（1）Tx | x是單詞是單詞“BASEBALL”中的字母中的字母（2）Bx | xRx2=92x=8（3）CP(A), A=1, 3, 7, 11（1）由由TB, A, S, E, L知知，card T5。（2）由由B

28、可知，可知，card B0。（3）由由|A|4可知可知，card Ccard P(A)|P(A)|2416。解答解答例例9.4 9.4 38方法一方法一由由card A0，card Bn，可知可知A, B都是可數(shù)集。都是可數(shù)集。令令A(yù)=a0, ,a1 , , a2 , , ，B=b0 , , b1 , , b2 , , , , bn 1。對(duì)任意的對(duì)任意的， AB，有有 i kj l定義函數(shù)定義函數(shù) f：ABNf()in+j, i0,1, j0,1,n 1由于由于 f 是是AB到到N的雙射函數(shù)，所以的雙射函數(shù)，所以card ABcard N。例例9.59.5解答解答例例9.59.5 設(shè)設(shè)A, B

29、為集合為集合，且且card A0， card Bn，n是自然數(shù)是自然數(shù)，n0。求求card AB。 39例例9.59.5方法二方法二因?yàn)橐驗(yàn)閏ard A0，card Bn，所以所以A, B都是可數(shù)集。都是可數(shù)集。根據(jù)性質(zhì)（根據(jù)性質(zhì)（3）可知，）可知，AB也是可數(shù)集，所以，也是可數(shù)集，所以，card AB0 當(dāng)當(dāng)B時(shí)，時(shí)，card Acard AB， 這就推出這就推出0card AB綜合所述，綜合所述，card AB 0 40本章主要內(nèi)容本章主要內(nèi)容q 集合等勢(shì)的定義集合等勢(shì)的定義q 等勢(shì)的性質(zhì)等勢(shì)的性質(zhì)q 集合優(yōu)勢(shì)的定義集合優(yōu)勢(shì)的定義q 優(yōu)勢(shì)的性質(zhì)優(yōu)勢(shì)的性質(zhì)q 重要的集合等勢(shì)以及優(yōu)勢(shì)的結(jié)果重要

30、的集合等勢(shì)以及優(yōu)勢(shì)的結(jié)果q 自然數(shù)及其自然數(shù)集合的定義自然數(shù)及其自然數(shù)集合的定義q 可數(shù)集與不可數(shù)集可數(shù)集與不可數(shù)集q 集合的基數(shù)集合的基數(shù) 41本章學(xué)習(xí)要求本章學(xué)習(xí)要求q 能夠證明兩個(gè)集合等勢(shì)。能夠證明兩個(gè)集合等勢(shì)。q 能夠證明一個(gè)集合優(yōu)勢(shì)于另一個(gè)集合。能夠證明一個(gè)集合優(yōu)勢(shì)于另一個(gè)集合。q 知道什么是可數(shù)集與不可數(shù)集。知道什么是可數(shù)集與不可數(shù)集。q 會(huì)求一個(gè)簡(jiǎn)單集合的基數(shù)。會(huì)求一個(gè)簡(jiǎn)單集合的基數(shù)。 42等勢(shì)的證明方法等勢(shì)的證明方法q 證明集合證明集合A A與與B B等勢(shì)的方法等勢(shì)的方法直接構(gòu)造從直接構(gòu)造從A A到到B B的雙射函數(shù)的雙射函數(shù) f需要證明需要證明 f 的滿(mǎn)射性和的滿(mǎn)射性和f f

31、的單射性。的單射性。構(gòu)造兩個(gè)單射函數(shù)構(gòu)造兩個(gè)單射函數(shù)f f：A AB B 和和 g g：B BA A。 給出函數(shù)給出函數(shù)f f和和g g，證明證明f f和和g g的單射性。的單射性。利用等勢(shì)的傳遞性利用等勢(shì)的傳遞性直接計(jì)算直接計(jì)算A A與與B B的基數(shù)，得到的基數(shù)，得到card card A A card card B B。q 證明集合證明集合A A與自然數(shù)集合與自然數(shù)集合N N等勢(shì)的方法等勢(shì)的方法找到一個(gè)找到一個(gè)“數(shù)遍數(shù)遍”A A中元素的順序。中元素的順序。 43例題選講例題選講1 1已知已知An7 7|nN，B n109|n N ，求下列各題：求下列各題：（1 1）card A（2 2）c

32、ard B（3 3）card (AB)（4 4）card (AB)（1）構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) f：NA， f(n)=n7 7 ，因此因此 card A0。（2）構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) g：NA， g(n)=n109，因此因此 card B0。（3 3）可數(shù)集的并仍舊是可數(shù)集可數(shù)集的并仍舊是可數(shù)集( (或者由于或者由于AB N) )， 因此因此card (AB)0， 但是但是 0 card Acard (AB)， 從而得到從而得到 card (AB)0。（4 4）因?yàn)橐驗(yàn)?與與109互素互素，card (AB)n7 109 | n N， 與（與（1 1）類(lèi)似得到）類(lèi)似得到 card (AB)0 。解答解答 44例題選講例題選講2.2.已知已知card A0，且且card B card A，求求card (A B) 。由由A B A，得到得到 card (A B)card A，即即card(A B)0 。由由card B card A可知，可知，B為有窮集，為有窮集，即存在自然數(shù)即存在自然數(shù)n，使得使得card B=n。假設(shè)假設(shè)card (A B) 0，那么存在自然數(shù)那么存在自然數(shù)m，使使 card (A B)m。從而得到，從而得到，card Acard (A B)B)n+m與與card A0矛盾。矛盾。因此，因此，card (A B)0。解答解答