离散数学第四章第二节.pptVIP

第4-2讲 集合的基数 1. 自然数集合 2. 等势 3. 可数集 4. 不可数集 5. 基数的比较 6. 第4-2讲 作业 1、自然数集合（1） 有时我们会对集合中元素的个数感兴趣，利用映射可以研究这一问题。为此, 要用到自然数集合，它可由空集及其后继集合的概念来产生。 1、自然数集合（2） 为书写方便，记空集为0，并且用1，2，3，…表示序列 ?， {?}， {?，{?}}，{?，{?}，{?,{?}}，…… 中的其它元素，就得到序列： 0，1，2，3，…… 1、自然数集合（3） 自然数集N可用皮亚诺公理来概括： 1. 0?N; 2. 对每个n?N,恰有唯一的n+?N; 3. 不存在n?N,使得n+=0; 4. 如果n+= m+,则n=m; 5. 如果S?N;且0?S;同时,若n?S,则n+?S；那么S=N。 2、等势（1） 2、等势（2） 2、等势（3） 3、可数集（1） 自然数集是无限的，但是否所有的无限集都能与自然数集建立一一对应呢？ 3、可数集（2） 定理5 任一无限集 必含有可数子集。 3、可数集（3） 定理7 可数集的任一无限子集是可数的。 （证明从略） 4、不可数集（1） 定理11 实数集R是不可数的。 4、不可数集（2） 将实数集R的基数记为 ，称为连续统的势。直观上看，自然数集N是实数集R的子集，那么， 。 5、基数的比较（1） 定义6 设A、B为集合，如果存在A到B的入射，则称A的基数小于或等于B的基数，记作K[A]?K[B]。如果存在A到B的入射，但不存在双射，则称A的基数小于B的基数，记作K[A]K[B]。 5、基数的比较（2） 定理14 设A为有限集合，K[A] 。 5、基数的比较（3） 定理15 (Cantor定理) 设M为集合，则K[M]K[?(M)]。 (证明从略) 5、课堂练习 练习1 证明 [0，1]与（0，1）表示的集合有相同的基数。 第4-2讲 作业 P164 1 P170 1a)c) * * 若A=?，则可产生下列后继集序列： ?， ?+，(?+)+ ，((?+)+ )+，…… 按后继集定义，该序列就是： ?， ??{?}， ??{?}?{??{?}} ，…… 可化简为： ?， {?}， {?，{?}}，{?，{?}，{?,{?}}}…… 定义1 给定集合A，其后继集定义为集合： A+=A?{A} 这里的0、1、2、3……不过是集合的代号而已，完全可用任何其它的符号取代。详细的说就是： 0 = ? 1 = 0+ = {?} = {0} 2 = 1+ = {?，{?}} = {0，1} 3 = 2+ = {?，{?}，{?,{?}} } = {0，1，2} …… n+1= n+ = {0，1，2，3，…，n} …… 如此可得“自然数集”：N={0，1，2，3，…}，它是集合的集合！ 皮亚诺公理使自然数具有如下结构: 而排除了左面结构的可能： 定义3 当且仅当集合A、B元素之间存在一一对应，称集合A与B是等势的，或者说集合A、B有相同的基数，记作A~B。集合A的基数记作K[A]。 定义2 给定两个集合P与Q，如果存在双射f:P?Q，则称集合P和Q的元素之间存在一一对应。 例如，自然数集N与非负偶数集M是等势的。因为存在双射 f:N?M，f(n)=2n。 例1 设R为实数集，S={x|x?R?0x1}，证明S~R。 证：作映射f:R?S,f(x)=(1/?)arctgx+1/2,显然，f是双射。 证：设集合A?S，则A~A，故~是自反的。 设集合A、B?S，如果A~B，则存在双射f:A?B，因而fC是B到A的双射，所以B~A。故~是对称的。 设集合A、B、C?S，如果A~B，B~C,则存在双射f:A?B，g:B?C,因而g?f是A到C的双射，所以A~C。故~是传递的。 综上述，等势关系~是等价关系。 定理2 设集合S的元素为集合(称S为集合族)，则S上的等势关系是等价关系。 等价关系~导出集合S的一个划分，这个划分的等价类叫基数类。属于同一基数类的集合有相同的基数，称它们“同基”。 定理3 自然数集N是无限集。 证明：只须证集合N与集合Nm不等势。即证不存在Nm到N的双射。 假设存在双射f:Nm?N， 令k=1+max{f(0), f(1),…,f(m)}，则