第四章 有限集和无限集 有限集合 元素的个数称为该集合的基数； 满足包含排斥原理。 集合元素无限多，如：自然数集合N、整数集I、实数集R等。

Presentation on theme: "第四章 有限集和无限集 有限集合 元素的个数称为该集合的基数； 满足包含排斥原理。 集合元素无限多，如：自然数集合N、整数集I、实数集R等。"— Presentation transcript:

1 第四章 有限集和无限集 有限集合 元素的个数称为该集合的基数； 满足包含排斥原理。 集合元素无限多，如：自然数集合N、整数集I、实数集R等。
问题： 对于这样的集合有没有基数呢？ 如果有，基数是多少？ 它们之间有无大小的差别? 本章主要借助于函数讨论集合的所谓“大小”问题。这里用到自然数集合这个重要的概念讨论无限集。

2 4.1基本概念 定义4.1 一个集合S与集合Nn={0,1,2，…n-1}，如存在 一一对应函数 f : Nn→S，则称S是有限集合，并称其 有基数n，如果S不是有限集合，则称为无限集合。 说明： 由集合的元素个数来定义； 由于量变引起的质变； 它们中的一种性质都不能随意扩展到另一个集合中。

3 4.2无限集 定义4.2 集合A和集合B的元素间，如果存在一一 对应的关系，则说A和B是等势的，记作A~B
说明：对有限集来说，两集合等势即说明两个 集合的元素的个数相同。

4 Hilbert旅馆 问题：一旅店有无穷多个房间，各房间编号依次为： #1， #2， #3，……
现所有房间已住满了人。这时来了一位新客 人要求住店。怎么安排？ 解决方法： 店主人把#1房的客人移到#2房，把#2房的客人移到#3房， 依此类推，新客人就住进了已腾空的#1房间； 接着，又来了第二位新客人，旅店主也照此办理， 使第二位客人得到落实。

5 紧接着，来了一个有无限多个游客的旅游团要求定住房间，怎么办 ？
店主人把#1房的客人移到#2房，把#2房的客人移到#4房，#3房的客人移到#6房，等等，所有奇数号的房间全部腾空了，新的无限多个客人就全住进了旅店； 紧接着发生了更为严重的情况，来了无穷多个具有无穷多名游客的旅游团，怎么办？ 第一个旅游团客人按如下房间编号住 第二个旅游团客人住的房间编号为 接着是

6 这样不仅安排了无穷多个旅游团的住宿，而且还空出了很多房间！
无限多个房间可住无穷多个具有无穷多个游客的旅游团 对于一个无穷集合，向其中添加有限个元素，甚至“无穷多个”元素得到的新集合，其势不变 一个集合A，若真子集B ：B⊂A，B与A等势，则A一定是无限集

7 Hilbert旅馆的内涵 问题：自然数和平方数谁要更多。
如果把自然数集合中的元素数量记为z， 那么z不管加上多大的数，乘以多少，它始终是一个无穷，不会变大或变小。 问题：自然数和平方数谁要更多。 用普通人的眼光来看，前10个数字中不过4和9两个数， 前100个数中也不过10个； 再往后， 平方数在自然数中所占的比例越来越小； 但是从另一个角度看，每一个自然数都对应着一个平方数； 所以， 自然数和平方数是一样多的， 这 “一一对应” 的规则也就是判断集合是否一样大的标准。

8 任何一个有限集合不能与其真子集等势。 另一种有限集、无限集的定义方法； 定义：如果存在一一对应的f: S→S，使得f(S)⊂S，即f(S)是S的真子集，则S是无限集合，否则S是有限集合。

9 证明：设函数f: N→N，定义为f(x)=2x，显然f是一一对应，而且f(N)⊂N ，因此N是无限集。
定理4.2 常数集R是无限集。 证明：设函数f: R→R，为 显然f(x)是一一对应的，而且显然有f(R)⊂R，因此R是无限的。

10 例：证明下面集合间是等势的。 例1：证明 N={0,1,2,3,4,…...} 与下列集合等势 A={0,2,4,6,8,…...} B={1,3,5,7,9,…...} C={1,10,100,1000,10000,…..} ={100,10,102,103,104,,…...} 证： f:NA，f(x)=2x g:NB， g(x)=2x+1 h:NC， h(x)=10x 是双射， 故N与A，B，C，等势。 可见无限集合与其真子集等势。

11 对于无限集合，可用下面的例子说明 自然数集合N={0,1,2,...}与其子集 S={1,3,…}均为无限集，且N~S； 可得无限集的一个特性：S⊂N及S~N； 即表明S是N的一个真子集，并且同时S与 N等势； 这种特性在有限集是不可能存在的。

12 集合间的等势关系“~”是个等价关系 证明：令S是个集合族(即“所有集合构成的集合”)， 在S上的等势关系~，满足： ⑴自反性：因为任何集合A，存在双射 IA:AA,因此A~A ⑵对称性：任何集合A,B，若A~B，有双射 f:AB，又有双射f -1:BA，所以B~A。

