计算机问题求解 – 论题1-11 - 有限与无限 2017年12月14日.

Presentation on theme: "计算机问题求解 – 论题1-11 - 有限与无限 2017年12月14日."— Presentation transcript:

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！

11

12 问题7: 为什么“鸽巢原理”在证 明一个集合是无限集合时 有关键的应用？

13 问题8： 对于“一对一”性质的满足，一个函数与 其在定义域的某个真子集上的“限制”相 互是什么关系？
限制不是一对一，函数就不是一对一 The restriction 𝑓 ​ 𝐶⊆𝐴 is not one-to-one, then f cannot be one-to-one

14 鸽巢：“证明策略”和“数学定理” 问题9： 你能简述一下这个证明的基本思路吗？

15

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 矛盾

24

25 直线上的点集与平面上的点集等势 这实际上意味着直线上的点与任意有限维空间的点“一样多”！ 0.a1a2a3.......
0.a1b1a2b2a3b3..... 0.a1a2a 0.b1b2b 这实际上意味着直线上的点与任意有限维空间的点“一样多”！

26 问题10：你从这个证明中看到康托尔对角线证明法了吗？
康托尔定理 – 没有“最大”的集合 问题10：你从这个证明中看到康托尔对角线证明法了吗？ 任何集合与其幂集不等势 即：A≉(A) 证明要点： 设g是从A到(A)的函数，构造集合B如下： B={x| xA, 但xg(x)} 则B(A)，但不可能存在xA，能满足g(x)=B 因为，如果有这样的x, 则xB iff. xB。 因此，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;