函数与集合的势.ppt

定理3（伯恩斯坦定理） A和B是两个任意集合。 若 |A|≤|B| 且 |B|≤|A| 则 |A| = |B| 伯恩斯坦（ Sergi Natanovich Bernstein，1880—1968） 原苏联数学家。 1880年3月6日生于敖德萨； 1968年10月26日卒于莫斯科。 1893年毕业于法国巴黎大学， 1901年又毕业于巴黎综合工科学校。 1904年在巴黎获数学博士学位， 1907年成为教授。 1914年在哈尔科夫又获纯粹数学博士学位。 “在概率论方面伯恩斯坦最早提出并发展了概率论的公理化结构，建立了关于独立随机变量之和的中心极限定理。” ──摘自《中国大百科全书》（数学卷） 定理4 有理数集Q是可数无限集 证明：作f: N→Q ，?x?N, f(x)=x。 显然 f是单射，则|Q|≥|N|。 又Z是整数集，我们知道 |Z|=|N| 且 |Z×Z|=|N|。 作g:Q→Z×Z, 对?x=q/p?Q, 其中p,q?Z, 互质, p0，令 g(x)=g(q/p)=(q,p) 则 g也是单射，所以 |Q|≤ |Z×Z|=|N|。 故由伯恩斯坦定理知，|Q|=|N|。 定理 (康托) ?1= ρ (?0) 连续统——实数集即直线上点的集合。 ?1——连续统的势（大小） 康托定理证明连续统势等于自然数集的幂集的势 证明详见董晓蕾，曹珍富编著《离散数学》，机械工业出版社，2009年，第143页 连续统假设 如果集合Ａ有ｎ个元素，ρ(A)有２n个元素， 在|Ａ|与ρ(A)之间存在着其它基数（势）。 于是，康托提出: 在阿列夫零?0与阿列夫?１之间是否也存在其它基数？ 连续统假设断言不存在这样的基数。 第八章 函数与集合的势 8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理 鸽巢原理 任意取出3个自然数，至少有两个数是同奇偶的 任意11个人各自写出一个幸运数字，则至少有两人写出的幸运数字相同。 任意13个人说出自己的生日星座，则至少有两人的生日星座相同。 鸽巢原理 如果有几个鸽子住在几个鸽巢中，鸽子的数目比鸽巢数目多，那么一定会有一个鸽巢至少住有两只鸽子。 鸽巢原理 设D和S是两个有限集，且 |D||S| 那么对于任意一个f:D→S，一定存在d1≠d2?D，使得 f(d1)=f(d2)。 鸽巢原理 设D和S是两个有限集，且 |D|2|S| 那么对于任意一个f:D→S，一定存在三个不同元素d1,d2,d3?D，使得 f(d1)=f(d2) =f(d3) 。 鸽巢原理 设D和S是两个有限集，记 i=[|D|/|S|]。 这里，[x]表示不小于x的最小整数。 即有： |D|（i-1）|S| 。 那么对于任意的f:D→S，D中必存在 i个不同元素 d1,d2,…di，使得 f(d1)=f(d2)=…=f(di)。 狄利克雷（G. Lejeune Dirichlet 1805.2.13——1859.5.5 ） 德国数学家、力学家。 柏林大学教授。 贡献涉及数学的各个方面，其中以数论、分析和位势论最著名，并是解析数论的创始人。他解决了n=5的费马大定理(x5+y5=z5没有非平凡整数解)。 鸽巢原理(Pigeonhole Principle)最早由狄利克雷在1834年提出的(“drawer principle”抽屉原理 )。 例1证明在任意选取的 n+1个整数中，存在两个整数，它们的差能被 n整除。 证明：设x1，x2，…，xn+1是任意选取的n+1个整数。任何整数被n 除的余数共有n个数： 0，1，2，…，n-1。 n+1个任意整数算 n+1个“鸽子”，任何整数被n 除有n 个可能余数算 n个“鸽巢”，这 n+1只“鸽子”飞到 n个“鸽巢”中，一定有一个“鸽巢”至少有两只“鸽子”，设为xi，xj (1≤ij≤n+1)。 xi与xj被n除余数相同，所以 n 整除 xi－xj。 例2证明在小于或等于2n 的任意 n+1个整数中，存在两个正整数，使得它们是互质的。 命题：相继的两个正整数是互质的。 证明： 设