第五章 无 限 集 合 第五章 无 限 集 合 5.1 可数和不可数集合可数和不可数集合5.2 基数的比较基数的比较5.3 基数算术基数算术 （了解）（了解）1 第五章 无 限 集 合 无限集合如何计数？ 偶数的个数比自然数的个数少偶数的个数比自然数的个数少 ）（五年级））（五年级）Ø20世纪著名数学家希尔伯特(D.Hilbert) ——没有任何问题可以像无穷那样深深地触动人的情感, 很少有别的观念能像无穷那样激励理智、产生富有成果的思想,然而也没有任何其他的概念能像无穷那样需要加以阐明 Ø康托被誉为对20世纪数学发展的影响最深的学者之一，他的研究就是从查点集合中元素数目开始的，而其独创性在于对无限集合（自然数集、整数集等）的研究康托发现人们在计数时应用了一一对应的方法，并由此把“无穷的各种关系弄得完全明朗 2 第五章 无 限 集 合 5.1 可数和不可数集合可数和不可数集合 5.1.1 有限和无限集合有限和无限集合 定定义义5.1-1 N的初始段是前n个(包括0个)自然数的集合{0,1,…,n-1}或N自身 定义定义5.1-2 如果有从N的初始段{0,1,…,n-1}到A的双射函数, 那么集合集合A是有限的是有限的, 具有基数基数n∈N。
如果集合A不是有限的, 那么它是无限的是无限的 3 第五章 无 限 集 合 定理定理5.1-1 自然数集合N是无限的 证证 为了证明N不是有限的, 我们必须证明没有n∈N使从{0,1,2,…,n-1} 到N的双射函数存在设n是N的任意元素, f是任意从{0,1,…,n-1}到N的函数, 令k=1+max｛f(0),f(1),…,f(n-1)｝那么k∈N, 但对每一x∈{0,1,2,…,n-1}, f(x)≠k 这说明, f不是一个满射函数, 所以f不是一个双射函数 因为n和f都是任意选取的, 我们得出N是无限的 4 第五章 无 限 集 合 定理定理5.1-2 有限集合的每一子集是有限的 推论推论5.1-2 设S是T的子集, 如果S是无限集, 那么T是无限集5 第五章 无 限 集 合 5.1.2 可数集合可数集合 度量集合大小的数叫基数或势为确定有限集的大小, 我们把称作N的初始段的集合{0,1,…,n-1}作为“标准集合”, 用双射函数做工具, 对它们进行比较当且仅当从{0,1,2,…,n-1}到集合A存在一双射函数时, 称集合A具有基数n, 记为|A|=n, 记为|A|=n,这就是日常生活中的数数的概念。
6 第五章 无 限 集 合 5.1.2 可数集合可数集合 把Z中的元素按如下顺序排列0，-1，1，-2，2，-3，3，-4，4，……让上面的每个元素与它的序号对应就建立了一个从Z到N的一一映射 是否说明Z与N的元素个数相同？7 第五章 无 限 集 合 某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为1，2，3，，……我们不妨管它叫无穷旅馆有一天开大会，所有房间都住满了后来来了一位客人，坚持要住房间旅馆老板于是引用“旅馆公理”说：“满了就是满了，非常对不起！”正好这时候，聪明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬一下，从这间房搬到下一间”于是1号房间的客人搬到2号房间，2号房间的客人搬到3号房间……依此类推最后1号房间空出来，请这位迟到的客人住下了这是怎么回事呢？第二天又来了五对夫妇旅游度假无穷饭店能不能接待他们？可以，老板聪明了，只不过把每个客人都一一移到高5号的房间中去，空出的1到5号房就给这5对夫妇第三天，无穷旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数无穷多位代表一定要住，这回不仅把老板难住了，连女儿也被难住了。
聪明的女儿想了很久，终于也想出了办法你想到了吗？你想到了吗？8 第五章 无 限 集 合 运用了一一对应的方法：第一天让住第n间房的人搬到第n+1间房：2 3 4 5 6……n……3 4 5 6 7……n+1……这样就空出了第1间房；第二天让住第n间房的人搬到第n+6间房，这样就空出了5间房；第三天呢？她说：“您让1号房间客人搬到2号，2号房间客人搬到4号……，k号房间客人搬到2k号，这样，1号，3号，5号，……房间就都空出来了，代表团的代表都能住下了 如我们所知，任何一个有限集都不能与它的一个真子集建立一一对应的关系对于无穷集这—点就不成立了看上去这样就违反了整体大于局部这一古老法则确实，一个无穷集可以定义为能够与它的一个真子集一一对应的集 9 第五章 无 限 集 合 •关于无穷大还有很多悖论计数用的数是无穷大等级中最低一级的无穷数在整个宇宙中的点数是第二级无穷大数，第三级无穷大数比这要多得多！•德国数学家乔治·康托发现了无穷大的这种等级，他把这种新型的奇异等级称为阿列夫零、阿列夫1、阿列夫2等等关于阿列夫数有很多深刻的神秘性，解决它们是现代数学中最激动人心的挑战之一。
10 第五章 无 限 集 合 5.1.2 可数集合可数集合 度量集合大小的数叫基数或势为确定有限集的大小, 我们把称作N的初始段的集合{0,1,…,n-1}作为“标准集合”, 用双射函数做工具, 对它们进行比较当且仅当从{0,1,2,…,n-1}到集合A存在一双射函数时, 称集合A具有基数n, 记为|A|=n, 记为|A|=n,这就是日常生活中的数数的概念 现在我们将这种想法加以推广 通过选取一些新的“标准集合”, 建立无限集合的基数的概念 11 第五章 无 限 集 合 定定义义5.1-3 如果存在一个从N到A的双射函数,那么集合A的基数是 0 , 记为|A|= 显然, 存在从N到N的双射函数, 所以, |N|= , 读做阿列夫零, 是希伯来文第一个字母 12 第五章 无 限 集 合 例例2函数f: N→I+, f(x)=x+1是一双射函数 函数f: N→I , 当x是偶数时 当x是奇数时 是一双射函数 13 第五章 无 限 集 合 定定义义5.1-4 如果存在从N的初始段到集合A的双射函数, 则称集合A是可可数数的的或可可列列的的;如果 , 则称集合A是可可数数无无限限的的; 如果集合A不是可数的, 则称集合A是不不可可数数的的或不不可可数数无无限限的的。
一个集合A, 如果它的元素可列成表, 我们说这个集合是可枚举的这个表可以是有限的也可以是无限的, A的元素也可以在表中重复出现, 即不要求表中的所有项都是有别的 如果一张表列出集合A, 那么表的每一项是A的一个元素, 而A的每一元素是表的一项 14 第五章 无 限 集 合 定定义义5.1-5 设A是一集合, A的枚枚举举是从N的初始段到A的一个满射函数f如果f也是单射的(所以是双射的), 那么f是一个无重复枚举; 如果f不是单射的, 那么f是重复枚举 枚举函数f通常是用给出序列〈f(0),f(1),f(2),…〉含蓄地指定 15 第五章 无 限 集 合 例例3 (1) 如果A={x,y}, 那么〈x,y,x〉和〈y,x〉都是A的有限枚举, 第一个是重复枚举, 第二个是无重复枚举 (2) 设A是非负的3的整倍数集合, 那么 〈0,3,6,…〉和〈3,0,9,6,15,12,…〉都是A的无重复枚举, 后者的枚举函数是16 第五章 无 限 集 合 定理定理5.1-3 一个集合A是可数的当且仅当存在A的枚举。
定理定理5.1-4 可数个可数集合的并是可数的 17 第五章 无 限 集 合 5.1.3 基数基数c 不是所有无限集都是可数无限的, 下一定理说明需要新的无限集基数 定理定理5.1-7 实数的子集［0,1］不是可数无限 18 第五章 无 限 集 合 定定义义5.1-6 如果有从［0,1］到集合A的双射函数,那么A的基数是c 选用字母c是根据集合［0,1］常叫做连续统(Continuum)这个事实 连续统连续统是一个数学概念当人们笼统地说：“在实数集里实数可以连续变动连续变动”，也就可以说实数集是个连续统实数集是个连续统；更严格的描述需要使用序理论、拓扑学等数学工具这里的连续是相对于离散离散的概念而言的在不讨论精确的定义前，有时人们也会谈到一个量可以在某范围内连续取值连续取值，或者说该量的变化范围是一个连续统是一个连续统在数学上，连续统这一术语至少有两种精确定义，但并不等价 19 第五章 无 限 集 合 5.2 基数的比较基数的比较 5.2.1 基数比较基数比较 我们知道, 如果A和B是有限集, |A|=n, |B|=m, 那么 (a) 如果存在一个从A到B的双射函数, 那么n=m。
(b) 如果存在一个从A到B的单射函数, 那么n≤m (c) 如果存在一个从A到B的单射函数, 但不存在双射函数, 那么n＜m 20 第五章 无 限 集 合 定义5.2-1 设A和B是任意集合 (1) 如果有一个从A到B的双射函数, 那么称A和B有相同的基数(或等势), 记为|A|=|B| (2) 如果有一个从A到B的单射函数, 那么称A的基数小于等于B的基数, 记为|A|≤|B| (3) 如果有一个从A到B的单射函数, 但不存在双射函数, 那么称A的基数小于B的基数, 记为|A|＜|B| 21 第五章 无 限 集 合 第一个定理叫做三歧性定律第一个定理叫做三歧性定律 定理定理5.2-2(Zermelo) 设A和B是集合,那么下述情况恰有一个成立: (a) |A|＜|B|, (b) |B|＜|A|, (c) |A|=|B| 第二个定理断言关系≤是反对称的 22 第五章 无 限 集 合 策梅洛策梅洛（德语：Ernst Friedrich Ferdinand Zermelo1871年7月27日－1953年5月21日）生于柏林，是德国数学家，其工作主要为数学基础，因而对哲学有重要影响。
1889年，他毕业于柏林大学他然后在柏林大学、Halle和弗莱堡研究数学、物理和哲学他于1894年在柏林大学完成博士学位，其博士论文是关于变分法的策梅洛留在柏林大学，他被聘为普朗克的助手，在其指导下，他开始研究流体力学在1897年，策梅洛去了格丁根，那时是整个世界的数学研究的中心，在那里他于1899年完成了教员资格论文策海洛于1953年5月21日在弗赖堡逝世 23 第五章 无 限 集 合 定理定理5.2-5 设A是有限集合, 那么 24 第五章 无 限 集 合 5.2.3 无限集合的特性无限集合的特性 定理定理5.2-6 每一无限集合包含一可数无限集合 证证 设A是无限集合, 应用选择公理于A的子集的序列，我们构造一无限序列〈a0,a1,a2,…〉如下: 从A中选取a0 从A-{a0}中 选取a1 从A-{a0,a1}中选取a2 从A-{a0,a1,a2}中选取a3 25 第五章 无 限 集 合 集合A-{a0,a1,a2,…,an}的每一个都是无限的。
若不然, A将等于两个有限集合A-{a0,a1,…,an}和{a0,a1,…,an}的并, 而两个有限集合的并是有限集合, 与A是无限集合矛盾这样, 我们能从A-{a0,a1,…,an}中选取一个新元素an+1, 从而能够构造一无限序列a0,a1,a2,…而没有重复这个序列的元素组成一个A的可数无限子集B 于是定理得证 26 第五章 无 限 集 合 定理定理5.2-7 是最小的无限集基数 证证 根据定理5.2-6, 如果A是无限集合, 那么A包含一可数无限子集B因为映射f: B→A, f(x)=x, x∈B是从B到A的单射函数, 这得出|B|≤|A|, 而 , 我们得 27 第五章 无 限 集 合 5.2.4 基数的无限性和连续统假设基数的无限性和连续统假设 定理定理5.2-9 (Cantor)设A是一集合, 那么|A|＜|ρ(A)|证证 容易看出, 函数f: A→ρ(A), f(a)={a}是单射的 所以, |A|≤|ρ(A)| ; 下面我们证明|A|≠|ρ(A)|。
设g:A→ρ(A)是任意函数, 我们要证明g不是满射的, 因而不是双射的 函数g映射A的每一元素x到A的子集g(x), 元素x可能在子集g(x)中, 即x∈g(x),也可能 定义集合S是A的子集 28 第五章 无 限 集 合 现在证明对任一a∈A, g(a)≠S用反证法, 假设g(a)=S, 则 根据S的定义 ;根据定义S的谓词 ; 根据假设g(a)=S 这是一个矛盾, 所以g(a)=S是假因为a是任意的, 这得出g不是满射函数, 因此不是双射函数又g是任意函数, 这证明了没有双射函数存在, 所以|A|≠|ρ(A)| 应用本定理我们能够构造一个可数无限的无限基数的集合 其中每一个都大于它前边的一个N|＜|ρ(N)|＜|ρ(ρ(N))|＜… 29 第五章 无 限 集 合 如果集合A有n个元素, 则ρ(A)有2n个元素, 本节例3证明了｜ρ(N)｜=c, 于是人们认为 A是有限集时, |A|和|ρ(A)|之间存在着其它基数, 于是康脱提出和c之间是否也存在其它基数 连续统假设断言不存在这样的基数。
从前已经知道连续统假设和集合论公理是一致的但1963年科恩(Paue Cohen)证明连续统假设的反命题也和集合论公理一致，即连续统假设和集合论公理是独立的这就给我们带来一个问题, 例如, 我们要证明所给集合A有基数c, 如果接受连续统假设, 那么我们只需证明|A|≤c和 如果拒绝这一假设, 那么这样的证明是不充分的, 可能有 我们应避开使用这一假设 30 。