集合的等势 基数的定义 基数的运算 基数的比较

Presentation on theme: "集合的等势 基数的定义 基数的运算 基数的比较"— Presentation transcript:

1 集合的等势 基数的定义 基数的运算 基数的比较
第12章集合的基数 集合的等势 基数的定义 基数的运算 基数的比较

2 12.2 集合的等势 定义12.2.1 对集合A和B，如果存在从A到B的双射函数，就称A和B等势，记作A≈B
注意：证明等势即构造双射 􀂆等势是等价关系，可以用来分类 􀂄自反性：A≈A IA:A→A双射 􀂄对称性：若A≈B，则B≈A f:A→B双射⇒f-1:B→A双射 􀂄传递性：若A≈B且B≈C，则A≈C f:A→B, g:B→C双射⇒gof:A→C双射

3 集合的等势 例1 N ≈N偶，N ≈N奇 f: N→ N偶, f(n)=2n；g: N→ N奇, g(n)=2n+1 例2 Z≈N.
f: Z→N, 0, n=0 f(n) = 2n, n>0 2|n|-1, n<0 例3 N≈N×N. (课本中图11.1.1) f:N×N→N, f(<i,j>)=(i+j)(i+j+1)/2 + i

4 例4 N≈Q 证明:因为任何有理数都可以表示成分数，即∀m ∈Z, ∀n ∈ N-{0}, m/n，从而找出全体既约分数，它们表示出了全体有理数，并编号。f:N→Q, f(n)=编号[n]的既约分数. (课本中图12.2.1)

5 集合的等势 例5 R≈R+. f: R→R+，f(x)=ex 例6 (0, 1)≈R f: (0,1)→R, ∀xε(0,1)
f(x)=tan(x-1/2)π 例7 [0, 1]≈(0, 1) f: [0,1]→(0,1), 1/2, x=0 f(x) = 1/(n+2), x=1/n, n∈N-{0} x, 其他 注：无限集合可以和它的真子集等势，但有限集合不能

6 结论 无限集合可以和它的真子集等势，但有限集合不能 N ≈Z ≈Q ≈N×N (0,1) ≈[0,1] ≈R

7 P(A)≈A2 证明: 令f:P(A)→A2, f(B)=χB, 其中χB是B∈P(A)的特征函数, χB :A→{0,1}, χB(x)=1 ⇔ x∈B. (1) f是单射, 设B1,B2⊆A且B1≠B2, 则 f(B1)= χB1(x)≠ χB2(x)=f(B2), 故χB1 ≠ χB2. (2) f是满射. 任给χB :A→{0,1}, 令 B={x|x∈A且χB(x)=1}⊆A, 则f(B)= χB

8 集合的等势 定理12.2.3(Cantor康托尔定理) (1) ¬N≈R (2) 对任意的集合A, ¬ A≈P(A)
证明: (1) (反证) 假设N≈R≈[0,1], 则存在f:N→[0,1]双射, 对∀n∈N, 令f(n)=xn+1, 于是 ran(f)=[0,1]= {x1,x2,x3,…,xn,…} 将xi表示成如下小数:

9 ¬N≈R x1=0.a11 a21 a31…… x2=0.a12 a22 a32…… x3=0.a13 a23 a33…… ┇
xn=0.a1n a2n a3n…… 其中0≤aji≤9, i,j=1,2,…

10 ¬N≈R 选一个[0,1]中的小数 x=0.b1b2b3……使得 (1) 0≤bj≤9, i=1,2,… (2) bn ≠ ann
由x的构造可知, x∈[0,1], x∉{x1,x2,x3,…,xn,…} (x与xn在第n位上不同). 这与[0,1]={x1,x2,x3,…,xn,…}矛盾!

11 ¬N≈R 对角化方法 x1=0.a11 a21 a31…… x2=0.a12 a22 a32…… x3=0.a13 a23 a33…… ┇
xn=0.a1n a2n a3n……ann…

