離散數(shù)學課件08函數(shù)

第8章函數(shù)離散數(shù)學中國地質(zhì)大學本科生課程本章說明本章的主要內(nèi)容函數(shù)的定義函數(shù)的性質(zhì)函數(shù)的逆函數(shù)的合成

本章與后續(xù)各章的關(guān)系是代數(shù)系統(tǒng)的基礎(chǔ)

2精選課件ppt8.1函數(shù)的定義與性質(zhì)8.2函數(shù)的復合與反函數(shù)8.3一個電話系統(tǒng)的描述實例

本章小結(jié)

習題

作業(yè)本章內(nèi)容3精選課件ppt8.1函數(shù)的定義與性質(zhì)定義8.1設(shè)F為二元關(guān)系，若x∈domF，都存在唯一的y∈ranF使xFy成立，則稱F為函數(shù)(function)(或稱作映射(mapping))。 對于函數(shù)F，如果有xFy，則記作y＝F(x)，并稱y為F在x的值。舉例判斷下列關(guān)系是否為函數(shù)

F1＝{<x1,y1>,<x2,y2>,<x3,y2>}

F2＝{<x1,y1>,<x1,y2>}是函數(shù)不是函數(shù)說明函數(shù)是特殊的二元關(guān)系。函數(shù)的定義域為domF，而不是它的真子集。一個x只能對應唯一的y。4精選課件ppt定義8.2設(shè)F,G為函數(shù)，則F＝G

FG∧GF由定義可知，兩個函數(shù)F和G相等,一定滿足下面兩個條件：（1）domF＝domG（2）x∈domF＝domG，都有F(x)＝G(x)例如 函數(shù)F(x)＝(x21)/(x+1)，G(x)＝x1不相等,因為 domF＝{x|x∈R∧x≠-1}

domG＝R顯然，domF≠domG，所以兩個函數(shù)不相等。函數(shù)相等5精選課件ppt定義8.3設(shè)A,B為集合，如果f為函數(shù)，domf＝A，ranfB，則稱f為從A到B的函數(shù)，記作f：A→B。例如：

f：N→N，f(x)＝2x是從N到N的函數(shù)，

g：N→N，g(x)＝2也是從N到N的函數(shù)。定義8.4所有從A到B的函數(shù)的集合記作BA，讀作“B上A”，符號化表示為BA＝{f|f：A→B}。從A到B的函數(shù)6精選課件ppt例8.2

設(shè)A＝{1,2,3}，B＝{a,b}，求BA。解答B(yǎng)A＝{f0,f1,f2,f3,f4,f5,f6,f7}。其中

f

0＝{<1,a>,<2,a>,<3,a>}

f

1＝{<1,a>,<2,a>,<3,b>}

f

2＝{<1,a>,<2,b>,<3,a>}

f

3＝{<1,a>,<2,b>,<3,b>}

f

4＝{<1,b>,<2,a>,<3,a>}

f

5＝{<1,b>,<2,a>,<3,b>}

f

6＝{<1,b>,<2,b>,<3,a>}

f

7＝{<1,b>,<2,b>,<3,b>}例8.2說明若|A|＝m，|B|＝n，且m,n>0，則|BA|＝nm。當A或B至少有一個集合是空集時：

A＝且B＝，則BA＝＝{}。A＝且B≠，則BA＝B＝{}。A≠且B＝，則BA＝A＝。7精選課件ppt定義8.5設(shè)函數(shù)f：A→B，A1A，B1B。（1）令f(A1)＝{f(x)|x∈A1}，稱f(A1)為A1在f下的像(image)。

特別地，當A1＝A時，稱f(A)為函數(shù)的像。（2）令f1(B1)＝{x|x∈A∧f(x)∈B1}，稱f1(B1)為B1在f下的完全原像(preimage)

。說明函數(shù)的像和完全原像注意區(qū)別函數(shù)的值和像兩個不同的概念。函數(shù)值f(x)∈B，而函數(shù)的像f(A1)B。8精選課件ppt討論設(shè)B1B，顯然B1在f下的原像f-1(B1)是A的子集。設(shè)A1A，那么f(A1)B。

f(A1)的完全原像就是f-1(f(A1))。 一般來說，f-1(f(A1))≠A1，但是A1f-1(f(A1))。例如函數(shù)f:{1,2,3}→{0,1}，滿足

f(1)＝f(2)＝0，f(3)＝1 令A1＝{1}，那么 f-1(f(A1))＝f-1(f({1}))＝f-1({0})＝{1,2} 這時，A1是f-1(f(A1))的真子集。9精選課件ppt例8.3

設(shè)f:N→N，且

令A＝{0,1}，B＝{2}，求f(A)和f1(B)。

解答f(A)＝f({0,1})＝{f(0),f(1)}＝{0,2}

f1(B)＝f1({2})＝{1,4} (因為

f(1)＝2,f(4)＝2)例8.310精選課件ppt定義8.6

設(shè)f:A→B，（1）若ranf＝B，則稱f:A→B是滿射(surjection)的。（2）若y∈ranf都存在唯一的x∈A使得f(x)＝y(tǒng)，則稱

f:A→B是單射(injection)的。（3）若f既是滿射又是單射的，則稱f:A→B是雙射(bijection)的(一一映像(one-to-onemapping))。

說明滿射、入射、雙射如果f:A→B是滿射的，則對于任意的y∈B，都存在x∈A，使得f(x)＝y(tǒng)。如果f:A→B是單射的，則對于x1、x2A且x1≠x2，一定有f(x1)≠f(x2)。

