函数与集合的势.ppt

1/51,第八章 函数与集合的势,8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理,2/51,哪个集合的元素多？,A={1,2,3,4,5, ⋯} B={2,4,6,8,10, ⋯},可选答案： A多 一样多 不能确定,3/51,伽利略的困惑,早在1638年，天文学家伽利略发现在一定意义下，正整数的平方数集合 S1={1, 4, 9, 16, 25, ⋯} 和正整数集合 S2={1, 2, 3, 4, 5, ⋯} 的元素一样多 因为，任给一个正整数n∊S2，则必有唯一的一个n2∊S1，这是一个一一对应，说明S1与S2所含不同元素的数目相等 但是，另一方面 S1又是S2的真子集4/51,势(cardinality),规定用 |A| 来表示一个集合A所含有的不同元素的多少， 称为集合A的势(或称基数)显然， | Ø |=0,注意： 一般规定card(A)表示集合A的势，而在A是有限集时用|A|表示，本书有限集情况较多，为统一起见用|A| 表示5/51,|A|=|B|,定义1 A，B是两个集合， 若存在f:A→B，且 f是双射函数， 则称集合A与集合B的势相等，记为 |A|=|B|,6/51,有限集、无限集,定义2 A是一个集合， 若存在n∊N，使得 |A|=|{0,1, ⋯,n-1}|， 则称集合A是有限集，并记 |A|=n 如果A不是有限集，它就是无限集。

7/51,定理1 自然数集N是无限集证明：用反证法，设存在n∊N，使得 |N|=| {0, 1, 2, ⋯, n-1} | 令 g: {0, 1, 2, ⋯, n-1} →N是双射 设 k=1+max{g(0), g(1), ⋯,g(n-1)}， 显然，k∊N，但对于任意的x∊{0, 1, 2, ⋯, n-1}， g(x) ≠k， 因此g不是满射函数，与 g是双射函数矛盾 矛盾说明不存在n，使得|N|=| {0, 1, 2, ⋯, n-1} | 所以，N不是有限集, N是无限集8/51,阿列夫零 0,定义3 A是一个集合，若|A|=|N|， 则称A为可数无限集，记 |A|= 0 (读作“阿列夫零”, 是康托引入的)一个可数无限集A可以表示为 A={a1, a2, ⋯,an, ⋯},9/51,例 偶数与自然数一样多,B={n∊N│存在k∊N，n=2k} 显然， B是偶数集， 它是自然数集N的真子集 令 g:N→B，对于任意的n∊N， g(n)=2n 不难证明 g是双射函数，也即有 |B|=|N|= 0,10/51,例1 Z是可数无限集0, -1, 1, -2, 2, -3, 3, -4, 4, …,11/51,例2 两个可数无限集A和B 的 A∪B仍然是可数无限集,解：设 A={a1, a2, …, an, …} B={b1, b2, …, bn, …} 考察元素列： a1, b1, a2, b2, …,an, bn,… 消去重复出现的元素，可以建立N中元素与上面序列消去重复出现的元素后剩下的元素安排的次序所建立的元素之间的一一对应，也即 |A∪B|=0,12/51,例3 两个可数无限集A和B 的A×B仍然是可数无限集,,解：设 A={a1, a2, …, an, …}, B={b1, b2, …, bn, …},先把 A×B中的元素按一定规则安排出来，见图8.1，每一个有序对(i,j) 表示有序对(ai,bj)，按箭头所指方向把 A×B中的元素排成一列，对于任意的(i,j) ∊N×N，有关系(i≥1,j≥1):,图8.1 两个可数无限集的排列图,13/51,定理2 无限集存在可数子集,A是一个任意无限集，则A中存在子集A’， |A’|=0,证明：任取 A中的一个元素，记a0∊A’； 在A ̶̶ {a0}中任意取一个元素，记a1∊A’， …，以此类推。

若A’⊇{a0, a1, …,an-1}，在A ̶ {a0, a1, …,an-1}中任取一个元素，记为an∊A’ 因为A是无限集，以上工作可以一直进行下去，因此建立函数f： 对应于任意的n∊N，f(n)=an f是一一对应，也即|A’|=0，且 A⊇A’14/51,定理3 无限集存在等势的真子集,A是无限集当且仅当 A中存在真子集A’，使 |A’|=|A|分析： A’’={a1,a2,a3,…} ⊆ A A= (A-A’’) ∪{a1,a2,a3,a4,…} A’= (A-A’’) ∪{a2,a3,a4,…},15/51,定理3 A是无限集当且仅当A中存在真子集A’，使 |A’|=|A|证明：A是无限集， 则A 中有子集A”, 使得|A”|=0 设A”={ a1，a2，a3, … } 令 A’=A ̶ {a1}，则 A’是A的真子集 作 f: A→A’，,显然, f是一一对应，即 |A|=|A’|16/51,定理3 A是无限集当且仅当A中存在真子集A’，使 |A’|=|A|证明：  用反证法， 若A不是无限集， 则 A是有限集，不妨设|A|=n， 并设A={a1,a2, …,an}。

