离散数学第五章 函数与基数

第五章 函数与基数5.1 函数基本概念5.2 函数类型5.3 函数运算5.4 基 数Date15.1 函数基本概念函数也常称为映射或变换，其定义如下：定义5.1.1 设A和B是任意两个集合，且f 是从A到B的关系，若对每一个xA，都存在唯 一的yB，使‹x,y›f，则称f为从A到B的函数 ，并记作f:ABA称为函数f的定义域，即 D(f)=A，B称为函数f的陪域，R(f)称为函数f的 值域，且R(f)B有时也用f(A)表示函数f的值 域，即Date2f(A)=R(f)={y|yB∧(x)(xA∧y=f(x))}并称f(A)为函数f的像对于f:AB来说，若‹x,y›f，则称x为函数的自变元，称y为函数因变元，因为y值依赖于x所取的值，或称y是f在x处的值，或称y为f下x的像通常把‹x,y›f记作f(x)=yDate3从本定义可以看出，从A到B的函数f和一 般从A到B的二元关系之不同有以下两点：① A的每一元素都必须是f的有序对的第一分量② 若f(x)=y，则函数F在x处的值是唯一的，即f(x)=y∧f(x)=zy=zDate4定义5.1.2 设f:AB，g:CD，若A=C，B=D，且对每一xA都有f(x)=g(x)，则称函数f和g相等，记为f=g。

本定义表明了，两函数相等，它们必须有相同的定义域、陪域和有序对集合Date5下面讨论由集合A和B，构成这样函数f:AB会有多少呢？或者说，在AB的所有子集中，是全部还是部分子集可以定义函数？令BA表示这些函数的集合(称为由集合A到集合B的超幂)，即 BA={f|f:AB}设|A|=m，|B|=n，则|BA|=nm这里|A|表示集合A的基数,或者叫势)这是因为对每个自变元，它的函数值都有n种取法，故总共有nm种从A到B的函数Date65.2 函数类型根据函数具有的不同性质，可以将函数分成不同的类型本节将定义这些函数，并给出相应的术语Date7定义5.2.1 设f:AB是函数，若R(f)=B， 即对任意bB，存在aA，使得f(a)=b，或形式 表为： (y)(yB(x)(xA∧f(x)=y))则称f:AB是满射函数，或称函数f:AB是满 射的本定义表明了，在函数f的作用下，B中每 个元素b，都至少是A中某元素a的像，因此， 若A和B是有限集合，存在满射函数f:AB，则 |A|≥|B|Date8定义5.2.2 设f:AB是函数，对任意的a，bA，且ab，都有f(a)f(b)，或形式表为(x)(y)(x,yA∧xyf(x)f(y))则称f:AB是单射函数，或称函数f:AB是单射的。

本定义揭示了，A中不同的元素，其在B中像也是不同的于是，若A的B是有限集合，存在单射函数f:AB，则|A|≤|B|Date9定义5.2.3 设f:AB是函数，若f既是满射又是单射，则称f:AB是双射函数（或一一对应），或称函数f:AB是双射的该定义说明了，B中的每个元素b是且仅是A中某个元素a的像因此，若A和B是有限集合，存在双射函数f:AB，则|A|=|B|Date10Date11定义5.2.4 设f:AB是函数，若存在bB，使对任意aA有f(a)=b，即f(A)={b}，则称f:AB为常值函数Date12定义5.2.5 设f:AA是函数，若对任意aA，有f(a)=a，亦即f={‹a,a›|xA}则称f:AA为A上恒等函数，通常记为IA，因为恒等关系即是恒等函数由定义可知，A上恒等函数IA是双射函数Date13定义5.2.6 设A和B为集合，且AB，若函数fA: B{0,1}为1 xAfA(x)=0 否则则称fA为集合A的特征函数Date14特征函数建立了函数与集合的一一对应关系于是，可通过特征函数的计算来研究集合上的命题Date15定义5.2.7 设‹A,≤›和‹B,≤›为全序集，函数f:AB。

对于任意a,bA.①若a≤b，有f(a)≤f(b)，则称f为单调递增函数②若a≤b，有f(a)≥f(b)，则称f为单调递减函数Date16③若a≤b，且ab，有f(a)＜f(b)，则称f为严格单调递增函数④若a≥b，且ab，有f(a)＞f(b)，则称f为严格单调递减函数显然，严格单调递增函数是单调递增函数，严格单调递减函数是单调递减函数Date175.3 函数运算函数是一种特殊关系，对关系可以进行运算，自然对函数也需要讨论运算问题，即如何由已知函数得到新的函数Date181．函数复合利用两个具有一定性质的已知函数通过复合运算可以得到新的函数定理5.3.1 设f:AB和g:BC是函数，通过复合运算  ，可以得到新的从A到C的函数，记为g  f，即对任意aA，有(g  f)(x)=g(f(x))Date19注意，函数是一种关系，今用“”表示函数复合运算，记为g  f，这是“左复合”，它与关系的“右复合”f*g次序正好相反，即有g  f=f*gDate20推论1 若f,g,h都是函数，则(f  g)  h=f (g  h)本推论表明，函数复合运算是可结合的若对于集合A，f:AA，则函数f能同自身复合成任意次。

