About
RSS

Bit Focus


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

Posted at 2012-09-14 10:05:30 | Updated at 2018-05-25 13:37:11

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

无限集的数量概念

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

常见于对角线方法的误解

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

    上述描述容易导致如下的误解
    看这个看多了, 久而久之当然就不确信对角线方法的靠谱度.

勘误

问题描述

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

证明

    第二个误解不过因为大部分凡人数学家将自己限制到无论什么都得眼见为实, 对于搞数学这确实不是个好事情, 不过有些人 (譬如我) 就爱这样搞. 如果不喜欢, 只须谨记: 只要否定皇帝新衣的不可见性, 它就是可见的. 这才是超凡逻辑学家应有的节操.
    那么证法变为如下
    这个方法是个典型的非构造方法, 证明中只是 "声称" 存在某个子集, 但并不给出构造方式与构造结果, 同时如果询问这个集合具体有什么东西则不会有任何结果 (就像 Java 里面实现了 Setcontains 但是 iterate 方法直接抛异常一样), 它只能判别某个东西是否存在于这个集合中.
    但无论怎么说, 这样就澄清了上述的两点误解.

Post tags:   Diagonal Argument  Set Theory  Power Set

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


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