第二章關(guān)系與映射

1、第二章關(guān)系與映射1 設(shè)集合 A=1,2,3,4, A上的二元關(guān)系 R= x, y | x, y A,且x _ y, 求R的關(guān)系圖與關(guān)系矩陣解 R 二 x,y |x, y A,且x _ y珂 1,1 , 2,1 , 3,1 ,4,1 , 2,2 ,3,2,4,2,3,3,4,3,4,4R的關(guān)系圖如圖2-1所示。圖2-110 0 0Mr1 0 01 1 01 1 1 一22.在由n個(gè)元素組成的集合上，可以有多少種不同的二元關(guān)系？若集合AB的元數(shù)分別為|A| = m,|B|二n，試問從A到B有多少種不同的二元關(guān)系？解因?yàn)橐粋€(gè)由 n個(gè)元素組成的集合A上,任何一個(gè)二元關(guān)系都是A A的子集，而A A=A2

2、中共有n個(gè)元素，取o個(gè)到n個(gè)元素可以組成2n子集，所以有2n個(gè)不同的關(guān)系。 而當(dāng)|A|=m,|B| = n時(shí)，a B這個(gè)全關(guān)系中共有 m n個(gè)元素，取0個(gè)到m n個(gè)元素 組成的子集共有2mn個(gè)，因此從A到B共有2mn種不同的二元關(guān)系。3.設(shè)集合A二1,2,3,令，A上的二元關(guān)系分別為：R 珂 1,1, 1,2, 2,4, 31,3,3S 二1,3, 2,2, 3,2, 4,4試用定義求R *S , S *R , R2, R4 , S ,，并畫出其關(guān)系圖。解 R*S 二1,3,1,2, 2,4, 3,3, 3,2S R= 1,1, 1,3, 2,4, 3,4 r2= 1,1,1,2,1,4,3,

3、1,32,3,3rJ 1,1 , 1,3, 2,1 , 3,3, 4,2 S4 = 2,2, 2,3, 3,1, 4,4 r.SA= 1,1 , 3,1 , 4,2, 4,3 其關(guān)系圖如圖2-2所示。圖2-2說明 1.當(dāng)用定義求復(fù)合關(guān)系時(shí)，先將左關(guān)系中每個(gè)序偶的第二元素作為中介元素， 到右關(guān)系中每個(gè)序偶里找與其相同的第一元素，將這個(gè)元素去掉，用剩余兩個(gè)元素組成新序 偶成為復(fù)合關(guān)系中的元素2.用定義求出的復(fù)合關(guān)系與逆關(guān)系，可以用關(guān)系矩陣來驗(yàn)證其正確性。4. 設(shè)集合A=x, y,z，集合B=a,b,c,d,e，r是集合a上的關(guān)系，S是A,B上的 關(guān)系。R = x,x，x,z , y,x , y,y

4、，z,x，z,y，z,zS = x,a , x,d , y,a , y,c , y , e , z,b, z,d 試驗(yàn)證M（rs）丄=Ms丄M R丄-1011-100101mR =110Ms：-10101證111 一i-01010 一Mrs - M r M S1 0 1 10 0 101 1 0 10 10 1_ 1 1 1 0 1 0 1 0 一110 1010 111_ J 1111 一1 1 11 0 10 1 1T11M（rs）= = Mrs= o 1111011 HYPERLINK l bookmark2 o Current Document MRj10J110001010101Ms

5、010Mr1 二 Ms1 M R丄_110 00 11 0=0101101010J_1 1 11 0 10 1 1M（RS）丄二Ms 丄 MR 丄。5. 圖2-3所示的圖形是集合別寫出對(duì)應(yīng)的關(guān)系矩陣，并說明每種關(guān)系所具有的性質(zhì)（自反性，對(duì)稱性，反對(duì)稱性，傳遞 性）。圖2-31 0 00 1 0解M = . 001 _jRi具有自反性，對(duì)稱性，反對(duì)稱性與傳遞性。1 0 00 1 1Mr2=P 1 1jR2具有對(duì)稱性與傳遞性。0 1 00 0 1Mr3= J 0 0JR3具有反對(duì)稱性。0 0 00 0 0 皿艮八000R4具有對(duì)稱性，反對(duì)稱性與傳遞性。說明本題判斷關(guān)系所具有的性質(zhì)，主要通過已知關(guān)系

