离散数学-函数课件.ppt

1、第5章 函数第5章 函数5.1 函数的基本概念函数的基本概念5.2 反函数和复合函数反函数和复合函数5.3 集合的基数集合的基数返回总目录第5章 函数 5.1函数的基本概念 定义5.1.1设A和B是两个任意集合，f是A到B的二元关系，如果对于A中的每一个元素x，都存在B中惟一元素y，使得x,yf，则称f是A到B的函数或映射。记为f：AB。x,yf，常记为y=f(x)，x称为自变元或像源，y称为在f作用下x的函数值或像。由函数的定义可以看出，函数是一种特殊的二元关系。若f是A到B的函数。它与一般二元关系的区别如下：函数的定义中强调A中的每一个元素x有像，所以A=dom f。这称为像的存在性。函数

2、的定义中还强调像y是唯一的，称做像的惟一性。像的惟一性可以描述为：设f(x1)=y1且f(x2)=y2。如果x1=x2，那么y1=y2。或者，如果y1y2，那么x1x2。第5章 函 数第5章 函数 【例5.2】设 N为自然数集合，下列N上的二元关系是否为函数？f=x,2x|xN g=x,2|xN 解：f和g都是从自然数集合N到自然数集合N的函数，常记为f：NN，f(x)=2x和g：NN，g(x)=2。设A和B是两个任意集合，AB任意子集是A到B的二元关系，但不一定是A到B的函数。当A和B是有限集时，由定理4.1.1的证明过程可以看出，A到B的二元关系共有2|A|B|个，A到B的函数有多少个呢？

3、以下研究这个问题。设A和B是两个任意的集合，f|f：AB是A到B的所有函数构成的集合，常记为BA。读作B上A。第5章 函数 【例5.3】设 A=1,2,3，B=a,b，求BA。解：由A到B的函数有以下8个：f0=1,a,2,a,3,a f1=1,a,2,a,3,b f2=1,a,2,b,3,a f3=1,a,2,b,3,b f4=1,b,2,a,3,a f5=1,b,2,a,3,b f6=1,b,2,b,3,a f7=1,b,2,b,3,b BA=f0,f1,f2,f3,f4,f5,f6,f7 A到B的函数共8个，8=23=|B|A|。当A和B都是有限集时，这个结论可以推广。一般地说，若|A|

4、=m，|B|=n，则|BA|=nm=|B|A|。第5章 函数 定义5.1.2 设A和B是两个任意的集合，f：AB，A1A，集合f(x)|xA1称为集合A1在f下的像，记为f(A1)。集合A在f下的像 f(A)=f(x)|xA称为函数f的像。显然，函数f的像f(A)就是二元关系f的值域，即f(A)=ran f。【例5.4】设f：1,2,3 a,b，f=1,a,2,a,3,b，A1=1,2，试求A1在f下的像f(A1)和函数f的像f(A)。解：f(A1)=f(x)|xA1=f(1),f(2)=a f(A)=f(x)|xA=f(1),f(2),f(3)=a,b第5章 函数 定义5.1.3 设f：AB

5、，g：CD，若A=C，B=D且xA，有f(x)=g(x)，则称函数f和g相等，记为f=g。例如，函数f：NN，f(x)=x3 函数g：1,2,3 N，g(x)=x3 虽然函数f和g有相同的表达式x3，但是它们是两个不同的函数。如果把f和g看成二元关系，fNN，用列举法表示为：0,0,1,1,2,8,3,27,4,64,g1,2,3 N，用列举法表示为：0,0,1,1,2,8,3,27 按二元关系相等的条件衡量，它们也是不等的。函数相等和二元关系相等是一致的。第5章 函数 定义5.1.4 设f：AB，若f的值域ran f=B，则称f为满射。设f是A到B的函数，由定义不难看出，如果yB，都存在xA

6、，使得f(x)=y，则f是满射函数。例如，A=a,b,c,d，B=1,2,3，f是由A到B的函数，定义为：f=a,1,b,1,c,3,d,2 因为ran f=f(A)=1,2,3=B，所以f是满射。图5.2是f的示意图。由图5.2可得出如下的结论：若A、B是有限集，f：AB是满射，在f的示意图中，B中每个元素至少是一个有向边的终点且|A|B|第5章 函数 定义5.1.5 设f：AB，若yran f，存在惟一的xA，使得f(x)=y，则称f为单射。设f是A到B的函数，由定义不难看出，如果对于x1A，x2A，f(x1)=y1，f(x2)=y2。当y1=y2时，一定有x1=x2，则f是单射函数。当x