12 (2) 对任意的集合A, ¬ A≈P(A) 证明: (反证) 假设存在双射f:A→P(A), 令 B = { x| x∈A∧x∉f(x) }
则B∈P(A). 由f是双射, 设f(b)=B, 则 b∈B⇔b∉f(b) ⇔b∉B, 矛盾!

13 12.3 有限集合与无限集合 自然数定义 对任意的集合A, 可以定义集合A+=A∪{A}, 把A+称为A的后继, A称为A+的前驱
集合0=∅是一个自然数。若集合n是一个自然数，则集合n+1=n+也是 一个自然数 列出自然数 0=∅ 1=0+=0∪{0}={0} 2=1+=1∪{1}={0, 1} 3=2+=2∪{2}={0, 1, 2} …

14 有限集合与无限集合 定义12.3.1 集合A是有限集合，当且仅当存在n∈N, 使n≈A.
集合A是无限集合，当且仅当A不是有限集合，即不存在n∈N, 使n≈A. 结论 􀂄不存在与自己真子集等势的自然数(鸽巢原理) 􀂄不存在与自己真子集等势的有限集合 􀂄任何与自己真子集等势的集合是无限集合.例N, R 􀂄任何有限集合只与唯一的自然数等势

15 12.4 集合的基数 集合的基数就是集合中元素的个数
定义9.6.1 如果存在n∈N，使集合A与集合{x|x∈N∧x<n}={0，1，2，…，n-1}的元素个数相同，就说集合A的基数是n，记作#(A)=n或|A|=n或card(A)=n 空集Φ的基数是0 定义9.6.2 如果存在n∈N，使n是集合A的基数．就说A是有限集合．如果不存在这样的n，就说A是无限集合

16 集合的基数 对任意的集合A和B，它们的基数分别用 card(A)和card(B)表示，并且card(A)=card(B)⇔A≈B
对有限集合A和n∈N, 若A≈n, 则card(A)=n (有限基数) N的基数：card(N)=ℵ0 (无限基数) R的基数：card(R)=ℵ1 (无限基数)

17 基数的运算 对任意的基数k和l, 若存在集合K和L, card(K)=k, card(L)=l, 则
(1)若K⋂L=∅, k+l=card(K⋃L) (2)k·l=card(K×L) (3)kl=card(LK), 其中LK是从L到K的函数的集合 􀂆对集合K, L, P, M, 如果K≈P且L≈M, 则K×L≈P×M且LK ≈MP. 如果同时成立K⋂L=∅且P⋂M=∅, 则K⋃L≈P⋃M

18 基数的运算 例7 k0=card(∅K)=card({∅})=1 0k=card(K∅)=card(∅)=0
00=card(∅∅)=card({∅})=1 例8 对任意集合A, 有card(P(A))=2card(A)

19 基数的运算 例9 对任意的n∈N, 有 (1)n+ℵ0=ℵ0 (2)n·ℵ0=ℵ0 (3)ℵ0+ℵ0=ℵ0 (4)ℵ0·ℵ0=ℵ0
证明: (1)令L=N, K={a1, …, an}, 且对于i=1, 2, …, n有ai∉N. 则card(L)=ℵ0, card(K)=n, K⋂L=∅. 于是K⋃L={a1, …, an, 0, 1, 2, …}. 构造双射函数f: K⋃L→N. 则K⋃L≈N, 且 n+ℵ0 =card(K)+card(L)=card(K⋃L)=card(N)=ℵ0

20 基数的运算 定理12.5.1 对任意的基数k、l和m，有 (1) k+l= l+k, k·l=l·k
(2) k+(l+m)=(k+l)+m, k· (l·m)=(k·l) ·m (3) k· (l+m)=k·l+k·m (4) k(l+m) =K l ·km (5) (k·l)m = km ·lm (6) (K l)m= k(l·m) 另外，对任意的基数k，有 k+0 =k, k·0=0, k·1=k, k·2=k+k 注意：对任意基数的运算的性质，与自然数的运算性质一致