6、圖與求出的關(guān)系矩陣進(jìn)行，同時(shí)對(duì)于比較難于判定的傳遞性，都可以一結(jié)合定義進(jìn)行判定。如果不破壞定義所要求的條件， 可以 認(rèn)為滿足定義要求，如對(duì) R4的判定。5. 5.下列關(guān)系是否具有如下性質(zhì)：自反性，對(duì)稱性，反對(duì)稱性，傳遞性？ R 二 x, y |x,y l,x y；R2 = x, x | x _ 0,且x為實(shí)數(shù)；A上的恒等關(guān)系R3 = x,x|x a；A=1,2,3，0上的空關(guān)系o解Ri具有反對(duì)稱性與傳遞性；R2具有反對(duì)稱性；R3具有自反性，對(duì)稱性，反對(duì)稱性與傳遞性；A上的空關(guān)系具有對(duì)稱性，反對(duì)稱性與傳遞性。說明 本題中的前兩個(gè)小題均為無限集合，第小題也未給定集合 A的元數(shù)，這樣不能得到完整的關(guān)

7、系圖與關(guān)系矩陣。但是，可以在草紙上作出部分元素的關(guān)系圖與關(guān)系矩陣進(jìn)行判斷，同時(shí)要充分利用定義要求，便具有該種性質(zhì)。第小題，與上題中題類型一致，只是 元數(shù)大一些，結(jié)果應(yīng)與上題相同。7.設(shè)R和R2是集合A上的任意關(guān)系，試證明或用反例推翻下列論斷：若R1和R2都是自反的，則 R1 R2也是自反的；若R1和R2都是對(duì)稱的，則 R1 R2也是對(duì)稱的；若R1和R2都是反對(duì)稱的，則 R1 R2也是反對(duì)稱的；若R1和R2都是傳遞的，則 R1 R2也是傳遞的。證 論斷正確。對(duì)任意a A，若R和R2都是A上的自反關(guān)系 ，(a,a 護(hù) R,(a,a) R?所以a,aR2，即R1 R2也是自反的。論斷不正確。例如，設(shè)

8、 A 二x,y,z，當(dāng) R = a,b , b,a , c,c, R2 = b,c, c,b，Ri與 R?都是對(duì)稱的，但是R1只2 = a,c , c,b已不是對(duì)稱的，故原論斷不正確。論斷不正確。Ri 門 a,a , b,a , b,c , c,a例如，設(shè)集合A二a,b,c，當(dāng)R2二a,b,b,b b,c,c,cR與R2都是反對(duì)稱的，但是，Ri只2=(a,b)(b,b)(b,c)(c,b已不是反對(duì)稱的，(因?yàn)?b,c)(c,b)w RR2)，故故原論斷不正確。論斷不正確。例如，設(shè)集合 A =a,b,c，當(dāng) Ri 門 a,b , b,c , a,c, R b,c , c,a b,a，Ri R a

9、,a , a,c , b,a 不是傳遞的，因?yàn)?b,a R 只2, a,c R R，而 b, c R1 R2，故原論斷不正確。證畢。8設(shè)R的關(guān)系圖如圖2-4所示，試畫出r(R)，S(R)和t(R)的關(guān)系圖。r(R)dbcas(R)dcabct(R)圖2-5說明 對(duì)于r(R)的關(guān)系圖，因?yàn)閞(R)二R - IA，只要在r的關(guān)系圖上對(duì)沒有自回路的 結(jié)點(diǎn)都添加上自回路，使可以畫成R的自反閉包r(R)的關(guān)系圖。 對(duì)于s(R)的關(guān)系圖，因?yàn)閟(R)二R- R*，只要將R的關(guān)系圖中所有單向弧都畫成雙 向弧，便可以畫成 R的對(duì)稱閉包s(R)的關(guān)系圖。nt(R) = R在 對(duì)于t(R)的關(guān)系圖，當(dāng)R是有限集合

10、上的關(guān)系時(shí)， 畫圖時(shí)，如果R關(guān) 系圖中從結(jié)點(diǎn) x到結(jié)點(diǎn)y有一連串帶箭頭的頭尾相接的弧相連著，則在R的關(guān)系圖上添加一條直接從x到y(tǒng)的弧，便可以畫出t(R)的關(guān)系圖，如圖2-5中t(R)關(guān)系圖上的a與c， a與d，a與e，b與d之間都應(yīng)畫一條有向弧。但是這里要特別注意Gd兩個(gè)結(jié)點(diǎn)，原有兩條c到d與d到c的有向弧，這屬于總結(jié)規(guī)律中的特殊情形，作為結(jié)點(diǎn)c看成是兩個(gè)結(jié)點(diǎn)的重合，所以結(jié)點(diǎn) c處要畫一條自回路，表示從結(jié)點(diǎn)c到結(jié)點(diǎn)c。同理，結(jié)點(diǎn)d也要畫一條自回路。9.設(shè)集合 A =1,2,3,4， a上的關(guān)系 R =(1,2，2,3 )(3,1，4,4求 t(R)和 sr(R)，并寫 出它們的關(guān)系矩陣解因?yàn)?