換句話說，如果對于x1、x2A有f(x1)＝f(x2)，則一定有x1＝x2。11精選課件ppt不同類型的對應關(guān)系的示例abc1234abc1234abc1234dabc1234dabc123d單射不是函數(shù)雙射函數(shù)滿射12精選課件ppt例8.4

判斷下面函數(shù)是否為單射、滿射、雙射的，為什么?(1)f：R→R，f(x)=-x2+2x-1

(2)f：Z+→R，f(x)=lnx，Z+為正整數(shù)集

(3)f：R→Z，f(x)=x

(4)f：R→R，f(x)=2x+1

(5)f：R+→R+，f(x)=(x2+1)/x，其中R+為正實數(shù)集。例8.4（1）f在x=1取得極大值0。既不是單射也不是滿射的。（2）f是單調(diào)上升的，是單射的，但不滿射。ranf={ln1,ln2,…}。（3）f是滿射的，但不是單射的，例如f(1.5)=f(1.2)=1。（4）f是滿射、單射、雙射的，因為它是單調(diào)函數(shù)并且ranf=R。（5）f有極小值f(1)=2。該函數(shù)既不是單射的，也不是滿射的。分析實數(shù)集合上函數(shù)性質(zhì)的判斷方法13精選課件ppt例8.5例8.5對于以下各題給定的A,B和f，判斷是否構(gòu)成函數(shù)f:A→B。如果是，說明f:A→B是否為單射、滿射和雙射的，并根據(jù)要求進行計算。(1)A＝{1,2,3,4,5}，B＝{6,7,8,9,10}，

f＝{<1,8>,<3,9>,<4,10>,<2,6>,<5,9>} 能構(gòu)成f:A→B，

f不是單射的，因為f(3)＝f(5)＝9,

f不是滿射的，因為7ranf。(2)A＝{1,2,3,4,5}，B＝{6,7,8,9,10}，

f＝{<1,7>,<2,6>,<4,5>,<1,9>,<5,10>} 不能構(gòu)成f:A→B，因為<1,7>∈f且<1,9>∈f。14精選課件ppt例8.5(3)A＝{1,2,3,4,5}，B＝{6,7,8,9,10}，

f＝{<1,8>,<3,10>,<2,6>,<4,9>} 不能構(gòu)成f:A→B，因為domf＝{1,2,3,4}≠A。(4)A＝B＝R，f(x)＝x 能構(gòu)成f:A→B，

且f是雙射的

。(5)A＝B＝R+，f(x)＝x/(x2+1)（x∈R+） 能構(gòu)成f:A→B，

但f既不是單射的也不是滿射的。 因為該函數(shù)在x＝1取得極大值f(1)＝1/2，函數(shù)不是單調(diào)的，且ranf

≠R+。15精選課件ppt例8.5(6)A＝B＝R×R，f(<x,y>)＝<x+y,x-y>

令L＝{<x,y>|x,y∈R∧y＝x+1}，計算f(L)。 能構(gòu)成f:A→B，且f是雙射的。 f(L)＝{<x+(x+1),x-(x+1)>|x∈R} ＝{<2x+1,-1>|x∈R}＝R×{-1}(7)A＝N×N，B＝N，f(<x,y>)＝|x2-y2|

計算f(N×{0}),f-1＝({0})。 能構(gòu)成f:A→B，

但

f既不是單射也不是滿射的。 因為f(<1,1>)＝f(<2,2>)＝0，且2ranf。

