离散数学无穷集合及基数(精品).ppt

集合与图论第第5节节 无穷集合及其基数无穷集合及其基数什么是无穷集合什么是无穷集合?无穷集合之间能否比较大小无穷集合之间能否比较大小?无穷集合有什么特殊性质无穷集合有什么特殊性质?本部分内容主要是利用映射，尤其是利用双射本部分内容主要是利用映射，尤其是利用双射为工具，建立可数集、不可数集，并研究它们的一为工具，建立可数集、不可数集，并研究它们的一些性质，从而得到无穷些性质，从而得到无穷(限限)集合的特征性质。然后集合的特征性质。然后将有穷集合元素的个数的概念推广到无穷集合，建将有穷集合元素的个数的概念推广到无穷集合，建立无穷集合的基数的概念。立无穷集合的基数的概念。引言引言1集合与图论第第4节节 无穷集合及其基数无穷集合及其基数可数集可数集不可数集不可数集基数及其比较基数及其比较康托康托-伯恩斯坦定理伯恩斯坦定理悖论与公理化集合论悖论与公理化集合论主要内容：主要内容：2集合与图论 集合的基数亦称作集合的势。集合的基数亦称作集合的势。粗略的说，就是一个集合的粗略的说，就是一个集合的“规模规模”，它的，它的“大大小小”，或者更确切地说，它有多少个元素。，或者更确切地说，它有多少个元素。通俗的说，集合的势是量度集合所含元素多少的通俗的说，集合的势是量度集合所含元素多少的量。集合的势越大，所含的元素越多。量。集合的势越大，所含的元素越多。很明显，如果集合中只有有限个元素，我们只要很明显，如果集合中只有有限个元素，我们只要数一数它有多少个可以了，这时集合的基数就是其中数一数它有多少个可以了，这时集合的基数就是其中所含元素的个数。所含元素的个数。什么是集合的基数？什么是集合的基数？值得注意的是无限集，它所含的元素有无穷多值得注意的是无限集，它所含的元素有无穷多个，个，这时怎样去数？这时怎样去数？为了解决这个问题，我们首先从伽利略为了解决这个问题，我们首先从伽利略“悖论悖论”说起。说起。3集合与图论 1638年意大利的天文学家伽利略发现了下面年意大利的天文学家伽利略发现了下面的问题：的问题：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集合与图论 但另一方面，对于但另一方面，对于N+中的每个元素都可以在中的每个元素都可以在N(2)中找到一个元素与之对应，这样看来，中找到一个元素与之对应，这样看来，N(2)中的元素中的元素不比不比N+中的元素要少。中的元素要少。那么到底那么到底N+与与N(2)中所含元素的个数是否一样呢中所含元素的个数是否一样呢？如果是，那么就有？如果是，那么就有 部分部分=整体？整体？然而按照传统，部分怎么能等于全体呢？这就然而按照传统，部分怎么能等于全体呢？这就是伽利略是伽利略“悖论悖论”，它不仅困惑了伽利略，还使许多，它不仅困惑了伽利略，还使许多数学家亦束手无策。数学家亦束手无策。伽利略伽利略“悖论悖论”5集合与图论 1874年，年，Cantor注意到伽利略注意到伽利略”悖论悖论”。在在1874年到年到1897年间完全解决了这个问题。年间完全解决了这个问题。Cantor详细地分析了断定有限集合的元素多少详细地分析了断定有限集合的元素多少的方法，即采用数数的方法。他认为的方法，即采用数数的方法。他认为“数数的过程数数的过程”就是作就是作“一一一一对应的过程对应的过程”。Cantor认为这种认为这种“一一对应一一对应”的方法不仅适用的方法不仅适用于有限集，也适用于无限集。于有限集，也适用于无限集。他牢牢地抓住这个原则，抛弃了部分必定小于他牢牢地抓住这个原则，抛弃了部分必定小于全体的教条，经历了大约全体的教条，经历了大约23年之后，他才冲破了传年之后，他才冲破了传统观念的束缚，革命性的解决了伽利略统观念的束缚，革命性的解决了伽利略“悖论悖论”。Cantor认为在认为在N+与与N(2)之间存在着一一对应之间存在着一一对应(即即双射双射)，因此，因此N+与与N(2)的元素个数是相等的。的元素个数是相等的。一一对应与可数集一一对应与可数集6集合与图论 定义定义4.1 设设A，B是集合，若存在着从是集合，若存在着从A到到B的的双射，就称双射，就称A和和B等势等势(或或对等对等)，记作，记作AB。Cantor把自然数集把自然数集N+称为可数集称为可数集(或可列集或可列集)，这是因为它的元素可以一个一个的数出来。，这是因为它的元素可以一个一个的数出来。凡是与自然数集凡是与自然数集N+等势的集合，它们的元素通等势的集合，它们的元素通过一一对应关系，也都可以一个一个的数出来，因过一一对应关系，也都可以一个一个的数出来，因此：此：一一对应与可数集一一对应与可数集 定义定义4.2 凡是与自然数集凡是与自然数集N+等势的集合，称为等势的集合，称为可数集可数集(或或可列集可列集)。7集合与图论 显然，显然，N也是可数的也是可数的。Cantor以此为出发点，对无限集合进行考察，他以此为出发点，对无限集合进行考察，他发现下面的集合都是可数集：发现下面的集合都是可数集：(1)ODD=x|x N，x是奇数是奇数N F：NODD F(n)=2n+1（F：N+ODD F(n)=2n-1）(2)EVEN=x|x N，x是偶数是偶数NF：NEVEN F(n)=2n（F：N+EVEN F(n)=2(n-1)）(3)N(n)=x|x=mn，m，n N NF：NN(n)F(m)=mn一一对应与可数集一一对应与可数集8集合与图论(4)NNN一一对应与可数集一一对应与可数集9集合与图论(6)ZZN F:ZN F(n)=2n(n0)F(n)=2|n|-1(n0)的数排成一张表。显然所有的有的数排成一张表。显然所有的有理数都在这张表内。理数都在这张表内。一一对应与可数集一一对应与可数集11集合与图论一一对应与可数集一一对应与可数集12集合与图论 注意：以注意：以0/1作为第一个数，按照箭头规定作为第一个数，按照箭头规定的顺序可以的顺序可以“数遍数遍”表中所有的数。但是这个计数表中所有的数。但是这个计数过程并没有建立过程并没有建立N到到Q的双射，因为同一个有理数的双射，因为同一个有理数可能被多次数到。例如可能被多次数到。例如1/1，2/2，3/3，都是有理都是有理数数1。为此我们规定，在计数过程中必须跳过第二为此我们规定，在计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。如次以及以后各次所遇到的同一个有理数。如1/1被被计数，那么计数，那么2/2，3/3，都要被跳过。表中数都要被跳过。表中数p/q上上方的方括号内标明了这个有理数所对应的计数。方的方括号内标明了这个有理数所对应的计数。这样就可以定义双射函数这样就可以定义双射函数f：NQ，其中，其中f(n)是是n下方的有理数。从而证明了下方的有理数。从而证明了NQ。一一对应与可数集一一对应与可数集13集合与图论 正是由于这一发现，使得他甚至猜想正是由于这一发现，使得他甚至猜想R也是可数也是可数集，并且着手去证明它。他没有得到预期的结果，集，并且着手去证明它。他没有得到预期的结果，却又作出了更伟大的发现。却又作出了更伟大的发现。Cantor利用它著名的对角线法，证明了利用它著名的对角线法，证明了0,1是是不不可数集，在这个基础上证明了可数集，在这个基础上证明了R也是不可数的，甚至也是不可数的，甚至于于Rn也是不可数的。也是不可数的。Cantor对角线法与不可数集对角线法与不可数集 注注：(1)如果集合如果集合X不是可数集且不是可数集且X不是有限集，则不是有限集，则称称X为为不可数集不可数集。(2)可数集与不可数集是对无穷集合而言的，可数集与不可数集是对无穷集合而言的，有有限集既不称作不可数集合也不称作可数集。限集既不称作不可数集合也不称作可数集。14集合与图论 定理定理4.1 区间区间0,1中的所有实数构成的集合是不中的所有实数构成的集合是不可数集。可数集。证证 区间区间0,1中每个实数，都可以写成十进制无限中每个实数，都可以写成十进制无限位小数形式位小数形式0.a1a2a3a4.，其中每位，其中每位ai 0,1,2,.,9。约定每个有限位小数后均补以无限多约定每个有限位小数后均补以无限多0。假定定理不成立，于是假定定理不成立，于是0,1中全体实数可排成一中全体实数可排成一个无穷序列个无穷序列:a1,a2,a3,.,an,.。Cantor对角线法与不可数集对角线法与不可数集15集合与图论每个每个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，但，但 n N，b an，矛盾。，矛盾。其中：若其中：若ann=5，则，则bn5；若若ann5，则，则bn=5，n=1,2,3,Cantor对角线法与不可数集对角线法与不可数集16集合与图论 这说明这说明0,1是不可数集，从而证明了并非一切是不可数集，从而证明了并非一切无限集合都是可数集，无限集合也是有区别的。无限集合都是可数集，无限集合也是有区别的。Cantor首次对无限集合从首次对无限集合从“定量定量”方面进行了方面进行了深入研究，使人们深刻认识到集合深入研究，使人们深刻认识到集合N与与R有本质不同。有本质不同。Cantor用对角线元素来构造小数用对角线元素来构造小数x*的方法称为的方法称为Cantor对角线法对角线法。Cantor所创造的这一方法是一个强有力的证明所创造的这一方法是一个强有力的证明方法，在函数论和计算机科学中有许多应用。在计方法，在函数论和计算机科学中有许多应用。在计算的复杂性理论和不可判定问题中，对角线法也是算的复杂性理论和不可判定问题中，对角线法也是为数不多的几个重要方法之一。为数不多的几个重要方法之一。Cantor对角线法与不可数集对角线法与不可数集17集合与图论 性质性质1 集合集合A为可数集的充分必要条件是为可数集的充分必要条件是A的全的全部元素可以排成无重复项的序列部元素可以排成无重复项的序列a1,a2,.,an,.性质性质2 无限集无限集A必包含可数子集。必包含可数子集。性质性质3 可数集的任一无限子集也是可数集。可数集的任一无限子集也是可数集。性质性质4 从可数集从可数集A中除去一个有限集中除去一个有限集M，则，则AM仍是可数集，即仍是可数集，即AAM。无限集合的性质无限集合的性质 性质性质5 设设M是一个无穷不可数集，是一个无穷不可数集，A为为M的至多的至多可数子集可数子集(即即A有穷或可数有穷或可数)，则，则MMA。定义定义4.3 凡能与自身的一个真子集对等的集合凡能与自身的一个真子集对等的集合称为称为无穷集合无穷集合，或，或无限集合无限集合。18集合与图论 如果要对任意的集合谈论它们中元素的如果要对任意的集合谈论它们中元素的“个数个数”，这就需要把有限集合里元素，这就需要把有限集合里元素“个数个数”的的概念推广到无限集合中，要求下一个定义对任何概念推广到无限集合中，要求下一个定义对任何集合都适用。集合都适用。集合的基数或集合的势是集合论中基本概念集合的基数或集合的势是集合论中基本概念之一，在朴素集合论体系中讨论基数的概念，只之一，在朴素集合论体系中讨论基数的概念，只能从几条规定或公理出发。能从几条规定或公理出发。集合的基数集合的基数 设设A为任意一个集合，现在规定用为任意一个集合，现在规定用cardA表示表示A中的元素中的元素“个数个数”，并称，并称cardA为集合为集合A的基数，的基数，并再作以下五条规定：并再作以下五条规定：19集合与图论 (3)对于自然数集合对于自然数集合N，规定，规定cardN=0(读作阿列夫零读作阿列夫零)。(4)对于实数集合对于实数集合R，规定，规定cardR=(读作阿列读作阿列夫夫)。(5)将将0，1，2，0，都称作基数，都称作基数，其中其中0，1，2，称作有穷基数，而称作有穷基数，而0，称作无称作无穷基数。穷基数。(1)对于任意的集合对于任意的集合A和和B，规定，规定 cardA=cardB当且仅当当且仅当AB。(2)对于任意的有限集合对于任意的有限集合A，规定与，规定与A等势的自等势的自然数然数n为为A的基数，记作的基数，记作cardA=n。集合的基数集合的基数20集合与图论 定义定义4.4 集合集合A的的基数基数是一个符号，凡与是一个符号，凡与A等势等势的集合都赋以同一个记号，集合的集合都赋以同一个记号，集合A的基数记为的基数记为|A|，也记作也记作cardA。定义定义4.4 所谓集合的所谓集合的基数基数是指所有与该集合等是指所有与该集合等势的集合所构成的集族的共同性质。势的集合所构成的集族的共同性质。(冯冯 诺伊曼诺伊曼)定义定义4.4 集合的集合的基数基数是集合的这样一种特性，是集合的这样一种特性，当把集合里元素固有特点抽出，以及把各元素在集当把集合里元素固有特点抽出，以及把各元素在集合中的次序不顾之后，仍然保留下来的特性，就叫合中的次序不顾之后，仍然保留下来的特性，就叫做基数。做基数。集合的基数集合的基数21集合与图论Cantor连续统猜想连续统猜想Cantor猜想猜想(连续统猜想，连续统猜想，CH)：在在 0与与之间是否还有别的基数？之间是否还有别的基数？定义定义4.5 凡与集凡与集0,1对等的集称为具有对等的集称为具有“连续连续统的势统的势”的集，或简称的集，或简称连续统连续统。实数集实数集R、无理数之集都无理数之集都是连续统。是连续统。1938年，年，K.哥德尔证明了哥德尔证明了CH对对ZFC公理系统公理系统（见公理集合论（见公理集合论)是协调的。是协调的。1963年，年，P.J.科恩证明科恩证明CH对对ZFC公理系统是独公理系统是独立的。立的。这样，在这样，在ZFC公理系统中，公理系统中，CH是不可能判定是不可能判定真假的。这是真假的。这是20世纪世纪60年代集合论的最大进展之年代集合论的最大进展之一。一。22集合与图论 定义定义4.6 集合集合A的基数与集合的基数与集合B的基数称为是相的基数称为是相等的，当且仅当等的，当且仅当AB。定义定义4.7 ，是任意两个基数，是任意两个基数，A，B是分别以是分别以，为其基数的集。如果为其基数的集。如果A与与B的一个真子集对等，的一个真子集对等，但但A却不能与却不能与B对等，则称基数对等，则称基数 小于基数小于基数，记为，记为 。规定规定 当且仅当当且仅当 当且仅当当且仅当 或或=。基数及其比较基数及其比较23集合与图论规定规定 当且仅当存在单射当且仅当存在单射f:AB。规定规定 当且仅当存在单射当且仅当存在单射f:AB，且不存在，且不存在A到到B的双射。的双射。无穷集合的基数也称超穷数，超穷数也可以比较无穷集合的基数也称超穷数，超穷数也可以比较大小。于是，像下面这些句子是有意义的：大小。于是，像下面这些句子是有意义的：“平面上平面上的点多还是平面上的圆多？的点多还是平面上的圆多？”，“集合集合0,1中的数中的数比自比自然数集然数集N中的数多中的数多”，“有理数和自然数一样多。有理数和自然数一样多。”基数及其比较基数及其比较问题：问题：无穷基数有多少？无穷基数有多少？有没有最大的无穷基数？有没有最大的无穷基数？定理定理4.2 (康托康托)对任一集合对任一集合M，M n，m=n，mn。那么，对任两个无限数那么，对任两个无限数，下面三个式子是否，下面三个式子是否也有且仅有一个成立呢也有且仅有一个成立呢?。答案是肯定的。答案是肯定的。25集合与图论 设是一个基数为设是一个基数为 的集合，是基数为的集合，是基数为 的集合。的集合。如果如果=，那么，那么 ，都不能成立都不能成立。若若 ，同时成立同时成立，则从，则从A到到B的每个单射都不的每个单射都不是满射，而从是满射，而从B到到A的每个单射都不是满射。的每个单射都不是满射。我们能证明这是不可能的，从而我们能证明这是不可能的，从而 与与 不能同不能同时成立。时成立。定理定理4.3(康托康托-伯恩斯坦伯恩斯坦)设设A，B是两个集合。是两个集合。如果存在单射如果存在单射f:AB与单射与单射g:BA，则，则A与与B对等。对等。只要能利用只要能利用f与与g直接建立一个从到的一个一直接建立一个从到的一个一一对应即可。一对应即可。康托康托-伯恩斯坦定理伯恩斯坦定理26集合与图论 推论推论 设设,为任意三个基数。如果为任意三个基数。如果 ，则，则 。定理定理4.4(E.Zermelo，策梅罗，策梅罗)设设 与与 为任意两为任意两个基数，则以下三个式子个基数，则以下三个式子=，中恰有一中恰有一个式子成立。个式子成立。27集合与图论 但另一方面，但另一方面，U是所有集合组成的集合，所以对是所有集合组成的集合，所以对任一任一X P(U)，X U 且且X是一个集合，从而是一个集合，从而X U，因此，因此，P(U)U，所以，所以|U|P(U)|矛盾。矛盾。首先从朴素集合论蕴含的悖论谈起。首先从朴素集合论蕴含的悖论谈起。所谓悖论是指这样一个命题所谓悖论是指这样一个命题A，从，从A出发可以导出出发可以导出一个语句一个语句B，然而若假定，然而若假定B真，则可以推知真，则可以推知B不真；若假不真；若假定定B不真，又可以推知不真，又可以推知B真。真。Cantor悖论悖论(最大基数悖论最大基数悖论)(1899)按按Cantor的集合概念，可以有所有集合的集合的集合概念，可以有所有集合的集合U。一方面，由一方面，由Cantor定理得到定理得到|U|P(U)|；悖论与公理化集合论悖论与公理化集合论28集合与图论令令S=x|x x 则则S S?S S S S S S S S 1919年罗素将其悖论通俗化：年罗素将其悖论通俗化：某一村落中的一个理发师，他只替村中所有不某一村落中的一个理发师，他只替村中所有不给自己理发的人理发，到底他是否替自己理发？给自己理发的人理发，到底他是否替自己理发？Cantor悖论和罗素悖论只涉及集合的概念，看悖论和罗素悖论只涉及集合的概念，看来来Cantor的集合概念蕴含着矛盾。为了消除悖论，的集合概念蕴含着矛盾。为了消除悖论，人们建立集合论的公理系统，在保留概括原则种的人们建立集合论的公理系统，在保留概括原则种的合理因素，对造集的任意性加以限制。在公理集合合理因素，对造集的任意性加以限制。在公理集合论中已出现的悖论都消掉了。论中已出现的悖论都消掉了。罗素悖论罗素悖论(1902年年)29