離散數(shù)學(xué)離散第八章

1、廣東工業(yè)大學(xué)計算機學(xué)院1第八章第八章 函數(shù)函數(shù)主要內(nèi)容主要內(nèi)容8.1 函數(shù)的定義與性質(zhì)函數(shù)的定義與性質(zhì)l 函數(shù)定義函數(shù)定義l 函數(shù)性質(zhì)函數(shù)性質(zhì)8.2 函數(shù)運算函數(shù)運算l 函數(shù)的逆函數(shù)的逆l 函數(shù)的合成函數(shù)的合成8.3 雙射函數(shù)與集合的基數(shù)雙射函數(shù)與集合的基數(shù)(課外閱讀課外閱讀)廣東工業(yè)大學(xué)計算機學(xué)院28.1 函數(shù)的定義與性質(zhì)函數(shù)的定義與性質(zhì)主要內(nèi)容主要內(nèi)容1. 函數(shù)定義與相關(guān)概念函數(shù)定義與相關(guān)概念l 函數(shù)定義函數(shù)定義l 函數(shù)相等函數(shù)相等l 從從A到到B的函數(shù)的函數(shù)f:ABl BAl 函數(shù)的像與完全原像函數(shù)的像與完全原像2. 函數(shù)的性質(zhì)函數(shù)的性質(zhì)l 單射、滿射、雙射函數(shù)的定義與實例單射、滿射、雙

2、射函數(shù)的定義與實例l 構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù)3. 某些重要的函數(shù)某些重要的函數(shù)廣東工業(yè)大學(xué)計算機學(xué)院3函數(shù)定義函數(shù)定義定義定義8.1 設(shè)設(shè) F 為二元關(guān)系為二元關(guān)系, 若若 xdomF 都存在唯一的都存在唯一的yranF 使使 xFy 成立成立, 則稱則稱 F 為為函數(shù)函數(shù) 對于函數(shù)對于函數(shù)F, 如果有如果有 xFy, 則記作則記作 y=F(x), 并稱并稱 y 為為F 在在 x 的的值值. 例例 F1 = , , F2 = , F1是函數(shù)是函數(shù), F2不是函數(shù)不是函數(shù)定義定義8.2 設(shè)設(shè)F, G 為函數(shù)為函數(shù), 則則 F=G F GG F 如果兩個函數(shù)如果兩個函數(shù)F 和和 G 相等相等,

3、一定滿足下面兩個條件：一定滿足下面兩個條件： (1) domF = domG (2) xdomF = domG 都有都有F(x) = G(x) 例：例：函數(shù)函數(shù)F(x) = (x2 1)/(x+1)與與G(x) = x 1不相等不相等, 因為因為 domF domG廣東工業(yè)大學(xué)計算機學(xué)院4從從A到到B的函數(shù)的函數(shù)定義定義8.3 設(shè)設(shè)A, B為集合為集合, 如果如果 f 為函數(shù)為函數(shù), domf=A, ranf B, 則稱則稱 f 為為從從A到到B的函數(shù)的函數(shù), 記作記作 f：AB.例例 f：NN, f(x) = 2x 是從是從N到到N的函數(shù)的函數(shù), g：NN, g(x) = 2 也是從也是從N

4、到到N的函數(shù)的函數(shù). 定義定義8.4 所有從所有從A到到B的的函數(shù)的集合函數(shù)的集合記作記作BA, 符號化表示為符號化表示為 BA = f | f：AB |A| = m, |B| = n, 且且m, n0, |BA|=nmA = , 則則BA = B = A且且B = , 則則BA = A = 廣東工業(yè)大學(xué)計算機學(xué)院5實例實例例例1 設(shè)設(shè)A = 1, 2, 3, B = a, b, 求求BA.解解BA = f0, f1, , f7, 其中其中 f0 = , , f1 = , , f2 = , , f3 = , , f4 = , , f5 = , , f6 = , , f7 = , , 注意注意:

