有限集和无限集 有限集合 无限集合 问题： 本章主要借助于函数讨论集合的所谓“大小”问题。这里 用到自然数集合这个重要的概念讨论无限集。

Presentation on theme: "有限集和无限集 有限集合 无限集合 问题： 本章主要借助于函数讨论集合的所谓“大小”问题。这里 用到自然数集合这个重要的概念讨论无限集。"— Presentation transcript:

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

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

3 基本概念 定义4.2 集合A和集合B的元素间，如果存在一一对 应的关系，则说A和B是等势（Cardinality）的，记 作A~B 说明：
对有限集来说，两集合等势即说明两个集合的元素的 个数相同； 集合的势：Cardinality of Sets

4 Hilbert旅馆 问题： #1， #2， #3，…… 客 满 一旅店有无穷多个房间，各房间编号依次为：
现所有房间已住满了人，这时来了一位新客人要求住 店，怎么安排？ 客 满

5 Hilbert旅馆 解决方法： 接着，又来了第二位新客人，旅店主也照此办理， 使第二位客人得到落实。
店主人把#1房的客人移到#2房，把#2房的客人移到#3 房，依此类推，新客人就住进了已腾空的#1房间； 接着，又来了第二位新客人，旅店主也照此办理， 使第二位客人得到落实。 紧接着，来了一个有无限多个游客的旅游团要求定住房间，怎么办 ？ 店主人把#1房的客人移到#2房，把#2房的客人移到#4房，#3房的客人移到#6房，等等，所有奇数号的房间全部腾空了，新的无限多个客人就全住进了旅店。

6 紧接着发生了更为严重的情况，来了无穷多个具有无穷多名游客的旅游团，怎么办？
第一个旅游团客人按如下房间编号住 第二个旅游团客人住的房间编号为 接着是

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

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

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

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

11 例1：证明 N={0,1,2,3,4,…...} 与下列集合等势 A={0,2,4,6,8,…...} B={1,3,5,7,9,…...} C={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等势 可见：无限集合与其真子集等势。

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

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

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

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

16 证明过程： 构造一个集合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。

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

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

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

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

21 定理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

22 直观上看，有理数比自然数多得多，但本质上它们却 “一样多”！
定理4.11 有理数集Q是可列集 证明：一切有理数均呈的形式，现将所有按下列次序排列， 正分数按其分子分母之和的大小顺序排列：从小到大 正分数的分子分母之和相同者按照分子大小顺序排列：从大到小 与正分数具有相同形式的负分数拍于正分数之后 按照上述规则可以得到一个序列 此序列可以跟自然数一一对应，因此是可列集。 “全体正整数的集合和全体有理数的集合等势”是在数学上很重要的一个例子，说明一个实数中的稠密集可以和一个离散集等势（稠密：在任意两个元素之间存在第三个元素） 直观上看，有理数比自然数多得多，但本质上它们却 “一样多”！

23 因为每个有理数都可以写成一个分数形式如下：
可以从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

24 之前出现过了

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

26 实数轴上的(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…... ..……..

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

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

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

30 自然数 N 的幂集 (2N) 是不可数的 [0,1) 之间的小数可以用十进制表示，也可以用二进制表示，表示形式是唯一的，0.5 D = 0.1 B，0.25 D = 0.01 B，.... 任意一个小于1 的非负小数，取其二进制形式，比如 ，如果将小数点后第 i 位对应的 0/1 看成是自然数 i 在某个集合中的无/有，那么 就对应自然数的一个子集 {1, 2, 4, 7}； 所以，任一个小数可以对应一个自然数的子集，当然，自然数的一个子集，也可以很容易写出一个小数： [0,1) 之间的小数与自然数 N 的所有子集的一一对应关系； 自然数的幂集，也就是自然数所有的子集形成的集合，它的基数，或是势，与 [0,1) 之间的实数相等，也有所有的实数的势相等；

31 连续统 定义：与区间（0，1)对等的集合就叫做连续统。对等就是找到一个映射，使得他们之间的元素满足一一映射。
在集合论中，连续统是一个拥有多于一个元素的线性序集，且满足如下性质（具此性质的序称为“稠密无洞”）： 稠密：在任意两个元素之间存在第三个元素 无洞：有上界的非空子集一定有上确界，实数集即为连续统的例子，实际上它是连续统的原型。 连续统假设（Continuum Hypothesis，常记作CH） 无穷集合中，除了整数集的基数，实数集的基数是最小的； 即0和1之间不存在其它x

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

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

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

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

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

37 定理. 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] 可数集合是“最小的”无限集合

