离散数学(函数)课件

1、2021/8/14*函 数第 八 章2021/8/14*12/19/20214.1 函数的概念v 函数定义函数定义v 函数与关系函数与关系v 函数相等函数相等v 特殊函数特殊函数: : 单射单射 满射满射 双射双射8.1 函数的定义与性质函数的定义与性质2021/8/14*12/19/2021设设 F 为二元关系为二元关系, 若若 xdomF 都存在唯一都存在唯一的的yranF 使使 xFy 成立成立, 则称则称 F 为为函数函数 对于函数对于函数F, 如果有如果有 xFy, 则记作则记作 y=F(x), 并称并称 y 为为F 在在 x 的的值值.x 自变元自变元 y 在在F 作用下作用下 x

2、 的像的像2021/8/14*12/19/2021 10,)212121xxNxxxxfa且,)2212121yyRyyyyfb, xxxx ) 22121x1的素数个数为不大于xNfc12yy 1 1 11x2x562101233423002021/8/14*12/19/2021设设F, G 为函数为函数, 则则 F=G F GG F 如果两个函数如果两个函数F 和和 G 相等相等, 一定满足下面两个一定满足下面两个条件：条件： (1) domF=domG (2) xdomF=domG 都有都有F(x)=G(x) 函数函数F(x)=(x2 1)/(x+1), G(x)=x 1不相等不相等,

3、因为因为domF domG.2021/8/14*12/19/2021设设A, B为集合为集合, 如果如果 f 为函数为函数, domf=A, ranf B, 则称则称 f 为为从从A到到B的函数的函数, 记作记作 f：AB.2021/8/14*12/19/2021 在 f 中, Adomf 定义域定义域Branf值域值域,( (函数像的集合函数像的集合) )例：例： 设设 X =张三、李四、王五张三、李四、王五， Y =法国、美国、俄罗斯、英国法国、美国、俄罗斯、英国f =Adomf Branf 美国、俄罗斯、英国美国、俄罗斯、英国 2021/8/14*12/19/2021n 函数的定义域是函

4、数的定义域是A, 而不是而不是A 的的 某个真子集；某个真子集；n 一个一个 x 只能对应于唯一的只能对应于唯一的 y ；n A B 的子集并不都能成为的子集并不都能成为 A 到到 B 的函数。的函数。 2021/8/14*12/19/2021 A=a,b,c, B=0,1 A B=, |P(A B)|=26, 但只有但只有 23 个子集定义为个子集定义为 X 到到 Y 的函数的函数.f0 = ,f1 = ,f2 = ,f7 = ,一般地，一般地，|A|=m, |B|=n,由由 A 到到 B 的任的任意函数的定义域是意函数的定义域是 A ,在函数中每个在函数中每个恰有恰有 m 个序偶个序偶,又

5、任何又任何x A ,可以有可以有 n 个元素中的任何一个作为它的像个元素中的任何一个作为它的像,故故共有共有 nm (|B|A| ) 个不同函数个不同函数. BA2021/8/14*12/19/2021所有从所有从A到到B的函数的集合记作的函数的集合记作BA, 表示为表示为 BA = f | f：AB |A|=m, |B|=n, 且且m, n0, |BA|=nmA=, 则则BA=B=A且且B=, 则则BA=A= 2021/8/14*12/19/2021设函数设函数 f：AB, A1 A, B1 B(1) A1在在 f 下的像下的像 f(A1) = f(x) | xA1 特别的特别的, f(A)

