今天听说了 Fitch 可知性悖论，在这里给大家讲一讲。这是由美国逻辑学家 Frederic Fitch 在 1963 年的一篇论文中提出来的。在这篇论文中， Fitch 利用严密的数理逻辑得出了一个看上去很不可思议的结论：假设所有知识都是人类有可能掌握的，那么所有知识都已经被人类掌握了。

    为了表达“能掌握的知识”这一概念，我们需要用到模态逻辑。模态逻辑中允许出现这样一种情况：一个命题是假的，但是它有可能是真的。比方说，命题“一加一等于三”是假的，而且它不可能是真的；命题“朝鲜在 2010 年世界杯中获得冠军”是假的，但它却有可能是真的。这两种情况的区别可以从平行宇宙的角度来解释。前者可以在逻辑上被推翻，在任何一个平行宇宙中都不成立；后者虽然在我们的世界中是假的，但却不排除在其它世界中为真的可能。在模态逻辑中，“明天可能会下雨”也能成为一个合法的命题。

    下面，我们用 K(φ) 表示人类已经知道了 φ 为真（也就是说 φ 在人类的知识库中）。因而， ¬K(φ) 就表示人类不知道 φ 。再用 P(φ) 表示 φ 有可能为真（在至少一个平行宇宙中成立）。因而， ¬P(φ) 就表示 φ 不可能为真，P(K(φ)) 就表示人类有可能知道 φ 为真。我们作出以下四个假设：

Read more…

    今天听说了一个非常有趣的思想实验——超级游戏（ Hypergame ，暂且让我翻译成“超级游戏”吧）。首先，如果一个游戏能在有限步之内分出胜负，我们就把它叫做“有限游戏”。注意，一个有无穷多种状态的游戏也可以是有限游戏。虽然每一步的决策无穷多，但只要能在有限步内结束游戏，我们都把它叫做有限游戏。举个例子，玩家 1 和玩家 2 游戏，玩家 1 说出任意一个正整数 N ，然后立即获胜。这个游戏的决策有无穷多，但它显然是有限游戏。另外，一个有限游戏的总步数甚至也可以没有上限。比如说，玩家 1 说出任意一个正整数 N ，然后玩家 2 说 N – 1 ，玩家 1 说 N – 2 ，以此类推，两人轮流倒数，谁数到 0 谁就获胜。结束这个游戏所需要的步数可以是任意多，但只要是有限的，我们都把它叫做有限游戏。

    下面，我们来看这个叫做“超级游戏”的游戏。在超级游戏中，首先，玩家 1 指定一个有限游戏，然后玩家 2 作为这个有限游戏的先行者与玩家 1 对弈。谁赢得了这个有限游戏，也就是这局超级游戏的获胜者。

    这个异想天开的游戏可以说是一下子打开了我们的思路，很多再正常不过的事情此时都变得有争议了。比如说，超级游戏的决策树是什么样子的？超级游戏算是组合游戏吗？甚至是问，超级游戏本身是一个有限游戏吗？

Read more…

    在准备前一篇日志时，我查阅了很多经典的悖论。我发现，虽说数学悖论大多是一些让人越想越糊涂的逻辑思维游戏，但也有不少悖论来自于实实在在的数学问题。在缺乏现代数学工具的年代，这些反直觉的结论和看似不可调和的矛盾让数学家们百思不得其解，那些最难解决的悖论甚至为数学新分支的开创带来了足够的动机。不太为人熟知的 Cramer 悖论就是一个漂亮的例子。

    在描述 Cramer 悖论之前，让我们先来考虑一个简单的情况。两条直线交于一点。反过来，过一点可以做两条不同的直线。事实上，过一点可以做无数条直线。确定一条直线需要两个点才够。一切都很正常。
    现在，考虑平面上的两条三次曲线。由于将两个二元三次方程联立求解，最多可以得到 9 组不同的解，因此两条三次曲线最多有 9 个交点。另外，三次曲线的一般形式为

      x^3 + a·x^2·y + b·x·y^2 + c·y^3 + d·x^2 + e·x·y + f·y^2 + g·x + h·y + i = 0

    这里面一共有 9 个未知系数。代入曲线上的 9 组不同的 (x, y) ，我们就能得出 9 个方程，解出这 9 个未知系数，恢复出这个三次曲线的原貌。也就是说，平面上的 9 个点唯一地确定了一个三次曲线。这次貌似就出问题了： “两条三次曲线交于 9 个点” 和 “ 9 个点唯一地确定一条三次曲线” 怎么可能同时成立呢？既然这 9 个点是两条三次曲线所共有的，那它们究竟会“唯一地”确定出哪条曲线呢？在没有线性代数的年代，这是一个令人匪夷所思的问题。

Read more…

（注：本文纯属搞笑，请勿当真）

理发师常论：一个理发师只给别人理发。

说谎者常论：我刚才说的是谎话。

Berry 常论：最小的能用 20 个以内的汉字描述的正整数。

万能上帝常论：上帝是万能的，他甚至为人类创造了一个“万能上帝悖论”，搞得大伙儿现在还在纠结中。

突击测验常论：老师决定在周一至周五的某一天进行一次出其不意的测验，但是他没有告诉学生。测验当天，所有学生都没有预料到。

Read more…

    最近看到几个有趣的数学谬证，想写下来与大家分享；结果写到这个又想到那个，一写就写个没完，于是想到干脆做一篇谬证大全，收集各种荒谬的证明。
    如果你有什么更棒的“证明”，欢迎来信与我分享，我会更新到这篇日志中。我的邮箱是 matrix67 at tom.com ，或者 gs.matrix67 at gmail.com 。

1=2？史上最经典的“证明”

    设 a = b ，则 a·b = a^2 ，等号两边同时减去 b^2 就有 a·b – b^2 = a^2 – b^2 。注意，这个等式的左边可以提出一个 b ，右边是一个平方差，于是有 b·(a – b) = (a + b)(a – b) 。约掉 (a – b) 有 b = a + b 。然而 a = b ，因此 b = b + b ，也即 b = 2b 。约掉 b ，得 1 = 2 。

    这可能是有史以来最经典的谬证了。 Ted Chiang 在他的短篇科幻小说 Division by Zero 中写到：

There is a well-known “proof” that demonstrates that one equals two. It begins with some definitions: “Let a = 1; let b = 1.” It ends with the conclusion “a = 2a,” that is, one equals two. Hidden inconspicuously in the middle is a division by zero, and at that point the proof has stepped off the brink, making all rules null and void. Permitting division by zero allows one to prove not only that one and two are equal, but that any two numbers at all—real or imaginary, rational or irrational—are equal.

    这个证明的问题所在想必大家都已经很清楚了：等号两边是不能同时除以 a – b 的，因为我们假设了 a = b ，也就是说 a – b 是等于 0 的。

Read more…