离散数学无穷集合及基数

《离散数学无穷集合及基数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5节无穷集合及其基数什么是无穷集合?无穷集合之间能否比较大小?无穷集合有什么特殊性质?本部分内容主要是利用映射，尤其是利用双射为工具，建立可数集、不可数集，并研究它们的一些性质，从而得到无穷(限)集合的特征性质。然后将有穷集合元素的个数的概念推广到无穷集合，建立无穷集合的基数的概念。引言1第4节无穷集合及其基数可数集不可数集基数及其比较康托-伯恩斯坦定理悖论与公理化集合论主要内容：2集合的基数亦称作集合的势。粗略的说，就是一个集合的“规模”，它的“大小”，或者更确切地说，它有多少个元素。通俗的说，集合的势是量度集合所含元素多少的量。集合的势越大，所含的元素越多。

2、很明显，如果集合中只有有限个元素，我们只要数一数它有多少个可以了，这时集合的基数就是其中所含元素的个数。什么是集合的基数？值得注意的是无限集，它所含的元素有无穷多个，这时怎样去数？为了解决这个问题，我们首先从伽利略“悖论”说起。31638年意大利的天文学家伽利略发现了下面的问题：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)中的元素

3、要多。4但另一方面，对于N+中的每个元素都可以在N(2)中找到一个元素与之对应，这样看来，N(2)中的元素不比N+中的元素要少。那么到底N+与N(2)中所含元素的个数是否一样呢？如果是，那么就有部分=整体？然而按照传统，部分怎么能等于全体呢？这就是伽利略“悖论”，它不仅困惑了伽利略，还使许多数学家亦束手无策。伽利略“悖论”51874年，Cantor注意到伽利略”悖论”。在1874年到1897年间完全解决了这个问题。Cantor详细地分析了断定有限集合的元素多少的方法，即采用数数的方法。他认为“数数的过程”就是作“一一对应的过程”。Cantor认为这种“一一对应”的

4、方法不仅适用于有限集，也适用于无限集。他牢牢地抓住这个原则，抛弃了部分必定小于全体的教条，经历了大约23年之后，他才冲破了传统观念的束缚，革命性的解决了伽利略“悖论”。Cantor认为在N+与N(2)之间存在着一一对应(即双射)，因此N+与N(2)的元素个数是相等的。一一对应与可数集6定义4.1设A，B是集合，若存在着从A到B的双射，就称A和B等势(或对等)，记作A≈B。Cantor把自然数集N+称为可数集(或可列集)，这是因为它的元素可以一个一个的数出来。凡是与自然数集N+等势的集合，它们的元素通过一一对应关系，也都可以一个一个的数出来，因此：一一对应与可数集定

5、义4.2凡是与自然数集N+等势的集合，称为可数集(或可列集)。7显然，N也是可数的。Cantor以此为出发点，对无限集合进行考察，他发现下面的集合都是可数集：(1)ODD={x

6、xN，x是奇数}≈NF：NODDF(n)=2n+1（F：N+ODDF(n)=2n-1）(2)EVEN={x

7、xN，x是偶数}≈NF：NEVENF(n)=2n（F：N+EVENF(n)=2(n-1)）(3)N(n)={x

8、x=mn，m，nN}≈NF：NN(n)F(m)=mn一一对应与可数集8(4)N×N≈N一一对应与可数集9(6)Z×Z≈NF:ZNF(n)=2n(n≥0)F

9、(n)=2

10、n

11、-1(n<0)(5)Z≈N一一对应与可数集10Cantor在解决了Z×Z≈N后，用类似的思想解决了Zn≈N。在这种想法之下，Cantor得到了一个令人惊异的发现：Q≈N。并且利用他独创的“折线法”，巧妙的建立了Q与N的一一对应。为建立N到Q的双射函数，先把所有形式为p/q(p，q为整数且q>0)的数排成一张表。显然所有的有理数都在这张表内。一一对应与可数集11一一对应与可数集12注意：以0/1作为第一个数，按照箭头规定的顺序可以“数遍”表中所有的数。但是这个计数过程并没有建立N到Q的双射，因为同一个有理数可能被多次数到。例如1/1，2/2，3/3，

12、…都是有理数1。为此我们规定，在计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。如1/1被计数，那么2/2，3/3，…都要被跳过。表中数p/q上方的方括号内标明了这个有理数所对应的计数。这样就可以定义双射函数f：N→Q，其中f(n)是[n]下方的有理数。从而证明了N≈Q。一一对应与可数集13正是由于这一发现，使得他甚至猜想R也是可数集，并且着手去证明它。他没有得到预期的结果，却又作出了更伟大的发现。Cantor利用它著名的对角线法，证明了[0,1]是不可数集，在这个基础上证明了R也是不可数的，甚至于Rn也是不可数的。Cantor对角线法与不可数集注：(1

13、)如果集合