则A的任何真子集与A之间不存在一一对应，与条件矛盾 故 A是无限集17/51,例4 A={x∊R│0≤x≤1}不是可数无限集,证：若|A|=0， 则存在g: N→A， g是双射 不失一般性，设 g(0)=0.a00a01a02a03a04… g(1)=0.a10a11a12a13a14… g(2)=0.a20a21a22a23a24… g(3)=0.a30a31a32a33a34… g(4)=0.a40a41a42a43a44… … …,g(0)=0.a00a01a02a03a04… g(1)=0.a10a11a12a13a14… g(2)=0.a20a21a22a23a24… g(3)=0.a30a31a32a33a34… g(4)=0.a40a41a42a43a44… … …,作：b=0.b0b1b2b3b4…,显然, 如果aii ≠bi, 则 g(i) ≠b,19/51,例4 证(续),作：b=0.b0b1b2…，其中,显然，0≤b≤1，即b∊A，但 ∀i∊N，g(i) ≠b， 这是因为∀i∊N，aii ≠bi 这与g是双射矛盾，矛盾说明|N|≠|A| 即A不是可数无限集。

20/51,例5,设 A={x∊R│0x1}，则|A|=|R|， 其中R 是实数集 解：令 g:A→R， ∀x∊A，g(x)=cot(πx) 则 g是一个双射， 故有 |R|=|A|注意: cot(0)与cot(π)没有定义, 书上有误.,21/51,例6,设A={x∊R│0 ≤ x ≤ 1}，B={x∊R│0 ≤ x 1} 求证： |A|=|B|证明：作 g:A→B， g(0)=0,,显然，g是双射，所以|A|=|B|22/51,例,用势相等的定义证明下面两集合等势 A={x∊R│0≤x≤1} A={x∊R│0x≤1} 其中 R是实数集23/51,例 设A,B,C,D为四个集合若 |A|=|B|, |C|=|D|, 且 A∩C=Ø, B∩D=Ø 则 |A∪C|=|B∪D|,证： 因为 |A|=|B|，故存在A到B双射函数f: A→B,又因 |C|=|D|，故存在C到D双射函数g: C→D 现在定义从A∪C到B∪D的函数h如下： 对于任意元素x∊ A∪C,,显然，由交集为空集的条件知，h(x)有唯一定义容易说明h(x)为双射函数24/51,第八章 函数与集合的势,8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理,25/51,|A|≤|B| 与 |A||B|,定义 A、B是两个集合， 若存在f:A→B是单射函数， 则称集合A的势小于等于集合B的势，记为 |A|≤|B|。

若|A|≤|B| 且|A|≠|B|， 则称集合A的势小于集合B的势，记为 |A||B|26/51,|N| |R|,例4(p98) A={x∊R│0≤x≤1}不是可数无限集,27/51,定理1 |A||2A|,证：作 g:A→2A， 对于x∊A，令g(x)={x} 显然，g是一个函数，且是单射函数， 故有|A|≤|2A| 可用反证法证明 |A|≠|2A|28/51,反证法证明 |A|≠|2A|,若存在φ:A→2A双射， 则∀x∊A, φ(x) ∊2A, 即φ(x)⊆A 构造集合M={x│x∊A且x∉φ(x)} 由M定义, 有A⊇M，即M∊2A 因为φ是双射， 所以存在a∊A，使得φ(a)=M29/51,反证法证明 |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|。

30/51,定理1 |A||2A|,有没有最大势的集合？,31/51,定理2,若|A|≤|B| 且|B|≤|C|， 则 |A|≤|C|,证明：因为|A|≤|B|， 则存在f:A→B是单射， 又|B|≤|C|， 则存在g:B→C是单射 于是 g∘f:A→C也是单射， 故 |A|≤|C|32/51,定理3（伯恩斯坦定理）,A和B是两个任意集合 若 |A|≤|B| 且 |B|≤|A| 则 |A| = |B|,33/51,伯恩斯坦（ Sergi Natanovich Bernstein，1880—1968）,原苏联数学家 1880年3月6日生于敖德萨； 1968年10月26日卒于莫斯科 1893年毕业于法国巴黎大学， 1901年又毕业于巴黎综合工科学校 1904年在巴黎获数学博士学位， 1907年成为教授 1914年在哈尔科夫又获纯粹数学博士学位在概率论方面伯恩斯坦最早提出并发展了概率论的公理化结构，建立了关于独立随机变量之和的中心极限定理 ──摘自《中国大百科全书》（数学卷）,34/51,定理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|35/51,定理 (康托) 1= ρ (0),连续统——实数集即直线上点的集合 1——连续统的势（大小） 康托定理证明连续统势等于自然数集的幂集的势,证明详见董晓蕾，曹珍富编著《离散数学》，机械工业出版社，2009年，第143页,36/51,连续统假设,如果集合Ａ有ｎ个元素，ρ(A)有２n个元素， 在|Ａ|与ρ(A)之间存在着其它基数（势） 于是，康托提出: 在阿列夫零0与阿列夫１之间是否也存在其它基数？ 连续统假设断言不存在这样的基数37/51,第八章 函数与集合的势,8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理,38/51,鸽巢原理,任意取出3个自然数，至少有两个数是同奇偶的 任意11个人各自写出一个幸运数字，则至少有两人写出的幸运数字相同。

任意13个人说出自己的生日星座，则至少有两人的生日星座相同39/51,鸽巢原理,如果有几个鸽子住在几个鸽巢中，鸽子的数目比鸽。