基数及其比较讲解.ppt

§3 基数及其比较 在抽象地研究集合时，最根本的是考虑集合的“大 小”，而集合中元素的性质是可以不加考虑的 对给定的集合Ａ和Ｂ，它们的“大小”是否相同？哪 一个集合元素“较多”？ 对于有限集合来说，集合的“大小”就是集合中元素 的个数，称为集合的基数 基数越大的集合所含元素的个数越多，也就是说这 个集合越大 但对于无穷集合来说，元素的“个数”这个概念是 没有意义的因为按通常的理解它是指一个有限数， 而不是无限数 至于一个无限数比另一个无限数大，更是不可思 意的了 但凭着我们的直觉与前面的定理可知，这种说法 是符合我们的看法的，只不过是现在说不清楚，之所 以说不清楚，是因为这里面有几个概念未加定义 于是，我们下面就要把有限集合个数的概念推广 ，使它对无穷集合也有精确的定义，这就是无穷集合 基数的概念；然后确定比较两个集合基数大小的方法 3.1基数的本质 由于我们已经定义了有限集合的基数的概念，即 集合中所含元素的个数，现在便从此进行分析和推广 有限集合的基数是一个具体的数，可是这个数又 是什么呢？实际上，数只是一个抽象的概念，给一个 具体的数只不过是对这个概念的一种符号表示 例如：对于“5”这个数。

世界上有“5”这个事物吗？没有 有的只是具体的5个事物，如5个人，5只笔，5张 桌子等等，而这个“5”无非就是一个符号，它表明具 有5个事物所形成的集合的共性 它们的共性就是它们相互对等，即它们的元素之 间可以建立起一一对应 于是， “5”这个符号就是赋给每个含有五个元 素的集合的一个记号，即若与含有五个元素的集对等 ，则都赋以相同的记号“5” 实际上，这就是“5”的本质 3.2 无穷集合的基数 定义1 集合Ａ的基数是一个符号，凡与集合Ａ对等的 每个集，对应着同一个符号 定义2(等价定义) 所有与集合Ａ对等的集形成的集族 （的共性）称为集合Ａ的基数，记为|A| 说明: (1) 现在已经把有限集合元素个数的概念推广到无穷 集合上了，于是，无穷集合元素个数的概念也有了明 确的定义，这就是基数的概念 (2) 这两个定义实质上等价的从定义1可知，凡与Ａ 对等的各个集合基数也都是|A|，于是有: 定义3 集合Ａ与集合Ｂ的基数相等Ａ～Ｂ 3.3无穷集合基数的比较 例：教室里人多还是椅子多？ 定义1 设A、B为任意两个集合，则 (1) 若存在从Ａ到Ｂ的单射，则称Ａ的基数小于或等于 Ｂ的基数，记为|A|≤|B|； (2) 若存在从Ａ到Ｂ的单射，但不存在一一对应，则称 Ａ的基数小于Ｂ的基数，记为|A||B|, |A||B|,三者中恰有一个成立。

定理3 (Bernstein) 设A,B是任意两个集合，若 |A|≤|B|且|B|≤|A|，则|A|=|B| 说明：(1) 这个定理提供了证明两个基数相等的有效 方法，而且也比较简单 若能构造一个单射f:A→B，用来证明|A|≤|B|， 再构造另一个单射g:B→A，用来证明|B|≤|A|，则由 定理可知|A|=|B| (2)在这里，f与g不必是满射，更不一定是一一对应 于是，定理3等价于“若存在从Ａ到Ｂ和从Ｂ到Ａ的单 射，则存在从Ａ到Ｂ的双射” (3)构造这样的两个单射是比构造双射要容易得多 例1 证明: |(0,1)|=|[0,1]| (4) 若用a表示可数集合的基数，用c表示连续统的基数 ，则有限集A，可数集和连续集基数之间有如下关系： 设A是任意的有限集合，则|A|ac 例2 证明: |A|ac 3.4最大集合是否存在？ 前面讨论了无穷集合中最小集合—可数集，然后又 讨论了连续统集的存在并且ac现在要问： 1.是否存在最大的集合？ 2.是否有比c还大的集合？ 3.是否存在一个基数b，使得abc 定理4(Cantor)设A是任意一个集合，则|A||2A| 说明： (1) Cantor定理告诉我们：对任意的集合A，总存在 比基数|A|更大的集合,也就是说:不存在最大的集合 。

