《集合论与图论》第9讲1 第9讲函数 内容提要 ?函数,偏函数,全函数,真偏函数 ?单射,满射,双射,计数问题 ?象,原象 ?常数函数,恒等函数,特征函数,单调函数, 自然映射 ?合成(复合),反函数,单边逆(左逆,右逆) ?构造双射(有穷集,无穷集) 《集合论与图论》第9讲2 函数(function),映射(mapping) ?单值的二元关系称为函数或映射 ?单值: ?x∈domF, ?y,z∈ranF, xFy ∧ xFz → y=z ?F(x)=y ? <x,y>∈F ? xFy ??是空函数 ?常用F,G,H,…,f,g,h,…表示函数. x y z 非单值 单值 《集合论与图论》第9讲3 偏函数(partial function) ?偏函数: domF?A ?A到B的偏函数: domF?A ∧ ranF?B ?偏函数记作F:A→B, 称A为F的前域, ?A到B的全体偏函数记为A→B A→B = { F | F:A→B } 《集合论与图论》第9讲4 例1 ?例1: 设A={a,b}, B={1,2}, 求A→B. ?解: |A|=2,|B|=2,|A×B|=4,|P(A×B)|=2 4 =16. f 0 =?, f 1 ={<a,1>}, f 2 ={<a,2>}, f 3 ={<b,1>}, f 4 ={<b,2>}, f 5 ={<a,1>,<b,1>}, f 6 ={<a,1>,<b,2>}, f 7 ={<a,2>,<b,1>},f 8 ={<a,2>,<b,2>}. A→B = {f 0 ,f 1 ,f 2 ,f 3 ,f 4 ,f 5 ,f 6 ,f 7 ,f 8 }. # ?非函数: {<a,1>,<a,2>}, {<b,1>,<b,2>}, {<a,1>,<a,2>,<b,1>},… 《集合论与图论》第9讲5 全函数(total function) ?全函数: domF=A ?全函数记作F:A→B ?A到B的全体全函数记为B A 或A→B B A = A→B = { F | F:A→B } 《集合论与图论》第9讲6 关于B A 的说明 ?B A = A→B = {F|F:A→B} = {F|F是A到B的全函数} ?|B A | = |B| |A| . ?当A=?时, B A ={?} ?当A≠?且B=?时, B A =A→B=?, 但A→B={?}. 《集合论与图论》第9讲7 真偏函数(proper partial function) ?真偏函数: domF?A, ?真偏函数记作F:A→B, ?A到B的全体真偏函数记为A→B A→B = { F | F:A→B } 《集合论与图论》第9讲8 例1(续) ?例1(续): 设A={a,b}, B={1,2}, 求A→B. ?解: f 0 =?, f 1 ={<a,1>}, f 2 ={<a,2>}, f 3 ={<b,1>}, f 4 ={<b,2>}, f 5 ={<a,1>,<b,1>}, f 6 ={<a,1>,<b,2>}, f 7 ={<a,2>,<b,1>},f 8 ={<a,2>,<b,2>}. A→B={f 0 , f 1 , f 2 , f 3 , f 4 }. # ?说明: F∈A→B ? F∈domF→B F∈A→B ? F∈domF→B 《集合论与图论》第9讲9 三者关系 ?A→B = A→B ∪ A→B 偏函数A→B domF?A 全函数A→B domF=A 真偏函数A→B domF?A 《集合论与图论》第9讲10 全函数性质 ?设F:A→B, ?单射(injection): F是单根的 ?满射(surjection): ranF=B ?双射(bijection): F既是单射又是满射, 亦 称为一一对应(one-to-one mapping). 非单射非满射 《集合论与图论》第9讲11 例2 ?例2: 设A 1 ={a,b}, B 1 ={1,2,3}, A 2 ={a,b,c}, B 2 ={1,2}, A 3 ={a,b,c}, B 3 ={1,2,3}, 求A 1 →B 1 ,A 2 →B 2 ,A 3 →B 3 中的单射,满射, 双射. 《集合论与图论》第9讲12 例2(解(1)) ?例2: (1) A 1 ={a,b}, B 1 ={1,2,3}, ?解: (1) A 1 →B 1 中无满射,无双射,单射6个: f 1 ={<a,1>,<b,2>}, f 2 ={<a,1>,<b,3>}, f 3 ={<a,2>,<b,1>}, f 4 ={<a,2>,<b,3>}, f 5 ={<a,3>,<b,1>}, f 6 ={<a,3>,<b,2>}. 《集合论与图论》第9讲13 例2(解(2)) ?例2: (2) A 2 ={a,b,c}, B 2 ={1,2}, ?解: (2) A 2 →B 2 中无单射,无双射,满射6个: f 1 ={<a,1>,<b,1>,<c,2>}, f 2 ={<a,1>,<b,2>,<c,1>}, f 3 ={<a,2>,<b,1>,<c,1>}, f 4 ={<a,1>,<b,2>,<c,2>}, f 5 ={<a,2>,<b,1>,<c,2>}, f 6 ={<a,2>,<b,2>,<c,1>}. 《集合论与图论》第9讲14 例2(解(3)) ?例2: (3) A 3 ={a,b,c}, B 3 ={1,2,3}, ?解: (3) A 2 →B 2 中双射6个: f 1 ={<a,1>,<b,2>,<c,3>}, f 2 ={<a,1>,<b,3>,<c,2>}, f 3 ={<a,2>,<b,1>,<c,3>}, f 4 ={<a,2>,<b,3>,<c,1>}, f 5 ={<a,3>,<b,1>,<c,2>}, f 6 ={<a,3>,<b,2>,<c,1>}. # 《集合论与图论》第9讲15 计数(counting)问题 ?设|A|=n, |B|=m, 问A→B中有多少单射,满 射,双射? ?n<m时, A→B中无满射,双射, 单射个数为 m(m-1)…(m-n+1) ?n=m时, A→B中双射个数为n! ?n>m时, A→B中无单射,双射, 满射个数为 .! ? ? ? ? ? ? m n m 《集合论与图论》第9讲16 例3 ?A,B是非空有穷集,讨论下列函数的性质 1. f:A→B, g:A→A×B, ?a∈A, g(a)=<a,f(a)> 2. f:A×B→A, ?<a,b>∈A×B, f(<a,b>)=a 3. f:A×B→B×A, ?<a,b>∈A×B, f(<a,b>)=<b,a> 《集合论与图论》第9讲17 例3(解) 1. f:A→B,g:A→A×B, ?a∈A, g(a)=<a,f(a)> ?当|B|>1时,g是单射,非满射,非双射 ?当|B|=1时,g是单射,满射,双射 2. f:A×B→A, ?<a,b>∈A×B, f(<a,b>)=a ?当|B|>1时,f非单射,是满射,非双射 ?当|B|=1时,f是单射,满射,双射 3. f:A×B→B×A,?<a,b>∈A×B, f(<a,b>)=<b,a> ?f是单射,满射,双射 《集合论与图论》第9讲18 象(image), 原象(preimage) ?设f:A→B, A’?A, B’?B ?A’的象是 f(A’) = {y|?x(x∈A’∧f(x)=y)} ? B ?f(A) = ranf ?B’的原象是 f -1 (B’) = {x|?y(y∈B’∧f(x)=y)} ? A A’ f(A’) f -1 (B’) B’ 《集合论与图论》第9讲19 象,原象(举例) ?例: f:N→N, f(x)=2x. A’=N 偶 ={0,2,4,6,…}={2k|k∈N}, f(A’)={0,4,8,12,…}={4k|k∈N} B’={2+4k|k∈N}={2,6,10,14,…}, f -1 (B’)={1+2k|k∈N} ={1,3,5,7,…}=N 奇 # 《集合论与图论》第9讲20 定理3.1 ?设f:C→D为单射,C为C的非空子集族. C 1 ,C 2 ?C,则 1. f(∪C) = ∪{f(A)|A∈C} 2. f(∩C) = ∩{f(A)|A∈C} 3. f(C 1 -C 2 ) = f(C 1 )-f(C 2 ). ?证明: 利用定理2.9和f的单射性. # 《集合论与图论》第9讲21 定理3.2 ?设f:C→D, D 1 ,D 2 ?D, D是D的非空子集族. 则 1. f -1 (∪D) = ∪{f -1 (D)|D∈D} 2. f -1 (∩D) = ∩{f -1 (D)|D∈D} 3. f -1 (D 1 -D 2 ) = f -1 (D 1 )-f -1 (D 2 ). ?证明: 利用定理2.9. # 《集合论与图论》第9讲22 特殊函数 ?常数函数: f:A→B, ?b∈B, ?x∈A, f(x)=b ?恒等函数: I A :A→A, I A (x)=x ?特征函数: χ A :E→{0,1}, χ A (x)=1?x∈A ?单调函数: f:A→B,<A,≤ A >,<B,≤ B >偏序集 ?单调增: ?x,y∈A, x≤ A y ? f(x)≤ B f(y) ?单调减: ?x,y∈A, x≤ A y ? f(y)≤ B f(x), ?严格单调: 把≤换成< ?自然映射: f:A→A/R, f(x)=[x] R , R为A上等 价关系 《集合论与图论》第9讲23 自然映射(举例) ?例: A={a,b,c,d,e,f}, A/R={{a,b},{c,d,e},{f}}, [a]=[b]={a,b}, [c]=[d]=[e]={c,d,e}, [f]={f}, F:A→A/R, F(x)=[x]. F(a)={a,b}, F(b)={a,b}, F( c )={c,d,e}, F(d)={c,d,e}, F(e)={c,d,e}, F(f)={f}. # a b c de f 《集合论与图论》第9讲24 函数运算 ?合成(复合): 性质, 左(右)单位元, 单调性 ?反函数: 存在条件(双射才有反函数) ?单边逆: 左逆, 右逆, 存在条件 《集合论与图论》第9讲25 函数合成(composite) ?定理3: 设g:A→B, f:B→C, 则 f○g: A→C, f○g(x)=f(g(x)). ?证明思路: ? f○g是函数(即f○g单值) ? dom f○g = A ? ran f○g ? C, f○g(x)=f(g(x)) 《集合论与图论》第9讲26 定理3(证明) ?证明: (1) f○g是函数,即f○g是单值的. ?x∈dom(f○g),若?z 1 ,z 2 ∈ran(f○g),则 x(f○g)z 1 ∧x(f○g)z 2 ??y 1 (y 1 ∈B∧xgy 1 ∧y 1 fz 1 )∧?y 2 (y 2 ∈B∧xgy 2 ∧y 2 fz 2 ) ??y 1 ?y 2 (y 1 ∈B∧y 2 ∈B∧xgy 1 ∧xgy 2 ∧y 1 fz 1 ∧y 2 fz 2 ) ??y(y∈B∧y 1 =y 2 =y∧y 1 fz 1 ∧y 2 fz 2 ) ?z 1 =z 2 《集合论与图论》第9讲27 定理3(证明) ?证明: (2) dom(f○g) = A. 显然dom(f○g)?A,下证A?dom(f○g), ?x, x∈A ? ?!y(y∈B∧xgy) ? ?!y?!z(y∈B∧z∈C∧xgy∧yfz) ? ?!z(z∈C∧x(f○g)z) ? x∈dom(f○g). 《集合论与图论》第9讲28 定理3(证明) ?证明: (3) f○g(x)=f(g(x)). 由(1)(2)知ran(f○g)?C, ?x,x∈A ? ?!z(z∈C∧z=f○g(x)) ? ?!z?!y(z∈C∧y∈B∧y=g(x)∧z=f(y)) ? ?!z(z∈C∧z=f(g(x))) 所以对任意x ∈A, 有,f○g(x)=f(g(x)). # 《集合论与图论》第9讲29 定理4 ?定理4: 设g:A→B, f:B→C, f○g:A→C,则 (1) f,g均为满射, 则f○g也是满射. (2) f,g均为单射, 则f○g也是单射. (3) f,g均为双射, 则f○g也是双射. # 《集合论与图论》第9讲30 定理5 ?定理5: 设g:A→B, f:B→C, 则 (1) 若f○g为满射, 则f是满射. (2) 若f○g为单射, 则g是单射. (3) 若f○g为双射, 则g是单射,f是满射. # g g f 《集合论与图论》第9讲31 定理6 ?定理6: 设f:A→B, 则f=f○I A =I B ○f. # AA B B I A I Bf 《集合论与图论》第9讲32 定理7(单调性) ?定理7: 设f:R→R, g:R→R, 且f,g按≤是单 调增的, 则f○g也是单调增的. ?证明: x≤y ? g(x)≤g(y) ?f(g(x))≤f(g(y)). # 《集合论与图论》第9讲33 反函数(inverse function) ?定理8: 设A为集合,则 A -1 为函数? A为单根的. # ?推论: 设R为二元关系,则 R为函数? R -1 为单根的. # ?定理9: 设f:A→B, 且为双射,则 f -1 :B→A, 且也为双射. # ?反函数: 若f:A→B为双射, 则f -1 :B→A称 为f的反函数. 《集合论与图论》第9讲34 构造双射及求反函数 ?|A|=m, |B|=n, A→B存在双射? n=m ?|A|=∞, |B|=∞, B?A, A→B可存在双射,如 f: N→N-{0,1,2}, f(n)=n+3 ?[0,1]→(0,1) ? R→(0,1) ? ?N×N→N ? 012345678 012345678 《集合论与图论》第9讲35 例6: 构造N×N→N 双射? 《集合论与图论》第9讲36 方法1: 用自然数性质 ? ?n∈N∧n≠0, ?α,β∈N, β为奇数, 使得 n=2 α β ?例: 1= 2 0 ×1, 2= 2 1 ×1, 3= 2 0 ×3,…, 6=2 1 ×3,…,100=2 2 ×25,… ?令n=2 α β-1,可以去掉n≠0的条件 ?令β=2j+1, β为奇数 ??n∈N, n=2 i (2j+1)-1, i,j∈N, 此表示唯一. 《集合论与图论》第9讲37 方法1: f:N×N→N ? f:N×N→N, f -1 :N→N×N, ?<i,j>∈N×N, f(<i,j>)=2 i (2j+1)-1, f -1 (n)=f -1 (2 i (2j+1)-1)=<i,j>. ?例: f(<0,0>)=0, f(<0,1>)=2, f(<1,0>)=1,… f -1 (5)=<1,1>, f -1 (101)=<1,25>, f -1 (200)=<0,100>,… 《集合论与图论》第9讲38 方法2:Cantor编码—对角线法 <m,n> <m,0> <m+n,0> 1+2+3+…+(m+n)+(m+1) =(m+n)(m+n+1)/2+(m+1) 对应的自然数为 (m+n)(m+n+1)/2+m 《集合论与图论》第9讲39 方法2: f:N×N→N ? f:N×N→N, f -1 :N→N×N, ?<m,n>∈N×N, f(<m,n>)=(m+n)(m+n+1)/2+m, ?求f -1 (r)=<?,?>=<m,n>. r=(m+n)(m+n+1)/2+m=t(t+1)/2+m, t=m+n, 0≤m≤t, 求最大t, 使得r≥t(t+1)/2. t 2 +t-2r≤0, , m=r-t(t+1)/2, n=t-m. ?例: f -1 (0)=<0,0>, f -1 (1)=<0,1>, f -1 (2)=<1,0>, f -1 (3)=<0,2>, … ? ? ? ? ? ? ?+= )181( 2 1 rt 《集合论与图论》第9讲40 单边逆 ?设f:A→B, g:B→A ?左逆: g是f的左逆? g○f=I A , ?右逆: g是f的右逆? f○g=I B , A B f g I A I B 《集合论与图论》第9讲41 单边逆(举例) BA B g f ABA g f f○g=I B g○f=I A 《集合论与图论》第9讲42 单边逆的存在条件 ?定理10: 设f:A→B, 且A≠?,则 (1) f存在左逆? f是单射; (2) f存在右逆? f是满射; (3) f 存在左逆,右逆? f 是双射 ? f 的左逆和右逆相等. # g○ff○g 《集合论与图论》第9讲43 总结 ?概念: 函数,偏函数,全函数,真偏函数 ?性质: 单射, 满射, 双射, 计数问题 ?术语: 象, 原象 ?特殊函数: 常数,恒等,特征,单调,自然映射 ?运算: 合成(复合), 反函数, 单边逆 ?技巧: 构造双射 《集合论与图论》第9讲44 作业(#7) ?p104, 习题三, 11,15,16,19,20