离散数学与 function .pptVIP

* 定理4-5.1 A为可数集的充分必要条件是A可以排列成A =｛a1,a2, ….,an, …｝的形式。 证明：如果A=｛a1,a2, ….,an, …｝ ，那么存在 f : A→N 且f (an) = n-1 (n = 1,2, …) f 为双射函数。故 A～N ，即 A 为可数集。 反之，如果 A 可数，那么 A～N ，则存在双射函数 f : N→A , 令 f (n) = an+1 (n = 0,1,2, …) 故 A=｛a1,a2, ….,an, …｝。 说明：此定理可以作为A 是可数集的一个等价定义，也是证明 A 可数的一个实用方法。 * 定理4-5.2 任一无限集必含有可数子集。 证明： 定理4-5.3 任一无限集必与其某一个真子集等势。 证明：设 M 为无限集，由定理4-5.2可知A=｛a1,a2, ….,an, …｝, 且A ?M。设 M-A = B ，定义函数 f: M→M-｛a1｝，且 f (x) = an+1( x = an , n = 1,2, …), f (x) = x(x?B) 显然 M-｛a1｝?M，且 f 为双射函数。 * 说明： 1、定理4-5.3中某一个真子集不是指所有真子集，如真子集为有限集，则有限集与无限集是不可能等势的。 2、可以证明 A 有限集是不满足定理4-5.3的（如何证明）。故有 A 无限集当且仅当与其某一个真子集等势，可以作为无限集的等价定义。 * 定理4-5.4 可数集的任何无限子集都是可数的。 证明：设 A 是可数集合，则 A=｛a1,a2, ….,an, …｝,B ?A 为一无限子集，将 A 中的元素从 a1开始，向后检查，不断地删去不在 B 中的元素，则得到新的一列 ai1,ai2, …,ain, … ,故B=｛ ai1,ai2, …,ain, … ｝，即 B 是可数的. * 即 S = ｛a11,a21,a11,a13,a22,a31,a41,a32, …｝ ，所以 S 是可数集。 定理4-5.5 可数个两两不相交的可数集合的并集，仍然是一可数集。 证明：（用排队的方法证明） 设可数个可数集分别表示为： S1 =｛a11,a12,a13, …,a1n, …｝ S2 =｛a21,a22,a23, …,a2n,…｝ S3 =｛a31,a32,a33, …,a3n,…｝ ……………… 令S =S1 ∪S2 ∪…= ，对 S 的元素作如下排列： * 说明： 1、定理4-5.5中 S 中的元素的排列方法是不唯一的。 2、利用定理4-5.4和定理4-5.5可以证明：可数个可数集的并是可数的。（如何证明） * 定理4-5.6 ：N×N是可数集。 证明： 令S1 =｛0,0,0,1,0,2, …,0,n, …｝ S2 = ｛1,0,1,1,1,2, …,1,n, …｝ S3 = ｛2,0,2,1,2,2, …,2,n, …} ……………… 则N×N= 由定理4-5.5可知 N×N是可数集。 说明：注意此种证明方法与教材上方法的差异 * 定理4-5.7 有理数集 Q 为可数集。（用排队法证明） 证明：一切有理数均呈±n/m(n,m∈N,m≠0) 。现将所有±n/m 按下列次序排列： （1）正分数按其分子、分母之和的大小顺序排列：从小到大。 （2）正分数的分子、分母之和相同者按分子大小顺序排列： 从大到小。 （3）将0放在首位，与正分数具有相同形式的负分数排于正分数之后。按照上述规则可得： 0,1/1,-1/1,2/1,-2/1,1/2,-1/2,3/1,-3/12/2,-2/2,1/3,-1/3, … 故所有呈±n/m 状的数所组成的集合为可数集，而 Q 为其无限子集，由定理4-5.4知 Q为可数集。 * 不可数的无限集 概念：连续统 并非所有的无限集均为可数集。选取（0,1）作为新的“标准集合”，记（0,1）的基数为 ，如果 A～(0,1) ，那么K[A] = 。 也称作连续统的势。 * 定理4-5.8 实数集R是不可数的。（用反证法证明） 证明： * 关于定理4-5.8的证明几点说明： 1、仅由 0,1 构成的无限序列集合是不可数的。 即 T=｛a0a1a2…an…|n∈N,an=0or1｝为不