离散数论-函数.pptVIP

离散数学

函数;主要内容;函数〔映射〕：一个集合和另外一个集合之间的联系。

一个集合中的每个元素都对应有另一个集合中唯一的一个元素。

函数是一种特殊的关系;

§3.1部分函数;局部函数;局部函数;定义域、值域;例子;特殊的局部函数;f={x，2x|x?R};象、原象;限制、延拓;;证明：i)和ii)显然，只证iii)和iv)

假设x∈A，因为A?domf，所以f(x)↓且f(x)∈f[A]，所以x∈f–1[f[A]]。

假设y∈B，那么y∈ranf〔因为B?ranf〕。因此，有x∈X使y=f(x)。从而得x∈f–1[B]。这说明y∈f[f–1[B]]。另一方面，假设y∈f[f–1[B]]，那么有x∈f–1[B]使f(x)=y，所以y∈B。;;证明：只证iv)，其它的证明与此类似。

假设B∈В，那么由∩В?B得：f–1[∩В]?f–1[B]

从而得：f–1[∩В]?∩{f–1[B]｜B∈Ｂ}；

另一方面，任取x∈∩{f–1[B]｜B∈Ｂ}，

假设B∈В，那么x∈f–1[B]，即f(x)∈B。

因此：f(x)∈∩В，即x∈f–1[∩В]。

故有：∩{f–1[B]｜B∈Ｂ}?f–1[∩В]。;;A到B的全函数集;例子;;作业;

§3.2函数的合成;函数的合成;关系的合成 ? 函数的合成;;合成;*合成函数gof与合成关系fog表示同一个集合。

这种差异是历史形成的，具有其方便之处：

(gof)(x)=g(f(x))

当x,z?fog时，必有y?Y使x,y?f且y,z?g。;;;恒等函数;;内射、满射和双射;设R为集合A上的等价关系，那么

?＝{〈x，[x]R〉｜x∈A}

是从A到A/R的满射，并称?为自然映射。;设f：X→Y和g：Y→Z

假设f和g都是满射，那么gof也是满射；

假设f和g都是内射，那么gof也是内射；

假设f和g都是双射，那么gof也是双射。;证明：i) ran(gof)

||

g[ranf]

|| f满射

g[Y]

|| g满射

Z;ii) 假设x1，x2?X且x1?x2

? f内射

f(x1)?f(x2)

? g内射

g(f(x1))?g(f(x2))

即(gof)(x1)?(gof)(x2)

故gof为内射;设f：X→Y和g：Y→Z

假设gof是满射，那么g是满射；

假设gof是内射，那么f是内射；

假设gof是双射，那么g是满射且f是内射。

规那么：左满右内;证明：i)显然rang?Z

又：ranf?Y

g[ranf]?g[Y]=rang

而：g[ranf]=ran(gof)〔定理3.2.2〕

且：ran(gof)=Z 〔gof满射〕

所以： Z?rang

因此： Z=rang，即g为满射。;ii)反证法。

假设f不是内射，那么有x1,x2?X且x1?x2使f(x1)=f(x2)。因此(gof)(x1)=g(f(x1))=g(f(x2))=(gof)(x2)，

这与gof为内射矛盾。

所以假设不成立，即f为内射。;作业