離散數(shù)學(xué)(函數(shù))課件

1、2021/8/14*函 數(shù)第 八 章2021/8/14*12/19/20214.1 函數(shù)的概念v 函數(shù)定義函數(shù)定義v 函數(shù)與關(guān)系函數(shù)與關(guān)系v 函數(shù)相等函數(shù)相等v 特殊函數(shù)特殊函數(shù): : 單射單射 滿射滿射 雙射雙射8.1 函數(shù)的定義與性質(zhì)函數(shù)的定義與性質(zhì)2021/8/14*12/19/2021設(shè)設(shè) F 為二元關(guān)系為二元關(guān)系, 若若 xdomF 都存在唯一都存在唯一的的yranF 使使 xFy 成立成立, 則稱則稱 F 為為函數(shù)函數(shù) 對(duì)于函數(shù)對(duì)于函數(shù)F, 如果有如果有 xFy, 則記作則記作 y=F(x), 并稱并稱 y 為為F 在在 x 的的值值.x 自變?cè)宰冊(cè)?y 在在F 作用下作用下 x

2、 的像的像2021/8/14*12/19/2021 10,)212121xxNxxxxfa且,)2212121yyRyyyyfb, xxxx ) 22121x1的素?cái)?shù)個(gè)數(shù)為不大于xNfc12yy 1 1 11x2x562101233423002021/8/14*12/19/2021設(shè)設(shè)F, G 為函數(shù)為函數(shù), 則則 F=G F GG F 如果兩個(gè)函數(shù)如果兩個(gè)函數(shù)F 和和 G 相等相等, 一定滿足下面兩個(gè)一定滿足下面兩個(gè)條件：條件： (1) domF=domG (2) xdomF=domG 都有都有F(x)=G(x) 函數(shù)函數(shù)F(x)=(x2 1)/(x+1), G(x)=x 1不相等不相等,

3、因?yàn)橐驗(yàn)閐omF domG.2021/8/14*12/19/2021設(shè)設(shè)A, B為集合為集合, 如果如果 f 為函數(shù)為函數(shù), domf=A, ranf B, 則稱則稱 f 為為從從A到到B的函數(shù)的函數(shù), 記作記作 f：AB.2021/8/14*12/19/2021 在 f 中, Adomf 定義域定義域Branf值域值域,( (函數(shù)像的集合函數(shù)像的集合) )例：例： 設(shè)設(shè) X =張三、李四、王五張三、李四、王五， Y =法國、美國、俄羅斯、英國法國、美國、俄羅斯、英國f =Adomf Branf 美國、俄羅斯、英國美國、俄羅斯、英國 2021/8/14*12/19/2021n 函數(shù)的定義域是函

4、數(shù)的定義域是A, 而不是而不是A 的的 某個(gè)真子集；某個(gè)真子集；n 一個(gè)一個(gè) x 只能對(duì)應(yīng)于唯一的只能對(duì)應(yīng)于唯一的 y ；n A B 的子集并不都能成為的子集并不都能成為 A 到到 B 的函數(shù)。的函數(shù)。 2021/8/14*12/19/2021 A=a,b,c, B=0,1 A B=, |P(A B)|=26, 但只有但只有 23 個(gè)子集定義為個(gè)子集定義為 X 到到 Y 的函數(shù)的函數(shù).f0 = ,f1 = ,f2 = ,f7 = ,一般地，一般地，|A|=m, |B|=n,由由 A 到到 B 的任的任意函數(shù)的定義域是意函數(shù)的定義域是 A ,在函數(shù)中每個(gè)在函數(shù)中每個(gè)恰有恰有 m 個(gè)序偶個(gè)序偶,又

5、任何又任何x A ,可以有可以有 n 個(gè)元素中的任何一個(gè)作為它的像個(gè)元素中的任何一個(gè)作為它的像,故故共有共有 nm (|B|A| ) 個(gè)不同函數(shù)個(gè)不同函數(shù). BA2021/8/14*12/19/2021所有從所有從A到到B的函數(shù)的集合記作的函數(shù)的集合記作BA, 表示為表示為 BA = f | f：AB |A|=m, |B|=n, 且且m, n0, |BA|=nmA=, 則則BA=B=A且且B=, 則則BA=A= 2021/8/14*12/19/2021設(shè)函數(shù)設(shè)函數(shù) f：AB, A1 A, B1 B(1) A1在在 f 下的像下的像 f(A1) = f(x) | xA1 特別的特別的, f(A)

