离散数学5复习课程课件

离散数学5枚举定义:N的一个初始段{0,1,…,n-1}到(非空)有限集A的一个满射函数f:

{0,1,…,n-1}

A称为A的一个有限枚举;若f是双射则称为有限无重复枚举.定理:集A为非空有限集当且仅当存在A的一个有限无重复枚举.注:N到集A的一个满射函数f:

N

A

称为A的一个无限枚举.基数一般概念(有限集元素数的推广)对任意集合A,B,如果存在A到B的双射(表示为AB)),则称A和B等势,或有相同基数,记为|A|=|B|;如果A与B的一个子集等势(即存在A到B的单射),则|A||B|,特别AB

|A||B|;如果存在A到B的单射但不存在A到B的双射,则|A|<|B|;如果|A||B|且|B||A|,则|A|=|B|(Berstein定理—定理5.2-3).集合上的等势关系是等价关系,同一等价类中的集合有相同基数.(恒等映射为双射,双射的逆,合成仍为双射)可数无限集的概念

记|N|=0,基数为0的集,即与

N

等势的集,称为可数无限集;有限集(包含空集)与可数无限集统称为可数集.(与N的子集等势的集合称为可数集)

例非负偶数的集:A={0,2,4,6,…}={2k|kN}是可数无限集.f:NA,f(x)=2x为双射

A为可数集

|A|0

存在A到N的单射

因恒等函数是可数集A的任意子集到A的单射,故可数集的任意子集是可数集.可数集的性质①A为可数集当且仅当A的元素可列成表(可按{0,1,…,n-1}或N与A元素间的一一对应关系列表),或说A是可枚举的.②A,B为可数集,则AB为可数集.证:若A或B为空集,则|AB|=||=0,结论成立.当A∧B时,AB的元素可列成表(见下两张幻灯片).注:

由归纳法易见:对任意正整数n,A1,,An为可数集A1An为可数集.1,11,21,31,n

2,12,22,32,nm-1,1m-1,2m-1,3m-1,nm,1m,2m,3m,n1,11,21,31,41,5

2,12,22,32,42,53,13,23,33,43,54,14,24,34,44,55,15,25,35,45,5可数集的性质续③可数集A的任意子集B都是可数集.(把A列成表后再划去表中A-B的所有元素即得B的列表)特别,任意二可数集的交集都是可数集.或|B||A|0

④可数个可数集Ai的并集

A=∪iS

Ai都是可数集(∵此并集的双射象是可数集NN的子集).⑤若A为有限集,B为可数集,则

A

到

B的所有函数的集

BA

是可数集.⑤的证明⑤若A为有限集,B为可数集,则

A

到

B

的所有函数的集

BA

是可数集.证:令

A={a1,…,an};

fBA.易见:

f与(f(a1),…,f(an))B…B=Bn一一对应,从而,BA

Bn

是可数集(②的注).可数无限集的性质及0的算术对每个正整数n,n个两两不交的可数无限集的并集是可数无限集,n0=0.可数无限集与其任意n元子集的差集是可数无限集,0-n=0(存在双射

f:N-{0,1,…,n-1}N,其中

f(i)=i-n,iN)对任意正整数n成立：0

n=0NN…NN,(0)n=0,nI+推论:N到m元有限集A的全体函数构成可数无限集AN(∵|AN||N|m=(0)m=0);可数集到有限集的全体函数构成可数集.今后将证:|(N)|=20

>

0,即

N的幂集不是可数的无限集(见定理5.2-9).定理5.2-7:可数无限集是最小无限集:A为无限集|A|0证:只需证任意无限集A中一定存在可数无限子集即可.这一结论可推导如下:A不是有限集

a0(a0A);

A1=A-{a0}不是有限集

a1(a1A1A);

A2=A1-{a1}不是有限集

a2(a2A2A);

