1、 第三章 集合與關(guān)系 第一節(jié) 集合的根本概念一、集合的定義直觀了解：由離散個(gè)體構(gòu)成的整體稱為集合，稱這些個(gè)體為集合的元素。二、集合的表示法1. 枚舉法-經(jīng)過列出全體元素來表示集合.2. 描畫法-經(jīng)過描畫集合元素的性質(zhì)確定集合.例： 枚舉法 自然數(shù)集合N=0,1,2,3,。 描畫法 S=x| x是實(shí)數(shù)，x21=0。 三、集合間的關(guān)系三、集合間的關(guān)系 A B x (xAxB) A = B A B B A A B A B A B A B x (xAxB)四、空集和選集四、空集和選集 1. 空集空集 ：不含有任何元素的集合：不含有任何元素的集合 實(shí)例：實(shí)例： x|xRx2+1=0空集空集是任何集合的子

2、集是任何集合的子集是獨(dú)一的是獨(dú)一的.2選集選集U：一個(gè)問題中包含了問題中一切集合的：一個(gè)問題中包含了問題中一切集合的集合集合. 五、冪集五、冪集 1定義：定義：P(A)=x | xA (也記作也記作2A) 2計(jì)數(shù)：假設(shè)計(jì)數(shù)：假設(shè)|A|=n，那么，那么|P(A)|=2n. 例：例： P()=, P()=,. 假設(shè)假設(shè)A=1,2,3,那么那么 P(A)=,1,2,3,1,2,1,3,2,3,1,2,3 .第二節(jié)第二節(jié) 集合的運(yùn)算與性質(zhì)集合的運(yùn)算與性質(zhì)1定義定義 并并 AB = x | xA xB 交交 AB = x | xA xB 差差 AB = x | xA xB對(duì)稱差對(duì)稱差 AB = (AB)

3、(BA) 補(bǔ)補(bǔ) A = UA ABABABABAUABABABABA3. 集合運(yùn)算的根本性質(zhì)集合運(yùn)算的根本性質(zhì)冪等律冪等律AA=A， AA=A結(jié)合律結(jié)合律ABC= A(BC)= (AB)C ABC= A (B C)= (AB)C交換律交換律AB=BA, AB=BA分配律分配律A(BC)=(AB)(AC) A(BC)=(AB)(AC)同一同一/零律零律 A=A, A = 排中排中/矛盾律矛盾律AA=U, A A= 吸收律吸收律 A(BA)=A, A(BA)=A德摩律德摩律 (AB)= A B , (A B)= A B雙重否認(rèn)雙重否認(rèn) A=A以上性質(zhì)可根據(jù)集合相等的定義證明以上性質(zhì)可根據(jù)集合相等的

4、定義證明四、有窮集合元素的計(jì)數(shù)四、有窮集合元素的計(jì)數(shù)1計(jì)數(shù)方法計(jì)數(shù)方法1文氏圖法文氏圖法2公式法公式法容斥原理容斥原理i) ii) |.|) 1(.|.|21111121nnnkjikjnjijiniinAAAAAAAAAAAAi |.|) 1(.|.|2111121nnnkjikjnjijiniinAAAAAAAAASAAAi 2計(jì)數(shù)實(shí)例計(jì)數(shù)實(shí)例 例例1 知校足球隊(duì)有知校足球隊(duì)有38人，籃球隊(duì)有人，籃球隊(duì)有15人，排球隊(duì)人，排球隊(duì)有有20人，三隊(duì)共人，三隊(duì)共58人。有人同時(shí)參與了幾個(gè)運(yùn)動(dòng)隊(duì)。人。有人同時(shí)參與了幾個(gè)運(yùn)動(dòng)隊(duì)。假設(shè)同時(shí)參與了假設(shè)同時(shí)參與了3個(gè)隊(duì)的人共個(gè)隊(duì)的人共3人，問同時(shí)至少參與人

5、，問同時(shí)至少參與了了2個(gè)隊(duì)的有多少人？個(gè)隊(duì)的有多少人？ 解：由于解：由于 | A 1A 2A 3 | =| A i | -|AiAj|+|AiAjAk|， 故有故有 58=(38+15+20)-|AiAj|+3， 所以所以 |AiAj|=18。 例例2 求求1,300整數(shù)中：整數(shù)中： 1.能被能被3或或5或或7整除的整數(shù)的個(gè)數(shù)；整除的整數(shù)的個(gè)數(shù)； 2.既不能被既不能被3和和5整除，也不能被整除，也不能被7整除的的個(gè)數(shù)。整除的的個(gè)數(shù)。 解解: (1) 記記 S = 1,2,300, A3 = x | xS且且x是是3的倍數(shù)的倍數(shù), A5 = x | xS且且x是是5的倍數(shù)的倍數(shù), A7 = x

6、| xS且且x是是7的倍數(shù)的倍數(shù)。 那么那么|S| = 300, |A3|= 300/3 =100, |A5|=300/5 =60, |A7|=300/7 = 42 . |A3A5 | = 300/lcm(3,5) = 300/15 = 20, |A3A7 | = 300/lcm(3,7) = 300/21 = 14, |A5A7 | = 300/lcm(5,7) = 300/35 = 8, |A3A5A7 | = 300/lcm(3,5,7) = 300/105 = 2, 故故 |A3A5A7 | = (100+60+42)-(20+14+8)+2 = 162 . (2) |S|- |A3A

7、5A7 | = 300-162=148。 |753AAA方法二方法二 圖圖32A3A7A561218346822第四節(jié)第四節(jié) 序偶與笛卡兒積序偶與笛卡兒積 1定義定義 兩個(gè)元素兩個(gè)元素x和和y按順序陳列的二元組按順序陳列的二元組稱為一個(gè)序偶，記作稱為一個(gè)序偶，記作.2序偶的性質(zhì)序偶的性質(zhì)1有序性有序性 當(dāng)當(dāng)xy時(shí)時(shí) 2與與相等的充要條件相等的充要條件= x=uy=v. 類似地，按順序陳列的類似地，按順序陳列的n個(gè)元素個(gè)元素稱為一個(gè)稱為一個(gè)n元組元組.第五節(jié)第五節(jié) 笛卡兒積笛卡兒積 定義定義 集合集合A A與集合與集合B B的笛卡兒積定義為的笛卡兒積定義為 A AB = | xB = | xA

8、Ay yB.B.例例 假設(shè)假設(shè)A=1,2,3, B=a,b,cA=1,2,3, B=a,b,c，那么，那么 A AB = B = , , , , , B BA = A = , , , 假設(shè)假設(shè)A=A=, B=, B=，那么，那么 P(A) P(A)A = A = , , P(A) P(A)B = B = 第六節(jié)第六節(jié) 二元關(guān)系二元關(guān)系 1. 1. 定義定義 元素均為序偶的一個(gè)集合稱為一個(gè)二元元素均為序偶的一個(gè)集合稱為一個(gè)二元關(guān)系關(guān)系, , 簡稱為關(guān)系，記作簡稱為關(guān)系，記作R.R. 假設(shè)假設(shè)R, R, 可記作可記作xRy. xRy. 例如，數(shù)學(xué)常有這樣例如，數(shù)學(xué)常有這樣表示，如表示，如2424，

9、2|42|4，2=2 2=2 。例：例：R=, S=,a,b. R=, S=,a,b. R R是二元關(guān)系是二元關(guān)系, , 當(dāng)當(dāng)a,ba,b不是有序?qū)r(shí)，不是有序?qū)r(shí)，S S不是二元不是二元關(guān)系關(guān)系. . 根據(jù)上面的記法，可以記作根據(jù)上面的記法，可以記作1R2, aRb.1R2, aRb. 2. A 2. A到到B B的關(guān)系的關(guān)系 A A上的關(guān)系上的關(guān)系 定義定義 設(shè)設(shè)A,BA,B為集合為集合, A, AB B的任何子集稱作的任何子集稱作A A到到B B的二元關(guān)系的二元關(guān)系, , 當(dāng)當(dāng)A=BA=B時(shí)那么稱作時(shí)那么稱作A A上的二元關(guān)系上的二元關(guān)系. .例例 A=0,1, B=1,2,3, A=0

10、,1, B=1,2,3, 那么那么 R1=, R2=A R1=, R2=AB, R3=B, R3=, R4=, R4=R1, R2, R3, R4R1, R2, R3, R4是從是從A A到到B B的二元關(guān)系的二元關(guān)系. . 3. A上重要關(guān)系的實(shí)例上重要關(guān)系的實(shí)例設(shè)設(shè)A為恣意集合，稱為恣意集合，稱EA = AA為為A上的全域關(guān)系上的全域關(guān)系, IA = | xA A上的恒等關(guān)系。上的恒等關(guān)系。 例如例如A=1,2時(shí)時(shí), EA = ,， IA = ,。 例例1 實(shí)數(shù)集實(shí)數(shù)集A上的小于或等于關(guān)系可定義為上的小于或等于關(guān)系可定義為 LA = | x,yAxy假設(shè)假設(shè)A = 1,2,3 ，那么，那么

11、 LA=, 例例2 整數(shù)集整數(shù)集A上的整除關(guān)系可定義為上的整除關(guān)系可定義為 DA = | x,yA且且x|y 假設(shè)假設(shè)A = 1,2,3 ，那么，那么 DA=, 例例3 元素為集合的集合元素為集合的集合A上的包含于關(guān)系可定上的包含于關(guān)系可定義為義為 R = | x,yA 且且 xy 假設(shè)假設(shè)B=a,b, A = P(B) = ,a,b,a,b, 那么那么A上的包含關(guān)系是上的包含關(guān)系是 R = , , 類似可定義大于等于關(guān)系類似可定義大于等于關(guān)系, 小于關(guān)系小于關(guān)系, 大于關(guān)系大于關(guān)系, 真包真包含關(guān)系等含關(guān)系等 4關(guān)系的表示關(guān)系的表示 表示關(guān)系的方法有三種：序偶的集合、關(guān)系矩陣、表示關(guān)系的方法

12、有三種：序偶的集合、關(guān)系矩陣、關(guān)系圖關(guān)系圖.(1) 關(guān)系矩陣關(guān)系矩陣 假設(shè)假設(shè)A=x1, x2, , xm，B=y1, y2, , yn，R是是從從A到到B的關(guān)系，的關(guān)系，R的關(guān)系矩陣是布爾矩陣的關(guān)系矩陣是布爾矩陣MR = rij mn, 其中其中rij = 1 R. (2) 關(guān)系圖關(guān)系圖 假設(shè)假設(shè)A= x1, x2, , xm，R是從是從A上的關(guān)系，上的關(guān)系， R的關(guān)系圖是將的關(guān)系圖是將A中的字符作為結(jié)點(diǎn)，中的字符作為結(jié)點(diǎn)，R中序偶中序偶作為邊得到的圖：假設(shè)作為邊得到的圖：假設(shè)R，那么在圖中畫一，那么在圖中畫一條從條從x到到y(tǒng)的有向邊的有向邊. 留意：關(guān)系矩陣僅適宜于留意：關(guān)系矩陣僅適宜于A

13、，B為有窮集的情形；為有窮集的情形；而關(guān)系圖只適宜表示有窮集而關(guān)系圖只適宜表示有窮集A上的關(guān)系。上的關(guān)系。 第七節(jié)第七節(jié) 關(guān)系的運(yùn)算關(guān)系的運(yùn)算1. 1. 關(guān)系的逆與關(guān)系的復(fù)合關(guān)系的逆與關(guān)系的復(fù)合 定義定義1 1 關(guān)系關(guān)系R R的逆定義為的逆定義為R R1 = 1 = | | RR 定義定義2 2 關(guān)系關(guān)系R R與與S S的復(fù)合定義為的復(fù)合定義為 R RS = | | S = | | y y (R RS) S) 例例 設(shè)設(shè) R=, , , R=, , , ， S=, , , S=, , , , , ， 那么那么 R R1=, , , 1=, , , ， R RS =, , S =, , ， S

14、SR =, , , R =, , , 。2. 性質(zhì)性質(zhì)1 設(shè)設(shè)R，S為關(guān)系，那么關(guān)系矩陣為關(guān)系，那么關(guān)系矩陣 (1) MR-1=(MR)T (2) MRS =MR MS 其中的加法為邏輯其中的加法為邏輯加加利用以上性質(zhì)可進(jìn)展關(guān)系的復(fù)合的計(jì)算。利用以上性質(zhì)可進(jìn)展關(guān)系的復(fù)合的計(jì)算。 例例 在上例中，計(jì)算在上例中，計(jì)算RS也可用以下方法進(jìn)展：也可用以下方法進(jìn)展： 故故 RS =, , ，與前面用定義，與前面用定義計(jì)算的結(jié)果一致。計(jì)算的結(jié)果一致。 000000000110000100000110010001010000000001101001 SRSRMMM 性質(zhì)性質(zhì)2 設(shè)設(shè)P，R，S為關(guān)系，那么有為

15、關(guān)系，那么有 (1) 結(jié)合律結(jié)合律 (PR)S=P(RS) (2) 復(fù)合的逆復(fù)合的逆 (PR)-1= R-1P-1 第八節(jié)第八節(jié) 一些重要關(guān)系一些重要關(guān)系1自反關(guān)系自反關(guān)系 反自反關(guān)系反自反關(guān)系 定義定義 設(shè)設(shè)R為為A上的關(guān)系：上的關(guān)系： 1假設(shè)假設(shè)xA, 均有均有R, 那么稱那么稱R是自是自反的反的. 2假設(shè)假設(shè)xA, 均有均有R, 那么稱那么稱R是反是反自反的自反的. 例例1 設(shè)設(shè)A=1,2,3, R1, R2, , , R3. R2是自反的，是自反的，R3是反自反的，是反自反的，R1既不是自反的也不既不是自反的也不是反自反的是反自反的. 例例2 小于等于關(guān)系小于等于關(guān)系LA, 整除關(guān)系整

