第5章
函 数
函数是一个在自然科学、工程技术，甚至在某些社会科学中被广泛应用的数学概念，也是重要的数学工具。无论在初等数学还是高等数学中，无论在基础课还是专业课中，大家都会经常与函数打交道，以函数为基本工具解决各种各样的数学问题和专业问题。实际上，计算机的任何输出都可看成是某些输入的函数、各种高级程序语言中使用了大量的函数。函数在数学、计算机科学以及许多应用领域里扮演者重要的角色。
对函数一词读者一定十分熟悉。在高一数学中学习过，函数被定义为两集合元素之间的满足特别要求的对应关系。本章从关系的角度给出函数的定义，即用一个集合来描述函数，并用集合论的方法来研究函数的运算和特性，以及通过函数来研究集合的分类和基数等问题。
5.1 函数的概念
函数也叫映射、变换或对应，函数是数学的一个基本概念。这里将高等数学中连续函数的概念推广到对离散量的讨论，即将函数看作是一种特殊的二元关系。
首先看看图5.1.1所示的集合到集合的6个关系。
图5.1.1 集合到集合的6个关系
在图5.1.1给出的6个关系中，关系，，，都具有下面两个特点：
（1）关系的定义域是；
（2）中任一元素对应唯一一个中的元素。
称具有这样两个特征的关系为函数（映射）。显然关系，没有这两个特点。
定义5.1.1 设是两个任意的集合，是到的一个关系，若对每一个，都存在一个唯一的，使得，则称关系为到的函数（function），记作或。若，则称为函数在处的值（或像），亦可记为。
如果为到的函数，将的值域改记为，称为函数的像集。对于，称为的像，即。
显然, 。
从定义5.1.1可知，函数是到的一个特殊关系，其特殊性在于：
（1） dom，集合X的每个元素有像，这称为像的存在性。
（2） 若，则函数在处的值是唯一的，这称为像的唯一性，即
例5.1.1 设，且有，那么是函数吗，如果是函数请求和。
解 因为dom，且每个中的元素都有唯一的中的元素与之对应。所以是函数。且
例5.1.2 设A={1, 2, 3, 4}, B={a, b, c, d}，试判断下列关系哪些是函数？如果是函数，请写出它的值域。
（1） f1={<1,a>,<2,a>,<3,d>,<4,c>}；
（2） f2={<1,a>,<2,a>,<2,d>,<4,c>}；
（3） f3={<1,a>,<2,b>,<3,d>,<4,c>}；
（4） f4={<2,b>,<3,d>,<4,c>}。
解 （1） 在f1中，因为A中每个元素都有唯一的像和它对应，所以f1是函数。其值域是A中每个元素的像的集合，即ran f1={a,c,d}；
（2） 在f2中，因为元素2有两个不同的像a和d，与像的唯一性矛盾，所以f2不是函数；
（3） 在f3中，因为A中每个元素都有唯一的像和它对应，所以f3是函数。其值域是A中每个元素的像的集合，即ran f3={a,b,c,d}；
（4） 在f4中，因为元素1没有像，所以f4不是函数。
例5.1.3 设R是实数集，N是自然数集，判别下列关系中哪个构成函数。
（1） ；
（2） ；
（3） ；
（4） ；
（5） 为小于的素数个数；
（6） ；
（7） ；
（8） 。
解 （1）构成函数。
（2） ，即值不唯一，故不构成函数。
（3） 因为不能取定义域中所有的值，且对应很多，故不构成函数。
（4） 因为不能取定义域中所有的值，故不构成函数。
（5） 构成函数。
（6） 构成函数。
（7） 因为对，值不唯一，故不构成函数。
（8） 因为对，值不唯一，故不构成函数。
例5.1.4 下列集合中，哪些是函数？并求函数的定义域和值域。
（1）
（2）
解 （1） 是函数。dom，
（2） 不是函数。
例5.1.5 设A={a,b},B={1,2}，请分别写出A到B的不同关系和不同函数。
解 因为|A|=2,|B|=2，所以|A×B|=|A|×|B|=4，即A×B={<a,1>,<a,2>, <b,1>,<b,2>}，此时从A到B的不同的关系有24=16个。
分别如下：
R0=(，R1={<a,1>}, R2={<a,2>}, R3={<b,1>},
R4={<b,2>}, R5={<a,1>,<b,1>}, R6={<a,1>,<b,2>}, R7={<a,2>,<b,1>},
R8={<a,2>,<b,2>}, R9={<a,1>,<a,2>}, R10={<b,1>,<b,2>}, R11={<a,1>,<a,2>,<b,1>},
R12={<a,1>,<a,2>,<b,2>}, R13={<a,1>,<b,1>,<b,2>}, R14={<a,2>,<b,1>,<b,2>}, R15={<a,1>, <a,2>,<b,1>,<b,2>}
从A到B的不同的函数仅有22=4个。分别如下：
R5={<a,1>,<b,1>}, R6={<a,1>,<b,2>}, R7={<a,2>,<b,1>}, R8={<a,2>,<b,2>}。
例5.1.6 设，，从到的所有函数如下：
，
，
，
，
从到的所有函数：
一般地，设和都为有限集，分别有和个不同元素，则从到共有个不同的函数。今后用符号表示从到的所有函数的集合，甚至当和是无限集时，也用这个符号，即
则有。特别地表示集合上函数的全体。
函数是特殊的关系，对有限集合之间的函数与关系有如下差异：
（1） 个数差别：从A到B的不同的关系有2|A|(|B|个；从A到B的不同的函数却仅有|B||A|个。
（2）元素差别：关系的第一个元素可以相同；函数的第一元素一定是互不相同的，且取遍集合A的所有元素。
由于函数归结为关系，因而函数的表示及运算可归结为集合的表示及运算，函数的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。
例5.1.7 对于集合A = {1,2,3} 到B = {a, b, c}, 关系f = {<1, a>, <2, b>, <3, c>} 和g = {<1, b>, <2, b>, <3, a>}，判断f, g, f ∪ g, f ∩ g, f ? g, , f ⊕ g是否为A到B的函数。
解 根据函数的定义，f和g都是集合A到集合B的函数。
f ∪ g = {<1, a>, <2, b>, <3, c>, <1, b>, <3, a>}不是A到B的函数，因为元素1和3都不满足像的单值性。
f ∩ g = {<2, b>}不是A到B的函数，因为元素1和元素3没有像。
f ? g = {<1, a>, <3, c>}不是A到B的函数，因为元素2没有像。
= {<1, b>, <1, c>, <2, a>, <2, c>, <3, a>, <3, b>}不是A到B的函数，因为元素1，2和3都不满足像的单值性。
f ⊕ g = {<1, a>, <3, c>, <1, b>, <3, a>}不是A到B的函数，因为元素1和3都不满足唯一像的单值性，且元素2没有像。
由上述例题可知，函数作为一种特殊关系或特殊集合，其集合运算的结果可能不再是函数。
定义5.1.2 设函数，函数，如果，且对于所有，有，则称函数和相等，记作。如果，且对于所有，有，则称函数包含于，记作。
事实上，当不强调函数是定义在哪个集合上的时候，由于函数是特殊的关系，所以f = g的充要条件是且。
例5.1.8 设R是实数集，判断下列函数是否相同：
（1） f = {<x, y>|x, y ∈ R ( y = (x2 ? 1)/(x + 1)}；
g = {<x, y>|x, y ∈ R ( y = x ? 1} 。
（2） f = {<x, y>|x, y ∈ R ( y = 1}；
g = {<x, y>| x, y ∈R ( y = x0}。
（3） f = {< x, y >| x, y ∈ R ( y = x2/x}；
g = {<x, y >| x, y ∈ R ( y = x }。
（4） f = {< x, y >|x, y ∈ R ( y = (x2 + 1)/ x}；
g = {<x, y>|x, y ∈ R ( y = x + 1/ x}。
解 根据函数的对应关系和定义域是否相同进行判断。
（1）、（2）、（3）均不是相同的函数，（4）是相同的函数。
定义5.1.3 设和是任意给定的两个非空集合，和分别是和的任意两个非空子集合，即有A1 ? A, B1 ? B。f是一个从A到B函数，即f: A → B。
（1） 令f (A1) = {f (x)| x ∈A1}，称f (A1)为A1在f下的像。当A1 = A时，称f(A)为f的像。
（2） 令f (1(B1) = {x| x ∈A( f (x) ∈ B1}，称f (1 (B1)为B1在f下的完全原像。
在上述定义中显然有：f (A1) ? B且f?1(B1) ? A。
请注意区别元素的像和集合的像是两个不同的概念，的像，而像。关于子集的像有下列性质。
定理5.1.1 设为到函数，对任意X，有
（1） ；
（2） ；
（3） 。
证明 （1）对任
因此，。
（2）、（3）的证明请读者完成。
注意：（2）、（3）中的“”不能用“=”代替。下面举例说明。
例5.1.9 设 ，如图5.1.2所示。
图5.1.2 例5.1.9中函数的图表示
那么
5.2 函数的基本类型
从本质上讲，从集合A到集合B的函数描述的是A中元素与B中元素之间的一种特殊对应关系，这种特殊对应关系可以是一对一的也可以是多对一的，但不能是一对多或多对多的关系。此外，函数值域可以是B的某个真子集，也可以是B自身。根据以上讨论，就可将所有函数分成如下四种不同的基本类型，即是单射但不是满射的函数、是满射但不是单射的函数、既是单射又是满射的函数、既不是单射也不是满射的函数。首先给出单射函数和满射函数的定义。
定义5.2.1 设函数。
（1）如果ran，即的每一个元素都是中一个或多个元素的像，则称这个函数为满射函数，简称满射。
（2）如果对于任意，若，则有，则称这个函数为单射函数（或入射函数），简称单射（入射）。
（3）若既是满射又是单射，则称是双射函数，简称双射。双射也称为1-1对应。特别地，若，称双射为上的一个1-1变换。
由定义不难看出，如果是满射，则对于任意，必存在，使得成立；如果是单射，则中没有两个不同元素有相同的像，即对于任意，。
图5.2.1说明了四类函数之间的关系，一般来说既非单射又非满射的函数是大量存在的。
图5.2.1 四类函数之间的关系
例5.2.1 确定下列函数的类型。
（1）设A={1,2,3,4,5}, B={a,b,c,d}
f: A→B定义为：{<1,a>,<2,c>,<3,b>,<4,a>,<5,d>}
（2）设A={1,2,3}, B={a,b,c,d }。f: A→B定义为
f={<1,a>,<2,c>,<3,b>}
（3）设A={1,2,3}, B={1,2,3}。f: A→B定义为
f ={<1,2>,<2,3>,<3,1>}
解 （1）因为对任意yB，都存在xB，使得<x,y>f，所以f是满射函数。
（2）因为A中不同的元素对应不同的象，所以f是单射函数。
（3）因为f既是单射函数，又是满射函数，所以f是双射函数。且f还是A上的1-1变换。
例5.2.2 （1）设，如果定义如下为
则是满射。
（2）定义为，则这个函数是单射，但不是满射。
（3）令表示实数的闭区间，即，定义为：。则这个函数是双射。
例5.2.3 判断图5.1.1中的4个函数R3，R4，R5，R6是单射，满射，还是双射？
解 因为，所以R3不是单射；
又因为无原像，所以R3也不是满射。
同理可知R4是单射，但因为b3无原像， 所以R4不是满射。
R5不是单射，但是满射。
R6既是单射，又是满射，即R6是双射。
例5.2.4 设是自然数集，R是实数集，下列函数哪些是满射、单射、双射？
（1）。
（2）。
（3）。
（4）。
（5）。
解 （1）单射。
（2）一般函数（既非满射，也非单射）。
（3）一般函数（既非满射，也非单射）。
（4）不是函数，无定义。
（5）一般函数（既非满射，也非单射）。
定理5.2.1 令和为有限集，若和的元素个数相同，即，则是单射，当且仅当它是一个满射。
证明 （1）若是单射，则。从的定义我们有而，因为是有限的，故，因此，是一个满射。
（2）若是一个满射，则，于是。因为和是有限的，所以，是一个单射。
这个定理必须在有限集情况下才能成立，在无限集上不一定有效，如整数集合上的函数，这里，在这种情况下整数函数到偶数，显然这是一个单射，但不是满射。
注意：设A，B为有限集合，f是从A到B的函数，则
（1） f是单射的必要条件为|A|≤|B|；
（2） f是满射的必要条件为|B|≤|A|。
另外，还有两个特殊而又重要的函数——常值函数和恒等函数。
定义5.2.2 （1）设，如果存在，使得对所有的都有，即，称是常值函数。
（2）任意集合上的恒等关系为一函数，称为恒等函数。因为对任意都有，是双射。
（3）对实数x，f (x)取不小于x的最小整数，则称f (x)为上取整函数，记为f (x) = 。
（4）对实数x，f (x)取不大于x的最大整数，则称f (x)为下取整函数，记为f (x) = 。
（5）如果f (x)是从集合A到B = {0,1}上的函数，则称f (x)为布尔函数。
例5.2.5 存储在计算机磁盘上的数据或网络上传输的数据通常表示为字节串，每个字节由8个数字组成，要表示100字位的数据需要多少字节?
解 根据题意，只需求100除以8的上取整函数即可。即= 13，所以表示100 字位的数据需要13字节。
例5.2.6 在异步传输模式下，数据按53字节分组，每组称为一个信元，在数据传输速率为500 kbps的连接上一分钟能传输多少个信元。
解 首先需要求出一分钟能传输的字位数，然后再求出这些字位数可以组成多少个信元。因为要求一分钟能够传输的信元数，故需用下取整函数完成。因为一分钟能够传输的字节数为500×1000×60/8 = 3750000，所以一分钟能传输的信元数为 = 70754。
5.3 函数基本运算
如前所述，函数作为一种特殊二元关系，其交、并、补、差运算结果不一定还是函数关系。因此，我们不再考虑函数的集合运算，而着重考察函数的复合运算、逆运算和递归运算。
5.3.1 函数的复合运算
前面已经学习了二元关系的复合运算，函数作为一种特殊的二元关系，也可以进行复合运算，函数的复合运算其实就是函数关系的合成，下面定理保证了两个函数复合后得到的关系仍然是一个函数，并据此得到复合函数的定义。
定理5.3.1 设f：A→B，g：B→C是两个函数，则f与g的复合关系
是一个从A到C的函数，称之为函数f与g的复合函数，记为：A→C。
证明 因为f和g分别是A到B和B到C上的二元关系，故由关系复合的定义可知是一个A到C上二元关系。下面证明是一个函数：对于，由于是A到B的函数，有唯一的值，即。又是B到C的函数，有唯一的值即。因此，这样的是唯一的。所以复合关系是一个函数。
根据上述定理，由于两个函数的复合结果仍然是一个函数，故可直接推广到多个函数的情形，并且多个函数复合运算结果仍是函数。由于函数复合就是关系复合，故多个函数的复合同样满足结合律。
注意：对任意xA，有。这就是说，当f，g为函数时，它们的复合函数作用于自变量的次序刚好与合成的原始记号的顺序相反。
例5.3.1 设，构造函数如下：
，
，
求。
解
例5.3.2 设均为实函数，且，。求 。
解
所以
由于函数的复合满足结合律，如果是集合上的函数，那么n个的复合可记为，常称为f的n次迭代，，且约定，即恒等函数。
定理5.3.2 设函数，是两个函数，, 的复合函数满足
（1）若和是满射，则是满射。
（2）若和是单射，则是单射。
（3）若和是双射，则是双射。
证明 （1）因为是满射，故使得；又因为是满射，故，使得所以，
即，使得。因此，是满射。
（2）对，因为是单射，故；又因为是单射，故，所以是单射。
（3）因为和是双射，根据（1）和（2），为满射和单射，即是双射。
定理5.3.3 设函数，函数，那么有
（1）若是满射，则是满射。
（2）若是单射，则是单射。
（3）若是双射，则是满射，是单射。
证明 设 ，，。
（1）因为是满射，则，，使，故
使得，，可见，所以是满射。
（2）设且。因为是单射，故，即 ，因为是一个函数，则，即
所以，是单射。
（3）是双射，则是满射且是单射。是满射，由（1）可知是满射；是单射，由（2）可知是单射。
函数的复合运算还有以下性质：
定理5.3.4 设函数，则。特别地当时，有 。
证明 对，有 ，，则
所以
5.3.2 函数的逆运算
任意关系都可进行求逆运算而得到其逆关系，但是对于任意一个函数来说，只能保证它的逆是一个二元关系，并不能保证一定是函数。因此，在求一个函数的逆运算时，必须对该函数做一些特殊的要求。
定义5.3.1 设的函数关系，如果其逆关系：
是一个从B到A的函数，则函数可逆，并称是函数的逆函数或反函数。