6、稱為稱為函數(shù)的像函數(shù)的像(2) B1在在 f 下的完全原像下的完全原像 f 1(B1)=x|xAf(x)B1注意：注意：函數(shù)值與像的區(qū)別：函數(shù)值函數(shù)值與像的區(qū)別：函數(shù)值 f(x)B, 像像f(A1) B一般說來一般說來 f 1(f(A1)A1, 但是但是A1 f 1(f(A1)2021/8/14*12/19/2021例例 設(shè)設(shè) f：NN, 且且令令A(yù)=0,1, B=2, 那么有那么有 f(A) = f 1(B) = 為奇數(shù)為奇數(shù)若若為偶數(shù)為偶數(shù)若若xxxxxf12/)( f( 0,1) = f(0), f(1)=0,2 f 1(2)=1,42021/8/14*12/19/2021設(shè)設(shè) f：AB

7、,(1) 若若 ranf=B, 則稱則稱 f:AB是是滿射滿射的的(2) 若若 yranf 都存在唯一的都存在唯一的 xA 使得使得 f(x)=y, 則稱則稱 f:AB是是單射單射的的(3) 若若 f:AB 既是滿射又是單射的既是滿射又是單射的, 則稱則稱 f:AB是是雙射雙射的的)()(,(21212121xfxfxxAxxxx 2021/8/14*12/19/2021 1x1y2y3y2x3x4y1y2x3x1x2y3y2x3x1x3y2y1y4x4y1x2x3x1y2y3y單 射 映射（函數(shù)）雙(單、滿)射滿射2021/8/14*12/19/2021判斷下面函數(shù)是否為單射判斷下面函數(shù)是否

8、為單射, 滿射滿射, 雙射的雙射的?(1) f:RR, f(x) = x2+2x 1(2) f:Z+R, f(x) = lnx, Z+為正整數(shù)集為正整數(shù)集(3) f:RZ, f(x) = x (4) f:RR, f(x)=2x+1(5) f:R+R+, f(x)=(x2+1)/x, 其中其中R+為正實(shí)數(shù)集為正實(shí)數(shù)集. 2021/8/14*12/19/2021 令令 A 和和 B 是有限集，若是有限集，若 A 和和 B 的元素個(gè)數(shù)相同，即的元素個(gè)數(shù)相同，即| A| = | B|，則則 f: A B是單射的，當(dāng)且僅當(dāng)是單射的，當(dāng)且僅當(dāng)它是一個(gè)滿射。它是一個(gè)滿射。此定理對(duì)無限集不一定成立。此定理對(duì)無

9、限集不一定成立。例如：例如：f: I I , f(x)=2x整數(shù)映射到偶整數(shù)整數(shù)映射到偶整數(shù)( (單射、非滿射單射、非滿射) )2021/8/14*12/19/2021對(duì)于給定的集合對(duì)于給定的集合A和和B構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) f:AB(1) A=P(1,2,3), B=0,11,2,3(2) A=0,1, B=1/4,1/2(3) A=Z, B=N(4) , B= 1,123,2 A2021/8/14*12/19/2021對(duì)于給定的集合對(duì)于給定的集合A和和B構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) f:AB(2) A=0,1, B=1/4,1/2(1,1/2)f(x)=(x+1)/42021/8/14*1

10、2/19/2021對(duì)于給定的集合對(duì)于給定的集合A和和B構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) f:AB A=-1, 1), B=2, 7)(1,7)(-1,2)2021/8/14*12/19/2021對(duì)于給定的集合對(duì)于給定的集合A和和B構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù) f:AB(3) A=Z, B=N 01202)(,NZxxxxff：(3) 將將Z中元素以下列順序排列并與中元素以下列順序排列并與N中元素對(duì)應(yīng)：中元素對(duì)應(yīng)：Z： 0 11 2 2 3 3 N： 0 1 2 3 4 5 6 這種對(duì)應(yīng)所表示的函數(shù)是：這種對(duì)應(yīng)所表示的函數(shù)是：2021/8/14*12/19/2021(1)設(shè)設(shè) f:AB, 如果存在如果存在c

11、B使得對(duì)所有使得對(duì)所有的的 xA都有都有 f(x)=c, 則稱則稱 f:AB是是常函常函數(shù)數(shù).(2) 稱稱 A上的恒等關(guān)系上的恒等關(guān)系IA為為A上的上的恒等函數(shù)恒等函數(shù), 對(duì)所有的對(duì)所有的xA都有都有IA(x)=x.(3) 設(shè)設(shè), 為偏序集，為偏序集，f:AB，如果對(duì)任意的如果對(duì)任意的 x1, x2A, x1 x2, 就有就有 f(x1) f(x2), 則稱則稱 f 為為單調(diào)遞增單調(diào)遞增的；如果的；如果對(duì)任意的對(duì)任意的x1, x2A, x1 x2, 就有就有f(x1) f(x2), 則稱則稱 f 為為嚴(yán)格單調(diào)遞增嚴(yán)格單調(diào)遞增的的. 類似類似的也可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的也可以定義單調(diào)遞減

12、和嚴(yán)格單調(diào)遞減的函數(shù)的函數(shù).2021/8/14*12/19/2021(4) 設(shè)設(shè)A為集合為集合, 對(duì)于任意的對(duì)于任意的A A, A的的特特征函數(shù)征函數(shù) A :A0,1定義為定義為 A(a)=1, aA A(a)=0, aA A(5) 設(shè)設(shè)R是是A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 令令 g:AA/R g(a)=a, aA稱稱 g 是從是從 A 到商集到商集 A/R 的的自然映射自然映射2021/8/14*12/19/2021 (1) 偏序集偏序集, , R 為包含關(guān)為包含關(guān)系系, 為一般的小于等于關(guān)系為一般的小于等于關(guān)系, 令令 f:P(a,b)0,1, f()=f(a)=f(b)=0, f(a,b)

13、=1, f 是是單調(diào)遞增的單調(diào)遞增的, 但不是嚴(yán)格單調(diào)遞增的但不是嚴(yán)格單調(diào)遞增的(2) A的每一個(gè)子集的每一個(gè)子集 A都對(duì)應(yīng)于一個(gè)特征函數(shù)都對(duì)應(yīng)于一個(gè)特征函數(shù), 不同的子集對(duì)應(yīng)于不同的特征函數(shù)不同的子集對(duì)應(yīng)于不同的特征函數(shù). 例如例如A=a,b,c, 則有則有 a,b= =, ,2021/8/14*12/19/2021(3) 不同的等價(jià)關(guān)系確定不同的自然映射不同的等價(jià)關(guān)系確定不同的自然映射, 恒等關(guān)系確定的自然映射是雙射恒等關(guān)系確定的自然映射是雙射, 其他其他自然映射一般來說只是滿射自然映射一般來說只是滿射. A=1,2,3, R=,IA g: AA/R, g(1)=g(2)=1,2, g(3

14、)=32021/8/14*12/19/2021 證明證明 f(A B) f(A) f(B)保序性：保序性：A B f(A) f(B)A B A A B B f(A B) f(A) f(A B) f(B) v方法方法1：f(A B) f(A) f(B)x A f(x) f(A)2021/8/14*12/19/2021 證明證明 f(A B) f(A) f(B)保序性：保序性：x A f(x) f(A)對(duì)于對(duì)于 y, y f(A B) , 則則 x, x A B ,使得使得f(x) = yv方法方法2： y f(A) f(B) 即即 x A x B ,使得使得f(x) = y f(x) f(A)

15、f(x) f(B) 2021/8/14*12/19/2021設(shè)設(shè)f和和g是定義域?yàn)樽匀粩?shù)是定義域?yàn)樽匀粩?shù)N上的函數(shù)上的函數(shù)f(n)=O(g(n). 若存在正數(shù)若存在正數(shù)c和和n0使得對(duì)一切使得對(duì)一切n n0 有有 0 f(n) cg(n)f(n) = (g(n). 若存在正數(shù)若存在正數(shù)c和和n0使得對(duì)一切使得對(duì)一切n n0有有 0 cg(n) f(n)f(n) =o(g(n). 若對(duì)任意正數(shù)若對(duì)任意正數(shù)c存在存在n0使得對(duì)一切使得對(duì)一切n n0有有 0 f(n) cg(n)f(n) = (g(n). 若對(duì)任意正數(shù)若對(duì)任意正數(shù)c存在存在n0使得對(duì)一切使得對(duì)一切n n0有有 0 cg(n) f(n

16、)f(n) = (g(n) f(n) =O(g(n) 且且 f(n) = (g(n)2021/8/14*12/19/2021f(n)c0g(n)c1g(n)n0f(n) is (g(n) f(n)cg(n)n0f(n) is O(g(n) f(n)cg(n)n0f(n) is (g(n) 2021/8/14*12/19/20211+2+ n n + n + n = n2 對(duì)于對(duì)于n 1 所以所以 1+2+ n =例：例： 1+2+n O(n2) 又又1+2+ n 1+1+1= n 對(duì)于對(duì)于n 1 所以所以 1+2+ n =(n)綜上綜上 1+2+ n = ?2021/8/14*12/19/20

17、21);()()();()()(0);()()(0)()(limgfngnfsgOfngnfsgfngnfssngnfn則的階高，比說明時(shí)，當(dāng)則的階低，比說明時(shí)，當(dāng)則同階，和說明時(shí)，當(dāng)若1+2+n=(n2)2021/8/14*12/19/20214.2 逆函數(shù)和復(fù)合函數(shù)v復(fù)合函數(shù)復(fù)合函數(shù)v反函數(shù)反函數(shù)8.2 函數(shù)的復(fù)合與反函數(shù)函數(shù)的復(fù)合與反函數(shù)關(guān)系與逆關(guān)系關(guān)系與逆關(guān)系: R-1 R函數(shù)與反函數(shù)。函數(shù)與反函數(shù)。 可能出現(xiàn)的問題：可能出現(xiàn)的問題：定義域定義域 (dom(f -1) A) 函數(shù)值函數(shù)值 (一對(duì)多一對(duì)多) 2021/8/14*12/19/2021設(shè)設(shè)F, G是函數(shù)是函數(shù), 則則F G也

18、是函數(shù)也是函數(shù), 且滿足且滿足(1) dom(F G)=x|xdomFF(x)domG(2) xdom(F G)有有F G(x)=G(F(x)證證 先證明先證明F G是函數(shù)是函數(shù). 因?yàn)橐驗(yàn)镕, G是關(guān)系是關(guān)系, 所以所以F G也是關(guān)系也是關(guān)系. 若對(duì)某個(gè)若對(duì)某個(gè)xdom(F G)有有xF Gy1和和 xF Gy2, 則則 F GF Gt1(FG) t2(FG) t1 t2(t1=t2GG) （F為函數(shù)）為函數(shù)） y1=y2 （G為函數(shù)）為函數(shù)）所以所以 F G 為函數(shù)為函數(shù)2021/8/14*12/19/2021f : X Y , g : W Z u F = , G = ,X = 1,2,

19、Y = 3,4, W = 3,6, Z = 7, 9 F G = u f = , g = , f g = (1) dom(F G)=x|xdomFF(x)domG2021/8/14*12/19/2021推論推論 設(shè)設(shè) f:AB, g:BC, 則則 f g:AC, 且且 xA都有都有 f g(x)=g(f(x)證證 由上述定理知由上述定理知 f g是函數(shù)是函數(shù), 且且 dom(f g)=x|xdomff(x)domg =x|xAf(x)B=A ran(f g) rang C因此因此 f g:AC, 且且 xA有有 f g(x)=g(f(x)2021/8/14*12/19/2021,3 , 2 ,

20、 1qpYX, baZ , 3, 2, 1qppf求fg,bqbpg 1, 2, 3,f gbbb f g (1)= g(f(1)= g(p) = b2021/8/14*12/19/2021定理定理 設(shè)設(shè)f:AB, g:BC (1) 如果如果 f:AB, g:BC滿射滿射, 則則 f g:AC也滿射也滿射(2) 如果如果 f:AB, g:BC單射單射, 則則 f g:AC也單射也單射 (3) 如果如果 f:AB, g:BC雙射雙射, 則則 f g:AC也雙射也雙射定理定理 設(shè)設(shè) f:AB, 則則 f = f IB = IA f 證證 (1) 任取任取cC, 由由g:BC的滿射性的滿射性, bB

21、使使得得 g(b)=c. 對(duì)于這個(gè)對(duì)于這個(gè)b, 由由 f:AB的滿射性，的滿射性， aA使得使得 f(a)=b. 由合成定理有由合成定理有 f g(a) = g(f(a) = g(b) = c從而證明了從而證明了f g:AC是滿射的是滿射的2021/8/14*12/19/2021定理定理 設(shè)設(shè)f:AB, g:BC (2) 如果如果 f:AB, g:BC單射單射, 則則 f g:AC也單射也單射 證證 (2) 假設(shè)存在假設(shè)存在x1, x2A使得使得 f g(x1)=f g(x2)由合成定理有由合成定理有 g(f(x1)=g(f(x2)因?yàn)橐驗(yàn)間:BC是單射的是單射的, 故故 f(x1)=f(x2

22、). 又由于又由于f:AB是是單射的單射的, 所以所以x1=x2. 從而證明從而證明f g:AC是單射的是單射的.2021/8/14*12/19/2021注意：定理逆命題不為真注意：定理逆命題不為真, 即如果即如果f g:AC是是單射單射(或滿射、雙射或滿射、雙射)的的, 不一定有不一定有 f:AB 和和 g:BC都是單射都是單射(或滿射、雙射或滿射、雙射)的的.fg2021/8/14*12/19/2021u多個(gè)函數(shù)可復(fù)合多個(gè)函數(shù)可復(fù)合例例: X 1 , 2 , 3f 1 , p , 2 2 , p , 3 3 , q 求求: f (g h )、 ( f g) hY p , qZ a , bW

23、 5, 6, 7g p , b , q , a h a , 6 , b , 6 解解: g h = p , 6 , q , 6 f (g h ) = 1 , 6 , 2 , 6 , 3 , 6 f g = 1 , b , 2 , b , ( f g) h = 1 , 6 , 2 , 6 , 3 , 6 2021/8/14*12/19/2021已知：集合已知：集合 A=1, 2, 3, B=a, b, c令令函數(shù)函數(shù) f: A B f =,但函數(shù)但函數(shù) f的逆的逆關(guān)系關(guān)系：f -1 =, , 不是函數(shù)不是函數(shù)v原函數(shù)值域原函數(shù)值域ran(f ) = dom(f -1) Bv原函數(shù)原函數(shù)f (多對(duì)

24、一多對(duì)一)原因原因2021/8/14*12/19/2021定理定理 設(shè)設(shè) f:AB是雙射的是雙射的, 則則f 1:BA也也是雙射的是雙射的.證明思路：證明思路：先證明先證明 f 1:BA，即即f 1是函數(shù)且是函數(shù)且domf 1=B, ranf 1=A. 再證明再證明f 1:BA的雙射性質(zhì)的雙射性質(zhì). 2021/8/14*12/19/2021證證 因?yàn)橐驗(yàn)?f 是函數(shù)是函數(shù), 所以所以 f 1是關(guān)系是關(guān)系, 且且 dom f 1 = ranf = B , ran f 1 = domf = A對(duì)于任意的對(duì)于任意的 xB = dom f 1, 假設(shè)有假設(shè)有y1, y2A使得使得 f 1f 1成立成立

25、, 則由逆的定義有則由逆的定義有 ff根據(jù)根據(jù) f 的單射性可得的單射性可得y1=y2, 從而證明了從而證明了f 1是函數(shù)，且是是函數(shù)，且是滿射的滿射的. 若存在若存在x1, x2B使得使得f 1 (x1)= f 1 (x2)=y, 從而有從而有 f 1f 1 ff x1=x2 對(duì)于雙射函數(shù)對(duì)于雙射函數(shù)f:AB, 稱稱 f 1:BA是它的是它的反函數(shù)反函數(shù).2021/8/14*12/19/2021定理定理(1) 設(shè)設(shè) f:AB是雙射的是雙射的, 則則 f 1 f = IB, f f 1 = IA(2) 對(duì)于雙射函數(shù)對(duì)于雙射函數(shù) f:AA, 有有 f 1 f = f f 1 = IA 證明 設(shè)

26、若 ,aA.bB( ),f ab則1( ),fba于是11()( )( )ff bf fb( )f ab1BffI2021/8/14*12/19/2021,2 , 1 , 0:cbaf001122aabbcc求求: f f -1 及及f -1 f 解解: ff -1012cbaf -1 ff f -1=IA=IB例2021/8/14*12/19/2021定理定理 是一一是一一:f AB對(duì)應(yīng)函數(shù)對(duì)應(yīng)函數(shù), ,則則ff11)( (雙射雙射) )定理定理:f AB:g BC均為一一對(duì)應(yīng)函數(shù)均為一一對(duì)應(yīng)函數(shù), , 則則111()fggf( (雙射雙射) )定理2021/8/14*12/19/2021g

27、 x (x) = (x+2)2 x 1 - -2 x 1 f g (x) = x2 +2 x 3 0 0 x 3 f RR , g : R R,f (x) = x2 x 3 - -2 x 3 v求求 f g g f g (x) = x+2 2021/8/14*12/19/20214.4 基數(shù)的概念v自然數(shù)集合自然數(shù)集合v等勢(shì)等勢(shì)v有有( (無無) )限集合限集合v基數(shù)基數(shù)8.3 雙射函數(shù)與集合的基數(shù)雙射函數(shù)與集合的基數(shù)2021/8/14*12/19/2021定義 給定 A的后繼集為AAA,若 為 ,則A,)(,)( ,可寫成如下形式,可簡記為, , , ,2021/8/14*12/19/202

28、1若命名集合 為0,則 0 1 0 ,1 0,1 2 0,1,2 3 , ,2 得到自然數(shù)集合, 3 ,2, 1 ,0N自然數(shù)自然數(shù)集合集合(n -1) 0,1,2,. . . . . . n -1 n2021/8/14*12/19/2021定義 給定兩個(gè)集合A 與 B, 當(dāng)且僅當(dāng)存在著從 A 到 B 的雙射函數(shù), 稱集合A 與B 是等勢(shì)的, 記為A B .等勢(shì)2021/8/14*12/19/2021等勢(shì)證明證明: 設(shè)集合族為S 對(duì)任意 A S ,A A . 若若 A ,B S , A B ,則B A 若若 A ,B ,C S,A B ,B C , 則 A C 定理定理 在集合族上等勢(shì)關(guān)系是一

29、個(gè)在集合族上等勢(shì)關(guān)系是一個(gè)等價(jià)關(guān)系等價(jià)關(guān)系. .(1) IA是從是從A到到A的雙射的雙射 (2) 若若 f:AB是雙射，是雙射，則則f 1:BA是從是從B到到A的雙射的雙射.(3) 若若 f:AB，g:BC是雙射，則是雙射，則f g:AC是從是從A到到C的雙射的雙射2021/8/14*12/19/2021定義 若有一個(gè)從集合 0,1, , n-1 到A 的雙射函數(shù),則稱A 是有限(窮)的; 若A 不是有限(窮)的,則它是無限的.有(無)限集合集合A 有限 A 某個(gè)自然數(shù)2021/8/14*12/19/2021定義定義(1) 對(duì)于有限集合對(duì)于有限集合A, 稱與稱與A等勢(shì)的那個(gè)等勢(shì)的那個(gè)惟一的自然

30、數(shù)為惟一的自然數(shù)為A的的基數(shù)基數(shù), 記作記作cardA (也可以記作也可以記作|A|) cardA = n A n 一個(gè)集合是一個(gè)集合是有限有限的當(dāng)且僅當(dāng)它與某個(gè)自然數(shù)等勢(shì)；的當(dāng)且僅當(dāng)它與某個(gè)自然數(shù)等勢(shì)；|有限集合有限集合| = 元素個(gè)數(shù)元素個(gè)數(shù) |空集空集| = 02021/8/14*12/19/2021等勢(shì) 例例1: 試證集合試證集合 A = a, b, c, d 與與 B = , , , 等勢(shì)等勢(shì)證明證明: 設(shè)設(shè) f : A B , f (a) = , f (b) = , f (c) = , f (d) = , 則則 f 是是 A B 的雙射函數(shù)的雙射函數(shù), 所以所以A B2021/8/

31、14*12/19/2021等勢(shì) 例例2: 試證自然數(shù)集合試證自然數(shù)集合 N 與與 集合集合 A = 2n | n N 等勢(shì)等勢(shì) .證明證明: 設(shè)設(shè) f : N A , 且且 f (n) = 2n, n = 0, 1, 2, , 則則 f 是是 N A 的的雙射函數(shù)雙射函數(shù), 所以所以 N A .2021/8/14*12/19/2021等勢(shì) 例例3: 設(shè)設(shè) A = ( 0,1 ) = x | x R 0 x 1, 證明證明 A 與實(shí)數(shù)集與實(shí)數(shù)集合合 R 等勢(shì)等勢(shì) .證明證明: 設(shè)設(shè) f : A R , 且且 f (x) = tg(2x -1 ) , 則則 f 是是 A R 的雙射的雙射函數(shù)函數(shù)

32、. 22021/8/14*12/19/2021等勢(shì) f 是單射的是單射的. 對(duì)于任意的對(duì)于任意的x1 和和 x2 , x1 , x2 ( 0,1 ) (2x1 -1) , (2x2 -1 ) (- , ) 于是于是 tan(2x1 -1) = tan(2x2 -1) (2x1 -1) =(2x2 -1 ) x1 = x2 , 所以所以 f 是單射函數(shù)是單射函數(shù) . 22222222因此因此 A R . f 是滿射的是滿射的. 對(duì)于任意的對(duì)于任意的 y R , 取取 x = arc tan y + 1 , 則則 x ( 0, 1 ) , 且且 f (x) = y ，所以所以 f 是滿射的是滿射的

33、 . 22021/8/14*12/19/2021等勢(shì)因此因此 A R . f 是單射的是單射的. x ( 0,1 ) (2x -1) (- , )222 f 是滿射的是滿射的. 對(duì)于任意的對(duì)于任意的 y R , 取取 x = arctan y + 1 , 則則 x ( 0, 1 ) , 且且 f (x) = y ，所以所以 f 是滿射的是滿射的 . 2因?yàn)橐驗(yàn)閒 單調(diào)單調(diào)，所以，所以f 是入射的是入射的.2f(x) =tan( 2x -1 ) f(0, 1) R2021/8/14*12/19/2021 01202)(,NZ:xxxxxff則則 f 是是Z到到N的雙射函數(shù)的雙射函數(shù). 從而證明了

34、從而證明了ZN.ZN 2021/8/14*12/19/2021221/ 201/ 21( )1/ 21/ 2 ,1,2,.nnxxf xxnxx其它0,1(0,1). 其中其中(0,1)和和0,1分別為實(shí)數(shù)分別為實(shí)數(shù)開區(qū)間和閉區(qū)間開區(qū)間和閉區(qū)間. 令令 f : 0,1(0,1)2021/8/14*12/19/2021 對(duì)任何對(duì)任何a, bR, ab, 0,1a,b，雙射函數(shù)雙射函數(shù) f:0,1a,b, f(x)=(b a)x+a類似地可以證明類似地可以證明, 對(duì)任何對(duì)任何a, bR, ab, 有有(0,1)(a,b).2021/8/14*12/19/2021定義 有限集、或者與自然數(shù)集合等勢(shì)的

35、任意集合稱為可數(shù)集(可列集),無限可數(shù)集的基數(shù)用0 0表示.可數(shù)集2021/8/14*12/19/2021可數(shù)集舉例例 A = a, b, c, B = 1, 3, 5, , 2n+1, , C = 3, 12, 27, , 3(n+1)2, , 整數(shù)集整數(shù)集Z , 有理數(shù)集有理數(shù)集Q .2021/8/14*12/19/2021定理定理 設(shè)設(shè)A是集合是集合, A為可數(shù)集的充要條件是可為可數(shù)集的充要條件是可排列成排列成A = a1 , a2 , . , an , . 的形式的形式. . 一個(gè)集合是可數(shù)集當(dāng)且僅當(dāng)可以將它的一個(gè)集合是可數(shù)集當(dāng)且僅當(dāng)可以將它的所有元素逐個(gè)的排成一個(gè)序列所有元素逐個(gè)的排

36、成一個(gè)序列, ,使得序列使得序列中每個(gè)元素都屬于這個(gè)集合中每個(gè)元素都屬于這個(gè)集合, ,并且這個(gè)集并且這個(gè)集合中的每個(gè)元素都在序列中的某個(gè)位置合中的每個(gè)元素都在序列中的某個(gè)位置出現(xiàn)且僅出現(xiàn)一次出現(xiàn)且僅出現(xiàn)一次. .對(duì)于任何的可數(shù)集對(duì)于任何的可數(shù)集, , 它的元素都可以排列成一個(gè)有序圖形它的元素都可以排列成一個(gè)有序圖形. . 換句話說換句話說, , 都可以找到一個(gè)都可以找到一個(gè)“數(shù)遍數(shù)遍”集集合中全體元素的順序合中全體元素的順序. . 可數(shù)集充要條件2021/8/14*12/19/2021mnmnmnmff 2)(1(),(,NNN:NNN. NN中所有的元素排成有序圖形中所有的元素排成有序圖形2

37、021/8/14*12/19/2021NQ. 雙射函數(shù)雙射函數(shù) f:NQ, 其中其中f(n)是是n下方的下方的有理數(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-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/

38、41/41/41414PLAY2021/8/14*12/19/2021,242322212aaaaS ,343332313aaaaS ,444342414aaaaS ,141312111aaaaS ,545352515aaaaS 1kkSS2021/8/14*12/19/2021可數(shù)集的性質(zhì)：可數(shù)集的性質(zhì)： 可數(shù)集的任何子集都是可數(shù)集可數(shù)集的任何子集都是可數(shù)集. 兩個(gè)可數(shù)集的并是可數(shù)集兩個(gè)可數(shù)集的并是可數(shù)集. 兩個(gè)可數(shù)集的笛卡兒積是可數(shù)集兩個(gè)可數(shù)集的笛卡兒積是可數(shù)集. 可數(shù)個(gè)可數(shù)集的笛卡兒積仍是可數(shù)集可數(shù)個(gè)可數(shù)集的笛卡兒積仍是可數(shù)集.2021/8/14*12/19/2021證明 是可數(shù)集, N

39、N,互質(zhì)且 nmNnmnmSS是可數(shù)的.令QSg:(,)mgm nn g是雙射的,故 是可數(shù)集.Q.QQQQQ0定理:Q可數(shù)集2021/8/14*12/19/2021有關(guān)勢(shì)的結(jié)果等勢(shì)結(jié)果等勢(shì)結(jié)果 N Z Q NN 任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合R等勢(shì)等勢(shì)不等勢(shì)的結(jié)果不等勢(shì)的結(jié)果: 定理定理 (康托定理康托定理)(1) N R； (2) 對(duì)任意集合對(duì)任意集合A都有都有A P(A)證明思路：證明思路：(1) 只需證明任何函數(shù)只需證明任何函數(shù) f:N0,1都不是滿射的都不是滿射的. 任取函數(shù)任取函數(shù) f:N0,1, 列出列出 f 的的所有所有函數(shù)值，函數(shù)值，然后構(gòu)造一個(gè)然后構(gòu)造一個(gè)

40、0,1區(qū)間的小數(shù)區(qū)間的小數(shù)b，使得，使得b與所有與所有的函數(shù)值都不相等的函數(shù)值都不相等. 2021/8/14*12/19/2021證證 (1) 規(guī)定規(guī)定0,1中數(shù)的表示中數(shù)的表示. 對(duì)任意的對(duì)任意的x0,1, 令令 x = 0. x1 x2 , 0 xi 9規(guī)定在規(guī)定在 x 的表示式中不允許在某位后有無數(shù)個(gè)的表示式中不允許在某位后有無數(shù)個(gè)9的情的情況況. 設(shè)設(shè) f: N0,1是任何函數(shù)，列出是任何函數(shù)，列出 f 的所有函數(shù)值：的所有函數(shù)值： f(0) = 0.a1(1)a2(1) f(1) = 0.a1(2)a2(2) f(n 1) = 0.a1(n)a2(n) 令令 y 的表示式為的表示式為0.b1b2, 并且