最新离散数学5教学讲义ppt.ppt

《最新离散数学5教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学5有限集的等价条件定理:集A为非空有限集当且仅当存在n>0和双射f:A{0,1,…,n-1}.(此陪域称为N的一个初始段)证:若A为非空有限集,令

2、A

3、=n>0;n-1N;若A={a0,a1,…,an-1}.定义f:A{0,1,…,n-1},f(ai)=i,i=0,1,…,n-1,则f为双射.反之,若存在上述双射,则f-1:{0,1,…,n-1}A是双射,由此推知A={f-1(0),f-1(1),…,f-1(n-1)},f-1(i)为1元集且两两不同,从而

4、A

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

6、1}A称为A的一个有限枚举;若f是双射则称为有限无重复枚举.定理:集A为非空有限集当且仅当存在A的一个有限无重复枚举.注:N到集A的一个满射函数f:NA称为A的一个无限枚举.1,11,21,31,n2,12,22,32,nm-1,1m-1,2m-1,3m-1,nm,1m,2m,3m,n1,11,21,31,41,52,12,22,32,42,53,13,23,33,43,54,14,24,34,4

7、4,55,15,25,35,45,5可数集的性质续③可数集A的任意子集B都是可数集.(把A列成表后再划去表中A-B的所有元素即得B的列表)特别,任意二可数集的交集都是可数集.或

8、B

9、

10、A

11、0④可数个可数集Ai的并集A=∪iSAi都是可数集(∵此并集的双射象是可数集NN的子集).⑤若A为有限集,B为可数集,则A到B的所有函数的集BA是可数集.⑤的证明⑤若A为有限集,B为可数集,则A到B的所有函数的集BA是可数集.证:令A={a1,…,an};fBA.易见:f与(f(a1),…,f(an))B…B=Bn一一对应,从而,BABn是可数集(②的注).可

12、数无限集的性质及0的算术对每个正整数n,n个两两不交的可数无限集的并集是可数无限集,n0=0.可数无限集与其任意n元子集的差集是可数无限集,0-n=0(存在双射f:N-{0,1,…,n-1}N,其中f(i)=i-n,iN)对任意正整数n成立：0n=0NN…NN,(0)n=0,nI+推论:N到m元有限集A的全体函数构成可数无限集AN(∵

13、AN

14、

15、N

16、m=(0)m=0);可数集到有限集的全体函数构成可数集.今后将证:

17、(N)

18、=20>0,即N的幂集不是可数的无限集(见定理5.2-9).定理5.2-7:可数无限集是最小无限集:A为无限集

19、

20、A

21、0证:只需证任意无限集A中一定存在可数无限子集即可.这一结论可推导如下:A不是有限集a0(a0A);A1=A-{a0}不是有限集a1(a1A1A);A2=A1-{a1}不是有限集a2(a2A2A);n(nI+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);提示:正有理数集合的基

22、数是0.#11(a).提示:利用定理5.1-7和#10(a)的结果.可数无限集的若干实例①一元字母集{a}的所有字符串集A={a}*={an

23、nN}(∵令an对应n可证ANA为可数无限集).②正有理数集合Q+是可数无限集(图5.1-1).有理数集合Q是可数无限集:

24、Q

25、=2

26、Q+

27、+1=20+1=0;同理可证,I为可数无限集.③在平面直角坐标下所有整坐标点集:(A={(x,y)

28、x,yI}=II)(

29、I

30、=2

31、N

32、-1=20-1=0-1=0)

33、A

34、=

35、II

36、=(0)2=0④所有整系数一次多项式的集A={ax+b

37、aI-{0},bI}是可数无限集.证ax+

38、b与a,b一一对应,故A(I-{0})I,

39、A

40、=

41、I-{0}

42、

43、I

44、=00=0.⑤具有可数数结点的所有关系的集A为可数无限集(∵对nN,具有n个结点的所有关系集An的基数等于n元集的叉积的幂集的元数,即

45、An

46、=2n2为有限集,故A=∪nNAn为可数集,又A显然不是有限集.)作业中出现的问题§3.5#9由对称和传递性推不出自反性因R对称:x,yRy,xR;因R传递:x,yR∧