《集合论与图论》第11讲1 第11讲基数 内容提要 ?等势, 优势, 劣势, 绝对优势, 绝对劣势 ?Cantor定理, Schr?der-Bernstein定理 ?基数(势), ? 0 , ? ?有穷集, 无穷集, 可数集(可列集) ?基数运算 《集合论与图论》第11讲2 两个基本过程 ?匹配(matching): 多少,大小(基数)----双射 {a} → {0}=1 {a,b} → {0,1}=2 {a,b,c} → {0,1,2}=3… ?计数(counting): 首尾,先后(序数)----良序 0→1→2→3→… a→b c→b→a …… 《集合论与图论》第11讲3 无穷之迷 ?许多关于无穷的悖论 ?无穷是否“存在”? 人是否“理解”无穷? ?无穷大, 无穷小, 无限可分性 ?极限 ?有穷与无穷的区别? 《集合论与图论》第11讲4 芝诺悖论(Zeno’s paradox) ?芝诺悖论: 阿基里斯(Achilles)追不上乌龟 ?阿基里斯比乌龟快一倍 ?乌龟在阿基里斯前面起跑 《集合论与图论》第11讲5 等势(same cardinality) ?等势: A≈B ??双射f:A→B ?优势,劣势: A≤?B ??单射f:A→B ? B比A优势? A比B劣势 ?绝对优势,绝对劣势: A<?B ? A≤?B ∧ A≈B ? B比A绝对优势? A比B绝对劣势 《集合论与图论》第11讲6 等势关系是等价关系 ?自反: A≈A I A :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双射? g○f:A→C双射 《集合论与图论》第11讲7 证明等势?构造双射 ?直接构造双射: ?N×N≈N, R≈(0,1), [0,1]≈(0,1), (0,1)≈2 N ?P(A)≈2 A , A→(B→C)≈(A×B)→C ?间接构造双射: ?传递性: A≈B ∧ B≈C ? A≈C ?S-B定理: A≤?B ∧ B≤?A ? A≈B 《集合论与图论》第11讲8 R≈(0,1) 《集合论与图论》第11讲9 [0,1]≈(0,1) ?N→N-{0,1,2}, {-2,-1}∪N→N 012345678 012345678 012345678 012345678 -1 -2 《集合论与图论》第11讲10 [0,1]≈(0,1) 《集合论与图论》第11讲11 (0,1)≈2 N ?N 0, 1, 2, 3, … S 1 0, 1, 1, 0, … S 2 1, 0, 1, 0, … ? 0, 0, 0, 0, … N 1, 1, 1, 1,… 0.0110…, 0.1010…, 0.0000…, 0.1111… ?问题: 0.0111111…=0.1000…, 非单射! ?解决: ? 《集合论与图论》第11讲12 P(A)≈2 A ?证明: 令f:P(A)→2 A , f(B)=χ B , 其中χ B 是B 的特征函数, χ B :A→{0,1}, χ B (x)=1?x∈B. (1) f是单射. 设A 1 ≠A 2 , 则?x∈A, 使得 χ A1 (x)≠χ A2 (x), 故χ A1 ≠χ A2 . (2) f是满射. 任给χ:A→{0,1}, 令 B = { x∈A | χ(x)=1 }?A, 则χ B =χ. # ?回忆: 2 A = A→2 ={ f | f:A→2 } (全函数) 《集合论与图论》第11讲13 A→(B→C) ≈ (A×B)→C ?证明: 令F: (A→(B→C)) → ((A×B)→C), F(f)=g, 其中 f:A→(B→C), g:(A×B)→C, g(<a,b>)=(f(a))(b), 注意f(a):B→C. 《集合论与图论》第11讲14 A→(B→C) ≈ (A×B)→C ?证明(续):(1) F是单射. 设f 1 ≠f 2 , F(f 1 )=g 1 , F(f 2 )=g 2 . 下证g 1 ≠g 2 . 因f 1 ≠f 2 , 故?a∈A, 使得f 1 (a)≠f 2 (a), 故又 ?b∈B, 使得(f 1 (a))(b)≠(f 2 (a))(b), 即 g 1 (<a,b>)≠g 2 (<a,b>), 所以g 1 ≠g 2 . 《集合论与图论》第11讲15 A→(B→C) ≈ (A×B)→C ?证明(续): (2) F是满射. 任给g:(A×B)→C, 下证?f:A→(B→C),使得 F(f)=g. 令f:A→(B→C), ?a∈A, f(a):B→C, ?x∈B, (f(a))(x) =g(<a,x>), 则F(f)=g. # 《集合论与图论》第11讲16 S-B定理 ?Schr?der-Bernstein定理: A≤?B ∧ B≤?A ? A≈B ?证明: 设f:A→B, g:B→A单射, 要构造 h:A→B双射. 《集合论与图论》第11讲17 S-B定理 A A B B f g 《集合论与图论》第11讲18 S-B定理 A B f g B 0 =B-ran f, A 0 =g(B 0 ), B 1 =f(A 0 ), A 1 =g(B 1 ), B 2 =f(A 1 ), … A n =g(B n ), B n+1 =f(A n ), … B 0 B 1 B 2 B 3 A 0 A 1 A 2 A 3 《集合论与图论》第11讲19 S-B定理 A B fg -1 B 0 B 1 B 2 B 3 A 0 A 1 A 2 A 3 A B f g B 0 B 1 B 2 B 3 A 0 A 1 A 2 A 3 《集合论与图论》第11讲20 证明不等势: 归纳法, 对角化 ?n,m∈N ∧ n≠m ? n≈m ?N≈P(N) ?A≈P(A) 《集合论与图论》第11讲21 n,m∈N ∧ n≠m ? n≈m ?定理: 不存在与自己的真子集等势的自然 数. ?说明:{0,1,…,n-1} → {0,1,…,m-1,…,n-1} ?证明: (数学归纳法)令 S ={ n∈N | ?f( f:n→n ∧ f单射→ f满射}. (1) 0∈S: f:0→0 ? f是空函数? f满射. 《集合论与图论》第11讲22 n,m∈N ∧ n≠m ? n≈m ?证明(续): (2) 设n∈S, 要证n + ∈S. 设f:n + →n + 且f是单射, 下证f是满射. 设g = f↑n : n→n + , (a) n 在f 下封闭. ran f = ran g ∪ {n} = n ∪ {n} = n + . (由归纳假设, ran g = n) ?说明: { 0,…,n-1,n } → { 0,…,n-1,n } { 0,…,n-1, n } → { 0,…,n-1,n} 《集合论与图论》第11讲23 n,m∈N ∧ n≠m ? n≈m ?证明(续):(b) n在f下不封闭. 设m∈n, f(m)=n, 令h:n + →n + , f(n), x=m h(x) = n, x=n f(x), x≠m ∧ x≠n 则n在h下封闭, 化为(a). ∴ S=N. # ?说明: {0,…m,…,n-1,n} → {0,…,f(n),…,n-1,n} {0,…,m,…n-1,n} → {…,f(n),…,n} 《集合论与图论》第11讲24 Cantor定理 ?Cantor定理: 设A为任意集合,则A≈P(A). ?证明: (反证) 假设存在双射f:A→P(A), 令 B = { x∈A| x?f(x) } 则B∈P(A). 由f是双射, 设f(b)=B, 则 b∈B ? b?f(b) ? b?B, 矛盾! # 《集合论与图论》第11讲25 Cantor定理(证明) A P(A) a b c ? a ab ac bc abc b c {a,b,c} {a,b} {a,c} {a} {b,c} {b} {c} ? 111 110 101 100 011 010 001 000 abc 《集合论与图论》第11讲26 Cantor定理(证明) A P(A) ? 《集合论与图论》第11讲27 对角化(diagonalization) ?Cantor定理(1874): 在全体自然数的幂集 与全体自然数之间不存在一一对应. ?证明:(反证)假设存在这样的一一对应. 于 是可以列举全体自然数的幂集: S 0 , S 1 , S 2 , … 《集合论与图论》第11讲28 ?m,n∈N, m∈S n ? OMMMMMMM L 是否否否是否 S 5 L 是是是是是是 S 4 L 否是否是否是 S 3 L 否否否否否否 S 2 L 否是否否是否 S 1 L 是是否是否是 S 0 L543210 《集合论与图论》第11讲29 ?n∈N, n∈S n ? OMMMMMMM L 是否否否是否 S 5 L 是是是是是是 S 4 L 否是否是否是 S 3 L 否否否否否否 S 2 L 否是否否是否 S 1 L 是是否是否是 S 0 L543210 《集合论与图论》第11讲30 S d = { n∈N| n?S n } OMMMMMMM L 否否否否是否 S 5 L 是否是是是是 S 4 L 否是是是否是 S 3 L 否否否是否否 S 2 L 否是否否否否 S 1 L 是是否是否否 S 0 L543210 《集合论与图论》第11讲31 对角化(diagonalization) ?证明(续):构造“对角化集”S d: S d = { n∈N| n?S n }, 显然S d ? { S 0 , S 1 , S 2 , … }, 这是因为n∈S d ? n?S n (?n∈N). 但是S d ∈{ S 0 , S 1 , S 2 , … }, 这是因为S 0 , S 1 , S 2 , …是对全体自然数 的幂集的列举, 矛盾! # 《集合论与图论》第11讲32 对角化简史(1) ?公元前7世纪(600 BC): Epimenides悖论 ?所有克里特人都是说谎者----一个克里特诗 人如是说. ?公元前5世纪(400 BC): Eubulides悖论 ?这句话是假的. ?公元13世纪(1200 AD): Medieval Study of Insolubia. ?我是说谎者. 《集合论与图论》第11讲33 对角化简史(2) ?1874年: Cantor定理 ?实数集是不可数的. ?1901年: Russell悖论 ?不以自身作为元素的集合的全体. ?1931年: G?del不完全性定理 ?这句话没有证明. 《集合论与图论》第11讲34 对角化简史(3) ?1936年: Turing. ?停机问题是不可判定的. ?1956年: Friedberg & Muchnik. ?存在不完全的Turing度. ?1965年: Hartmanis & Stearns ?更多的时间可以“计算出”更多的语言. 《集合论与图论》第11讲35 有穷集, 无穷集 ?有穷集(finite set): 不能与自身真子集建 立双射的集合 ?无穷集(infinite set) : 可以与自身真子集 建立双射的集合 ?无穷集也称无限集 ?Bernhard Bolzano(1781~1848), ?Czech人, 1851, “paradoxes of the infinite” ?首次使用“set”一词 ?给出无穷集的上述定义 《集合论与图论》第11讲36 基数(cardinality) ?基数: |A|, 或card A, 满足5条约定(公理) 1. card A = card B ? A ≈ B 2. A为有穷集,则card A = n, 其中A ≈ n (n是唯一的) 3. card N = ? 0 4. card R = ? 5. 0,1,2,…,? 0 ,?,都是基数, {0,1,2,…,}是有 穷基数 ?K 0 ={?},K 1 ={x|card x=1},K κ ={x|card x=κ} 《集合论与图论》第11讲37 基数的比较 ?设κ,λ为基数, A,B为集合, card A = κ, card B = λ, 规定: ?κ≤λ?A ≤? B ?κ < λ?A <? B ?κ = λ?A ≈ B ?例: 0≤κ. 设card A = κ, 单射?: ?→A. A非空时, 0<κ.n≤? 0 . card A < card P(A). 《集合论与图论》第11讲38 可数集(enumerable set) ?可数集(可列集): card A ≤? 0 . ?有穷可数集: n, (?n∈N) ?无穷可数集: N ?定理15: A是无穷可数集? A={a 1 ,a 2 ,…} ?定理18: A是无穷集? P(A)不是可数集 《集合论与图论》第11讲39 基数运算 ?设κ,λ为基数, K,L为集合, card K = κ, card L = λ, 规定 (1) κ+λ = card(K∪L), 其中K∩L=? (2) κ×λ = card(K × L) (3) κ λ = card(L→K) ?κ×λ也记作κ?λ, 或κλ 《集合论与图论》第11讲40 基数运算 ?定理19: 设K 1 ,K 2 ,L 1 ,L 2 为集合, K 1 ≈K 2 , L 1 ≈L 2 , 则 (1) 若K 1 ∩L 1 =K 2 ∩L 2 =?, 则K 1 ∪L 1 ≈ K 2 ∪L 2 (2) K 1 ×L 1 ≈ K 2 ×L 2 (3) K 1 →L 1 ≈ K 2 →L 2 . # 《集合论与图论》第11讲41 基数运算 ?定理20: (1) 2 cardA =card P(A) (2) κ < 2 κ . # ?推论: (1) card P(N) = 2 ?0 (2) card P(R) = 2 ? (3) ? = 2 ?0 . # 《集合论与图论》第11讲42 基数运算 ?定理21:设κ,λ,μ为基数 (1) κ+λ = λ+κ (2) (κ+λ)+μ = λ+(κ+μ) (3) κ?(λ+μ)= (κ?λ)+(κ?μ) (4) κ λ+μ = κ λ ?κ μ (5) (κ?λ) μ = κ μ ?λ μ (6) (κ λ ) μ = κ λ?μ . # 《集合论与图论》第11讲43 基数运算 ?定理22:设κ≤λ, μ为基数 (1) κ+μ≤λ+μ (2) κ?μ ≤ λ?μ (3) κ μ ≤λ μ (4) μ κ ≤μ λ , 其中κ,μ不同时为0. # 《集合论与图论》第11讲44 基数运算 ?定理23:设κ为无穷基数,则κ?κ = κ. # ?定理24:设κ为无穷基数, λ为基数,则 κ+λ = κ?λ = max{κ,λ}, (其中λ≠0) ?推论: κ+κ = κ?κ = κ. # ?定理25:设κ为无穷基数,则κ κ = 2 κ . # 《集合论与图论》第11讲45 总结 ?等势, 优势, 劣势, 绝对优势, 绝对劣势 ?Cantor定理, Schr?der-Bernstein定理 ?基数(势), ? 0 , ? ?有穷集, 无穷集, 可数集(可列集) ?基数运算 《集合论与图论》第11讲46 作业(#9) ?p148, 习题五, 5,11,12,+补充题 ?补充题: 设κ为任意基数, 证明: (1) κ 0 = 1; (2) 当κ≠0 时, 0 κ = 0; (3) κ + κ = 2κ 《集合论与图论》第11讲47 通知 ?ftp://162.105.30.157:graph:graph ?第4周 ?3月13日(本周四):序数 ?第5周 ?3月17日(下周一):习题课 ?3月19日(下周三):图论 ?3月20日(下周四):测验(1小时)