16、除關(guān)系DA是自反關(guān)系是自反關(guān)系, 而而實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系是反自反實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系是反自反關(guān)系。關(guān)系。假設(shè)運(yùn)用關(guān)系矩陣，那么假設(shè)運(yùn)用關(guān)系矩陣，那么 關(guān)系為自反的關(guān)系為自反的矩陣對(duì)角線元素全為矩陣對(duì)角線元素全為1； 關(guān)系為反自反的關(guān)系為反自反的矩陣對(duì)角線元素全為矩陣對(duì)角線元素全為0 假設(shè)運(yùn)用關(guān)系圖，那么假設(shè)運(yùn)用關(guān)系圖，那么 關(guān)系為自反的關(guān)系為自反的圖中每個(gè)點(diǎn)均有環(huán)；圖中每個(gè)點(diǎn)均有環(huán)； 關(guān)系為反自反的關(guān)系為反自反的圖中每個(gè)點(diǎn)均沒有環(huán)圖中每個(gè)點(diǎn)均沒有環(huán)例例3 全域關(guān)系全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA都是自反的。都是自反的。2對(duì)稱性對(duì)稱性 反對(duì)稱性反對(duì)稱性

17、定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 1假設(shè)假設(shè) R, 均有均有 R, 那么稱那么稱R是對(duì)稱是對(duì)稱的的.2假設(shè)假設(shè) R, R, 就有就有x=y, 那么稱那么稱R是反是反對(duì)稱的對(duì)稱的.(或或:假設(shè)假設(shè)R(xy),就有就有 R, 那么稱那么稱R是反對(duì)是反對(duì)稱的稱的) R是對(duì)稱的是對(duì)稱的MR為對(duì)稱矩陣為對(duì)稱矩陣; R是反對(duì)稱的是反對(duì)稱的MR為每為每對(duì)元素對(duì)元素mij, mji(ij)均不同時(shí)為均不同時(shí)為1 R是對(duì)稱的是對(duì)稱的關(guān)系圖中有邊相聯(lián)的兩點(diǎn)間邊均成對(duì)出現(xiàn)關(guān)系圖中有邊相聯(lián)的兩點(diǎn)間邊均成對(duì)出現(xiàn); R是反對(duì)稱的是反對(duì)稱的關(guān)系圖中兩點(diǎn)間邊均不成對(duì)出現(xiàn)關(guān)系圖中兩點(diǎn)間邊均不成對(duì)出現(xiàn) 實(shí)例：實(shí)例：對(duì)稱關(guān)

18、系：對(duì)稱關(guān)系：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA反對(duì)稱關(guān)系：恒等關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系IA例例 設(shè)設(shè)A1,2,3, R1, R2, R3和和R4都是都是A上的關(guān)系上的關(guān)系, 其中其中 R1,，R2, R3,，R4, R1既是對(duì)稱也是反對(duì)稱的既是對(duì)稱也是反對(duì)稱的. R2是對(duì)稱的但不是反對(duì)稱的是對(duì)稱的但不是反對(duì)稱的. R3反對(duì)稱反對(duì)稱, 但非對(duì)稱但非對(duì)稱. R4既不是對(duì)稱的也不是反對(duì)稱的既不是對(duì)稱的也不是反對(duì)稱的. 3傳送性傳送性 定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 假設(shè)假設(shè), R 都有都有 R, 那么稱那么稱R是是A上的傳送關(guān)系上的傳送關(guān)系. 實(shí)例：實(shí)例：A上的全域關(guān)

19、系上的全域關(guān)系EA,恒等關(guān)系恒等關(guān)系IA, 小于等于和小于關(guān)系，整除小于等于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系關(guān)系，包含與真包含關(guān)系. 設(shè)設(shè)A1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3那么那么R1和和R3是是A上的傳送關(guān)系上的傳送關(guān)系, R2不是不是A上的傳送關(guān)系上的傳送關(guān)系.二關(guān)系性質(zhì)的等價(jià)描畫二關(guān)系性質(zhì)的等價(jià)描畫 下面給出這五種性質(zhì)成立的充分必要條件下面給出這五種性質(zhì)成立的充分必要條件. 定理定理 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 那么那么1 R在在A上自反當(dāng)且僅當(dāng)上自反當(dāng)且僅當(dāng) IA R.2 R在在A上反自反當(dāng)且僅當(dāng)上反自反當(dāng)且僅當(dāng) RI

20、A =.3 R在在A上對(duì)稱當(dāng)且僅當(dāng)上對(duì)稱當(dāng)且僅當(dāng) R=R1.4 R在在A上反對(duì)稱當(dāng)且僅當(dāng)上反對(duì)稱當(dāng)且僅當(dāng) RR1IA.5 R在在A上傳送當(dāng)且僅當(dāng)上傳送當(dāng)且僅當(dāng) RRR . 例例 判別以下圖中關(guān)系的性質(zhì)判別以下圖中關(guān)系的性質(zhì), 并闡明理由并闡明理由. 1 2 31不是自反也不是反自反的；對(duì)稱的不是自反也不是反自反的；對(duì)稱的, 不是反對(duì)稱的；不是反對(duì)稱的；不是傳送的不是傳送的. 2是反自反但不是自反的；是反對(duì)稱的但不是對(duì)稱的；是是反自反但不是自反的；是反對(duì)稱的但不是對(duì)稱的；是傳送的傳送的. 3是自反但不是反自反的；是反對(duì)稱的但不是對(duì)稱的；不是自反但不是反自反的；是反對(duì)稱的但不是對(duì)稱的；不是傳送的是

21、傳送的. 第九節(jié)第九節(jié) 關(guān)系的閉包關(guān)系的閉包一、閉包定義一、閉包定義 定義定義 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, 在在R中添中添加最少的序偶后使其成為自反的對(duì)稱的或傳送加最少的序偶后使其成為自反的對(duì)稱的或傳送的的,所得新關(guān)系所得新關(guān)系R稱為原關(guān)系稱為原關(guān)系R的自反的自反(對(duì)稱或傳送對(duì)稱或傳送)閉包閉包. 普通將普通將R的自反閉包記作的自反閉包記作r(R), 對(duì)稱閉包記作對(duì)稱閉包記作s(R), 傳送閉包記作傳送閉包記作t(R). 二、閉包的構(gòu)造方法二、閉包的構(gòu)造方法 1. 用集合的方法用集合的方法 定理定理 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 那么有那么有 1r(R)=RR02s(R)

