大学精品课件：集合论.ppt

1、1 集合论集合论 Set Theory 2 1.1. 集合集合 2.2. 关系关系 3.3. 关系性质与闭包关系性质与闭包 4.4. 等价关系等价关系 5.5. 偏序关系偏序关系 6.6. 函数函数 7.7. 集合基数集合基数 内容提要内容提要 1 1、集合、集合 概念概念： 集合集合, , 外延性原理外延性原理, , , , , , , , 空集空集, , 全集全集, , 幂集幂集 文氏图文氏图, , 交交, , 并并, , 差差, , 补补, , 对称差对称差 4 集合集合 一些一些可以明确区分的对象的整体可以明确区分的对象的整体, 对象的次序无关紧要对象的次序无关紧要. 对象称为对象称为

2、元素元素. 约定: 用大写字母表示集合. 例:A ; 用小写字母表示元素. 例:a 属于: a A 不属于：a A 集合表示: 列举法 eg. A= a,b,c 叙述法 eg. A= x|x=a或x=b或x=c 集合相等 (外延性原理) : 两个集合相等,当且仅当它们有相同 的元素. 例: 1,2 = 2,1 1,2,2 = 1,2 5 集合与集合之间的关系：集合与集合之间的关系： , =, , , , A B x ( x A x B ) A = B A B B A A B A B A B A B x ( x A x B ) 6 空集空集 不含有任何元素的集合不含有任何元素的集合 实例：实例：

