离散数学 -贾振华 第六章 集合的基数.pptVIP

第6章 集合的基数 本章学习目标 主要内容 6.1 基数的概念 6.1 基数的概念 6.1 基数的概念 6.1 基数的概念 6.2 可数集和不可数集 6.2 可数集和不可数集 6.2 可数集和不可数集 6.2 可数集和不可数集 6.2 可数集和不可数集 6.2 可数集和不可数集 6.2 可数集和不可数集 6.2 可数集和不可数集 6.3 基数的比较 6.3 基数的比较 6.3 基数的比较 6.3 基数的比较 6.3 基数的比较 6.3 基数的比较 本章小结 * 在线教务辅导网： 教材其余课件及动画素材请查阅在线教务辅导网 QQ:349134187 或者直接输入下面地址： 集合的基数就是指集合中元素的个数，由此我们划分了有限集和无限集。由于无限集无法用确切的个数来描述，因此如何描述无限集的基数和比较无限集之间的大小要在本章中进一步讨论。通过本章学习，读者应掌握以下内容： l???????? （1）? 有限集和无限集 l????????? （2）集合的基数 l????????? （3）集合的等势 l????????? （4）可数集和不可数集 （5）基数的比较 6.1 基数的概念 6.2 可数集和不可数集 6.3 基数的比较 定义6.1.1 设X、Y为两个集合，如果存在从X到Y的双射函数，则称X和Y是等势的，记作X≈Y。 （1）设有集合 O+={x | x∈N，x是奇数}，证明：O+≈N。 （2）设R为实数集合，证明 ：（0，1）≈R 证明 （1）由于存在函数f：N→O+，且n∈N，f（n）=2n+1，不难证明，f是双射函数， 因而，O+≈N成立。 （2）令f：（0，1）→R f（x）= tgπ（2x-1）/2 （其中x∈（0，1）） 显然，f是双射函数，因而，（0，1）≈R。 例6.1.1 证明以下集合之间的等势。 定理6.1.1 设X、Y、Z为任意的集合，则 ⑴ X≈X； ⑵ 若X≈Y，则Y≈X； ⑶ 若X≈Y，Y≈Z，则X≈Z。 定义6.1.2 如果有一个从集合{0，1，……，n-1}到X的双射函数，即X与某个自然数n等势，则称集合X是有限的，否则称集合X是无限的。 定理6.1.2 自然数集合N是无限的。 定义6.1.3 设X为任意集合，称card X为集合X的基数，并作以下规定： （1）对于任意的集合X和Y，规定card X = card Y ，当且仅当 X≈Y； （2）对于任意有限集合X，规定与X等势的那个唯一的自然数n为X的基数，记作 card X = n （3）对于自然数集合N，规定 card N = （读作阿列夫零） （4）对于开区间（0，1），规定 card（0，1）= （读作阿列夫） 例6.1.2 证明区间[0，1]与（0，1）基数相同。 证明 显然只需证明 [0，1]≈（0，1）， 定义函数f：[0，1] → （0，1），对于任意x∈[0，1]，有 f（x） = 可证f是双射函数，因而，[0，1]与（0，1）基数相同。 定义6.2.1 凡是与自然数集合N等势的集合，称为可数集合，其基数记为：。 例如，X = {1，4，9，16，…，n2，…} Y = {1，1/2，1/3， …，1/n，…} Z = {x | x∈N，x是素数} 均为可数集。 定理6.2.1 集合X为可数集的充分必要条件是可以排列成 X={x1，x2，…，xn，…} 的形式。 6.2.1 可数集 定理6.2.2 任一无限集必含有可数子集。 定理6.2.3 任意无限集，一定与它的某一真子集等势。 证明 设X为无限集合，现从X中任意取出一个元素，记为x1，因为X是无限的，显然X－{x1}还是无限集合，然后从X－{x1}中再取出一元素，记为x2，而X－{x1，x2}还是无限的，所以又可再取一元素x3，如此重复这一过程，就可得到X的可数子集。 证明 设X为无限集合，根据定理6.4，X必含有可数子集A＝{a1， a2， …， an， …}，设B=X－A，定义函数f：X→X－{a1}，使得f（an）=an+1 （n=1， 2，…），而对于任意元素b∈B，有f（b）=b，显然f是双射函数，定理得证 6.2.1 可数集 定理6.2.4 可数集的任何无限子集是可数的。 证明 设X为可数集合，YX为一无限子集。现将X中的元素排列成x1，x2，…，xn，…，从x1开始，向后检查，依次将Y中的元素删去，这些元素就组成了一个新的序列xi1，xi2，…，xin，…，它与自然数一一对应，所以Y是可