对角论证法的两个小问题

饭团同学x · March 21, 2017 · 学习

对角论证法是康托尔用于证明实数集不可数的方法。学习过程中,有同学提出了以下两个问题,我认为值得记录。

问题一

该证明的基本方法是矛盾证明法(proof by contradiction)。假设区间 $[0, 1]$ 是可数无穷的,那么,我们可以把已知的所有数字排成数列。之后构造出一个不存在于此数列中却处于集合中的数,由此得出矛盾,证明 $[0, 1]$ 是不可数的。

有同学认为,对角论证法必然要满足“对角”条件,意即,列出来的数字应当排成一个方阵。假设我们列出了 $n$ 个数字,那么我们在构造新数字时,必然要有第 $n$ 位,但第 $n$ 为实际上需要列出 $10^n$ 个数字。因此,由于 $10^n$ 与 $n$ 的增长速度不同,我们无法假设这样的方阵存在,因而也不能使用对角论证法。

这样的说法或许传达得不够准确,在解决问题的过程中我找到了一篇博文,虽然文章使用的一些名词我不大懂。但也许说的是一回事。

从后来群里的讨论来看。这个问题和 $10^n$ 没有太大关系,因为我们假定 $[0, 1]$ 是可列的,那么它的基数(cardinality)便与自然数相等,因此可以实现一一对应。不存在不同的增长速度的问题。正如偶数和自然数的基数相等,但看起来自然数好像比偶数多、增长速度快,但既然我们已经假设了基数相等,便总有对应。

问题二

对角论证法是否可以用来证明整数不可数?

这个问题在 StackExchange 上有两个相关讨论(其一其二)。简单地说,实数可以不断在后面加上 0,但对整数而言,一旦整数被确定,它的位数就是有限的。而用类似的方法构造出来的整数实质上已经不是整数,不过一串字符而已。

添加新评论 »


© POWERED BY TYPECHO 
THEME SIMPLEONE 1.3 BY TYPECHO CLUB