例：构造可数个无穷基数的集合：N,2N,22N…且 |N||2N||22N|… 其中左面的不等式表示 |N|=a2N，以后每一个都大于前面的一个，因此，没 有最大集合 (2)当Ａ为可数集时，|2A|～ |2N|=c (3)确实有比c还大的基数因为|N|=a2a22a…，把 大于c的这样的集合都称为无穷不可数集合而不去研 究它 (4) 这个定理说明：自然数Ｎ有多少个子集？就是 [0,1]上有多少个实数，也就是实数一共有多少个，或 者直线上一共有多少个实数，或平面上有多少个实数 3.5连续统假设 由于ac，a是“最小”无穷集合－可数集合的基数 ，现在要问： 问题：在a和c之间有没有其它的基数呢？ 有没有这样的基数b，使得abc？换句话说就是： 是否存一个集合S，S不是可数集，但Ｓ有一个可数 真子集，并且Ｓ不与[0,1]对等却能与[0,1]的一个不 可数真子集对等？ 连续统假设: 集合论的创始人康托在一百多年前就认为 没有这样的无穷集合这就是著名的康托的“连续统假 设” 对于这个问题，数学家们做了多年的努力，企图证 明连续统假设成立，或证明它不成立现在，这个问题 已解决到这样的程度： 1938年哥德尔（1906-1978）证明了连续统假设与 集合论的公理是无矛盾的，即承认连续统假设，绝不会 引出矛盾。

就是说，在集合论的公理下，根本不会证明 连续统假设是错的 但这并不等于证明了它是正确的 1963年柯亨（1934-）证明了连续统假设对集合论 中的常用公理是独立的这又表明，从集合论的常用 公理出发，根本不可能证明连续统假设是正确的因 此，1966年柯亨获得菲尔兹奖于是，a与ｃ间是否有 基数存在的问题，回答是： 不知道 不过，大多数数学家承认这个假设，即认为a与ｃ 之间没有其它基数 无限数有无穷多个，没有最大的这些工作都归 功于集合论的创始人康托在康托之前，不同的无穷 集合所含的元素的个数多少没有明确区别，均含有无 穷多个现在就能区分它们之间哪一个含有更多或是 否含有同样多的元素 §5 集合的悖论 5.1什么是悖论 “这句话是错的”―就是一个悖论 上面所介绍的内容是属于Cantor开创的朴素集合论 早在上世纪末已有一些数学家反对Cantor集合论中 所研究的无穷集，怀疑其中的推理过程，但是又找不 出什么毛病1895年Contor本人也已经觉察到了这一 点，他和其它的一些数学家一起举出了不少例子说明 朴素集合论将导致矛盾,这种矛盾被称为悖论 所谓悖论是指一个命题Ｐ，若Ｐ为真可推出Ｐ为假 ，又从Ｐ为假推出Ｐ为真，则说命题Ｐ是一个悖论;显 然，若从命题Ｑ引出一个命题Ｐ，而Ｐ是一个悖论,则 Ｑ也是一个悖论。

下面介绍最有名的两个悖论，即罗素悖论和Cantor 悖论 Russell(1872-1970)是英国哲学家和数学家，于 1901年提出有名的Russell悖论在未给出Russell 悖论之前，先介绍两个通俗两有趣的悖论：说谎悖 论和理发师悖论 虽然它们和集合论没有明显的联系，但能够帮助 我们理解罗素悖论 例1 说谎悖论是古代的一个通俗的悖论，有一个人在 断言“我正在说谎”要问，这个人是在说谎还是在 讲真话？ 若他在说谎，这表明他的断言“我正在说谎”是谎 话，也就是说他在讲真话，所以我们得出这样一个结 论，若他是说谎，那么他是讲真话（即没有说谎） 另一方面，若他讲真话，这表明他的断言“我正在 说谎”是真话，也就是说他在说谎，所以我们又得出 结论：若他是讲真话，那么他在说谎（即没有讲真话 ） 通过以上分析使我们看到，以命题出现的断言“我 正在说谎”就是一个悖论，我们无法断言它的真假 例2 理发师悖论是Russell在1918年给出的，一个乡村 理发师公开宣布他不给村子中所有自己替自己理发的 人理发，但却给所有自己不替自己理发的人理发 一天他发生了疑问，他是否应当给自己理发 如果他自己替自己理发，那么按他声言的前半部分 ，他就不应当给自己理发； 如果他的头由另外的人给他理，那么按照他的规定 ，他又必须给自己理发。