n(nI+

An

-{a1,…,an}不是有限集)(否则,An-1,,A1,A是有限集,矛盾)得证:A中含可数无限集{a1,…,an,…,}.§5.1和§5.2的作业布置5.1习题#2;#5(b);提示:I是无限可数的.#7(d).5.2习题#4(a);提示:证明A与(A)的一个子集等势.#10(a);提示:正有理数集合的基数是0.#11(a).提示:利用定理5.1-7和#10(a)的结果.可数无限集的若干实例①一元字母集{a}的所有字符串集A={a}*={an|nN}(∵

令an对应n可证ANA为可数无限集).②正有理数集合Q+是可数无限集(图5.1-1).有理数集合Q是可数无限集:|Q|=2|Q+|+1=20+1=0;同理可证,I为可数无限集.③在平面直角坐标下所有整坐标点集:(A={(x,y)|x,yI}=II)(|I|=2|N|-1=20-1=0-1=0)

|A|=|II|=(0)2=0

④所有整系数一次多项式的集

A={ax+b|aI-{0},bI}

是可数无限集.证

ax+b与a,b一一对应,故

A(I-{0})I,|A|=|I-{0}||I|=00=0.⑤具有可数数结点的所有关系的集A为可数无限集(∵对nN,具有n个结点的所有关系集An的基数等于n元集的叉积的幂集的元数,即|An|=2n2为有限集,故A=∪nNAn为可数集,又A显然不是有限集.)作业中出现的问题§3.5#9由对称和传递性推不出自反性因R对称:x,yRy,xR;因R传递:x,yR∧y,xRx,xR.注意:如果没有x,yR或y,xR,便得不到x,xR.所以,上面的推导得不出自反律:x(x,xR).反例:A={0,1,2},R={0,1,1,0,0,0,1,1}.易见,R是对称的和传递的,但不是自反的(因2,2R,即2R2不成立).§4.3#1

下列函数是否满,单,双射?求集合S的逆象;求函数诱导的等价关系.(i)f:RR+,f(x)=2x,S={1,2}.解:∵f是连续函数且f(-)=0;f()=,

f是满射.

∵f(x)>0(或f(x)=f(y)2x=2yx=y)

f也是单射,从而f是双射.由上式也看出函数f诱导的等价关系是相等关系:1R.f-1({1,2})={0,1}.§4.3#1下列函数是否满,单,双射?求集合S的逆象;求函数诱导的等价关系.(ii)f:IN,f(x)=|x|,S={0,1}.解:f是满射但不是单射(反例:|-1|=|1|).

f诱导的等价关系R是:xRy

f(x)=f(y)

|x|=|y|f-1({0,1})={0,1,-1}.(iii)f:RR+,f(x)=3,S=N.解:函数f显然不是满射(f(R)={3}R+);函数f也不是单射(f(0)=3=f(1));f-1(S)=R.因xy(x,yRf(x)=3=f(y)),故f诱导的等价关系是全域关系:RR.[0,1]不是可数集|[0,1]|=|(N)|>0证:每个数x[0,1]都可唯一表示为无限二进制数:x=0.x1x2

xn其中xn{0,1},nI+.(x1=2x;x2=4(x-x1);x3=23(x-x1-x2);

,x表示不大于x的最大整数).因(N)的每个元A一一对应于无限二进制串(特征函数):x1x2

xn,(若nA,xn=1;否则xn=0),故存在双射f:[0,1](N).下面用反证法证上述双射f不是[0,1]的枚举(从而推出[0,1]不是可数集].若f是枚举,则[0,1]的全部元素可枚举为x1=0.x11x12

x1n

x2=0.x21x22

x2n………xn=0.xn1xn2

xnn………作无限二进制数:y=0.y1y2yn其中nI+(yn=1,若xnn=0;

yn=0,若xnn=1)则nI+(yxn),从而,与y[0,1]相矛盾.

|[0,1]|=|(N)|>0

