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

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

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

查看更多 »

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

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

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

查看更多 »

    在准备前一篇日志时，我查阅了很多经典的悖论。我发现，虽说数学悖论大多是一些让人越想越糊涂的逻辑思维游戏，但也有不少悖论来自于实实在在的数学问题。在缺乏现代数学工具的年代，这些反直觉的结论和看似不可调和的矛盾让数学家们百思不得其解，那些最难解决的悖论甚至为数学新分支的开创带来了足够的动机。不太为人熟知的 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 个点是两条三次曲线所共有的，那它们究竟会“唯一地”确定出哪条曲线呢？在没有线性代数的年代，这是一个令人匪夷所思的问题。

查看更多 »

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

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

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

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

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

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

查看更多 »

    最近看到几个有趣的数学谬证，想写下来与大家分享；结果写到这个又想到那个，一写就写个没完，于是想到干脆做一篇谬证大全，收集各种荒谬的证明。
    如果你有什么更棒的“证明”，欢迎来信与我分享，我会更新到这篇日志中。我的邮箱是 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 的。

查看更多 »

视频链接：http://www.tudou.com/programs/view/YP7twFzOA3A/

查看更多 »

    承认选择公理可能给我们带来很多有悖于直觉的结论。最著名的例子可谓 Banach-Tarski 悖论了：你可以把一个三维的实心球分成有限多块，通过刚体移动把它变成两个和原来一模一样的球。本 Blog 还介绍过另外一个有趣的结论，它违背常理的程度也不亚于 Banach-Tarski 悖论。今天，我给大家看一个比这些悖论更加荒唐的结论：利用选择公理，我们可以实现预测未来！

    在探讨这个话题之前，我们得先为“预测未来”建立一个合理的数学模型。我们假设，对于任一时刻，宇宙中的所有信息都可以编码为某个状态值，我们就把它叫做宇宙的一个“点状态”。宇宙中所有可能的点状态就组成了宇宙的“状态集合”。以数学的眼光看宇宙，一个宇宙也就无非是一个一元函数 f(t) 。它的定义域是整个时间轴 R ，它的值域是宇宙的状态集合，预测未来也就仅仅是根据已知的函数值来推测未知的函数值罢了。假设我们已经知道在区间 (-∞, t0) 上函数的所有取值，如果你能据此给出 f(t0) 的精确值，我们就说你成功地预测了 t0 时刻的宇宙状态。当然，仅凭借过去的信息你是不可能保证猜对 t0 时刻的点状态的，例如对于两个只在 t0 处有区别的宇宙，算法最多只能猜对其中一个宇宙在 t0 处的状态。但你相信吗，存在一个算法，使得我能正确预测几乎所有时间点的宇宙状态。换句话说，我能构造出这样一个算法，使得除了可数个点以外，给定任意一点以前的全部函数值，我都能套用该算法猜对该点的点状态。再换句话说，利用这个算法预测任意时刻的宇宙状态，成功的概率为 1 。

查看更多 »

    大家或许知道 Banach-Tarski 悖论——把一个三维球分成有限多份并重新拼成两个和原来一模一样大的球——这个悖论告诉我们利用选择公理我们能够推出看上去多么不合逻辑的东西。今天我听说了另一个类似的悖论叫做 Sierpinski-Mazurkiewicz 悖论，它的结论在直观上同样令人难以接受，并且推导不依赖于选择公理。
    Sierpinski-Mazurkiewicz 悖论是说，存在平面上的一个点集 S ，我们能把它划分成两个子集 A 和 B ，使得 A 旋转 1 弧度后与 S 完全重合， B 平移一个单位后也与 S 完全相同。换句话说，存在这么一个点集，我们能把它分成两个与自身一模一样的子集！这听上去实在是不可思议，然而构造却极其简单。

查看更多 »