11、R=1,2,2,3,3,1,4,42所以R 二1,3,2,1 ,3,2,4 ,4R3 =1 ,1 , 2,2,3,3,4,4R4 = 1 ,2,2,3,3,1,4,4t(R) =RR2R3R4= (1 ,1 ,1,2 ,(1,3 ,2 ,1 2,2 ,2,3 ,(3,1 )(3,2 ,3,3 ,4,4 r (R) = R IA=1 ,1 , 1 ,2,2 ,2,2 ,3,3,1, 3,3,4 ,4(r(R)二1,1, 1 ,3,2,1, 2,2,3,2,3,3,4,4sr(R) =r(R) (r(R)二 1,1 , 1,2 , 1 ,3,2 ,1 2 ,2,2,3,3,1 , 3,2,3,3,

12、4 ,4此題t( R)二sr(R),故其關(guān)系矩陣為111011101110M t(R) = M sr(R) = -0001_說明 此題t(R)二sr(R),這純屬偶然情況，一般地，t(R) =sr(R)。設(shè)R是集合A上的二元關(guān)系，若 R是傳遞的，則r(R)也是傳遞的，而s(R)不一定是 傳遞的。證 由 2.4定理1知，R是傳遞的，當(dāng)且僅當(dāng)t(R) =R,故要證r(R)是傳遞的，只需證 明 t(r(R) =r(R)。因?yàn)?t(r(R) =t(RI a) =t(RR0) =R0)(I r)i(2 R0) = u Rj下面用歸納法證明j出當(dāng)i -1時(shí)，左端=R R0 =右端k,(2 R0)k =2

13、Rj假設(shè)當(dāng)i =k時(shí)，命題成立，即) uk., (RuR0)2 = (RuR0)k (R.R0)=uRj (R.R0) 當(dāng) i =k T 時(shí)，i=o由 2.2，習(xí)題7的結(jié)論，可得kR _ _ Rj R0k 1Rjj =0kk廠占(R R0)k；：1Rj丄k 1Rj o:i .-R = t(R) 一 Ia = R- lA=r(R)R j故 t(r(R)十jMR即t(r(R)二r(R)，故r(R)是傳遞的。s(R)不一定是傳遞的。例如 設(shè)集合A二a,b,c上的二元關(guān)系 R，當(dāng)R二 a,b , b,c , a,c，r是傳遞的，而 s(R) =R 一 R= a,b , a,c , b,a , b,c

14、, c,a , c,b時(shí)，s(R)已經(jīng)不是傳遞的。 證畢。設(shè)R是集合A上的二元關(guān)系，判斷下列命題是否正確？ rt(R) =tr(R)； ts(R) =st(R)。解命題正確。由于 tr(R) =t(R I a)， rt(R) =t(R)I a，并利用 Ra = 1 a R，以及對(duì)于一切n自然數(shù)n, iA=Ia，用數(shù)學(xué)歸納法的可以證明(r-Ia)a-R)，所以tr(R) =t(r(R) =t(R_. Ia)=(R lA) 一(R- l A)? 一 (- Ia)3 -=IA - R - R? - R3 -=Ia - t(R)=r(t(R) = rt(R)。 命題不正確?？梢宰C明 st(R)匚ts(

15、R)。首先證明，當(dāng) Ri 二 R?時(shí)，則 s(Ri) = s(R2)且t(Ri) =t(R2)。這是因?yàn)?，s(Ri)是對(duì)稱的且s(Ri)二R1，但是R1=R?，故s(RJ二R?。由s(R2)的定義，s(R?)是包含R?的最小對(duì)稱關(guān)系，故s(R)二s(R?)。同理可證， t(RO 二 t(R2)。由對(duì)稱閉包定義，有 S(R)二R，利用上面證過的結(jié)論：ts(R)二 t(R),sts(R)二 st(R)再由教材P58例5(2)可知，s(R)是對(duì)稱的，ts(R)也是對(duì)稱的，又根據(jù) 2.4定理1中(2)， ts( R)是對(duì)稱的，當(dāng)且僅當(dāng) sts(R) =ts(R)，因此 ts(R)二 st(R)，即 s

16、t(R)三 ts(R)。st(R)二 ts(R)不一定成立。例如，集合A Ha,b,c上關(guān)系，R 珂 a,b ,b,c，則 R2 珂 a,c, R3 二,R 珂 b,a ,c,b，t(R) = R 一 R2 一 R3= a,b , b,c , a,c(t(R)= b,a ,c,b, c,as(t(R) (R) 一 t(R)，= a,b ,a,c, b,a b,c ,c,a, c,b而 s(R)二R 一 RJ = a,b , b,a , b,c,c,bs(R)2 a,a , a,c , b,b , c,a , c,c(s(R)3 二a,b ,b,c ,b,a, c,b。t(s(R) =s(R)

17、一 s(R)2 一 s(R)3珂 a,a , a ,b , a ,c , b,a , b ,b , b ,c , c,a , c ,b , c ,c故 s(t(R)不包含 t(s(R)設(shè)R|和R2是集合A上的二兀關(guān)系，試判斷下列命題是否正確？ r(R 一 R2)寸侃)rR)； s(RR2) =s(Ri) s(R2)； t( R - R2 ) - t(Rlt(R2 )。解命題正確。因?yàn)?r(Ri .JR2)=RiR2j a = Ri.J I a1R2- I a = r (Ri)r(R2)。命題正確。首先證明任取a,b - (Ri _ R2)，當(dāng)且僅當(dāng)b，a R &，當(dāng)且僅當(dāng)b，a R或b,a &

18、, 當(dāng)且僅當(dāng)a，b,或a，bR2J ,當(dāng)且僅當(dāng)a，bR R2 1 ,故證得 TOC o 1-5 h z .i丄 _. i(Ri _ R2 ) = Ri R2而 S( R - R2 ) (Ri - R2) - (R - R2 ) i . i=Ri _ R2 _ Ri - R2 i i=(R- _ Ri ) - (R2 -)二 s(R) 一 sR)命題不正確，可以證明t(Ri - R2) = t(Ri) t(R2)。因?yàn)镽i - R2 - Ri ,利用前一例題中證明中證過的結(jié)論：當(dāng)Ri二R2時(shí)，則t(Ri )二 t(R2)，有 t (Ri - R2)二 t (Ri )同理，Ri - R R2，有

19、t(R - R2) JR)故 t(Ri 一 R2) =t(Ri) _ t(R2)t(Ri) 一 t(R2)=t(Ri 一 R2)不一定成立。例如，設(shè)集合A二a,b,c , a上的二元關(guān)系Ri和R2分別為R = a,b , b,cR2 = a,c , c,b則Ri2 = a,cRi3 二R；珂 a,bR；二t(RJ 二尺 一 Ri2 - Ri；= a,b , a,c , b,ct(R2)譏-R； - R；二 a,b , a,c ,c,b t(Ri) t(R2)- a,b , a,c , b,c , c,b而 Ri _ R2= a,b ,a,c ,b,c, c,b(Ri R2) = a,c , a

20、,b , b,b , c,c(Ri 一 R2)3= a,b , a,c ,b,c,c,b2 3t (RiR2) = (RiR2)-(Ri-R2)-(Ri-R2)顯然，= a,b , a,c , b,b , b,c , c,b , c,c t(R1) _. t(R2)不包含 t(R1R2)13.設(shè)集合A二a,b,c,d,e , a上的關(guān)系關(guān)于等價(jià)關(guān)系 R的等價(jià)類為:Mi =a，b,c, M2 =d,e，試求:等價(jià)關(guān)系R :寫出關(guān)系矩陣M r ；畫出關(guān)系圖。解 因?yàn)榈葍r(jià)關(guān)系R具有自反性，所以Ia = a,a , b,b , c , c, d,d ,e,e。Ia R又因?yàn)?a,b,c在同一個(gè)等價(jià)類中

21、, 所以( a,b), (b,a), (a,c), (c,a)(b,c), (c,b) 5 R再因?yàn)閐,e在同一個(gè)等價(jià)類中，所以 (d,e),(e,d) 乂 R因此 R =1A - (a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(d,e),(e,d)。圖2-611101110M r = li110000114.設(shè)Ri和R2是非空集合A上的等價(jià)關(guān)系，下列各式哪些是 A上的等價(jià)關(guān)系？哪些不是A上的等價(jià)關(guān)系？舉例說明： A A - Ri ； Ri - R2 ；2 R ； r(R1 - R2)； Rl R2解 A A-Ri不是A上的等價(jià)關(guān)系。例如，設(shè)集合 A二a,b , A上

22、的關(guān)系R a,a ,b,bA A = a, a ,a,b ,b,a, b,bA A-R 二a,b , b,a不具A A-Ri不是A上的等價(jià)關(guān)系。R1 -R2不是A上的等價(jià)關(guān)系。例如，設(shè)集合A二a，b，C,R = a,a , a,b , b ,a , b,b , b,c , c ,b , c,cR2 - a,a , b,b , c ,cR -R2 = a,b , b ,a , b,c , c,b不具有自反性和傳遞性，因此Ri -r2不是A上的等 價(jià)關(guān)系。r2是集合A上的等價(jià)關(guān)系。2 因?yàn)镽是集合A上的等價(jià)關(guān)系，任取A ,有a，a A ,而且有a,a Ri只1二Ri , 所以R2在集合A上是自反的

23、。任取a,bA,若a,b R2,則存在A,使得 a,c R且c,b R,因?yàn)镽i是2 2 對(duì)稱的，有c，a 尺且b,c 尺，于是b，a Ri ,所以Ri是對(duì)稱的。任取a,b,cA,若a,b R2且b,c R；,貝y存在d,eA ,分別使得dRi,且 d,b ReR ,且 e,cRi由于Ri是傳遞的，元素 a與b之間以d為中介元素，b與c之間以e為中介元素，有a,bRi , b,c R ,再根據(jù)關(guān)系的復(fù)合，有 a,c R Ri =Ri2所以Ri2是可傳遞的，2故R是集合A上的等價(jià)關(guān)系r(R1 -R2)不是集合A上的等價(jià)關(guān)系。由題所舉例子，R1 -R2 二 a,b , b,a , b,c ,c,b

24、有 r(R1 iR2)=(Rli R2) - I A鞏 a, a , a,b , b,a , b,b , b,c , c,b , c , cr(Ri -R2)不具有傳遞性，所以r(Ri -R2)不是集合A上的等價(jià)關(guān)系。Ri R2是集合A上的等價(jià)關(guān)系。對(duì)于任意aA，有a,a R且a,aR2，故a,aRi R2，因此Ri R2是自反的任取a，bA，若(a，b)Ri,Ri是對(duì)稱的，必有(b,a)，Ri，而R2是自反的，對(duì)于a,b A，有(a,a)R2,(b,b)R2，由(a,b)Ri與(b,b)R2,得(a,b)RiR2,由(b,a)R|與(a, a)，R2，得(b,a)，RiR2,因此RiR2 是

25、對(duì)稱的。任取a,b,cA，若(a,b) Ri, (b,c) Ri , Ri是傳遞的，必有(a,c) Ri。由于R2是自反的，由(a,b) R 與(b,b)FR，得(a, b) R R?(b,c)R1 與(c,c)R?，得(b,c)Ri R2 (a,c)乏 Ri 與(c,c)e R2,得(a,c) e R R故Ri R2是集合A上的等價(jià)關(guān)系。15.設(shè)集合A=1,2,3,4，A上的四個(gè)半序關(guān)系分別為：R =( 1,1), (1,2), (1,3), (1,4), (2,2),(2,3), (3,3), (4,4)R2 二(1,1), (1,2), (2,2), (3,1), (3,2), (3,3

26、), (4,1), (4,2), (4,3), (4,4)R3 二(1,1),(2,2),(2,4),(3,1),(3,3),(4,4)哪個(gè)具有良序關(guān)系?2-7所示。R =(1,1), (1,2), (1,3), (1,4), (2,2),(2,3),(2,4), (3,3), (3,4),(4,4) 試分別畫出它們的哈斯圖，并判斷起其中哪個(gè)具有序關(guān)系？ 解 集合上的半序關(guān)系的哈斯圖如圖RiR2Ri圖2-7其中關(guān)系圖R2與所有元素都排在鏈上，即任意兩個(gè)元素之間都有關(guān)系存在，所以R2和&都是序關(guān)系。由于 R2和R4中每一非空子集都有最小元，所以也都是良序關(guān)系。說明此題中的阿拉伯?dāng)?shù)字已經(jīng)失去了它們

27、在實(shí)數(shù)集中的大小關(guān)系，應(yīng)該把它們看成四個(gè)不同符號(hào)。16.設(shè)集合A珂2,3,4,6,8,12,24，R為A上的整除關(guān)系。畫出半序集（A,R）的哈斯圖；寫出集合 A中的最大元，最小元，極大元，極小元；寫出A的子集B二2,3,6,12的上界，下界，最小上界，最大下界。解 半序集（A,R）的哈斯圖如圖2-8所示。81263圖2-8集合A中的最大兀是24,無最小兀，極大兀也是24,極小兀是2和3。集合B的上界是12與24,無下界，最小上界是12,無最大下界說明最大元與極大元的區(qū)別在于，最大元是一個(gè)集合中的最大”者，若有則是唯一的；而極大元?jiǎng)t是集合中的元素沒有比它“大”的，可能不唯一。對(duì)于最小元與極小元具

28、有同樣情況。這里把“大”字用弓I號(hào)引起來，因?yàn)閷?shí)際上不一定在研究數(shù)與數(shù)之間的大小關(guān)系，而是 在研究某種半序關(guān)系。17. 設(shè)R是集合A上的半序關(guān)系，且B A，試證明RRr（B B）是b上的半序關(guān) 系。證 對(duì)于B任意，因?yàn)锽 A，故A，而R是A上的半序關(guān)系，貝U R在A上具有 自反性，于是（a,a）R，且（a,a）B B，這樣可得（a,a） R 一 （B B）二 R即R 在B上是自反的。任取a,b B，且a = b，若（a,b） R ，可得（a,b） R且（a,b）B B，因?yàn)閞具有 反對(duì)稱性，必有（b, ab R，故（b, aV R,即R在B上具有反對(duì)稱性。對(duì)于任意a，b,cB ,因?yàn)锽 A ,

