离散数学无穷集合及基数.ppt

第5节无穷集合及其基数第4节无穷集合及其基数集合的基数亦称作集合的势。
粗略的说，就是一个集合的“规模”，它的“大
小”，或者更确切地说，它有多少个元素。
通俗的说，集合的势是量度集合所含元素多少的
量。集合的势越大，所含的元素越多。
很明显，如果集合中只有有限个元素，我们只要
数一数它有多少个可以了，这时集合的基数就是其中
所含元素的个数。1638年意大利的天文学家伽利略发现了下面
的问题：
N+={1,2,3,…,n,…}与N(2)={1,4,9,…,n2,…}
这两个集合，哪一个的元素更多一些？但另一方面，对于N+中的每个元素都可以在N(2)中找到一个元素与之对应，这样看来，N(2)中的元素不比N+中的元素要少。

那么到底N+与N(2)中所含元素的个数是否一样呢？如果是，那么就有
部分=整体？
然而按照传统，部分怎么能等于全体呢？这就是伽利略“悖论”，它不仅困惑了伽利略，还使许多数学家亦束手无策。1874年，Cantor注意到伽利略”悖论”。
在1874年到1897年间完全解决了这个问题。
Cantor详细地分析了断定有限集合的元素多少的方法，即采用数数的方法。他认为“数数的过程”就是作“一一对应的过程”。
Cantor认为这种“一一对应”的方法不仅适用于有限集，也适用于无限集。
他牢牢地抓住这个原则，抛弃了部分必定小于全体的教条，经历了大约23年之后，他才冲破了传统观念的束缚，革命性的解决了伽利略“悖论”。
Cantor认为在N+与N(2)之间存在着一一对应(即双射)，因此N+与N(2)的元素个数是相等的。定义4.1设A，B是集合，若存在着从A到B的双射，就称A和B等势(或对等)，记作A≈B。显然，N也是可数的。
Cantor以此为出发点，对无限集合进行考察，他发现下面的集合都是可数集：(4)N×N≈N(6)Z×Z≈NCantor在解决了Z×Z≈N后，用类似的思想解
决了Zn≈N。

在这种想法之下，Cantor得到了一个令人惊异
的发现：Q≈N。

并且利用他独创的“折线法”，巧妙的建立了Q与
N的一一对应。

为建立N到Q的双射函数，先把所有形式为p/q
(p，q为整数且q>0)的数排成一张表。显然所有的有
理数都在这张表内。一一对应与可数集注意：以0/1作为第一个数，按照箭头规定
的顺序可以“数遍”表中所有的数。但是这个计数
过程并没有建立N到Q的双射，因为同一个有理数
可能被多次数到。例如1/1，2/2，3/3，…都是有理
数1。
为此我们规定，在计数过程中必须跳过第二
次以及以后各次所遇到的同一个有理数。如1/1被
计数，那么2/2，3/3，…都要被跳过。表中数p/q上
方的方括号内标明了这个有理数所对应的计数。
这样就可以定义双射函数f：N→Q，其中f(n)
是[n]下方的有理数。从而证明了N≈Q。正是由于这一发现，使得他甚至猜想R也是可数
集，并且着手去证明它。他没有得到预期的结果，
却又作出了更伟大的发现。
Cantor利用它著名的对角线法，证明了[0,1]是不
可数集，在这个基础上证明了R也是不可数的，甚至
于Rn也是不可数的。定理4.1区间[0,1]中的所有实数构成的集合是不
可数集。每个ai写成十进制无限小数形式排成下表这说明[0,1]是不可数集，从而证明了并非一切无限集合都是可数集，无限集合也是有区别的。
Cantor首次对无限集合从“定量”方面进行了深入研究，使人们深刻认识到集合N与R有本质不同。
Cantor用对角线元素来构造小数x*的方法称为Cantor对角线法。
Cantor所创造的这一方法是一个强有力的证明方法，在函数论和计算机科学中有许多应用。在计算的复杂性理论和不可判定问题中，对角线法也是为数不多的几个重要方法之一。性质1集合A为可数集的充分必要条件是A的全
部元素可以排成无重复项的序列如果要对任意的集合谈论它们中元素的“个数”，这就需要把有限集合里元素“个数”的概念推广到无限集合中，要求下一个定义对任何集合都适用。

集合的基数或集合的势是集合论中基本概念之一，在朴素集合论体系中讨论基数的概念，只能从几条规定或公理出发。(3)对于自然数集合N，规定cardN=א0
(读作阿列夫零)。定义4.4集合A的基数是一个符号，凡与A等势的集合都赋以同一个记号，集合A的基数记为|A|，也记作cardA。

定义4.4’所谓集合的基数是指所有与该集合等势的集合所构成的集族的共同性质。(冯诺伊曼)

定义4.4’’集合的基数是集合的这样一种特性，当把集合里元素固有特点抽出，以及把各元素在集合中的次序不顾之后，仍然保留下来的特性，就叫做基数。Cantor连续统猜想定义4.6集合A的基数与集合B的基数称为是相
等的，当且仅当A≈B。规定≤当且仅当存在单射f:AB。康托-伯恩斯坦定理设Ａ是一个