交大数理逻辑课件11-1 函数

1、第11章 函 数11.1 函数和选择公理11.2 函数的合成和函数的逆11.3 函数的性质定义 设 f：XY,(1) 若ran( f ) = Y, 则称 f 是满射. (2)若x1,x2X, x1x2, 都有f(x1)f(x2) ,都称 f 是单射. (3)若 f 既是满射又是单射的, 则称 f 是双射.x1x2x3y1y2XY满射函数的分类|X|Y|x1x2x3y1y2Yy3Xy4单射f(x1) = f(x2) x1= x2x1x2x3y1y2Yy3X双射|X|=|Y|判断下面函数是否为单射, 满射, 双射 f：RR, f(x)=x2+2x1 在x=1取得极大值0. 既不单射也不满射。f：Z

2、 + R, f(x)=lnx 单调上升, 是单射. 但不满射, ranf=ln1, ln2, .f：RZ, f(x)= x 满射, 但不是单射, 例如 f(1.5)=f(1.2)=1.f：RR, f(x)=2x+1 满射、单射、双射, 因为它是单调的并且ranf=R.f：R+R +, f(x)=(x2+1)/x 有极小值f(1)=2. 该函数既不单射也不满射. 构造从A到B的双射函数一、有穷集之间的构造例 A=P(1,2,3), B=0,11,2,3解： A=,1,2,3,1,2,1,3,2,3,1,2,3. B= f0, f1, , f7 , 其中 f0=, f1=, f2=, f3=, f

3、4=, f5=, f6=, f7=,.令 f：AB, f()=f0, f(1)=f1, f(2)=f2, f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f7二、实数区间之间构造双射构造方法：直线方程例 A=0,1 B=1/4,1/2构造双射 f :AB构造从A到B的双射函数（续）解1： 令 f：0,11/4,1/2 f(x)=(x+1)/4 解2： 令 f：1, 01/4,1/2 f(x)=-x/4+1/2=-(x-2)/4 构造从A到B的双射函数（续）三、A 与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始 按

4、照次序与自然数对应例 A=Z, B=N，构造双射 f：AB 将Z中元素以下列顺序排列并与N中元素对应： Z：0 1 1 2 2 3 3 N：0 1 2 3 4 5 6 则这种对应所表示的函数是： 构造从A到B的双射函数（续） 三、A 与自然数集合之间构造双射例： A=NN， B=N，构造双射 f：AB 将A中元素以下列顺序排列并与N中元素对应： 则对应所表示的函数是：11.1.3常用的函数 1. 设f：AB, 若存在 cB 使得 xA 都有 f(x)=c, 则称 f：AB是常函数. 2. 称 A 上的恒等关系 IA为 A 上的恒等函数, 对所有 的 xA 都有 IA(x)=x. 3. 设 f：

5、RR，如果对任意的 x1, x2R，x1 x2, 就 有 f(x1) f(x2), 则称 f 为单调递增的；如果对任意的 x1, x2A, x1 x2, 就有 f(x1) f(x2), 则称 f 为 严格单调递增 的. 类似可以定义单调递减 和严格单调递减 的函数.集合的特征函数设 A 为集合, A A, A 的 特征函数 A：A0, 1 定义为实例：集合：X = A, B, C, D, E, F, G, H , 子集：T = A, C, F, G, H T 的特征函数T ： x A B C D E F G H T(x) 1 0 1 0 0 1 1 1 AA设 R 是 A 上的等价关系, 令g

