1、集 合 论第四章 函 数 1 函数概念 2 逆函数和复合函数 3 基数概念 4*可数集与不可数集1/73第四章 函数函数是二元关系中特殊一类，也就是说，函数是一个特定类型二元关系。本章讨论是离散函数，它能把一个有穷集合变换到另一个有穷集合。例：在计算机上执行程序能够看作是函数变换：（自变量）输入-计算机-输出（函数值）在这章我们主要讨论：函数定义、特殊函数及其性质、函数运算。最终利用函数概念，尤其是双射函数，介绍一下无限集合基数问题。2/731 函数概念函数定义函数定义：定义定义设X和Y是任意两个集合，f是从XY一个关系，若对于每一个xX，都存在一个唯一 yY，能使 f，则称关系f为函数（映射
2、）,并记为：f：XY。讨论定义：（1）f：XY中，若，则称x为自变量，与x对应y称作f作用下象点（值）；也可用y=f(x)表示，y称作函数f在x点处值。3/731 函数概念（2）X中每一个元素都有定义，函数f定义域（3）对应于某一个，其值f(x)是唯一，即 （4）f 值域有时也记为Rf 集合 Y称为f 共域4/731 函数概念例：判定以下关系是否为函数是函数 不是函数 值不是唯一不是函数 5/731 函数概念例：设X=Y=R（实数）值是唯一 这不是函数，不满足值唯一性6/731 函数概念定义：定义：给定函数f:AB和g:CD，假如A=C，B=D，并对全部 或 都有f(x)=g(x)，则称函数f
3、和g是相等，即f=g。函数组成函数组成 例：设X=a,b,c，Y=0,1，则 中，有 个子集，7/731 函数概念但在64个子集中只有8个 符合函数定义，这8个函数为：8/731 函数概念讨论：从此例中可得到三点结论：（1）设|X|=m，|Y|=n，则函数f:XY中均是m个序偶集合；（即序偶个数=定义域基数）（2）X中每一个元素所对应象点f(x)可能是Y中n个，从X-Y全部函数个数 9/731 函数概念（3）XY有别函数个数和 子集个数关系为：即二个集合之间能组成函数个数比能组成二元关系数少得多 3.几个特殊函数几个特殊函数 定义：定义：给定函数f:XY，假如值域 则称f为满射函数。10/73
4、1 函数概念例：满射函数一定有：(1)|X|Y|定义：定义：给定f:XY，假如有 或者：则称f是入射函数。11/731 函数概念入射函数有：定义：定义：给定函数f:XY，假如f既是满射函数，又是入射函数，则称f为双射函数。（或称“一一对应函数”，“一对一满射函数”）12/731 函数概念双射函数一定有：（1）（值域）（2）（定义域）|X|=|Y|例：在全班同学集合中，设：X=序号，Y=姓名 则：f:XY是一双射函数（序号和姓名关系）13/732逆函数和复合函数设，则 现在讨论函数能否像二元关系那样得到逆函数呢？先举一例 例：定义一函数由例题可见：定义域不是Y，而是Y子集 不满足函数定义：即值是
5、唯一 是一个二元关系，而不是函数 14/732逆函数和复合函数（3）一个函数反函数存在话，则此函数一定是双射函数，而入射，满射函数逆关系均不满足函数定义（4）为了和逆关系相区分，函数f用“逆函数”来表示 定理：定理：假如f:XY是双射函数，则有：也为双射函数。定义：定义：设是一双射函数，称为f逆函数。15/732逆函数和复合函数定义：定义：设f:XY和g:WZ是二个函数，若 则：称g在函数f左边可复合。讨论定义：(1)两个函数复合是一个函数。(2)函数 称为f和g左复合，这里和习惯上符合函数书写求得一致。例：sin(ln x)，先求ln x，然后求sin(ln x)16/732逆函数和复合函数
6、定理：定理：设f:XY和g:YZ是二个函数，于是复合函数 是一个从X到Z函数，对于每一个 有：证实：有定义可知 是从XZ函数，即 设：xX 由f:XY得y=f(x)设：yY 由g:YZ得z=g(y)由 得：17/732逆函数和复合函数例：设X=1,2,3,Y=p,q,Z=a,b f:XY=g:YZ=则：是XZ函数上例函数复合图为：18/732逆函数和复合函数f:XY g:YZ：XZ函数复合运算不满足交换律。19/732逆函数和复合函数定理：定理：函数复合运算是可结合，即假如f,g,h均为函数，则有：证实：函数也是一个二元关系，二元关系复合是满足结合律，函数复合也是满足结合律。例：I是整数集合，
7、f：II定义成f(i)=2i+1，求复合函数 并证实它满足结合律。20/732逆函数和复合函数解：21/732逆函数和复合函数定理：定理：设f:XY，g:YZ，是一合成函数，则：(1)假如f和g都是满射函数，则 也是满射函数；(2)假如f和g都是入射函数，则 也是入射函数；(3)假如f和g都是双射函数，则 也是双射函数。证实：（2）设任一 f为入射函数，又g为入射函数,且 22/732逆函数和复合函数即 是任一，也是单射函数。可用一样方法证实（1）和（3）23/732逆函数和复合函数例：设 是负整数集合，定义二个双射函数f和g，f(x)=-x=，g(x)=x-1=，是一双射函数。24/732逆
8、函数和复合函数定义：定义：给定f:XY，假如对于全部 和某一个yY，有f(x)=y，则称f为常函数。例：25/732逆函数和复合函数定义：定义：给定，若对全部 有，即 则称 为恒等函数。例：26/732逆函数和复合函数定理：定理：对于任何函数f:XY，其中 是XX恒等函数，是YY恒等函数，则有 XXYY27/732逆函数和复合函数定理：定理：假如函数f:XY有逆函数 则 且 证实：设任一，则 此定理说明：可用双射函数f和 复合来生成恒等函数。28/732逆函数和复合函数定理：定理：若f是一双射函数，则 证实：设任一 则 定理：定理：设f:XY和g:YZ,且f和g均为双射函数，则有 29/732
9、逆函数和复合函数证实：由给定条件f,g均为双射函数,则均为双射函数 设任一 则y=f(x)，z=g(y)且 x是任意 有 30/733基数概念1.基数概念基数概念对于有限集：集合中不一样元素个数。对于无限集：？是否全部没有限集基数都一样？为了比较两个集合“大小”，确定有限集和无限集概念，我们首先引进自然数集合。定义定义给定集合A，A+=AA，称A+是A后继集合。利用后继集合概念来定义自然数集合0，1，2，31/733基数概念设A=，则A后继集合可写成：A+=，（A+）+=，（A+）+）+=，=，令：=0 则+=0+=1，（+）+=1+=2上述求0后继集合而得到N=0，1，2，Peano公理公理
10、 (1)0N (这里要求0=)(2)nNn+N (这里n+是n后继数)(3)若SN，且()0S ()nSn+S，则可得S=N32/733基数概念定义：定义：给定二个集合P和Q，假如我们对P中每一个不一样元素与Q中每一个不一样元素能够分别两两成对，则我们说P中元素和Q中元素存在着一一对应。例:P=1,3,52n-1,奇正数，Q=2,4,62n,偶正数则P和Q之间存在着一一对应，其函数关系为：f:PQ，f(n)=n+1，定义：定义：当且仅当集合A元素与集合B元素之间 存在着一一对应，则称A与B是等势，记作：AB。例：在 集合中，奇整数和偶整数集合是等势。f:AB,f(x)=(x+1),f(1)=2
11、,f(3)=433/733基数概念例：N和正偶整数集合E是等势。证实：作一函数f:NE，且对任一，有f(n)=2n，则 为一一对应函数，有NE。例：推广到对于有限集合，此定义也是适用 设：A=1,2,3,4,5，B=a,b,c,d,e，定义一函数f=f为一双射函数，AB(|A|=|B|)34/733基数概念定理：定理：集合族上等势关系是一等价关系 证实：设集合族为S,任一 则必有（AA）,自反若AB，则BA，对称若AB BC，则AC，可传递例：P为全班同学集合，P上同姓关系是一等价关系，其集合族S=张李 则同姓关系中等势关系是一等价关系，即若张李等势关系是一等价关系。35/733基数概念定义：
12、定义：假如从集合0，1，2，n-1是到集合A双射函数，那么称A是有限集合，若集合A不是有限，则它一定是无限。此定义也可叙述为：基数为某一自然数任何集合是有限集合，反之为无限集合。定理：定理：自然数集合N是无限集合。证实：设 作一f:0,1,2n-1N函数 f(x)=x 36/733基数概念只要证实它不是双射函数，则N一定为无限集合 定义一个k，设k=1+maxf(0),f(1)f(n),则中元素不能和k对应 n和f是任意，N一定是无限集合假如两个集合能够建立双射函数，则两集合元素间必一一对应，该两集合含有相同基数。37/734可数集与不可数集定义：定义：与自然数集合等势任何集合称为可数集合（或
13、称可数无限集合），它们基数等于等于 例：则|A|=|B|=|C|=|D|=38/734可数集与不可数集定理：实数子集(0,1)是不可数集。证实：设集合（用反证法）R1是任一实数必可写成无限十进制小数其中ai是0，1，2.9中某个数这里，我们要求，全部有限小数都写成以9为循步骤循环小数（比如0.2写成0.19999.）现设R1是可数集，则它元素可编号以下：39/734可数集与不可数集而一切适合0 x1实数应该完全在其中，现在我们结构一个新实数40/734可数集与不可数集所以biiaii，且b也是(0,1)区间一个数，即bR1。但显然b与全部实数a1,a2,a3都不相同。所以bR1，这就产生了矛盾
14、。R1是一个不可数集。以上定理说明集合R1与自然数集N属于不一样基数类。我们用 表示R1基数。41/734可数集与不可数集定理：定理：实数R是不可数集，而且它基数就是证实：定义函数这是一个由R1到R双射，所以R也是不可数集，且含有连续基数42/73集合论小结经过第三，第四章学习应该到达下面基本要求：（1 1）能够正确地表示一个集合，会画文氏图。（2 2）能判定元素是否属于给定集合。（3 3）能判断两个集合之间是否存在包含、相等或真包含关系。（4 4）能熟悉地进行集合并，交，相对补，绝对补，对称差运算，会计算幂集。（5 5）能正确地使用集合表示式、关系矩阵和关系图表示给定二元关系。（6 6）给定
15、A上关系R（可能是集合表示式，也可能是关系矩阵或关系图），能判别R性质。43/73集合论小结（7）给定关系R和S，求RS；给定A上关系R，求Rn，r(R)，s(R)，t(R)。（8）给定A上等价关系R，求全部等价类和商集A/R，或者求与R相对应划分，以及给定A划分，求对应等价关系。（9）给定A上偏序关系，画出偏序集哈斯图；给定偏序集哈斯图，求A和集合表示式。（10）确定偏序集极大元、极小元、最大元、最小元、最大下界和最小上界。（11）给定集合A，B和f，判别f是否为A到B函数，假如是，说明是否为入射、满射、双射。44/733基数概念1.基数概念基数概念对于有限集：集合中不一样元素个数。对于无限
16、集：？是否全部没有限集基数都一样？为了比较两个集合“大小”，确定有限集和无限集概念，我们首先引进自然数集合。定义定义给定集合A，A+=AA，称A+是A后继集合。利用后继集合概念来定义自然数集合0，1，2，45/733基数概念设A=，则A后继集合可写成：A+=，（A+）+=，（A+）+）+=，=，令：=0 则+=0+=1，（+）+=1+=2上述求0后继集合而得到N=0，1，2，Peano公理公理 (1)0N (这里要求0=)(2)nNn+N (这里n+是n后继数)(3)若SN，且()0S ()nSn+S，则可得S=N46/733基数概念定义：定义：给定二个集合P和Q，假如我们对P中每一个不一样元
17、素与Q中每一个不一样元素能够分别两两成对，则我们说P中元素和Q中元素存在着一一对应。例:P=1,3,52n-1,奇整数，Q=2,4,62n,偶整数则P和Q之间存在着一一对应，其函数关系为：f:PQ，f(n)=n+1，定义：定义：当且仅当集合A元素与集合B元素之间 存在着一一对应，则称A与B是等势，记作：AB。例：在 集合中，奇整数和偶整数集合是等势。f:AB,f(x)=(x+1),f(1)=2,f(3)=447/733基数概念例：N和正偶整数集合E是等势。证实：作一函数f:NE，且对任一，有f(n)=2n，则 为一一对应函数，有NE。例：推广到对于有限集合，此定义也是适用 设：A=1,2,3,
18、4,5，B=a,b,c,d,e，定义一函数f=f为一双射函数，AB(|A|=|B|)48/733基数概念定理：定理：集合族上等势关系是一等价关系 证实：设集合族为S,任一 则必有（AA）,自反若AB，则BA，对称若AB BC，则AC，可传递例：P为全班同学集合，P上同姓关系是一等价关系，其集合族S=张李 则同姓关系中等势关系是一等价关系。49/733基数概念定义：定义：假如f是从集合0，1，2，n-1是到集合A双射函数，那么称A是有限集合，若集合A不是有限，则它一定是无限。此定义也可叙述为：基数为某一自然数任何集合是有限集合，反之为无限集合。定理：定理：自然数集合N是无限集合。证实：设 f 是
19、任意从0,1,2n-1N函数 50/733基数概念定义一个k，设k=1+maxf(0),f(1)f(n-1),则中元素不能和k对应 因为n和f是任意，N一定是无限集合假如两个集合能够建立双射函数，则两集合元素间必一一对应，该两集合含有相同势。但51/734可数集与不可数集定义：定义：与自然数集合等势任何集合称为可数集合（或称可数无限集合），它们基数等于 例：则|A|=|B|=|C|=|D|=52/734可数集与不可数集定理：实数子集(0,1)是不可数集。证实：设集合（用反证法）R1是任一实数必可写成无限十进制小数其中ai是0，1，2.9中某个数这里，我们要求，全部有限小数都写成以9为循步骤循环
20、小数（比如0.2写成0.19999.）现设R1是可数集，则它元素可编号以下：53/734可数集与不可数集而一切适合0 x1实数应该完全在其中，现在我们结构一个新实数54/734可数集与不可数集所以biiaii，且b也是(0,1)区间一个数，即bR1。但显然b与全部实数a1,a2,a3都不相同。所以bR1，这就产生了矛盾。R1是一个不可数集。以上定理说明集合R1与自然数集N属于不一样基数类。我们用 表示R1基数。55/734可数集与不可数集定理：定理：实数R是不可数集，而且它基数就是证实：定义函数这是一个由R1到R双射，所以R也是不可数集，且含有连续基数56/73集合论小结经过第三，第四章学习应
21、该到达下面基本要求：（1 1）能够正确地表示一个集合，会画文氏图。（2 2）能判定元素是否属于给定集合。（3 3）能判断两个集合之间是否存在包含、相等或真包含关系。（4 4）能熟悉地进行集合并，交，相对补，绝对补，对称差运算，会计算幂集。（5 5）能正确地使用集合表示式、关系矩阵和关系图表示给定二元关系。（6 6）给定A上关系R（可能是集合表示式，也可能是关系矩阵或关系图），能判别R性质。57/73集合论小结（7 7）给定关系R和S，求RS；给定A上关系R，求Rn，r(R)，s(R)，t(R)。（8 8）给定A上等价关系R，求全部等价类和商集A/R，或者求与R相对应划分，以及给定A划分，求对应
22、等价关系。（9 9）给定A上偏序关系，画出偏序集哈斯图；给定偏序集哈斯图，求A和集合表示式。（1010）确定偏序集极大元、极小元、最大元、最小元、最大下界和最小上界。（1111）给定集合A，B和f，判别f是否为A到B函数，假如是，说明是否为入射、满射、双射。58/73例题选讲例例1.设A，B，C，D代表任意集合，判断以下命题是否恒真，假如不是，请举一反例。(1)AB CDAC BD(2)AB CDA-DB-C(3)AB B=A(B-A)(4)A-B=B-A A=B解：(1)不为真。举反例以下：令A1,B=1,4,C=2,D=2,3则AB且CD，但AC BD，与结论矛盾。59/73例题选讲(2)
23、因为CDDC，又由A B可得 ADBC即AD BC成立。(3)因为A(BA)=A B故有：B=A(BA)B=A B A B即A B充要条件为B=A B或A=AB或AB=60/73例题选讲(4)易见，当A=B时，必有A-B=B-A 由A-B=B-A得(A-B)B=(B-A)B 即：(AB)B=(BA)B 即：B-A=BA同理可证：AB从而得到：AB61/73例题选讲例例2.设：A、B是任意集合(1)试证实(A)(B)=(AB)(2)(A)(B)=(AB)成立吗？为何？解：(1)证实 S(A)(B)，则S(A)且S(B)，所以：SA且SB S AB 即S(AB)(A)(B)(AB)反之，设S(AB
24、)，则S AB，62/73例题选讲所以SA且SBS(A)且S(B)于是S(A)(B)(AB)(A)(B)由上知(A)(B)(AB)(2)(A)(B)(AB)成立。其证实以下：设：S(A)(B)，则S(A)或S(B)所以 SA或SB SAB即S(AB)故(A)(B)(AB)成立63/73例题选讲(AB)(A)(B)不成立设：S(AB)，则SAB。但此时无法推断SA，也无法推断SB，所以既不能得出S(A)，也不能得出S(B)。比如：设 A=a,c，B=c,b则 AB=a,b,c，设 S=a,b，则SAB即 S(AB)但 S(A)且S(B)所以 S(A)(B)64/73例题选讲例3.设S=1,2,3
25、,10，是S上整除关系，求 哈斯图，并求其中最大元，最小元。最小上界，最大下界。分析：画哈斯图关键在于确定结点层次和元素间盖住关系。画图基本步骤是：(1)确定偏序集中极小元，并将这些极小元放在哈斯图最底层；(2)若第n层元素已确定完成，从A中剩下元素中选取最少能盖住第n层中一个元素元素，将这些元素放在哈斯图第n+1层。65/73例题选讲在排列结点位置时，注意把盖住较多元素结点放在中间，将只盖住一个元素结点放在两边，以降低连线交叉；(3)将相邻两层结点依据盖住关系进行连线。66/73例题选讲在画哈斯图时应该注意下面几个问题：(1)哈斯图中不应该出现三角形，假如出现三角形，一定是盖住关系没找对。纠
26、正方法是重新考查这3个元素在偏序集中次序，然后将不满足盖住关系那条边去掉。(2)哈斯图中不应该出现水平线段。出现这种错误原因在于没有将“较大”元素放在“较小”元素上方。纠正时只要依据“大小”次序将“较大”元素放到更高一层，将水平线改为斜线就能够了。(3)哈斯图中要尽可能降低线交叉。图形中线交叉多少主要取决于同一层结点排列次序，67/73例题选讲假如出现交叉过多，能够适当调整结点排列次序。最终，怎样确定哈斯图中极大元、极小元、最大元、最小元、最小上界和最大下界。方法以下：(1)假如图中有孤立结点，那么这个结点既是极小元，也是极大元，而且图中既无最小元，也无最大元。（除只有唯一孤立结点情况）(2)
27、除了孤立结点以外，其它极小元是图中全部向下通路终点，其它极大元是图中全部向上通路终点。68/73例题选讲例例4.设Z+=x|xZx0，1，2是Z+2个划分，1=x|x Z+，2=Z+，求划分1，2所确定Z+上等价关系。分析：等价关系和划分是两个不一样概念。等价关系是有序正确集合，而划分是子集集合。但对于给定集合A，A上等价关系R和A划分是一一对应。即：Rx 和y在同一划分块里。本题中，1划分块都是单元集，没有含两个以上 元素划分块；69/73例题选讲2中只有一个划分块Z+，Z+包含了集合中全体元素。R1就是Z+上恒等关系；R2就是Z+上全域关系。例例5.对下面给定集合A和B，结构从A到B双射函
28、数 分析：结构从集合A到B双射函数，普通可采取下面方法：(1)若A，B都是有穷集合，能够先用列元素方法表示A，B70/73例题选讲然后，次序将A中元素与B中元素建立对应。(2)若A，B是实数区间，能够采取直线方程作为从A到B双射函数。比如：A1,2，B2,6是实数区间。先将A，B区间分别标识在直角坐标系x轴和y轴上，过(1,2)和(2,6)两点直线方程将A中每个数映到B中每一个数。所以，该直线方程：就是从A到B双射函数。71/73例题选讲这种经过直线方程结构双射函数方法对任意两个同类型实数区间(同为闭区间、开区间或半开半闭区间)都是适用。另外，对于一些特殊实数区间，可能选择其它严格单调初等函数更方便。对于本题:(3)A是一个无穷集合，B是自然数集N 只须将A中元素排成一个有序序列，且指定这个序列初始元素，这就叫做把A“良序化”。比如：结构从整数集Z到自然数集N双射，以下排列：72/73例题选讲Z：0，-1，1，-2，2，-3，3，.N：0，1，2，3，4，5，6，.即：显然f是从Z到N双射。73/73