7、1x2时，一定有y1y2，则f是单射函数。【例5.5】设f：a,b2,4,6，定义 f=a,2,b,6函数f是否为单射？f是否为满射？第5章 函数 解：因为f(a)=2，f(b)=6，所以f是单射。因为 f 的值域ran f=2,62,4,6，所以f不是满射。图5.3是 f 的示意图。由图5.3可得出如下的结论：若A、B是有限集，f：AB是单射，在 f 的示意图中，B中每个像点是且仅是一条有向边的终点且|A|B|第5章 函数 定义5.1.6 设f：AB，若f既是单射，又是满射，则称f为双射。例如：A=1,2,3，B=a,b,c，f=1,a,2,c,3,b，f是A到B的双射函数，图5.4是f的示

8、意图。第5章 函数 若A、B是有限集，f：AB是双射，则 f一定是满射。故B中每个元素至少是一个有向边的终点；f 也是单射，故B中每个像点是且仅是一条有向边的终点。所以，在双射函数的示意图中，B中每一个元素是且仅是一条有向边的终点。若A、B是有限集，f：AB是双射，则 f 一定是满射，所以|A|B|；f 也是单射，所以|A|B|。于是|A|=|B|。第5章 函数 【例5.6】判断下列函数是否为单射、满射或双射。为什么？f：RR，f(x)=-x2+2x-1，其中，R是实数集合 f：IR，f(x)=ln x，其中，I是正整数集合 f：RI，f(x)=x，其中，x是不大于x的最大整数 f：RR，f(

9、x)=2x+1 f：RR，f(x)=，其中，R是正实数集合xx12第5章 函数 解：f(x)=-x2+2x-1=-(x-1)2，f 是开口向下的抛物线，不是单调函数，所以不是单射。在 x=1处取得极大值0，所以f 不是满射。f 既不是单射也不是满射。f 是单调增加函数。因此是单射，但不是满射，因为ran f=ln 1，ln 2，R f是满射，但不是单射，例如f(1.5)=1.5=1，而f(1.2)=1.2=1 f是单调增加函数且ran f=R，它既是单射，也是满射，因此它是双射。f 不是单射也不是满射。当x0时，f(x)；而当x时，f(x)。在x=1处函数f(x)取得极小值f(1)=2。因此它

