集合论 王智慧 复旦大学计算机学院
集合论 王智慧 复旦大学计算机学院
函数 ·函数的定义与性质 函数的复合与反函数 双射函数与集合的基数
2 函数 • 函数的定义与性质 • 函数的复合与反函数 • 双射函数与集合的基数
函数的定义 定义:设F为二元关系,若∨x∈domF,都存在唯一的 yenan, 使xFy成立,则称F为函数(或映射)对于函数F,如果有xFy, 则记作y=F(x),并称y为F在x的值 例:设A={1,2,3},F1和F2为A上的二元关系: F1={,,} F2={,} 请判断F1和F2是否为A上的函数?
3 函数的定义 定义: 设F为二元关系, 若∀x∈domF, 都存在唯一的y∈ranF, 使xFy成立, 则称F为函数(或映射).对于函数F, 如果有xFy, 则记作y=F(x), 并称y为F在x的值. 例: 设A={1, 2, 3}, F1和F2为A上的二元关系: F1 = { , , } F2 = { , } 请判断F1和F2是否为A上的函数?
函数的相等 由于函数是集合,可用集合相等来定义函数的相等: 定义.设F和G为函数,则F=G分FcG∧GcF 由以上定义可知,如果两个函数F和G相等,一定满足下面 两个条件: (1)domF=donG (2) VxedomF=domG,都有F(x)=G(x) 例:请判断函数F()=(x21)/x+1,G(x)=x1是否相等? 因为domF={x|x∈R∧x≠-1},domG=R
4 函数的相等 由于函数是集合, 可用集合相等来定义函数的相等: 定义. 设F和G为函数, 则 F=G ⇔ F⊆G∧G⊆F . 由以上定义可知, 如果两个函数F和G相等, 一定满足下面 两个条件: (1) domF = domG (2) ∀x∈domF = domG, 都有 F(x) = G(x) 例: 请判断函数F(x) = (x2-1)/(x+1), G(x) = x-1是否相等? 因为 domF = { x | x∈R∧x ≠ -1 } , domG = R
从A到B的函数 定义:设A和B为集合,如果f为函数,且domf=A, rance,则 称为从A到B的函数,记作:A→B 例如: f:N→N,f(x)=2x是从N到N的函数, g:N→N,g(x)=2也是从N到N的函数 定义:所有从A到B的函数的集合记作B,读作“B上A”符号 化表示为BA={f|f:A→B}
5 从A到B的函数 定义: 设A和B为集合, 如果f为函数, 且domf = A, ranf⊆B, 则 称f为从A到B的函数, 记作f:A→B. 定义: 所有从A到B的函数的集合记作BA, 读作“B上A”.符号 化表示为BA = { f | f: A→B }. 例如: f: N→N, f(x) = 2x是从N到N的函数, g: N→N, g(x) = 2也是从N到N的函数
从A到B的函数 例:设A={1,2,3},B={a,b},求B 解:B={f,f1,f},其中 f0={,,}f1={,,} f2={,,}f3={,,} f4={,,}fs={,} f={,,}f={,, 由排列组合知识不难证明:若A=m,B=n,且m,n>0, 则|B=n 在上面的例子中,=3,B=2,所以,BN=23=8
6 从A到B的函数 例: 设A = { 1, 2, 3 }, B = { a, b }, 求BA. 解: BA = { f0, f1,…, f7 }, 其中 f0 = { , , } f1 = { , , } f2 = { , , } f3 = { , , } f4 = { , , } f5 = { , , } f6 = { , , } f7 = { , , } 由排列组合知识不难证明: 若|A| = m, |B| = n, 且m, n > 0, 则|BA| = nm. 在上面的例子中, |A| = 3, |B| = 2, 所以, |BA| = 23 = 8
从A到B的函数 当A或B中至少有一个集合是空集时,可以分成下面三 种情况: 1)A=φ且B=中,则BA=φ〓{φ 2)A=φ且B≠则BA=B={φ 3),A≠φ且B=,则BA=中A=中
7 从A到B的函数 当A或B中至少有一个集合是空集时, 可以分成下面三 种情况: 1). A = φ且B = φ, 则BA = φφ = { φ }. 2). A = φ且B ≠ φ, 则BA = Bφ = { φ }. 3). A ≠ φ且B = φ, 则BA = φA = φ
函数的像与完全原像 定义:设函数A→B,A1A,B1B. (1)令(A1)={fx)x∈A1}称f(A1)为A1在f下的像特别的, 当A1=A时称f(A)为函数的像 (2)令f(B1)={x|x∈AAx)∈B1},称f(B1)为B1在下的完 全原像 注意 函数的值和像的区别函数值f(x)∈B,而像f(A1)B 设B1三B,那么B1在下下的完全原像f(B1)是A的子集 考虑A1A,那么f(A1)∈B.f(A1)的完全原像就是f((A1) 一般来说,f(A1)≠A1,但是A1fl(f(A1)
8 函数的像与完全原像 定义: 设函数f: A→B, A1 ⊆ A, B1 ⊆ B. (1) 令f(A1) = { f(x) | x∈A1 }, 称f(A1)为A1在f下的像.特别的, 当A1=A时称f(A)为函数的像. (2) 令f-1(B1) = { x | x∈A∧f(x)∈B1 }, 称f-1(B1)为B1在f下的完 全原像. 注意: ¾函数的值和像的区别.函数值f(x)∈B, 而像f(A1) ⊆ B. ¾设B1 ⊆ B, 那么B1在f下的完全原像 f-1(B1)是A的子集. ¾考虑A1 ⊆ A, 那么f(A1) ⊆ B. f(A1)的完全原像就是f-1(f(A1)). 一般来说, f-1(f(A1)) ≠ A1, 但是A1 ⊆ f-1(f(A1))
函数的像与完全原像 例:函数f:{1,2,3}→{0,1},满足(1)=()=0,(3)=1, 令A1={1},那么,f((A1=f(f({1})=f({0}={1,2} 此时,A1cfl(f(A1) 例:设:N→N,且 f(x)=x/2若x为偶数 x+1若x为奇数 令A={0,1},B={2},那么有 f(A)=f({0,1})={f(0),f(1)}={0,2} f(B)=f({2})={1,4}
9 函数的像与完全原像 例: 函数f: { 1, 2, 3 }→{ 0, 1 }, 满足 f(1)=f(2)=0, f(3)=1, 令A1 = { 1 }, 那么, f-1(f(A1)) = f-1(f({1})) = f-1({0}) = {1, 2} 此时, A1 ⊂ f-1(f(A1)). 例: 设f: N→N, 且 令A = { 0, 1 }, B = { 2 }, 那么有 f(A) = f({0,1}) = { f(0), f(1) } = { 0, 2 } f-1(B) = f-1({2}) = {1, 4} 若 为奇数 若 为偶数 x x x x f x ⎩⎨⎧ + = 1/ 2 ( )
满射、单射和双射 定义:设f:A→B (1)若ranf=B,则称fA→B是满射的; (2)若 yEnan,都存在唯一的x∈A,使得f(x)=y,则称f A→B是单射的 (3)若既是满射又是单射,则称是双射的(或一一映射) 注意: 若f:A→B是满射的,则对于vy∈B,都存在x∈A,使得 f(x)=y; >若f:A→B是单射的,则对于x1,x2∈A,x1≠X2一定有 f(x1)≠f(x2也就是说,若Vx1x2∈A,有f(x)=f(x2), 则有x1=x2
10 满射、单射和双射 定义: 设f: A→B, (1) 若ranf = B, 则称f: A→B是满射的; (2) 若∀y∈ranf, 都存在唯一的x∈A, 使得f(x) = y, 则称f: A→B是单射的 (3) 若f既是满射又是单射, 则称f是双射的(或一一映射). 注意: ¾若f: A→B是满射的, 则对于∀y∈B, 都存在x∈A, 使得 f(x) = y; ¾若f: A→B是单射的, 则对于∀x1, x2∈A, x1 ≠ x2, 一定有 f(x1) ≠ f(x2); 也就是说, 若∀x1, x2∈A, 有 f(x1) = f(x2), 则有 x1 = x2