理发师的头应由谁来理呢？这个理发师陷入了逻辑 的窘境 Russell悖论是相当简单的,一点也用不到集合论的专 门知识 例3 Russell仔细地分析了Contor给集合下定义： “把一些确定的，可以区别的事物——可以是直观的对象， 也可以是思维的对象——放在一起，组成一个整体，称为集” ，他发现集合可以分成两种: 第一种是集合Ａ本身不是Ａ的一个元素，即AA； 第二种是集合Ａ本身是Ａ的一个元素，即A∈A 于是，可以看出：对任意的一个集A，不是第一种 就是第二种，两种集彼此可以明确识别，所以由 Cantor的定义，令 S={A|AA}, 也就是说Ｓ是由满足条件“AA”的那些Ａ组成的 一个新的集合，现在我们要问： 集S是第一种集还是第二种集？即AA ，还是A∈A 若S是第一种集，即SS； 因为Ｓ是由所有满足条件的AA组成的，而SS ，知S当然就在S中，也就是说S∈S而S∈S，表明 S是第二种集，从而产生矛盾 若Ｓ是第二种集，即S∈S；因为对S中任一元素A，都 有AA，而S∈S，知S是S中的元素，也就是SS 而SS，表明Ｓ是第一种集，从面产生矛盾 这样，Ｓ既不是第一种集也不是第二种集，即Ｓ 既不是SS，也不是S∈S。

这个矛盾就是Russell所发现的“集合论是自相 矛盾的”，即 著名的Russell悖论 例4 Cantor最大基数悖论 Cantor在1899年给出的悖论，现叙述如下： 集合是具有某些性质的元素组成，因此也可以假设 集合Ｓ是由所有集合所组成的集合现在要问： S与2S的基数哪一个基数更大 这个悖论称为Contor最大基数悖论 一方面，由Cantor定理可知，|S||2S| 但另一方面，因为S是所有集合所组成的集合，而 2S中每个元素都是S的一个子集，从而2S是集合，所以 2S⊆S，即|2S||S|于是产生了矛盾 但是，Cantor的最大基数悖论并未引起人们多大的 注意，因为它涉及的概念较多： 集，子集，基数，基数之间的大小比较等 人们认为可能是由于某些中间环节技术处理得不 恰当所引起的当时Cantor想对集合加以区分，借以 排除他的悖论，但他的悖论尚未排除， Russell悖论 又出现了，而Russell悖论是从集合论的基本概念着手 的，它是那样的那初等，那样清晰明白不容辩驳，人 们不得不承认，集合论自相矛盾 5.2悖论的所在 现在我们要问问题的毛病出在哪里呢？ 由Russell悖论可以得出，问题就出在Cantor对 集合概念的定义上。

这个定义蕴含着矛盾，蕴含着 循环定义 集合是由元素组成的，在集合还未形成时怎能以 一个实体出现充当自己元素呢？这不正是含有循环 定义吗？ 因此，在对集合概念描述时，曾强调不能说 “所有集合的集合” 这样一类话的原因 5.3解决方法 为了解决集合论的悖论，为了解决集合论中自身 的问题，一些著名数学家在本世纪初开始了集合论公 理化方面的研究，产生了各种不同的学派和各种不同 的公理系统，解决了悖论问题，大大推进了集合论的 发展，有关集合论公理化方面的内容，本书作为自学 介绍，有兴趣读者请参看有关文献 本书是以朴素的观点来介绍集合论的，因此未给 出公理系统，但对于计算机科学的一般问题以及大多 数数学问题及其应用，这已足够了 总 结 可数集合、连续统、无穷集合 基数、基数的比较 对角线法的应用 定理 { [0,1]不可数 ；|A||2A|} 第四章 无穷集合及其基数习题1 1.设A为由序列a1,a2,…,an,…的所有项组成的集合， 则A是否是可数的？为什么？ 2.证明：直线上互不相交的开区间的全体所构成的集 合至多可数 3.证明：单调函数的不连续点的集合至多可数 4.任一可数集A的所有有限子集构成的集族是可数集合 。

5.判断下列命题之真伪： (1)若f:XY且f是满射，则只要X。