f(N×{0})＝{n2-02|n∈N}＝{n2|n∈N} f-1({0})＝{<n,n>|n∈N}16精選課件ppt例8.6例8.6對于給定的集合A和B構(gòu)造雙射函數(shù)f:A→B。（1）A＝P({1,2,3}),B＝{0,1}{1,2,3}（2）A＝[0,1],B＝[1/4,1/2]（3）A＝Z,B＝N（4）A＝[/2,3/2],B＝[1,1]17精選課件ppt例8.6的解答（1）A＝P({1,2,3}),B＝{0,1}{1,2,3} A＝{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。 B＝{f0,f1,…,f7},其中f0＝{<1,0>,<2,0>,<3,0>}, f1＝{<1,0>,<2,0>,<3,1>},

f2＝{<1,0>,<2,1>,<3,0>}, f3＝{<1,0>,<2,1>,<3,1>},

f4＝{<1,1>,<2,0>,<3,0>}, f5＝{<1,1>,<2,0>,<3,1>},

f6＝{<1,1>,<2,1>,<3,0>}, f7＝{<1,1>,<2,1>,<3,1>}。令f:A→B, f()＝f0, f({1})＝f1, f({2})＝f2, f({3})＝f3, f({1,2})＝f4, f({1,3})＝f5,

f({2,3})＝f6, f({1,2,3})＝f718精選課件ppt例8.6的解答（2）A＝[0,1],B＝[1/4,1/2]令f:A→B,f(x)＝(x+1)/4。（3）A＝Z,B＝N將Z中元素以下列順序排列并與N中元素對應：

Z：0112233…

↓↓↓↓↓↓↓

N：0123456…則這種對應所表示的函數(shù)是：（4）A=[/2,3/2],B=[1,1]令f:A→B，f(x)＝sinx。

19精選課件ppt常用函數(shù)—常函數(shù)和恒等函數(shù)設(shè)f：A→B，如果存在c∈B，使得對所有的x∈A都有f(x)＝c，則稱f：A→B是常函數(shù)。設(shè)f：A→B，對所有的x∈A都有IA(x)＝x，稱IA為A上的恒等函數(shù)。20精選課件ppt常用函數(shù)—單調(diào)遞增函數(shù)設(shè)<A,≤>，<B,≤>為偏序集，f：A→B，如果對任意的x1,x2∈A，x1＜x2，就有f(x1)≤f(x2)，則稱f為單調(diào)遞增的； 如果對任意的x1,x2∈A,x1＜x2,就有f(x1)＜

f(x2),則稱f為嚴格單調(diào)遞增的。類似的也可以定義單調(diào)遞減和嚴格單調(diào)遞減的函數(shù)。舉例：f:R→R,f(x)＝x+1是嚴格單調(diào)遞增的。 偏序集<P({a,b}),R>，<{0,1},≤>，R為包含關(guān)系，≤為一般的小于等于關(guān)系。令f：P({a,b})→{0,1}，f()＝f({a})＝f()＝0，f({a,b})=1，

f是單調(diào)遞增的,但不是嚴格單調(diào)遞增的。21精選課件ppt常用函數(shù)—特征函數(shù)設(shè)A為集合，對于任意的AA，A的特征函數(shù)A

:A→{0,1}定義為1，a∈A

0，a∈AAA(a)＝舉例:A的每一個子集A都對應于一個特征函數(shù)，不同的子集對應于不同的特征函數(shù)。 例如A＝{a,b,c},則有

＝{<a,0>,<b,0>,<c,0>}， {a}＝{<a,1>,<b,0>,<c,0>}

{a,b}＝{<a,1>,<b,1>,<c,0>}22精選課件ppt常用函數(shù)—自然映射設(shè)R是A上的等價關(guān)系，令g：A→A/R

g(a)=[a]，a∈A

稱g是從A到商集A/R的自然映射。給定集合A和A上的等價關(guān)系R，就可以確定一個自然映射g：A→A/R。

例如A＝{1,2,3}，R＝{<1,2>,<2,1>}∪IAg(1)＝g(2)＝{1,2},g(3)＝{3}不同的等價關(guān)系確定不同的自然映射，其中恒等關(guān)系所確定的自然映射是雙射，而其他的自然映射一般來說只是滿射。23精選課件ppt定義在自然數(shù)集合上的計數(shù)函數(shù)對于給定規(guī)模為n的輸入，計算算法所做基本運算的次數(shù)，將這個次數(shù)表示為輸入規(guī)模的函數(shù)。排序和檢索問題的基本運算是比較。矩陣乘法的基本運算是元素的相乘。估計算法在最壞情況下所做基本運算的次數(shù)記為W(n)。估計算法在平均情況下所做基本運算的次數(shù)記為A(n)。設(shè)f是定義在自然數(shù)集合上的函數(shù)，當n變得很大時，函數(shù)值f(n)的增長取決于函數(shù)的階。階越高的函數(shù)，算法的復雜度就越高，同時意味著算法的效率越低。算法分析的主要工作就是估計復雜度函數(shù)的階。階可以是： n，n2，n3，nlogn，logn，2n

……24精選課件ppt定義在自然數(shù)集合上的計數(shù)函數(shù)若存在正數(shù)c和n0，使得對一切n≥n0，有0≤f(n)≤cg(n)，記作f(n)＝O(g(n))。若存在正數(shù)c和n0，使得對一切n≥n0，有0≤cg(n)≤f(n)，記作f(n)＝Ω(g(n))。若f(n)＝O(g(n))且f(n)＝Ω(g(n))，則f(n)＝Θ(g(n))。例如f(n)＝1/2n2-3n，則f(n)＝Θ(n2)g(n)＝6n3，則g(n)＝Θ(n3)25精選課件ppt構(gòu)造從A到B的雙射函數(shù)有窮集之間的構(gòu)造例1

A=P({1,2,3}),B={0,1}{1,2,3}解

A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={f0,f1,…,f7},其中

f0={<1,0>,<2,0>,<3,0>},f1={<1,0>,<2,0>,<3,1>},

f2={<1,0>,<2,1>,<3,0>},f3={<1,0>,<2,1>,<3,1>},

f4={<1,1>,<2,0>,<3,0>},f5={<1,1>,<2,0>,<3,1>},

f6={<1,1>,<2,1>,<3,0>},f7={<1,1>,<2,1>,<3,1>}.

令f:A→B,f()=f0,f({1})=f1,f({2})=f2,f({3})=f3,f({1,2})=f4,f({1,3})=f5,f({2,3})=f6,f({1,2,3})=f726精選課件ppt實數(shù)區(qū)間之間構(gòu)造雙射構(gòu)造方法：直線方程例2

A=[0,1]

B=[1/4,1/2]

構(gòu)造雙射f:A→B構(gòu)造從A到B的雙射函數(shù)(續(xù))解令f:[0,1]→[1/4,1/2]f(x)=(x+1)/4

27精選課件pptA與自然數(shù)集合之間構(gòu)造雙射方法：將A中元素排成有序圖形，然后從第一個元素開始按照次序與自然數(shù)對應構(gòu)造從A到B的雙射函數(shù)(續(xù))例3

A=Z,B=N，構(gòu)造雙射f:A→B將Z中元素以下列順序排列并與N中元素對應：

Z：0112233…

↓↓↓↓↓↓↓

N：0123456…

則這種對應所表示的函數(shù)是：

28精選課件ppt8.2函數(shù)的復合與反函數(shù)函數(shù)的復合就是關(guān)系的右復合，一切和關(guān)系右復合有關(guān)的定理都適用于函數(shù)的復合。本節(jié)重點考慮在復合中特有的性質(zhì)。29精選課件ppt定理8.1(復合函數(shù)基本定理)定理8.1設(shè)F,G是函數(shù)，則FG也是函數(shù)，且滿足（1）dom(FG)＝{x|x∈domF∧F(x)∈domG}（2）x∈dom(FG)，有FG(x)＝G(F(x))30精選課件ppt證明：

先證明FG是函數(shù)。

因為F、G是關(guān)系，所以FG也是關(guān)系。 若對某個x∈dom(FG)，若有xFGy1和xFGy2，則

<x,y1>∈FG∧<x,y2>∈FG

t1(<x,t1>∈F∧<t1,y1>∈G)∧t2(<x,t2>∈F∧<t2,y2>∈G) t1t2(t1＝t2∧<t1,y1>∈G∧<t2,y2>∈G) （F為函數(shù)） y1＝y(tǒng)2 （G為函數(shù)） 所以FG為函數(shù)。定理8.1的證明31精選課件ppt定理8.1的證明任取x，(要證明dom(FG)＝{x|x∈domF∧F(x)∈domG})x∈dom(FG)

ty(<x,t>∈F∧<t,y>∈G)

t(x∈domF∧t＝F(x)∧t∈domG)

x∈{x|x∈domF∧F(x)∈domG} 所以（1）得證。任取x，（要證明x∈dom(FG)，有FG(x)＝G(F(x))）x∈domF∧F(x)∈domG<x,F(x)>∈F∧<F(x),G(F(x))>∈G<x,G(F(x))>∈FG

x∈dom(FG)∧FG(x)＝G(F(x))

所以（2）得證。32精選課件ppt推論1設(shè)F,G,H為函數(shù)，則(FG)H和F(GH)都是函數(shù)，且(FG)H=F(GH)證明：由定理8.1（復合函數(shù)基本定理）和定理7.2（關(guān)系合成具有結(jié)合性）得證。定理8.1的推論133精選課件ppt推論2設(shè)f：A→B，g：B→C，則fg：A→C，且x∈A都有fg(x)=g(f(x))。證明：由定理8.1（復合函數(shù)基本定理）可知fg是函數(shù)，且 dom(fg) ＝{x|x∈domf∧f(x)∈domg} ＝{x|x∈A∧f(x)∈B} ＝A

ran(fg)rang

C

因此fg：A→C，且x∈A有fg(x)＝g(f(x))。定理8.1的推論234精選課件ppt定理8.2設(shè)f：A→B，g：B→C。（1）如果f：A→B，g：B→C都是滿射的，則fg：A→C

也是滿射的。（2）如果f：A→B，g：B→C都是單射的，則fg：A→C也

是單射的。（3）如果f：A→B，g：B→C都是雙射的，則fg：A→C也

是雙射的。說明函數(shù)的復合運算的性質(zhì)該定理說明函數(shù)的復合能夠保持函數(shù)單射、滿射、雙射的性質(zhì)。35精選課件ppt定理8.2的證明(1)如果f：A→B，g：B→C都是滿射的，則fg：A→C也

是滿射的。證明：任取c∈C，由g：B→C的滿射性，所以

b∈B使得g(b)=c。對于這個b，由f：A→B的滿射性，所以a∈A使得f(a)=b。由合成定理有

fg(a)＝g(f(a))＝g(b)＝c所以，fg：A→C是滿射的。

36精選課件ppt定理8.2的證明(2)如果f：A→B，g：B→C都是單射的，則fg：A→C也是

單射的。證明：假設(shè)存在x1,x2∈A使得fg(x1)＝fg(x2)，由合成定理有g(shù)(f(x1))=g(f(x2)) 因為g：B→C是單射的，故f(x1)＝f(x2)。 又由于f：A→B也是單射的，所以x1＝x2。 所以，fog：A→C是單射的。(3)如果f：A→B，g：B→C都是雙射的，則fg：A→C也

是雙射的。證明：由（1）和（2）得證。37精選課件ppt定理8.2之逆不為真考慮集合A＝{a1,a2,a3}，B＝{b1,b2,b3,b4}，C＝{c1,c2,c3}。 令 f＝{<a1,b1>,<a2,b2>,<a3,b3>}

g＝{<b1,c1>,<b2,c2>,<b3,c3>,<b4,c3>} 則 fg={<a1,c1>,<a2,c2>,<a3,c3>} 那么f:A→B和fg:A→C都是單射的，但g:B→C不是單射的。考慮集合A={a1,a2,a3}，B={b1,b2,b3}，C={c1,c2}。 令 f＝{<a1,b1>,<a2,b2>,<a3,b2>} g＝{<b1,c1>,<b2,c2>,<b3,c2>} 則 fg＝{<a1,c1>,<a2,c2>,<a3,c2>} 那么g:B→C和fg:A→C是滿射的，但f:A→B不是滿射的。38精選課件ppt定理8.3定理8.3設(shè)f：AB，則f＝foIB＝IAof

證明：由定理8.1的推論2可知

foIB：AB

和IAof：AB任取<x,y>，<x,y>∈f<x,y>∈f∧yB<x,y>∈f∧

<y,y>IB<x,y>∈foIB所以，

f

foIB<x,y>∈foIBt(<x,t>∈f∧

<t,y>IB)<x,t>∈f∧

t=y<x,y>∈f所以，foIB

f所以，f＝

foIB同理可證f＝

IAof

39精選課件ppt什么樣的函數(shù)f：A→B，它的逆f1是從B到A的函數(shù)呢？任給函數(shù)F,它的逆F1不一定是函數(shù),只是一個二元關(guān)系。

F＝{<x1,y1>，<x2,y1>}

F-1＝{<y1,x1>，<y1,x2>}任給單射函數(shù)f：A→B,則f1是函數(shù),且是從ranf到A的雙射函數(shù),但不一定是從B到A的雙射函數(shù)。 因為對于某些y∈B－ranf，f-1沒有值與之對應。任給滿射函數(shù)f：A→B，則f1不一定是函數(shù)。對于雙射函數(shù)f：A→B,f1：B→A是從B到A的雙射函數(shù)。

反函數(shù)40精選課件ppt定理8.4設(shè)f：A→B是雙射的，則f1：B→A也是雙射的。證明： 先證明f-1：B→A是函數(shù)，且domf1＝B，ranf1＝A。

因為f是函數(shù)，所以f1是關(guān)系，且

domf

1＝ranf＝B,ranf1＝domf＝A，

對于任意的x∈B＝domf1，

假設(shè)有y1,y2∈A，使得<x,y1>∈f

1∧<x,y2>∈f

1成立，

則由逆的定義有，<y1,x>∈f∧<y2,x>∈f。

根據(jù)

f的單射性，可得y1＝y(tǒng)2。

所以，f-

1是函數(shù)。反函數(shù)存在的條件41精選課件ppt再證明f-1：B→A的雙射性質(zhì)。（證明單射）若存在x1,x2∈B，使得f

1(x1)=f

1(x2)=y，從而有<x1,y>∈f

1∧<x2,y>∈f

1<y,x1>∈f∧<y,x2>∈f

x1＝x2（因為f是函數(shù)）所以，f-

1是單射的。（證明滿射）對于任意的y∈A

，因為f是雙射的，所以必存在x∈B

，使得<y,x>∈f，所以<x,y>∈f

1，所以，f

1是滿射的。綜上所述，f

1是雙射函數(shù)。說明定理8.4的證明對于雙射函數(shù)f：A→B，稱f-

1：B→A是它的反函數(shù)。42精選課件ppt反函數(shù)的性質(zhì)定理8.5設(shè)f：A→B是雙射的，則f-1f=IB，ff-1=IA證明：根據(jù)定理可知f-1：B→A也是雙射的，且

f-1f：B→B，ff-1：A→A。

任取<x,y><x,y>f

1ft(<x,t>f1

∧

<t,y>f)t(<t,x>f∧

<t,y>f)x=y∧x,yB<x,y>IB所以，f-1f

IB<x,y>IBx＝y(tǒng)∧x,yBt(<t,x>f∧

<t,y>f)t(<x,t>f1

∧

<t,y>f)<x,y>f-1f所以，IB

f-1f綜上所述，f-1f＝

IB。同理可證

ff-1＝IA43精選課件ppt例8.8例8.8設(shè)f：R→R,g：R→R

求fg，gf。如果f和g存在反函數(shù)，求出它們的反函數(shù)。解答g：R→R是雙射的，它的反函數(shù)是

g1：R→R，g1(x)=x244精選課件ppt定義8.8

設(shè)A,B是集合，如果存在著從A到B的雙射函數(shù)，就稱A和B是等勢（samecardinality）的，記作A≈B。 如果A不與B等勢，則記作AB。8.3雙射函數(shù)與集合的基數(shù)≈通俗的說，集合的勢是量度集合所含元素多少的量。集合的勢越大，所含的元素越多。45精選課件ppt（1）Z≈N。則f是Z到N的雙射函數(shù)。從而證明了Z≈N。等勢集合的實例(1)46精選課件ppt等勢集合的實例(2)（2）

N×N≈N。雙射函數(shù)47精選課件ppt等勢集合的實例(3)（3）N≈Q。把所有形式為p/q(p,q為整數(shù)且q>0)的數(shù)排成一張表。-2/1[5]-1/1[4]-3/1[18]2/1[10]3/1[11]0/1[0]1/1[1]-2/2-1/2[3]-3/2[17]2/23/2[12]0/21/2[2]-2/3[6]-1/3[7]-3/32/3[9]3/30/31/3[8]-2/4-1/4[15]-3/4[16]2/43/4[13]0/41/4[14]……………………以0/1作為第一個數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍”表中所有的數(shù)。計數(shù)過程中必須跳過第二次以及以后各次所遇到的同一個有理數(shù)。48精選課件ppt等勢集合的實例(4)（4）(0,1)≈R。其中實數(shù)區(qū)間(0,1)={x|x∈R∧0<x<1}。令雙射函數(shù)則f是(0,1)到R的雙射函數(shù)。從而證明了(0,1)≈R

。49精選課件ppt等勢集合的實例(5)（5）[0,1]≈(0,1)。其中(0,1)和[0,1]分別為實數(shù)開區(qū)間和閉區(qū)間。雙射函數(shù)

f:[0,1](0,1)，250精選課件ppt等勢集合的實例(6)（6）對任何a,b∈R，a<b，[0,1]≈[a,b]。

雙射函數(shù)f：[0,1]→[a,b]，f(x)＝(ba)x+a。51精選課件ppt例8.10

設(shè)A為任意集合，則P(A)≈{0,1}A。構(gòu)造f：P(A)→{0,1}A，

f(A)=A，A∈P(A)。

其中A是集合A的特征函數(shù)。(1)易證f是單射的。(2)對于任意的g∈{0,1}A，那么有g(shù)：A→{0,1}。令 B={x|x∈A∧g(x)=1}則BA，且B=g，即B∈P(A)，使得f(B)=g。

所以f是滿射的。由等勢定義得P(A)≈{0,1}A。例8.10證明復習52精選課件ppt定理8.6

設(shè)A，B，C是任意集合，（1）A≈A。（2）若A≈B，則B≈A。（3）若A≈B，B≈C，則A≈C。（1） IA是從A到A的雙射，因此A≈A。（2） 假設(shè)A≈B，存在f:

AB是雙射， 那么f1:

BA是從B到A的雙射，所以B≈A。（3） 假設(shè)A≈B，B≈C，存在f:AB，g:BC是雙射， 則fg:

AC是從A到C的雙射。

所以A≈C。等勢的性質(zhì)證明53精選課件ppt

N≈Z≈Q≈N×NR≈[0,1]≈(0,1)任何的實數(shù)區(qū)間（開區(qū)間、閉區(qū)間以及半開半閉的區(qū)間）都與實數(shù)集合R等勢。問題：N和R是否等勢？若干等勢集合54精選課件ppt（1）如果能證明N[0,1]，就可以斷定NR。

只需證明任何函數(shù)f：N→[0,1]都不是滿射的。構(gòu)造一個[0,1]區(qū)間的小數(shù)b，使得b在N中不存在原像。（2）任取函數(shù)f：AP(A)，構(gòu)造B∈P(A)，使得B在A中不存在原像。 或者使用反證法。定理8.7

康托定理（1）NR。（2）對任意集合A都有AP(A)?？低卸ɡ怼帧帧帧址治?5精選課件ppt（1）首先規(guī)定[0,1]中數(shù)的表示。

對任意的x∈[0,1]，令x=0.x1x2…,（0≤xi≤9）

注意：為了保證表示式的唯一性，如果遇到0.24999…，則將x表示為0.25000…。

設(shè)f:N→[0,1]是從N到[0,1]的任何一個函數(shù)。f的所有函數(shù)值為：

f(0)=0.a1(1)a2(1)…

f(1)=0.a1(2)a2(2)…

…

f(n1)=0.a1(n)a2(n)…

…

令y的表示式為0.b1b2…，并且滿足bi≠ai(i)，i=1,2,…， 則y∈[0,1]，

但y與上面列出的任何一個函數(shù)值都不相等。 即f不是滿射的。

所以，NR。康托定理≈56精選課件ppt康托定理假設(shè)A≈P(A)，則必有函數(shù)f:A→P(A)是雙射函數(shù)。 如下構(gòu)造集合B：

B＝{x|x∈A∧xf(x)}

可知

B∈P(A)。

于是存在唯一一個元素b∈A，使得f(b)＝B。

若b∈B，則由B的定義知，bf(b)，即bB，矛盾。

若bB，則bf(b)，于是由B的定義知，b∈B，矛盾。57精選課件ppt（2）設(shè)g：A→P(A)是從A到P(A)的任意函數(shù)，如下構(gòu)造集合B：

B＝{x|x∈A∧xg(x)}

則B∈P(A)。但是對任意x∈A，都有

x∈B

xg(x) 所以，對任意的x∈A都有B≠g(x)，即Brang 即P(A)

中存在元素B，在A中找不到原像。所以，g不是滿射的。所以，AP(A)。說明康托定理≈根據(jù)這個定理可以知道NP(N)。綜合前面的結(jié)果，可知N

{0,1}N。實際上，P(N)，{0,1}N和R都是比N“更大”的集合。

≈≈58精選課件ppt定義8.9（1）設(shè)A,B是集合，如果存在從A到B的單射函數(shù)，就稱B優(yōu)勢于A，記作A≤·B。如果B不是優(yōu)勢于A，則記作A≤·B。（2）設(shè)A,B是集合，若A≤·B且AB，則稱B真優(yōu)勢于A，記作A＜·B。如果B不是真優(yōu)勢于A，則記作A≮·B。例如：N≤·

NN≤·

RA≤·

P(A)N＜·RA＜·

P(A)R≮·

N

N≮·

N優(yōu)勢≈R≤·N59精選課件ppt定理8.8

設(shè)A,B,C是任意的集合，則（1）A≤·

A。（2）若A≤·

B且B≤·

A，則A≈B。（3）若A≤·

B且B≤·

C,則A≤·

C

。證明：（1）IA是A到A的單射，因此A≤·

A。（2）證明略。（3）假設(shè)A≤·

B且B≤·

C，那么存在單射f:A→B，g:B→C，于是fg：A→C也是單射的，因此A≤·

C

。優(yōu)勢的性質(zhì)說明該定理為證明集合之間的等勢提供了有力的工具。構(gòu)造兩個單射f：AB和g：BA函數(shù)容易集合等勢。60精選課件ppt例題例題：證明[0,1]與(0,1)等勢。證明：構(gòu)造兩個單射函數(shù)f:(0,1)→[0,1]，f(x)＝xg:[0,1]→(0,1)，g(x)＝x/2+1/461精選課件ppt證明{0,1}N≈[0,1)(1)設(shè)x[0,1)，0.x1x2…是x的二進制表示。為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無數(shù)個1。例如x＝0.1010111，應按規(guī)定記為0.1011000。對于x，如下定義f：[0,1)→{0,1}N，使得

f(x)=tx，且tx：N→{0,1}，tx(n)=xn+1，n=0,1,2,…例如x=0.10110100…，則對應于x的函數(shù)tx是： n 01234567… tx(n) 10110100…易見tx∈{0,1}N，且對于x,y∈[0,1)，x≠y，必有tx≠ty，

即f(x)≠f(y)。所以，f：[0,1)→{0,1}N是單射的。62精選課件ppt(2)定義函數(shù)g：{0,1}N→[0,1)。

g的映射法則恰好與f相反，即t∈{0,1}N，t：N→{0,1}，g(t)=0.x1x2…,其中xn+1=t(n)。但不同的是，將0.x1x2…看作數(shù)x的十進制表示。 例如t1，t2∈{0,1}N，且g(t1)＝0.0111…，g(t2)＝0.1000…， 若將g(t1)和g(t2)都看成二進制表示，則g(t1)＝g(t2)； 但若看成十進制表示，則g(t1)≠g(t2)。所以，g：{0,1}N→[0,1)是單射的。根據(jù)定理9.3，有{0,1}N≈[0,1)。證明{0,1}N≈[0,1)63精選課件ppt總結(jié)N≈Z≈Q≈N×NR≈[a,b]≈(c,d)≈{0,1}N≈P(N)

其中[a,b]，(c,d)代表任意的實數(shù)閉區(qū)間和開區(qū)間。{0,1}A≈P(A)N＜·RA＜·

P(A)64精選課件ppt8.3.2集合的基數(shù)

上一節(jié)我們只是抽象地討論了集合的等勢與優(yōu)勢。本節(jié)將進一步研究度量集合的勢的方法。最簡單的集合是有窮集。盡管前面已經(jīng)多次用到“有窮集”這一概念，當時只是直觀地理解成含有有限多個元素的集合，但一直沒有精確地給出有窮集的定義。為解決這個問題我們需要先定義自然數(shù)和自然數(shù)集合。65精選課件ppt定義9.38.10設(shè)a為集合，稱a∪{a}為a的后繼，記作a+，即

a+=a∪{a}。

例

考慮空集的一系列后繼。+

=∪{}={}

++

={}+={}∪{{}}={,{}}={,+}

+++

={,{}}+={,{}}∪{{,{}}}={,{},{,{}}}={,+,++}后繼

說明前邊的集合都是后邊集合的元素。前邊的集合都是后邊集合的子集。66精選課件ppt利用后繼的性質(zhì)，可以考慮以構(gòu)造性的方法用集合來給出自然數(shù)的定義，即 0= 1=0+＝+＝{}＝{0} 2=1+＝{}+＝{}∪{{}}＝{,{}}＝{0,1} 3＝2+＝{,{}}+＝{,{},{,{}}}＝{0,1,2}

… n＝{0,1,…,n1} …說明自然數(shù)的定義

這種定義沒有概括出自然數(shù)的共同特征。67精選課件ppt（1） 對任何自然數(shù)n，有n≈n。（2） 對任何自然數(shù)n,m，若m

n，則m≈n。（3） 對任何自然數(shù)n,m，若m∈n，則m

n。（4） 對任何自然數(shù)n和m，以下三個式子：

m∈n，m≈n，n∈m

必成立其一且僅成立其一。（5） 自然數(shù)的相等與大小順序 對任何自然數(shù)m和n，有 m=n

m≈n

m<n

m∈n

自然數(shù)的性質(zhì)

68精選課件ppt定義8.11

有窮集、無窮集（1）一個集合是有窮的當且僅當它與某個自然數(shù)等勢；（2）如果一個集合不是有窮的，就稱作無窮集。例如：{a,b,c}是有窮集，因為3＝{0,1,2}，且{a,b,c}≈{0,1,2}＝3N和R都是無窮集，

因為沒有自然數(shù)與N和R等勢。任何有窮集只與唯一的自然數(shù)等勢。說明有窮集和無窮集

69精選課件ppt定義8.12（1）對于有窮集合A，稱與A等勢的那個唯一的自然數(shù)為A的基數(shù)，記作cardA，即cardA＝n

A≈n

（對于有窮集A，cardA也可以記作|A|）（2）自然數(shù)集合N的基數(shù)記作0，即cardN=0（3）實數(shù)集R的基數(shù)記作（讀作阿列夫），即cardR=

基數(shù)(cardinality)

70精選課件ppt定義8.13設(shè)A,B為集合，則（1）cardA＝cardB

A≈B（2）cardA≤cardB

A≤·

B（3）cardA<cardBcardA≤cardB∧cardA≠cardB例如：cardZ＝cardQ＝cardN×N＝0cardP(N)＝card2N＝card[a,b]＝card(c,d)＝0<說明：集合的基數(shù)就是集合的勢，基數(shù)越大，勢就越大?；鶖?shù)的相等和大小