f的n次复合定义为：① f 0(x)=x② f n+1(x)=f(fn(x))，nNDate21定理5.3.2 设f:AB，g:BC① 若f:AB，g:BC都是满射，则g  f:AC也是满射② 若f:AB，g:BC都是单射，则g  f:AC也是单射③ 若f:AB，g:BC都是双射，则g  f:AC也是双射Date22定理5.3.3 若f:AB是函数，则f=f  IA=IB  f本定理揭示了，恒等函数在复合函数运算中的特殊性质，特别地，对于f:AA，有f  IA= IA  f=fDate232．函数逆运算给定关系R，其逆关系是存在，但对已知 一函数,它作为关系其逆是存在,但未必是函数. 例如,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:AB是双射，则f-1便是从B到A的函 数定理5.3.4 若f:AB是双射，则f-1:BA也 是双射Date24定义5.3.1 设f:AB是双射函数,称 f -1:BA是f的逆函数,习惯上常称f-1为f的反函数。

定理5.3.5 设f:AB是双射函数,则 f -1  f=IA，f  f-1=IB定理5.3.6 若f:AB是双射,则(f-1)-1=fDate255.4 基 数1．基数定义首先选取一个“标准集合”Nn={0,1,2,···,n-1}，再用双射函数为工具，给出集合基数的定义如下：Date26定义5.4.1 设A是集合，若f:NnA为双射函 数，则称集合A是有限集，A的基数是n，记为 |A|=n，或card A=n若集合A不是有限的，则 称A是无限集本定义表明了，对于有限集合A，可以用“ 数”数的方式来确定集合A的基数定理5.4.1 自然数集合N是无限集为了确定某些无穷集合的基数，选取第二 个“标准集合”N来度量这些集合Date27定义5.4.2 设A是集合，若f:NA为双射 函数，则称A的基数是0，记为|A|=0显然，存在从N到N的双射函数，故 |N|=0，0读作“阿列夫零”符号0是康托 引入的0是一个无法确定的数, 是一个抽象的描述Date28定义5.4.3 设A是集合，l若|A|=0，则称A是可数无限集；l若A是无限的且不可数的，则称A是不可数集或不可数无限集。

Date29在上述基数定义中，是使用两个“标准集合”Nn和N以及双射函数（或一一对应），引入了集合基数的概念这种方式可以把基数简单地 看作对集合指派一个符号，指派原则是：与Nn构成双射或一一对应的集合，指派它的基数是n，与N构成双射或一一对应的集合，指派它的基数为0指派空集的基数为0Date302．基数比较基数概念是有限集合元素个数的推广可数(无限)集的基数都等于0那么, 无限集的基数都一样吗? 有没有最大的基数呢？Date31在集合基数的基础上，可以建立相等关系和次序关系，进行基数比较和基数运算，这里仅讨论前者定义5.4.4 设A和B为任意集合(包括无限集)①若有一个从A到B的双射函数，则称A和B 有相同基数（或称A与B是等势），记为|A|=|B|（ 或AB）Date32②若有一个从A到B的单射函数，则称A的基数小于等于B的基数，记为|A|≤|B|③若有一个从A到B的单射函数，但不存在双射函数，则称A的基数小于B的基数，记为|A|＜|B|Date33由于在复合运算下，双射函数是封闭的，双射函数的逆函数（即常说反函数）是双射函数，因此等势关系有以下性质：定理5.4.3 等势是任何集合族上的等价关系。

Date34从上面定义及定理可知：①等势是集合族上的等价关系，它把集合 族划分成等价类，在同一等价类中的集合具有 相同的基数因此可以说：基数是在等势关系 下集合的等价类的特征或者说：基数是在等 势关系下集合的等价类的名称这实际上就是 基数的一种定义例如，3是等价类 {{a,b,c},{p,q,r},{1,2,3}}的名称（或特征）0 是自然数集合N所属等价类的名称Date35②要证明一个集合A有基数，只需选取基数 为的任意集合B，证明从A到B或从B到A存在一 个双射函数选取集合B的原则是使证明尽可能容易下面将不加证明地引入两个定理第一个定 理称为三分律第二定理表明：≤是反对称的Date36定理5.4.4 （Zermelo）设A和B是任意两个集合，则下述情况恰有一个成立：① |A|＜|B| ② |B|＜|A| ③ |A|=|B|Date37定理5.4.5 （Cantor-Schroder-Bernstein） 设A和B是任意两个集合，若|A|≤|B|和|B|≤|A|，则 |A|=|B|本定理对证明两集合具有相同基数提供了有 效的方法若能够构造一单射函数f:AB，则有 |A|≤|B|；又能构造另一个单射函数g:BC，以证 明|B|≤|A|。

于是根据本定理即可得出|A|=|B|特 别要注意，f和g不必是满射因为通常构造这样 两个单射函数比构造一个双射函数要容易许多Date38对于有限集，我们有：定理5.4.6 设A是有限集合，则|A|＜0对于无限集呢？我们有必要对无限集有所了解Date39有限集与无限集虽然是数量上的差别， 但是由“量变”而引起了“质”的变化，无限集有 着很多有限集所没有的一些特性，而有限集的 一些特性也不能任意推广到无限集中去，即使 有的能推广也要做某些意义上的修改下面我们先讨论无限集的一些特性Date40定理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SDate41无限集的这个特征可以作为区别无限集 与有限集的一个标志即有推论 一个集合为无限集的充分必要条件是它 必含有与其等势的真子集有了这个推论后，我们可以重新定义有限 集与无限集定义 一集合若存在与其等势的真子集则称其 为无限集，否则称为有限集。

Date42下面我们对无限集作进一步的探讨，我们讨论一种特殊类型的也是最常见的无限集——可数(无限)集的性质Date43定理5.4.8 每个无限集必包含一可数无限子集定理5.4.9 可数无限集的无限子集仍为一可数无限集由此可知，可数无限集。