22、=RR13t(R)=RR2R3 Rn (n=|A|) 2. 用關(guān)系矩陣構(gòu)造用關(guān)系矩陣構(gòu)造 性質(zhì)性質(zhì) 設(shè)設(shè)R，S為關(guān)系，那么關(guān)系矩陣為關(guān)系，那么關(guān)系矩陣 (1) MR-1=(MR)T (2) MRS =MR MS 其中的加法為邏輯加其中的加法為邏輯加 設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為的關(guān)系矩陣分別為M, Mr, Ms和和Mt, 那么那么 Mr=M+I , Ms=M+MT , Mt=M+M2+M3+Mn其中其中I是和是和M同階的單位矩陣同階的單位矩陣, MT是是M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣. 留意在上述等式中矩陣的元素相加時(shí)運(yùn)用邏輯加留意在上述等式中矩陣的元素相加時(shí)運(yùn)用

23、邏輯加. *3. 用圖構(gòu)造用圖構(gòu)造 對(duì)關(guān)系對(duì)關(guān)系R: r(R): 在在R中添加最少個(gè)數(shù)的環(huán)中添加最少個(gè)數(shù)的環(huán), 使得每個(gè)點(diǎn)上均有環(huán)使得每個(gè)點(diǎn)上均有環(huán). s(R): 在在R中恣意有單邊相聯(lián)的兩點(diǎn)間加上一邊中恣意有單邊相聯(lián)的兩點(diǎn)間加上一邊(方向與已方向與已有邊相反有邊相反). t(R): 在在R中從每個(gè)點(diǎn)中從每個(gè)點(diǎn)xi出發(fā)出發(fā), 假設(shè)假設(shè)xi可以到可以到xk (至少一步至少一步)的的話話, 當(dāng)原圖沒有邊當(dāng)原圖沒有邊時(shí)就加上邊時(shí)就加上邊, k=1,2,.,n.3. Warshall算法算法求可達(dá)矩陣求可達(dá)矩陣(傳送閉包傳送閉包) 對(duì)于有向圖對(duì)于有向圖R, 其可達(dá)矩陣其可達(dá)矩陣M=(mij)nn表示圖

24、的表示圖的各點(diǎn)到其它點(diǎn)能否可達(dá)的情況各點(diǎn)到其它點(diǎn)能否可達(dá)的情況, mij表示點(diǎn)表示點(diǎn)xi是可以到達(dá)是可以到達(dá)點(diǎn)點(diǎn)xj(1-可達(dá)可達(dá), 0-不可達(dá)不可達(dá)). Warshall 算法算法 for (j=1;jn;j+) /第第j列列 for(i=1;in;i+ ) /第第i個(gè)個(gè) if (mij=1) 第第i行行=第第i行行第第j行行; 11111111111111111111100011111111011110000111011100101000011100100010100001010010M 例例 用用Marshall 算法求上例中關(guān)系算法求上例中關(guān)系R的傳送的傳送閉包閉包.將第將第1行加到值

25、為行加到值為1的行上去的行上去將第將第2行加到值為行加到值為1的行上去的行上去第十節(jié)第十節(jié) 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分一、等價(jià)關(guān)系的定義與實(shí)例一、等價(jià)關(guān)系的定義與實(shí)例定義定義 假設(shè)關(guān)系假設(shè)關(guān)系R是自反、對(duì)稱、傳送的是自反、對(duì)稱、傳送的, 那么稱那么稱R是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系. 設(shè)設(shè)R是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系, 假設(shè)假設(shè) R, 稱稱x等價(jià)于等價(jià)于y, 記做記做xy.例例 設(shè)設(shè)A=1,2,8, 如下定義如下定義A上的模上的模3關(guān)關(guān)系系R： R=| x,y A且且x,y除以除以3的余數(shù)一的余數(shù)一樣樣不難驗(yàn)證不難驗(yàn)證R為為A上的等價(jià)關(guān)系：上的等價(jià)關(guān)系：(1)xA, 有有xRx; (2)x,

26、yA, 假設(shè)假設(shè)xRy, 顯然有顯然有yRx; (3)x,y,zA, 假設(shè)假設(shè)xRy, yRz, 顯然有顯然有xRz .二、等價(jià)類及其性質(zhì)二、等價(jià)類及其性質(zhì) 1. 等價(jià)類等價(jià)類 定義定義 設(shè)設(shè)R為非空集合為非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, xA，令，令 xR = y | yA且且xRy,稱稱xR為為x關(guān)于關(guān)于R的等價(jià)類的等價(jià)類, 簡稱為簡稱為x 的等價(jià)類的等價(jià)類, 簡簡記為記為x或或 x.A=1, 2, , 8上模上模3等價(jià)關(guān)系的等價(jià)類：等價(jià)關(guān)系的等價(jià)類： 1 = 4 = 7 = 1, 4, 7, 2 = 5 = 8 = 2, 5, 8, 3 = 6 = 3, 6 .2等價(jià)類的性質(zhì)等價(jià)類的

27、性質(zhì) 定理定理7.14 設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 那么那么 1xA, x是是A的非空子集的非空子集. 2x,yA, 假設(shè)假設(shè)xRy, 那么那么 x = y. 3x,yA, 假設(shè)假設(shè)x Ry, 那么那么 x與與y不交不交. 4x | xA=A.證證1由等價(jià)類的定義可知由等價(jià)類的定義可知, xA有有xA. 又由自反性又由自反性有有x x, 即即x非空非空.2任取任取z, 那么有那么有 zx R R, RR R R從而證明了從而證明了zy. 綜上所述必有綜上所述必有 xy. 同理可證同理可證 yx. 這就得到了這就得到了x = y. 3 假設(shè)假設(shè) xy , 那么存在那么

28、存在zxy, 從從而有而有z x，zy, 即即R，R成立成立. 根據(jù)根據(jù)R的對(duì)稱性和傳送性必有的對(duì)稱性和傳送性必有R, 與與xRy矛盾矛盾.4 先證先證x | xA A任取任取yx | xA ，設(shè)，設(shè) yx0 A，那么，那么yA .從而從而 x | xA A .再證再證A x | xA. 任取任取 yA yy yx | xA, 從而從而 x | xA A.綜上所述綜上所述, 得得x | xA = A. 三、商集與集合的劃分三、商集與集合的劃分 1. 商集商集 定義定義7.17 設(shè)設(shè)R為非空集合為非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 以以R的的一切等價(jià)類作為元素的集合稱為一切等價(jià)類作為元素的集合