71精選課件ppt關(guān)于基數(shù)的說明

由于對任何集合A都滿足A≤P(A)，所以有

cardA<

cardP(A)，這說明不存在最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到： 0,1,2,…,n,…,0,,…0,1,2…,n,…是全體自然數(shù)，是有窮基數(shù)。0,,…是無窮基數(shù)。0是最小的無窮基數(shù)，后面還有更大的基數(shù)，如

cardP(R)等。72精選課件ppt可數(shù)集定義8.14

設(shè)A為集合，若cardA≤0，則稱A為可數(shù)集(enumerable)或可列集。例如：

{a,b,c}、5、整數(shù)集Z、有理數(shù)集Q、N×N等都是可數(shù)集。實數(shù)集R不是可數(shù)集，與R等勢的集合也不是可數(shù)集。

對于任何的可數(shù)集，都可以找到一個“數(shù)遍”集合中全體元素的順序。回顧前邊的可數(shù)集，特別是無窮可數(shù)集，都是用這種方法來證明的。說明73精選課件ppt（1）可數(shù)集的任何子集都是可數(shù)集。

一個集合的無限子集若不可數(shù)，則該集合也不可數(shù)。（2）兩個可數(shù)集的并是可數(shù)集。（3）兩個可數(shù)集的笛卡兒積是可數(shù)集。（4）可數(shù)個可數(shù)集的笛卡兒積仍是可數(shù)集。（5）無窮集A的冪集P(A)不是可數(shù)集。

