前些日子查资料的时候发现逻辑学家 George Boolos (不是 boolean 类型的 George Boole) 曾经给出过 Gödel 定理的一个新证明. 看了之后觉得十分有趣.

Review of Gödel's Proof

关于 Gödel 的原始证明, 网上已有许多解释, 如刘未鹏的这篇文章. 这里再从数理逻辑角度简单回顾一下, 因为 Boolos 的证明用了许多 Gödel 的思想.

证明的第一步是建立 Gödel Numbering, 也即建立一套编码系统, 使得形式系统中任意公式可与自然数一一对应. 这种思想及其方法在有了计算机的今天是十分轻易的, 在 Gödel 的文章里, 他用了不同素数表示形式系统中的最基本符号, 从而实现了这一点, 这种方法后来被称为 Gödel Numbering.

没错, 这篇文章其实是 Cantor, Gödel, Turing 这个主题. 我发现只要关于他们的东西都很容易让我看 high..

最近在看那本 The Annotated Turing. 书中第三章以 David Hilbert 为主线, 介绍了 20 世纪初的几十年里数理逻辑与集合论的发展. 想一想的话, Hilbert 的确是将 Cantor, Gödel, Turing 联系起来的关键人物, 然而这段历史我以前知道的并不细致, 而且关于 Hilbert's Program, Hilbert's Problems 的故事各个地方说的都乱七八糟的自己也不清楚了, 于是做个记录.

在翻 Matrix67 的思考的乐趣的时候, 看到集合论那里, 依次证明了有理数, 代数数, 可计算数, 可定义数的可数性, 甚舒畅. 然后用经典的 Cantor's Diagonal Argument 证了实数的不可数性, 并说明了此方法对有理数不可用, 因为对角线生成的新数未必是有理数.

然后我想, 对角线法用在可计算数上似乎也可以啊.. 假设可计算数可数, 排成一列 之后, 按照对角线法取出一数, 保证取出数 满足 , 则 也没有被列出. 而进一步, 如果我们规定取数时的对应法则 , 令 无不动点, , 那么取出的新数也就是可计算的了. 那按照 Diagonal Argument, 可计算数不就不可数了?