38 选择公理（Axiom of Choice） 选择公理：设C为一个由非空集合所组成的集合。那么可以从每一个在C中的集合中，都选择一个元素来组成一个新的集合。 选择公理的意思是：如果有一堆非空集合，那么我们可以从每个集合里各取出一个元素。

39 说明 怎么从集合中选择一个元素？ 接受了选择公理，就意味着我们假定了选择函数f(s)始终存在，即使我们没有办法给出任何具体的构造和例子。
考虑实数的所有非空子集，怎么从每个非空子集中选一个元素？ 目前为止，没有人能找到一个恰当的f(s)作为选择函数，并且，模型论(model theory)中有一些颇具说服力的论证表明，这样的f(s)是不可能找到的。 接受了选择公理，就意味着我们假定了选择函数f(s)始终存在，即使我们没有办法给出任何具体的构造和例子。 哥德尔和寇恩证明了，无论接受选择公理与否，都不会导致矛盾，只是身处不同的『数学世界』而已。

40 选择公理（Axiom of Choice） 不少数学家曾尝试证明选择公理，他们希望用最基本的工具来作证明，但往往在这些证明中，都用了一些并不基本的理论，例如：「良序原理」（Well-ordering Principle）及「佐恩引理」（Zorn's Lemma）， 良序原理：所有集合也是良序集。换句话说，对每一个集合来说，都存在一种排序方法，使得它的所有子集也有极小元素。 佐恩引理：若一偏序集是归纳序集，那么，它必然存在最大元素。换句话说，如果在一个偏序集的每一条链中都存在著上界，这偏序集必存在最大元素。 事实上，「选择公理」、「良序原理」及「佐恩引理」都是等价的命题。

41 要在数学上证明或否证「选择公理」并非易事，对於这条公理不只是接纳和不接纳的问题，如果放弃这条公理，有很多美好且乎合「常理」的结果会同时被放弃；但它实际上又与很多「常理」大不协调。
其中一个为人熟识的不合乎常理的结果是「巴拿赫─塔斯基悖论」（Banach-Tarski Paradox），或称「分球问题」。这个誖论可以说是违反了物理学定律，因为这个誖论说可以把一个单位球体（半径为1）分成有限份，最少可分成五份，然後透过一些刚体运动，即旋转和平移，再重新组合，不过在组合後，竟然成为两个单位球体，也即是体积增加了一倍，而这个誖论的证明是必须利用到「选择公理」的。也就是说，如果我们选择接纳「选择公理」，则「巴拿赫─塔斯基誖论」便是一条定理，但现实中有这个可能吗？ 这其实也是牵涉另一个数学概念──可测集合（Measurable Set）。「巴拿赫─塔斯基悖论」便是存在不可测集合的结果。如果我们接纳「选择公理」，则我们必须接纳不可测集合。若我们不接纳「选择公理」，则可设所有集合皆是「勒贝格可测的」（Lebesgue Measurable），而这个假设也可能是较合乎常理。 「选择公理」是一条十分争议性的命题，一般的数学家都接受这条公理，因为可以从而得出很多有用的结果，反正使用这公理是没有逻辑矛盾的。

42 关于“巴拿赫─塔斯基悖论”的视频

43 随堂作业 证明：N×N的基数/势是0，N是自然数集合。