13 ⑶传递性：任何集合A,B,C，若A~B，且B~C，
则有双射f:AB，和双射g:BC，由函数的复合得 双射： g◦f:AC，所以A~C。 所以~是等价关系。 按照等势关系“~”对集合族S，进行划分，得 到商集S/~，进而得到基数类的概念。

14 定理4.7 一个集合为无限集，则它必会有与它等势的真子集。 说明：
1.无限集的另一个定义； 2.该无限集减去这个真子集后得到的差集，可以是无限集，可以是有限集。 设M是一个无限集，现在需要证明： 必存在另一个无限集M’，M⊃ M’且M~ M’； 因为M不一定是可列集，因此才要这样证明，即M=一个可列集⋃另一个集合。

15 证明过程： 构造一个集合M，先从M中任取一个元素m1，这样剩余部分也是一个集合M-{m1}，并且是无限集；
再从此无限集M-{m1}中任取一个元素m2，剩余部分为M-{m1，m2}也是一个无限集； 如此继续，可取出m3,m4,m5,…无限多个元素，则可得到另一个集合M1={m1,m2,…}； 令M2=M-M1，即M中除去M1后得到的集合， 则M=M1∪ M2， 做另一集合M’={m2,m3,…} ∪M2，显然M⊃M’且M’~M，因此存在如下一一对应的关系： 对于M的每个mi对应mi+1，对于M中的每个m∈ M2，对应M’中的m。

16 推论：一集合为无限集的充分必要条件是它包含有与它等势的真子集。 证明：必要条件已经在前面证明，下面证明其充分条件。
反证法： 设一集合M含有与其等势的真子集M’，若M’为有限集，设其元素个数为n，即|M|=n，则此时必有n>m； 但此时M与M’间由于元素个数不同而无法建立一一对应的关系而产生矛盾。   鸽洞原理

17 定义4.5 一集合存在与其等势的真子集，则称为无限集，否则称为有限集。
有限集和无限集的重要定义 定义4.5 一集合存在与其等势的真子集，则称为无限集，否则称为有限集。 无限子集可做进一步划分：可列集和可数集。 定义4.6 与自然数集N等势的集合称为可列集。 能和自然数集合N建立一一对应关系的集合是可列集； 可排成一列，能一个一个数下来的集合。

18 定理4.8 无限集必包含可列集。 证明： 设一无限集A，由A中取出一个元素a0，再从其剩余部分取出一个元素a1，如此继续进行，可得一个序列： a0，a1，a2.。。。 由此可得一个无限集A’={a0,a1,a2,...} 集合A’为可列集

19 定理4.9 可列集的无限子集仍为一可列集。 证明：设有一可列集A={a0,a1,a2,...}，依次顺序取一个任意的无限集A’={am0,am1,am2,...}，A’与N一一对应； 故A’为可列集； 由此可知，可列集是无限集中最小的集合。

20 定理4.10 整数集I是可列集。 证明：整数集合Ｉ与Ｎ是等势的。 将集合Ｉ元素重排，写成 Ｎ＝｛0， 1， 2， 3， 4， 5，…｝
Ｎ＝｛0， 1，　2，　3，　4，　5，…｝ Ｉ＝｛0，＋1, －1，＋2, －2， +3 －3，…｝ 　f(i)＝ 是Ｉ到Ｎ的双射。 因此Ｉ是可列集。 1 2 3 -1 -2 -3

21 定理4.11 有理数集Q是可列集 证明：一切有理数均呈的形式，现将所有按下列次序排列， 正分数按其分子分母之和的大小顺序排列：从小到大
正分数的分子分母之和相同者按照分子大小顺序排列：从大到小 与正分数具有相同形式的负分数拍于正分数之后 按照上述规则可以得到一个序列 此序列可以跟自然数一一对应，因此是可列集。 问题：有重复数字。 直观上看，有理数比自然数多得多，但本质上它们却 “一样多”！

22 因为每个有理数都可以写成一个分数形式如下：
可以从0/1开始按照箭头指定次序排列Q中元素 (如果这个有理数在前面出现，就跳过去)， 所以Q是可数集。 另外 I×I~N如右图所示。 同理可证 N×N~N 0/1 1/1 2/1 3/1 --1/1 -2/1 -3/1 -1/2 -2/2 -3/2 0/2 1/2 2/2 3/2 0/3 1/3 2/3 3/3 -1/3 -2/3 -3/3 -1/4 -2/4 -3/4 0/4 1/4 2/4 3/4 ... 1 2 3 -1 -2 -3

23 之前出现过了

24 定理4.12 实数集R不是可列集。 思路：首先证明R~(0,1)， 然后证明(0,1)不是可列集。 证明： 构造函数f: (0,1)  R
f(x)=tg(πx-π/2) 显然 f是双射，所以R~(0,1). 1

