《集合论与图论》第12讲1 第12讲序数 内容提要 ?良序, 序数, ω ?序数与基数 ?ZFC+CH系统 ?Collatz猜想 《集合论与图论》第12讲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 …… 《集合论与图论》第12讲3 基数 ? ?κ < 2 κ . ?κ κ = 2 κ . (κ为无穷基数) ?κ+κ = κ?κ = κ. (κ为无穷基数) ?连续统假设(continuum hypothesis): LL ,2,2,2,,,2,1,0 0 2 0 0 2 3 2 210 ? ? =?=?=?? ? )2( 0 0 ? <<??? κκ 《集合论与图论》第12讲4 序数(ordinality) ?集合-------双射----------等势----基数 ?良序集----保序双射----同构----序数 ?良序集的同构?: 良序集<A,< A >,<B,< B >,双射f:A→B,满足 x< A y ? f(x)< B f(y) (保序性) ?例: <{0,1,2},<> ? <{b,p,z},< 字母 >, f(0)=b, f(1)=p, f(2)=z 《集合论与图论》第12讲5 良序 ?良序:任何非空子集都有最小元的偏序 ?良序集的计数过程: <A,<> t 0 = min( A ), t 1 = min( A-{t 0 } ), t 2 = min( A-{t 0 ,t 1 } ), …… t 0 < t 1 < t 2 <…<… 《集合论与图论》第12讲6 序数: 0, 1, 2, … ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?… 0=?是良序集 《集合论与图论》第12讲7 序数: ω, ω+1, ω+2, … ? ω ?ω+1 ?ω+2 ?ω+3 ?ω+4 ?…… 《集合论与图论》第12讲8 序数: 2ω, …, 3ω, … ?ω+ω=2ω ?2ω+1 ?2ω+2 ?… ?3ω ?3ω+1 ?… 《集合论与图论》第12讲9 序数: ω 2 , ω 2 +1, …, ω 3 , … ?ωω=ω 2 ?ω 2 +1 ?ω 2 +2 ?… ?ω 3 ?ω 3 +1 ?… 《集合论与图论》第12讲10 序数: ?ω ω ?…… ? ?…… ω ω ω ω次 ω ω 次 LL ,,, ω ωω ωω 《集合论与图论》第12讲11 实例: 英语字典 ?英语单词如何排序? ?字母序: ε < 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ω ? 《集合论与图论》第12讲12 三类序数 ? 0 ?后继序数: 1,2,…,ω+1,ω+2,… (有头有尾) ?极限序数: ω, 2ω, ω 2 , ω ω ,… (有头无尾) 《集合论与图论》第12讲13 ?基数: ?序数: ?初始序数: 不与前面的序数等势的序数 ?基数实现: 归纳集, 幂集, 连续统假设 ?序数实现: 传递集,选择公理,超限归纳法 LL ,,,,,2,1,0 ω ωω ωωω LL ,2,2,2,,,2,1,0 0 2 0 0 22 0 ? ? ? ? LLLLLL ,,,,,,,2,,1,,,2,1,0 2 ω ωω ωωωωωω + 序数与基数 《集合论与图论》第12讲14 归纳集与传递集 ?归纳集: ?∈A ∧?x( x∈A→x∪{x}∈A ) ?传递集: ?x( x∈y∈A→x∈A ) 《集合论与图论》第12讲15 连续统假设(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 )2( 0 0 ? <<??? κκ 《集合论与图论》第12讲16 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} ) 《集合论与图论》第12讲17 ZF系统(续) ?幂集公理: A是集合? P(A)是集合 ?空集公理: ?是集合 ?正则公理: A是非空集合? A有基础元素 (基础元素: 不属于A中其他元素的元素). ( 用途: 防止A∈A ) ?替换公理: f是A上函数? { f(a) | a∈A }是 集合 ?无穷公理: N是集合 《集合论与图论》第12讲18 ZFC系统 ?ZF系统+选择公理(Choice axiom) ?选择公理: A是元素互不相交的非空集族, 可以从A的每个元素中选择一个元素,组 成一个集合 《集合论与图论》第12讲19 选择公理的等价形式(部分) ?广义选择公理: 任何非空集族都有选择 函数( f:A→UA, f(X)∈X ) ?良序原理: 任何集合都可良序化 ?Zorn引理: 链总有上界的非空偏序集存在 极大元 ?Hausdorff极大原理: 任何链都包含于极 大链 ?三歧性原理: A,B是集合? |A|≤|B| ∨ |B|≤|A| 《集合论与图论》第12讲20 ZFC+CH系统 ?ZF+C+CH ?ZF: Zermelo-Fraenkel公理(9条) ?C: 选择公理 ?CH: 连续统假设 《集合论与图论》第12讲21 超限归纳原理 ?良序集的超限归纳原理: <A,<>, B?A∧?t((t∈A∧seg t?B)→t∈B) ? B=A ?前节(segment): seg t = { x∈A | x<t } 《集合论与图论》第12讲22 对比 ?数学归纳法: P(0), P(n)→P(n+1) ?第二数学归纳法: P(0), P(0)∧P(1)∧…∧P(n)→P(n+1) ?超限归纳法: “P(seg t)”→P(t) P( ) P( ) 《集合论与图论》第12讲23 Collatz猜想 ?Collatz猜想(Collaz conjecture): ?m∈N + , ?k∈N + , f k (m)=1 其中f k 是f的k次复合, f:N + →N + , ?这是悬而未决问题(open problem)! ? ? ? ? ? + = 是奇数 是偶数 nn n n nf 13 , 2 )( 《集合论与图论》第12讲24 Collatz猜想 ?实验: m=100 ?50,25,76,38,19,58,29,88,44,22,11,34,17 ,52,26,13,40,20,10,5,16,8,4,2,1 ?实验: m=120 ?60,30,15,46,23,70,35,106,53,160,80,40 ?证明: ? ?想法(idea): 自然数表示, 性质, 用处? 100=0010010100010100100010000 《集合论与图论》第12讲25 总结 ?良序, 序数, ω ?序数与基数 ?ZFC+CH系统 ?Collatz猜想 《集合论与图论》第12讲26 答疑 ?时间: 公共空闲时间= ? ?地点: 理科1#楼1625室 ?电话: 62765818