可數(shù)集的性質(zhì)

74精選課件ppt例8.11

求下列集合的基數(shù)。（1）T＝{x|x是單詞“BASEBALL”中的字母}（2）B＝{x|x∈R∧x2=9∧2x=8}（3）C＝P(A),A={1,3,7,11}（1）由T＝{B,A,S,E,L}知，cardT＝5。（2）由B＝可知，cardB＝0。（3）由|A|＝4可知，cardC＝cardP(A)＝|P(A)|＝24＝16。解答例8.1175精選課件ppt方法一由cardA＝0，cardB＝n，可知A,B都是可數(shù)集。令A={a0,a1,

a2,…}，B={b0,

b1,

b2,…,

bn1}。對任意的<ai,

bj>，<ak,

bl>∈A×B，有

<ai,

bj>＝<ak,

bl>

i＝k∧j＝l定義函數(shù)f：A×B→N

f(<ai,

bj>)＝in+j,i＝0,1,…,j＝0,1,…,n1由于f是A×B到N的雙射函數(shù)，所以cardA×B＝cardN＝。例8.12解答例8.12

設(shè)A,B為集合，且cardA＝0，cardB＝n，n是自然數(shù)，n≠0。求cardA×B。76精選課件ppt例8.12方法二因為cardA＝0，cardB＝n，所以A,B都是可數(shù)集。根據(jù)性質(zhì)（3）可知，A×B也是可數(shù)集，所以， cardA×B≤0

