《离散数学导论(盘) 教学课件 ppt 作者 王元元 张桂芸 第七章演示文稿》由会员分享，可在线阅读，更多相关《离散数学导论(盘) 教学课件 ppt 作者 王元元 张桂芸 第七章演示文稿（32页珍藏版）》请在金锄头文库上搜索。
1、第 七 章 基 数,7.l 有限集和无限集,7.2 基 数,第七章 基数,7.1.1 有限集、可数集与不可数集,7.1.2 无限集的特性,第七章 基数,7.l 有限集和无限集,7.2.1 有限集、可数无限集 和连续统的基数,7.2.2 基数比较,7.2.3 基数算术,第七章 基数,7.2 基 数,第七章 基数,7.1.1 有限集、可数集与不可数集,7.l 有限集和无限集,定义 7.1 集合A称为有限集，如果存在集合 0，1，2，n-1 （自然数n）到A，或A到该集合的双射；否则称A为无限集。,第七章 基数,7.1.1 有限集、可数集与不可数集,7.l 有限集和无限集,定理7.1 任何有限集的任
2、意子集为有限集。,定理7.2 任何含有无限子集的集合必定 是无限集。,第七章 基数,7.1.1 有限集、可数集与不可数集,7.l 有限集和无限集,定义 7.2 集合A称为可数无限集（countable infinite sets）， 如果存在双射f：NA（或双射f：AN）。其它无限集称为不可数无限集。有限集和可数无限集统称为可数集（countable sets）。因此，不可数集即不可数无限集。,第七章 基数,7.1.1 有限集、可数集与不可数集,7.l 有限集和无限集,定理7.3 整数集为可数无限集。,定义7.3 称集合A是可枚举的（recursively enumerable） 如果存在满射
3、f：NA。f被称为枚举函数。,第七章 基数,7.1.1 有限集、可数集与不可数集,7.l 有限集和无限集,定理7.4 非空集合A是可数集当且仅当 A是可枚举的。,定理7.5 有理数集是可数集。,定理7.6 可数个可数集的并集是可数的。,第七章 基数,7.1.1 有限集、可数集与不可数集,7.l 有限集和无限集,定理7. 7 如果A是有限集，B是可数集，那么A 到B的全体函数的集合BA为可数集。,定理7.8 实数集的子集0，1区间是不可数集。,第七章 基数,7.1.2 无限集的特性,7.l 有限集和无限集,定理7.9 任何无限集合均含有一可数无限子集。,定理7.10 集合A为无限集，当且仅当有A
4、的真子集A0及双射函数f：AA0。,第七章 基数,7.l 有限集和无限集,7.1.2 无限集的特性,选择公理（choice axiom） 对任何一个集合族A = Ad dD， 总有集合B，使B与诸Ad的交均为 单元素集合。常称B为A的代表元素集。,第七章 基数,7.2 基 数,7.2.1 有限集、可数无限集和连续统的基数,定义7.4 称集合A的基数（cardinal number）为 n(n为自然数)，如果有双射f:0,1,2, ,n-1A, 或双射f：A0,1,2, ,n-1。记为 A = n 。,第七章 基数,7.2 基 数,7.2.1 有限集、可数无限集和连续统的基数,定义7.5 称集合
5、A的基数为0，如果有双射 f：NA，或双射f：AN，N为自然数集。 记为 A = 0。,第七章 基数,7.2 基 数,7.2.1 有限集、可数无限集和连续统的基数,定义7.6 称集合A的基数为C，如果有 双射f：0，lA，或双射f：A0，1。 记为 A = C。具有基数C的集合常称为 连续统（continuum）。,第七章 基数,7.2 基 数,7.2.1 有限集、可数无限集和连续统的基数,定理7.11 实数集上的任何闭区间a，b，开区 间(a,b) (ab),以及实数集本身都是连续统。,第七章 基数,7.2 基 数,7.2.2 基数比较,定义7.7 设A，B为任意集合。 （1）称A，B基数相
6、等，记为 A = B ，如果有双射f：AB或双射 f：BA。 （2）称A的基数小于等于B的基数，记为 A B ，如果有单射f：AB或满射 f：BA。 （3）称A的基数小于B的基数，记为 A B ，如果 A B , 且 A B 。,第七章 基数,7.2 基 数,7.2.2 基数比较,定理7.12 基数相等关系为一等价关系， 即对任何集合A，满足： （1） A = A 。 （2）若 A = B ，则 B A 。 （3）若 A = B ， B C ， 则 A = C 。,第七章 基数,7.2 基 数,定理7.13 对任意集合A，B，C， （1） A A 。 （2）若 A B ， B C ， 则 A
7、C 。,7.2.2 基数比较,第七章 基数,7.2 基 数,7.2.2 基数比较,定理7.14 对任意集合A，B，或者 A B ，或者 A = B ，或者 B A ，且不能兼而有之。,定理7.15 对任意集合A，B，如果 A B ， B A ，那么 A = B 。,第七章 基数,7.2 基 数,7.2.2 基数比较,定理 7.16 (N)（N为自然数集）为连续统。,定理7.17 0是最小的无限集基数，即没有无限集A，使 A 0,第七章 基数,7.2 基 数,7.2.2 基数比较,定理7.18 对任一基数，总存在集合，其基数大于，即 。,定理7.19 设A，B为任意有限集，那么 （1） AB =
8、 A B - AB （2） AB min( A , B ) （3） A - B = A - AB （4） (A) = 2A,7.2 基 数,第七章 基数,7.2.3 基数算术,定理7 . 20 设A1，A2,An，是n个有限集合， 那么 A1A2An =,定义7.8 设,分别为集合A，B的基数，AB = ，那么定义基数和为+= AB ,第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.21 对任意基数, （1）+=+ （2）(+)+=+(+),第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.22 设,为任意基数，那么 （1）当,时，+ （2）当，时， +,第七章 基数,7
9、.2 基 数,7.2.3 基数算术,定理7.23 对任何无限集基数，有 ,定理7.24 设, 为基数，为无限集基数， ，那么 + = ,定义7.9 设, 分别是集合A，B的基数， 那么与的基数积定义为 = A B,第七章 基数,7.2 基 数,7.2.3 基数算术,第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.25 设,为任意基数，那么 （1）= （2）()=() （3）(+)=+ , (+) = + ,第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.26 设,，为任何基数，那么 （1）当,时，。 （2）当,时，。,定理7.27 对任何无限集基数，有 = ,第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.28 设 ,为基数， 为无限集基数， 且， 0,那么 = ,定义7.10 设 ,分别是集合A，B的基数，那么基数的幂，的次幂定义为 = A B ,第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.29 设 ,为任意基数，那么 （1）= + （2）() = （3）() = ,定理7.30 设 ,为任意基数，那么 （1）如果，那么 。 （2）如果 ，那么 。,第七章 基数,7.2 基 数,7.2.3 基数算术,定理7.31 对任意无限基数，= 2 。 （注意，2为集合0,1。）,