6、称为称为函数的像函数的像(2) B1在在 f 下的完全原像下的完全原像 f 1(B1)=x|xAf(x)B1注意：注意：函数值与像的区别：函数值函数值与像的区别：函数值 f(x)B, 像像f(A1) B一般说来一般说来 f 1(f(A1)A1, 但是但是A1 f 1(f(A1)2021/8/14*12/19/2021例例 设设 f：NN, 且且令令A=0,1, B=2, 那么有那么有 f(A) = f 1(B) = 为奇数为奇数若若为偶数为偶数若若xxxxxf12/)( f( 0,1) = f(0), f(1)=0,2 f 1(2)=1,42021/8/14*12/19/2021设设 f：AB

7、,(1) 若若 ranf=B, 则称则称 f:AB是是满射满射的的(2) 若若 yranf 都存在唯一的都存在唯一的 xA 使得使得 f(x)=y, 则称则称 f:AB是是单射单射的的(3) 若若 f:AB 既是满射又是单射的既是满射又是单射的, 则称则称 f:AB是是双射双射的的)()(,(21212121xfxfxxAxxxx 2021/8/14*12/19/2021 1x1y2y3y2x3x4y1y2x3x1x2y3y2x3x1x3y2y1y4x4y1x2x3x1y2y3y单 射 映射（函数）双(单、满)射满射2021/8/14*12/19/2021判断下面函数是否为单射判断下面函数是否

8、为单射, 满射满射, 双射的双射的?(1) f:RR, f(x) = x2+2x 1(2) f:Z+R, f(x) = lnx, Z+为正整数集为正整数集(3) f:RZ, f(x) = x (4) f:RR, f(x)=2x+1(5) f:R+R+, f(x)=(x2+1)/x, 其中其中R+为正实数集为正实数集. 2021/8/14*12/19/2021 令令 A 和和 B 是有限集，若是有限集，若 A 和和 B 的元素个数相同，即的元素个数相同，即| A| = | B|，则则 f: A B是单射的，当且仅当是单射的，当且仅当它是一个满射。它是一个满射。此定理对无限集不一定成立。此定理对无

9、限集不一定成立。例如：例如：f: I I , f(x)=2x整数映射到偶整数整数映射到偶整数( (单射、非满射单射、非满射) )2021/8/14*12/19/2021对于给定的集合对于给定的集合A和和B构造双射函数构造双射函数 f:AB(1) A=P(1,2,3), B=0,11,2,3(2) A=0,1, B=1/4,1/2(3) A=Z, B=N(4) , B= 1,123,2 A2021/8/14*12/19/2021对于给定的集合对于给定的集合A和和B构造双射函数构造双射函数 f:AB(2) A=0,1, B=1/4,1/2(1,1/2)f(x)=(x+1)/42021/8/14*1

10、2/19/2021对于给定的集合对于给定的集合A和和B构造双射函数构造双射函数 f:AB A=-1, 1), B=2, 7)(1,7)(-1,2)2021/8/14*12/19/2021对于给定的集合对于给定的集合A和和B构造双射函数构造双射函数 f:AB(3) A=Z, B=N 01202)(,NZxxxxff：(3) 将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z： 0 11 2 2 3 3 N： 0 1 2 3 4 5 6 这种对应所表示的函数是：这种对应所表示的函数是：2021/8/14*12/19/2021(1)设设 f:AB, 如果存在如果存在c

11、B使得对所有使得对所有的的 xA都有都有 f(x)=c, 则称则称 f:AB是是常函常函数数.(2) 称称 A上的恒等关系上的恒等关系IA为为A上的上的恒等函数恒等函数, 对所有的对所有的xA都有都有IA(x)=x.(3) 设设, 为偏序集，为偏序集，f:AB，如果对任意的如果对任意的 x1, x2A, x1 x2, 就有就有 f(x1) f(x2), 则称则称 f 为为单调递增单调递增的；如果的；如果对任意的对任意的x1, x2A, x1 x2, 就有就有f(x1) f(x2), 则称则称 f 为为严格单调递增严格单调递增的的. 类似类似的也可以定义单调递减和严格单调递减的也可以定义单调递减

12、和严格单调递减的函数的函数.2021/8/14*12/19/2021(4) 设设A为集合为集合, 对于任意的对于任意的A A, A的的特特征函数征函数 A :A0,1定义为定义为 A(a)=1, aA A(a)=0, aA A(5) 设设R是是A上的等价关系上的等价关系, 令令 g:AA/R g(a)=a, aA称称 g 是从是从 A 到商集到商集 A/R 的的自然映射自然映射2021/8/14*12/19/2021 (1) 偏序集偏序集, , R 为包含关为包含关系系, 为一般的小于等于关系为一般的小于等于关系, 令令 f:P(a,b)0,1, f()=f(a)=f(b)=0, f(a,b)

13、=1, f 是是单调递增的单调递增的, 但不是严格单调递增的但不是严格单调递增的(2) A的每一个子集的每一个子集 A都对应于一个特征函数都对应于一个特征函数, 不同的子集对应于不同的特征函数不同的子集对应于不同的特征函数. 例如例如A=a,b,c, 则有则有 a,b= =, ,2021/8/14*12/19/2021(3) 不同的等价关系确定不同的自然映射不同的等价关系确定不同的自然映射, 恒等关系确定的自然映射是双射恒等关系确定的自然映射是双射, 其他其他自然映射一般来说只是满射自然映射一般来说只是满射. A=1,2,3, R=,IA g: AA/R, g(1)=g(2)=1,2, g(3

14、)=32021/8/14*12/19/2021 证明证明 f(A B) f(A) f(B)保序性：保序性：A B f(A) f(B)A B A A B B f(A B) f(A) f(A B) f(B) v方法方法1：f(A B) f(A) f(B)x A f(x) f(A)2021/8/14*12/19/2021 证明证明 f(A B) f(A) f(B)保序性：保序性：x A f(x) f(A)对于对于 y, y f(A B) , 则则 x, x A B ,使得使得f(x) = yv方法方法2： y f(A) f(B) 即即 x A x B ,使得使得f(x) = y f(x) f(A)

15、f(x) f(B) 2021/8/14*12/19/2021设设f和和g是定义域为自然数是定义域为自然数N上的函数上的函数f(n)=O(g(n). 若存在正数若存在正数c和和n0使得对一切使得对一切n n0 有有 0 f(n) cg(n)f(n) = (g(n). 若存在正数若存在正数c和和n0使得对一切使得对一切n n0有有 0 cg(n) f(n)f(n) =o(g(n). 若对任意正数若对任意正数c存在存在n0使得对一切使得对一切n n0有有 0 f(n) cg(n)f(n) = (g(n). 若对任意正数若对任意正数c存在存在n0使得对一切使得对一切n n0有有 0 cg(n) f(n

16、)f(n) = (g(n) f(n) =O(g(n) 且且 f(n) = (g(n)2021/8/14*12/19/2021f(n)c0g(n)c1g(n)n0f(n) is (g(n) f(n)cg(n)n0f(n) is O(g(n) f(n)cg(n)n0f(n) is (g(n) 2021/8/14*12/19/20211+2+ n n + n + n = n2 对于对于n 1 所以所以 1+2+ n =例：例： 1+2+n O(n2) 又又1+2+ n 1+1+1= n 对于对于n 1 所以所以 1+2+ n =(n)综上综上 1+2+ n = ?2021/8/14*12/19/20

17、21);()()();()()(0);()()(0)()(limgfngnfsgOfngnfsgfngnfssngnfn则的阶高，比说明时，当则的阶低，比说明时，当则同阶，和说明时，当若1+2+n=(n2)2021/8/14*12/19/20214.2 逆函数和复合函数v复合函数复合函数v反函数反函数8.2 函数的复合与反函数函数的复合与反函数关系与逆关系关系与逆关系: R-1 R函数与反函数。函数与反函数。 可能出现的问题：可能出现的问题：定义域定义域 (dom(f -1) A) 函数值函数值 (一对多一对多) 2021/8/14*12/19/2021设设F, G是函数是函数, 则则F G也

18、是函数也是函数, 且满足且满足(1) dom(F G)=x|xdomFF(x)domG(2) xdom(F G)有有F G(x)=G(F(x)证证 先证明先证明F G是函数是函数. 因为因为F, G是关系是关系, 所以所以F G也是关系也是关系. 若对某个若对某个xdom(F G)有有xF Gy1和和 xF Gy2, 则则 F GF Gt1(FG) t2(FG) t1 t2(t1=t2GG) （F为函数）为函数） y1=y2 （G为函数）为函数）所以所以 F G 为函数为函数2021/8/14*12/19/2021f : X Y , g : W Z u F = , G = ,X = 1,2,

19、Y = 3,4, W = 3,6, Z = 7, 9 F G = u f = , g = , f g = (1) dom(F G)=x|xdomFF(x)domG2021/8/14*12/19/2021推论推论 设设 f:AB, g:BC, 则则 f g:AC, 且且 xA都有都有 f g(x)=g(f(x)证证 由上述定理知由上述定理知 f g是函数是函数, 且且 dom(f g)=x|xdomff(x)domg =x|xAf(x)B=A ran(f g) rang C因此因此 f g:AC, 且且 xA有有 f g(x)=g(f(x)2021/8/14*12/19/2021,3 , 2 ,

20、 1qpYX, baZ , 3, 2, 1qppf求fg,bqbpg 1, 2, 3,f gbbb f g (1)= g(f(1)= g(p) = b2021/8/14*12/19/2021定理定理 设设f:AB, g:BC (1) 如果如果 f:AB, g:BC满射满射, 则则 f g:AC也满射也满射(2) 如果如果 f:AB, g:BC单射单射, 则则 f g:AC也单射也单射 (3) 如果如果 f:AB, g:BC双射双射, 则则 f g:AC也双射也双射定理定理 设设 f:AB, 则则 f = f IB = IA f 证证 (1) 任取任取cC, 由由g:BC的满射性的满射性, bB

21、使使得得 g(b)=c. 对于这个对于这个b, 由由 f:AB的满射性，的满射性， aA使得使得 f(a)=b. 由合成定理有由合成定理有 f g(a) = g(f(a) = g(b) = c从而证明了从而证明了f g:AC是满射的是满射的2021/8/14*12/19/2021定理定理 设设f:AB, g:BC (2) 如果如果 f:AB, g:BC单射单射, 则则 f g:AC也单射也单射 证证 (2) 假设存在假设存在x1, x2A使得使得 f g(x1)=f g(x2)由合成定理有由合成定理有 g(f(x1)=g(f(x2)因为因为g:BC是单射的是单射的, 故故 f(x1)=f(x2

22、). 又由于又由于f:AB是是单射的单射的, 所以所以x1=x2. 从而证明从而证明f g:AC是单射的是单射的.2021/8/14*12/19/2021注意：定理逆命题不为真注意：定理逆命题不为真, 即如果即如果f g:AC是是单射单射(或满射、双射或满射、双射)的的, 不一定有不一定有 f:AB 和和 g:BC都是单射都是单射(或满射、双射或满射、双射)的的.fg2021/8/14*12/19/2021u多个函数可复合多个函数可复合例例: X 1 , 2 , 3f 1 , p , 2 2 , p , 3 3 , q 求求: f (g h )、 ( f g) hY p , qZ a , bW

23、 5, 6, 7g p , b , q , a h a , 6 , b , 6 解解: g h = p , 6 , q , 6 f (g h ) = 1 , 6 , 2 , 6 , 3 , 6 f g = 1 , b , 2 , b , ( f g) h = 1 , 6 , 2 , 6 , 3 , 6 2021/8/14*12/19/2021已知：集合已知：集合 A=1, 2, 3, B=a, b, c令令函数函数 f: A B f =,但函数但函数 f的逆的逆关系关系：f -1 =, , 不是函数不是函数v原函数值域原函数值域ran(f ) = dom(f -1) Bv原函数原函数f (多对

24、一多对一)原因原因2021/8/14*12/19/2021定理定理 设设 f:AB是双射的是双射的, 则则f 1:BA也也是双射的是双射的.证明思路：证明思路：先证明先证明 f 1:BA，即即f 1是函数且是函数且domf 1=B, ranf 1=A. 再证明再证明f 1:BA的双射性质的双射性质. 2021/8/14*12/19/2021证证 因为因为 f 是函数是函数, 所以所以 f 1是关系是关系, 且且 dom f 1 = ranf = B , ran f 1 = domf = A对于任意的对于任意的 xB = dom f 1, 假设有假设有y1, y2A使得使得 f 1f 1成立成立

25、, 则由逆的定义有则由逆的定义有 ff根据根据 f 的单射性可得的单射性可得y1=y2, 从而证明了从而证明了f 1是函数，且是是函数，且是满射的满射的. 若存在若存在x1, x2B使得使得f 1 (x1)= f 1 (x2)=y, 从而有从而有 f 1f 1 ff x1=x2 对于双射函数对于双射函数f:AB, 称称 f 1:BA是它的是它的反函数反函数.2021/8/14*12/19/2021定理定理(1) 设设 f:AB是双射的是双射的, 则则 f 1 f = IB, f f 1 = IA(2) 对于双射函数对于双射函数 f:AA, 有有 f 1 f = f f 1 = IA 证明 设

26、若 ,aA.bB( ),f ab则1( ),fba于是11()( )( )ff bf fb( )f ab1BffI2021/8/14*12/19/2021,2 , 1 , 0:cbaf001122aabbcc求求: f f -1 及及f -1 f 解解: ff -1012cbaf -1 ff f -1=IA=IB例2021/8/14*12/19/2021定理定理 是一一是一一:f AB对应函数对应函数, ,则则ff11)( (双射双射) )定理定理:f AB:g BC均为一一对应函数均为一一对应函数, , 则则111()fggf( (双射双射) )定理2021/8/14*12/19/2021g

27、 x (x) = (x+2)2 x 1 - -2 x 1 f g (x) = x2 +2 x 3 0 0 x 3 f RR , g : R R,f (x) = x2 x 3 - -2 x 3 v求求 f g g f g (x) = x+2 2021/8/14*12/19/20214.4 基数的概念v自然数集合自然数集合v等势等势v有有( (无无) )限集合限集合v基数基数8.3 双射函数与集合的基数双射函数与集合的基数2021/8/14*12/19/2021定义 给定 A的后继集为AAA,若 为 ,则A,)(,)( ,可写成如下形式,可简记为, , , ,2021/8/14*12/19/202

28、1若命名集合 为0,则 0 1 0 ,1 0,1 2 0,1,2 3 , ,2 得到自然数集合, 3 ,2, 1 ,0N自然数自然数集合集合(n -1) 0,1,2,. . . . . . n -1 n2021/8/14*12/19/2021定义 给定两个集合A 与 B, 当且仅当存在着从 A 到 B 的双射函数, 称集合A 与B 是等势的, 记为A B .等势2021/8/14*12/19/2021等势证明证明: 设集合族为S 对任意 A S ,A A . 若若 A ,B S , A B ,则B A 若若 A ,B ,C S,A B ,B C , 则 A C 定理定理 在集合族上等势关系是一

29、个在集合族上等势关系是一个等价关系等价关系. .(1) IA是从是从A到到A的双射的双射 (2) 若若 f:AB是双射，是双射，则则f 1:BA是从是从B到到A的双射的双射.(3) 若若 f:AB，g:BC是双射，则是双射，则f g:AC是从是从A到到C的双射的双射2021/8/14*12/19/2021定义 若有一个从集合 0,1, , n-1 到A 的双射函数,则称A 是有限(穷)的; 若A 不是有限(穷)的,则它是无限的.有(无)限集合集合A 有限 A 某个自然数2021/8/14*12/19/2021定义定义(1) 对于有限集合对于有限集合A, 称与称与A等势的那个等势的那个惟一的自然

30、数为惟一的自然数为A的的基数基数, 记作记作cardA (也可以记作也可以记作|A|) cardA = n A n 一个集合是一个集合是有限有限的当且仅当它与某个自然数等势；的当且仅当它与某个自然数等势；|有限集合有限集合| = 元素个数元素个数 |空集空集| = 02021/8/14*12/19/2021等势 例例1: 试证集合试证集合 A = a, b, c, d 与与 B = , , , 等势等势证明证明: 设设 f : A B , f (a) = , f (b) = , f (c) = , f (d) = , 则则 f 是是 A B 的双射函数的双射函数, 所以所以A B2021/8/

31、14*12/19/2021等势 例例2: 试证自然数集合试证自然数集合 N 与与 集合集合 A = 2n | n N 等势等势 .证明证明: 设设 f : N A , 且且 f (n) = 2n, n = 0, 1, 2, , 则则 f 是是 N A 的的双射函数双射函数, 所以所以 N A .2021/8/14*12/19/2021等势 例例3: 设设 A = ( 0,1 ) = x | x R 0 x 1, 证明证明 A 与实数集与实数集合合 R 等势等势 .证明证明: 设设 f : A R , 且且 f (x) = tg(2x -1 ) , 则则 f 是是 A R 的双射的双射函数函数

32、. 22021/8/14*12/19/2021等势 f 是单射的是单射的. 对于任意的对于任意的x1 和和 x2 , x1 , x2 ( 0,1 ) (2x1 -1) , (2x2 -1 ) (- , ) 于是于是 tan(2x1 -1) = tan(2x2 -1) (2x1 -1) =(2x2 -1 ) x1 = x2 , 所以所以 f 是单射函数是单射函数 . 22222222因此因此 A R . f 是满射的是满射的. 对于任意的对于任意的 y R , 取取 x = arc tan y + 1 , 则则 x ( 0, 1 ) , 且且 f (x) = y ，所以所以 f 是满射的是满射的

33、 . 22021/8/14*12/19/2021等势因此因此 A R . f 是单射的是单射的. x ( 0,1 ) (2x -1) (- , )222 f 是满射的是满射的. 对于任意的对于任意的 y R , 取取 x = arctan y + 1 , 则则 x ( 0, 1 ) , 且且 f (x) = y ，所以所以 f 是满射的是满射的 . 2因为因为f 单调单调，所以，所以f 是入射的是入射的.2f(x) =tan( 2x -1 ) f(0, 1) R2021/8/14*12/19/2021 01202)(,NZ:xxxxxff则则 f 是是Z到到N的双射函数的双射函数. 从而证明了

34、从而证明了ZN.ZN 2021/8/14*12/19/2021221/ 201/ 21( )1/ 21/ 2 ,1,2,.nnxxf xxnxx其它0,1(0,1). 其中其中(0,1)和和0,1分别为实数分别为实数开区间和闭区间开区间和闭区间. 令令 f : 0,1(0,1)2021/8/14*12/19/2021 对任何对任何a, bR, ab, 0,1a,b，双射函数双射函数 f:0,1a,b, f(x)=(b a)x+a类似地可以证明类似地可以证明, 对任何对任何a, bR, ab, 有有(0,1)(a,b).2021/8/14*12/19/2021定义 有限集、或者与自然数集合等势的

35、任意集合称为可数集(可列集),无限可数集的基数用0 0表示.可数集2021/8/14*12/19/2021可数集举例例 A = a, b, c, B = 1, 3, 5, , 2n+1, , C = 3, 12, 27, , 3(n+1)2, , 整数集整数集Z , 有理数集有理数集Q .2021/8/14*12/19/2021定理定理 设设A是集合是集合, A为可数集的充要条件是可为可数集的充要条件是可排列成排列成A = a1 , a2 , . , an , . 的形式的形式. . 一个集合是可数集当且仅当可以将它的一个集合是可数集当且仅当可以将它的所有元素逐个的排成一个序列所有元素逐个的排

36、成一个序列, ,使得序列使得序列中每个元素都属于这个集合中每个元素都属于这个集合, ,并且这个集并且这个集合中的每个元素都在序列中的某个位置合中的每个元素都在序列中的某个位置出现且仅出现一次出现且仅出现一次. .对于任何的可数集对于任何的可数集, , 它的元素都可以排列成一个有序图形它的元素都可以排列成一个有序图形. . 换句话说换句话说, , 都可以找到一个都可以找到一个“数遍数遍”集集合中全体元素的顺序合中全体元素的顺序. . 可数集充要条件2021/8/14*12/19/2021mnmnmnmff 2)(1(),(,NNN:NNN. NN中所有的元素排成有序图形中所有的元素排成有序图形2

37、021/8/14*12/19/2021NQ. 双射函数双射函数 f:NQ, 其中其中f(n)是是n下方的下方的有理数有理数. -2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/

38、41/41/41414PLAY2021/8/14*12/19/2021,242322212aaaaS ,343332313aaaaS ,444342414aaaaS ,141312111aaaaS ,545352515aaaaS 1kkSS2021/8/14*12/19/2021可数集的性质：可数集的性质： 可数集的任何子集都是可数集可数集的任何子集都是可数集. 两个可数集的并是可数集两个可数集的并是可数集. 两个可数集的笛卡儿积是可数集两个可数集的笛卡儿积是可数集. 可数个可数集的笛卡儿积仍是可数集可数个可数集的笛卡儿积仍是可数集.2021/8/14*12/19/2021证明 是可数集, N

39、N,互质且 nmNnmnmSS是可数的.令QSg:(,)mgm nn g是双射的,故 是可数集.Q.QQQQQ0定理:Q可数集2021/8/14*12/19/2021有关势的结果等势结果等势结果 N Z Q NN 任何实数区间都与实数集合任何实数区间都与实数集合R等势等势不等势的结果不等势的结果: 定理定理 (康托定理康托定理)(1) N R； (2) 对任意集合对任意集合A都有都有A P(A)证明思路：证明思路：(1) 只需证明任何函数只需证明任何函数 f:N0,1都不是满射的都不是满射的. 任取函数任取函数 f:N0,1, 列出列出 f 的的所有所有函数值，函数值，然后构造一个然后构造一个

40、0,1区间的小数区间的小数b，使得，使得b与所有与所有的函数值都不相等的函数值都不相等. 2021/8/14*12/19/2021证证 (1) 规定规定0,1中数的表示中数的表示. 对任意的对任意的x0,1, 令令 x = 0. x1 x2 , 0 xi 9规定在规定在 x 的表示式中不允许在某位后有无数个的表示式中不允许在某位后有无数个9的情的情况况. 设设 f: N0,1是任何函数，列出是任何函数，列出 f 的所有函数值：的所有函数值： f(0) = 0.a1(1)a2(1) f(1) = 0.a1(2)a2(2) f(n 1) = 0.a1(n)a2(n) 令令 y 的表示式为的表示式为0.b1b2, 并且