5、 1. 有序?qū)Φ牡谝辉鞑幌嗤行驅(qū)Φ牡谝辉鞑幌嗤?. 定義域中每一個元素都必定義域中每一個元素都必須出現(xiàn)須出現(xiàn)廣東工業(yè)大學(xué)計算機學(xué)院6函數(shù)的像和完全原像函數(shù)的像和完全原像定義定義8.5 設(shè)函數(shù)設(shè)函數(shù) f：AB, A1 A, B1 B(1) A1在在 f 下的像下的像 f(A1) = f(x) | xA1, 函數(shù)的像函數(shù)的像 f(A) (2) B1在在 f 下的完全原像下的完全原像 f 1(B1) = x|xAf(x)B1注意注意：(1) 函數(shù)值與像的區(qū)別：函數(shù)值函數(shù)值與像的區(qū)別：函數(shù)值 f(x)B, 像像f(A1) Bl (2) 一般說來一般說來 f 1(f(A1)A1, 但是但是A1 f

6、 1(f(A1)l 例如函數(shù)例如函數(shù)f: 1, 2, 3 0, 1，滿足，滿足f(1) = f(2) = 0, f(3) = 1令令A(yù)1 = 1，則有，則有f 1(f(A1) = f 1(f(1) = f 1(0) = 1, 2例例 設(shè)設(shè) f：NN, 且且令令A(yù) = 0,1, B = 2, 那么有那么有 f(A) = f(0, 1) = f(0), f(1) = 0, 2 f 1(B) = f 1(2) = 1, 4 為奇數(shù)為奇數(shù)若若為偶數(shù)為偶數(shù)若若xxxxxf12/)(廣東工業(yè)大學(xué)計算機學(xué)院7函數(shù)的性質(zhì)函數(shù)的性質(zhì)定義定義8.6 設(shè)設(shè) f：AB,(1) 若若 ranf = B, 則稱則稱 f:

7、AB是是滿射滿射的的(2) 若若 yranf 都存在唯一的都存在唯一的 xA 使得使得 f(x)=y, 則稱則稱 f: AB 是是單射單射的的(3) 若若 f: AB 既是滿射又是單射的既是滿射又是單射的, 則稱則稱 f: AB是是雙射雙射的的例例2 判斷下面函數(shù)是否為單射判斷下面函數(shù)是否為單射, 滿射滿射, 雙射的雙射的, 為什么為什么?(1) f: RR, f(x) = x2+2x 1 在在x=1取得極大值取得極大值0. 既不是單射也不是滿射的既不是單射也不是滿射的(2) f: Z+R, f(x) = lnx, Z+為正整數(shù)集為正整數(shù)集 是單調(diào)上升的是單調(diào)上升的, 是單射的是單射的. 但不

8、滿射但不滿射, ranf = ln1, ln2, .廣東工業(yè)大學(xué)計算機學(xué)院8例題解答例題解答解：解：(3) f: RZ, f(x) = x 是滿射的是滿射的, 但不是單射的但不是單射的, 例如例如f(1.5) = f(1.2) = 1(4) f: RR, f(x)=2x+1 是滿射、單射、雙射的是滿射、單射、雙射的, 因為它是單調(diào)函數(shù)并且因為它是單調(diào)函數(shù)并且ranf=R(5) f: R+R+, f(x)=(x2+1)/x 有極小值有極小值 f(1)=2. 該函數(shù)既不是單射的也不是滿射的該函數(shù)既不是單射的也不是滿射的廣東工業(yè)大學(xué)計算機學(xué)院9特殊函數(shù)的圖形表示特殊函數(shù)的圖形表示廣東工業(yè)大學(xué)計算機學(xué)

9、院10從定義可知從定義可知: 當(dāng)當(dāng)A、B為有限集時為有限集時, f: AB1. f 為單射的必要條件是為單射的必要條件是 |A|B|；2. f 為滿射的必要條件是為滿射的必要條件是 |A|B|；3. f 為雙射的必要條件是為雙射的必要條件是 |A| = |B|。討論：討論：設(shè)設(shè) |A| = n, |B| = m,(1) 當(dāng)當(dāng)n m, AB中共含的中共含的單單射射函數(shù)函數(shù)： 滿滿射函數(shù)：射函數(shù)：關(guān)于特殊函數(shù)的討論關(guān)于特殊函數(shù)的討論ABnmCnmP0n!0!rnm12211001111nnnnrnrnrrn廣東工業(yè)大學(xué)計算機學(xué)院11舉例舉例1已知已知 A1=a ,b, B1 = 1, 2, 3,

10、求求A1B1求求A1B1中的單射、滿射、雙射函數(shù)中的單射、滿射、雙射函數(shù).解解: |A| = 2, |B| = 3，無滿射，無雙射。，無滿射，無雙射。 A1B1中單射有中單射有 = 6個：個： f1 = , , f2 = , , f3 = , , f4 = , , f5 = , , f6 = , . 23P廣東工業(yè)大學(xué)計算機學(xué)院12舉例舉例2例例2：A2 = a, b, c, B2 = 1, 2, 求求A2B2的單射、滿射、雙的單射、滿射、雙射函數(shù)射函數(shù).解解: (2) |A| =3, |B| = 2，無單射，無雙射，無單射，無雙射. A2B2中中滿射滿射 = 6個個: f1 = , , ,

11、f2 = , , , f3 = , , , f4 = , , , f5 = , , , f6 = , , . 1!mnnCm廣東工業(yè)大學(xué)計算機學(xué)院13某些重要函數(shù)某些重要函數(shù)定義定義8.7 (1)設(shè)設(shè) f:AB, 如果存在如果存在cB使得對所有的使得對所有的 xA都有都有 f(x) = c, 則稱則稱 f: AB是是常函數(shù)常函數(shù).(2) 稱稱 A上的恒等關(guān)系上的恒等關(guān)系IA為為A上的上的恒等函數(shù)恒等函數(shù), 對所有的對所有的xA都有都有IA(x) = x.(3) 設(shè)設(shè), 為偏序集，為偏序集，f: AB，如果對任意的，如果對任意的 x1, x2A, x1 x2, 就有就有 f(x1) f(x2),

12、 則稱則稱 f 為為單調(diào)遞增單調(diào)遞增的；如的；如果對任意的果對任意的x1, x2A, x1 x2, 就有就有f(x1) f(x2), 則稱則稱 f 為為嚴(yán)嚴(yán)格單調(diào)遞增格單調(diào)遞增的的. 類似的也可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù)類似的也可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù)例：例：(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) = 1 f 是單調(diào)遞增的是單調(diào)遞增的, 但不是嚴(yán)格單調(diào)遞增的但不是嚴(yán)格單調(diào)遞增的廣東工業(yè)大學(xué)計算機學(xué)院14(4) 設(shè)設(shè)A

13、為集合為集合, 對于任意的對于任意的A A, A的的特征函數(shù)特征函數(shù) A: A0, 1定義為定義為 A(a) = 1, a A A(a) = 0, a A A舉例：舉例：A的每一個子集的每一個子集 A都對應(yīng)于一個特征函數(shù)都對應(yīng)于一個特征函數(shù), 不同的子不同的子集對應(yīng)于不同的特征函數(shù)集對應(yīng)于不同的特征函數(shù). 例如例如A = a, b, c, 則有則有 =, , ， a, b=, , 某些重要函數(shù)某些重要函數(shù)(續(xù)續(xù)1)廣東工業(yè)大學(xué)計算機學(xué)院15(5) 設(shè)設(shè)R是是A上的等價關(guān)系上的等價關(guān)系, 令令 g: AA/R g(a) = a, aA稱稱 g 是從是從 A 到商集到商集 A/R 的的自然映射自然

14、映射舉例：舉例：不同的等價關(guān)系確定不同的自然映射。不同的等價關(guān)系確定不同的自然映射。 恒等關(guān)系確定的自然映射是雙射恒等關(guān)系確定的自然映射是雙射, 其他自然映射一般來說其他自然映射一般來說只是滿射只是滿射. 例如例如 A = 1, 2, 3, R = , IA g: AA/R, g(1) = g(2) = 1, 2, g(3) = 3某些重要函數(shù)某些重要函數(shù)(續(xù)續(xù)2)廣東工業(yè)大學(xué)計算機學(xué)院168.2 函數(shù)的復(fù)合與反函數(shù)函數(shù)的復(fù)合與反函數(shù) 主要內(nèi)容主要內(nèi)容l 1. 復(fù)合函數(shù)基本定理復(fù)合函數(shù)基本定理l 2. 函數(shù)的復(fù)合運算與函數(shù)性質(zhì)函數(shù)的復(fù)合運算與函數(shù)性質(zhì)l 3. 反函數(shù)的存在條件反函數(shù)的存在條件l

15、 4. 反函數(shù)的性質(zhì)反函數(shù)的性質(zhì)廣東工業(yè)大學(xué)計算機學(xué)院171. 復(fù)合函數(shù)基本定理復(fù)合函數(shù)基本定理定理定理8.1 設(shè)設(shè)F, G是函數(shù)是函數(shù), 則則F G也是函數(shù)也是函數(shù), 且滿足且滿足(1) dom(F G) = x|xdomF F(x)domG(2) xdom(F G)有有F G(x) = G(F(x)【也寫作也寫作(F G)(x) 】證明：證明：先證明先證明F G是函數(shù)是函數(shù). 因為因為F, G是關(guān)系是關(guān)系, 所以所以F G也是關(guān)系也是關(guān)系. 若對某個若對某個xdom(F G)有有xF Gy1和和 xF Gy2, 則則 F GF G t1(FG) t2(FG) t1 t2(t1 = t2GG

16、) （F為函數(shù)）為函數(shù)） y1 = y2 （G為函數(shù)）為函數(shù)）所以所以 F G 為函數(shù)為函數(shù)廣東工業(yè)大學(xué)計算機學(xué)院18函數(shù)的復(fù)合定理證明函數(shù)的復(fù)合定理證明定理定理8.1 設(shè)設(shè)F, G是函數(shù)是函數(shù), 則則F G也是函數(shù)也是函數(shù), 且滿足且滿足(1) dom(F G) = x|xdomF F(x)domG(2) xdom(F G)有有F G(x) = G(F(x)證明：證明：(1) 任取任取x, xdom(F G) t y(FG) t (xdomFt=F(x)tdomG) x x | xdomFF(x)domG (2) 任取任取x, xdomFF(x)domG FG F G xdom(F G)F

17、G(x)G(F(x)廣東工業(yè)大學(xué)計算機學(xué)院19函數(shù)的復(fù)合定理推論函數(shù)的復(fù)合定理推論推論推論1 設(shè)設(shè)F, G, H為函數(shù)為函數(shù), 則則(F G) H和和F (G H)都是函數(shù)都是函數(shù), 且且 (F G) H=F (G H)證證 由上述定理和運算滿足結(jié)合律得證由上述定理和運算滿足結(jié)合律得證.推論推論2 設(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,

18、 且且 xA有有 f g(x) = g(f(x)廣東工業(yè)大學(xué)計算機學(xué)院20函數(shù)復(fù)合與函數(shù)性質(zhì)函數(shù)復(fù)合與函數(shù)性質(zhì)定理定理8.2 設(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也是也是雙射雙射的的 證明：證明：(1) 任取任取cC, 由由g: BC的滿射性，的滿射性， bB使得使得 g(b) = c.對于對于b, 由由 f: AB

19、的滿射性，的滿射性， aA使得使得 f(a) = b.由合成定理有由合成定理有 f g(a) = g(f(a) = g(b) = c從而證明了從而證明了f g: AC是滿射的是滿射的廣東工業(yè)大學(xué)計算機學(xué)院21函數(shù)復(fù)合與函數(shù)性質(zhì)函數(shù)復(fù)合與函數(shù)性質(zhì)證明證明定理定理8.2 設(shè)設(shè)f: AB, g: BC (2) 如果如果 f: AB, g: BC是是單射單射的的, 則則 f g: AC也是也是單射單射的的 證明：證明：假設(shè)存在假設(shè)存在x1, x2A使得：使得：f g(x1)=f g(x2)由合成定理有由合成定理有 g(f(x1) = g(f(x2)因為因為g: BC是單射的是單射的, 故故 f(x1)

20、=f(x2). 又由于又由于f: AB是單射的是單射的, 所以所以x1=x2. 從而證明從而證明f g: AC是單射的是單射的.注意：注意：定理逆命題不為真定理逆命題不為真, 即如果即如果f g: AC是單射是單射(或滿射、或滿射、雙射雙射)的的, 不一定有不一定有 f: AB 和和g: BC都是單射都是單射(或滿射、雙或滿射、雙射射)的的.定理定理8.3 設(shè)設(shè) f: AB, 則則 f = f IB = IA f （證明略）（證明略）廣東工業(yè)大學(xué)計算機學(xué)院22實例實例考慮集合考慮集合A=a1, a2, a3, B=b1, b2, b3, b4, C=c1, c2, c3. 令令 f=, g=,

21、 f g=,那么那么 f: AB和和f g: AC是單射的是單射的, 但但g: BC不是單射的不是單射的. 考慮集合考慮集合A=a1, a2, a3, B=b1, b2, b3, C=c1, c2. 令令f=,g=,f g=,那么那么g: BC 和和 f g: AC是滿射的是滿射的, 但但 f: AB不是滿射的不是滿射的.廣東工業(yè)大學(xué)計算機學(xué)院232. 反函數(shù)反函數(shù)反函數(shù)存在的條件：反函數(shù)存在的條件：(1) 任給函數(shù)任給函數(shù)F, 它的逆它的逆F 1不一定是函數(shù)不一定是函數(shù), 只是一個二元關(guān)系只是一個二元關(guān)系.(2) 任給單射函數(shù)任給單射函數(shù) f: AB, 則則f 1是函數(shù)是函數(shù), 且是從且是從

22、ranf 到到A的雙的雙 射函數(shù)射函數(shù), 但不一定是從但不一定是從B到到A的雙射函數(shù)的雙射函數(shù)(3) 對于雙射函數(shù)對于雙射函數(shù) f: AB, f 1: BA是從是從B到到A的雙射函數(shù)的雙射函數(shù). 注意注意: 僅當(dāng)僅當(dāng)f是雙射函數(shù)，才可定義是雙射函數(shù)，才可定義f逆函數(shù)，逆函數(shù)，且且f 1就是就是f的逆的逆關(guān)系。關(guān)系。廣東工業(yè)大學(xué)計算機學(xué)院24證明證明定理定理8.4 設(shè)設(shè) f: AB是雙射的是雙射的, 則則f 1: BA也是雙射的也是雙射的.證明思路：證明思路：(1) 先證明先證明 f 1: BA，即，即f 1是函數(shù)，且是函數(shù)，且domf 1=B, ranf 1=A. (2) 再證明再證明f 1:

23、 BA具有雙射性質(zhì)具有雙射性質(zhì).證明：證明：因為因為 f 是函數(shù)是函數(shù), 所以所以 f 1是關(guān)系是關(guān)系, 且且 dom f 1 = ranf = B , ran f 1 = domf = A對于任意的對于任意的 xB = dom f 1, 假設(shè)有假設(shè)有y1, y2A使得使得 f 1f 1成立成立, 則由逆的定義有則由逆的定義有 ff根據(jù)根據(jù) f 的單射性可得的單射性可得y1=y2, 從而證明了從而證明了f 1是函數(shù)。是函數(shù)。由由x的任意性可知，的任意性可知， f 1是滿射的是滿射的.廣東工業(yè)大學(xué)計算機學(xué)院25證明證明(續(xù)續(xù))定理定理8.4 設(shè)設(shè) f: AB是雙射的是雙射的, 則則f 1: BA

24、也是雙射的也是雙射的.證明思路：證明思路：先證明先證明 f 1: BA，即，即f 1是函數(shù)，且是函數(shù)，且domf 1=B, ranf 1=A. 再證明再證明f 1: BA的雙射性質(zhì)的雙射性質(zhì).證明證明(續(xù)續(xù))：再證明再證明f 1的單射性。的單射性。若存在若存在x1, x2B使得使得f 1 (x1)= f 1 (x2)=y, 從而有從而有 f 1f 1 ff x1=x2 對于雙射函數(shù)對于雙射函數(shù)f:AB, 稱稱 f 1:BA是它的是它的反函數(shù)反函數(shù). 所以所以f 1是雙射的是雙射的廣東工業(yè)大學(xué)計算機學(xué)院26反函數(shù)的性質(zhì)反函數(shù)的性質(zhì)定理定理8.5 (1) 設(shè)設(shè) f: AB是雙射的是雙射的, 則則

25、f 1 f = IB, f f 1 = IA(2) 對于雙射函數(shù)對于雙射函數(shù) f: AA, 有有 f 1 f = f f 1 = IA 證明思路：證明思路：根據(jù)定理可知根據(jù)定理可知 f 1: BA也是雙射的也是雙射的, 由合成基本定理可知由合成基本定理可知 f 1 f: BB, f f 1: AA，且它們都是恒等函數(shù)，且它們都是恒等函數(shù). 廣東工業(yè)大學(xué)計算機學(xué)院27解解 121)2()(RR:3032)(RR:22xxxxfgfgxxxxgfgff: RR不是雙射的不是雙射的, 不存在反函不存在反函數(shù)數(shù). g: RR是雙射的是雙射的, 它的反函數(shù)是它的反函數(shù)是g 1: RR, g 1(x)=x

26、 2求解求解例例5 設(shè)設(shè) 求求 f g, g f. 如果如果f 和和 g 存在反函數(shù)存在反函數(shù), 求出它們的反函數(shù)求出它們的反函數(shù).2)(323)(RR:,RR:2 xxgxxxxfgf廣東工業(yè)大學(xué)計算機學(xué)院283. 鴿巢原理鴿巢原理(pigeonhole principle)鴿巢原理鴿巢原理(pigeonhole principle): 又名又名鴿洞原理鴿洞原理。若把。若把n+1只只鴿子裝進(jìn)鴿子裝進(jìn)n只鴿巢只鴿巢, 則至少有一只鴿巢裝則至少有一只鴿巢裝2只以上的鴿子只以上的鴿子.又名又名抽屜原則抽屜原則(Dirichlet drawer principle), (Peter Gustav L

27、ejeune Dirichlet,18051859)例：例：一個輪盤賭轉(zhuǎn)盤的圓周分為一個輪盤賭轉(zhuǎn)盤的圓周分為36段，將段，將1，2，36，任意標(biāo)在每一段上，證明一定存在連續(xù)的三段，它們的數(shù)字任意標(biāo)在每一段上，證明一定存在連續(xù)的三段，它們的數(shù)字之和至少是之和至少是56。解：解：1+2+36 = 666 36段可以分作段可以分作12個組連續(xù)的個組連續(xù)的3段，每組平均數(shù)字之和：段，每組平均數(shù)字之和： 666/12 = 55.5， 55.5 = 56 必存在連續(xù)的三段，它們的數(shù)字之和至少是必存在連續(xù)的三段，它們的數(shù)字之和至少是56廣東工業(yè)大學(xué)計算機學(xué)院298.3 雙射函數(shù)與集合的基數(shù)雙射函數(shù)與集合的基

28、數(shù)主要內(nèi)容主要內(nèi)容l 集合的等勢及其性質(zhì)集合的等勢及其性質(zhì)l 重要的等勢或不等勢的結(jié)果重要的等勢或不等勢的結(jié)果l 集合的優(yōu)勢及其性質(zhì)集合的優(yōu)勢及其性質(zhì)l 集合的基數(shù)集合的基數(shù)l 可數(shù)集可數(shù)集廣東工業(yè)大學(xué)計算機學(xué)院30 01202)(,NZ:xxxxxff則則 f 是是Z到到N的雙射函數(shù)的雙射函數(shù). 從而證明了從而證明了ZN.集合的等勢集合的等勢集合等勢的實例集合等勢的實例例例6 (1) ZN. 定義定義8.8 設(shè)設(shè)A, B是集合是集合, 如果存在著從如果存在著從A到到B的雙射函數(shù)的雙射函數(shù), 就稱就稱A和和B是是等勢等勢的的, 記作記作AB. 如果如果A不與不與B 等勢等勢, 則記作則記作A

29、B.廣東工業(yè)大學(xué)計算機學(xué)院31mnmnmnmff 2)(1(),(,NNN:集合等勢的實例集合等勢的實例: NNNNNN. NN中所有的元素排成有序圖形中所有的元素排成有序圖形廣東工業(yè)大學(xué)計算機學(xué)院32-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/

30、41515-3/4-3/416162/42/43/43/413130/40/41/41/41414PLAYNQ. 雙射函數(shù)雙射函數(shù) f:NQ, 其中其中f(n)是是n下方的有理數(shù)下方的有理數(shù). 集合等勢的實例集合等勢的實例: NQ廣東工業(yè)大學(xué)計算機學(xué)院33212tan)(,R)1 , 0(: xxff xxnxxxxfnn其它其它,.2 , 1,2/12/112/102/1)(12(6) 對任何對任何a, bR, ab, 0,1a,b，雙射函數(shù)雙射函數(shù) f:0,1a,b, f(x)=(b a)x+a類似地可以證明類似地可以證明, 對任何對任何a, bR, ab, 有有(0,1)(a,b).(4

31、) (0,1)R. 其中實數(shù)區(qū)間其中實數(shù)區(qū)間 (0,1)=x| xR0 x1. 令令(5) 0,1(0,1). 其中其中(0,1)和和0,1分別為實數(shù)開區(qū)間和閉區(qū)間分別為實數(shù)開區(qū)間和閉區(qū)間. 令令 f : 0,1(0,1)實數(shù)集合的等勢實數(shù)集合的等勢廣東工業(yè)大學(xué)計算機學(xué)院34實例實例例例7 設(shè)設(shè)A為任意集合為任意集合, 則則P(A)0,1A.證證 如下構(gòu)造從如下構(gòu)造從P(A) 到到 0,1A 的函數(shù)的函數(shù) f:P(A)0,1A, f(A)= A, AP(A).其中其中 A是集合是集合A的特征函數(shù)的特征函數(shù). 易證易證 f 是單射的是單射的. 對于任意的對于任意的 g0,1A, 那么有那么有 g

32、:A0,1. 令令 B= x| xAg(x)=1則則B A, 且且 B=g, 即即 BP(A), f(B)=g. 從而證明了從而證明了f 是滿射是滿射的的. 由等勢定義得由等勢定義得 P(A)0,1A.廣東工業(yè)大學(xué)計算機學(xué)院35等勢的性質(zhì)等勢的性質(zhì)定理定理8.6 設(shè)設(shè)A, B,C是任意集合，是任意集合，(1) AA(2) 若若AB，則，則BA(3) 若若AB，BC，則，則AC.證明思路：利用等勢的等義證明思路：利用等勢的等義. (1) IA是從是從A到到A的雙射的雙射(2) 若若 f:AB是雙射，則是雙射，則f 1:BA是從是從B到到A的雙射的雙射.(3) 若若 f:AB，g:BC是雙射，則是

33、雙射，則f g:AC是從是從A到到C的雙射的雙射 廣東工業(yè)大學(xué)計算機學(xué)院36有關(guān)勢的重要結(jié)果有關(guān)勢的重要結(jié)果等勢結(jié)果等勢結(jié)果l N Z Q NNl 任何實數(shù)區(qū)間都與實數(shù)集合任何實數(shù)區(qū)間都與實數(shù)集合R等勢等勢不等勢的結(jié)果不等勢的結(jié)果: 定理定理8.7 (康托定理康托定理)(1) N R； (2) 對任意集合對任意集合A都有都有A P(A)證明思路：證明思路：(1) 只需證明任何函數(shù)只需證明任何函數(shù) f:N0,1都不是滿射的都不是滿射的. 任取函數(shù)任取函數(shù) f:N0,1, 列出列出 f 的所有函數(shù)值，然后構(gòu)造一個的所有函數(shù)值，然后構(gòu)造一個0,1區(qū)間的小數(shù)區(qū)間的小數(shù)b，使得，使得b與所有的函數(shù)值都不

34、相等與所有的函數(shù)值都不相等. (2) 任取函數(shù)任取函數(shù) f:AP(A)，構(gòu)造，構(gòu)造B P(A)，使得，使得B與與 f 的任何函的任何函 數(shù)值都不等數(shù)值都不等. 廣東工業(yè)大學(xué)計算機學(xué)院37Cantor定理的證明定理的證明證證 (1) 規(guī)定規(guī)定0,1中數(shù)的表示中數(shù)的表示. 對任意的對任意的x0,1, 令令 x = 0. x1 x2 , 0 xi 9規(guī)定在規(guī)定在 x 的表示式中不允許在某位后有無數(shù)個的表示式中不允許在某位后有無數(shù)個1的情況的情況. 設(shè)設(shè) f: N0,1是任何函數(shù)，列出是任何函數(shù)，列出 f 的所有函數(shù)值：的所有函數(shù)值： f(0) = 0.a1(1)a2(1) f(1) = 0.a1(2

35、)a2(2) f(n 1) = 0.a1(n)a2(n) 令令 y 的表示式為的表示式為0.b1b2, 并且滿足并且滿足bi ai(i), i=1,2, 那么那么y 0,1, 且且y與上面列出的任何函數(shù)值都不相等與上面列出的任何函數(shù)值都不相等. 這就推出這就推出y ranf, 即即 f 不是滿射的不是滿射的.廣東工業(yè)大學(xué)計算機學(xué)院38(2) 我們將證明任何函數(shù)我們將證明任何函數(shù) g:AP(A)都不是滿射的都不是滿射的. 設(shè)設(shè) g:AP(A)是從是從A到到P(A)的函數(shù)的函數(shù), 如下構(gòu)造集合如下構(gòu)造集合B： B=x| xAx g(x)則則BP(A), 但對任意但對任意xA都有都有 xB x g(

36、x)從而證明了對任意的從而證明了對任意的 xA都有都有 Bg(x). 即即B rang. 注意：根據(jù)注意：根據(jù)Cantor定理可以知道定理可以知道N P(N)，N 0,1N.Cantor定理的證明定理的證明廣東工業(yè)大學(xué)計算機學(xué)院39集合的優(yōu)勢集合的優(yōu)勢定義定義8.9 (1) 設(shè)設(shè)A, B是集合是集合, 如果存在從如果存在從A到到B的單射函數(shù)的單射函數(shù), 就就稱稱B優(yōu)勢于優(yōu)勢于A, 記作記作A B. 如果如果B不是優(yōu)勢于不是優(yōu)勢于A, 則記作則記作A B.(2) 設(shè)設(shè)A, B是集合是集合, 若若A B 且且 A B, 則稱則稱 B 真優(yōu)勢于真優(yōu)勢于A, 記作記作 A B. 如果如果 B 不是真優(yōu)

37、勢于不是真優(yōu)勢于A, 則記作則記作A B. 實例實例 N N, N R, A P(A), R N N R, A P(A), 但但N N定理定理8.8 設(shè)設(shè) A, B, C是任意的集合是任意的集合, 則則(1) A A(2) 若若A B且且B A, 則則AB(3) 若若A B且且B C, 則則A C 廣東工業(yè)大學(xué)計算機學(xué)院40應(yīng)用：證明等勢應(yīng)用：證明等勢證證 設(shè)設(shè)x 0,1), 0. x1x2 是是 x 的二進(jìn)制表示的二進(jìn)制表示. 規(guī)定表示式中不規(guī)定表示式中不允許出現(xiàn)連續(xù)無數(shù)個允許出現(xiàn)連續(xù)無數(shù)個1. 對于對于x，如下定義，如下定義 f:0,1)0,1N, f(x) = tx, 且且 tx:N0,

38、1, tx(n) = xn+1, n = 0,1,2,例如例如 x = 0.1 0 1 1 0 1 0 0, 則對應(yīng)于則對應(yīng)于x 的函數(shù)的函數(shù) tx是：是： n 0 1 2 3 4 5 6 7 tx(n) 1 0 1 1 0 1 0 0 tx0,1N, 且對于且對于x,y0,1), xy, 必有必有txty, 即即 f(x)f(y). 這就證明了這就證明了f:0,1)0,1N是單射的是單射的.例例8 證明證明 0,1N0,1).廣東工業(yè)大學(xué)計算機學(xué)院41考慮考慮 t0,1N, 其中其中 t(0)=0, t(n)=1, n=1, 2, . 按照按照 f 的定義的定義, 只有只有 x = 0.01

39、1 才能滿足才能滿足 f(x)=t. 但根據(jù)規(guī)定但根據(jù)規(guī)定, 這個數(shù)這個數(shù) x 記為記為0.100, 所以根本不存在所以根本不存在 x0,1), 滿足滿足 f(x)=t.定義函數(shù)定義函數(shù) g:0,1N0,1). g的映射法則恰好與的映射法則恰好與 f 相反相反. 即即 t0,1N, t：N0,1, g(t)=0. x1x2, 其中其中xn+1=t(n). 將將0. x1x2 看作數(shù)看作數(shù) x 的十進(jìn)制表示的十進(jìn)制表示. 這樣就避免了形如這樣就避免了形如 0.0111和和0.1000.在二進(jìn)制表示中對應(yīng)了同一個數(shù)的情在二進(jìn)制表示中對應(yīng)了同一個數(shù)的情況，從而保證了況，從而保證了g的單射性的單射性.

40、根據(jù)定理有根據(jù)定理有0,1N0,1). 再使用等勢的傳遞性得再使用等勢的傳遞性得0,1NR.構(gòu)造另一個單射構(gòu)造另一個單射廣東工業(yè)大學(xué)計算機學(xué)院42自然數(shù)的集合定義自然數(shù)的集合定義 定義定義8.10 設(shè)設(shè)a為集合為集合, 稱稱aa為為a的的后繼后繼, 記作記作a+, 即即 a+=aa.如下定義自然數(shù)：如下定義自然數(shù)： 0= 1=0+=+ = =0 2=1+= + = =,=0,1 3=2+=,+= ,= 0,1,2 n=0, 1, , n 1 自然數(shù)的相等與大小，即對任何自然數(shù)自然數(shù)的相等與大小，即對任何自然數(shù) n和和m，有有 m=n m n ， mn m n廣東工業(yè)大學(xué)計算機學(xué)院43有窮集和無

41、窮集有窮集和無窮集定義定義8.11 (1) 一個集合是一個集合是有窮有窮的當(dāng)且僅當(dāng)它與某個自然數(shù)等勢；的當(dāng)且僅當(dāng)它與某個自然數(shù)等勢；(2) 如果一個集合不是有窮的如果一個集合不是有窮的, 就稱作就稱作無窮集無窮集.實例：實例：(1) a,b,c是有窮集是有窮集, 因為因為3=0,1,2, 且且 a,b,c0,1,2=3(2) N和和R都是無窮集都是無窮集, 因為沒有自然數(shù)與因為沒有自然數(shù)與N和和R等勢等勢利用自然數(shù)的性質(zhì)可以證明：任何有窮集只與惟一的自然數(shù)利用自然數(shù)的性質(zhì)可以證明：任何有窮集只與惟一的自然數(shù)等勢等勢. 廣東工業(yè)大學(xué)計算機學(xué)院44集合基數(shù)的定義集合基數(shù)的定義定義定義8.12(1)

42、 對于有窮集合對于有窮集合A, 稱與稱與A等勢的那個惟一的自然數(shù)為等勢的那個惟一的自然數(shù)為A的的基基數(shù)數(shù), 記作記作cardA (也可以記作也可以記作|A|) cardA = n A n (2) 自然數(shù)集合自然數(shù)集合N的基數(shù)記作的基數(shù)記作0, 即即 cardN =0(3) 實數(shù)集實數(shù)集R的基數(shù)記作的基數(shù)記作, 即即 cardR =廣東工業(yè)大學(xué)計算機學(xué)院45基數(shù)的相等和大小基數(shù)的相等和大小定義定義8.13 設(shè)設(shè)A, B為集合為集合, 則則(1) cardA=cardB AB(2) cardAcardB A B(3) cardAcardB cardAcardBcardAcardB根據(jù)上一節(jié)關(guān)于勢的

43、討論不難得到：根據(jù)上一節(jié)關(guān)于勢的討論不難得到： card Z = card Q = card NN =0 card P(N) = card 2N = card a,b = card (c,d) = 0 card Acard P(A)其中其中2N = 0,1N廣東工業(yè)大學(xué)計算機學(xué)院46基數(shù)的大小基數(shù)的大小不存在最大的基數(shù)不存在最大的基數(shù). 將已知的基數(shù)按從小到大的順序排列就將已知的基數(shù)按從小到大的順序排列就得到：得到： 0, 1, 2, , n, , 0, , 其中：其中： 0, 1, 2, n, 是全體自然數(shù)是全體自然數(shù), 是有窮基數(shù)是有窮基數(shù). 0, , 是無窮基數(shù)是無窮基數(shù), 0是最小的無

44、窮基數(shù)是最小的無窮基數(shù), 后面還后面還有更大的基數(shù)有更大的基數(shù), 如如cardP(R)等等. 廣東工業(yè)大學(xué)計算機學(xué)院47可數(shù)集可數(shù)集定義定義8.14 設(shè)設(shè)A為集合為集合, 若若cardA0, 則稱則稱A為為可數(shù)集可數(shù)集或或可列集可列集.實例：實例：a,b,c, 5, 整數(shù)集整數(shù)集Z, 有理數(shù)集有理數(shù)集Q, NN等都是可數(shù)集等都是可數(shù)集, 實數(shù)集實數(shù)集 R不是可數(shù)集不是可數(shù)集, 與與R等勢的集合也不是可數(shù)集等勢的集合也不是可數(shù)集. 對于任何的可數(shù)集對于任何的可數(shù)集, 它的元素都可以排列成一個有序圖形它的元素都可以排列成一個有序圖形. 換換句話說句話說, 都可以找到一個都可以找到一個“數(shù)遍數(shù)遍”集

45、合中全體元素的順序集合中全體元素的順序. 可數(shù)集的性質(zhì)：可數(shù)集的性質(zhì)：l 可數(shù)集的任何子集都是可數(shù)集可數(shù)集的任何子集都是可數(shù)集.l 兩個可數(shù)集的并是可數(shù)集兩個可數(shù)集的并是可數(shù)集.l 兩個可數(shù)集的笛卡兒積是可數(shù)集兩個可數(shù)集的笛卡兒積是可數(shù)集.l 可數(shù)個可數(shù)集的笛卡兒積仍是可數(shù)集可數(shù)個可數(shù)集的笛卡兒積仍是可數(shù)集.l 無窮集無窮集A的冪集的冪集P(A)不是可數(shù)集不是可數(shù)集廣東工業(yè)大學(xué)計算機學(xué)院48實例實例解解 (1) 由由T=B, A, S, E, L知知 cardT=5(2) 由由B=, 可知可知 cardB=0.(3) 由由|A|=4 可知可知 cardC=cardP(A)=|P(A)|=24=

46、16.例例9 求下列集合的基數(shù)求下列集合的基數(shù)(1) T=x | x是單詞是單詞“BASEBALL”中的字母中的字母(2) B=x | xRx2=92x=8(3) C=P(A), A=1, 3, 7, 11廣東工業(yè)大學(xué)計算機學(xué)院49例例10 設(shè)設(shè)A, B為集合為集合, 且且 cardA=0, cardB=n, n是自然數(shù)是自然數(shù), n0. 求求card AB.實例實例解解 方法一方法一 構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù)由由cardA=0, cardB=n, 可知可知 A, B都是可數(shù)集都是可數(shù)集. 令令 A=a0,a1,a2, B=b0,b1,b2,bn 1 對任意的對任意的, AB有有 = i=kj

47、=l 定義函數(shù)定義函數(shù) f :ABN f()=in+j, i=0,1, j=0,1,n 1易見易見f是是AB到到N的雙射函數(shù)的雙射函數(shù), 所以所以 card AB=card N = 0廣東工業(yè)大學(xué)計算機學(xué)院50方法二方法二 直接使用可數(shù)集的性質(zhì)求解直接使用可數(shù)集的性質(zhì)求解. 因為因為 card A=0, card B=n, 所以所以A, B都是可數(shù)集都是可數(shù)集.根據(jù)性質(zhì)根據(jù)性質(zhì)(3) 可知可知 AB也是可數(shù)集也是可數(shù)集, 所以所以 card AB0 顯然當(dāng)顯然當(dāng) B時時, card A card AB, 這就推出這就推出 0 card AB綜合上述得到綜合上述得到 card AB=0. 實例實

48、例廣東工業(yè)大學(xué)計算機學(xué)院51第八章第八章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 函數(shù)，函數(shù)，從從A到到B的函數(shù)的函數(shù) f:AB，BA，函數(shù)的像與完全原像，函數(shù)的像與完全原像l 函數(shù)的性質(zhì)：單射、滿射、雙射函數(shù)函數(shù)的性質(zhì)：單射、滿射、雙射函數(shù)l 重要函數(shù)：恒等函數(shù)、常函數(shù)、單調(diào)函數(shù)、集合的特征函重要函數(shù)：恒等函數(shù)、常函數(shù)、單調(diào)函數(shù)、集合的特征函 數(shù)、自然映射數(shù)、自然映射l 集合等勢的定義與性質(zhì)集合等勢的定義與性質(zhì)l 集合優(yōu)勢的定義與性質(zhì)集合優(yōu)勢的定義與性質(zhì)l 重要的集合等勢以及優(yōu)勢的結(jié)果重要的集合等勢以及優(yōu)勢的結(jié)果l 可數(shù)集與不可數(shù)集可數(shù)集與不可數(shù)集l 集合基數(shù)的定義集合基數(shù)的定義廣東工業(yè)大學(xué)計算機學(xué)

49、院52基本要求基本要求l 給定給定 f, A, B, 判別判別 f 是否為從是否為從A到到B的函數(shù)的函數(shù)l 判別函數(shù)判別函數(shù) f:AB的性質(zhì)（單射、滿射、雙射）的性質(zhì)（單射、滿射、雙射）l 熟練計算函數(shù)的值、像、復(fù)合以及反函數(shù)熟練計算函數(shù)的值、像、復(fù)合以及反函數(shù)l 證明函數(shù)證明函數(shù) f:AB的性質(zhì)（單射、滿射、雙射）的性質(zhì)（單射、滿射、雙射）l 給定集合給定集合A, B，構(gòu)造雙射函數(shù)，構(gòu)造雙射函數(shù) f:AB l 能夠證明兩個集合等勢能夠證明兩個集合等勢l 能夠證明一個集合優(yōu)勢于另一個集合能夠證明一個集合優(yōu)勢于另一個集合l 知道什么是可數(shù)集與不可數(shù)集知道什么是可數(shù)集與不可數(shù)集l 會求一個簡單集合

50、的基數(shù)會求一個簡單集合的基數(shù)廣東工業(yè)大學(xué)計算機學(xué)院53練習(xí)練習(xí)11給定給定A, B 和和 f, 判斷是否構(gòu)成函數(shù)判斷是否構(gòu)成函數(shù) f:AB. 如果是如果是, 說明該說明該 函數(shù)是否為單射、滿射、雙射的函數(shù)是否為單射、滿射、雙射的. 并根據(jù)要求進(jìn)行計算并根據(jù)要求進(jìn)行計算.(1) A=1,2,3,4,5, B=6,7,8,9,10, f=,.(2) A,B同同(1), f=,.(3) A,B同同(1), f=,.(4) A=B=R, f(x)=x3(5) A=B=R+, f(x)=x/(x2+1).(6) A=B=RR, f()=, 令令 L=|x,yRy=x+1, 計算計算 f(L).(7) A

51、=NN, B=N, f()=|x2 y2|. 計算計算f(N0), f 1(0)廣東工業(yè)大學(xué)計算機學(xué)院54解解答解答(1) 能構(gòu)成能構(gòu)成 f:AB, f:AB既不是單射也不是滿射既不是單射也不是滿射, 因為因為 f(3)=f(5)=9, 且且7 ranf.(2) 不構(gòu)成不構(gòu)成 f:AB, 因為因為 f 不是函數(shù)不是函數(shù). f 且且f, 與函與函 數(shù)定義矛盾數(shù)定義矛盾(3) 不構(gòu)成不構(gòu)成 f:AB, 因為因為dom f = 1,2,3,4 A(4) 能構(gòu)成能構(gòu)成 f:AB, 且且 f:AB是雙射的是雙射的(5) 能構(gòu)成能構(gòu)成 f:AB, f:AB既不是單射的也不是滿射的既不是單射的也不是滿射的.

52、 因為該因為該 函數(shù)在函數(shù)在 x=1取極大值取極大值 f(1)=1/2. 函數(shù)不是單調(diào)的函數(shù)不是單調(diào)的,且且ranfR+.(6) 能構(gòu)成能構(gòu)成 f:AB, 且且 f:AB是雙射的是雙射的. f(L) = |xR=R 1(7) 能構(gòu)成能構(gòu)成 f:AB, f:AB既不是單射的也不是滿射的既不是單射的也不是滿射的. 因為因為 f()=f()=0, 2 ranf. f(N0) = n2 02|nN = n2|nN f 1(0) = |nN廣東工業(yè)大學(xué)計算機學(xué)院551)(, 1, 1)(,)(,0, 10, 1)(4321 xfZxZxxfxxfxxxf練習(xí)練習(xí)22. 設(shè)設(shè) f1, f2, f3, f4

53、 RR，且，且令令Ei 是由是由 fi 導(dǎo)出的等價關(guān)系，導(dǎo)出的等價關(guān)系，i=1,2,3,4，即，即 xEiy fi(x)=fi(y) (1) 畫出偏序集畫出偏序集的哈斯圖，其中的哈斯圖，其中T 是加細(xì)關(guān)系：是加細(xì)關(guān)系： T x(x R/Eiy(y R/Ej x y) (2) gi:RR/Ei 是自然映射，求是自然映射，求gi(0), i=1,2,3,4.(3) 對每個對每個i, 說明說明 gi 的性質(zhì)（單射、滿射、雙射）的性質(zhì)（單射、滿射、雙射）.廣東工業(yè)大學(xué)計算機學(xué)院56(1) 哈斯圖如下哈斯圖如下(2) g1(0) = x | x R x 0, g2(0)=0, g3(0)=Z, g4(0

54、)=R(3) g1, g3, g4是滿射的；是滿射的；g2是雙射的是雙射的. 解圖1解答解答廣東工業(yè)大學(xué)計算機學(xué)院57練習(xí)練習(xí)33對于以下集合對于以下集合A和和B，構(gòu)造從，構(gòu)造從A到到B的雙射函數(shù)的雙射函數(shù) f:AB(1) A=1,2,3，B=a, b, c(2) A=(0,1)，B=(0,2)(3) A=x| x Zx0，B=N (4) A=R，B=R+ 解解 (1) f=, , (2) f:AB, f(x)=2x(3) f:AB, f(x)= x 1(4) f:AB, f(x)=ex 廣東工業(yè)大學(xué)計算機學(xué)院584.4.設(shè)設(shè) 證明證明 f 既是滿射的，也是單射的既是滿射的，也是單射的. yxyxyxff,),(,RRRR: 2,2vuvuvuvuvuf,)2,2( vuyxvyuxvuyxvuyxvuvuyxyxvufyxf,),(),(證證 任取任取 R R，存在，存在使得使得 練習(xí)練習(xí)4因此因此 f 是是滿射的滿射的對于任意的對于任意的 , R R, 有有因此因此