29、故a,b,cA ,若（a,b） R且（b,c） R而 R=R-（B B），故（a,b） R 一 （B B）,（b,c） R 一 （B B），由（a,b） R 一 （B B）, 可得（a,b） R且（a,b）B B，即當(dāng)（a,b）R同時(shí)R且b R。同理，當(dāng)（b,c） R - （B B），也有（b,c） R 同時(shí) b R 且 c R。因?yàn)镽在A上具有傳遞性，由（a,b） R且（b,c） R，得（a,c），R。又a,b,c，B，故 （a,c）B B，因此（a,c）R- （B B）二R：r，滿足傳遞性，所以R是B上的半序關(guān) 系。18 設(shè)集合 A 二0,1,2,3,4,5, B 二% ,映射二定義為二(

30、2n) =0,；(2 n 1) =1,( n =0,1,2),C =2,3解 因?yàn)槎?A B , A 二O，1,2,3,4,5, B 二0,1，當(dāng) aA時(shí)(2n)=0當(dāng)門=0,1,2時(shí)，a = 0,2,4cr (a)=呼(2n+1)=1當(dāng)門=0,1,2時(shí)，a=1,3,5而 C 二2,3A，設(shè)映射.:C B二(2n) =0二(2n 1) = 1 故皿(獷1 即 .(2) = 0, .(3) = 1t (a) = *此時(shí)n只取1, a = 2此時(shí)n也只取1, a =3a = 2a = 3為 二 在 C 上 的 限 制 二(0) = 0,二(2) = 0,；(4) = 0,二二仁=仁二1為.在A上的

31、擴(kuò)充。設(shè)A和B是兩個(gè)有限集合，它們的元數(shù)都是n，則二:A B是單射的充分必要條件是二為滿射證 必要性，當(dāng)-是單射時(shí)，二(A)的元數(shù)是n，而匚(A) b,b的元數(shù)也是 n，故 二(A) =B，因此c : A B是滿射。充分性，若二:A B為滿射時(shí)，有 匚(A) = B，則；(A)的元數(shù)為n，A的元數(shù)也是 n，n個(gè)原象對(duì)應(yīng)n個(gè)象，即不同元素對(duì)應(yīng)不同的象，因此二是a到B的單射。設(shè) R 為實(shí)數(shù)集，二：R R、Rf(X,y) =x y,又.:R R R, (x,y x y,試證 明二和都是滿射，而不是單射。證 對(duì)于任意a R，可以使x y成立的x, y有無數(shù)對(duì)，且(x, y) R R，也就是說值域R中每個(gè)元素都有無數(shù)原象在R R中，所以二是滿射，而不是單射。對(duì)于任意aR，能使a=xy成立的x, y也不止一對(duì)實(shí)數(shù)存在。例如a=6，而 x=2, y=3，或x=3,y=2, ，即象集中每一元素都有原象， 而且原象不唯一，所以是 滿射，而不是單射。證畢