北京大学：《离散数学》系列课程之一《集合论与图论》第11讲 基数

第11讲基数 内容提要 等势,优势,劣势,绝对优势,绝对劣势 秦 Cantor定理, Schroder-Bernstein定理 基数(势),N,N 有穷集,无穷集,可数集(可列集) 基数运算 《集合论与图论》第11讲

《集合论与图论》第11讲 1 第11讲 基数 内容提要 等势, 优势, 劣势, 绝对优势, 绝对劣势 Cantor定理, Schröder-Bernstein定理 基数(势), א0, א 有穷集, 无穷集, 可数集(可列集) 基数运算

两个基本过程 匹配( matching):多少,大小(基数)--双射 {a>{0}=1 {ab}>{0,1}2 {ab,c}→{0,1,2}=3 计数(counting)首尾,先后(序数)--良序 0→)1→>2->3→ a>b C→>b→>a 《集合论与图论》第11讲

《集合论与图论》第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讲

《集合论与图论》第11讲 3 无穷之迷 许多关于无穷的悖论 无穷是否“存在”? 人是否“理解”无穷? 无穷大, 无穷小, 无限可分性 极限 有穷与无穷的区别?

芝诺悖论( Zeno's paradoX) 芝诺悖论:阿基里斯( Achilles追不上乌龟 阿基里斯比乌龟快一倍 乌龟在阿基里斯前面起跑 《集合论与图论》第11讲

《集合论与图论》第11讲 4 芝诺悖论(Zeno’s paradox) 芝诺悖论: 阿基里斯(Achilles)追不上乌龟 阿基里斯比乌龟快一倍 乌龟在阿基里斯前面起跑

尊势( same cardinality) 婚等势:A≈B分彐双射fA→B 婚优势劣势:AB 台→B比A优势兮A比B劣势 癱绝对优势绝对劣势: A<·B台A·B∧AB ◇→B比A绝对优势◇A比B绝对劣势 《集合论与图论》第11讲

《集合论与图论》第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绝对劣势

等势关系是等价关系 自反:AA IA:A->A双射 秦对称:A≈B→B≈A fA→>B双射→f1B→A双射 传递:AB∧BC→AC f:A>B,g:B>C双射→gfA>C双射 《集合论与图论》第11讲

《集合论与图论》第11讲 6 等势关系是等价关系 自反: 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双射 ⇒ g○f:A→C双射

证明等势兮构造双射 癱直接构造双射: NXNN,R≈(0,1),[0.1(0,1,(0,1)≈2N P(A)≈2A,A>(B→)C≈(AXB)>C 癱间接构造双射: 传递性:A≈B∧B≈C→AC SB定理:A<B∧B≤A→AB 《集合论与图论》第11讲

《集合论与图论》第11讲 7 证明等势 ⇔ 构造双射 直接构造双射: N×N≈N, R≈(0,1), [0,1]≈(0,1), (0,1)≈2N P(A)≈2A, A→(B→C)≈(A×B)→C 间接构造双射: 传递性: A≈B ∧ B≈C ⇒ A≈C S-B定理: A≤•B ∧ B≤•A ⇒ A≈B

R≈(0,1) 《集合论与图论》第11讲

《集合论与图论》第11讲 8 R≈(0,1)

0,1]≈(0,1) N>N0,12},{2,-1yNN 《集合论与图论》第11讲

《集合论与图论》第11讲 9 [0,1]≈(0,1) N→N-{0,1,2}, {-2,-1}∪N→N 012345678 012 345678 012345678 012345678 -1 -2

0,1]≈(0,1) Y 00 HH+ 《集合论与图论》第11讲

《集合论与图论》第11讲 10 [0,1]≈(0,1)