一点儿悖论
在读《可能与不可能的边界》 [^1] 时，有这样一个命题：
There is no proof that this sentence is true. [^2]
即「没有证据能证明这句话是真的」。仔细思考一下，你会看出来这是一个悖论。
悖论对很多人来说都不陌生，也许大部分人都可以随口讲出几个。比如
「这句话是假的」就是最典型的悖论之一。我小时候曾经读到过一个故事，讲的是一个商人被强盗打劫，强盗对商人说，「你可以猜一猜我会杀了你还是放了你，如果猜对了我就放你走」。聪明的商人说，「我猜你会杀了我」。如果强盗真的杀了商人，那么商人就猜对了，强盗就得放了他；如果商人猜错了，那么强盗也是要放了他的。所以强盗陷于自己的悖论中，只能让商人离开。
这并不是我第一次接触到「悖论」，但这个故事令我印象深刻。它对年幼的我来说十分有趣，同时也令我怀疑，如果强盗这么讲道理，为什么还要做强盗。
这里我还想说另一个可能不是那么广为人知但是很有趣的悖论。1902年，弗雷格已经发展了一整套形式逻辑语言，并撰写了两卷著作阐述如何利用《概念文字》的逻辑发展处自然数的算术。而一个也许是他最著名的读者，罗素，写信提出了一个疑问。在弗雷格的工作中曾经使用了「集合的集合」这一概念[^3]，罗素指出，这个概念的使用很容易产生悖论。
罗素把包含自己的集合成为异常的，否则就是正常的集合。比如「所有那些能够用数目少于19的英文单词定义的东西组成的集合（the set of all those things that can be defined in fewer than 19 English words）」就是一个异常的集合。或者更简单的，「所有不是麻雀的东西所组成的集合」也是一个异常集合。那么问题来了：「所有正常集合组成的集合是正常的还是异常的？」如果它是正常的，那么它属于它自身，导致它的异常；反之如果它是异常的，它也应该属于它自身，但异常集合不能属于它自身。悖论产生了。
我们现在看来，这个悖论的构造过程是很有趣的，但弗雷格的毕生成就几乎尽毁于此。事实上尽管他非常正直的在第二卷著作出版时紧急地发表了声明来阐述这个问题，但他再也没有从这个打击中恢复过来。
所谓的「悖论」，是指会产生矛盾的命题。就是说「如果它是真的，那么会它就是假的，反之亦然」。但说出来你可能不信，开始的那个命题并不是一个悖论，而是一个真命题。
假设它为假，即有证据证明它是真的，那么它就应该是真的，和假设矛盾，因此它是真的。
这是一个典型的反证法流程：提出假设，根据假设推出矛盾，完成证明。你也许会说，我们找到了一条证据，证明这个命题是真的，但它的「真」本身导致了矛盾，因此这是一个悖论。
关于这点，书中给出的解释是：
我们并没有完全证明那个命题是真的，因为不得不首先假设所有能被证明为真的命题都确实是真的。哥德尔也表明，我们不能证明『所有能被证明为真的命题都确实是真的』。
也就是说，刚才的反证法并不能证明这个命题为真，也就是说这条证明并不是一条「证据」。这个说明有一些晦涩，它似乎挑战了一些基本判断的合法性。我给出另一个解释：
如果刚才的反证法成立，那么会推出矛盾，即我们在证明它是「真」的同时也证明了它是「假」。因此这条证明并不是「能证明这句话为真的证据」。即我们没有证明这条命题是真的，但证明了它肯定不是假的。如果我们承认此命题为真，并且此命题不可能被证明，那么也不会有任何矛盾产生，这个命题就是自洽的。
在《牛津通识读本·数学》[^6] 中讨论排序算法的比较次数时有这么一段描述：
这种论证的麻烦在于，要考虑的情况数量会急剧增加。譬如当对象有100个时，需要比较的确切次数是不可能算出来的——几乎可以确定这个数永远无从得知。（我犹记得，当我第一次听一位数学家宣称某个特定量的确切值永远无法算出，我当时有多么震惊。但现在我已经习以为常了，这是常有的事，并不是特殊情况。...) [^3]
我在读到这里的时候，和作者一样，感到很震惊，而且是双倍震惊。首先和作者一样，我震惊于居然存在一个特定量无法被确切地计算出；然后又被「这是常有的事」震到了。所以当我得知哥德尔构造了这个命题由，实际上是证明了「存在无法被证明为真的真命题」的时候，又一次感受到了这种不确定性带来的震动。
我去翻阅了《逻辑的引擎》[^4] ，里面讲述了哥德尔的这段故事，但这个故事要从希尔伯特讲起。彼时康托尔已经发展出了一套「无限集合」的理论，但被数学界的一部分人（包括万能的高斯）强烈反对。尤其是在前面提到的罗素悖论之后，人们对于数学和逻辑产生了极大的危机感，而希尔伯特尝试证明实数算数的一致性[^5]，并作为康托尔的支持者，坚定地要把康托尔的「超限数」包括进来。这个问题最终就是被康托尔解决。但哥德尔证明了在这个系统内，存在无法被证明的真命题（还记得开头的那个命题吧）。并以此为基础证明，系统的一致性无法被证明。这和罗素悖论很相似，哥德尔本来希望自己能够支持希尔伯特的理论，但没想到自己亲手葬送了希尔伯特纲领。
希尔伯特一直是一个极其乐观的人。他曾宣称，所有的科学家都深信，每一个明确的数学问题都必定可以完全得到解决，这一信念是对他们工作的巨大鼓舞。在一次会议的演讲中，在他表述了数学在科学中的重要性，以及逻辑在数学中的重要性之后，他强调了自己的信念，即「不存在不能解决的问题」。他这样结束了自己的演讲：
Wir müssen wissen
Wir werden wissen
这段话也刻在了他的墓碑上。
我们必须知道，
我们终将知道。
[1] 如果你是豆瓣阅读用户，我不推荐这本书的电子版本。因为其中有不少的数学公式排版的错误和缺失。虽然有些电子书会在修订后推送更新，但在我反馈之后一个月的今天为止，都还没有修订。
[2] 《可能与不可能的边界》，7.1「骗子悖论」
[3] 这里他使用「集合」来表明自然数，比如自然数3就是所有个数为3的事物的集合。而一个给定集合的元素数目被定义为「能够与给定集合一一对应的所有那些集合的集合」
[4] 《数学》，第七章 估计与近似
[5] 所谓的一致性，即是说在这个系统内得出的任何结论都不会彼此矛盾
[6] 这本书很值得推荐，尤其对于喜欢《量子物理史话》这种书的读者。你可以看到数学尤其是逻辑学的发展中面临的各种危机，以及历史浪潮中诞生的各种英雄人物。张卜天先生的翻译极佳，由于原作者的数学知识背景，这本书的语音风格非常严谨，你在阅读的时候能感受到其数学定理一般严丝合缝的快感。但同时，也继承了数学语言晦涩难懂的部分，如果你要读懂每句话，那么很可能读起来不那么畅快（也许会让你感到智商上的卑微）。所以我从来没有读完过。此外罗素悖论的描述也出自此书。
