第五章 函数与基数

1、2021-7-261第五章第五章 函数与基数函数与基数5.1 函数基本概念函数基本概念5.2 函数类型函数类型5.3 函数运算函数运算5.4 基基 数数2021-7-2625.1 函数基本概念函数基本概念 函数也常称为映射或变换，其定义如下：函数也常称为映射或变换，其定义如下： 定义定义5.1.1 设设A和和B是任意两个集合，且是任意两个集合，且f是从是从A到到B的关系，若对每一个的关系，若对每一个x A，都存在，都存在唯一的唯一的y B，使，使x,y f，则称，则称f为从为从A到到B的函的函数，并记作数，并记作f:AB。A称为函数称为函数f的定义域，即的定义域，即D(f)=A，B称为函数称为

2、函数f的陪域，的陪域，R(f)称为函数称为函数f的的值域，且值域，且R(f) B。有时也用。有时也用f(A)表示函数表示函数f的值的值域，即域，即2021-7-263f(A)=R(f)=y|y B( x)(x Ay=f(x) 并称并称f(A)为函数为函数f的像。的像。 对于对于f:AB来说，若来说，若x,y f，则称，则称x为函为函数的自变元，称数的自变元，称y为函数因变元，因为为函数因变元，因为y值依赖值依赖于于x所取的值，或称所取的值，或称y是是f在在x处的值，或称处的值，或称y为为f下下x的像。通常把的像。通常把x,y f记作记作f(x)=y。2021-7-264 从本定义可以看出，从从

3、本定义可以看出，从A到到B的函数的函数f和一和一般从般从A到到B的二元关系之不同有以下两点：的二元关系之不同有以下两点： A的的每一每一元素都必须是元素都必须是f的有序对的第一的有序对的第一分量。分量。 若若f(x)=y，则函数，则函数F在在x处的值是唯一的，处的值是唯一的，即即f(x)=yf(x)=zy=z2021-7-265 定义定义5.1.2 设设f:AB，g:CD，若若A=C，B=D，且对每一，且对每一x A都有都有f(x)=g(x)，则称函数，则称函数f和和g相等，记为相等，记为f=g。 本定义表明了，两函数相等，它们必须有本定义表明了，两函数相等，它们必须有相同的定义域、陪域和有序

4、对集合。相同的定义域、陪域和有序对集合。2021-7-266 下面讨论由集合下面讨论由集合A和和B，构成这样函数，构成这样函数f:AB会有多少呢？或者说，在会有多少呢？或者说，在A B的所有子的所有子集中，是全部还是部分子集可以定义函数？令集中，是全部还是部分子集可以定义函数？令BA表示这些函数的集合表示这些函数的集合(称为由集合称为由集合A到集合到集合B的超幂的超幂)，即，即 BA= f|f:AB 设设|A|=m，|B|=n，则，则|BA|=nm。(这里这里|A|表表示集合示集合A的基数的基数,或者叫势或者叫势)这是因为对每个自变这是因为对每个自变元，它的函数值都有元，它的函数值都有n种取法

5、，故总共有种取法，故总共有nm种种从从A到到B的函数。的函数。2021-7-2675.2 函数类型函数类型 根据函数具有的不同性质，可以将函数分根据函数具有的不同性质，可以将函数分成不同的类型。本节将定义这些函数，并给出成不同的类型。本节将定义这些函数，并给出相应的术语。相应的术语。2021-7-268 定义定义5.2.1 设设f:AB是函数，若是函数，若R(f)=B，即对任意即对任意b B，存在，存在a A，使得，使得f(a)=b，或形，或形式表为：式表为：( y)(y B( x)(x Af(x)=y) 则称则称f:AB是满射函数，或称函数是满射函数，或称函数f:AB是满是满射的。射的。 本

6、定义表明了，在函数本定义表明了，在函数f的作用下，的作用下，B中每中每个元素个元素b，都至少是，都至少是A中某元素中某元素a的像，因此，的像，因此，若若A和和B是有限集合，存在满射函数是有限集合，存在满射函数f:AB，则则|A|B|。2021-7-269 定义定义5.2.2 设设f:AB是函数，对任意的是函数，对任意的a，b A，且且a b，都有，都有f(a) f(b)，或形式表为，或形式表为( x)( y)(x,y Ax yf(x) f(y) 则称则称f:AB是单射函数，或称函数是单射函数，或称函数f:AB是单是单射的。射的。 本定义揭示了，本定义揭示了，A中不同的元素，其在中不同的元素，其

7、在B中中像也是不同的。于是，若像也是不同的。于是，若A的的B是有限集合，存是有限集合，存在单射函数在单射函数f:AB，则，则|A|B|。2021-7-2610 定义定义5.2.3 设设f:AB是函数，若是函数，若f既是满射既是满射又是单射，则称又是单射，则称f:AB是双射函数（或一一对是双射函数（或一一对应），或称函数应），或称函数f:AB是双射的。是双射的。 该定义说明了，该定义说明了，B中的每个元素中的每个元素b是且仅是是且仅是A中某个元素中某个元素a的像。因此，若的像。因此，若A和和B是有限集是有限集合，存在双射函数合，存在双射函数f:AB，则，则|A|=|B|。2021-7-26112

8、021-7-2612 定义定义5.2.4 设设f:AB是函数，若存在是函数，若存在b B，使对任意使对任意a A有有f(a)=b，即即f(A)=b，则称，则称f:AB为常值函数。为常值函数。2021-7-2613 定义定义5.2.5 设设f:AA是函数，若对任意是函数，若对任意a A，有有f(a)=a，亦即，亦即f=a,a|x A 则称则称f:AA为为A上恒等函数，通常记为上恒等函数，通常记为IA，因，因为恒等关系即是恒等函数。为恒等关系即是恒等函数。 由定义可知，由定义可知，A上恒等函数上恒等函数IA是双射函数。是双射函数。2021-7-2614 定义定义5.2.6 设设A和和B为集合，且为

9、集合，且A B，若函，若函数数fA: B 0,1为为 1 x A fA(x)= 0 否则否则 则称则称fA为集合为集合A的特征函数。的特征函数。 特征函数建立了函数与集合的一一对应关特征函数建立了函数与集合的一一对应关系。于是，可通过特征函数的计算来研究集合系。于是，可通过特征函数的计算来研究集合上的命题。上的命题。2021-7-2615 定义定义5.2.7 设设A,和和B,为全序集，函数为全序集，函数f:AB。对于任意。对于任意a,b A. 若若ab，有有f(a)f(b)，则称，则称f为单调递增函为单调递增函数。数。 若若ab，有有f(a)f(b)，则称，则称f为单调递减函为单调递减函数。数

10、。2021-7-2616 若若ab，且且a b，有，有f(a)f(b)，则称，则称f为为严格单调递增函数。严格单调递增函数。 若若ab，且且a b，有有f(a)f(b)，则称，则称f为为严格单调递减函数。严格单调递减函数。 显然，严格单调递增函数是单调递增函数，显然，严格单调递增函数是单调递增函数，严格单调递减函数是单调递减函数。严格单调递减函数是单调递减函数。2021-7-26175.3 函数运算函数运算 函数是一种特殊关系，对关系可以进行运函数是一种特殊关系，对关系可以进行运算，自然对函数也需要讨论运算问题，即如何算，自然对函数也需要讨论运算问题，即如何由已知函数得到新的函数。由已知函数得

11、到新的函数。2021-7-26181函数复合函数复合 利用两个具有一定性质的已知函数通过复利用两个具有一定性质的已知函数通过复合运算可以得到新的函数。合运算可以得到新的函数。 定理定理5.3.1 设设f:AB和和g:BC是函数，通是函数，通过复合运算过复合运算 ，可以得到新的从，可以得到新的从A到到C的函数，的函数，记为记为g f，即对任意，即对任意a A，有，有(g f)(x)=g(f(x)。2021-7-2619 注意，函数是一种关系，今用注意，函数是一种关系，今用“ ”表示函表示函数复合运算，记为数复合运算，记为g f，这是，这是“左复合左复合”，它，它与关系的与关系的“右复合右复合”f

12、*g次序正好相反，即有次序正好相反，即有g f=f*g。2021-7-2620推论推论1 若若f,g,h都是函数，则都是函数，则(f g) h=f (g h)。本推论表明，函数复合运算是可结合的。本推论表明，函数复合运算是可结合的。 若对于集合若对于集合A，f:AA，则函数，则函数f能同自身能同自身复合成任意次。复合成任意次。f的的n次复合定义为：次复合定义为： f 0(x)=x f n+1(x)=f(fn(x)，n N。2021-7-2621定理定理5.3.2 设设f:AB，g:BC 若若f:AB，g:BC都是满射，则都是满射，则g f:AC也是满射。也是满射。 若若f:AB，g:BC都是单

13、射，则都是单射，则g f:AC也是单射。也是单射。 若若f:AB，g:BC都是双射，则都是双射，则g f:AC也是双射。也是双射。2021-7-2622定理定理5.3.3 若若f:AB是函数，则是函数，则f=f IA=IB f 本定理揭示了，恒等函数在复合函数运本定理揭示了，恒等函数在复合函数运算中的特殊性质，特别地，对于算中的特殊性质，特别地，对于f:AA，有有f IA= IA f=f。2021-7-26232函数逆运算函数逆运算 给定关系给定关系R，其逆关系是存在，但对已知，其逆关系是存在，但对已知一函数一函数,它作为关系其逆是存在它作为关系其逆是存在,但未必是函数但未必是函数.例如例如,

14、A=a,b,c ,B=1,2,3,f=a,1,b,1,c,3是函数是函数,而而f-1=1,a,1,b,3,c却不是从却不是从B到到A的函数。但若的函数。但若f:AB是双射，则是双射，则f-1便是从便是从B到到A的函数。的函数。 定理定理5.3.4 若若f:AB是双射，则是双射，则f-1:BA也也是双射。是双射。2021-7-2624 定义定义5.3.1 设设f:AB是双射函数是双射函数,称称 f -1:BA是是f的逆函数的逆函数,习惯上常称习惯上常称f-1为为f的反的反函数。函数。 定理定理5.3.5 设设f:AB是双射函数是双射函数,则则 f -1 f=IA，f f-1=IB 定理定理5.3

15、.6 若若f:AB是双射是双射,则则(f-1)-1=f。2021-7-26255.4 基基 数数1基数定义基数定义 首 先 选 取 一 个首 先 选 取 一 个 “ 标 准 集标 准 集合合”Nn=0,1,2,n-1，再用双射函数为工，再用双射函数为工具，给出集合基数的定义如下：具，给出集合基数的定义如下：2021-7-2626 定义定义5.4.1 设设A是集合，若是集合，若f:NnA为双射为双射函数，则称集合函数，则称集合A是有限集，是有限集，A的基数是的基数是n，记，记为为|A|=n，或或card A=n。若集合。若集合A不是有限的，不是有限的，则称则称A是无限集。是无限集。 本定义表明了

16、，对于有限集合本定义表明了，对于有限集合A，可以用，可以用“数数”数的方式来确定集合数的方式来确定集合A的基数。的基数。 定理定理5.4.1 自然数集合自然数集合N是无限集。是无限集。 为了确定某些无穷集合的基数，选取第二为了确定某些无穷集合的基数，选取第二个个“标准集合标准集合”N来度量这些集合。来度量这些集合。2021-7-2627 定义定义5.4.2 设设A是集合，若是集合，若f:NA为双射为双射函数，则称函数，则称A的基数是的基数是0，记为，记为|A|=0。 显然，存在从显然，存在从N到到N的双射函数，故的双射函数，故|N|=0，0读作读作“阿列夫零阿列夫零”。符号。符号0是康是康托引

17、入的。托引入的。0是一个无法确定的数是一个无法确定的数, 是一个抽是一个抽象的描述。象的描述。 2021-7-2628 定义定义5.4.3 设设A是集合，是集合， 若若|A|=0，则称，则称A是可数无限集；是可数无限集； 若若A是无限的且不可数的，则称是无限的且不可数的，则称A是不可数是不可数集或不可数无限集。集或不可数无限集。不可数无限集可数无限集无限集有限集集合2021-7-2629 在上述基数定义中，是使用两个在上述基数定义中，是使用两个“标准集标准集合合”Nn和和N以及双射函数（或一一对应），引入以及双射函数（或一一对应），引入了集合基数的概念。这种方式可以把基数简单了集合基数的概念。

18、这种方式可以把基数简单地看作对集合指派一个符号，指派原则是：与地看作对集合指派一个符号，指派原则是：与Nn构成双射或一一对应的集合，指派它的基数构成双射或一一对应的集合，指派它的基数是是n，与与N构成双射或一一对应的集合，指派它构成双射或一一对应的集合，指派它的基数为的基数为0。指派空集的基数为。指派空集的基数为0。2021-7-26302基数比较基数比较基数概念是有限集合元素个数的推广。基数概念是有限集合元素个数的推广。可数可数(无限无限)集的基数都等于集的基数都等于0。那么那么, 无限集的基数无限集的基数都一样都一样吗吗? 有没有有没有最大的基数最大的基数呢？呢？2021-7-2631 在

19、集合基数的基础上，可以建立相等关系和在集合基数的基础上，可以建立相等关系和次序关系，进行基数比较和基数运算，这里仅讨次序关系，进行基数比较和基数运算，这里仅讨论前者。论前者。 定义定义5.4.4 设设A和和B为任意集合为任意集合(包括无限集包括无限集) 若有一个从若有一个从A到到B的双射函数，则称的双射函数，则称A和和B有相同基数（或称有相同基数（或称A与与B是等势），记为是等势），记为|A|=|B|（或或A B）。）。2021-7-2632 若有一个从若有一个从A到到B的单射函数，则称的单射函数，则称A的的基数小于等于基数小于等于B的基数，记为的基数，记为|A|B|。 若有一个从若有一个从A

20、到到B的单射函数，但不存的单射函数，但不存在双射函数，则称在双射函数，则称A的基数小于的基数小于B的基数，记的基数，记为为|A|B|。2021-7-2633 由于在复合运算下，双射函数是封闭的，双由于在复合运算下，双射函数是封闭的，双射函数的逆函数（即常说反函数）是双射函数，射函数的逆函数（即常说反函数）是双射函数，因此等势关系有以下性质：因此等势关系有以下性质： 定理定理5.4.3 等势是任何集合族上的等价关系。等势是任何集合族上的等价关系。2021-7-2634 从上面定义及定理可知：从上面定义及定理可知： 等势是集合族上的等价关系，它把集合等势是集合族上的等价关系，它把集合族划分成等价类

21、，在同一等价类中的集合具有族划分成等价类，在同一等价类中的集合具有相同的基数。因此可以说：基数是在等势关系相同的基数。因此可以说：基数是在等势关系下集合的等价类的特征。或者说：基数是在等下集合的等价类的特征。或者说：基数是在等势关系下集合的等价类的名称。这实际上就是势关系下集合的等价类的名称。这实际上就是基 数 的 一 种 定 义 。 例 如 ，基 数 的 一 种 定 义 。 例 如 ， 3 是 等 价 类是 等 价 类a,b,c,p,q,r,1,2,3的名称（或特征）。的名称（或特征）。0是自然数集合是自然数集合N所属等价类的名称。所属等价类的名称。2021-7-2635 要证明一个集合要证

22、明一个集合A有基数有基数 ，只需选取基，只需选取基数为数为 的任意集合的任意集合B，证明从，证明从A到到B或从或从B到到A存在存在一个双射函数。选取集合一个双射函数。选取集合B的原则是使证明尽可的原则是使证明尽可能容易。能容易。 下面将不加证明地引入两个定理。第一个定下面将不加证明地引入两个定理。第一个定理称为三分律。第二定理表明：理称为三分律。第二定理表明：是反对称的。是反对称的。2021-7-2636 定理定理5.4.4 （Zermelo）设设A和和B是任意两是任意两个集合，则下述情况恰有一个成立：个集合，则下述情况恰有一个成立： |A|B| |B|A| |A|=|B|2021-7-263

23、7 定理定理5.4.5 （Cantor-Schroder-Bernstein）设设A和和B是任意两个集合，若是任意两个集合，若|A|B|和和|B|A|，则则|A|=|B|。 本定理对证明两集合具有相同基数提供了有本定理对证明两集合具有相同基数提供了有效的方法。若能够构造一单射函数效的方法。若能够构造一单射函数f:AB，则有，则有|A|B|；又能构造另一个单射函数；又能构造另一个单射函数g:BC，以，以证明证明|B|A|。于是根据本定理即可得出。于是根据本定理即可得出|A|=|B|。特别要注意，特别要注意，f和和g不必是满射。因为通常构造这不必是满射。因为通常构造这样两个单射函数比构造一个双射函

24、数要容易许多。样两个单射函数比构造一个双射函数要容易许多。2021-7-2638对于有限集，我们有：对于有限集，我们有：定理定理5.4.6 设设A是有限集合，则是有限集合，则|A|0。对于无限集呢？对于无限集呢？我们有必要对无限集有所了解我们有必要对无限集有所了解2021-7-2639l 有限集与无限集虽然是数量上的差别，但是由有限集与无限集虽然是数量上的差别，但是由“量变量变”而引起了而引起了“质质”的变化，无限集有着的变化，无限集有着很多有限集所没有的一些特性，而有限集的一很多有限集所没有的一些特性，而有限集的一些特性也不能任意推广到无限集中去，即使有些特性也不能任意推广到无限集中去，即使

25、有的能推广也要做某些意义上的修改。的能推广也要做某些意义上的修改。l下面我们先讨论无限集的一些特性下面我们先讨论无限集的一些特性2021-7-2640 定理定理5.4.7 无限集必含有与其等势的真子集。无限集必含有与其等势的真子集。例如：自然数集例如：自然数集N=0,1,2,3,与其真子集与其真子集S=1,3,5,7,均为无限集，且均为无限集，且N S。这是因为。这是因为它们之间存在双射（一一对应）：它们之间存在双射（一一对应）：N: 0 1 2 3 4 S: 1 3 5 7 9 这种一一对应关系可以写成这种一一对应关系可以写成s=2n+1,其中其中n N,s S2021-7-2641 无限集

26、的这个特征可以作为区别无限集与有无限集的这个特征可以作为区别无限集与有限集的一个标志。即有限集的一个标志。即有 推论推论 一个集合为无限集的充分必要条件是一个集合为无限集的充分必要条件是它必含有与其等势的真子集。它必含有与其等势的真子集。 有了这个推论后，我们可以重新定义有限集有了这个推论后，我们可以重新定义有限集与无限集与无限集 定义定义 一集合若存在与其等势的真子集则称一集合若存在与其等势的真子集则称其为无限集，否则称为有限集。其为无限集，否则称为有限集。2021-7-2642 下面我们对无限集作进一步的探讨，我们讨下面我们对无限集作进一步的探讨，我们讨论一种特殊类型的也是最常见的无限集论

27、一种特殊类型的也是最常见的无限集可数可数(无限无限)集的性质。集的性质。2021-7-2643定理定理5.4.8 每个无限集必包含一可数无限子集。每个无限集必包含一可数无限子集。定理定理5.4.9 可数无限集的无限子集仍为一可数无限可数无限集的无限子集仍为一可数无限集。集。由此可知，可数无限集是无限集中的最小集合。由此可知，可数无限集是无限集中的最小集合。从而有从而有定理定理5.4.10 0是最小无限集合的基数。是最小无限集合的基数。2021-7-2644下面给出一可数无限集的结论下面给出一可数无限集的结论定理定理5.4.11 整数集整数集Z是可数无限集。是可数无限集。定理定理5.4.12 有理数集有理数集Q是可数无限集。是可数无限集。 下面的一个问题是：是否所有的无限集都是下面