Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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;


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

Similar presentations


Ads by Google