承认或不承认有不可数集这个东西, 倒有点哲学的味道, 而非证明这样数学上的东西. --- 我自己说的.
这篇文章算不得很数学的研讨文章, 用开源许可证里面经常用到的措辞就是它 AS IS.

无限集的数量概念

在离散数学中, 集合论部分中有个证明, 给出了两个不那么跟经验相符的说法

整数跟有理数一样多
实数比有理数多 (自然也就比整数多)

对于无穷数量的比较, 日常的说法就是, 给定无限集合 A 跟 B, 如果每从 A 里面拿出来一个东西, B 里面都相应地能拿出一个东西, 那么至少 B 中元素个数不会比 A 中元素数目少; 如果反过来也成立, 那么 A 跟 B 在元素个数上相同.
按照上面的思路, 前面一个断言的证明多种多样. 首先经验告诉我们有理数集 Q 不会比整数集 Z 中的元素少 (因为 Z 是 Q 的子集); 反过来, 从 Q 中拿出任何一个数 X/Y, 其中 X Y 分别在用二进制表示为

X = ...x_nx_n-1...x₃x₂x₁x₀
Y = ...y_ny_n-1...y₃y₂y₁y₀

那么必然可以在 Z 中找到数

K = ...x_ny_nx_n-1y_n-1...x₁y₁x₀y₀

与之对应, (并且不同表示的有理数对应的整数一定是不同的,) 因此 Z 中元素也不少于 Q. 命题得证.

常见于对角线方法的误解

而为了证明实数集 R 中元素多于 Z, 康托尔引入了称为对角线方法的证明方式. 对于这个证明方法如果叙述不严谨, 容易出现误解. 对角线方法不准确地阐述方式包括如下不准确的步骤

反证法: 假定实数区间 [0, 1) 是可数无限的
将这个区间中的元素按照某种方式排列成一个序列, 它与自然数一一映射
构造一个数 S, 它与这个序列中第 1 个数在小数点后第 1 位不同, 而与第 2 个数在小数点后第 2 位不同, ...
那么 S (很) 可能不是一个有理数, 但一定是一个实数, 并且与列表中任何一个实数的值不同
因此产生矛盾, 假定的条件不成立.

即证: 实数集不是可数的.

上述描述容易导致如下的误解

(S 真的不在列表中吗?) 两个数表现不同, 但它们的值可以是相同的. 比如构造出的 S=0.8999... 而列表中有 0.9000... 存在, 实际上这两个数虽然长得不一样, 值却是相同的.
(要花多久构造这个 S?) 如果让一台图灵机来干这个活计, 当然是 --- 无限久. 一个定理的破证明需要无穷多个步骤, 那还叫证明么? 四色定理的证明都比这强.

看这个看多了, 久而久之当然就不确信对角线方法的靠谱度.

勘误

问题描述

第一个误解是因为每次讲到这货, 书上 (甚至维基百科也如此) 偏偏要拿实数集来搞事. 其实还是回归证明的本质 (证明可数集的幂集的基数严格大于该可数集的基数), 只要设某个可数集 T (不一定是整数集之类的) 的幂集 p(T) 是可数的, 并且可列出一张表, 然后构造出一个 T 的子集不存在于这张表里面, 构造的要点当然也是.
因此, 首先明确要证明的是: 给定一个可数集 T, 如 {t₀, t₁, ... }, 它的幂集中元素的个数严格大于 T 中元素的个数.

证明

第二个误解不过因为大部分凡人数学家将自己限制到无论什么都得眼见为实, 对于搞数学这确实不是个好事情, 不过有些人 (譬如我) 就爱这样搞. 如果不喜欢, 只须谨记: 只要否定皇帝新衣的不可见性, 它就是可见的. 这才是超凡逻辑学家应有的节操.
那么证法变为如下

反证法: 假定 T 的幂集是可数的
也就是说, T 的所有子集可以按照某种方式排列成一个序列 S₀, S₁, ...
声称存在一个 S 是 T 的子集, 但不能存在于上述序列中, 给定任一整数 n, 若 t_n 属于 S_n, 告之 t_n 不属于 S, 反之类似
于是 S 并不在上述列表中, 产生矛盾, 故假定的条件不成立.

这个方法是个典型的非构造方法, 证明中只是 "声称" 存在某个子集, 但并不给出构造方式与构造结果, 同时如果询问这个集合具体有什么东西则不会有任何结果 (就像 Java 里面实现了 Set 的 contains 但是 iterate 方法直接抛异常一样), 它只能判别某个东西是否存在于这个集合中.
但无论怎么说, 这样就澄清了上述的两点误解.

Bit Focus

无限的困扰 - 对角线方法注校

无限集的数量概念

常见于对角线方法的误解

勘误

问题描述

证明

	Back to Bit Focus
	NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
	About this site

		Your comment will be licensed under
		CC-NC-ND 3.0