29、稱為A關(guān)于關(guān)于R的商集的商集, 記記做做A/R, A/R = xR | xA. 三、集合的劃分與等價(jià)關(guān)系三、集合的劃分與等價(jià)關(guān)系 1集合的劃分集合的劃分 定義定義 設(shè)設(shè)A為非空集合為非空集合, 假設(shè)假設(shè)A的子集族的子集族 ( P(A)滿足下面條件：滿足下面條件： 1 ; 2x,y，有，有xy=; 3 = A.那么稱那么稱是是A的一個(gè)劃分的一個(gè)劃分, 稱稱中的元素為中的元素為A的劃分塊的劃分塊. 例例 設(shè)設(shè)Aa,b,c,d, 給定給定1, 2, 3, 4, 5, 6如下：如下：1=a,b,c,d,2=a,b,c,d,3=a,a,b,c,d,4=a,b,c,5=,a,b,c,d, 6=a,a,b,

30、c,d,那么那么1和和2是是A的劃分的劃分, 其他都不是其他都不是A的劃分的劃分. 2. 等價(jià)關(guān)系與劃分的對(duì)應(yīng)關(guān)系等價(jià)關(guān)系與劃分的對(duì)應(yīng)關(guān)系 性質(zhì)性質(zhì) 假設(shè)假設(shè)R是集合是集合A上的等價(jià)關(guān)系，那上的等價(jià)關(guān)系，那么么x R | xA就是就是A的一個(gè)劃分。的一個(gè)劃分。 A上不上不同的等價(jià)關(guān)系決議同的等價(jià)關(guān)系決議A上不同的劃分上不同的劃分. 例例 設(shè)設(shè)A=1,2,8, A關(guān)于模關(guān)于模3等價(jià)關(guān)系等價(jià)關(guān)系R的的劃分為劃分為 1= 1,4,7, 2,5,8, 3,6 . A關(guān)于恒等關(guān)系和全域關(guān)系的劃分為：關(guān)于恒等關(guān)系和全域關(guān)系的劃分為： 2= 1, 2, , 8 , 3= 1,2,8 .反過來，任給反過來，任

31、給A的一個(gè)劃分的一個(gè)劃分, 如下定義如下定義A上上的關(guān)系的關(guān)系R： R=| x,yAx與與y在在的同一劃分塊的同一劃分塊中中, 那么那么R為為A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 且該等價(jià)關(guān)系所確且該等價(jià)關(guān)系所確定的劃分就是定的劃分就是. 定理定理 A上的等價(jià)關(guān)系與上的等價(jià)關(guān)系與A的劃分是一一對(duì)應(yīng)的劃分是一一對(duì)應(yīng)的的. 123圖7例例 給出給出A1,2,3上一切的等價(jià)關(guān)系上一切的等價(jià)關(guān)系. 解解 如以下圖如以下圖, 先做出先做出A的一切劃分的一切劃分, 從左到右分從左到右分別記作別記作1,2,3,4,5. 這些劃分與這些劃分與A上的等價(jià)關(guān)系之間的一一對(duì)應(yīng)是：上的等價(jià)關(guān)系之間的一一對(duì)應(yīng)是：4對(duì)應(yīng)于全域關(guān)

32、系對(duì)應(yīng)于全域關(guān)系EA, 5對(duì)應(yīng)于恒等關(guān)系對(duì)應(yīng)于恒等關(guān)系IA, 1,2和和3分別對(duì)應(yīng)于等價(jià)關(guān)系分別對(duì)應(yīng)于等價(jià)關(guān)系R1, R2和和R3. 其其中中 R1=,IA, R2=,IA, R3=,IA .第十一節(jié)第十一節(jié) 偏序關(guān)系偏序關(guān)系一、偏序關(guān)系一、偏序關(guān)系 1定義定義 自反、反對(duì)稱和傳送的關(guān)系稱為自反、反對(duì)稱和傳送的關(guān)系稱為偏序關(guān)系偏序關(guān)系(廣義廣義“小于或等于小于或等于) ，記作，記作 .設(shè)設(shè) 為偏序關(guān)系為偏序關(guān)系, 假設(shè)假設(shè) , 那么記作那么記作x y, 讀作讀作x“小于或等于小于或等于y. 2. 實(shí)例實(shí)例集合集合A上的恒等關(guān)系上的恒等關(guān)系IA是是A上的偏序關(guān)系上的偏序關(guān)系. 小于或等于關(guān)系小于

33、或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系相應(yīng)集合上的偏序關(guān)系. 3相關(guān)概念相關(guān)概念定義定義 設(shè)設(shè)R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, x,yA, x與與y可比可比 x y y x. 任取兩個(gè)元素任取兩個(gè)元素x和和y, 能夠有下述幾種情況發(fā)生：能夠有下述幾種情況發(fā)生： 或者或者 x y(或或y x), 或者或者 xy, 或者或者x與與y不可比不可比. 定義定義 R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, 假設(shè)假設(shè) x,yA, x與與y都是可比的，那么稱都是可比的，那么稱R為全序或線序。為全序或線序。例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系，

34、但整除關(guān)系不例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系，但整除關(guān)系不是正整數(shù)集合上的全序關(guān)系。是正整數(shù)集合上的全序關(guān)系。定義定義 x,yA, 假設(shè)假設(shè)x y且不存在且不存在zA使得使得x z y, 那么那么稱稱y覆蓋覆蓋x.例如例如1,2,4,6集合上的整除關(guān)系集合上的整除關(guān)系, 2覆蓋覆蓋1, 4和和6覆蓋覆蓋2. 但但4不不覆蓋覆蓋1. 二、偏序集與哈斯圖二、偏序集與哈斯圖1偏序集偏序集定義定義 集合集合A和和A上的偏序關(guān)系上的偏序關(guān)系 一同叫做偏序集一同叫做偏序集, 記作記作. 實(shí)例：實(shí)例：整數(shù)集合整數(shù)集合Z和數(shù)的小于或等于關(guān)系和數(shù)的小于或等于關(guān)系構(gòu)成偏序集構(gòu)成偏序集，集合，集合A的冪集的冪集

35、P(A)和包含關(guān)系和包含關(guān)系R構(gòu)成偏序集構(gòu)成偏序集. 2哈斯圖哈斯圖利用偏序關(guān)系的自反、反對(duì)稱、傳送性進(jìn)展簡化的關(guān)系圖利用偏序關(guān)系的自反、反對(duì)稱、傳送性進(jìn)展簡化的關(guān)系圖特點(diǎn)：特點(diǎn)：每個(gè)結(jié)點(diǎn)沒有環(huán)；每個(gè)結(jié)點(diǎn)沒有環(huán)；兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系經(jīng)過結(jié)點(diǎn)位置的高低表示，位兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系經(jīng)過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前；置低的元素的順序在前；具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊。具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊。例例 偏序集偏序集 和和 的哈斯圖的哈斯圖. 例例 知偏序集知偏序集的哈斯圖如以下圖所示的哈斯圖如以下圖所示, 試求出集合試求出集合A和和關(guān)系關(guān)系R的表達(dá)式的表達(dá)式. 解解 A

36、=a,b,c,d,e,f,g,h，R=,IA 三、偏序集中的特殊元素三、偏序集中的特殊元素. 1. 最小元、最大元、極小元、極大元最小元、最大元、極小元、極大元定義定義 設(shè)設(shè)為偏序集為偏序集, BA, yB.1假設(shè)假設(shè)y為為B中最小者中最小者, 那么稱那么稱y為為B的最小元的最小元.2假設(shè)假設(shè)y為為B中最大者中最大者, 那么稱那么稱y為為B的最大元的最大元. 3假設(shè)假設(shè)B中與中與y可比的一切元素中可比的一切元素中y最小最小, 那么稱那么稱y為為B的極小元的極小元. 4假設(shè)假設(shè)B中與中與y可比的一切元素中可比的一切元素中y最大最大, 那么稱那么稱y為為B的極大元的極大元. 性質(zhì)：性質(zhì)： 對(duì)于有窮

37、集，極小元和極大元一定存在，還能夠?qū)τ谟懈F集，極小元和極大元一定存在，還能夠存在多個(gè)存在多個(gè). 最小元和最大元不一定存在，假設(shè)存在一定獨(dú)一最小元和最大元不一定存在，假設(shè)存在一定獨(dú)一.最小元一定是極小元；最大元一定是極大元最小元一定是極小元；最大元一定是極大元. 孤立結(jié)點(diǎn)既是極小元，也是極大元孤立結(jié)點(diǎn)既是極小元，也是極大元. 2下界、上界、下確界最大下界、上確界最小上界下界、上界、下確界最大下界、上確界最小上界定義定義 設(shè)設(shè)為偏序集為偏序集, BA, yA.1假設(shè)假設(shè)x (xBx y)成立成立, 那么稱那么稱y為為B的上界的上界. 2假設(shè)假設(shè)x(xBy x)成立成立, 那么稱那么稱y為為B的下界

