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

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

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

3、 雙射函數(shù)雙射函數(shù) 7等勢集合的實例等勢集合的實例(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作為第一個數(shù)，按照箭頭規(guī)定的順序可以作為第一個數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍數(shù)遍”表中表中所有的數(shù)。計數(shù)過程中必須跳過第二次以及以后各次所遇到的所有的數(shù)。計數(shù)過程中必須跳過第二次以及以后各次所遇到的同一個有理數(shù)。同一個有理數(shù)。 8等勢集合的實例等勢集合的實例(4)(4)（4）(0,1)R。 其中實數(shù)區(qū)間其中實數(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等勢集合的實例等勢集合的實例(5)(5)（5 5）0,1(0,1)。 其中其中(0,1)和和0,1分別為實數(shù)開區(qū)間和閉區(qū)間。分別為實數(shù)開區(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等勢集合的實例等勢集合的實例(6)(6)（6 6）對任何）對任何a, bR，ab， 0,1a,

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

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

8、閉區(qū)間以及半開半閉的區(qū)間）任何的實數(shù)區(qū)間（開區(qū)間、閉區(qū)間以及半開半閉的區(qū)間）都與實數(shù)集合都與實數(shù)集合R R等勢。等勢。q 問題：問題：N N和和R R是否等勢？是否等勢？若干等勢集合若干等勢集合 14（1）如果能證明）如果能證明N 0,1，就可以斷定就可以斷定N R。 只需證明任何函數(shù)只需證明任何函數(shù)f：N0,1都不是滿射的。都不是滿射的。 構造一個構造一個0,1區(qū)間的小數(shù)區(qū)間的小數(shù)b，使得使得b在在N中不存在原像。中不存在原像。（2）任取函數(shù)）任取函數(shù)f：AP(A)，構造構造BP(A)，使得使得B在在A中不存在中不存在原像。原像。或者使用反證法。或者使用反證法。定理定理9.29.2 康托定理

9、康托定理（1）N R。（2）對任意集合對任意集合A都有都有A P(A)?？低卸ɡ砜低卸ɡ矸治龇治?15（1 1）首先規(guī)定）首先規(guī)定0,1中數(shù)的表示。中數(shù)的表示。 對任意的對任意的x0,1，令令x = 0. .x1x2 , （0 xi 9） 注意：為了保證表示式的唯一性，如果遇到注意：為了保證表示式的唯一性，如果遇到0.249990.24999，則將，則將x x表表示為示為0.250000.25000。 設設 f:N0,1是從是從N到到0,1的任何一個函數(shù)。的任何一個函數(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，并且滿足并且滿足bi ai(i)，i=1,2, ,，則則y0,1， 但但y與上面列出的任何一個函數(shù)值都不相等與上面列出的任何一個函數(shù)值都不相等。即即f不是滿射的。不是滿射的。 所以所以，N R?？低卸ɡ砜低卸ɡ?16康托定理康托定理q 假設假設A AP(A)，則必有函數(shù)則必有函數(shù) f : AP(A)是雙射函數(shù)。是雙射函數(shù)。如下構造集合如下構造集合B：Bx| xAx f (x) 可知可知 BP(A)。于是存在唯一一個元素于是存在唯一一個元素bA，使得使得 f(b)B。若若bB，則由則由B的定義知，的定義知，b f (b)，即即 b B

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

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

13、) R N N N優(yōu)勢優(yōu)勢RN 19定理定理9.39.3 設設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）假設）假設A B且且B C，那么存在單射，那么存在單射 f:AB:AB，g:BC:BC， 于是于是 f g：AC也是單射的，因此也是單射的，因此A C 。優(yōu)勢的性質(zhì)優(yōu)勢的性質(zhì)說說明明q 該定理為證明集合之間的等勢提供了有力的工具該定理為證明集合之間的等勢提供了有力的工具。q 構造兩個單射構

14、造兩個單射f：A AB B 和和 g g：B BA A函數(shù)容易集合等勢函數(shù)容易集合等勢。 20例題例題例題：例題：證明證明0,10,1與與(0,1)(0,1)等勢。等勢。證明：證明：構造兩個單射函數(shù)構造兩個單射函數(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) 設設x 0,1)，0.x1x2是是x的的二進制表示二進制表示。 為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無數(shù)個為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無數(shù)個1。 例如例如 x0.1010111，

15、應按規(guī)定記為應按規(guī)定記為0.1011000。 對于對于x，如下定義如下定義f：0,1)0,1N，使得使得 f(x) = tx，且且tx：N0,1， tx(n) = xn+1，n = 0,1,2, 例如例如 x = 0.10110100，則對應于則對應于x的函數(shù)的函數(shù)tx是是： n 0 1 2 3 4 5 6 7tx(n) 1 0 1 1 0 1 0 0 易見易見tx0,1N，且對于且對于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的十進制表示的十進制表示。 例如例如t1，t20,1N，且且g(t1)0.0111，g(t2)0.1000， 若將若將g(t1)和和g(t2)都看成二進制表示，則都看成二進制表示，則g(t1)g(t2)； 但若看成十進制表示，則但若看成十進制表示，則g(t1)g(t2)。 所以所以， g：0,1N0,1) 是單射的。是單射的。 根據(jù)根據(jù)定理定理9.3，有，有0,1N0,1)。證明證明 0,1N0,1) 23總結總結q N Z Q NNq

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

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

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

