第12讲 序数 北京大学计算机系离散数学讲义(ppt版).pptVIP

《集合论与图论》第12讲 第12讲 序数 内容提要 良序, 序数, ? 序数与基数 ZFC+CH系统 Collatz猜想 两个基本过程 匹配(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 …… 基数 ? 2? . ?? = 2?. (?为无穷基数) ?+? = ??? = ?. (?为无穷基数) 连续统假设(continuum hypothesis): 序数(ordinality) 集合-------双射----------等势----基数 良序集----保序双射----同构----序数 良序集的同构?: 良序集A,A,B,B,双射f:A?B,满足 xAy ? f(x)Bf(y) (保序性) 例: {0,1,2}, ? {b,p,z},字母, f(0)=b, f(1)=p, f(2)=z 良序 良序:任何非空子集都有最小元的偏序 良序集的计数过程: A, t0 = min( A ), t1 = min( A-{t0} ), t2 = min( A-{t0,t1} ), …… t0 t1 t2 …… 序数: 0, 1, 2, … 0 1 2 3 4 5 6 … 序数: ?, ?+1, ?+2, … ? ?+1 ?+2 ?+3 ?+4 …… 序数: 2?, …, 3?, … ?+?=2? 2?+1 2?+2 … 3? 3?+1 … 序数: ?2, ?2+1, …, ?3, … ??=?2 ?2+1 ?2+2 … ?3 ?3+1 … 序数: ?? …… …… 实例: 英语字典 英语单词如何排序? 字母序: ? a b c … x y z 标准序: 短在前,长在后,等长的依次比字母, 如 to up cap cat too two boat boot card 字典序: 依次比字母, 如 boat boot cap card cat to too two up 英语字典: a,…,b,…,c,…,…,z,… 26? ? 三类序数 0 后继序数: 1,2,…,?+1,?+2,… (有头有尾) 极限序数: ?, 2?, ?2, ??,… (有头无尾) 序数与基数 基数: 序数: 初始序数: 不与前面的序数等势的序数 基数实现: 归纳集, 幂集, 连续统假设 序数实现: 传递集,选择公理,超限归纳法 归纳集与传递集 归纳集: ??A ? ?x( x?A?x?{x}?A ) 传递集: ?x( x?y?A?x?A ) 连续统假设(CH) Georg Cantor(1845~1918), 最早提出 David Hilbert(1862~1943),1900年, 著名的23个问题之一 Kurt G?del(1906~1978),1938年,相容性 Paul Cohen(1934~), 1963年, 独立性 集合论公理系统: ZF, ZFC, ZFC+CH ZF系统 外延公理: A=B ? ?x(x?A?x?B) 无序对公理: a,b是集合 ? {a,b}是集合 子集公理: A是集合 ? {x?A|P(x)}是集合 ( 定义 A?B = { x?A | x?B } ) 并集公理: A是集族 ? UA是集合 ( 配合无序对公理, 定义 A?B =U{A,B} ) ZF系统(续) 幂集公理: A是集合 ? P(A)是集合 空集公理: ?是集合 正则公理: A是非空集合 ? A有基础元素(基础元素: 不属于A中其他元素的元素). ( 用途: 防止 A?A ) 替换公理: f是A上函数 ? { f(a) | a?A }是集合 无穷公理: N是集合 ZFC系统 ZF系统+选择公理(Choice axiom) 选择公理: A是元素互不相交的非空集族,可以从A的每个元素中选择一个元素,组成一个集合 选择公理的等价形式(部分) 广义选择公理: 任何非空集族都有选择函数( f:A?UA, f(X)?X ) 良序原理: 任何集合都可良序化 Zorn引理: 链总有上界的非空偏序集存在极大元 Hausdorff极大原理: 任何链都包含于极大链 三歧性原理: A,B是集合 ? |A|?|B| ? |B|?|A| ZFC+CH系统 ZF+C+CH ZF: Zermelo-Fraenkel公理(9条) C: 选择公理 CH: 连续统假设 超限归纳原理 良序集的超限归纳原理: A,, B?A??