當B≠時，cardA≤cardA×B，這就推出

0≤cardA×B綜合所述，cardA×B＝

077精選課件ppt本章主要內(nèi)容函數(shù)的基本概念與性質(zhì)（單射，滿射，雙射）。

函數(shù)的合成與反函數(shù)。

78精選課件ppt本章主要內(nèi)容（續(xù)）集合等勢的定義等勢的性質(zhì)集合優(yōu)勢的定義優(yōu)勢的性質(zhì)重要的集合等勢以及優(yōu)勢的結(jié)果可數(shù)集與不可數(shù)集集合的基數(shù)

79精選課件ppt本章學習要求掌握函數(shù)、A到B的函數(shù)、集合在函數(shù)下的像、集合在函數(shù)下的完全原像的概念及表示法；當A與B都是有窮集時，會求A到B的函數(shù)的個數(shù)。

掌握A到B的函數(shù)是單射、滿射、和雙射的定義及證明方法。

掌握常函數(shù)、恒等函數(shù)、單調(diào)函數(shù)、特征函數(shù)、自然映射等概念。

掌握合成函數(shù)的主要性質(zhì)和求合成函數(shù)的方法。

掌握反函數(shù)的概念及主要性質(zhì)。

80精選課件ppt本章學習要求（續(xù)）能夠證明兩個集合等勢。能夠證明一個集合優(yōu)勢于另一個集合。知道什么是可數(shù)集與不可數(shù)集。會求一個簡單集合的基數(shù)。

