离散数学(16)

《离散数学(16)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章函数4.2特殊函数类本节介绍具有一定性质的函数,因为今后应用中遇到最多的正是它们.定义4.2―1设f是从X到Y的函数.(a)如果f(X)=Y,那么f是满射的(每个Y都有原像)(b)如果x≠x΄蕴含着f(x)≠f(x΄)(即f(x)=f(x΄),时1那么x=x΄),那么f是单射的(不能多对一).(c)如果f是满射的且是单射的(一对一和映到的),那么f是双射的.具有这些性质的函数分别叫做满射函数,单射函数和双射函数。如果f:X→Y是满射的,那么每一元素y∈Y是在f的象中,或者说Y等于f的值域。2如果f是单射的,那么前域不同的元素映射到陪域不同的元素。如果f是双射的,

2、那么Y的每一元素y是且仅是X的某个元素x的映象,常称双射为一一对应.图4.2―1用以说明定义4.2―1中各类函数的概念,3函数的前域和陪域分别用左边的和右边的一列小圆点表示。图4.2―14(a)是单射的但不满射,(b)是满射的但不单射,(c)是双射的。显然,如果f是满射的,那么至少有一条弧终止于陪域的每一个元素.如果f是单射的,那么终止于陪域的每一元素的弧不多于一条。如果f是双射的,那么有且只有一条弧终止于陪域的每一元素。5例:证明函数f:RR,f(x)=2x－15是双射.证明:取yR令y=2x－15得到而代入函数有说明每个象都能找到原象,所以函数是满射的.再取x

3、1,x2R,并且x1x2,则:f(x1)－f(x2)=2(x1－x2)0所以函数是单射的,故函数是双射的.6例1(a)皮亚诺函数S:N→N,S(n)=n+1是单射函数但不满射,S的映象是N的真子集{1,2,…}。(b)g:［0,1］→［a,b］,这里a＜b,g(x)=(b－a)x+a是双射函数。(c)h:R→R,f(x)=x3+2x2是满射函数但不单射.因为每一水平线横截图形至少一次,而有些地方多于一次(参看图4.2―2)。7y可能有多个x值对应同一个值y.图4.2―28定理4.2―1设g:X→Y和f:Y→Z是函数,fg是合成函数。(a)如果f和g是满射的,那么

4、fg是满射的。(b)如果f和g是单射的,那么fg是单射的。(c)如果f和g是双射的,那么fg是双射的。证(a)任取z∈Z,因f是满射的,存在y∈Y,9使f(y)=z;又因g是满射的,存在x∈X,使g(x)=y。于是fg(x)=f(g(x))=f(y)=z,所以z∈fg(X)。因为z是任意的,这就证明了(a)部分。(b)设x1,x2是X的两个不同的元素,因为g是单射的,推得g(x1)≠g(x2);又因f是单射的且g(x1)≠g(x2),推得fg(x1)≠fg(x2).所以,x1≠x2蕴含着fg(x1)≠fg(x2).这证明了(b)部分.10(c)因为f和g是双射的,它们

5、都是满射和单射的.从(a)和(b)得fg是满射和单射的,所以是双射的。证毕。例2(a)设E是偶整数集合,M是奇整数集合。双射函数f和g定义如下:11g:I→E,g(x)=2xf:E→M,f(x)=x+1因为f和g都是双射函数,故合成函数fg:I→M,fg(x)=f(2x)=2x+1.也是双射函数。12(b)设则g,f都是单射函数,于是13定理4.2―1的每一部分的逆定理都不真,但有下述“部分逆定理”.定理4.2―2设fg是合成函数,(a)如果fg是满射的,那么f是满射的.(b)如果fg是单射的,那么g是单射的.(c)如果fg是双射的,那么f是满射的而g是单射的。14定

6、义4.2―2对函数f:X→Y,如果存在y∈Y使对每一x∈X有f(x)=y,即f(X)={y},那么f称为常函数(每个原像x的映射都是同一个y)。定义4.2―3如果函数f:X→X对一切x∈X有f(x)=x,则称f为X上的恒等函数,通常记为1X.恒等函数是双射函数.就是一个集合上的相等关系.15定理4.2―3设f:X→Y是函数,那么,f=f·1X=1Y·f。定义4.2―4X上的双射函数称为X上的置换或排列。例3(a)一集合X上的恒等函数是一个置换,并被称作么置换,或恒等置换。(b)函数f:｛1,2,3｝→｛1,2,3｝,这里f(1)=2,f(2)=1,f(3)=3是一置换

7、.16我们常常把这样的置换用矩阵形式表示如下(c)函数f:I→I,f(x)=x+5,是整数集合上的一个置换。当集合X是无限集时,X上的置换称为无限次的,当集合X是有限集时,若｜X｜=n;17则X上的置换称为n次的。n次置换常写成的形式,可以任意交换列的次序,但习惯上矩阵的第一行元素还是保持在原定义域的次序。这种表示法在我们将来研究群论时很有用.18定理4.2―4在n个元素的集合中,不同的n次置换有n!个.证用归纳法。为了叙述方便,我们把P:X→X记成P:X→Y。当n=1时,X={x1},Y={y1},于是X→Y的双射函数的数目等于1!=1.设从n个元