21 基数的比较 定义 对集合K和L，card(K)=k, card(L)=l, 如果存在从K到L的单射函数，则称集合L优势于K，记作K≤L，且称基数k不大于基数l，记作k≤l 定义 对基数k和l，如果k≤l且k≠l，则称k小于l，记作k<l 例: 对任意的自然数n，n≤ℵ0

22 基数的比较 例10 对任意的基数k，有k<2k
证明：对基数k，存在集合K，使得card(K)=k. 则有card(P(K))=2k. 构造函数f: A→P(A), f(x)={x}, 则f是单射的，进而k≤2k. 又¬K≈P(K)，k≠2k 因此k<2k 注意：不存在最大的基数

23 基数的比较 定理12.6.1 对任意的基数k，l和m，有 (1)k≤k (2)若k≤l且l≤m，则k≤m
(3)若k≤l且l≤k，则k=l(Schroder-Bernstein施罗德-伯恩斯坦定理) (4)k≤l或l≤k

24 基数的比较 例11 R≈N2 证明：先证R≤N2. 因(0,1)≈R, 即证(0, 1)≤N2 H: (0,1)→(N→2) 单射,
∀z∈(0,1)的二进制小数, H(z):N→{0,1}, H(z)(n)=z的二进制表示的第n+1位小数. 再证N2≤R.因[0,1]≈R, 即证N2≤[0, 1] (2) G: (N→2)→[0,1] 单射, ∀f:N→2, G(f)=0.f(0)f(1)f(2) …(第n+1位小数是f(n)). 􀂆由此例可得 ℵ1=card(R)=card(N2)=card(P(A))=2ℵ0 注意：对任意集合A，有P(A)≈A2

25 举例 (1) z= 时 H(z)(0)=1; H(z)(1)=0; H(z)(2)=1; H(z)(3)=1; H(z)(4)=1; … (2) 特征函数f(0)=1, f(1)=0, f(2)=1, f(3)=0,… 可以得到十进制小数f=0.1010…∈[0, 1]

26 基数的比较 定理12.6.2 对任意的基数k，l和m，如果k≤l，则 (1) k+m≤l+m (2) k·m≤l·m (3) km ≤lm
(4) 若k≠0或m≠0，mk ≤ml 例2ℵ0=1·2ℵ0≤ℵ0·2ℵ0≤2ℵ0· 2ℵ0=2ℵ0+ℵ0=2ℵ0 所以ℵ0·2ℵ0=2ℵ0

27 基数的比较 结论 对基数k和l，如果k≤l、k≠0，l是无限基数，则 k+l=k·l=l=max(k, l)
对任意的无限基数k，kk =2k 对任意的无限集合K，N≤K 对任意的无限基数k，ℵ0≤k (ℵ0是最小的无限基数) 对任意的基数k，k < ℵ0当且仅当k是有限基数 有限集合的子集一定是有限的

28 12.7 可数集合与连续统假设 定义12.7.1 对集合K，如果card(K)≤ℵ0,则称K是可数集合
亦可描述为：如果集合K是有限的或与N等势，就称K为可数集合 例 对n∈N，n是有限可数集合 􀂄N，Z，Q是无限可数集合 􀂄R是不可数集合

29 可数集合 性质 􀂄可数集的任何子集是可数集 􀂄两个可数集的并集和笛卡儿积是可数集 􀂄若K是无限集合，则P(K)是不可数的
􀂄可数个可数集的并集是可数集 (或者，若A是可数集，A的元素都是可数集，则⋃A是可数集)

30 连续统假设 已知的基数按从小到大的次序排列为： 0，1，…，n，…，ℵ0，ℵ1，2ℵ1 ，…
连续统假设断言：不存在基数k，使得 ℵ0<k<ℵ1=2ℵ0 该假设至今未得到证明. 但是，据证，根据现有的公理系统，既不能证明它是对的，也不能证明它是错的