38、的下界. 3令令Cy| y為為B的上界的上界, 那么稱那么稱C的最小元為的最小元為B的最小上的最小上界或上確界界或上確界. 4令令Dy| y為為B的下界的下界, 那么稱那么稱D的最大元為的最大元為B的最大下的最大下界或下確界界或下確界. 性質(zhì)：性質(zhì)：下界、上界、下確界、上確界不一定存在。下界、上界、下確界、上確界不一定存在。 下界、上界存在不一定獨(dú)一。下界、上界存在不一定獨(dú)一。 下確界、上確界假設(shè)存在，那么獨(dú)一。下確界、上確界假設(shè)存在，那么獨(dú)一。 集合的最小元就是它的下確界，最大元就是它的上確界；反集合的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì)之不對(duì). 例例 設(shè)偏序集設(shè)偏序集如以下

39、圖所示，求如以下圖所示，求A的極小元、最小元、的極小元、最小元、極大元、最大元極大元、最大元. 設(shè)設(shè)Bb,c,d, 求求B的下界、上界、下確界、上確界的下界、上界、下確界、上確界. 解解 極小元：極小元：a, b, c, g； 極大元：極大元：a, f, h；沒有最小元與最大元；沒有最小元與最大元.B的下界和最大下界都不存在的下界和最大下界都不存在, 上界有上界有d 和和f, 最小上界為最小上界為d. 第八章第八章 函數(shù)函數(shù)主要內(nèi)容主要內(nèi)容函數(shù)的定義函數(shù)的定義函數(shù)的性質(zhì)函數(shù)的性質(zhì)函數(shù)的逆函數(shù)的逆函數(shù)的合成函數(shù)的合成 第一節(jié)第一節(jié) 函數(shù)的定義與性質(zhì)函數(shù)的定義與性質(zhì)主要內(nèi)容主要內(nèi)容一、函數(shù)定義與相

40、關(guān)概念一、函數(shù)定義與相關(guān)概念 函數(shù)定義函數(shù)定義 函數(shù)相等函數(shù)相等 從從A到到B的函數(shù)的函數(shù)f:AB BA 函數(shù)的像與完全原像函數(shù)的像與完全原像二、函數(shù)的性質(zhì)二、函數(shù)的性質(zhì)單射、滿射、雙射函數(shù)的定義與實(shí)例單射、滿射、雙射函數(shù)的定義與實(shí)例構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù)三、某些重要的函數(shù)三、某些重要的函數(shù) 一、函數(shù)的定義與相關(guān)概念一、函數(shù)的定義與相關(guān)概念1函數(shù)定義函數(shù)定義 定義定義8.1 設(shè)設(shè)F為二元關(guān)系為二元關(guān)系, 假設(shè)假設(shè)xdomF都存都存在獨(dú)一的在獨(dú)一的yranF 使使xFy成立成立, 那么稱那么稱F為函數(shù)為函數(shù). 對(duì)于函數(shù)對(duì)于函數(shù)F, 假設(shè)有假設(shè)有xFy, 那么記作那么記作y=F(x), 并稱并稱

41、y為為F在在x的值的值. 例例 F1=, F2=, F1是函數(shù)是函數(shù), F2不是函數(shù)不是函數(shù). 2. 函數(shù)相等函數(shù)相等 定義定義8.2 設(shè)設(shè)F, G為函數(shù)為函數(shù), 那么那么 F=G FGGF .假設(shè)兩個(gè)函數(shù)假設(shè)兩個(gè)函數(shù)F和和G相等相等, 該當(dāng)滿足下面兩個(gè)條件：該當(dāng)滿足下面兩個(gè)條件： (1) domF=domG； (2) xdomF=domG 都有都有F(x)=G(x)。 函數(shù)函數(shù)F(x)=(x21)/(x+1), G(x)=x1不相等不相等, 由由于于domF domG. 3. 從從A到到B的函數(shù)的函數(shù)定義定義8.3 設(shè)設(shè)A, B為集合為集合, 假設(shè)假設(shè)f為函數(shù)為函數(shù), domf=A,ranf

42、 B, 那么稱那么稱f為從為從A到到B的函數(shù)的函數(shù), 記作記作f：AB. 例例 f：NN, f(x)=2x 是從是從N到到N的函數(shù)的函數(shù), g：NN, g(x)=2 也是從也是從N到到N的函數(shù)的函數(shù). 4BA定義定義8.4 一切從一切從A到到B的函數(shù)的集合記作的函數(shù)的集合記作BA, 符號(hào)化符號(hào)化表示為表示為 BA=f | f：AB 。|A|=m, |B|=n, 且且m,n0, |BA|=nm.A=, 那么那么BA=B=. A且且B=, 那么那么BA=A= . 例例 設(shè)設(shè)A=1,2,3, B=a,b, 求求BA.解解BA=f0,f1,f7, 其中其中 f 0 = , , f 1 = , , f