25 实数轴上的(0,1)区间中的实数是不可数的。 证明：假设(0,1)是可数的，则可以将它的元素写成如下序列形式：{x1,x2,x3,...} ，其中 xi =0.ai1ai2ai3 …… i=1,2,3,….. 即 0＜ xi＜1 aik∈{0,1,2,3,4,5,6,7,8,9} k=1,2,3,4,… 令 x1 =0.a11a12a13a14…... x2 =0.a21a22a23a24…... x3 =0.a31a32a33a34…... ………... xn =0.an1an2an3an4…... ..……..

26 构造一个数b=0.b1b2b3b4…bn……， 其中 ： b1≠a b2 ≠ a b3≠a33… bn≠ ann... 于是 b≠x1, b≠ x2, b≠ x b ≠ xn … 因此： b(0,1) 但是b这样的形式应该是属于集合(0,1)的，因此产生矛盾，所以(0,1)是不可数的。

27 说明： 这种方法称为：康托对角线法； 对角线法并非康托尔关于实数不可数的第一个证明，而是发表在他第一个证明的三年后；
他的第一个证明既未用到十进制展开，也未用到任何其它数字系统； 自从该技巧第一次使用以来，在很大范围内的证明中都用到了类似的证明构造方法。

28 由前面这些定理可知： 因此： 实数集比可列集要大； 可列集的基数可表示为0 （Aleph 0，阿列夫零）；
实数集的基数用1或c表示，称作连续统的势。 因此： 无限集也有大小，最小的无限集是可列集，其次是实数集； 对于任何一个无限集，总存在一个基数大于这个集合的集合，比如这个集合的幂集； 可列集的幂集和实数集等势。

29 康拓的一些结论： 1.任何一个集合A，它的幂集ρ(A)的一定比A的基数大（已经证明）。 2. 0和1之间没有其他基数存在 （连续统假设continuum hypothesis ） 1874年格奥尔格·康托尔猜测； 又被称为希尔伯特第一问题，在1900年第二届国际数学家大会上，大卫·希尔伯特把康托尔的连续统假设列入20世纪有待解决的23个重要数学问题之首； 1938年哥德尔证明了连续统假设和世界公认的ZFC公理系统（带有选择公理的集合论之公理系统）不矛盾； 1963年美国数学家科亨证明连续假设和ZFC公理系统是彼此独立的； 连续统假设不能在ZFC公理系统内证明其正确性与否。

30 判定连续统假设对数学的重大意义 数学基础中最主要的问题就是如何处理自然数和实数的关系，即如何用离散的方法来构造连续统；
自从古希腊人发现这个难题以来，至今它仍未得到完全解决，到目前为止，我们对连续统还所知甚少； 数学归纳法是数学的基本方法，它是建立在自然数基础上的，对连续统假设的否定性证明正好说明：人们可以用这种方法去无限逼近连续统，但却永远也不能达到其尽头。

31 有限和无限的区别及联系 区别： 无限集中，部分可以等于全体（无限的本质）； 有限情况下，部分小于全体；
　　有限情况下，部分小于全体； 无限集中，有限时成立的许多命题不再成立。如加法的结合律。 联系： 数学归纳法 通过有限证明无限； 极限，通过有限描述无限 ； 无限可由有限构成，无限多个有限无限；有限也由无限构成：有限的长度由无限个点组成。

32 集合基数的判别定理： 无限集减去一个有限子集，或添上有限个元素，基数不变； 有限个或可列个可列集的并集可列；
可列个有限集的并集至多可列； 无限集并一个可列集，基数不变； 不可列无限集，减去一个可列子集，基数不变； 有限个或可列个基数为的集合的并，基数为。

33 补充内容： 基数的比较 前边基数相等与否的问题，下面讨论诸如和0哪个大的问题，即所谓无限集合的“次序”问题。
在比较两个集合基数相等时，要看这两个集合之间是否存在双射， 但是找双射往往是个麻烦的事, 为了解决这个问题，提出下面定理：

34 定理. 1 如果集合A到B存在内射函数，则K[A]≤K[B]。 K[A]表示A的基数。 定理
定理.1 如果集合A到B存在内射函数，则K[A]≤K[B]。 K[A]表示A的基数。 定理.2 (Zermelo定理) A和B是任何集合，则以下三条之一必有一个成立： a.) K[A]<K[B]. b.) K[B]<K[A] c.) K[A]=K[B]. 定理.3 (Contor- Schroder- Bernstein定理) A和B是任何集合， 如果 K[A]≤K[B] 且 K[B]≤K[A] 则K[A]=K[B]。 定理.4 设A是有限集合，则K[A]< 0 <  定理.5 设A是无限集合，则0≤ K[A] 可数集合是“最小的”无限集合

35 可以用这些定理对集合基数进行比较。 例. 证明[0,1]与(0,1)等势。 证明：构造两个内射函数: f:(0,1)[0,1] f(x)=x g:[0,1](0,1) g(x)=x/2+ 1/4 因为f和g都是单射的，所以有： K[(0,1)]≤K[[0,1]] 且 K[[0,1]]≤K[(0,1)] 根据定理3，可得 K[[0,1]]=K[(0,1)]