第五章-函数与基数课件

第五章函数与基数5.1函数基本概念5.2函数类型5.3函数运算5.4基数7/23/202315.1函数基本概念函数也常称为映射或变换，其定义如下：

定义5.1.1

设A和B是任意两个集合，且f是从A到B的关系，若对每一个xA，都存在唯一的yB，使‹x,y›f，则称f为从A到B的函数，并记作f:AB。A称为函数f的定义域，即D(f)=A，B称为函数f的陪域，R(f)称为函数f的值域，且R(f)B。有时也用f(A)表示函数f的值域，即7/23/20232f(A)=R(f)={y|yB∧(x)(xA∧y=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。7/23/20233从本定义可以看出，从A到B的函数f和一般从A到B的二元关系之不同有以下两点：①A的每一元素都必须是f的有序对的第一分量。②若f(x)=y，则函数F在x处的值是唯一的，即f(x)=y∧f(x)=zy=z7/23/20234

定义5.1.2

设f:AB，g:CD，若A=C，B=D，且对每一xA都有f(x)=g(x)，则称函数f和g相等，记为f=g。本定义表明了，两函数相等，它们必须有相同的定义域、陪域和有序对集合。7/23/20235下面讨论由集合A和B，构成这样函数f:AB会有多少呢？或者说，在AB的所有子集中，是全部还是部分子集可以定义函数？令BA表示这些函数的集合(称为由集合A到集合B的超幂)，即BA={f|f:AB}

设|A|=m，|B|=n，则|BA|=nm。(这里|A|表示集合A的基数,或者叫势)这是因为对每个自变元，它的函数值都有n种取法，故总共有nm种从A到B的函数。7/23/202365.2函数类型根据函数具有的不同性质，可以将函数分成不同的类型。本节将定义这些函数，并给出相应的术语。7/23/20237

定义5.2.1

设f:AB是函数，若R(f)=B，即对任意bB，存在aA，使得f(a)=b，或形式表为：(y)(yB(x)(xA∧f(x)=y))

则称f:AB是满射函数，或称函数f:AB是满射的。本定义表明了，在函数f的作用下，B中每个元素b，都至少是A中某元素a的像，因此，若A和B是有限集合，存在满射函数f:AB，则|A|≥|B|。7/23/20238

定义5.2.2

设f:AB是函数，对任意的a，bA，且ab，都有f(a)f(b)，或形式表为(x)(y)(x,yA∧xyf(x)f(y))

则称f:AB是单射函数，或称函数f:AB是单射的。本定义揭示了，A中不同的元素，其在B中像也是不同的。于是，若A的B是有限集合，存在单射函数f:AB，则|A|≤|B|。7/23/20239

定义5.2.3

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

定义5.2.4

设f:AB是函数，若存在bB，使对任意aA有f(a)=b，即f(A)={b}，则称f:AB为常值函数。7/23/202312

定义5.2.5

设f:AA是函数，若对任意aA，有f(a)=a，亦即f={‹a,a›|xA}

则称f:AA为A上恒等函数，通常记为IA，因为恒等关系即是恒等函数。由定义可知，A上恒等函数IA是双射函数。7/23/202313

定义5.2.6

设A和B为集合，且AB，若函数fA:B{0,1}为

1xA

fA(x)= 0否则则称fA为集合A的特征函数。特征函数建立了函数与集合的一一对应关系。于是，可通过特征函数的计算来研究集合上的命题。7/23/202314

定义5.2.7

设‹A,≤›和‹B,≤›为全序集，函数f:AB。对于任意a,bA.①若a≤b，有f(a)≤f(b)，则称f为单调递增函数。②若a≤b，有f(a)≥f(b)，则称f为单调递减函数。7/23/202315③若a≤b，且ab，有f(a)＜f(b)，则称f为严格单调递增函数。④若a≥b，且ab，有f(a)＜f(b)，则称f为严格单调递减函数。显然，严格单调递增函数是单调递增函数，严格单调递减函数是单调递减函数。7/23/2023165.3函数运算函数是一种特殊关系，对关系可以进行运算，自然对函数也需要讨论运算问题，即如何由已知函数得到新的函数。7/23/2023171．函数复合利用两个具有一定性质的已知函数通过复合运算可以得到新的函数。

定理5.3.1

设f:AB和g:BC是函数，通过复合运算

，可以得到新的从A到C的函数，记为g

f，即对任意aA，有(gf)(x)=g(f(x))。7/23/202318注意，函数是一种关系，今用“”表示函数复合运算，记为gf，这是“左复合”，它与关系的“右复合”f*g次序正好相反，即有g

f=f*g。7/23/202319推论1

若f,g,h都是函数，则(f

g)h=f(gh)。本推论表明，函数复合运算是可结合的。若对于集合A，f:AA，则函数f能同自身复合成任意次。f的n次复合定义为：①f0(x)=x②fn+1(x)=f(fn(x))，nN。7/23/202320定理5.3.2

设f:AB，g:BC①若f:AB，g:BC都是满射，则g

f:AC也是满射。②若f:AB，g:BC都是单射，则g

f:AC也是单射。③若f:AB，g:BC都是双射，则g

f:AC也是双射。7/23/202321定理5.3.3

若f:AB是函数，则f=fIA=IBf本定理揭示了，恒等函数在复合函数运算中的特殊性质，特别地，对于f:AA，有fIA=IA

f=f。7/23/2023222．函数逆运算给定关系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:AB是双射，则f-1便是从B到A的函数。

定理5.3.4

若f:AB是双射，则f-1:BA也是双射。7/23/202323

定义5.3.1

设f:AB是双射函数,称f-1:BA是f的逆函数,习惯上常称f-1为f的反函数。

定理5.3.5

设f:AB是双射函数,则

f-1f=IA，ff-1=IB

定理5.3.6

若f:AB是双射,则(f-1)-1=f。7/23/2023245.4基数1．基数定义首先选取一个“标准集合”Nn={0,1,2,···,n-1}，再用双射函数为工具，给出集合基数的定义如下：7/23/202325

定义5.4.1

设A是集合，若f:NnA为双射函数，则称集合A是有限集，A的基数是n，记为|A|=n，或cardA=n。若集合A不是有限的，则称A是无限集。本定义表明了，对于有限集合A，可以用“数”数的方式来确定集合A的基数。

定理5.4.1

自然数集合N是无限集。为了确定某些无穷集合的基数，选取第二个“标准集合”N来度量这些集合。7/23/202326

定义5.4.2

设A是集合，若f:NA为双射函数，则称A的基数是0，记为|A|=0。显然，存在从N到N的双射函数，故|N|=0，0读作“阿列夫零”。符号0是康托引入的。0是一个无法确定的数,是一个抽象的描述。

7/23/202327

定义5.4.3

设A是集合，若|A|=0，则称A是可数无限集；若A是无限的且不可数的，则称A是不可数集或不可数无限集。7/23/202328在上述基数定义中，是使用两个“标准集合”Nn和N以及双射函数（或一一对应），引入了集合基数的概念。这种方式可以把基数简单地看作对集合指派一个符号，指派原则是：与Nn构成双射或一一对应的集合，指派它的基数是n，与N构成双射或一一对应的集合，指派它的基数为0。指派空集的基数为0。7/23/2023292．基数比较基数概念是有限集合元素个数的推广。可数(无限)集的基数都等于0。那么,无限集的基数都一样吗?有没有最大的基数呢？7/23/202330在集合基数的基础上，可以建立相等关系和次序关系，进行基数比较和基数运算，这里仅讨论前者。

定义5.4.4

设A和B为任意集合(包括无限集)①若有一个从A到B的双射函数，则称A和B有相同基数（或称A与B是等势），记为|A|=|B|（或AB）。7/23/202331②若有一个从A到B的单射函数，则称A的基数小于等于B的基数，记为|A|≤|B|。③若有一个从A到B的单射函数，但不存在双射函数，则称A的基数小于B的基数，记为|A|＜|B|。7/23/202332由于在复合运算下，双射函数是封闭的，双射函数的逆函数（即常说反函数）是双射函数，因此等势关系有以下性质：

定理5.4.3

等势是任何集合族上的等价关系。7/23/202333从上面定义及定理可知：①等势是集合族上的等价关系，它把集合族划分成等价类，在同一等价类中的集合具有相同的基数。因此可以说：基数是在等势关系下集合的等价类的特征。或者说：基数是在等势关系下集合的等价类的名称。这实际上就是基数的一种定义。例如，3是等价类{{a,b,c},{p,q,r},{1,2,3}}的名称（或特征）。0是自然数集合N所属等价类的名称。7/23/202334②要证明一个集合A有基数，只需选取基数为的任意集合B，证明从A到B或从B到A存在一个双射函数。选取集合B的原则是使证明尽可能容易。下面将不加证明地引入两个定理。第一个定理称为三分律。第二定理表明：≤是反对称的。7/23/202335

定理5.4.4

（Zermelo）设A和B是任意两个集合，则下述情况恰有一个成立：①|A|＜|B|②|B|＜|A|③|A|=|B|7/23/202336

定理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不必是满射。因为通常构造这样两个单射函数比构造一个双射函数要容易许多。7/23/202337对于有限集，我们有：定理5.4.6

设A是有限集合，则|A|＜0。对于无限集呢？我们有必要对无限集有所了解7/23/202338有限集与无限集虽然是数量上的差别，但是由“量变”而引起了“质”的变化，无限集有着很多有限集所没有的一些特性，而有限集的一些特性也不能任意推广到无限集中去，即使有的能推广也要做某些意义上的修改。下面我们先讨论无限集的一些特性7/23/202339

定理5.4.7

无限集必含有与其等势的真子集。例如：自然数集N={0,1,2,3,…}与其真子集S={1,3,5,7,…}均为无限集，且NS。这是因为它们之间存在双射（一一对应）：N:01234…↕↕↕↕↕S:13579…这种一一对应关系可以写成s=2n+1,其中nN,sS7/23/202340无限集的这个特征可以作为区别无限集与有限集的一个标志。即有推论一个集合为无限集的充分必要条件是它必含有与其等势的真子集。有了这个推论后，我们可以重新定义有限集与无限集定义一集合若存在与其等势的真子集则称其为无限集，否则称为有限集。7/23/202341下面我们对无限集作进一步的探讨，我们讨论一种特殊类型的也是最常见的无限集——可数(无限)集的性质。7/23/202342定理5.4.8

每个无限集必包含一可数无限子集。定理5.4.9

可数无限集的无限子集仍为一可数无限集。由此可知，可数无限集是无限集中的最小集合。从而有定理5.4.10

0是最小无限集合的基