10、既不是单射也不是满射。第5章 函数 定义5.1.7 设 f：AB，若yB，xA，都有 f(x)=y，则称 f为常函数。设IA是A上的恒等关系，它是A到A的函数，IA叫做A上的恒等函数。常记为y=IA(x)。设A是任意集合，AA，xA，定义：A0,1如下：叫做A的特征函数。设R是A上的等价关系，xR是 x形成的R等价类，A/R是A关于R的商集，f：AA/R，定义为：f(x)=xR，称f为A到商集A/R的自然函数或自然映射。AAxAxxxA01)()(xxA第5章 函数 例如，设A=a,b,c，A=b，B=a,b，则 A的特征函数 xA=a,0,b,1,c,0。B的特征函数 xB=a,1,b,1,

11、c,0。显然A的每一个子集都对应一个特征函数。又例如，设A=a,b,c，A上的等价关系R为：R=a,a,b,b,b,c,c,b,c,c，商集A/R=a,b,c f：AA/R f(a)=a f(b)=f(c)=b,c 不同的等价关系确定不同的自然映射，其中恒等关系确定的自然映射是双射，而其它的自然映射一般地说是满射。返回章目录第5章 函数 5.2反函数和复合函数 5.2.1 反函数 定理5.2.1 设 f：AB是双射函数，则 f 的逆关系f C是B到 A的双射函数。证明：先证逆关系 f C是B到 A的函数。因为 f 是函数，所以 f C是B到 A的二元关系。以下证明B到 A的二元关系f C是B到

12、 A的函数。yB，因为 f：AB是满射，所以，xA，使x,y f，由逆关系的定义得，y,x f C。设y1,x1 fC，y2,x2 fC，y1=y2，由逆关系的定义知，x1,y1 f，x2,y2 f，因为f是单射，所以x1=x2 故 f C是B到 A的函数。第5章 函数 再证 f C是满射。由定理4.2.7有ran f C=dom f。又因为 f 是A到B的函数，所以dom f=A。于是ran f C=A。所以f C是B到 A的满射。最后证f C是单射。设y1,x1 f C，y2,x2 f C且x1=x2，由逆关系的定义有x1,y1 f，x2,y2 f，又因为f是函数，必有y1=y2。所以 f

13、 C是单射。这就证明了f C是双射函数。第5章 函数 定义5.2.1 设f：AB是双射函数，f的逆关系f C是B到 A的双射函数。称双射函数f C为f的反函数，记为：f-1。例如，设A=1,2,3，B=a,b,c。f=1,a,2,c,3,b 显然，f是A到B的双射函数。f的逆关系 f C=a,1,c,2,b,3是B到A的双射函数，记为f-1，f 1是 f 的反函数。又如 g=1,a,2,a,3,b也是A到B的函数，但g不是满射，也不是单射，因而不是双射。逆关系 gC=a,1,a,2,b,3不是B到 A的函数。第5章 函数 定理5.2.2 设f：AB为双射函数，f-1：BA是f的反函数，则(f-

14、1)-1=f。证明：由定理5.2.1和定义5.2.1知(f-1)-1：AB，且为双射。xA，设 f(x)=y，则 f-1(y)=x，(f-1)-1(x)=y=f(x)，所以(f-1)-1=f。例如，设A=a,b,c，B=1,2,3。f：AB为双射函数，定义为：f=a,2,b,3,c,1则 f-1=2,a,3,b,1,c (f-1)-1=a,2,b,3,c,1=f第5章 函数 5.2.2 复合函数 第4章介绍了二元关系的复合运算。在那儿，二元关系的复合关系定义为：设X，Y，Z是集合，R XY，SYZ，集合 x,zxXzZ(y)(yYx,yRy,zS)叫做R和S的复合关系。记为R S。即 R S=

15、x,zxXzZ(y)(yYx,yRy,zS)将R S=x,zxXzZ(y)(yYx,yRy,zS)记为S R，即 S R=x,zxXzZ(y)(yYx,yRy,zS)第5章 函数 前者叫做R和S的复合关系。为了与前者区别，后者叫做二元关系S在二元关系R左边的复合关系，简称为S和R的左复合关系。前面已经讲过，函数是满足一定条件的二元关系，当然它可以进行左复合运算。函数的左复合关系描述为：设f：AB，g：CD，若f(A)C，集合 g f=a,d|aAdD(b)(bBa,bfb,dg)=a,d|aAdD(b)(bBb=f(a)d=g(b)第5章 函数 定义5.2.2 设f：AB，g：CD，若f(A)

16、C，集合 a,d|aAdD(b)(bBb=f(a)d=g(b)称为函数g在函数f左边的复合关系，记为g f。定理5.2.3 设f：AB，g：CD，f(A)C，则函数g在函数f左边的复合关系g f是A到D的函数。证明：aA，因为f是A到B函数，必存在惟一的bB，使得a,bf。即b=f(a)。而b=f(a)f(A)C，故bC。又因为g是C到D函数，必存在惟一的dD，使得b,dg。即d=g(b)。故由定义5.2.2，a,dg f，即g f(a)=d。所以g f是A到D的函数。第5章 函数 定义5.2.3 设f：AB，g：CD，若f(A)C，函数g在函数f左边的复合关系g f称为函数 g在函数f左边可

17、复合函数，简称为g和f的左复合函数或g和f的复合函数。仍然记为g f。g f是A到D的函数。推论 设f：AB，g：CD，f(A)C，则g f(x)=g(f(x)。证明：由定理5.2.3的证明过程可以看出，aA，b=f(a)且d=g(b)，g f(a)=d，于是，g f(a)=d=g(b)=g(f(a)。所以，g f(x)=g(f(x)。第5章 函数 定理5.2.4 设f：AB，g：BC，g f：AC。如果f和g都是满射，则g f也是满射。如果f和g都是单射，则g f也是单射。如果f和g都是双射，则g f也是双射。证明：cC，因为g是B到C的满射，bB，使c=g(b)。又因为f是A到B满射，aA

18、，使b=f(a)。于是，g f(a)=g(f(a)=g(b)=c，所以g f是满射。设a1A且a2A，a1a2，因为f是A到B单射，f(a1)f(a2)，f(a1)B，f(a2)B。又因为g是B到C单射，所以g(f(a1)g(f(a2)，即g f(a1)g f(a2)，故g f是单射。f和g都是双射，则f和g都是满射和单射，由和知，g f是满射和单射，故g f是双射。第5章 函数 在第4章的第2节中定义了二元关系的复合运算，介绍了复合运算性质。这些性质有：设RXY，SYZ，T ZW。(R S)T=R(S T)R IY=IX R=R R RC=IX，RC R=IY (R S)C=SC RC 函数

19、的复合运算也有类似的性质。以下几个定理介绍了这些性质。第5章 函数 定理5.2.5 设f：AB，g：BC，h：CD，则 h(g f)=(h g)f 证明：由定义5.2.3知，g f：AC，h(g f)：AD。类似地 h g：BD，(h g)f：AD。令f(x)=y，g(y)=z，h(z)=u。由定理5.2.3的推论知，g f(x)=g(f(x)=g(y)=z，h g(y)=h(g(y)=h(z)=u h(g f)(x)=h(g f)(x)=h(z)=u =h g(y)=h g(f(x)=(h g)f(x)所以 h(g f)=(h g)f 因为函数的复合运算满足结合律，所以可略去函数复合运算中的

20、括号，即用h g f记h(g f)=(h g)f，另外，还可以定义函数的幂：f 2=f f，f 3=f f f，第5章 函数 【例5.8】设R是实数集合，下面是R到R的函数f(x)=x+2，g(x)=x-2，h(x)=3x 先求g和f的复合函数g f，h和g的复合函数h g。再验证h(g f)=(h g)f 解：显然h(g f)：RR (h g)f：RR g f(x)=g(f(x)=g(x+2)=(x+2)-2=x h g(x)=h(g(x)=h(x-2)=3(x-2)=3x-6 h(g f)(x)=h(g f(x)=h(x)=3x (h g)f(x)=h g(f(x)=h g(x2)=3(x

21、2)-6=3x所以 h(g f)(x)=(h g)f(x)故 h(g f)=(h g)f 第5章 函数 定理5.2.6 设f：AB，IA是A上的恒等函数，IB是B上的恒等函数，则IB f=f IA=f 证明：先证f IA=f 由定义5.2.3知，f IA：AB，再由定理5.2.3的推论知 f IA(x)=f(IA(x)=f(x)所以 f IA=f 类似地可以证明IB f=f 定理5.2.7设f：AB为双射函数，f1：BA是f的反函数，则f-1 f=IA，f f-1=IB 证明：先证明f-1 f=IA 由定义5.2.3知f-1 f：AA。IA：AA。xA，设f(x)=y，则f-1(y)=x。f-

22、1 f(x)=f-1(f(x)=f-1(y)=x=IA(x)所以 f-1 f=IA 类似地可以证明f f-1=IB 第5章 函数 【例5.9】设 A=0,1,2，B=a,b,c，f：AB，定义为：f=0,c,1,a,2,b，求f1、f-1 f和f f-1，验证 f-1 f=IA和f f-1=IB 解：f-1=a,1,b,2,c,0 f-1 f=0,0,1,1,2,2 f f-1=a,a,b,b,c,c f-1 f：AA，IA：AA f-1 f(0)=0=IA(0)，f-1 f(1)=1=IA(1)，f-1 f(2)=2=IA(2)所以f-1 f=IA f f-1：BB，IB：BB f f-1(

23、a)=a=IB(a)，f f-1(b)=b=IB(b)，f f-1(c)=c=IB(c)所以f f-1=IB 第5章 函数 定理5.2.8 设f：AB，g：BC且 f和g均为双射函数，则(g f)-1=f-1 g-1 证明：因为f和g均为双射函数，f-1和g-1存在且 f-1：BA，g-1：CB所以 f-1 g-1：CA 另一方面，由定义5.2.3知，g f：AC。所以 (g f)-1：CA。zC，因为g为双射函数，yB 使g(y)=z，又因为f为双射函数，xA，使f(x)=y，于是，g f(x)=g(f(x)=g(y)=z故 (g f)-1(z)=x。另一方面，f-1(y)=x，g-1(z)

24、=y。于是，f-1 g-1(z)=f-1(g-1(z)=f-1(y)=x 所以 (g f)-1=f-1 g-1返回章目录第5章 函数 5.3集合的基数 5.3.1集合的等势 定义5.3.1 设A和B是集合，如果存在A到B的双射函数，则称集合A和集合B等势。记作AB。设A和B是有限集合，AB，则存在A到B的双射函数，根据5.1节中双射的性质，|A|=|B|。即A和B中元素的个数相等。【例5.10】设I是整数集，N是自然数集。试证明IN。证明：设f：IN，定义为：00122)(xxxxxf第5章 函数 以下证明f是I到N的双射函数。任取nN，若n是偶数，有 I且 0，使f()=2 =n；若n是奇数

25、，有 I且 0，使f()=-2()-1=n。所以f是满射。2n2n2n2n21n21n21n21n 按照这个定义将I中的元素如下排列与N中的元素对应：I 0 -1 1 -2 2 -3 3 -4 4 N 0 1 2 3 4 5 6 7 8 第5章 函数 若有n1I，n2I且n1n2。分下列4种情况讨论：假定n10且n20，则f(n1)-f(n2)=2n1-2n2=2(n1-n2)0，所以f(n1)f(n2)。假定n10且n20，则f(n1)-f(n2)=(-2n1-1)-(-2n2-1)=2(n2-n1)0，所以f(n1)f(n2)。假定n10且n20，则f(n1)-f(n2)=2n1-(-2n

26、2-1)=2(n1n2)+10(因为一个偶数与1的和或差永远不能为0)，所以f(n1)f(n2)。假定n10且n20，类似，同样有f(n1)f(n2)。所以f是单射。于是f是I到N的双射函数。IN第5章 函数 定理5.3.1设A，B，C是任意三个集合。则集合的等势有下列性质。自反性:即AA。对称性:即若AB，则BA。传递性:即若AB，BC，则AC。证明：仅证明。因为AB，BC，由等势的定义知，存在双射函数f：AB和双射函数g：BC，由定理5.2.4知，g f是A到C的双射函数。所以AC。第5章 函数 5.3.2有限集和无限集 定义5.3.2 如果集合A与集合0,1,2,n-1(n是某个自然数)

27、等势，则称A为有限集，如果集合A不是有限集，则称A为无限集。定理5.3.2 自然数集N是无限集。证明：nN，设f是任意集合0,1,2,n-1到N的函数，令k=1+maxf(0),f(1),f(n-1)，kN。x0,1,2,n-1,f(x)k。因此，f不是从0,1,2,n-1到N的满射函数。当然不是从0,1,2,n-1到N的双射函数。因为n和f都是任意的，所以，自然数集N不是有限集，而是无限集。定理5.3.3 有限集不与它的任何真子集等势。证明：设A为任一有限集，BA，则C=A-B。|B|=|A|-|C|A|，即|A|B|，根据5.1节中双射的性质，A与B之间不存在双射函数。A与B不等势。第5章

28、 函数 定理5.3.4 无限集必与其某个真子集等势。证明：首先证明在任何一个无限集a中，一定能取出一系列元素a1,a2,。在A中任取一个元素，记为a1。因为集合A是无限集，显然，集合A-a1不空。再从A-a1中取一个元素，记为a2。同样，集合A-a1,a2不空。继续做下去，可从A中取出一系列元素a1,a2,。记=a-a1,a2,，令=a2,a3,，显然A。f：A，定义为：f(ai)=ai+1 i=1,2,f(x)=x x 显然，f是A到的双射。A 根据定理5.3.3和定理5.3.4可以给出有限集与无限集的另外一个定义如下：不能和自己的任何真子集等势的集合称作有限集。能与自己的某个真子集等势的集

29、合称作无限集。第5章 函数 5.3.3集合的基数 定义5.3.3 将相互等势的集合归于同一类，对这样的每一类集合规定一个记号，称这个记号是这一类集合中每一个集合的基数或者势。集合A的势记为|A|。根据定义5.3.3，任何等势的集合具有相同的基数；而不等势的集合基数也不相同。规定有限集的势是该集合中元素的个数，空集的势为0。定义5.3.4 设N是自然数集合，凡与N等势的集合称为可数集或可列集，也叫无限可数集或无限可列集。通常记可数集的基数为0。读作“阿列夫零”。根据此定义，由例5.10知自然数集合N和整数集I都是可数集，|N|=|I|=0。第5章 函数 定理5.3.5 集合A是可数集的充分必要条

30、件是A的全部元素可以排成一个无限序列a0,a1,。证明：设A是可数集，下证A的全部元素可以排成一个无序列a0,a1,。因为A是可数集，由可数集的定义有NA。由等势的定义知，存在N到A的双射函数。设f：NA是双射函数，令an=f(n)A。则a可写成一个无限序列a0,a1,。设A的全部元素可以排成一个无限序列a0,a1,，下证A是可数集。因为A的全部元素可以排成一个无限序列a0,a1,，所以可定义N到A一个双射函数f(n)=an，故A是可数集。该定理说明一个能用自然数编号的无限集是可数集。第5章 函数 【例5.11】设N为自然数集，证明集合 M=x|x=10nnN是可数集。证明：令ai=10i，则

31、集合M可用列举法表示为：M=0,10,20,30,=a0,a1,M是能用自然数编号的无限集，根据定理5.3.5，M是可数集。定理5.3.6 任何无限集必含有可数子集。证明：设A为无限集，则A，在A中任取一个元素，记为a0。因为集合A是无限集，显然，集合A-a0不空。再从A-a0中取一个元素a1。同样A-a0,a1不空。可以继续做下去，从a中取出一系列元素a0,a1,令A=a0,a1,由定理5.3.5知，A是可数集。显然AA。第5章 函数 定理5.3.7 可数集的无限子集仍为可数集。证明：设a为可数集，它的元素编号如下：a0,a1,an,任取a的无限子集B，在a的元素中，从a0开始逐个检查，将遇

32、到的第一个B的元素记为 ，第二个记为 ，。因为B是无限集，所以B中的元素可排为 ，。由定理5.3.5，B是可数集。1ia1ia2ia2iania第5章 函数 定理5.3.8 可数个可数集的并集仍为可数集。证明：设可数个可数集分别为：A0=a00,a01,a02,a03,a04,A1=a10,a11,a12,a13,a14,A2=a20,a21,a22,a23,a24,A3=a30,a31,a32,a33,a34,p+q=h称为元素apq(p,q=0,1,2,)的高度。对上述集合的所有元素，先按高度大小编号，在同一高度中按q的值由小到大编号。这样就可以把并集A0A1A2中所有的元素按下列顺序(箭

33、头所指顺序)编成一列：第5章 函数 a00，a01，a02，a03，a04,a10，a11，a12，a13，a14,a20，a21，a22，a23，a24,a30，a31，a32，a33，a34,a00;a10,a01;a20,a11,a02;因为Ai，Aj可能有公共元素，这些公共元素在并集中是同一元素，在这一序列中去掉重复元素后的集合仍是可数的。所以并集A0A1A2是可数集。第5章 函数 【例5.12】在直角坐标系下，两坐标x，y均为整数的点(x,y)称为格点。证明全体格点构成可数集。证明：对每个固定的整数n，An=n,m|m是整数中的元素可排列为：n,0，n,1，n,-1，n,2，n,-2

34、，所以An是可数集。显然，右半平面上的格点全体构成的集合就是并集A0A1A2，这是可数个可数集的并，因而是可数集。左半平面上的格点全体构成的集合就是并集A-1A-2A-3，这也是可数个可数集的并，因而是可数集。因为可数集的并是可数集，所以平面上的格点全体构成的集合A0A1A2A-1A-2A-3是可数集。第5章 函数 【例5.13】证明有理数全体是可数集。证明：有理数r可写成分数 ，其中q0，p,q为互质的整数。把分数 记为序偶p,q，就成为平面上的格点。在平面上的全体格点构成的集合中删除q=0和p,q不互质的序偶得集合S，S就是有理数集合,它是平面上的全体格点构成的集合的无限子集，而平面上的全

35、体格点构成的集合是可数集。由定理5.3.7 知，有理数全体是可数集。qpqp第5章 函数 定理5.3.9 设R为实数集，则集合x|xR0 x1是不可数集。证明：如果x|xR0 x1是不可数集，那么x|xR0 x1自然是不可数集。所以先证x|xR0 x1是不可数集。如果x|xR0 x1是可数集，那么，其中所有实数可排成一数列：t1,t2,tn,，将这些实数用十进制无限小数表示为：t1=0.t11t12t13t14 t2=0.t21t22t23t24 t3=0.t31t32t33t34 第5章 函数 其中所有tij都是0，1，2，9十个数字中的一个，并且对每一个i，ti=0.ti1ti2ti3ti

36、4中无限项后不全为0。作十进制小数 a=0.a1a2a3a4 其中aitii，ai0，ai9，i=1,2,。这是办得到的。因为对任意的i，如tii=1，令ai=2，如tii1，那末取ai=1就行了。于是所作成的数a应该在集合x|xR0 x1中，但不会在数列t1,t2,tn,中，因为对于每个n，antnn，所以atn，这和ti|i=1,2,是区间x|xR0 x1中实数全体的假设相矛盾。因此x|xR0 x1是不可数集。从而x|xR0 x1也是不可数集。定义5.3.5 集合x|xR0 x1的基数称为连续点集的基数。记为。读作“阿列夫”。第5章 函数 5.3.4集合基数的比较 定义5.3.6 若集合A

37、到集合B存在一个单射，则称A的基数不大于B的基数或称A的基数小于等于B的基数，记为|A|B|。若集合A到集合B存在一个单射，但不存在双射，则称A的基数小于B的基数，记为|A|B|。定理5.3.10 设A和B是集合，如果|A|B|且|B|A|，则|A|=|B|证明从略。这个定理对证明集合的基数相同提供了有效方法。如果我们能够构造一单射函数f：AB，即说明有|A|B|。另外，如能够构造单射函数f：BA，即有|B|A|。根据本定理就得到|A|=|B|。第5章 函数 【例5.14】证明区间0,1与(0,1)有相同的基数。证明：作单射函数 f：(0,1)0,1，f(x)=x|(0,1)|0,1|g：0,

38、1(0,1)，f(x)=+|0,1|(0,1)|所以|(0,1)|=|0,1|定理5.3.11 实数集R的基数是。证明：先证集合R1=x|xR0 x1和实数集R等势。作R1到R的函数f：R1R f(x)=因为正切函数tg x在R1中是单调递增的，所以f是R1到R的双射函数。根据定义5.3.1，R1R，再由定义5.3.3和定义5.3.5，|R|=。2x21212 xtg第5章 函数 【例5.15】设A是自然数集合，B=(0,1)，|A|N|=0，|B|=，求证|AB|=。证明：设R是实数集合。定义一个从AB到R的函数。f(n,x)=nx 显然f是从AB到R的单射函数，所以|AB|R|，而|R|=

39、，故|AB|此外，作函数 g：(0,1)AB，g(x)=0,x因为g是单射的，|(0,1)|AB|，而|(0,1)|=，故|AB|。所以|AB|=。第5章 函数 定理5.3.12 设A是有限集合，则|A|0。证明：设|A|=n，则A0,1,2,n-1。定义函数 f：0,1,2,n-1N(N为自然数)，f(x)x。f是单射函数，故|A|N|=0 在定理5.3.2中已证得0,1,2,n-1到N之间不存在双射函数，所以|A|N|=0，即|A|0。又作函数 g：N0,1，g(n)=，g是单射函数，故|N|。因为N与0,1间不存在双射函数，所以|N|，因此0。|A|0成立。11n第5章 函数 定理5.3

40、.13 设A是无限集合，则0|A|。证明：因为A是无限集合，故A必包含一个可数无限子集A，作函数f：AA，f(x)=x，显然f是A到A单射函数，所以|A|A|而|A|=0，从而0|A|我们在定理5.3.12中已经证明了0。在定理5.3.13中证明了，当A是无限集合时，0|A|。但是直到目前为止还没有人能够证明：有一个无限集的基数严格介于0与之间。第5章 函数 下面定理说明，没有最大的基数，也没有最大的集合。定理5.3.14 设A是集合，P(A)是A的幂集合，则|A|P(A)|证明：先证明|A|P(A)|作函数f：AP(A)，f(a)=a，f是A到P(A)单射，故|A|P(A)|再证明|A|P(

41、A)|设|A|=|P(A)|，则必存在A到P(A)双射函数，设为g：AP(A)。对于任意aA，必有P(A)中惟一的g(a)与之对应。第5章 函数 如果ag(a)，称a是A的内部元素；若ag(a)，称a是A的外部元素。令S=a|aAag(a)，即S是A的外部元素集合。显然SA，故SP(A)。因为g是双射函数，故必有一个元素bA，使g(b)=S。若bS，则由S的定义，b是A的外部元素；又因为g(b)=S，bS=g(b)，此时，由A的内部元素的定义，b是A的内部元素。得出矛盾。若bS，则由S的定义，b是A的内部元素；又因为g(b)=S，bS=g(b)，此时，由A的外部元素的定义，b是A的外部元素。又得出矛盾。故|A|P(A)|由和得|A|P(A)|返回总目录返回章目录