Download presentation
Presentation is loading. Please wait.
1
计算机问题求解 – 论题 有限与无限 2017年12月14日
2
“聪明的经理”、“非常聪明的经理”和“非常非常聪明的经理”
问题1: 你能给我们讲讲这个故事吗? 客 满 “希尔伯特旅馆”
3
集合的等势 问题2: 你原来脑海中的“两个集合元素一样多”的概 念是什么样的呢? 对无穷集合适用吗?
4
问题3:如何精确定义什么是有限集? 更加数学化的表述:(每一个自然数也是一个集合) 空集记为0;
如果k是自然数,则其“后继”为: k {k} 。 于是: 有限集就是与某个自然数等势的集合。
5
问题4: 什么是无限集合? 提示:有限集就是与某个自然数等势的集合
A set is infinite if it is not finite A set is infinite if and only if for every natural number the set has a subset whose cardinality is that natural number.
6
自然数集与整数集等势 “排队”: 0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, … 开启无限的无限想象
7
问题5: “…-3,-2,-1,0,1,2,3,…”不 能算“排好队”了, 为什么? 排队本质是在做什么? 双射
8
关于双射的证明 (1) 注意: 不能遗漏了case 3!
9
关于双射的证明 (2)
10
伽利略悖论: 整体与局部“一样大”! 无穷不仅仅是“很多很多” Not necessary!
It is possible to define comparisons amongst infinite sets in a meaningful way! 伽利略悖论: 整体与局部“一样大”! Galileo Galilei The ideas of less, equal, and greater apply to (what we would now call) finite sets, but not to infinite sets!
12
问题7: 为什么“鸽巢原理”在证 明一个集合是无限集合时 有关键的应用?
13
问题8: 对于“一对一”性质的满足,一个函数与 其在定义域的某个真子集上的“限制”相 互是什么关系?
限制不是一对一,函数就不是一对一 The restriction 𝑓 𝐶⊆𝐴 is not one-to-one, then f cannot be one-to-one
14
鸽巢:“证明策略”和“数学定理” 问题9: 你能简述一下这个证明的基本思路吗?
16
Then 𝑓∘𝑔 cannot be one-to-one;
g 1 2 3 … j m 1 2 3 … j m q n+1 f 𝑓∘𝑔 1,…,𝑚−1 maps 1,…,𝑚−1 to 1,…,𝑛 ; By H, 𝑓∘𝑔 1,…,𝑚−1 is not one-to-one. Then 𝑓∘𝑔 cannot be one-to-one; As 𝑔 is one-to-one, So 𝑓 cannot be one-to-one; ( 𝑓∘𝑔)(𝑚) = 𝑓 (𝑔(𝑚)) = 𝑛+1 .
17
问题7: 为什么“鸽巢原理”在证 明一个集合是无限集合时 有关键的应用?
18
自然数集是无限集 反证法 无限变有限,构造鸽子与笼子
19
有限集合的“势”(cardinality)
问题10: 如果不唯一,怎样能构造出与 “鸽巢原理”的矛盾来?
20
可数集 注意: 这个性质使得我们可以不区分有限或无限可数; 通常找一个一对一的函数比找一个双射容易。
原因:建立在下一页ppt上,可数集合的任意子集也是可数的
21
Every subset of ℕ is countable
可数集的子集是可数集 可以比拟为“辅助线”的定理: Every subset of ℕ is countable “N与其任一无限子集T之间存在双射”证明的基本思路: 建立一个函数f : f (k)=T 中第k个“最小”元素; 证明f 是一对一的:函数值构成严格递增序列; 证明f 是满射:对T 中任何元素s , 假设比s 小的元素有n 个, 则f (n+1)=s。
22
有理数集是可数集
23
但是实数集不是可数集! 矛盾 Cantor’s diagonalization argument
反证:假设实数集可数 Since every subset of a countable set is countable, the open interval (0,1) must be (infinitely) countable 矛盾
25
直线上的点集与平面上的点集等势 这实际上意味着直线上的点与任意有限维空间的点“一样多”! 0.a1a2a3.......
0.a1b1a2b2a3b3..... 0.a1a2a 0.b1b2b 这实际上意味着直线上的点与任意有限维空间的点“一样多”!
26
问题10:你从这个证明中看到康托尔对角线证明法了吗?
康托尔定理 – 没有“最大”的集合 问题10:你从这个证明中看到康托尔对角线证明法了吗? 任何集合与其幂集不等势 即:A≉(A) 证明要点: 设g是从A到(A)的函数,构造集合B如下: B={x| xA, 但xg(x)} 则B(A),但不可能存在xA,能满足g(x)=B 因为,如果有这样的x, 则xB iff. xB。 因此,g不可能是满射。 B类似于前面通过对角线找到的特殊的实数;
27
集合的“大小” – 基数 ? N2 N1 还有什么 曲线 N0 点 可数 我们能想象到的世界 有限 我们能感觉到的世界
28
Open topic-1 介绍选择公理及其等价公理 ZF与ZFC The Axiom of Choice
If the axiom of choice holds, then a set is infinite if and only if it includes a countable infinite subset. 介绍选择公理及其等价公理 ZF与ZFC The Axiom of Choice Well-ordering theorem ZORN引理
29
Open topic-2 介绍连续统假设( Continuum hypothesis)
It asserts that the infinite of the reals is the smallest infinite bigger than the listable(countable) infinite Kurt Gödel Paul Cohen
30
家庭作业 UD problems: 20.4, 20.8-10; problems: 21.7, 21.9-11, 21.16-19;
Similar presentations