離散數(shù)學(xué)function.ppt

,離散數(shù)學(xué),2,第四章 函數(shù),4-1函數(shù)的概念 4-2逆函數(shù)和復(fù)合函數(shù) 4-4基數(shù)的概念 4-5可數(shù)集與不可數(shù)集 4-6基數(shù)的比較,3,第四章 函數(shù),4-1函數(shù)的概念 4-2逆函數(shù)和復(fù)合函數(shù) 4-4基數(shù)的概念 4-5可數(shù)集與不可數(shù)集 4-6基數(shù)的比較,4,函數(shù)的概念,定義4-1.1 設(shè)X 和Y是任何兩個(gè)集合。而 f 是X 到Y(jié)的一個(gè)關(guān)系，如果對于每一個(gè)xX ，有唯一的 yY，使得x,yf ，稱關(guān)系 f 為函數(shù)，記作：f:XY 或 概念：自變量、映像、定義域和值域 注意： 1 函數(shù)與關(guān)系 2 函數(shù)亦稱映射或變換。習(xí)慣用小寫英文 f,g, 表示函數(shù)符。 3 在x,y f 中，f 的前域就是函數(shù)的定義域,記作dom f (或Df ) 顯然由定義可知： Df=x xX (y)(yY y = f (x) =X,5,4 f 的值域記為 ran f (或Rf)， 即： Rf=yyY (x)(xX y = f (x) 。 問題：ran f=Y? 5 映像集：f(X)=ran f,6,實(shí)例,例1 設(shè) X=1,5,p,張明，Y=2,q,7,9,G,f = 1,2 , 5,q , p,7, 張明, G 。求：Dom f和ran f 例2 判別下列關(guān)系中哪個(gè)能構(gòu)成函數(shù) 1 f = x1,x2x1,x2 N ,且x1+x210。 2 f = y1,y2y1,y2 R,y22 = y1 。 3 f = x1,x2x1,x2 N ,x2為小于x1的素?cái)?shù)個(gè)數(shù) 。,7,函數(shù)相等,定義4-1.2 (函數(shù)相等)設(shè)函數(shù) f :AB, g :CD,若A=C,B=D且對一切 x A ,有 f (x) = g(x)，則稱函數(shù) f 和 g 相等。記為 f = g。 問題：函數(shù)相等的兩個(gè)要素？ 問題：對于有限的集合X和Y，并且|X|=m，|Y|=n： 1 X到Y(jié)的關(guān)系有多少個(gè)？ 2 X到Y(jié)的函數(shù)有多少個(gè)？ 概念：符號YX 表示從 X 到 Y 的所有函數(shù)的集合，甚 至當(dāng) X 和 Y 是無限集時(shí)，也用這個(gè)符號。,8,滿射函數(shù),定義4-1.3 對于f :XY 的映射中，若ran f = Y，即Y 的每一個(gè)元素是 X 中一個(gè)或多個(gè)元素的像點(diǎn)，則稱這個(gè)映射為滿射(或到上映射)。 問題：如何說明或證明一個(gè)函數(shù)是滿射的，請用謂詞公式進(jìn)行說明。 例1 A =a,b,c,d,B =1,2,3如果 f 為A 到 B 的函數(shù),且f (a) = 1, f (b) = 1, f (c) = 3, f (d) = 2 ，則f 是A 到B 上的滿射。,9,入射函數(shù),定義4-1.4 從 X 到Y(jié)的映射,X中沒有兩個(gè)元素有相同的像，則稱這個(gè)映射為入射(或一對一映射)。 問題：1 如何說明或證明一個(gè)函數(shù)是入射的，請用謂詞公式進(jìn)行說明。 2 建立在X和Y上的滿射及雙射函數(shù)個(gè)數(shù)與集合大小的關(guān)系。 例 函數(shù)f:a,b2,4,6, f (a) = 2, f (b) = 6 則 f 是入射，但不是滿射。,10,雙射函數(shù),定義4-1.5 從 X 到 Y 的一個(gè)映射，若既是滿射又是入射，則稱這個(gè)映射是雙射(或一一對應(yīng)映射)。 例 函數(shù) f:a,b1,2, f (a) = 1, f (b) = 2，則 f 為雙射。 例 在下圖中,(a),(c)是滿射,(b),(c)是入射,(c)是雙射, (d)非滿射又非入射。,(a) (b) (c) (d),11,定理4-1.1 令 X和 Y 為有限集，若X和Y的元素個(gè)數(shù)相同，即|X| = |Y| ，則f :XY 是入射的，iff 它是一個(gè)滿射。 證明： 注意：此定理僅在有限集的情況下才能成立，在無限集上不一定成立。如：f:II , f (x) = 2x,這里顯然 f 是一個(gè)入射，而不是滿射。,12,第四章 函數(shù),4-1函數(shù)的概念 4-2逆函數(shù)和復(fù)合函數(shù) 4-4基數(shù)的概念 4-5可數(shù)集與不可數(shù)集 4-6基數(shù)的比較,13,逆函數(shù),問題：給定一個(gè)關(guān)系 R ，顛倒 R 的所有序偶，得到逆關(guān)系Rc 。給定一個(gè)函數(shù) f ，顛倒 f 的所有序偶，得到的逆關(guān)系 f c 是函數(shù)嗎？如果不是，在什么情況下其是逆函數(shù)？,14,定理4-2.1 設(shè)f :XY 是一雙射函數(shù)，則f c 是YX 的雙射函數(shù)。 證明思路：分兩步，（1）證f c 為函數(shù)；（2）證f c 為雙射) 定義4-2.1 設(shè)f :XY 是一雙射函數(shù)，稱YX的雙射函數(shù)f c為f 的逆函數(shù)，記作f -1 。,15,復(fù)合函數(shù),定義4-2.2 設(shè)函數(shù)f : XY ,g: WZ ，若f (X) W ，則g f=|xXzZ(y)(yYy=f (x)z=g(y) 稱g在函數(shù)f 的左邊可復(fù)合。 注意： 1、關(guān)系的復(fù)合與函數(shù)復(fù)合在記法上的區(qū)別。 2、若ran f dom g 這個(gè)條件不成立，則定義g f 為空。 3、定理4-2.3兩個(gè)函數(shù)的復(fù)合是一個(gè)函數(shù)。 4、定義4-2.2中，當(dāng)W=Y是，則函數(shù)g f 稱為復(fù)合函數(shù)，或稱 g f 為g對 f 的左復(fù)合。 5、g f(x) = g(f(x) 。 6、由于函數(shù)的復(fù)合仍為函數(shù)，故可推廣到有限個(gè)函數(shù)的復(fù)合。,16,例 f :RR, g:RR, h :RR, f(x)=x+2,g(x)=x-2,h(x)=3x 問題：函數(shù)的復(fù)合滿足可結(jié)合性嗎？ 定理4-2.3 令g f 是一個(gè)復(fù)合函數(shù)。 a)若g 和 f 是滿射，則g f是滿射的。 b)若g 和 f 是入射，則g f 是入射的。 c)若g 和 f 是雙射，則g f 是雙射的。 證明思路：利用滿射、入射和雙射的定義直接證明,17,常函數(shù)和恒等函數(shù),定義4-2.3 函數(shù) f :XY 叫做常函數(shù)，如果存在某個(gè)y0Y ， 對于每個(gè)xX都有 f (x) = y0，即f (X) =y0 。 定義4-2.4 如果IX =x,x|xX，則稱函數(shù)IX:XX 為恒等函數(shù)。 定理4-2.4 設(shè)函數(shù) f :XY ，則 f = f IX = IY f 。 證明思路：證明定義域相同，對應(yīng)關(guān)系相同。 定理4-2.5 如果函數(shù)f :XY 有逆函數(shù)f -1:YX ， f-1 f = IX , f f1 = IY。,18,逆函數(shù)的逆函數(shù)與復(fù)合函數(shù)的逆函數(shù),定理4-2.6 若f : XY 是雙射函數(shù)，則( f 1)1 = f 。 定理4-2.7 若f :XY, g :YZ 均為雙射，則(g f )-1 = f -1 g -1 。 證明： 因?yàn)閒, g為雙射，由定理4-2.3知g f 是雙射。 由逆函數(shù)定義可知：f 1 =f c, g 1 =g c , (g f )-1= (g f )c。再由復(fù)合關(guān)系逆的性質(zhì)知：( g f) c =f c gc。 所以 (g f )-1= (g f )c = f c g c= f -1 g -1 。,19,第四章 函數(shù),4-1函數(shù)的概念 4-2逆函數(shù)和復(fù)合函數(shù) 4-4基數(shù)的概念 4-5可數(shù)集與不可數(shù)集 4-6基數(shù)的比較,20,集合的大小,有限集合的大小 無限集合的大小 問題：如何比較兩個(gè)集合的大??？,21,G.Peano公理,定義4-4.1設(shè)A是任意集合，A的后繼集定義為集合： A+ = AA。 (G.Peano公理)自然數(shù)N是如下集合： (1)0 N (其中0 = )。 (2)如果n N ，那么 n+ N ，(其中n = n+ n )。 (3)如果一個(gè)子集S N具有性質(zhì)： a. 0 S ; b. 如果n S ，有n+ S ，則S = N 。,22,說明： 1 上述自然數(shù)定義稱為歸納定義。 其中(1)為基礎(chǔ)，(2)為歸納，(3)為極小性(指明了自然數(shù)系統(tǒng) 是滿足公理(1)和(2)的最小集合)。 2 從N的定義可見，任意一個(gè)自然數(shù)可看作是一個(gè)集合的名。 問題：自然數(shù)系統(tǒng)是什么呢？,23,等勢集合,定義4-4.2 給定兩個(gè)集合P與Q，若對P中每個(gè)不同元素，與Q中每個(gè)元素可以分別兩兩成對，則說P的元素與Q的元素間存在著一一對應(yīng)。 定義4-4.3 iff 集合A的元素與集合B的元素之間存在著一一對應(yīng)，集合A與集合B稱為是等勢的(或稱同濃的)，記作AB 。,24,實(shí)例,例1：N1=x|x=2*i, i N，證明N1N 例2：設(shè)R為實(shí)數(shù)集合，S =x|xR0x1。 證明： RS 。 證明：令f : RS ，f (x) =(arctg x/ )+1/2 。 顯然 f : RS 是一個(gè)雙射函數(shù)。故 RS 。,25,定理4-4.1 (等勢的性質(zhì))在集合族上等勢關(guān)系是一個(gè)等 價(jià)關(guān)系。 證明：設(shè)S為集合族。 1)對于AS，可作恒等函數(shù) IA :AA, IA(x) = x。顯然IA:AA 為一個(gè)雙射函數(shù)。故AA 。即等勢關(guān)系為自反關(guān)系。 2)對于 A,BS ，如果AB ，那么存在雙射函數(shù) f :AB 。由定理4-2.1可知 f -1:BA 存在，且為雙射函數(shù)，故BA ，即等勢關(guān)系為對稱關(guān)系。 3)對于 A,B,CS ，如果AB,BC那么存在 f : AB, g : BC均為雙射函數(shù)。由定理4-2.3可知 g f :AC 為雙射函數(shù)， 故AC ，即等勢關(guān)系為一個(gè)傳遞關(guān)系。 由(1)、(2)、(3)可知集合族上的等勢關(guān)系是一個(gè)等價(jià)關(guān)系。 ,26,有限集合和無限集合,定義4-4.4 如果有一個(gè)從集合0，1，n-1到集合A的雙射函數(shù)，則稱集合A是有限的；如果集合A不是有限的，則它是無限的。 概念： Nn =0,1,2, ,n-1稱為N的初始段，Nn 可用于證明集合N為有限集。故Nn 又作為一個(gè)“標(biāo)準(zhǔn)集合”。 定理4-4.2 自然數(shù)集N是無限的。 證明：,27,基數(shù)-無限集合的大小,定義4-4.5 所有與集合A等勢的集合所組成的集合，叫做集合A的基數(shù)，記作 KA (或 、 |A| ) 說明： 1 、定義4-4.5是由G.弗雷格與B.A.W.羅素分別在1884年與1902年給 出的。但在ZFC系統(tǒng)中不能證明它構(gòu)成一個(gè)集合。按照康托爾的原意，認(rèn)為集合A的基數(shù)是量詞抽象的結(jié)果，一次從A 的元素中抽去質(zhì)的特性，另一次是抽去元素之間的次序關(guān)系。A 的基數(shù)是一切與A具有等勢關(guān)系集的共同特征。故用或 |A| 中的兩個(gè)杠表示二次抽象。 2、根據(jù)康托爾的原意，通常將基數(shù)定義描述為：度量集合大小的 量叫基數(shù)(或勢)。如 KNn =n 。約定K = 0 。故有限集合的基 數(shù)為集合所含元素的個(gè)數(shù)。如果 A,B 為無限集合，并且AB ，則 有KA = KB 。,28,實(shí)例,證明區(qū)間0,1 與（0,1）基數(shù)相同。 證明：設(shè) 定義 f : 0,1 （0,1）, 顯然 f 是0,1 到（0,1）上的雙射函數(shù)。（如下圖所示）。 ,29,第四章 函數(shù),4-1函數(shù)的概念 4-2逆函數(shù)和復(fù)合函數(shù) 4-4基數(shù)的概念 4-5可數(shù)集與不可數(shù)集 4-6基數(shù)的比較,30,可數(shù)集,說明： N 是無限集，但是并非所有無限集都可以與 N 等勢。故無限集合之間也是有大小的。 定義4-5.1 與自然數(shù)集合等勢的任意集合稱為可數(shù)的，可數(shù)集合的基數(shù)為 。即KN = 例：A =1,4,9,16, ,n2, ，B =1,8,27,64, ,n3, C =2,5,10,17, ,n2+1, ，D =1, 12 , 13 , , 1n , 均為可數(shù)集，且 KA = KB = K C = KD = 。,31,定理4-5.1 A為可數(shù)集的充分必要條件是A可以排列成A =a1,a2, .,an, 的形式。 證明：如果A=a1,a2, .,an, ，那么存在 f : AN 且f (an) = n-1 (n = 1,2, ) f 為雙射函數(shù)。故 AN ，即 A 為可數(shù)集。 反之，如果 A 可數(shù)，那么 AN ，則存在雙射函數(shù) f : NA , 令 f (n) = an+1 (n = 0,1,2, ) 故 A=a1,a2, .,an, 。 說明：此定理可以作為A 是可數(shù)集的一個(gè)等價(jià)定義，也是證明 A 可數(shù)的一個(gè)實(shí)用方法。,32,定理4-5.2 任一無限集必含有可數(shù)子集。 證明： 定理4-5.3 任一無限集必與其某一個(gè)真子集等勢。 證明：設(shè) M 為無限集，由定理4-5.2可知A=a1,a2, .,an, , 且A M。設(shè) M-A = B ，定義函數(shù) f: MM-a1，且 f (x) = an+1( x = an , n = 1,2, ), f (x) = x(xB) 顯然 M-a1M，且 f 為雙射函數(shù)。,33,說明： 1、定理4-5.3中某一個(gè)真子集不是指所有真子集，如真子集為有限集，則有限集與無限集是不可能等勢的。 2、可以證明 A 有限集是不滿足定理4-5.3的（如何證明）。故有 A 無限集當(dāng)且僅當(dāng)與其某一個(gè)真子集等勢，可以作為無限集的等價(jià)定義。,34,定理4-5.4 可數(shù)集的任何無限子集都是可數(shù)的。 證明：設(shè) A 是可數(shù)集合，則 A=a1,a2, .,an, ,B A 為一無限子集，將 A 中的元素從 a1開始，向后檢查，不斷地刪去不在 B 中的元素，則得到新的一列 ai1,ai2, ,ain, ,故B= ai1,ai2, ,ain, ，即 B 是可數(shù)的.,35,即 S = a11,a21,a11,a13,a22,a31,a41,a32, ，所以 S 是可數(shù)集。,定理4-5.5 可數(shù)個(gè)兩兩不相交的可數(shù)集合的并集，仍然是一可數(shù)集。 證明：（用排隊(duì)的方法證明） 設(shè)可數(shù)個(gè)可數(shù)集分別表示為： S1 =a11,a12,a13, ,a1n, S2 =a21,a22,a23, ,a2n, S3 =a31,a32,a33, ,a3n, 令S =S1 S2 = ，對 S 的元素作如下排列：,36,說明： 1、定理4-5.5中 S 中的元素的排列方法是不唯一的。 2、利用定理4-5.4和定理4-5.5可以證明：可數(shù)個(gè)可數(shù)集的并是可數(shù)的。（如何證明）,37,定理4-5.6 ：NN是可數(shù)集。 證明： 令S1 =, , S2 = , , S3 = , , 則NN= 由定理4-5.5可知 NN是可數(shù)集。 說明：注意此種證明方法與教材上方法的差異,38,定理4-5.7 有理數(shù)集 Q 為可數(shù)集。（用排隊(duì)法證明） 證明：一切有理數(shù)均呈n/m(n,mN,m0) ?，F(xiàn)將所有n/m 按下列次序排列： （1）正分?jǐn)?shù)按其分子、分母之和的大小順序排列：從小到大。 （2）正分?jǐn)?shù)的分子、分母之和相同者按分子大小順序排列： 從大到小。 （3）將0放在首位，與正分?jǐn)?shù)具有相同形式的負(fù)分?jǐn)?shù)排于正分?jǐn)?shù)之后。按照上述規(guī)則可得： 0,1/1,-1/1,2/1,-2/1,1/2,-1/2,3/1,-3/12/2,-2/2,1/3,-1/3, 故所有呈n/m 狀的數(shù)所組成的集合為可數(shù)集，而 Q 為其無限子集，由定理4-5.4知 Q為可數(shù)集。,39,不可數(shù)的無限集,概念：連續(xù)統(tǒng) 并非所有的無限集均為可數(shù)集。選取（0,1）作為新的“標(biāo)準(zhǔn)集合”，記（0,1）的基數(shù)為 ，如果 A(0,1) ，那么KA = 。 也稱作連續(xù)統(tǒng)的勢。,40,定理4-5.8 實(shí)數(shù)集R是不可數(shù)的。（用反證法證明） 證明：,41,關(guān)于定理4-5.8的證明幾點(diǎn)說明： 1、僅由 0,1 構(gòu)成的無限序列集合是不可數(shù)的。 即 T=a0a1a2an|nN,an=0or1為不可數(shù)集。 2、將(1)推廣由 0,1,2, ,9 構(gòu)成的無限序列集合也是不可數(shù)集。 3、S =(x,y)|x.yR0x,y1 為不可數(shù)集。 (提示：構(gòu)作f:S(0,1) 為雙射函數(shù) ) 4、證明：RRR = Rn 是不可數(shù)集。,42,第四章 函數(shù),4-1函數(shù)的概念 4-2逆函數(shù)和復(fù)合函數(shù) 4-4基數(shù)的概念 4-5可數(shù)集與不可數(shù)集 4-6基數(shù)的比較,43,基數(shù)的比較,說明：通過構(gòu)造雙射函數(shù)證明集合等勢需要高度的技巧性。 定義4-6.1 若從集合A到集合B存在一個(gè)入射，則稱A的基數(shù)不大于B的基數(shù)，記作 KA KB 。若從A到B存在一個(gè)入射，但不存在雙射，則稱A的基數(shù)小于B的基數(shù)，記作KA KB 。,44,定理4-6.1