20>0,§5.1#9与连续统[0,1]等势的集的基数记为c基数是c的集合例子(1)对任意实数a<b,|[a,b]|=c.证:令f:[0,1][a,b],f(x)=(b-a)x+a,x[0,1],则f(x)为单调增加连续函数,并且f(0)=a;f(1)=b,由此推出

f(x)为双射.

(2)|(0,1)|=|[0,1]|=c=|(0,1]|=|[0,1)|证:无限集(0,1)中有可数无限子集A={1/n|n=1,2,…}N,B={0,1}∪A为[0,1]的可数无限子集,故有双射g:BA.令f:[0,1](0,1),f(x)=g(x),当xB;f(x)=x,当x[0,1]-B.则f是双射,得证|[0,1]|=|(0,1)|=c.(3)

由①的证明和②又得:任何长度大于0的(有限)闭,开,半开半闭区间的基数都是

c.(4)

单位圆周的基数也是

c(§5.1#7)

A={x,y|x,yR∧x2+y2=1}|A|=

c证:令f:[0,2)A,f()=sin

,cos

A,易见f(x)为双射函数,从而|A|=|[0,2)|=

c.

(5)

实数集的基数也是c:|R|=c.证:

作函数g:(0,1)R,g(x)=则g为区间(0,1)上的单调减少的连续函数,满足g(0)=+;g(1)=-;和x(x(0,1)g(x)<0).所以g是双射函数,|R|=|(0,1)|=c.基数c的集合的有限重叉积基数也是c证:只须证[0,1][0,1][0,1](§5.2#9)即可.我们知道,[0,1]上的每个数x与无限十进制小数一一对应:

x0.x1x2

xn,xn{0,1,…,9},nI+.叉积[0,1][0,1]的元素可表为

a,b,其中a0.a1a2

an,b0.b1b2

bn为无限十进制小数.令

f:[0,1][0,1][0,1],f(x)=a,b,其中

x0.x1x2

xn,a0.x1x3

x2k-1

,b0.x2x4

x2k

易见f为双射函数,从而得证:

c2=c.集合A是无限集有单射f:AA,f(A)A证:必要性

令

B

={a0,a1,

an}为A的一个可数无限子集,作函数

f:

AA-{a0},f(x)=x,xB;f(an)=an+1,nN,则f显然为双射,且f(A)=A-{a0}是A真子集.充分性若

f:AA为单射,且f(A)为A真子集,则

A

不能为有限集.不然的话,便出现一个有限集的元素个数与它的一个真子集的元素个数相等的矛盾.例:

N是无限集,原因是A={2x|xN}为N的真子集;

Q是无限集,因为N为Q的真子集.Cantor定理:对任意集A成立|A|<|(A)|证:只须证明:从A到(A)存在单射但不存在双射即可.易见:A(A),f(a)={a},aA是单射.下证:若任何函数

g:

A(A)是双射都会导致矛盾.令S={x|xg(x)},则

S

是

A

的子集.若对某aA,g(a)=S,则aS

a{x|xg(x)}

ag(a)

aS上述矛盾证明:对任意aA都有g(a)S.这又与

g:A(A)是满射的假设矛盾.所以,从A到(A)不存在双射.证毕.存在可数无限个无限基数;连续统假设利用Cantor定理可证:存在可数无限个无限基数集:0=|N|<|(N)|(=c)<|((N))|<若A为有限集|A|=n>1,则在|A|和|(A)|之间存在其它基数.Cantor提出连续统假设:在0=|N|和c=|(N)|之间不存在别的基数.连续统假设为无数事实所证明,并且已成功地用于解决许多理论问题.特别由这个假设推出:若无限集

A

满足

0<|A|c，则|A|=c.连续统假设的一个推论

我们证明过:任何长度大于

0

的有限闭,开,半开半闭区间的基数都是

c.

现在任何长度大于

0

的无限(闭,开,