100囚犯问题、100囚犯问题加强版与选择公理(下)

    无穷个囚犯面向数轴的正方向依次就座,第i个囚犯坐在数轴上坐标为i的地方,他可以看见所有坐标大于i的囚犯头顶上的帽子。看守给每个囚犯戴上黑色或白色的帽子,然后依次叫每个囚犯猜测自己头上的帽子颜色,猜对了的予以释放。另外一点和原来不同的是,囚犯们不能听到其他人的猜测。另外注意到,由于每个人前面都有无穷多个人,因此囚犯们无法通过数他前面的人数来判断出自己的位置,于是我们不得不加上一句:每个人都知道他后面有多少人(即他是第几个被问的)。同样地,事先所有囚犯可以商量出一个策略。你认为这下囚犯们还有什么好办法没?
    这下囚犯已经不能通过自己的猜测来通风报信了,似乎每个人都只能瞎猜,任何人都无法保证自己能猜对。你相信吗,居然有这样的策略,它可以保证除了有限个囚犯之外,其他囚犯全部释放!
    考虑所有可能的颜色序列(你可以简单地想像成01串)。我们说两个颜色序列“无穷远相等”,如果经过了有限多项之后,余下的无穷多项完全相同(即存在某个数x,使得两个串在各自的第x位后面完全重合)。这种关系显然满足自反性、对称性和传递性,是一种等价关系。因此,按照这种有限位后对应相等的关系,我们可以把所有可能的颜色序列划分为一个个等价类。它们的交集为空(两个等价类如果有交集,由传递性它们立即并成了一个更大的等价类),并集为全集(若某序列不属于任何等价类,则它自己就是一个新的等价类),是全集的一个划分。你能想象出一个等价类大致是什么样子的吗?假如把同一个等价类里的所有序列对齐并排放在一起,你从前往后走过去的时候会发现这些序列“越来越相像”。你走得越远,你会发现越来越多的序列开始变得互相重合;当你走到无穷远时,所有的序列都变成一个样了。
    囚犯们事先在每一个等价类中选一个代表元,然后把所有等价类的代表元背下来。到时候,每个人都能够看到他前面无穷多个人的帽子颜色,并且知道他自己在整个序列的位置,于是能立即判断出他们现在所处的颜色序列在哪个等价类里。接下来,他们只需要按照事先背好的代表元来猜就行了。由“无穷远相等”的定义,经过有限次猜测后最终这个代表元会和他们所处的序列重合,于是除了前面有限多个人以外,以后无穷多个人都可以保证猜对。

    你是否觉得这种“策略”很不合理,虽然从逻辑上看每一步推理都是无懈可击的?有人认为,这是选择公理带来的悖论。选择公理是说,给你一系列的集合(可能有无穷多个),那么我们总可以在每一个集合里取出一个元素来。这并不是显然正确的。你不可以依次考虑每个集合,从里面随便取出一个元素来,因为集合个数有可能无穷多个(甚至不可数),这样的操作将永无止境,不允许出现在数学推理过程中。我们需要定义一套系统,使得它对于给定的每一个集合都适用,这样我们就可以“一下子”处理完所有的集合。换句话说,对于一组数量任意多的集合,我们需要定义一个函数f,使得对其中任一集合S,f(S)为S里的一个元素。我们称函数f为选择函数。例如,给出自然数集的所有子集,选择函数f可以定义为“集合中的最小元素”;给出实数集的所有有限长的区间,则选择函数f可以定义为“区间的中点”。但对于某些情况,目前还没有办法用之前已有的公理系统定义出合适的选择函数。比如,目前仍然不清楚,对于实数集的所有非空子集是否存在一个选择函数。但选择函数的存在是很多数学推理的前提假设。因此,我们有必要承认选择公理,构成新的公理体系(即ZFC公理体系)。于是在今后的数学推理中,我们可以假设存在这样一个超级选择函数f,它就是专门用来干这破事的。承认选择公理有可能推出一些与生活经验背道而驰的结论,最著名的就是Banach-Tarski悖论:你可以把一个三维球体分成有限多块,然后拼接组合成两个和原来一样大的球体。上面所提到的100囚犯问题加强版则是选择公理带来的另一个悖论。

参考资料:http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong (墙就是强)

14 条评论

  • Eagle_Fantasy

    我怎么觉得这种策略挺合理呢…

  • dahe_1984

    迷糊………..[sad]

  • Voldemort

    囚犯要记忆无限多的信息啊。

  • sqybi

    显然这个下我没看懂…

  • cosechy

    有无穷多个等价类,所以很难判断。。
    要是特别简单的等价类,比如全一样或者循环,那当然可以保证无限的人被释放
    不过有个问题是无限的人被释放不代表只有有限的人不被释放

  • lsz

    无穷多个等价类,每个等价类的代表元又有无穷多个01编号……显然囚犯是没法记住的。所以也就没有这个悖论了吧?

  • user

    考虑所有可能的颜色序列(你可以简单地想像成01串)。我们说两个颜色序列“无穷远相等”,如果经过了有限多项之后,余下的无穷多项完全相同(即存在某个数x,使得两个串在各自的第x位后面完全重合)
    ____________________________________________________
    这个在推理上明显有问题,假定串A为1111….的序列,串B为0000……的序列,有哪一个数X,使得两个串在x位后完全相等?

  • Icewolf

    这个证明好像有问题。每一个等价类都有无穷多个序列,因此对任何一个囚犯来说,符合要求的等价类里的序列都大于1个,因此他猜错的可能性都大于零。也就是说,有无穷多个囚犯会猜错。等价类只有在无穷远处才相等。

  • ATMxsp01

    这个结论的问题是不是在于等价类的“无穷远相等”啊
    从定义上看,等价类中每一个元素只有在无穷远处才是完全相等的,也即只有在无穷远处囚犯才能猜对,然而从一到无穷大显然有无穷大个元素,也就是说有无穷多的囚犯只能猜;
    从另一个方面说,我们来看第一个囚犯,他看到了前面的囚犯帽子的颜色,从而得知了所在序列的等价类,然而这等价类中有两种可能,区别只在他头上帽子的颜色不同,因此,他猜对的几率为1/2,再看第二个囚犯,他看到前面的囚犯帽子的颜色,从而得知了所在序列的等价类,然而这等价类中有四种可能,区别只在他和第一个囚犯头上帽子的颜色不同,而第一个囚犯帽子的颜色对他没有实际影响,所以他猜对的几率也是1/2;继续推下去,所有囚犯猜对的几率都是1/2,事实上,这个结论对无穷远处的囚犯也是成立的,因此,这种策略并不能达到目标

  • www.tongbao218.com

    一个人是在对周围生活环境的反抗中创造成功的。

  • 烦啦

    好像可以用 timing attack 的思想(参见 meltdown 漏洞)

发表评论