欢迎来到天天文库
浏览记录
ID:40320626
大小:638.00 KB
页数:23页
时间:2019-07-31
《离散数学 贾振华 第六章 集合的基数》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第6章集合的基数本章学习目标集合的基数就是指集合中元素的个数,由此我们划分了有限集和无限集。由于无限集无法用确切的个数来描述,因此如何描述无限集的基数和比较无限集之间的大小要在本章中进一步讨论。通过本章学习,读者应掌握以下内容:l(1)有限集和无限集l(2)集合的基数l(3)集合的等势l(4)可数集和不可数集(5)基数的比较主要内容6.1基数的概念6.2可数集和不可数集6.3基数的比较6.1基数的概念定义6.1.1设X、Y为两个集合,如果存在从X到Y的双射函数,则称X和Y是等势的,记作X≈Y。(1)设有集合O+={x
2、x∈N,x是奇数},
3、证明:O+≈N。(2)设R为实数集合,证明:(0,1)≈R证明(1)由于存在函数f:N→O+,且n∈N,f(n)=2n+1,不难证明,f是双射函数,因而,O+≈N成立。(2)令f:(0,1)→Rf(x)=tgπ(2x-1)/2(其中x∈(0,1))显然,f是双射函数,因而,(0,1)≈R。例6.1.1证明以下集合之间的等势。6.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等势,则称
4、集合X是有限的,否则称集合X是无限的。定理6.1.2自然数集合N是无限的。6.1基数的概念定义6.1.3设X为任意集合,称cardX为集合X的基数,并作以下规定:(1)对于任意的集合X和Y,规定cardX=cardY,当且仅当X≈Y;(2)对于任意有限集合X,规定与X等势的那个唯一的自然数n为X的基数,记作cardX=n(3)对于自然数集合N,规定cardN=(读作阿列夫零)(4)对于开区间(0,1),规定card(0,1)=(读作阿列夫)6.1基数的概念例6.1.2证明区间[0,1]与(0,1)基数相同。证明显然只需证明[0,1]≈(0
5、,1),定义函数f:[0,1]→(0,1),对于任意x∈[0,1],有f(x)=可证f是双射函数,因而,[0,1]与(0,1)基数相同。6.2可数集和不可数集定义6.2.1凡是与自然数集合N等势的集合,称为可数集合,其基数记为:。例如,X={1,4,9,16,…,n2,…}Y={1,1/2,1/3,…,1/n,…}Z={x
6、x∈N,x是素数}均为可数集。定理6.2.1集合X为可数集的充分必要条件是可以排列成X={x1,x2,…,xn,…}的形式。6.2.1可数集6.2可数集和不可数集定理6.2.2任一无限集必含有可数子集。定理6.2.3任
7、意无限集,一定与它的某一真子集等势。证明设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可数集
8、和不可数集定理6.2.4可数集的任何无限子集是可数的。证明设X为可数集合,YX为一无限子集。现将X中的元素排列成x1,x2,…,xn,…,从x1开始,向后检查,依次将Y中的元素删去,这些元素就组成了一个新的序列xi1,xi2,…,xin,…,它与自然数一一对应,所以Y是可数的。6.2.1可数集6.2可数集和不可数集定理6.2.5可数个可数集的并集仍然是一可数集。6.2.1可数集证明设S1,S2,S3,……是可数个可数集,分别表示为:S1={a11,a12,a13,…,a1n,…}S2={a21,a22,a23,…,a2n,…}S3={a3
9、1,a32,a33,…,a3n,…}…………6.2可数集和不可数集定理6.2.5可数个可数集的并集仍然是一可数集。6.2.1可数集令S=S1∪S2∪S3∪…,对S中的元素作以下排列:a11a12a13a14…a21a22a23a24…a31a32a33a34…a41a42a43a44…6.2可数集和不可数集在上面元素的排列中,由左上端开始,其每一斜线上的每一元素的两足码之和都相同,依次为2,3,4,…,各斜线上元素的个数依次为1,2,3,4,…,故A的排列为:a11,a21,a12,a31,a22,a13,…故S是可数的,定理得证。定理6
10、.2.5可数个可数集的并集仍然是一可数集。6.2.1可数集6.2可数集和不可数集定理6.2.6设自然数集合N,则N×N是可数集。定理6.2.7有理数集合Q是可数集。6.2.1可数集6.2可数集
此文档下载收益归作者所有