无穷集合及基数

关于无穷集合及基数12第4节无穷集合及其基数可数集不可数集基数及其比较康托-伯恩斯坦定理悖论与公理化集合论主要内容：第2页,共29页，2024年2月25日，星期天3

集合的基数亦称作集合的势。粗略的说，就是一个集合的“规模”，它的“大小”，或者更确切地说，它有多少个元素。通俗的说，集合的势是量度集合所含元素多少的量。集合的势越大，所含的元素越多。很明显，如果集合中只有有限个元素，我们只要数一数它有多少个可以了，这时集合的基数就是其中所含元素的个数。什么是集合的基数？

值得注意的是无限集，它所含的元素有无穷多个，这时怎样去数？为了解决这个问题，我们首先从伽利略“悖论”说起。

第3页,共29页，2024年2月25日，星期天41638年意大利的天文学家伽利略发现了下面的问题：

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页,共29页，2024年2月25日，星期天5

但另一方面，对于N+中的每个元素都可以在N(2)中找到一个元素与之对应，这样看来，N(2)中的元素不比N+中的元素要少。那么到底N+与N(2)中所含元素的个数是否一样呢？如果是，那么就有

部分=整体？然而按照传统，部分怎么能等于全体呢？这就是伽利略“悖论”，它不仅困惑了伽利略，还使许多数学家亦束手无策。伽利略“悖论”第5页,共29页，2024年2月25日，星期天61874年，Cantor注意到伽利略”悖论”。在1874年到1897年间完全解决了这个问题。

Cantor详细地分析了断定有限集合的元素多少的方法，即采用数数的方法。他认为“数数的过程”就是作“一一对应的过程”。

Cantor认为这种“一一对应”的方法不仅适用于有限集，也适用于无限集。他牢牢地抓住这个原则，抛弃了部分必定小于全体的教条，经历了大约23年之后，他才冲破了传统观念的束缚，革命性的解决了伽利略“悖论”。

Cantor认为在N+与N(2)之间存在着一一对应(即双射)，因此N+与N(2)的元素个数是相等的。一一对应与可数集第6页,共29页，2024年2月25日，星期天7

定义4.1

设A，B是集合，若存在着从A到B的双射，就称A和B等势(或对等)，记作A≈B。

Cantor把自然数集N+称为可数集(或可列集)，这是因为它的元素可以一个一个的数出来。凡是与自然数集N+等势的集合，它们的元素通过一一对应关系，也都可以一个一个的数出来，因此：一一对应与可数集

定义4.2

凡是与自然数集N+等势的集合，称为可数集(或可列集)。

第7页,共29页，2024年2月25日，星期天8

显然，N也是可数的。

Cantor以此为出发点，对无限集合进行考察，他发现下面的集合都是可数集：(1)ODD={x|x

N，x是奇数}≈N

F：N

ODDF(n)=2n+1（F：N+

ODDF(n)=2n-1）(2)EVEN={x|x

N，x是偶数}≈NF：N

EVENF(n)=2n（F：N+

EVENF(n)=2(n-1)）

(3)N(n)={x|x=mn，m，n

N}≈NF：N

N(n)F(m)=mn一一对应与可数集第8页,共29页，2024年2月25日，星期天9(4)N×N≈N一一对应与可数集第9页,共29页，2024年2月25日，星期天10(6)Z×Z≈N

F:Z

NF(n)=2n(n≥0)F(n)=2|n|-1(n<0)

(5)Z≈N一一对应与可数集第10页,共29页，2024年2月25日，星期天11Cantor在解决了Z×Z≈N后，用类似的思想解决了Zn≈N。在这种想法之下，Cantor得到了一个令人惊异的发现：Q≈N。并且利用他独创的“折线法”，巧妙的建立了Q与N的一一对应。为建立N到Q的双射函数，先把所有形式为p/q(p，q为整数且q>0)的数排成一张表。显然所有的有理数都在这张表内。一一对应与可数集第11页,共29页，2024年2月25日，星期天12一一对应与可数集第12页,共29页，2024年2月25日，星期天13

注意：以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。

一一对应与可数集第13页,共29页，2024年2月25日，星期天14

正是由于这一发现，使得他甚至猜想R也是可数集，并且着手去证明它。他没有得到预期的结果，却又作出了更伟大的发现。

Cantor利用它著名的对角线法，证明了[0,1]是不可数集，在这个基础上证明了R也是不可数的，甚至于Rn也是不可数的。Cantor对角线法与不可数集

注：(1)如果集合X不是可数集且X不是有限集，则称X为不可数集。(2)可数集与不可数集是对无穷集合而言的，有限集既不称作不可数集合也不称作可数集。第14页,共29页，2024年2月25日，星期天15

定理4.1

区间[0,1]中的所有实数构成的集合是不可数集。

证区间[0,1]中每个实数，都可以写成十进制无限位小数形式0.a1a2a3a4...，其中每位ai{0,1,2,...,9}。

约定每个有限位小数后均补以无限多0。

