2020/9/25
《集合论与图论》第11讲
14
A(BC) (AB)C
证明(续): (2) F是满射. 任给g:(AB)C, 下证f:A(BC),使得 F(f)=g. 令f:A(BC), aA, f(a):BC, xB, (f(a))(x) =g(<a,x>), 则F(f)=g. #
2020/9/25
说明: {0,…m,…,n-1,n} {0,…,f(n),…,n-1,n}
{0,…,m,…n-1,n} {…,f(n),…,n}
2020/9/25
《集合论与图论》第11讲
23
Cantor定理
Cantor定理: 设A为任意集合,则AP(A). 证明: (反证) 假设存在双射 f:AP(A), 令
29
Sd = { nN | nSn }
0 1 2 3 4 5
S0 否 否 是 否 是 是 S1 否 否 否 否 是 否 S2 否 否 是 否 否 否 S3 是 否 是 是 是 否 S4 是 是 是 是 否 是 S5 否 是 否 否 否 否
2020/9/25
《集合论与图论》第11讲
穷基数
K0={},K1={x|card x=1},K={x|card x=}
2020/9/25
《集合论与图论》第11讲
36
基数的比较
设 ,为基数, A,B为集合, card A = , card B = , 规定: A • B < A <• B =AB 例: 0. 设card A = , 单射: A. A非空时, 0<. n0.
《集合论与图论》第11讲
35
基数(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,…,}是有
2020/9/25
《集合论与图论》第11讲
3
等势关系是等价关系
自反: AA IA :AA双射
对称: AB BA f :AB双射 f -1:BA双射
传递: AB BC AC f :AB, g:BC双射 g○f:AC双射
2020/9/25
《集合论与图论》第11讲
6
证明等势 构造双射
A
A0 A1
g
A2 A3 f
B B0 B1 B2 B3
B0=B-ran f, A0=g(B0), B1=f(A0), A1=g(B1), B2=f(A1), … An=g(Bn), Bn+1=f(An), …
2020/9/25
《集合论与图论》第11讲
18
S-B定理
A
A0 A1
g
A2 A3 f
B B0 B1 B2 B3
直接构造双射:
NNN, R(0,1), [0,1](0,1), (0,1)2N P(A)2A, A(BC)(AB)C
间接构造双射:
传递性: AB BC AC S-B定理: A•B B•A AB
2020/9/25
《集合论与图论》第11讲
7
R(0,1)
2020/9/25
《集合论与图论》第11讲
30
对角化(diagonalization)
证明(续): 构造“对角化集”Sd :
Sd = { nN | nSn },
显然
Sd { S0, S1, S2, … },
这是因为 nSd nSn (nN).
但是
Sd { S0, S1, S2, … },
这是因为 S0, S1, S2, … 是对全体自然数 的幂集的列举, 矛盾! #
2020/9/25
《集合论与图论》第11讲
38
基数运算
设 ,为基数, K,L为集合, card K = , card L = , 规定 (1) + = card(KL), 其中KL= (2) = card(K L) (3) = card(LK) 也记作•, 或
1936年: Turing.
停机问题是不可判定的.
1956年: Friedberg & Muchnik.
存在不完全的Turing度.
1965年: Hartmanis & Stearns
更多的时间可以“计算出”更多的语言.
2020/9/25
《集合论与图论》第11讲
34
有穷集, 无穷集
有穷集(finite set): 不能与自身真子集建 立双射的集合
A
A0 A1 A2 A3
g-1
f
B B0 B1 B2 B3
2020/9/25
《集合论与图论》第11讲
19
证明不等势: 归纳法, 对角化
n,mN nm nm NP(N) AP(A)
2020/9/25
《集合论与图论》第11讲
20
n,mN nm nm
定理: 不存在与自己的真子集等势的自然 数.
2020/9/25
《集合论与图论》第11讲
25
Cantor定理(证明)
?
A
P(A)
2020/9/25
《集合论与图论》第11讲
26
对角化(diagonalization)
Cantor定理 (1874): 在全体自然数的幂集 与全体自然数之间不存在一一对应.
证明: (反证)假设存在这样的一一对应. 于 是可以列举全体自然数的幂集: S0, S1, S2, …
《集合论与图论》第11讲
15
S-B定理
Schröder-Bernstein定理: A•B B•A AB
证明: 设f :AB, g:BA单射, 要构造 h:AB双射.
2020/9/25
《集合论与图论》第11讲16S-B定理A f
B A
g B
2020/9/25
《集合论与图论》第11讲
17
S-B定理
card A < card P(A).
2020/9/25
《集合论与图论》第11讲
37
可数集(enumerable set)
可数集(可列集): card A 0. 有穷可数集: n, (nN) 无穷可数集: N 定理15: A是无穷可数集 A={a1,a2,…} 定理18: A是无穷集 P(A)不是可数集
我是说谎者.
2020/9/25
《集合论与图论》第11讲
32
对角化简史(2)
1874年: Cantor定理
实数集是不可数的.
1901年: Russell悖论
不以自身作为元素的集合的全体.
1931年: Gödel不完全性定理
这句话没有证明.
2020/9/25
《集合论与图论》第11讲
33
对角化简史(3)
《集合论与图论》第11讲
28
nN, nSn ?
0 1 2 3 4 5
S0 是 否 是 否 是 是 S1 否 是 否 否 是 否 S2 否 否 否 否 否 否 S3 是 否 是 否 是 否 S4 是 是 是 是 是 是 S5 否 是 否 否 否 是
2020/9/25
《集合论与图论》第11讲
第11讲 基数
内容提要 等势 ,优势 ,劣势 ,绝对优势 ,绝对劣势 Cantor定理 ,Schröder-Bernstein定理 基数(势 א,0 א,) )可列集(可数集 ,无穷集 ,有穷集 基数运算
2020/9/25
《集合论与图论》第11讲
1
两个基本过程
匹配(matching): 多少,大小(基数)----双射 {a} {0}=1
2020/9/25
《集合论与图论》第11讲
31
对角化简史(1)
公元前7世纪(600 BC): Epimenides悖论
所有克里特人都是说谎者----一个克里特诗 人如是说.
公元前5世纪(400 BC): Eubulides悖论
这句话是假的.
公元13世纪(1200 AD): Medieval Study of Insolubia.
{a,b} {0,1}=2 {a,b,c} {0,1,2}=3… 计数(counting): 首尾,先后(序数)----良序
0123… ab
cba ……
2020/9/25
《集合论与图论》第11讲
2
无穷之迷
许多关于无穷的悖论 无穷是否“存在”? 人是否“理解”无
穷? 无穷大, 无穷小, 无限可分性 极限 有穷与无穷的区别?
说明: { 0,…,n-1,n } { 0,…,n-1,n }
{ 0,…,n-1, n } { 0,…,n-1,n}
2020/9/25
《集合论与图论》第11讲
22
n,mN nm nm
证明(续): (b) n在f下不封闭. 设mn, f(m)=n, 令 h:n+n+, f(n), x=m h(x) = n, x=n f(x), xm xn 则n在h下封闭, 化为(a). S=N. #
说明: {0,1,…,n-1} {0,1,…,m-1,…,n-1} 证明: (数学归纳法)令
S ={ nN | f( f:nn f单射 f满射 }. (1) 0S: f:00 f是空函数 f满射.
2020/9/25
《集合论与图论》第11讲
21
n,mN nm nm
证明(续): (2) 设 nS, 要证 n+S. 设 f:n+n+ 且 f是单射, 下证 f是满射. 设 g = fn : nn+, (a) n 在 f 下封闭. ran f = ran g {n} = n {n} = n+. (由归纳假设, ran g = n)
