第四章 9基数

**离散数学(DiscreteMathematics)**4-4基数的概念自然数集合等势的概念基数的概念小结**4-4基数的概念一、自然数集合(NaturalNumbersSet)问1：如何衡量集合的大小？对于有限集：集合中不同元素的个数。对于无限集：？为了比较两个集合的“大小”，确定有限集和无限集的概念，我们首先引进自然数集合。问题2：是否所有无限集的基数都一样？**4-4基数的概念定义4-4.1给定集合A，A+=A{A}，称A+是A的后继集合(SuccessorSet)。例1设A=，则A的后继集合可写成：A+={}={}(A+)+={}{{}}={,{}}((A+)+)+={,{}}{{,{}}}={,{},{,}}}…**4-4基数的概念Peano公理自然数集合N是如下定义的集合：(1)基础：N；(2)归纳：如果nN，那么n+N；(3)极小性：若SN，且S也满足(1)、(2)，则S=N.按照这个定义，自然数可罗列如下：，{}，{,{}}，{,{},{,{}}}，…若依次记为0，1，2，3，…，则自然数集合为N={0，1，2，3，…}**4-4基数的概念定义4-4.2给定二个集合P和Q，如果我们对P中每一个不同元素与Q中每一个不同元素可以分别两两成对，则我们说P中的元素和Q中的元素存在着一一对应。例2P={1,3,5,…,2n-1,…}Q={2,4,6,…,2n,…}则P和Q之间存在着一一对应，其函数关系为：f：P→Q，f(n)=n+1二、等势的概念**4-4基数的概念定义4-4.3当且仅当集合A的元素与集合B的元素之间存在着一一对应，则称A与B是等势的(EqualCardinality)，记作A~B。例如，在I+集合中，奇数集和偶数集是等势的。例3自然数集N和非负偶数集E是等势的。证f(n)=2n，则f：N→E为一一对应函数。∴N~E。作一函数f：N→E，且对任一nN，有**4-4基数的概念例4(0,1)~R。证则f：R→(0,1)为一一对应函数。∴(0,1)~R。例5设A={1,2,3,4,5}，B={a,b,c,d,e},定义一函数f为一双射函数。∴A~B(|A|=|B|)证激活函数Sigmoide=2.7182**4-4基数的概念定理4-4.1集合族上的等势关系是一个等价关系。证设集合族为S。(1)自反性：对任意AS，必有A~A。(2)对称性：对任意A，BS，若A~B，则必有B~A。(3)传递性：对任意A，B，CS，若A~B，B~C，则必有C~A。所以，集合族上的等势关系是一个等价关系。**4-4基数的概念定义4-4.4如果有一个从集合{0,1,…,n-1}到A的双射函数，那么称集合A为有限集(FiniteSet)。如果集合A不是有限集，那么它是无限集(InfiniteSet)。定理4-4.2自然数集合N是无限的。证对任一函数，对任意的nN，设但x{0,1,…,n-1}，f(x)≠k，即f不是满射，也就不是双射，则kN，再由n，f的任意性，可知自然数集合N是无限的。**4-4基数的概念定义4-4.4所有与集合A等势的集合所组成的集合，叫做集合A的基数或势(Cardinality，Potency)，记为K[A]（或|A|）。三、基数的概念有限集合的基数就是其元素的个数。A与B等势K[A]=K[B]集合A与集合B的元素存在一一对应**4-4基数的概念例6证明[0,1]与(0,1)等基数。证则f：[0,1]→(0,1)为双射函数。故[0,1]与(0,1)等基数。设**4-4基数的概念本结介绍了自然数集合、一一对应、等势基数以及有限集与无限集的概念。重点是基数的概念。四、小结**离散数学(DiscreteMathematics)**4-5可数集与不可数集可数集与不可数集的概念可数集与不可数集的性质小结**4-5可数集与不可数集一、可数集与不可数集的概念定义4-5.1与自然数集合等势的任何集合称为可数集合(CountableInfiniteSet)。其基数用示。例如|A|=|B|=|C|=|D|=。有限集与可数集统称为至多可数集。不是可数集的无限集称为不可数集。**4-5可数集与不可数集定理4-5.1集合A为可数集的充要条件是A可以表示成的形式。定理4-5.2任一无限集必包含可数子集。**4-5可数集与不可数集定理4-5.4可数集任何无限子集是可数的。定理4-5.5可数个两两不相交的可数子集的并集仍是可数的。定理4-5.3任一无限集必与其某一真子集等势。有限集不能与其真子集等势。集合A是无限集的充要条件是A含有一个真子集A1与A等势。**由定理4-5.6可知N×N是可数的，在N×N中删除所有m与n不是互质的序偶，得集合S，4-5可数集与不可数集定理4-5.7有理数的全体组成的集合是可数的。证明定理4-5.6设N为自然数集合，则N×N是可数的。因为S是N×N的无限子集，由定理4-5.4可知，S是可数的。作映射因为g是双射，故Q+是可数集。又因为故是可数集。**用反证法（康托尔对角线法）。4-5可数集与不可数集定理4-5.6集合(0,1)是不可数的。证明则由定理4-5.1，(0,1)可表示为其中假设(0,1)集合是可数的，一切适合0