这篇文章算不得很数学的研讨文章, 用开源许可证里面经常用到的措辞就是它 AS IS.
无限集的数量概念
在离散数学中, 集合论部分中有个证明, 给出了两个不那么跟经验相符的说法- 整数跟有理数一样多
- 实数比有理数多 (自然也就比整数多)
按照上面的思路, 前面一个断言的证明多种多样. 首先经验告诉我们有理数集 Q 不会比整数集 Z 中的元素少 (因为 Z 是 Q 的子集); 反过来, 从 Q 中拿出任何一个数 X/Y, 其中 X Y 分别在用二进制表示为
- X = ...xnxn-1...x3x2x1x0
- Y = ...ynyn-1...y3y2y1y0
- K = ...xnynxn-1yn-1...x1y1x0y0
常见于对角线方法的误解
而为了证明实数集 R 中元素多于 Z, 康托尔引入了称为对角线方法的证明方式. 对于这个证明方法如果叙述不严谨, 容易出现误解. 对角线方法不准确地阐述方式包括如下不准确的步骤- 反证法: 假定实数区间 [0, 1) 是可数无限的
- 将这个区间中的元素按照某种方式排列成一个序列, 它与自然数一一映射
- 构造一个数 S, 它与这个序列中第 1 个数在小数点后第 1 位不同, 而与第 2 个数在小数点后第 2 位不同, ...
- 那么 S (很) 可能不是一个有理数, 但一定是一个实数, 并且与列表中任何一个实数的值不同
- 因此产生矛盾, 假定的条件不成立.
上述描述容易导致如下的误解
- (S 真的不在列表中吗?) 两个数表现不同, 但它们的值可以是相同的. 比如构造出的 S=0.8999... 而列表中有 0.9000... 存在, 实际上这两个数虽然长得不一样, 值却是相同的.
- (要花多久构造这个 S?) 如果让一台图灵机来干这个活计, 当然是 --- 无限久. 一个定理的破证明需要无穷多个步骤, 那还叫证明么? 四色定理的证明都比这强.
勘误
问题描述
第一个误解是因为每次讲到这货, 书上 (甚至维基百科也如此) 偏偏要拿实数集来搞事. 其实还是回归证明的本质 (证明可数集的幂集的基数严格大于该可数集的基数), 只要设某个可数集 T (不一定是整数集之类的) 的幂集 p(T) 是可数的, 并且可列出一张表, 然后构造出一个 T 的子集不存在于这张表里面, 构造的要点当然也是.因此, 首先明确要证明的是: 给定一个可数集 T, 如 {t0, t1, ... }, 它的幂集中元素的个数严格大于 T 中元素的个数.
证明
第二个误解不过因为大部分凡人数学家将自己限制到无论什么都得眼见为实, 对于搞数学这确实不是个好事情, 不过有些人 (譬如我) 就爱这样搞. 如果不喜欢, 只须谨记: 只要否定皇帝新衣的不可见性, 它就是可见的. 这才是超凡逻辑学家应有的节操.那么证法变为如下
- 反证法: 假定 T 的幂集是可数的
- 也就是说, T 的所有子集可以按照某种方式排列成一个序列 S0, S1, ...
- 声称存在一个 S 是 T 的子集, 但不能存在于上述序列中, 给定任一整数 n, 若 tn 属于 Sn, 告之 tn 不属于 S, 反之类似
- 于是 S 并不在上述列表中, 产生矛盾, 故假定的条件不成立.
Set 的 contains 但是 iterate 方法直接抛异常一样), 它只能判别某个东西是否存在于这个集合中.但无论怎么说, 这样就澄清了上述的两点误解.