20、歸納集 28定義定義9.59.5 自然數(shù)自然數(shù)（1 1）一個）一個自然數(shù)自然數(shù)n是屬于每一個歸納集的集合。是屬于每一個歸納集的集合。（2 2）自然數(shù)集自然數(shù)集N是所有歸納集的交集。是所有歸納集的交集。說明說明：根據(jù)定義根據(jù)定義9.5得到的自然數(shù)集得到的自然數(shù)集 N 恰好由恰好由, +, +, +,等集合構成。而這些集合正是構造性方法所定義的等集合構成。而這些集合正是構造性方法所定義的全體自然數(shù)。全體自然數(shù)。 例如：例如：自然數(shù)都是集合，集合的運算對自然數(shù)都適用。自然數(shù)都是集合，集合的運算對自然數(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） 對任何自然數(shù)對任何自然數(shù)n，有有n n。（2） 對任何自然數(shù)對任何自然數(shù)n, m，若若m n，則則m n。（3） 對任何自然數(shù)對任何自然數(shù)n, m，若若mn，則則m n。（4） 對任何自然數(shù)對任何自然數(shù)n和和m，以下三個式子：以下三個式子： mn，m n， nm必成立其一且僅成立其一。必成

22、立其一且僅成立其一。（5） 自然數(shù)的相等與大小順序自然數(shù)的相等與大小順序 對任何自然數(shù)對任何自然數(shù)m和和n，有有m = n m n m n mn 自然數(shù)的性質(zhì)自然數(shù)的性質(zhì) 31定義定義9.69.6 有窮集、無窮集有窮集、無窮集（1 1）一個集合是）一個集合是有窮的有窮的當且僅當它與某個自然數(shù)等勢；當且僅當它與某個自然數(shù)等勢；（2 2）如果一個集合不是有窮的，就稱作）如果一個集合不是有窮的，就稱作無窮集無窮集。例如：例如：q a,b,c是有窮集，是有窮集， 因為因為30,1,2，且，且a,b,c0,1,23qN和和R都是無窮集，都是無窮集， 因為沒有自然數(shù)與因為沒有自然數(shù)與N和和R等勢。等勢。q

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

24、.8 9.8 設設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說明說明：集合的基數(shù)就是集合的勢，基數(shù)越大，勢就越大。：集合的基數(shù)就是集合的勢，基數(shù)越大，勢就越大?；鶖?shù)的相等和大小基數(shù)的相等和大小 34關于基數(shù)的說明關于基數(shù)的說明 q 由于對任何集合由于對任何集合A都滿足都滿足A P(A)，所以有所以有 card

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

26、b,c、5、整數(shù)集整數(shù)集Z、有理數(shù)集有理數(shù)集Q、NN等都是可數(shù)集。等都是可數(shù)集。q 實數(shù)集實數(shù)集R不是可數(shù)集，與不是可數(shù)集，與R等勢的集合也不是可數(shù)集。等勢的集合也不是可數(shù)集。 對于任何的可數(shù)集，都可以找到一個對于任何的可數(shù)集，都可以找到一個“數(shù)遍數(shù)遍”集合中全體集合中全體元素的順序。回顧前邊的可數(shù)集，特別是無窮可數(shù)集，都元素的順序。回顧前邊的可數(shù)集，特別是無窮可數(shù)集，都是用這種方法來證明的。是用這種方法來證明的。說說明明 36（1 1）可數(shù)集的任何子集都是可數(shù)集。）可數(shù)集的任何子集都是可數(shù)集。 一個集合的無限子集若不可數(shù)，則該集合也不可數(shù)。一個集合的無限子集若不可數(shù)，則該集合也不可數(shù)。（2

27、2）兩個可數(shù)集的并是可數(shù)集。）兩個可數(shù)集的并是可數(shù)集。（3 3）兩個可數(shù)集的笛卡兒積是可數(shù)集。）兩個可數(shù)集的笛卡兒積是可數(shù)集。（4 4）可數(shù)個可數(shù)集的笛卡兒積仍是可數(shù)集。）可數(shù)個可數(shù)集的笛卡兒積仍是可數(shù)集。（5 5）無窮集）無窮集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=a0, ,a1 , , a2 , , ，B=b0 , , b1 , , b2 , , , , bn 1。對任意的對任意的， 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 設設A, B

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

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

31、的單射性。的單射性。構造兩個單射函數(shù)構造兩個單射函數(shù)f f：A AB B 和和 g g：B BA A。 給出函數(shù)給出函數(shù)f f和和g g，證明證明f f和和g g的單射性。的單射性。利用等勢的傳遞性利用等勢的傳遞性直接計算直接計算A A與與B B的基數(shù)，得到的基數(shù)，得到card card A A card card B B。q 證明集合證明集合A A與自然數(shù)集合與自然數(shù)集合N N等勢的方法等勢的方法找到一個找到一個“數(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）構造雙射函數(shù)構造雙射函數(shù) f：NA， f(n)=n7 7 ，因此因此 card A0。（2）構造雙射函數(shù)構造雙射函數(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）因為因為7與與109互素互素，card (AB)n7 109 | n N， 與（與（1 1）類似得到）類似得到 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。假設假設card (A B) 0，那么存在自然數(shù)那么存在自然數(shù)m，使使 card (A B)m。從而得到，從而得到，card Acard (A B)B)n+m與與card A0矛盾。矛盾。因此，因此，card (A B)0。解答解答