离散数学无穷集合及基数.ppt
《离散数学无穷集合及基数.ppt》由会员分享,可在线阅读,更多相关《离散数学无穷集合及基数.ppt(29页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、离散数学无穷集合及基数1现在学习的是第1页,共29页第第4节节 无穷集合及其基数无穷集合及其基数 可数集可数集 不可数集不可数集 基数及其比较基数及其比较 康托康托-伯恩斯坦定理伯恩斯坦定理 悖论与公理化集合论悖论与公理化集合论主要内容:主要内容:2现在学习的是第2页,共29页 集合的基数亦称作集合的势。集合的基数亦称作集合的势。粗略的说,就是一个集合的粗略的说,就是一个集合的“规模规模”,它的,它的“大大小小”,或者更确切地说,它有多少个元素。,或者更确切地说,它有多少个元素。通俗的说,集合的势是量度集合所含元素多少的通俗的说,集合的势是量度集合所含元素多少的量。集合的势越大,所含的元素越多
2、。量。集合的势越大,所含的元素越多。很明显,如果集合中只有有限个元素,我们只要很明显,如果集合中只有有限个元素,我们只要数一数它有多少个可以了,这时集合的基数就是其中数一数它有多少个可以了,这时集合的基数就是其中所含元素的个数。所含元素的个数。什么是集合的基数?什么是集合的基数?值得注意的是无限集,它所含的元素有无穷多值得注意的是无限集,它所含的元素有无穷多个,个,这时怎样去数?这时怎样去数?为了解决这个问题,我们首先从伽利略为了解决这个问题,我们首先从伽利略“悖论悖论”说起。说起。3现在学习的是第3页,共29页 1638年意大利的天文学家伽利略发现了下面年意大利的天文学家伽利略发现了下面的问
3、题:的问题:N+=1,2,3,n,与与N(2)=1,4,9,n2,这两个集合,哪一个的元素更多一些?这两个集合,哪一个的元素更多一些?伽利略伽利略“悖论悖论”一方面,凡是一方面,凡是N(2)的元素都是的元素都是N+的元素,也就的元素,也就是说是说N(2)N+,而且由于,而且由于2,3,5等元素都不在等元素都不在N(2)中,所以中,所以N(2)N+。这样看来,。这样看来,N+中的元素要比中的元素要比N(2)中的元素要多。中的元素要多。4现在学习的是第4页,共29页 但另一方面,对于但另一方面,对于N+中的每个元素都可以在中的每个元素都可以在N(2)中找到中找到一个元素与之对应,这样看来,一个元素
4、与之对应,这样看来,N(2)中的元素不比中的元素不比N+中的中的元素要少。元素要少。那么到底那么到底N+与与N(2)中所含元素的个数是否一样呢?如果中所含元素的个数是否一样呢?如果是,那么就有是,那么就有 部分部分=整体?整体?然而按照传统,部分怎么能等于全体呢?这就是伽然而按照传统,部分怎么能等于全体呢?这就是伽利略利略“悖论悖论”,它不仅困惑了伽利略,还使许多数学家,它不仅困惑了伽利略,还使许多数学家亦束手无策。亦束手无策。伽利略伽利略“悖论悖论”5现在学习的是第5页,共29页 1874年,年,Cantor注意到伽利略注意到伽利略”悖论悖论”。在在1874年到年到1897年间完全解决了这个
5、问题。年间完全解决了这个问题。Cantor详细地分析了断定有限集合的元素多少的方详细地分析了断定有限集合的元素多少的方法,即采用数数的方法。他认为法,即采用数数的方法。他认为“数数的过程数数的过程”就是作就是作“一一一一对应的过程对应的过程”。Cantor认为这种认为这种“一一对应一一对应”的方法不仅适用于有的方法不仅适用于有限集,也适用于无限集。限集,也适用于无限集。他牢牢地抓住这个原则,抛弃了部分必定小于全体他牢牢地抓住这个原则,抛弃了部分必定小于全体的教条,经历了大约的教条,经历了大约23年之后,他才冲破了传统观念的束年之后,他才冲破了传统观念的束缚,革命性的解决了伽利略缚,革命性的解决
6、了伽利略“悖论悖论”。Cantor认为在认为在N+与与N(2)之间存在着一一对应之间存在着一一对应(即双射即双射),因此,因此N+与与N(2)的元素个数是相等的。的元素个数是相等的。一一对应与可数集一一对应与可数集6现在学习的是第6页,共29页 定义定义4.1 设设A,B是集合,若存在着从是集合,若存在着从A到到B的双射的双射,就称,就称A和和B等势等势(或或对等对等),记作,记作AB。Cantor把自然数集把自然数集N+称为可数集称为可数集(或可列集或可列集),这是,这是因为它的元素可以一个一个的数出来。因为它的元素可以一个一个的数出来。凡是与自然数集凡是与自然数集N+等势的集合,它们的元素
7、通过一等势的集合,它们的元素通过一一对应关系,也都可以一个一个的数出来,因此:一对应关系,也都可以一个一个的数出来,因此:一一对应与可数集一一对应与可数集 定义定义4.2 凡是与自然数集凡是与自然数集N+等势的集合,称为等势的集合,称为可数集可数集(或或可列集可列集)。7现在学习的是第7页,共29页 显然,显然,N也是可数的也是可数的。Cantor以此为出发点,对无限集合进行考察,他发现以此为出发点,对无限集合进行考察,他发现下面的集合都是可数集:下面的集合都是可数集:(1)ODD=x|x N,x是奇数是奇数N F:NODD F(n)=2n+1(F:N+ODD F(n)=2n-1)(2)EVE
8、N=x|x N,x是偶数是偶数NF:NEVEN F(n)=2n(F:N+EVEN F(n)=2(n-1))(3)N(n)=x|x=mn,m,n N NF:NN(n)F(m)=mn一一对应与可数集一一对应与可数集8现在学习的是第8页,共29页(4)NNN一一对应与可数集一一对应与可数集9现在学习的是第9页,共29页(6)ZZN F:ZN F(n)=2n(n0)F(n)=2|n|-1(n0)的数排成一张表。显然所有的有的数排成一张表。显然所有的有理数都在这张表内。理数都在这张表内。一一对应与可数集一一对应与可数集11现在学习的是第11页,共29页一一对应与可数集一一对应与可数集12现在学习的是第1
9、2页,共29页 注意:以注意:以0/1作为第一个数,按照箭头规定作为第一个数,按照箭头规定的顺序可以的顺序可以“数遍数遍”表中所有的数。但是这个计数表中所有的数。但是这个计数过程并没有建立过程并没有建立N到到Q的双射,因为同一个有理数的双射,因为同一个有理数可能被多次数到。例如可能被多次数到。例如1/1,2/2,3/3,都是有理都是有理数数1。为此我们规定,在计数过程中必须跳过第二为此我们规定,在计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。如次以及以后各次所遇到的同一个有理数。如1/1被被计数,那么计数,那么2/2,3/3,都要被跳过。表中数都要被跳过。表中数p/q上上方的方括号
10、内标明了这个有理数所对应的计数。方的方括号内标明了这个有理数所对应的计数。这样就可以定义双射函数这样就可以定义双射函数f:NQ,其中,其中f(n)是是n下方的有理数。从而证明了下方的有理数。从而证明了NQ。一一对应与可数集一一对应与可数集13现在学习的是第13页,共29页 正是由于这一发现,使得他甚至猜想正是由于这一发现,使得他甚至猜想R也是可数也是可数集,并且着手去证明它。他没有得到预期的结果,集,并且着手去证明它。他没有得到预期的结果,却又作出了更伟大的发现。却又作出了更伟大的发现。Cantor利用它著名的对角线法,证明了利用它著名的对角线法,证明了0,1是不是不可数集,在这个基础上证明了
11、可数集,在这个基础上证明了R也是不可数的,甚至也是不可数的,甚至于于Rn也是不可数的。也是不可数的。Cantor对角线法与不可数集对角线法与不可数集 注注:(1)如果集合如果集合X不是可数集且不是可数集且X不是有限集,则不是有限集,则称称X为为不可数集不可数集。(2)可数集与不可数集是对无穷集合而言的,有可数集与不可数集是对无穷集合而言的,有限集既不称作不可数集合也不称作可数集。限集既不称作不可数集合也不称作可数集。14现在学习的是第14页,共29页 定理定理4.1 区间区间0,1中的所有实数构成的集合是不中的所有实数构成的集合是不可数集。可数集。证证 区间区间0,1中每个实数,都可以写成十进
12、制无限中每个实数,都可以写成十进制无限位小数形式位小数形式0.a1a2a3a4.,其中每位,其中每位ai 0,1,2,.,9。约定每个有限位小数后均补以无限多约定每个有限位小数后均补以无限多0。假定定理不成立,于是假定定理不成立,于是0,1中全体实数可排成一中全体实数可排成一个无穷序列个无穷序列:a1,a2,a3,.,an,.。Cantor对角线法与不可数集对角线法与不可数集15现在学习的是第15页,共29页每个每个ai写成十进制无限小数形式排成下表写成十进制无限小数形式排成下表 a1=0.a11a12a13a14.a1n.a2=0.a21a22a23a24.a2n.a3=0.a31a32a3
13、3a34.a3n.an=0.an1an2an3an4.ann.其中其中aij 0,1,2,.,9构造一个新的小数构造一个新的小数 b=0.b1b2b3.bn.,显然,显然,b 0,1,但,但 n N,b an,矛盾。,矛盾。其中:若其中:若ann=5,则,则bn5;若若ann5,则,则bn=5,n=1,2,3,Cantor对角线法与不可数集对角线法与不可数集16现在学习的是第16页,共29页 这说明这说明0,1是不可数集,从而证明了并非一切无限集合是不可数集,从而证明了并非一切无限集合都是可数集,无限集合也是有区别的。都是可数集,无限集合也是有区别的。Cantor首次对无限集合从首次对无限集合
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 无穷 集合 基数
限制150内