05 离散数学 第五章 无限集合

第五章无限集合第五章无限集合5.1可数和不可数集合5.2基数的比较5.3基数算术第五章无限集合5.1可数和不可数集合5.1.1有限和无限集合定义5.1-1N的初始段是前n个(?包括0个)自然数的集合{0,1,…,n-1}或N自身。定义5.1-2如果有从N的初始段{0,1,…,n-1}到A的双射函数,那么集合A是有限的,具有基数n∈N。如果集合A不是有限的,那么它是无限的。第五章无限集合定理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是无限的。证毕。第五章无限集合定理5.1-2有限集合的每一子集是有限的。证设S是有限集T的任一子集,(i)如果S是空集,S的双射函数——空函数,根据定义5.1-2,S是有限的。(ii)如果S是非空集,那么T也是非空集。因为T是有限的,所以存在双射函数使T的每一元素和某个N的初始段中的数对应。我们把和数i对应的元素就记为ai,于是T的元素是a0,a1,a2,…,an-1第五章无限集合现在我们要造出一个双射函数g,使某一N的初始段和S的元素对应。构造方法如下:(1)置i=0,j=0。(2)先检查ai是否在S中,如果在S中,转第3步。否则转第4步。(3)使g(j)=ai,把j的值加1,把i的值加1,加1后如果i＜n转第(2)步,否则结束。(4)把i的值加1,加1后如果i＜n转第(2)步,否则结束。容易看出这样构造的函数g是从初始段{0,1,2,…,j-1}到S的双射函数。按定义5.1-2,S是有限集。第五章无限集合推论5.1-2设S是T的子集,如果S是无限集,那么T是无限集。本推论是上一定理的逆反。例1设A表示永不停机的ALGOL程序集合,我们通过构造永不停机的程序集合A的一个子集A′,证明A是无限集合。begin;B:gotoB;end这个程序我们记作p0是A的一个元素。在紧接于begin的后边,我们插入语句gotoB第五章无限集合5.1.2可数集合度量集合大小的数叫基数或势。为确定有限集的大小,我们把称作N的初始段的集合{0,1,…,n-1}作为“标准集合”,用双射函数做工具,对它们进行比较。当且仅当从{0,1,2,…,n-1}到集合A存在一双射函数时,称集合A具有基数n,记为|A|=n,记为|A|=n,这就是日常生活中的数数的概念。现在我们将这种想法加以推广。通过选取一些新的“标准集合”,建立无限集合的基数的概念。第五章无限集合定义5.1-3如果存在一个从N到A的双射函数,那么集合A的,记为。显然,存在从N到N的双射函数,所以,,读做阿列夫零,是希伯来文第一个字母。SS0\SSA0\SSN0\||SS0\SS\第五章无限集合例2SSIa0\||)(函数f:N→I+,f(x)=x+1是一双射函数。SSIb0\||)(函数f:N→I,212)(xxxf当x是偶数时当x是奇数时是一双射函数。第五章无限集合定义5.1-4如果存在从N的初始段到集合A的双射函数,则称集合A是可数的或可列的如果,则称集合A是可数无限的;如果集合A不是可数的,则称集合A是不可数的或不可数无限的。SSA0\||一个集合A,如果它的元素可列成表,我们说这个集合是可可枚举的。这个表可以是有限的也可以是无限的,A的元素也可以在表中重复出现,即不要求表中的所有项都是有别的。如果一张表列出集合A,那么表的每一项是A的一个元素,而A的每一元素是表的一项。第五章无限集合定义5.1-5设A是一集合,A的枚举是从N的初始段到A的一个满射函数f。如果f也是单射的(所以是双射的),那么f是一个无重复枚举;如果f不是单射的,那么f是重复枚举。枚举函数f通常是用给出序列〈f(0),f(1),f(2),…〉含蓄地指定。第五章无限集合.),1(3.),1(3)(是奇数如果是偶数如果nnnnnf例3(a)如果A=,仅有一个A的枚举,它是空函数。(b)如果A={x,y},那么〈x,y,x〉和〈y,x〉都是A的有限枚举,第一个是重复枚举,第二个是无重复枚举。(c)设A是非负的3的整倍数集合,那么〈0,3,6,…〉和〈3,0,9,6,15,12,…〉都是A的无重复枚举,后者的枚举函数是第五章无限集合定理5.1-3一个集合A是可数的当且仅当存在A的枚举。证必要性。如果A是可数的,那么根据定义,存在一从N的初始段到A的双射函数,这证明了存在A的枚举。充分性。我们考虑两种情况:情况1如果A是有限的,那么根据有限集合的定义和可数集合的定义,A是可数的。情况2假设A不是有限的而f是A的枚举。枚举f必须以N的全集作为它的前域。如果f是双射函数,那么根据可数无限集合的定义,A而A是可数的。如果f不是双射函数。利用下述办法,根据枚举f构造一个从N到A的双射函数g,以证明A是可数的。SSA0\||第五章无限集合(1)置g(0)=f(0),i=1,j=1。(2)检查f(i)是否已出现在S={g(0),g(1),…,g(j-1)}中,如果f(i)不在S中,转第(3)步,否则转第(4)步。(3)置g(j)=f(i),把j的值加1,把i的值加1,然后转第2步。(4)把i的值加1,再转第(2)步。如此地进行下去,就可得出任意n∈N的g(n)值。因为A的每一元素是某整数i的对应值f(i),这得出A的这个元素是函数g对某自变元j的值g(j),这里j≤i。因此g是满射的。又根据构造方法,g(0)、g(1)、g(2)…中无重复的,另外,因为A是无限的,g的前域将是整个集合N。所以g是N到A的双射函数。这证明了和A是可数的。SSA0\||第五章无限集合例4(a)设Σ={a,b},则Σ*是可数无限的。不妨设a≤b,这样,Σ*的元素能用标准序列出,Σ*的枚举是〈Λ,a,b,aa,ab,ba,bb,aaa,aab,…〉所以,Σ*是可数无限的。对任何有限字母表Σ,以上结论均成立。但注意,如果｜Σ｜＞1,那么Σ*不能按词典序枚举。(b)正有理数集合Q+是可数无限的。显然Q+不是有限的,因为其真子集正整数集合I+是无限的。可如图5.1-1那样,对Q+进行重复枚举,枚举的次序用有向路径指出。所以,Q+是可数无限的。第五章无限集合图5.1-1第五章无限集合图5.1-2第五章无限集合定理5.1-4可数个可数集合的并是可数的。证设S是N的初始段,集合这里每一Ai是可数的。如果S=或对每一i∈S,Ai=,那么A=,结果成立。现在假定S≠且至少有一非空集合Ai;不失一般性,我们假定A0≠。我们用非空集合的枚举构造一无限数组。如果Ai≠,那么数组第i行是Ai的枚举;如果Ai是有限的我们用无限重复枚举。如果Ai=,我们置第i行等于第i-1行。这样,数组包含所有A的元素而无其它元素。A元素的一个枚举由图5.1-3中的有向路径指定。从定理5.1-3得出A是可数的,于是定理得证。,iSiAA第五章无限集合图5.1-3第五章无限集合例5上述定理能用来证明下列每一个集合都是可数无限的。(a)N2={〈n1,n2〉|ni∈N}。;(b)In={〈x1,x2,…,xn〉|xi∈I}(整数分量的n重组集合)。(c)Qn={〈x1,x2,…,xn〉|xi∈Q}。;(d)有理系数的所有n次多项式集合。;(e)有理系数的所有多项式集合。;(f)以有理数为元素的所有n×m矩阵集合。;(g)以有理数为元素的任意有限维的所有矩阵集合。第五章无限集合定理5.1-6如果A是有限集合,B是可数集合,那么BA是可数的。证若A是空集,则|BA|=1,是可数的;若A非空,而B有限(包括是?空集),则|BA|=|B||A|有限,因而是可数的。剩下只需证明｜A｜=n＞0,且B是可数无限的情况。设B的无重复枚举函数是g:N→B,对每一正整数k∈N定义集合Fk如下:那么Fk包括所有这样的函数,其象是包含在B的枚举的前k个元素组成的集合中;|Fk|=kn。因为A是有限的,对每一函数f:A→B存在某m∈N,如果取k＞m,那么f∈Fk;所以。但每一集合Fk是有限的因而BA是可数的。证毕。kNkAFB})}1,,2,1,0({)(|{kgAfBffFAk第五章无限集合5.1.3基数c不是所有无限集都是可数无限的,下一定理说明需要新的无限集基数。定理5.1-7实数的子集［0,1］不是可数无限。证设f是从N到［0,1］的任一函数,我们将证明f不是满射函数,从而证明了对［0,1］没有枚举存在。我们把每一x∈［0,1］都表示为无限十进制小数,于是f(0),f(1),f(2)…可表示为第五章无限集合3210232221201312111003020100:)(:)2(:)1(:)0(nnnnxxxxnfxxxxfxxxxfxxxxf第五章无限集合这里xni是f(n)小数展开式的第i个数字。现在我们指定实数y∈［0,1］如下:210yyyy21iy如果xii≠1如果xii=1数y是决定于数组对角线上的数字。显然,y∈［0,1］,然而,y与每一f(n)的展开式至少有一个数字(即第n个数字)不同。因此,对一切n,y≠f(n)。我们得出映射f:N→［0,1］不是一个满射函数。所以f不是［0,1］的枚举。因为f是任意的,这证明。这个定理和证明是康脱给出的。这种证明方法叫“康脱对角线法”,被广泛地应?用于可计算理论。SS0\|]1,0[|第五章无限集合定义5.1-6如果有从［0,1］到集合A的双射函数,那么A的基数是c。选用字母c是根据集合［0,1］常叫做连续统(Continuum)这个事实。第五章无限集合例6(a)｜［a,b］｜=c。这里［a,b］是R中的任意闭区间,a＜b。注意到f(x)=(b-a)x+a是从［0,1］到［a,b］的双射函数,即可证明。(b)｜(0,1)｜=｜［0,1］｜。这两个集合的不同仅在于区间的两端点;为了构造从［0,1］到(0,1)的一个双射函数,我们必须在(0,1)中找出0和1的象而保持映射是满射的。定义集合A是,定义映射f如下:n1,,21,1,021)0()1,0(]1,0[:ffAxxxfnnnf]1,0[)(1211对对第五章无限集合图5.1-4第五章无限集合(c)｜R｜=c。我们定义一个从(0,1)到R的双射函数如下:)1(21)(,)1,0(:xxxxgRg因为前例中的f是从［0,1］到(0,1)的双射函数,而g是(0,1)到R的双射函数,合成函数gf是从［0,1］到R的双射函数。因此｜R｜=c。第五章无限集合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。第五章无限集合定义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|。第五章无限集合(i)等势是集合族上的等价关系,它把集合族划分成等价类,在同一等价类中的集合有相同的基数。因此可以说“基数是在等势关系下集合的等价类的?特征”,或者干脆说“基数是在等势关系下集合的等价类的名称”,这实际上就是基数的一般定义。例如,3是等价类{{a,b,c},{0,1,2},{r,s,t},…}的名称(或特征),是N所属