假定定理不成立，于是[0,1]中全体实数可排成一个无穷序列:a1,a2,a3,...,an,...。Cantor对角线法与不可数集第15页,共29页，2024年2月25日，星期天16每个ai写成十进制无限小数形式排成下表a1=0.a11a12a13a14...a1n...a2=0.a21a22a23a24...a2n...a3=0.a31a32a33a34...a3n..........................an=0.an1an2an3an4...ann..........................其中aij{0,1,2,...,9}构造一个新的小数b=0.b1b2b3...bn...，显然，b[0,1]，但nN，ban，矛盾。其中：若ann=5，则bn≠5；若ann≠5，则bn=5，n=1,2,3,…Cantor对角线法与不可数集第16页,共29页，2024年2月25日，星期天17

这说明[0,1]是不可数集，从而证明了并非一切无限集合都是可数集，无限集合也是有区别的。

Cantor首次对无限集合从“定量”方面进行了深入研究，使人们深刻认识到集合N与R有本质不同。

Cantor用对角线元素来构造小数x*的方法称为Cantor对角线法。

Cantor所创造的这一方法是一个强有力的证明方法，在函数论和计算机科学中有许多应用。在计算的复杂性理论和不可判定问题中，对角线法也是为数不多的几个重要方法之一。Cantor对角线法与不可数集第17页,共29页，2024年2月25日，星期天18

性质1

集合A为可数集的充分必要条件是A的全部元素可以排成无重复项的序列a1,a2,...,an,...性质2无限集A必包含可数子集。性质3

可数集的任一无限子集也是可数集。

性质4

从可数集A中除去一个有限集M，则A\M仍是可数集，即A≈A\M。无限集合的性质

性质5

设M是一个无穷不可数集，A为M的至多可数子集(即A有穷或可数)，则M≈M\A。

定义4.3

凡能与自身的一个真子集对等的集合称为无穷集合，或无限集合。第18页,共29页，2024年2月25日，星期天19

如果要对任意的集合谈论它们中元素的“个数”，这就需要把有限集合里元素“个数”的概念推广到无限集合中，要求下一个定义对任何集合都适用。集合的基数或集合的势是集合论中基本概念之一，在朴素集合论体系中讨论基数的概念，只能从几条规定或公理出发。集合的基数

设A为任意一个集合，现在规定用cardA表示A中的元素“个数”，并称cardA为集合A的基数，并再作以下五条规定：第19页,共29页，2024年2月25日，星期天20(3)对于自然数集合N，规定cardN=א0

(读作阿列夫零)。(4)对于实数集合R，规定cardR=א

(读作阿列夫)。(5)将0，1，2，…，א0，א，…都称作基数，其中0，1，2，…称作有穷基数，而א0，א…称作无穷基数。

(1)对于任意的集合A和B，规定

cardA=cardB当且仅当A≈B。

(2)对于任意的有限集合A，规定与A等势的自然数n为A的基数，记作cardA=n。集合的基数第20页,共29页，2024年2月25日，星期天21

定义4.4

集合A的基数是一个符号，凡与A等势的集合都赋以同一个记号，集合A的基数记为|A|，也记作cardA。定义4.4’

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

定义4.4’’

集合的基数是集合的这样一种特性，当把集合里元素固有特点抽出，以及把各元素在集合中的次序不顾之后，仍然保留下来的特性，就叫做基数。

集合的基数第21页,共29页，2024年2月25日，星期天22Cantor连续统猜想Cantor猜想(连续统猜想，CH)：在א0与א之间是否还有别的基数？

定义4.5

凡与集[0,1]对等的集称为具有“连续统的势”的集，或简称连续统。实数集R、无理数之集都是连续统。1938年，K.哥德尔证明了CH对ZFC公理系统（见公理集合论)是协调的。

1963年，P.J.科恩证明CH对ZFC公理系统是独立的。这样，在ZFC公理系统中，CH是不可能判定真假的。这是20世纪60年代集合论的最大进展之一。第22页,共29页，2024年2月25日，星期天23

定义4.6

集合A的基数与集合B的基数称为是相等的，当且仅当A≈B。

定义4.7

，是任意两个基数，A，B是分别以，为其基数的集。如果A与B的一个真子集对等，但A却不能与B对等，则称基数小于基数，记为

<。

规定≤当且仅当<或=。

规定>当且仅当<。

规定≥当且仅当>或=。基数及其比较第23页,共29页，2024年2月25日，星期天24规定≤当且仅当存在单射f:AB。

规定<

当且仅当存在单射f:AB，且不存在A到B的双射。

无穷集合的基数也称超穷数，超穷数也可以比较大小。于是，像下面这些句子是有意义的：“平面上的点多还是平面上的圆多？”，“集合[0,1]中的数比自然数集N中的数多”，“有理数和自然数一样多。”基数及其比较问题：无穷基数有多少？有没有最大的无穷基数？定理4.2(康托)对任一集合M，M<2M

。第24页,共29页，2024年2月25日，星期天25康托-伯恩斯坦定理

在有限数大小的比较中，对任取两个有限数（非负整数）m，n，下面三式有且仅有一式成立:m>n，m=n，m<n。

那么，对任两个无限数，，下面三个式子是否也有且仅有一个成立呢?

<，=，>。

答案是肯定的。第25页,共29页，2024年2月25日，星期天26

设Ａ是一个基数为的集合，Ｂ是基数为的集合。

如果

=，那么<，<都不能成立。

若

<，<同时成立，则从A到B的每个单射都不是满射，而从B到A的每个单射都不是满射。

我们能证明这是不可能的，从而

<与<不能同时成立。