3、 x | x R x2+1=0 定理：定理： 空集是任何集合的子集。空集是任何集合的子集。 推论推论 ： 是惟一的。是惟一的。 全集全集 E 包含了所有元素的集合包含了所有元素的集合 注：全集具有相对性：与问题有关，不存在绝对的全集注：全集具有相对性：与问题有关，不存在绝对的全集 7 幂集幂集 P(A)= x | x A 例例: (1) 令令 A= 1,2 , 则则 P(A)=,1,2,1,2 (2) 计算计算 P(), P(P(), P(P(P(). 定理：如果定理：如果 |A|=n，则，则 |P(A)|=2n. 8 集合的基本运算集合的基本运算 并并 A B = x | x A x B 交

4、交 A B = x | x A x B 差（相对补）差（相对补） A B = x | x A x B 对称差对称差 A B = (A B) (B A) 补（绝对补）补（绝对补） A = E A = x|x A 注：并和交运算可以推广到有穷个集合上，即注：并和交运算可以推广到有穷个集合上，即 A1 A2 An = x | x A1 x A2 x An A1 A2 An = x | x A1 x A2 x An 9 文氏图文氏图 (Venn Diagram):将全集将全集E看成二维的全平面上所有看成二维的全平面上所有的的 点构成的集合点构成的集合.而而E的子集表示成平面上由封闭曲线围成的点集的子集

5、表示成平面上由封闭曲线围成的点集. 集合运算的表示集合运算的表示 A B A B A B A B A B A B A B AB A B A 10 广义运算广义运算 广义并 A = x | z ( zA xz ) 广义交广义交 A= x | z ( z A x z ) 例例: 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a 11 集合恒等式集合恒等式 集合算律集合算律 1只涉及一个运算的算律：只涉及一个运算的算律： 交换律交换律、结合律结合律、幂等律幂等律 交换交换 A B=B A A B=B A A B=B A 结合结合 (A B)

6、C =A (B C) (A B) C= A (B C) (A B) C =A (B C) 幂等幂等 A A=A A A=A 12 集合算律集合算律 2涉及两个不同运算的算律：涉及两个不同运算的算律： 分配律、吸收律分配律、吸收律 与与 与与 分配分配 A (B C)= (A B) (A C) A (B C)= (A B) (A C) A (B C) =(A B) (A C) 吸收吸收 A (A B)=A A (A B)=A 13 集合算律集合算律 3涉及补运算的算律：涉及补运算的算律： DM律律，双重否定律双重否定律 D.M律律 A (B C)=(A B) (A C) A (B C)=(A B

7、) (A C) (B C)= BC (B C)= BC 双重否定双重否定 A=A 14 集合算律集合算律 4涉及全集和空集的算律：涉及全集和空集的算律： 补元律补元律、零律零律、同一律同一律、否定律否定律 E 补元律补元律 AA= AA=E 零律零律 A= A E=E 同一律同一律 A=A A E=A 否定否定 =E E= 2 2、关系、关系 概念概念： 序偶序偶, 笛卡尔积笛卡尔积, 关系关系, domR, ranR, 关系图关系图, 空关系空关系, 全域关系全域关系, 恒等关系恒等关系. 16 序偶序偶 （有序对，（有序对， Pair） 由两个元素由两个元素 x 和和 y，按照一定的顺序组

8、成的二元组，按照一定的顺序组成的二元组， 记作记作. 有序对性质有序对性质: (1) 有序性有序性 （当（当x y时）时） (2) 与与相等的充分必要条件是相等的充分必要条件是 = x=u y=v. 17 笛卡儿积笛卡儿积 设设A,B为集合，为集合，A与与B的的笛卡儿积笛卡儿积记作记作A B定义为定义为 A B = | x A y B. 例例 ： A=1,2,3, B=a,b,c A B= , B A= , 18 注意注意: A= 或或 B= 时时, A B= “ ”不满足结合律”不满足结合律. 当当 A1 A2 An时时,约定约定“ “左结合左结合,即即 A1 A2 An=( (A1 A2)

9、 An-1) An An=A A A ( n个个 A) 19 性质证明性质证明 证明证明 A (B C) = (A B) (A C) 证证 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有所以有A(BC) = (AB)(AC). 20 实例实例 例例2 (1) 证明证明A=B,C=D A C=B D (2) A C = B D是否推出是否推出 A=B,C=D? 为什么？为什么？ 解解 (1) 任取任取 A C x A y C x B y D B D (2) 不一定不一定.反例如下：反例如下： A=1，B=2, C = D = ,

10、则则A C = B D但是但是A B. 21 关系关系(Relation) : 两个定义两个定义 (1) 序偶的一个集合序偶的一个集合, 确定了一个二元关系确定了一个二元关系R。R 中任一序偶中任一序偶 ,可记作可记作 R 或或 xRy (2) 笛卡尔积的子集笛卡尔积的子集： R A B 对通常的对通常的“关系关系“给出了一种抽象的描述给出了一种抽象的描述. 例例: 令令 A=B=1,2,3 R=,，其实，其实R就是通就是通 常意义下的常意义下的 关系。关系。 22 前域前域 dom(R) = x| y. R 值域值域 ran(R) = y| x. R 域域 fld(R) = domR ran

11、R 例例5 R=, 则则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 23 设设R为二元关系为二元关系, A是集合是集合 (1) R在在A上的上的限制限制记作记作 R A, 其中其中 R A = | xRyxA (2) A在在R下的下的像像记作记作RA, 其中其中 RA=ran(R A) 例例：设设R=, 则则 R 1 = , R = R 2,3 = , R1 = 2,3 R = 24 R A B,则称则称R是是从从A到到B的关系的关系. 当当 A=B 时称时称 R 为为 A 上的二元关系上的二元关系. 全域关系全域关系 AB 空关系空关系 恒等关系恒等

12、关系 IA = | xA 25 关系的表示关系的表示 关系矩阵关系矩阵 若若A=x1, x2, , xm，B=y1, y2, , yn，R是从是从A到到B的的 关系，关系，R的关系矩阵是布尔矩阵的关系矩阵是布尔矩阵MR = rij m n, 其中其中 rij = 1 R. 关系图关系图 若若A= x1, x2, , xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是 GR=, 其中其中A为结点集，为结点集，R为边集为边集. 如果如果属于属于 关系关系R，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边. 注意：注意： 关系矩阵适合表示从关系矩阵适合表示从A到到B

13、的关系或的关系或A上的关系（上的关系（A,B为有为有 穷集）穷集） 关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系 26 实例实例 A=1,2,3,4, R=, R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下： 0010 0000 1100 0011 R M 27 复合关系复合关系 (Composition) R S = | y ( R S) 例：例： R = , , , S = , , , , R 1 = , , , R S = , , S R = , , , (R S) P=R (S P) (设设 R X Y, S Y Z, P Z W) Rm = R R R (m个

14、个R) 28 逆关系逆关系 (Inverse) R 1 = | R 互逆互逆 (R 1) 1 = R 定理定理1: 设设R , S都是都是从从A到到B的二元关系的二元关系,则则 (R S) 1 = R 1 S 1 (R S) 1 = R 1 S 1 (A B) 1 = B A (R - S) 1 = R 1 - S 1 定理定理2: 设设R X Y,S Y Z,则则 (R S) 1 = S 1 R 1 3 3、关系性质与闭包、关系性质与闭包 概念概念： 自反的自反的, 反自反的反自反的, 对称的对称的, 反对称的反对称的, 传递的传递的 自反闭包自反闭包 r(R),对称闭包对称闭包 s(R),

15、 传递闭包传递闭包 t(R) 30 自反的自反的 Reflexive 若若 xA，都有，都有 R, 则称则称 R 是是自反自反的的. 反自反的反自反的 Anti-Reflexive 若若 xA，都有，都有 R, 则称则称 R 是是反自反反自反的的. 实例：实例：A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3 R2 自反自反 ，R3 反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的. 注意：讨论关系性质时，均假定注意：讨论关系性质时，均假定R为某个集合为某个集合A上的上的 二元关系，即二元关系，即R A A. 31 对称的对

16、称的 Symmetric 对对任意任意x,y A,满足满足, 若若 R,则则 R 反对称的反对称的 Anti-symmetric 对对任意任意x,y A,满足满足，若若 R 且且 R,则则x=y R1：对称和反对称；：对称和反对称； R2：只有对称；：只有对称；R3：只有反对称；：只有反对称； R4：不对称、不反对称：不对称、不反对称 例：设例：设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1,，R2, R3,，R4, 32 传递的传递的 Transitive 对任意的对任意的x,y,z A, 满足满足: 若若 R 且且 R, 则则 R, 则称则称R是

17、传递的是传递的. 例：例： 设设 A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3 R1和和R3是是A上的传递关系上的传递关系, R2不是不是A上的传递关系上的传递关系. 33 自反自反闭包闭包 ( Reflexive closure) 设设R是是A上上的二元关系的二元关系,如果有另一个关系如果有另一个关系R满足满足: R是自反的是自反的; R R; 对于任何自反的关系对于任何自反的关系R”,若若R“ R, 则有则有R“ R. 则则称关系称关系R为为R的自反闭包的自反闭包. 记为记为 r(R). 注注: 类似地类似地可定义可定义对称对称闭包闭包 s(

18、R) 和和传递闭包传递闭包 t(R)。 34 定理定理 : 设设R为为A上的关系上的关系, 则有则有 (1) r(R)=RIA (2) s(R)=RR 1 (3) t(R)=RR2R3 特殊地，特殊地， 若若|A|=n， 则则 t(R)=RR2 Rn 例例: 设设A=1,2,3, 在在A上定义表示上定义表示 R = ,. 求求 r(R), s(R), t(R). 4 4、等价关系、等价关系 概念概念： 等价关系等价关系, , 等价类等价类, , 商集商集, , 划分划分. . 36 等价关系等价关系 (Equivalence relation) 设设 R 为集合为集合 A 上的一个二元关系上的

19、一个二元关系。若若 R 是自反的是自反的, 对称的对称的, 传递的传递的, 则称则称 R 为为 A 上的等价关系上的等价关系. 例例: 令令A=1,2,3,4 R= , , , , , , , 37 等价类等价类 (Equivalence class) 设设R为集合为集合A上的等价关系上的等价关系, 对对 a A, 定义定义: aR = x|x A 且且 R 称之为称之为元素元素a关于关于R的等价类的等价类。 例例(续上续上): 1R=4R=1,4 2R=3R=2,3 定理定理1: 给定给定A上的等价关系上的等价关系R,对于对于a,b A有有 aRb iff aR=bR 38 商集商集 (Qu

20、atient set) 设设R是是A上的等价关系上的等价关系，定义定义 A/R=aR|a A 称之为称之为A关于关于R的商集的商集. 例例: (见上例见上例)中商集为中商集为: 1R,2R 或更详细写或更详细写成成 1,4,2,3 39 划分划分 （Partition） 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A)满足满足: (1) (2) x y(x,y xyxy=) (3) = A 则称则称是是A的一个的一个划分划分, 称称中的元素为中的元素为A的的划分块划分块. 40 定理定理2: 给定集合给定集合 A 上的等价关系上的等价关系 R, 则商集则商集 A/R 是是 A

21、的一的一 个划分个划分. 例例(见上例见上例): A/R=1,4,2,3是一个划分是一个划分. 定理定理 4: 设设R1和和R2为非空集合为非空集合A上的一个等价关系上的一个等价关系, 则则 R1 = R2 iff A/R1 = A/R2. 定理定理3: 集合集合A的一个划分的一个划分诱导出诱导出A上的一个等价关系上的一个等价关系R. R 定义为定义为R= | x,y A 且且x,y在在的同一分块中的同一分块中 例例: 设设A=a,b,c,d,e的一个划分为的一个划分为S= a,b,c,d,e . 求由求由 划分划分S诱导的诱导的A上的一个等价关系上的一个等价关系R. 5 5、偏序关系、偏序关

22、系 概念概念： 偏序偏序, , 哈斯图哈斯图, , 全序全序( (线序线序), ), 极大元极大元/ /极小元极小元, , 最大最大 元元/ /最小元最小元, , 上界上界/ /下界下界. . 42 偏序偏序 (Partial Ordering) 设设A是一个集合是一个集合. 如果如果 A 上的二元关系上的二元关系 R 是是自反的自反的,反对称反对称 的和传递的的和传递的, 则称则称R是是A上的一个上的一个偏序关系偏序关系. 记记R为为“ ”, 且且 称序偶称序偶 为为偏序集偏序集。 例例: 设设A=a,b,在在 P(A)上的二元关系上的二元关系R为包含关系为包含关系, 即即 R= |x,y

23、P(A) 且且 x y 证明证明: 是偏序集是偏序集. 43 全序全序/线序线序(Total Ordering/ Linear Ordering) 设设 为偏序集为偏序集, 若对任若对任 意的意的x,y A满足满足: x y或或 y x 则称则称 为为全序关系全序关系. 为为全序集全序集. 例例: (1) Z为整数集，为整数集，为全序集。为全序集。 (2) 设设A=a,b，则，则是偏序集是偏序集，但不是全序集。，但不是全序集。 44 覆盖（覆盖（Covering） 设设为偏序集为偏序集,若若x,y A, x y,x y且没有其它元素且没有其它元素z满足满足x z,z y, 则称则称y覆盖覆盖x

24、. 记记covA= |x,y A且且y覆盖覆盖x 例例:cov(P(A)= , 45 哈斯图哈斯图(Hasse Diagram) 作图规则作图规则 用小元圈用小元圈 代表元素代表元素; 若若x y且且x y,则将代表则将代表y的小元圈画在代表的小元圈画在代表x的小元圈之上的小元圈之上; 若若 covA, 则在则在x,y之间之间用直线用直线连接连接。 例例: 画出画出 的哈斯图的哈斯图. 46 其他例子其他例子 偏序集偏序集和和 的哈斯图的哈斯图. 47 已知偏序集已知偏序集的哈斯图如下图所示的哈斯图如下图所示, 试求出集合试求出集合A 和关系和关系R的表达式的表达式. 解解 A= a, b,

25、c, d, e, f, g, h R=,IA 实例实例 48 极极小小元元(Minimal Element)/极极大大元元(Maximal Element) 设设为偏序集为偏序集, B A (1) 对对b B，若若B中不存在中不存在x满足满足: b x且且 x b 则称则称b为为B的的极极小小元元. (2) 对对b B，若若B中不存在中不存在x满足满足: b x且且 b x 则称则称b为为B的的极极大大元元. 49 最最小小元元(The Smallest Element) / 最最大大元元 (The Greatest Element) 设设为偏序集为偏序集,B A,若有某个若有某个b B (1

26、) 对于对于B中每一个元素中每一个元素x都有都有b x，则称则称b为为B的的最最小小元元. (2) 对于对于B中每一个元素中每一个元素x都有都有x b，则称则称b为为B的的最大元最大元. 50 下界下界(Lower Bound) / 上界上界(Upper bound) 设设为偏序集为偏序集, B A (1) 若有若有a A,且对且对 x B 满足满足 a x，则称则称a为为B的的下下界界。 进一步进一步:设设a为为B的的下下界界,若若B的所有的所有下下界界y均有均有y a, 则称则称a为为B的的下下确界确界 ，记为，记为glb B。 (2) 若有若有a A,且对且对 x B 满足满足 x a，

27、则称则称a为为B的的上界上界。 进一步进一步:设设a为为B的上界的上界,若若B的所有上界的所有上界y均有均有a y, 则称则称a为为B的的上确界上确界，记为，记为lub B。 . 51 实例实例 设偏序集设偏序集，求，求A的极小元、最小元、极大元、最的极小元、最小元、极大元、最 大元，设大元，设B b,c,d , 求求B的下界、上界、下确界、上确界的下界、上界、下确界、上确界. 解解 极小元：极小元：a, b, c, g； 极大元：极大元：a, f, h； 没有最小元与最大元没有最小元与最大元. B的下界和最大下界都不存在；的下界和最大下界都不存在； 上界有上界有 d 和和 f, 最小上界为最

28、小上界为 d. 六、函数六、函数 概念概念： 函数函数, , 常函数常函数, , 恒等函数恒等函数, , 满射满射, ,入射入射, ,双射双射， 复合函数复合函数，反，反函数函数 53 函数函数 设设X,Y为两个集合为两个集合,f X Y, 若对若对 x X, !y Y,满足满足: f, 则称则称f为为函数函数.记为记为:f:XY 定义域定义域: domf=X 值域值域: ranf (有时记为有时记为f(X)=f(x)|x X 例例: 判别下列关系能否构成函数判别下列关系能否构成函数. f1 = |y1,y2 R 且且y22=y1 f2 = |y1,y2 R 且且 y2 = y12 f3 =

29、|y1,y2 R 且且y22 =y1 f4 = |y1,y2 N 且且y1 + y210 54 函数相等函数相等 设设f和和g都是从都是从A到到B的函数的函数, 若对任意若对任意x A,有有f(x)=g(x),则则 称称f和和g相等相等.记为记为f=g 函数的个数函数的个数 设设f:AB,|A|=m, |B|=n.记记 BA=f|f: AB, 则则| BA |= nm 55 实例实例 设设A=1,2,3, B=a,b, 求求BA. 解：解：BA= f0, f1, , f7, 其中其中 f0 = , f1 = , f2 = , f3 = , f4 = , f5 = , f6 = , f7 = ,

30、 56 满射满射(Surjective) (到上映射到上映射) 设设 f: X Y, 若若 ranf = Y, 则称则称 f 为为满射的满射的. 入射入射(Injective) (一对一映射一对一映射) 设设f: XY, 对对 x1, x2 X, 满足满足: 若若 x1 x2, 则则 f(x1) f(x2), 称称 f 为为入射的入射的. 双射双射(bijective) (一一对应映射一一对应映射) 设设f:XY, 若若f既是满射的既是满射的, 又是入射的又是入射的. 则称则称f是是双射的双射的. 57 例：判断下面函数是否为单射例：判断下面函数是否为单射, 满射满射, 双射的双射的, 为什么

31、为什么? (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+为正实数集为正实数集. 单射单射 满射满射 双射双射 （1） （2） （3） （4） （5） 58 几个特殊函数几个特殊函数 (1)设设 f:AB, 如果存在如果存在cB使得对所有的使得对所有的 xA都有都有 f(x)=c, 则称则称 f:AB是是常函数常函数. (2) 称称 A上的恒等关系上的恒等关系IA为为A上的上的恒

32、等函数恒等函数, 对所有的对所有的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 为为严严 格单调递增的格单调递增的. 类似的也可以定义类似的也可以定义单调递减单调递减和和严格单调递严格单调递 减的减的函数函数 59 (4) 设设A为集合为集合, 对于任意的对于任意的A A, A的的特征函数特征函数 A :A0,1定义为定义

33、为 A(a)=1, aA A(a)=0, aA A (5) 设设R是是A上的等价关系上的等价关系, 令令 g:AA/R g(a)=a, aA 称称 g 是从是从 A 到商集到商集 A/R 的的自然映射自然映射 几个特殊函数（续）几个特殊函数（续） 60 复合函数复合函数 设设 f:XY,g:YZ, 定义定义: fog = |x X且且z Z且可找到且可找到y Y使使y=f(x),z=g(y) 称称fog为为f与与 g 的复合函数的复合函数. 注注: (1) 课本中课本中关系关系、函数均使用“、函数均使用“右复合右复合”。函数复合在习惯”。函数复合在习惯 上也常采用“上也常采用“左复合左复合”，

34、”，g f(a)=g(f(a)。读文献时须留意。读文献时须留意。 (2) 函数的复合运算可结合函数的复合运算可结合. 61 函数复合与函数性质函数复合与函数性质 定理定理 设设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也是双射的也是双射的 62 反反函数函数（逆函数）（逆函数） 设设f:XY是一个双射函数是一个双射函数，那么，那么f -1是是YX

35、的双射函数的双射函数. 称称f -1为为f的的反反函数函数. 注：注： （1）互逆互逆 (f -1 )-1=f （2）设）设 f:AB是双射的是双射的, 则则 f 1 f = IB, f f 1 = IA 七、集合基数七、集合基数 概念概念： 基数基数, , 等势等势, , 有限集有限集/ /无限集无限集, , 可数集可数集, , 不可数集不可数集 64 16381638年年, ,意大利天文学家意大利天文学家GalieoGalieo比较集合大小的困惑：比较集合大小的困惑： “部分”等于“整体”？“部分”等于“整体”？ N=0,1,2,3,N=0,1,2,3, N N(2) (2)=0,1,4,

36、9, =0,1,4,9, 18741874- -18971897年年, ,德国数学家德国数学家CantorCantor 冲破传统观念冲破传统观念, ,采用数采用数“数数”的方法的方法观察集合大小。观察集合大小。 基数基数(Cardinality) 用来用来衡量集合大小的一个概念衡量集合大小的一个概念. 对于有限集合集来说对于有限集合集来说, 集合的集合的 基数就是其中所含元素的个数基数就是其中所含元素的个数. 65 等势的（基数相同）等势的（基数相同） 设设A, B是集合是集合, 如果存在着从如果存在着从A到到B的双射函数的双射函数, 就称就称 A和和B是是等势的等势的, 记作记作AB. 如果

37、如果A不与不与B 等势等势, 则记作则记作A B. 注：通常将注：通常将A的的基数基数记为记为 |A|. 重要等势结果重要等势结果 N Z Q NN 任何实数区间都与实数集合任何实数区间都与实数集合R等势等势 0,1NR 66 012 02 )(,NZ: xx xx xff 则则 f 是是Z到到N的双射函数的双射函数. 从而证明了从而证明了ZN. （1）证明：）证明： ZN. 证：证： 67 m nmnm nmff 2 )(1( ),(,NNN: （2）NQ NNN. NN中所有的元素排成有序图形中所有的元素排成有序图形 68 - -2/12/1 55 - -1/11/1 44 - -3/13

38、/1 1818 2/12/1 1010 3/13/1 1111 0/10/1 00 1/11/1 11 - -2/22/2 - -1/21/2 33 - -3/23/2 1717 2/22/2 3/23/2 1212 0/20/2 1/21/2 22 - -2/32/3 66 - -1/31/3 77 - -3/33/3 2/32/3 99 3/33/3 0/30/3 1/31/3 88 - -2/42/4 - -1/41/4 1515 - -3/43/4 1616 2/42/4 3/43/4 1313 0/40/4 1/41/4 1414 PLAY NQ. 双射函数双射函数 f:NQ, 其中

39、其中f(n)是是n下方的有理数下方的有理数. 69 2 12 tan)(,R)1 , 0( : x xff xx nx x x xf nn 其它其它 ,.2 , 1,2/12/1 12/1 02/1 )( 1 2 (6) 对任何对任何a, bR, ab, 0,1a,b，双射函数，双射函数 f:0,1a,b, f(x)=(b a)x+a 类似地可以证明类似地可以证明, 对任何对任何a, bR, ab, 有有(0,1)(a,b). (4) (0,1)R. 其中实数区间其中实数区间 (0,1)=x| xR0x1. 令令 (5) 0,1(0,1). 其中其中(0,1)和和0,1分别为实数开区间和闭区间

40、分别为实数开区间和闭区间. 令令 f : 0,1(0,1) 70 (7) 设设A为任意集合为任意集合, 则则P(A)0,1A. 证证 如下构造从如下构造从P(A) 到到 0,1A 的函数的函数 f:P(A)0,1A, f(A)= A, AP(A). 其中其中 A是集合是集合A的特征函数的特征函数. 易证易证 f 是单射的是单射的. 对于任意的对于任意的 g0,1A, 那么有那么有 g:A0,1. 令令 B= x| xAg(x)=1 则则B A, 且且 B=g, 即即 BP(A), f(B)=g. 从而证明了从而证明了f 是满射是满射 的的. 由等势定义得由等势定义得 P(A)0,1A. 71

41、康托定理康托定理 (1) N R； (2) 对任意集合对任意集合A都有都有A P(A). 证明思路证明思路（对角线方法对角线方法 Diagonal method）：）： (1) 只需证明任何函数只需证明任何函数 f:N0,1都不是满射的都不是满射的. 任取函数任取函数 f:N0,1, 列出列出 f 的所有函数值，然后构造的所有函数值，然后构造 一个一个0,1区间的小数区间的小数b，使得，使得b与所有的函数值都不相与所有的函数值都不相 等等. (2) 任取函数任取函数 f:AP(A)，构造，构造B P(A)，使得，使得B与与 f 的任的任 何函数值都不等何函数值都不等. 72 有限集有限集(Finite set)/无限集无限集 (Infinite set) 设设A为一个集合为一个集合. 若存在某个自然数若存在某个自然数n, 使得使得A与集合与集合 0,1,n-1等势等势, 则称则称A是有限的是有限的. 若集合若集合A不是有