81精選課件ppt對于任意的<x,y>,<u,v>RR,有證明：任取<u,v>RR，存在RR，使得因此f是滿射的。因此f是單射的。例題證明f既是滿射的，也是單射的。其中82精選課件ppt例題令X＝{x1,x2,…,xm}，Y={y1,y2,…,yn}，問（1）

有多少不同的由X到Y(jié)的關(guān)系？（2）

有多少不同的X到Y(jié)的映射？（3）

有多少不同的由X到Y(jié)的單射、雙射？解：（1）

有2mn不同的由X到Y(jié)的關(guān)系。

（2）

有nm不同的X到Y(jié)的映射。

（3）

X到Y(jié)的單射個數(shù)為：

若mn，有0個單射。

若m＝n，有m!個單射。

只有m＝n時，才存在X到Y(jié)的雙射，個數(shù)為m!。

若mn，有

個單射。83精選課件ppt設(shè)A、B、C、D是任意集合，f是A到B的雙射，g是C到D的雙射。令h:ACBD，且<a,c>AC，h(<a,c>)=<f(a),g(c)>，那么h是雙射嗎？請證明你的判斷。證明：先證明h是滿射。

<b,d>BD，則bB，dD，因為f是A到B的雙射，g是C到D的雙射,所以，aA，cC，使得f(a)=b，g(c)=d，

也就是<a,c>AC，使得h(<a,c>)=<f(a),g(c)>=<b,d>,所以，h是滿射。例題84精選課件ppt例題再證h是單射。

<a1,c1>,<a2,c2>AC，若h(<a1,c1>)=h(<a2,c2>)，則 <f(a1),g(c1)>=<f(a2),g(c2)>所以，f(a1)=f(a2)，g(c1)=g(c2)。因為f是A到B的雙射，g是C到D的雙射,

所以，a1

=a2，c1=c2。所以，<a1,c1>=<a2,c2>，所以，h是單射。綜上所述，h是雙射。85精選課件ppt等勢的證明方法證明集合A與B等勢的方法直接構(gòu)造從A到B的雙射函數(shù)f 需要證明f的滿射性和f的單射性。構(gòu)造兩個單射函數(shù)f：AB和g：BA。給出函數(shù)f和g，證明f和g的單射性。利用等勢的傳遞性直接計算A與B的基數(shù)，得到cardA＝cardB。證明集合A與自然數(shù)集合N等勢的方法找到一個“數(shù)遍”A中元素的順序。86精選課件ppt例題選講1．已知A＝{n7|n∈N}，B＝{n109|n∈N}，求下列各題：（1）