6、：AA/Rg(a) = a, aA称 g 是从 A 到商集 A/R 的自然映射.恒等关系确定的自然映射是双射, 其他的自然映射一般来说是满射. 自然映射 例如：A=1, 2, 3, R=,IA则有：g(1) = 1,2, g(2) = 1,2, g(3) = 311.2 函数的合成与函数的逆函数的合成设 g：AB f：BC，则(1) f g是函数 f g： AC(2)对xA，有 (f g)(x)= f (g(x) 说明：函数合成后还是函数。只有当两个函数中一个的定义域与另一个函数的值域相同时，它们的合成才有意义。且 dom(g)=dom(f g)实例：设g:RR, f:R+R, g(x)=x+

7、1, f(x)=lnx ，则 gf(x) =g(f(x)=g(lnx)= lnx+1 fg(x)=f(g(x)=f(x+1)= ln(x+1) 一般地，gffggf 和 fg的定义域不同函数合成的性质定理11.2.2 设 f：BC, g：AB. 则有若 f 和g 都是满射的, 则 fg也是满射.若 f 和g 都是单射的, 则 fg也是单射.若 f 和g 都是双射的, 则 fg也是双射.证明：若 f 和g 都是满射, 则 fg也是满射. 证： cC, f 是满射, 必bB, 使得 f(b)=c. 对这个b, 又 g 是满射, 必aA, 使得 g(a)=b. 由合成定理有： c = f(b)= f

8、(g(a)= fg(a) 证毕. 说明 函数的合成运算能够保持函数单射、满射、双射的性质。 b3a1a2a3a4b1c1A B Cc2b2gf函数合成的性质定理11.2.3 设 f：BC, g：AB. 则有若 fg是满射.则f 是满射的若 fg是单射.则g是单射的若 fg是双射.则f 是单射的，g 是满射的。设 f: BC, g: AB,举例说明: fg是满射，但 g不是满射。 设：A=a1,a2, B=b1,b2, C=c, 定义函数如图，则 fg(a1)= fg(a2)=c说明函数合成运算性质的逆命题不为真。a2b2a1b1cA B Cgfa2b3a1b1c1A B Cc2b2函数合成的性

9、质定理11.2.3 设 f：BC, g：AB. 则有若 fg是满射.则f 是满射的若 fg是单射.则g是单射的若 fg是双射.则f 是单射的，g 是满射的。设 f: BC, g: AB,举例说明: fg是单射，但 f 不是单射。 设：A=a1,a2, B=b1,b2,b3, C=c1,c2, 定义函数如图， 则 fg(a1)=c1, fg(a2)=c2说明函数合成运算性质的逆命题不为真。gf11.2.2函数的逆任给函数 f, 它的逆f 1不一定是函数, 是二元关系.实例：f =,， f 1 =, 定理11.2.6 设 f：AB是双射函数，则 f 的逆关系f 1 是B到 A的双射函数。例如，设A

10、=1,2,3，B=a,b,c。 f=1, a ,2, c ,3, b 显然，f是A到B的双射函数。f的逆关系 f 1 =a,1,c,2,b,3是B到A的双射函数，记为f 1 。也称为反函数。函数的逆定理11.2.7 若f：AB为双射函数，对xA, 有f -1(f(x)=x,对yB, 有f(f-1(y)=y。反函数的性质对双射函数 f：AB，有 f 1f = IB, ff 1 = IA对双射函数 f：AA, 有 f 1 f = ff 1 = IA例：设A=0,1,2, B=a,b,c, f：AB, f=0,c,1,a,2,b解： f -1= a,1,b,2,c,0 f -1f =0,0,1,1,

11、2,2 IA ff -1=a,a,b,b,c,c IB012A B A B012abcabcf f -1 f11.3函数的性质定义11.3.1 设 f：AB, g：CD. 若xAC都有f(x)=g(x),就说f和g是相容的。定义11.3.2 设C是由一些函数组成的集合，若C中任意两函数 f 和 g 都是相容的，就说C是相容的。例：Cf, g, h, 其中f :a,b 1,2, f =,g :a,c 1,2, g =,h :b,c 1,2, h =,f和g相容、f和h相容，但g和h不相容，所以C是不相容的11.3.2 函数与等价关系的相容性定义11.3.3 设R是A上的等价关系，且 f：AA,

12、若x,yA, 有R R 则称关系R与函数f是相容的。例：A=1,2,3, R是A上的等价关系，商集A/R=1,2,3,设f：AA 定义为f(1)=3, f(2)=3, f(3)=1对 R, 有= R 对 R, 有= R 所以R与f是相容的。第12章 集合的基数12.2 集合的等势12.3 有限集合与无限集合12.4 集合的基数12.2集合的等势势就是集合的基数，等势就是集合的基数相等。定义12.2.1 设A和B是集合，若存在A到B的双射函数，则称集合A和集合B等势。记作AB。否则，称A和B不等势，记作AB。即对有限集合A和B，若AB，则|A|=|B|。即A和B中元素个数相等。例：R R ，因为

13、存在双射函数a,b,c 3，因为存在双射函数 f:a,b,c 3 , f(a)=0, f(b)=1, f(c)=2集合的等势举例Z N，因为存在双射函数R R ，因为存在双射函数a,b,c 3，因为存在双射函数 f:a,b,c 3 , f(a)=0, f(b)=1, f(c)=2集合的等势定理12.2.1对任意集合A，有：P(A) A2其中，因为2=0,1, 所以, A2是所有函数 f: A 0,1 组成的集合。可以构造双射函数H: P(A) A2, H(B)= B(x) 其中， B(x) 是以A为全集时B的特征函数，对BP(A),有B A ,则存在唯一的特征函数B(x)， a b c0 0

14、00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 集合等势所具有的性质 定理12.2.2设A，B，C是任意三个集合。则集合的等势有下列性质。 自反性: AA。 对称性: 若A B，则BA。 传递性: 若A B，BC，则AC。定理12.2.3（康托尔定理） (1) NR (2) 对任意的集合A，AP(A)定义12.3.1集合A是有限集合，当且仅当存在nN, 使nA.集合A是无限集合，当且仅当A不是有限集合，即不存在nN, 使nA. 12.3有限集合与无限集合定理12.3.1不存在与自己的真子集等势的自然数。(抽屉原理)推论1：不存在与自己的真子集等势的有限集合。 证明：

15、设A为任一有限集，BA，则C=A-B 。 |B|=|A|-|C|A|，即|A|B|，由双射的性质，A与B之间不存在双射函数。所以，A与B不等势有限集合与无限集合推论1：不存在与自己的真子集等势的有限集合。推论2：任何与自己的真子集等势的集合是无限集合，N和R都是无限集合。推论1和推论2给出了有限集合与无限集合的另一种定义不能和自己的任何真子集等势的集合称作有限集合能与自己的某个真子集等势的集合称作无限集合。推论3：有限集合只与唯一的自然数等势。12.4集合的基数定义12.4.1对任意集合A和B，它们的个数分别用card(A)和card(B)表示，并且card(A) = card(B) A B(等势集合的基数相同)对有限集合A和nN, 若A n, 则card(A) = n。自然数集合N的基数N的基数不是自然数，因为N不与任何自然数等势，把card(N)记作0。读作“阿列夫零”。凡与自然数集合N等势的集合叫做可数集.可数集的势叫做可数势.记做: 0 NZNN 0集合的基数实数集合R的基数R的基数不是自然数，也不是0，因为由康托尔定理得NR。 把card(R)记作1。读作“阿列夫壹”。实数集R是不可数的.card(0,1)=card(0,1)=card(R+)= 112.6基数的比较若