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

“聪明的经理”、“非常聪明的经理”和“非常非常聪明的经理” 问题1： 你能给我们讲讲这个故事吗？ 客 满 “希尔伯特旅馆” http://www.science4all.org/article/cantors-infinite/

集合的等势 问题2： 你原来脑海中的“两个集合元素一样多”的概 念是什么样的呢？ 对无穷集合适用吗？

问题3：如何精确定义什么是有限集？ 更加数学化的表述：(每一个自然数也是一个集合) 空集记为0； 如果k是自然数，则其“后继”为: k  {k} 。 于是： 有限集就是与某个自然数等势的集合。

问题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.

自然数集与整数集等势 “排队”： 0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, … 开启无限的无限想象

问题5: “…-3,-2,-1,0,1,2,3,…”不 能算“排好队”了, 为什么? 排队本质是在做什么？ 双射

关于双射的证明 (1) 注意: 不能遗漏了case 3!

关于双射的证明 (2)

伽利略悖论： 整体与局部“一样大”！ 无穷不仅仅是“很多很多” 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！ https://en.wikipedia.org/wiki/Galileo%27s_paradox

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

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

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

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 .

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

自然数集是无限集 反证法 无限变有限，构造鸽子与笼子

有限集合的“势”(cardinality) 问题10： 如果不唯一，怎样能构造出与 “鸽巢原理”的矛盾来？

可数集 注意： 这个性质使得我们可以不区分有限或无限可数； 通常找一个一对一的函数比找一个双射容易。 原因：建立在下一页ppt上，可数集合的任意子集也是可数的

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。

有理数集是可数集

但是实数集不是可数集！ 矛盾 Cantor’s diagonalization argument 反证：假设实数集可数 Since every subset of a countable set is countable, the open interval (0,1) must be (infinitely) countable 矛盾

http://www.science4all.org/article/cantors-infinite/

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

问题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类似于前面通过对角线找到的特殊的实数；

集合的“大小” – 基数 ？ N2 N1 还有什么 曲线 N0 点 可数 我们能想象到的世界 有限 我们能感觉到的世界

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引理 http://www.mn.uio.no/math/tjenester/kunnskap/kompendier/acwozl.pdf https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory https://en.wikipedia.org/wiki/Infinite_set

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

家庭作业 UD problems: 20.4, 20.8-10; problems: 21.7, 21.9-11, 21.16-19;