一对一函数和映上函数
《离散数学及其应用（原书第6版）》第2章基本结构：集合、函数、数列与求和，本章将介绍数列的概念，它表示 有序的元素排列。还将介绍一些重要类型的数列，讨论一个从几个初始条件确定的数列模式问题。用排序数列的概念将定义集合可数的含义，也就是说，能用一个数 列列出集合的所有元素。本节为一对一函数和映上函数。
2.3.2 一对一函数和映上函数
有些函数在它们的定义域的不同成员上有不同的像。这种函数称为一对一的。
定义5
函数f称为一对一的或单射的，当且仅当对于f的定义域中的所有a和b，f（a）=f（b）蕴含着a=b。一对一的函数称为单射。
注意
函数f是一对一的，当且仅当只要a≠b就有f（a）≠f（b）。这种表达f为一对一函数的方式是对定义中的蕴含倒置而来。我们可以用量词，如�a�b（f（a）=f（b）→a=b）或等价地�a�b（a≠b→f（a）≠f（b）），来表达f是一对一的，其中论域是函数的定义域。
我们通过一对一的函数和不是一对一的函数示例来说明这个概念。
例8
判断从｛a,b,c,d｝到｛1，2，3，4，5｝的函数f是否为一对一的，f的定义是 f（a）=4，f（b）=5，f（c）=1而f（d）=3。
解f是一对一的，因为f在它定义域的四个元素上取不同的值。图2-10说明了这一点。
 |
| 图2-10一个一对一函数 |
例9判断从整数集合到整数集合的函数f（x）=x2是否为一对一的。
解函数f（x）=x2不是一对一的，因为，例如f（1）=f（-1）=1,但1≠-1。
注意，若定义域限制为Z+，函数f(x)＝x2就是一对一的。（技术上说，当限定一个函数的定义域的时候，我们得到了一个新的函数，被限制的元素的值域与原来是相同的，而被限制的定义域以外的原来定义域的元素就不被限制的函数定义了。）
例10判断函数f(x)＝x+1是否为实数集合到它自身的一对一函数。
解函数f（x）=x+1是一对一的。要证明这一点，只需注意在x≠y时x+1≠y+1。
现在我们给出保证函数为一对一的某些条件。
定义6
定义域和伴域都是实数集子集的函数f称为递增的，如果对f的定义域中的x和y，只要x<y就有f(x)≤f(y)(若对于x<y，恒有 f(x)＜f(y),则称函数f为严格递增的)。类似地，f是递减的，如果对f的定义域中的x和y，只要x<y就有f(x)≥f(y)(若对于 x<y，恒有f(x)＞f(y),称函数f为严格递减的)（定义中严格一词意味着严格不等式）。
注意
如果�x�y（x＜y→f（x）≤f（y））,则函数f是递增的；如果�x�y（x＜y→f（x）<f（y））,则函数f是严格递增的。
如果�x�y（x<y→f(x) ≥ f(y)）,则函数f就是递减的；如果�x�y（x<y→f(x)>f(y)）,则函数f就是严格递减的。这里论域均为函数f的定义域。
从上述定义可知，只要函数是严格递增的或者严格递减的，它必定是一对一的。但是，如果一个函数不是严格意义上的递增或递减，就不必然一对一了。
有些函数的值域和伴域相等，也就是说，伴域中的每个成员都是定义域中某个元素的像。具有这一性质的函数称为映上函数。
定义7
从A到B的函数f称为映上的或满射的，当且仅当对每个b∈B，有元素a∈A使得f（a）=b。如果函数f是映上的，就说它是满射函数。
注意
如果�y�x（f（x）=y），函数f就是映上的，其中x的论域是函数的定义域，y的论域是函数的伴域。
我们现在举几个映上函数和非映上函数的例子。
例11
令f为从｛a,b,c,d｝到｛1，2，3｝的函数，其定义为f（a）=3,f（b）=2,f（c）=1及f（d）=3。f是映上函数吗?
解由于伴域中所有3个元素均为定义域中元素的像，f是映上的。图2-11说明了这一点。
注意，若伴域是{1，2，3，4}，f就不是映上的。
 |
| 图2-11 一个映上函数 |
例12从整数集到整数集的函数f（x）=x2是映上的吗?
解f不是映上的，因此，比如说没有x使x2=-1。
例13从整数集到整数集的函数f（x）=x+1是映上的吗?
解这个函数是映上的，因为对每个整数y，都有一个整数x使f（x）=y。为看出这一点，只要注意f（x）=y的充分必要条件是x+1=y，而这只要令x=y-1就成立。
定义8
若函数f既是一对一的，又是映上的，就说它是一一对应或双射的。
下面的例14和例15阐述双射的概念。
例14令f为从｛a,b,c,d｝到｛1，2，3，4｝的函数，其定义为f（a）=4,f（b）=2,f（c）=1及f（d）=3。f是双射吗?
解函数f是一对一的和映上的。它是一对一的，是因为函数值都不同；它是映上的，是因为伴域中的所有4个元素，均为定义域的元素的像。于是f是双射。
图2-12给出了4个函数:其中第1个是一对一的，但不是映上的；第2个是映上的，但不是一对一的；第3个，既是一对一的，又是映上的；第4个既不是一对一的，也不是映上的。图2-12中的第5个对应关系不是函数，因为它把一个元素传递给两个不同的元素。
a）一对一，非映上 b）映上，非一对一c）一对一，映上d）既非一对一，也非映上 e）不是函数
 |
| （点击查看大图）图2-12 不同类型的对应关系的例子 |
假定f是从集合A到它自己的函数。如果A是有限的，那么f是一对一的当且仅当它是映上的。（从本节末练习68的结果即可得出这一结论。）当A为无限集时，这一结论不一定成立（参看2.4节）。
例15令A为集合。A上的恒等函数是函数ιA∶A→A，其中
对所有x∈A。换言之，恒等函数ιA是这样的函数，它赋给每个元素的是这个元素自身。函数ιA是一对一的和映上的，所以是双射。
| 回书目 上一节 下一节 |