网友Gestorm在TopLanguage里问到，如何构造一个[0,1]到(0,1)的一一映射。两个集合的势显然相等，它们之间一定有一个一一对应的函数。注意到(0,1)是[0,1]的子集，利用Cantor-Bernstein-Schroeder定理，只要我们能找到一个从[0,1]到(0,1)的单射函数，我们便找到了两个集合间的双射函数（因为上述定理的证明是构造性的）。这非常简单，例如f(x)表示x与0.5的平均数即可。考虑上述定理的Julius König证明，我们立即得到一个[0,1]到(0,1)的一一映射：f(0)=1/4, f(1/4)=3/8, f(3/8)=7/16, ...，不断进行(x+1/2)/2的迭代；同样地，f(1)=3/4, f(3/4)=5/8, f(5/8)=9/16, ...；对于其它所有未定义到的x，f(x)=x。这个函数显然是双射的。
    仔细观察这个函数。当你领会到这个函数的真谛时，你突然恍然大悟：我可以用类似地办法弄出无穷多个[0,1]到(0,1)的一一映射。例如，最简单的便是f(0)=1/2, f(1)=1/3；然后f(1/2)=1/4, f(1/3)=1/5, f(1/4)=1/6, ..., f(1/i)=1/(i+2)；对于其它未定义的x，f(x)=x。
    查看TopLanguage的原帖可以看到一些类似的结果。

    明天考英语，单词还没背。先冒死更新一个^_^
    我们称一个从集合A到集合B的映射是“单射”的，如果A中的任两个相异元素都不会映射到B里的同一个元素。如果一个A→B的映射是单射的，并且B里的所有元素都被射了（满射），那么这个映射就是“双射”的。Cantor-Bernstein-Schroeder定理是说，假如存在一个从集合A到集合B的单射函数f，以及一个从集合B到集合A的单射函数g，那么A与B之间一定存在一个双射函数（即能建立起一一对应的关系，两个集合有相等的势）。这个结论并不是显然的。对于无穷集合，我们可以构造出很多这样的例子，两个映射A→B和B→A都是单射，但都不是满射的。例如，给定一个正方形和正方形外的一条直线，把正方形放到直线上滚一圈所形成的对应关系是一个从正方形上的所有点到直线上的点的一个单射函数，而连接直线上的点和正方形一边中点后与正方形的另一个交点构成了一个从直线到正方形的单射关系（如图）。那么，根据Cantor-Bernstein-Schroeder定理，我们一定可以找到一种函数，使得直线上的所有点和正方形上的所有点有一一对应的关系。

查看更多 »

    无穷个囚犯面向数轴的正方向依次就座，第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 （墙就是强）

    康托集合是闭区间[0,1]的子集，它的定义如下：给定区间[0,1]，把这个区间分成三段，去掉中间那一端（即去掉(1/3,2/3)），然后把剩下的两段中每一段都按照刚才的方法再进行操作，然后再分，再分，就这样一直挖洞挖下去。在第二次操作后，剩下的区间是[0,1/9]∪[2/9,1/3]∪[2/3,7/9]∪[8/9,1]，再操作一次后区间将由8段构成。最后剩下来的东西是什么呢？你能找到存在于这个集合中的某个具体的元素吗（不包括形如x/(3^n)的端点）？
    我们看到，n次操作后，区间的总长度为(2/3)^n，当n趋于无穷时，区间长度趋于0。但是这并不能说明这个区间里没有任何元素。事实上，我们可以找到至少一个元素。比如，下图中绿色的点表示三等分点，如果P满足AP/AB=A'P/A'B'的话，那么P点始终以比例相同的位置留在某一段上，这样的话即使无限地分下去也不会把它挖掉。
      
    P点的坐标可以通过解这个方程得到：x/1=(x-2/9)/(1/9)。解出来x为1/4。因此，1/4属于康托集合。当然，除了1/4之外还有很多点在这个集合内，我们只是找到了其中一个。事实上，康托集合内的元素有无穷多个。假如我们把所有0到1的数用三进制表示，那么我们发现，去掉的部分都是三进制小数里有数字“1”的。比如，第一次操作时，1/3和2/3的三进制分别是0.1和0.2，我们去掉的是所有从0.1到0.2的数（不包含端点，因为0.1也可以写成0.0222222222...）。第二次操作就去掉了百分位有1的那些数，依此类推。因此，只要一个位于0和1之间的三进制小数能够只用0和2写出，那么它就属于康托集合，因为它永远不会被去掉。刚才的1/4转化为三进制是0.020202...，因此它属于这个集合。显然，这样的数有无穷多个，比如三进制0.002002002...等于十进制的1/13，因此它也属于康托集合。同样，康托集合里不存在孤点，因为在它的左右可以找出无数个属于康托集合的数。应用对角线方法，这个集合里的元素居然还是不可数的。事实上，我们可以建立康托集合与闭区间[0,1]的一一对应关系。
    用以下方法可以把康托集合里的所有数与[0,1]的所有实数对应起来：将康托集合内的任意一个转化为三进制小数后，把每一个数字除以2，再当成是二进制小数转化回来。由于这些三进制小数里只含0和2，因此康托集合里的每个数都恰好能转化为一个[0,1]之间的二进制小数；同样地，二进制小数里的每个“1”变成“2”后也能得到一个康托集合里的数。
      
    设f为定义域在康托集合内的函数，定义f(x)为按照上面的转化方法x所对应的二进制小数，显然这个函数的值域就是[0,1]。比如1/3的三进制为0.0222...，而二进制0.01111...=0.1即十进制的1/2，因此f(1/3)=1/2。我们发现，2/3的三进制为0.2，而0.1的十进制也是1/2。于是f(1/3)=f(2/3)。类似地，那些被挖去的区间的两个端点对应的函数值都相同。现在，我们把这个函数的定义域也扩展到[0,1]：让康托集合里的那些被挖去的区间里的点的函数值与该区间对应的端点相同（在函数图象上看相当于把函数值相等的点用横线段连起来）。于是，f(1/2)=f(1/3)=f(2/3)=1/2，f(1/8)=f(1/9)=f(2/9)=1/4。这个函数一定是上升函数，它在长度为1的区间里从0增长到了1。同时，这个函数也是一个连续函数，因为康托集合与[0,1]的所有实数一一对应。这个函数是一个阶梯状的函数，但是它不是分段的，是连续的。它是无穷多个横线段组成的一个连续函数，除端点无意义以外导数值都是0。或者说，这个函数在不变之中上升。

做人要厚道
转贴请注明出处