43、2 = , , f 3 = , , f 4 = , , f 5 = , , f 6 = , , f7=, 5函數(shù)的像和完全原像函數(shù)的像和完全原像定義定義8.5 設(shè)函數(shù)設(shè)函數(shù)f：AB, A1A, B1B. 1A1在在f下的像下的像f(A1)=f(x)|xA1 。函數(shù)的像函數(shù)的像f(A) 2B1在在f下的完全原像下的完全原像 f 1(B1) = x| xAf(x)B1留意：留意： 函 數(shù) 值函 數(shù) 值 f ( x ) B , 而 像而 像 f ( A 1 ) B . 普通說來普通說來f 1(f(A1)A1, 但是但是A1f 1(f(A1). 例例 設(shè)設(shè)f：NN, 且且 令令A(yù)=0,1, B=2,

44、那么有那么有 f(A)=f(0,1)=f(0),f(1)=0,2， f 1(B)= f 1(2)=1,4。 為奇數(shù)為奇數(shù)若若為偶數(shù)為偶數(shù)若若xxxxxf12/)( 定義定義8.6 設(shè)設(shè)f：AB,1假設(shè)假設(shè)ranf=B, 那么稱那么稱f：AB是滿射的是滿射的.2假設(shè)假設(shè)yranf都存在獨(dú)一的都存在獨(dú)一的xA使得使得f(x)=y, 那么稱那么稱f：AB是單射的是單射的.3假設(shè)假設(shè)f：AB既是滿射又是單射的既是滿射又是單射的, 那么稱那么稱f：AB是雙射的是雙射的例例 判別下面函數(shù)能否為單射判別下面函數(shù)能否為單射, 滿射滿射, 雙射的雙射的, 為什么為什么? 1 f ： R R , f ( x )

45、= x 2 + 2 x 1 2f：Z+R, f(x)=lnx, Z+為正整數(shù)集為正整數(shù)集 3 f ： R Z , f ( x ) = x 4 f ： R R , f ( x ) = 2 x + 1 5f：R+R+, f(x)=(x2+1)/x, 其中其中R+為正實(shí)數(shù)為正實(shí)數(shù)集集. 解解1f：RR, f(x)=x2+2x1 在在x=1獲得極獲得極大值大值0. 既不是單射也不是滿射的既不是單射也不是滿射的.2f：Z+R, f(x)=lnx 是單調(diào)上升的是單調(diào)上升的, 是單射的是單射的. 但不滿射但不滿射, ranf=ln1, ln2, . 3f：RZ, f(x)= x 是滿射的是滿射的, 但不是單

46、射的但不是單射的, 例如例如f(1.5)=f(1.2)=1.4f：RR, f(x)=2x+1 是滿射、單射、雙射的是滿射、單射、雙射的, 由于它是單調(diào)函數(shù)并且由于它是單調(diào)函數(shù)并且ranf=R.5f：R+R+, f(x)=(x2+1)/x 有極小值有極小值f(1)=2. 該該函數(shù)既不是單射的也不是滿射的函數(shù)既不是單射的也不是滿射的. 例例 對(duì)于給定的集合對(duì)于給定的集合A和和B構(gòu)造雙射函數(shù)構(gòu)造雙射函數(shù)f：AB.1A=P(1,2,3), B=0,11,2,32A=0,1, B=1/4,1/23A=Z, B=N4A=/2,3/2, B=1,1 解解1A=,1,2,3,1,2,1,3,2,3,1,2,3

47、. B=f0,f1,f7, 其中其中f0=, f1=,f2=, f3=,f4=, f5=,f6=, f7=,. 令令f：AB, 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)=f7 2令f：0,11/4,1/2, f(x)=(x+1)/4.3將Z中元素以以下順序陳列并與N中元素對(duì)應(yīng)：Z：011 2233 N：0 1 2 3 4 5 6 那么這種對(duì)應(yīng)所表示的函數(shù)是： 4令f：/2,3/21,1 f(x)=sinx 01202)(,ZxxxxfNf：三、某些重要函數(shù)三、某些重要函數(shù)定義定義8.

48、7 1設(shè)設(shè)f：AB, 假設(shè)存在假設(shè)存在cB使得對(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，假，假設(shè)對(duì)恣意的設(shè)對(duì)恣意的x1, x2A, x1 1 x2, 就有就有f(x1) 2 f(x2), 那么稱那么稱f為單調(diào)遞增的；假設(shè)對(duì)恣意的為單調(diào)遞增的；假設(shè)對(duì)恣意的x1, x2A, x1 1 x2, 就有就有f(x1) 2f(x2), 那么稱那么稱f為嚴(yán)厲單調(diào)遞增為嚴(yán)厲單調(diào)遞增的的. 類似的也可以定義單調(diào)遞減和

49、嚴(yán)厲單調(diào)遞減的類似的也可以定義單調(diào)遞減和嚴(yán)厲單調(diào)遞減的函數(shù)函數(shù). (4) 設(shè)設(shè)A為集合為集合, 對(duì)于恣意的對(duì)于恣意的AA, A的特征函數(shù)的特征函數(shù) A：A0,1定義為定義為 A(a)=1, aA A(a)=0, aAA(5) 設(shè)設(shè)R是是A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 令令 g：AA/R g(a)=a, aA,稱稱g是從是從A到商集到商集A/R的自然映射的自然映射. 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)

50、厲單調(diào)遞增的.2A的每一個(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=, .3給定集合給定集合A和和A上的等價(jià)關(guān)系上的等價(jià)關(guān)系R, 就可以確定就可以確定一個(gè)自然映射一個(gè)自然映射g：AA/R. 不同的等價(jià)關(guān)系確定不同的自然映射不同的等價(jià)關(guān)系確定不同的自然映射, 其中恒其中恒等關(guān)系所確定的自然映射是雙射等關(guān)系所確定的自然映射是雙射, 而其他的自然映而其他的自然映射普通來說只是滿射射普通來說只是滿射. 例如例如 A=1,2,3, R=,IA, g(1)=g(2)=

51、1,2, g(3)=3 .第九章第九章 集合的基數(shù)集合的基數(shù)主要內(nèi)容主要內(nèi)容集合的等勢及其性質(zhì)集合的等勢及其性質(zhì)重要的等勢或不等勢的結(jié)果重要的等勢或不等勢的結(jié)果集合的優(yōu)勢及其性質(zhì)集合的優(yōu)勢及其性質(zhì)自然數(shù)與自然數(shù)集合自然數(shù)與自然數(shù)集合集合的基數(shù)集合的基數(shù)可數(shù)集可數(shù)集 第一節(jié)第一節(jié) 集合的等勢與優(yōu)勢集合的等勢與優(yōu)勢 一、集合的等勢一、集合的等勢 1. 等勢定義等勢定義定義定義9.1 設(shè)設(shè)A, B是集合是集合, 假設(shè)存在著從假設(shè)存在著從A到到B的雙射函數(shù)的雙射函數(shù), 就稱就稱A和和B是等勢的是等勢的, 記作記作AB. 假設(shè)假設(shè)A不與不與B等勢等勢, 那么記作那么記作AB.2. 集合等勢的實(shí)例集合等勢

52、的實(shí)例.例例1ZN. 那么那么f是是Z到到N的雙射函數(shù)的雙射函數(shù). 從而證明了從而證明了ZN. 01202)(,:xxxxxfNZf2 NNN. NN中一切的元素排成有序序列中一切的元素排成有序序列: 圖圖1 雙射函數(shù)雙射函數(shù) 3 NQ. 為建立N到Q的雙射函數(shù), 先把一切方式為p/q (p,q為整數(shù)且q0) 的數(shù)排成一張表. 在計(jì)數(shù)中只思索每個(gè)數(shù)的第一次出現(xiàn). 表中數(shù)p/q上方的方括號(hào)內(nèi)標(biāo)明了這個(gè)有理數(shù)所對(duì)應(yīng)的計(jì)數(shù)結(jié)果. 雙射函數(shù) f：NQ, 其中f(n)是n下方的有理數(shù). 從而證明了NQ. -2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111

53、110/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/41/41/41414PLAY4(0,1)R. 其中實(shí)數(shù)區(qū)間其中實(shí)數(shù)區(qū)間 (0,1)=x| xR0 x1. 令令雙射函數(shù)雙射函數(shù) 50,1(0,1). 其中其中(0,1)和和0,1分別為實(shí)數(shù)開區(qū)間和閉區(qū)間分別為實(shí)數(shù)開區(qū)間和閉區(qū)

54、間. 雙射函數(shù)雙射函數(shù) f : 0,1(0,1) 6對(duì)任何對(duì)任何a, bR, ab, 0,1a,b. 雙射函數(shù)雙射函數(shù)f：0,1a,b, f(x)=(ba)x+a.類似地可以證明類似地可以證明, 對(duì)任何對(duì)任何a, bR, ab, 有有(0,1)(a,b). 212tan)(,)1 , 0(: xxfRf xxnxxxxfnn其其它它,.2,1,2/1,2/11,2/10,2/1)(12例例 設(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的

55、特征函數(shù)的特征函數(shù). 易證易證f是單射的是單射的. 對(duì)于恣意的對(duì)于恣意的g0,1A, 那么有那么有g(shù)：A0,1. 令令 B=x| xAg(x)=1,那么那么BA, 且且B=g, 即即BP(A), f(B)=g. 從從而證明了而證明了f是滿射的是滿射的. 由等勢定義得由等勢定義得 P(A)0,1A. 3等勢的性質(zhì)等勢的性質(zhì)定理定理9.1 設(shè)設(shè)A，B，C是恣意集合，是恣意集合， 1AA;2假設(shè)假設(shè)AB，那么，那么BA;3假設(shè)假設(shè)AB，BC，那么，那么AC.證明思緒：利用等勢的等義證明思緒：利用等勢的等義. 1IA是從是從A到到A的雙射的雙射; 2假設(shè)假設(shè)f：AB是雙射，那么是雙射，那么f1：BA是

56、是從從B到到A的雙射的雙射; 3假設(shè)假設(shè)f：AB，g：BC是雙射，那么是雙射，那么fg：AC是從是從A到到C的雙射的雙射.二、重要的等勢或不等勢的結(jié)果二、重要的等勢或不等勢的結(jié)果1等勢結(jié)果等勢結(jié)果 N Z Q NN 任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合R等勢等勢 2不等勢的結(jié)果不等勢的結(jié)果 定理定理9.2 (康托定理康托定理) 1NR 2對(duì)恣意集合對(duì)恣意集合A都有都有AP(A). 證明思緒：證明思緒：1只需證明任何函數(shù)只需證明任何函數(shù)f：N0,1都不是滿射的都不是滿射的. 任取函數(shù)任取函數(shù)f：N0,1, 列出列出f的一切函數(shù)值的一切函數(shù)值. 然后構(gòu)造一個(gè)然后構(gòu)造一個(gè)0,1區(qū)間的小數(shù)

57、區(qū)間的小數(shù)b，使得，使得b與一切的函數(shù)與一切的函數(shù)值都不相等值都不相等. 2任取函數(shù)任取函數(shù)f：AP(A)，構(gòu)造，構(gòu)造BP(A)，使得，使得B與與f的任的任何函數(shù)值都不等何函數(shù)值都不等. 證證 1首先規(guī)定首先規(guī)定0,1中數(shù)的表示中數(shù)的表示. 對(duì)恣意的對(duì)恣意的x0,1, 令令 x = 0.x1x2, 0 xi 9.留意在留意在x的表示式中不允許在某位比如第的表示式中不允許在某位比如第i位為位為0之后有無之后有無數(shù)個(gè)數(shù)個(gè)1的情況的情況. 假設(shè)遇到這種情況假設(shè)遇到這種情況, 那么將那么將x的第的第i位變成位變成1，而后，而后面全是面全是0. 設(shè)設(shè)f： N0,1是從是從N到到0,1的任何一個(gè)函數(shù)的任何

58、一個(gè)函數(shù). 如以下出如以下出f的的一切函數(shù)值：一切函數(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,那么那么y0,1, 且且y與上面列出的任何一個(gè)函數(shù)值都不相等與上面列出的任何一個(gè)函數(shù)值都不相等. 這就推出這就推出yranf, 即即f不是滿射的不是滿射的. 2我們將證明任何函數(shù)我們將證明任何函數(shù)g：AP(A)都不是滿射的都不是滿射的. 設(shè)設(shè)g：AP(A)是從是從A到到P(A)的函數(shù)的函數(shù), 如下構(gòu)造集如下構(gòu)造集合合B： B=x| xAx

59、g(x),那么那么BP(A), 但對(duì)恣意但對(duì)恣意xA都有都有 xB xg(x),從而證明了對(duì)恣意的從而證明了對(duì)恣意的xA都有都有Bg(x). 即即Brang. 留意：根據(jù)這個(gè)定理可以知道留意：根據(jù)這個(gè)定理可以知道NP(N)，N 0,1N. 三優(yōu)勢三優(yōu)勢 1優(yōu)勢定義優(yōu)勢定義定義定義9.21 設(shè)設(shè)A, B是集合是集合, 假設(shè)存在從假設(shè)存在從A到到B的單射函數(shù)的單射函數(shù), 就稱就稱B優(yōu)勢于優(yōu)勢于A, 記作記作A B. 假設(shè)假設(shè)B不是優(yōu)勢于不是優(yōu)勢于A, 那么記作那么記作A B.2設(shè)設(shè)A, B是集合是集合, 假設(shè)假設(shè)A B且且AB, 那么稱那么稱B真優(yōu)勢于真優(yōu)勢于A, 記作記作A B. 假設(shè)假設(shè)B不是

60、真優(yōu)勢于不是真優(yōu)勢于A, 那么記作那么記作A B. 實(shí)例實(shí)例 N N, N R, A P(A), R N N R, A P(A), 但但N N. 2. 優(yōu)勢的性質(zhì)優(yōu)勢的性質(zhì).定理定理9.3 設(shè)設(shè)A, B, C是恣意的集合是恣意的集合, 那么那么 1A A2假設(shè)假設(shè)A B 且且 B A, 那么那么AB3假設(shè)假設(shè)A B 且且 B C, 那么那么A C 證明：略證明：略 例例 證明證明 0,1N0,1).設(shè)設(shè)x0,1), 0.x1x2是是x的二進(jìn)制表示的二進(jìn)制表示. 規(guī)定表示規(guī)定表示式中不允許出現(xiàn)延續(xù)無數(shù)個(gè)式中不允許出現(xiàn)延續(xù)無數(shù)個(gè)1. 對(duì)于對(duì)于x，如下定義，如下定義f：0,1)0,1N, 使得使得f