《2022年2022年离散数学刘任任课后答案习题 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学刘任任课后答案习题 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12 习 题 四1试证明，自然数集N与奇自然数集D等势. 证明：定义DN:如下 : 1, 12)(nnn. 显然是双射。故ND。2设, ,a bxR axb a bR，R为实数集 . 试证明：,a bR. 证明：定义Rbaf),(:如下 : )/()2/)()(abbaxtgxf显然f是双射。故Rba),(。3利用“抽屉原则”证明：（1）从小于201 的正整数中任取101 个数，其中必有一个数能整除另一个数. （2）任意 52 个整数中，必有两个数之和能被100 整除或者两个数之差能被100 整除 . 证明： (1). 设 A=1,2, ,200 。已知任何正整数m都可以写成lk2(其中k为非
2、负整数，l是正奇数 )。显然 A 中只有 100 个奇数，由于要从A 中取出 101 个数, 故这 101 个数都写成lk2的形式后 , 至少有两个数所对应的奇数l是相同的，而对应的k都是非负整数。故对应于k小的数可整除对应于k大的另一个数。(2) 设有 52 个整数5221,aaa。若存在521ji, 使jiaa, 则)(100jiaa。否则不妨设5221aaa。令51, 1,52iaabii(1) 51, 1,52jaacjj(2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
3、 1 页，共 5 页 - - - - - - - - - 13 假设结论不成立, 则jicb ,均不能被100 整除。设 100 除ib余数为ir, i=1, ,51 ; 100 除ic余数为is, j=1,51 ，则 1ir,is=99 。由于 (1), (2)式共有 102 个, 因此，余数也有102 个。故必有i, j 使得jirr(1=ij=51) (a-1) 或jisr(1=ij=51) (b-1) 或jiss(1=ij=51) (c-1) 即jjiikaakaa100)(100)(5252(a-2) 或jjiikaakaa100)(100)(5252(b-2) 或jjiikaaka
4、a100)(100)(5252(c-2) 于是有)(*100)(ijjikkaa(a-3) )(*100)(ijjikkaa(b-3) )(*100)(jijikkaa(c-3) 此与假设矛盾。故本题得证。4证明定理4. 2. 2 和定理 4. 2. 3. 证明 : 证明定理4.2.3。(1) 对任意集合A, 因为 AA, 所以 |A|=|A| 。(2) 若|A|=|B| , 则 AB, 即存在双射BA:，于是AB:1存在且为双射 , 故 BA, 即 |B|=|A| 。(3) 若 |A|=|B|,|B|=|C|, 则存在双射BA:, CB:名师资料总结 - - -精品资料欢迎下载 - - -
5、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 14 于是CA:是双射，因此，AC 。故 |A|=|C|。再证定理 4.2.3。(1) 令AA:,axxx,)(。于是是单射。故 |A|A|. (2) 设|A|B| 且 |B|A, 则存在单射 : BA:, AB:, 若不是满射 , 则可推得不是单射 , 矛盾。故必为双射 , 即|A|=|B|。(3) 设 |A|B| 且|B|C|, 则存在单射BA:, CB:, 显然 , CA:是单射。故|A|C|。5设A和B是两个集合，B. 试证明
6、：AB当且仅当存在A到B的满射 . 证明 : 必要性。设 |B|A| , 则存在单射AB:。(1)若是满射 , 则是双射，因此BA:1也是满射。(2)若不是满射 , 不妨设 B,任取Be，令BA:如下：中无象源在若（使若存在aab)B,b)(eba显然，是A到B的满射。充分性。设BA:是满射 , 则BA)(，于是 |B|=|(A)|A|, 故|B|A|。6设A是一个无限集，试证明：存在A的一个真子集B，使得AB. 证明 : 先证任何无限集均包含一个可数子集。设 A 为无限集 , 任取Aa1, 因 A 无限 , 故存在12aAa, 名师资料总结 - - -精品资料欢迎下载 - - - - - -
7、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 15 如此下去 , 有,21aa, 显然,211aaA是 A 的可数子集。令,1aAB则AB。再证存在双射BA:。 令11)(Axxaxaxii显然，是 A 到 B 的双射。故结论成立。7试证明下列集合是可数集：（1）,16, 9, 4, 12nA；（2）,64,27, 8, 13nA；（3）,3 ,27,12, 32nA；（4）,/1 , 3/1 ,2/1 , 1nA. 证明：(1) 令,)(21nnNn(2) 令,)(32nnNn(3) 令
8、,3)(23nnNn(4) 令,/1)(4nnNn8试证明：任何一个无限集必含可数子集. 证明：题 6 已证。9试证明：NN是可数集，N为自然数集 . 证明：将NN 的元素如下排列, 设NN。（1）按yx的值由小到大排列, （2）若vuyx, 则 和 中x ,u的 较 小 者 先 排 , 这 样 就 有, . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 16 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -