第八章 函数与集合的势_18222.pptVIP

第八章 函数与集合的势 8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理 |A|≤|B| 与 |A||B| 定义 A、B是两个集合， 若存在f:A→B是单射函数， 则称集合A的势小于等于集合B的势，记为 |A|≤|B|。 若|A|≤|B| 且|A|≠|B|， 则称集合A的势小于集合B的势，记为 |A||B|。 |N| |R| 例4(p98) A={x?R│0≤x≤1}不是可数无限集 定理1 |A||2A| 证：作 g:A→2A， 对于x?A，令g(x)={x}。 显然，g是一个函数，且是单射函数， 故有|A|≤|2A|。 可用反证法证明 |A|≠|2A|。 反证法证明 |A|≠|2A| 若存在φ:A→2A双射， 则?x?A, φ(x) ?2A, 即φ(x)?A。 构造集合M={x│x?A且x?φ(x)}。 由M定义, 有A?M，即M?2A。 因为φ是双射， 所以存在a?A，使得φ(a)=M。 反证法证明 |A|≠|2A| 下面我们来看一个矛盾现象， a是一个元素， M是一个集合，按我们约定：a?M或者a?M，二者有一种且仅有一种可能出现。 若a?M，因为φ(a)=M，所以 a?φ(a)，但由M的定义知 a?M，矛盾。所以 a?M不成立。 若a?M，因为φ(a)=M，所以 a?φ(a)，但由M的定义知 a?M, 又出现矛盾。所以a?M也不成立。 出现这种矛盾现象说明假设有问题， 即不存在A到2A的双射函数，所以|A|≠|2A|。 定理1 |A||2A| 有没有最大势的集合？ 定理2 若|A|≤|B| 且|B|≤|C|， 则 |A|≤|C| 证明：因为|A|≤|B|， 则存在f:A→B是单射， 又|B|≤|C|， 则存在g:B→C是单射。 于是 g°f:A→C也是单射， 故 |A|≤|C|。 定理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与阿列夫?１之间是否也存在其它基数？ 连续统假设断言不存在这样的基数。 此定理告诉我们没有最大势的集合。 此定理告诉我们没有最大势的集合。 此定理告诉我们没有最大势的集合。 此定理告诉我们没有最大势的集合。 从前已经知道连续统假设与集合论公理是一致的，但1963年科恩（Paue Cohen）证明连续统假设的反命题也和集合论公理一致。这样，